Grid A*：面向野外空地协同应急处置的快速路径规划算法

Grid A*：面向野外空地协同应急处置的快速路径规划算法 Grid A*：A Fast Path Planning Algorithm for Air-Ground Cooperative Response of Emergency Rescue in the Field 1 first-author 王修远（1992— ）， 男， 硕士研究生， 研究方向为地表可通行性分析与路径规划。E-mail： adhamwang@pku.edu.cn。 王修远（1992— ）， 男， 硕士研究生， 研究方向为地表可通行性分析与路径规划。E-mail： adhamwang@pku.edu.cn。 adhamwang@pku.edu.cn 1 corresp 孙敏（1968— ）， 男，副教授，硕士生导师，从事无人机遥感与数字摄影测量学研究，E-mail：sunmin@pku.edu.cn。 孙敏（1968— ）， 男，副教授，硕士生导师，从事无人机遥感与数字摄影测量学研究，E-mail：sunmin@pku.edu.cn。 sunmin@pku.edu.cn 1 1 2 北京大学 遥感与地理信息系统研究所, 北京 100871 北京大学 遥感与地理信息系统研究所, 北京 100871 Institute of Remote Sensing and Geographical Information System, Peking University, Beijing 100871, China Institute of Remote Sensing and Geographical Information System, Peking University, Beijing 100871, China 冀北中原岩土工程有限公司, 廊坊 065001 冀北中原岩土工程有限公司, 廊坊 065001 JIBEIZHONGYUAN Geotechical Engineering co.,LTD, Langfang, 065001, China JIBEIZHONGYUAN Geotechical Engineering co.,LTD, Langfang, 065001, China 在野外应急救援活动中，灾害现场或事故区域通常缺乏地面交通工具可直达的现成道路，但该区域地表环境仍可满足部分越野车辆的通行。在空地协同系统中，无人机可提供行进路径周边环境的影像，地面终端可快速提取影像中地表类型以及地形起伏等特征信息，通过分析计算便可为车辆提供通往救援目标点的导航路径。本文针对这一应用需求，对现有A*算法进行了改进，主要有三个方面的创新：其一、针对户外地表环境的应用特点，提出一种综合地表类型与地表高程信息的通行性代价函数；其二、针对无人机影像分辨率与实际车辆通行路径之间的尺度关系，提出一种基于格网单元的路径快速搜索算法；其三、在顾及格网单元内部地表类型连通分布特点的基础上，选择格网边缘特征点用于通行性路径规划，在提高算法搜索效率的同时，兼顾了格网单元内部的地形信息，从而使算法在优化计算的同时，能充分利用到无人机影像的细节信息。实验表明，算法搜索得到的可通行路径具有较高的可靠性，从路径三维可视化结果来看，符合越野车辆通行的需要。此外，同等情况下，本算法的运行时间降至传统A*算法的15%，提高了野外应急救援应用的时效性。 Objective Disasters and accidents often occur in remote areas that are inaccessible by common transportation. Common map navigation software also fails to provide a passable path. Therefore, only SUVs can be used in field rescue. However, ground vehicles have limited awareness of their surroundings, so we chose to set up an air-ground cooperative system to overcome vehicles’ shortcoming. In the air-ground cooperative system, the UAV can provide environmental images surrounding the SUV for the ground terminal to obtain the navigation path of the vehicle by quickly extracting the type of surface and terrain undulations in the images.Method To better meet the above application requirement, this paper improves the existing A* algorithm with three main innovations. First, we proposed a passability cost function that integrates surface type and surface elevation information considering the application characteristics of outdoor surface environment. Second, we proposed a fast path search algorithm based on grid cells given the scale relationship between the resolution of UAV images and the actual vehicle paths. Third, we chose the marginal feature points of the grid for the passability path search in view of the connected surface type distribution inside the grid cell, which improves the search efficiency of the algorithm while taking into account the terrain information inside the grid cell, so that the algorithm could make full use of the detailed information of the UAV images and optimize the calculation.Result The 3D visualization experiments show that the paths searched by Grid A* algorithm are more reliable and meet the needs of SUVs.Conclusion The Grid A* algorithm proposed in this paper, aiming at the high-resolution images obtained by UAV, synthesizes image classification, slope calculation and other methods to structure a passability cost function, so that the paths are more reliable. In addition, the time cost of the algorithm is reduced to 15% of the traditional A* algorithm, which improves the timeliness of emergency rescue in the field. 路径规划算法，Grid A*算法，A*算法，空地协同，通行性 Path planning Grid A* algorithm A* algorithm Air-ground coordination Passability cost function 1　引 言 1 在地理信息科学、计算机科学等领域中，路径规划的研究一直有着非常重要的理论和应用价值。在传统的路径规划与导航方面相关的应用相当成熟，如车辆导航系统，当周边路网环境已知时，可以快速地规划出从起始点至目标点的比较合理的路线。但是在城市以外的许多野外环境，由于缺乏道路，较难使用现有的算法进行路径规划。例如在应急救援、军事行动等活动中，工作场景常常是地形复杂多样且无人工道路的野外环境。在这些环境中的路径规划任务并不像传统的路径规划任务一样有现成的道路信息可以使用，此时传统的路径规划方法难以发挥作用，故需要使用新的策略进行路径规划。 在没有矢量路网的情况下进行路径规划，主要的受制因素是地面车辆对周边环境有限的感知能力，导致其无法在更大的范围了解周边地表环境信息。为了弥补地面车辆视野小的缺陷，可以使用空中的观测平台（如无人机，UAV）作为辅助手段扩充视野范围，获取必要的环境信息，这种地面端与无人机平台协作完成任务的方式即为称为空地协同系统。 空地协同系统近年来在目标检测与跟踪以及路径规划等领域有着广泛的应用。针对地面端行进路径规划需求，无人机通常被用来获取周边地形信息。 如：Choi K.等（2009； 2012）设计的系统中，由无人机获取的影像快速生成高分辨率的DEM、正射影像等空间信息，为地面行动提供详细的地图信息，但其工作仅限于地面信息的快速获取与处理，并没有进行路径分析，无法直接引导地面车辆通行。Li J.等（2016）利用UAV获取地面影像，并提出了一种基于栅格数据的混合路径规划算法为地面无人车（UGV）提供可通行路径。但其实验仅在室内进行了仿真模拟，相关技术手段在野外真实场景中的有效性仍有待验证。 席阿行等（2019） 席阿行等（2019） 等人提出了一种根据UAV获取的信息，UGV使用A*算法进行全局路径规划的方法，并进行了典型搜救场景的仿真验证，但其实验场景为人工搭建的比较简单的环境，不能满足野外应急搜救场景的需要。Delmerico J.等（2017）对UAV实时获取到的影像进行了分类，同时提取地表高程信息用来辅助分析地面的通行性，并使用D*算法为UGV提供路径规划服务，但其研究实验场景较小，地物类型也比较简单，且D*算法搜索效率较低，故在野外应急救援中的应用比较有限。 以上研究虽然都使用UAV获取地表信息，且均使用路径规划算法为地面车辆提供路径指引，但实验均未能模拟野外真实场景，对于野外复杂环境下的应急救援活动的适用性有待进一步完善。 针对以上问题， 黎晓东（2017） 黎晓东（2017） ， 李修贤等（2019） 李修贤等（2019） 等提出一种空地协同的方法：首先使用UAV获取研究区域的遥感影像，通过图像校正拼接、空中三角测量、遥感影像分类等过程，将遥感影像转化为可以用于路径规划的影像地图。再通过建立地表可通行性模型、构建恰当的通行代价计算函数，使用合适的路径规划算法在影像地图上搜索从起点到目标结点之间具备最优可通行性的路径，实现了UAV与UGV的空地协同。其研究成果也为本研究中野外应急救援路径规划问题提供了解决思路，但其所用的传统A*算法存在一定的局限性，并不能完全满足为UGV快速提供安全且具可通行路径的需求。 为便于本文工作的阐述，论文后续部分进行如下安排：首先在第2节总结国内外相关领域的研究现状，第3节重点介绍本文提出的Grid A*算法，然后在第4节通过实验对本文提出的算法与传统A*算法性能加以比较和分析，以说明本文算法的有效性。 2　研究现状 1 针对A*算法的改进，国际上有一些研究，其中代表性的工作有：Harabor D.等（2011）针对A*算法逐像元搜索效率较低的问题，提出了JPS（Jump Point Search）算法，该算法通过“跳跃式”搜索大幅减少了算法搜索的结点个数，压缩了搜索空间，提升了运算效率，但是该算法仅适用于代价均匀的栅格地图，并不适用于通行代价变化复杂的越野地形。Yap P.等（2011）提出了Block A*算法，该算法将 <math id="M1"><mi>m</mi><mi>*</mi><mi>n</mi></math> http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=21890472&type= http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=21890471&type= 6.43466663 2.62466669 单元内所有的可能存在的障碍分布情况及对应的可通行的路径预先存储到一个小型数据库中，并以 <math id="M2"><mi>m</mi><mi>*</mi><mi>n</mi></math> http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=21890472&type= http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=21890471&type= 6.43466663 2.62466669 方块作为搜索的基本单元，从而大大提高了搜索速度，但是对于现实中较为复杂的地形，如果使用该算法穷举单元内部的可通行路径会消耗极大的计算和存储资源。 国内近些年也有一些代表性的研究，如： 吴天羿等（2013） 吴天羿等（2013） 提出了一种改进的A*算法，分别针对特定车辆估计出了不同的地表类型的粗糙度，并以此粗糙度与格网间距离之比值作为A*算法的代价函数。其所提算法使用通行禁忌表以排除对不可通行单元的搜索，但其实验仅限于200×200格网的模拟数据，一方面实验数据过少，另一方面未能给出优化前后算法的对比。 范林林（2017） 范林林（2017） 提出了利用六角格剖分地表，并基于六角格单元进行路径规划的算法，但为方便表达，在所用六角格单元中，将原始地表类型综合为单一类型，同时六角格内高程信息由插值得到，显然算法主要针对的是较小比例尺的地形信息，其实验使用1：5万地形图，由于忽略了微地貌形态，故所搜索路径很难用于实际应急环境。 赵德群等（2017）针对三维路径搜索问题，提出将地表高程信息引入A*算法的代价函数，以改进传统二维空间的A*路径规划算法，但其研究未考虑地表植被与土壤等信息，故其搜索路径的可靠性不足。 孙玉泽（2020） 孙玉泽（2020） 结合了DEM与地表分类信息用于路径搜索，但未给出完整的通行代价评估函数，仅将DEM坡度用于判断路径是否通行，地物类型用于计算通行速度。其比较研究表明，改进A*算法较改进蚁群算法更为稳定。 以上这些研究工作，除了D*算法效率较低外，国内这些工作的共通特点，是未使用真实的高分辨率影像数据，也未使用高分地形数据，未能融合考虑地形坡度、地表植被以及地表土壤类型信息对通行性的影响。尽管对A*算法进行了优化，但优化前后效率究竟提高了多少，未能给出充分的说明。 在野外应急救援应用场景中，为了获取现势性很好的周边环境信息，需要由UAV为地面车辆拍摄周边区域的高分影像，经一系列处理后，为越野车辆快速规划一条安全、且具最优通行性的路线。但现有研究成果并不适于空地协同环境条件下的地表路径规划，概括而言，主要原因如下： 1） 普遍使用了卫星影像，分辨率较低，没有顾及影响地表通行性的微地貌因素； 2） 目前使用的搜索算法，就户外应急或远程在线使用的情景而言，计算的时效性仍有待改进； 3） 搜索算法中代价函数的构造过于简单，对地表坡度、土壤及植被类型信息对通行性的综合影响，未能深入分析从而使搜索结果的实用性和可靠性不足； 4） 现有算法，无论是基于格网（或六角格）还是基于像元，其本质上与基于像元的算法是一致的，均未考虑格网内部信息的不均一性，搜索结果路径是一条逐格网单元或像元连接且以其为宽度的路径，与实际所用交通工具所需的通行路径无关。然而在现实环境中，如不顾及实际交通工具的相关参数，则所搜索的路径不一定具有真正可靠的通行性。 为了解决上述问题，本文提出了一种基于格网单元的改进A*算法，该算法综合考虑地物类型和高程起伏对车辆通行性的影响以构建可通行性代价函数；同时顾及高分辨率影像与实际通行路径之间的尺度关系，综合利用格网特征像元之间的拓扑关系实现路径搜索，极大地压缩了搜索空间，提升了运算效率，本文将该算法命名为Grid A*算法。 3　Grid A*算法基本思想 1 前文提及，在野外无具体道路的条件下，我们需要搜索出一条具备最佳通行性的、可供车辆行驶的路径。如研究现状所评述，在野外地形环境较为复杂的应用场景中，现有方法机械地以像元为基本计算单元，或进行了单元划分（如六角格），但未考虑实际地面通行工具的路径尺度，故无法有效地针对空地协同系统的应用需求，快速地规划出合理可行的路径。为此，本研究构建了一种基于原始像元信息、以地物类型和地形起伏为核心因子的通行性计算代价函数，同时结合实际交通工具的通行路径需求，考虑影像空间分辨率与实际通行路径宽度之间的尺度关系，以一定尺寸的格网单元作为路径搜索的基本单元，使算法对路径的评估结果以及搜索结果更符合实际车辆的行驶条件。 下面分别对传统A*算法原理、格网单元的划分、可通行性评估模型以及Grid A*算法计算流程等进行详细阐述。 3.1　传统A*算法原理 2 传统A*算法是一种启发式的路径规划算法，结合了Dijkstra算法和最佳优先搜索算法（Best First Search，BFS算法）的优点，是在路径规划领域应用最广泛的算法之一。 传统A*算法的代价函数 <math id="M3"><mi>f</mi><mfenced separators="|"><mrow><mi>n</mi></mrow></mfenced></math> http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=21890576&type= http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=21890575&type= 6.77333355 3.80999994 表达式为： <math display="block" id="M4"><mi>f</mi><mfenced separators="|"><mrow><mi>n</mi></mrow></mfenced><mo>=</mo><mi>g</mi><mfenced separators="|"><mrow><mi>n</mi></mrow></mfenced><mo>+</mo><mi>h</mi><mfenced separators="|"><mrow><mi>n</mi></mrow></mfenced><mo>#</mo><mfenced separators="|"><mrow><mn mathvariant="normal">1</mn></mrow></mfenced></math> http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=21890476&type= http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=21890475&type= 37.08399963 3.80999994 其中， <math id="M5"><mi>g</mi><mfenced separators="|"><mrow><mi>n</mi></mrow></mfenced></math> http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=21890488&type= http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=21890487&type= 7.02733374 3.80999994 表示从起点到结点n的已知通行代价， <math id="M6"><mi>h</mi><mfenced separators="|"><mrow><mi>n</mi></mrow></mfenced></math> http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=21890554&type= http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=21890553&type= 6.94266701 3.72533321 表示从结点n到目标结点预估代价。 7　相邻结点 i、j 之间的通行代价可以表示为 1 <math display="block" id="M7"><mi>c</mi><mi>o</mi><mi>s</mi><msub><mrow><mi>t</mi></mrow><mrow><mi>i</mi><mo>,</mo><mi>j</mi></mrow></msub><mo>=</mo><msub><mrow><mi>D</mi></mrow><mrow><mi>i</mi><mo>,</mo><mi>j</mi></mrow></msub><mo>×</mo><msub><mrow><mi>r</mi></mrow><mrow><mi>i</mi><mo>,</mo><mi>j</mi></mrow></msub><mfenced separators="|"><mrow><msub><mrow><mi>T</mi></mrow><mrow><mi>s</mi></mrow></msub><mo>,</mo><mi>X</mi></mrow></mfenced><mo>#</mo><mfenced separators="|"><mrow><mn mathvariant="normal">2</mn></mrow></mfenced></math> http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=21890482&type= http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=21890481&type= 40.72467041 5.16466665 其中， <math id="M8"><msub><mrow><mi>D</mi></mrow><mrow><mi>i</mi><mo>,</mo><mi>j</mi></mrow></msub></math> http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=21890484&type= http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=21890483&type= 4.65666676 3.72533321 为两点的之间的距离， <math id="M9"><msub><mrow><mi>r</mi></mrow><mrow><mi>i</mi><mo>,</mo><mi>j</mi></mrow></msub><mfenced separators="|"><mrow><msub><mrow><mi>T</mi></mrow><mrow><mi>s</mi></mrow></msub><mo>,</mo><mi>X</mi></mrow></mfenced></math> http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=21890486&type= http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=21890485&type= 13.80066681 5.16466665 为两点间的单位长度的通行阻力，则对于某条路径上的结点n而言，从起点到该结点的通行代价 <math id="M10"><mi>g</mi><mfenced separators="|"><mrow><mi>n</mi></mrow></mfenced></math> http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=21890488&type= http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=21890487&type= 7.02733374 3.80999994 可以定义为： <math display="block" id="M11"><mi>g</mi><mfenced separators="|"><mrow><mi>n</mi></mrow></mfenced><mo>=</mo><msubsup><mo>∑</mo><mrow><mn mathvariant="normal">1</mn></mrow><mrow><mi>n</mi></mrow></msubsup><mrow><msub><mrow><mi>D</mi></mrow><mrow><mi>i</mi><mo>-</mo><mn mathvariant="normal">1</mn><mo>,</mo><mi>i</mi></mrow></msub></mrow><mo>×</mo><msub><mrow><mi>r</mi></mrow><mrow><mi>i</mi><mo>,</mo><mi>j</mi></mrow></msub><mfenced separators="|"><mrow><msub><mrow><mi>T</mi></mrow><mrow><mi>s</mi></mrow></msub><mo>,</mo><mi>X</mi></mrow></mfenced><mo>#</mo><mfenced separators="|"><mrow><mn mathvariant="normal">3</mn></mrow></mfenced></math> http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=21890490&type= http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=21890489&type= 48.93733215 5.16466665 A*算法定义了两张表来存储遍历过的结点，其中OPEN表中存储具备可通行性且尚未搜索的像元，CLOSED表中存储无法通行或已搜索过的像元。 传统A*算法首先对起点的邻域进行遍历，并将所获结点都加入到OPEN表中，此后每一次计算都会对OPEN表中代价函数 <math id="M12"><mi>f</mi><mfenced separators="|"><mrow><mi>n</mi></mrow></mfenced></math> http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=21890576&type= http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=21890575&type= 6.77333355 3.80999994 值最小的结点的邻域进行搜索，所获结点均加入到OPEN表中，并将该结点移入CLOSED表，直到搜索到目标结点。最后，A*算法通过回溯结点之间的邻域关系，生成一条从起点至目标结点的路径。 3.2　格网单元及其特征选取 2 传统A*算法普遍适用于经过通行阻力赋值的栅格地图，但是该算法运行时间随着搜索范围的增大迅速增长，所以当研究区域较大或图像分辨率较高时，传统A*算法无法实现快速搜索。 本研究为了提高算法效率，采用格网划分、分块处理的方式，利用格网单元内部地表属性的连通分布特点，在格网单元边缘选取特征像元，用于路径快速搜索，实现了压缩搜索空间、提升运算效率，但又不丢失过多格网单元内部细节信息的效果。 对于空地协同过程中所采用无人机遥感影像而言，越野车辆的实际尺寸是影像空间分辨率的多倍以上，所以路径规划过程中需要考虑车体覆盖范围内的所有像元对通行造成的影响。为此，我们顾及车体尺寸与影像分辨率之间的尺度关系，以与车体尺寸相近的格网单元对无人机影像进行划分，并以格网单元作为基本单位进行通行性路径分析计算。 影响通行性的主要两方面因素中，地形起伏信息（即坡度）的一致性连续较差，而地物分类信息的一致性连续较强；同时地形坡度的突变较少，而地物类型的突变较多。尤其在不同地物之间存在明确的界限时，相邻像元之间可通行性的主要差别更多地体现在地物类型的变化方面，因此，我们以地物分类影像作为格网单元的划分的基础。 格网单元的尺度大小我们选择 <math id="M13"><mi>n</mi><mi>*</mi><mi>n</mi></math> http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=21890620&type= http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=21890619&type= 5.58799982 2.62466669 像素，即把整个影像以 <math id="M14"><mi>n</mi><mi>*</mi><mi>n</mi></math> http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=21890620&type= http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=21890619&type= 5.58799982 2.62466669 的格网单元进行划分，如 图1 图1 所示为影像被划分为格网的局部示意图。格网单元大小的选择，以通行工具的尺度要求为参考，同时一个格网单元内部尽量不包含、或少包含独立地物分类图斑。 如图2a为格网单元尺寸为9（即 <math id="M15"><mi>n</mi><mo>=</mo><mn mathvariant="normal">9</mn></math> http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=21890501&type= http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=21890500&type= 8.21266651 2.70933342 ）时，格网单元的划分方式，黑色线条所围区域是一个9×9大小的格网单元。该格网单元边缘像元中，1、3、5、7为角像元，其余为边像元。相邻的格网单元之间共用边、角像元，整个研究区域从而被边缘相互重叠的格网单元所覆盖。利用相邻格网之间共用边界像元的特点，路径搜索时便可以以边界像元连接，实现相邻格网之间的路径连续搜索。 格网的边界像元的分布有着明显的规律性，为了方便描述格网的可通行性，本研究引入“特征像元”的概念。如图2b所示，边界像元中标记为深色的像元，是格网边缘某一地物类型的连续像元中的中间点，由于地物分布的连续性特点，格网边缘出现的地物类型，一般在格网单元内部也会出现，故将其选为“特征像元”，指其代表了格网在该边缘方向上所具有的地表属性。如图2b所示，格网内部地物属性有三类，边缘的特征像元即能代表格网内部的地物类型，由于每一条格网边缘至少存在一个特征像元，这些特征像元在一定程度上表达了格网单元中地物分布的连通性。如果存在图2c中情况，当格网内部存在独立地物分类图斑，即某种岛状地物完全包含在格网单元内部时，这类斑块的出现会给特征像元的选取、格网单元内部的可通行性评估增加困难，Grid A*算法可通过通行阻力平均对独立图斑对车辆行进造成的影响进行评估，本文在后续实验部分给出了具体解决方法。 特征像元的选取，主要是考虑了地表覆盖类型这一个影响通行性的重要因子。由于不同地物属性的像元意味着不同的通行性，所以对于穿行某一特定格网单元的路径而言，最优路径不会沿地物间分界线像元经过。在格网单元边缘上，本算法选择同类型连续像元的中间点作为特征像元，如果当前格网中，某种地表类型具有最优的通达性，则最优路径应尽可能完全位于该类型的地表范围中；如果在格网边缘上任意选择像元，则搜索选路径可能同时覆盖两种或多种地表类型，从而无法保证最优的通达性。对于任意选择像元的问题，在4.4节分析与讨论部分将作进一步阐述。 此外，人们在现实环境中在遇到均匀、无变化地表环境时，行走或驾车的方向随意性较大，所以在Grid A*算法中，我们考虑选取连续同类像元的中间像元作为特征用于计算，以保证所选路径在同类地表区域的中间，从而在优化计算的同时，兼顾了路径搜索的可靠性。 路径搜索过程中，Grid A*算法通过以特征像元为结点建立拓扑关系的方式，缩短对格网单元遍历所需时间的同时，实现了路径的快速搜索。 3.3　格网单元及其特征选取 2 1）　影响通行性的主要因子赋值 3 合理的地表通行性代价函数是搜索到高可靠性通行路径的重要基础。在户外环境中，影响通行性的主要因子是地表的地物类型和地形坡度。我们沿用 李修贤等（2019） 李修贤等（2019） 的研究方法，以越野车为例，依据其在不同地表环境中的行驶特点，给出了几类代表性地物与三个典型坡度值对应条件下的行驶速度。如 表1 表1 所示，车辆的最大通行坡度，在不同的地表条件下，对其取不同值；平地即0坡度一般而言具有最大通行速度，在确保野外行驶安全的情况下，下坡也应适当减慢速度，为简便起见，我们取与上坡同样的速度；据一般性经验，我们认为10度属于坡度值出现频率最高的中间值，故取其为一个典型坡度值。 地物种类 0°通行速度 0°通行阻力 10°通行速度 10°通行阻力 最大通行角度 道路 30km/h 1 15 km/h 2 30° 戈壁 20km/h 1.5 10 km/h 3 25° 盐碱地 16km/h 1.875 8 km/h 3.75 25° 低矮植物 12km/h 2.5 4 km/h 7.5 20° 沙地 10km/h 3 3 km/h 10 20° 水体 0km/h ∞ 0 km/h ∞ 0° 从地物类型而言，野外道路的通行性最佳，故通行阻力最小。设 <math id="M16"><msub><mrow><mi>S</mi></mrow><mrow><mn mathvariant="normal">0</mn></mrow></msub><mo>=</mo><mn mathvariant="normal">30</mn><mi>k</mi><mi>m</mi><mo>/</mo><mi>h</mi></math> http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=21890508&type= http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=21890507&type= 18.62666702 3.80999994 为其基准通行速度，对应的通行阻力值 <math id="M17"><msub><mrow><mi>r</mi></mrow><mrow><mn mathvariant="normal">0</mn></mrow></msub><mo>=</mo><mn mathvariant="normal">1.0</mn></math> http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=21890510&type= http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=21890509&type= 11.76866722 3.80999994 。其它地物类型的通行速度，以平地作为参照，结合经验性估计给出。例如，考虑到戈壁地面主要以小砂石为主，地面较为稳固，通行速度也较快；盐碱地则稍弱于戈壁；低矮植物有一定的固沙作用，故也有一定的可通行性；而沙地主要是由细沙构成，质地松软，不利于通行；水体则完全不能通行，故其通行阻力取无穷大。 由文献综述我们可以看出，现有研究对通行代价函数的构建考虑普遍较为简单。本文研究依据一般性经验，认为车辆通行速度与地物及坡度之间的具有二次非线性函数关系，并非一般文献中给出的简单的线性关系，故在 表1 表1 所给三点值的基础上，我们采用函数拟合法，得到对应不同地物类型，在任意坡度条件下的通行速度表达式与通行阻力表达式，如公式（4）、（5）所示。 表1 表1 地物种类与不同坡度对应的通行速度与通行阻力 不同地表地物和坡度环境下用于计算车辆通行速度的表达式 <math id="M18"><mi>S</mi><mfenced separators="|"><mrow><msub><mrow><mi>T</mi></mrow><mrow><mi>s</mi></mrow></msub><mo>,</mo><mi>X</mi></mrow></mfenced></math> http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=21890512&type= http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=21890511&type= 12.27666664 5.16466665 和通行阻力表达式 <math id="M19"><mi>r</mi><mfenced separators="|"><mrow><msub><mrow><mi>T</mi></mrow><mrow><mi>s</mi></mrow></msub><mo>,</mo><mi>X</mi></mrow></mfenced></math> http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=21890540&type= http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=21890539&type= 11.68400002 5.16466665 如下： <math display="block" id="M20"><mtable columnalign="left"><mtr><mtd><mi>S</mi><mfenced separators="|"><mrow><msub><mrow><mi>T</mi></mrow><mrow><mi>s</mi></mrow></msub><mo>,</mo><mi>X</mi></mrow></mfenced><mo>=</mo></mtd></mtr><mtr><mtd><mfenced open="{" close="" separators="|"><mrow><mtable><mtr><mtd><mn mathvariant="normal">82.56</mn><mo>×</mo><msup><mrow><mfenced separators="|"><mrow><mi mathvariant="normal">t</mi><mi mathvariant="normal">a</mi><mi mathvariant="normal">n</mi><mtext> </mtext><mi>X</mi></mrow></mfenced></mrow><mrow><mn mathvariant="normal">2</mn></mrow></msup><mo>-</mo><mn mathvariant="normal">99.63</mn><mo>×</mo><mi mathvariant="normal">t</mi><mi mathvariant="normal">a</mi><mi mathvariant="normal">n</mi><mtext> </mtext><mi>X</mi><mo>+</mo><mn mathvariant="normal">30</mn><mo>,</mo><mtext> </mtext><msub><mrow><mi>T</mi></mrow><mrow><mi>s</mi></mrow></msub><mo>=</mo><mi>r</mi><mi>o</mi><mi>a</mi><mi>d</mi></mtd></mtr><mtr><mtd><mn mathvariant="normal">47.67</mn><mo>×</mo><msup><mrow><mfenced separators="|"><mrow><mi mathvariant="normal">t</mi><mi mathvariant="normal">a</mi><mi mathvariant="normal">n</mi><mtext> </mtext><mi>X</mi></mrow></mfenced></mrow><mrow><mn mathvariant="normal">2</mn></mrow></msup><mo>-</mo><mn mathvariant="normal">65.12</mn><mo>×</mo><mi mathvariant="normal">t</mi><mi mathvariant="normal">a</mi><mi mathvariant="normal">n</mi><mtext> </mtext><mi>X</mi><mo>+</mo><mn mathvariant="normal">20</mn><mo>,</mo><mtext> </mtext><msub><mrow><mi>T</mi></mrow><mrow><mi>s</mi></mrow></msub><mo>=</mo><mi>g</mi><mi>o</mi><mi>b</mi><mi>i</mi></mtd></mtr><mtr><mtd><mn mathvariant="normal">38.13</mn><mo>×</mo><msup><mrow><mfenced separators="|"><mrow><mi mathvariant="normal">t</mi><mi mathvariant="normal">a</mi><mi mathvariant="normal">n</mi><mtext> </mtext><mi>X</mi></mrow></mfenced></mrow><mrow><mn mathvariant="normal">2</mn></mrow></msup><mo>-</mo><mn mathvariant="normal">52.09</mn><mo>×</mo><mi mathvariant="normal">t</mi><mi mathvariant="normal">a</mi><mi mathvariant="normal">n</mi><mtext> </mtext><mi>X</mi><mo>+</mo><mn mathvariant="normal">16</mn><mo>,</mo><mtext> </mtext><msub><mrow><mi>T</mi></mrow><mrow><mi>s</mi></mrow></msub><mo>=</mo><mi>s</mi><mi>a</mi><mi>l</mi><mi>i</mi><mi>n</mi><mi>e</mi><mtext> </mtext><mi>s</mi><mi>o</mi><mi>i</mi><mi>l</mi></mtd></mtr><mtr><mtd><mn mathvariant="normal">66.09</mn><mo>×</mo><msup><mrow><mfenced separators="|"><mrow><mi mathvariant="normal">t</mi><mi mathvariant="normal">a</mi><mi mathvariant="normal">n</mi><mtext> </mtext><mi>X</mi></mrow></mfenced></mrow><mrow><mn mathvariant="normal">2</mn></mrow></msup><mo>-</mo><mn mathvariant="normal">57.02</mn><mo>×</mo><mi mathvariant="normal">t</mi><mi mathvariant="normal">a</mi><mi mathvariant="normal">n</mi><mtext> </mtext><mi>X</mi><mo>+</mo><mn mathvariant="normal">12</mn><mo>,</mo><mtext> </mtext><msub><mrow><mi>T</mi></mrow><mrow><mi>s</mi></mrow></msub><mo>=</mo><mi>g</mi><mi>r</mi><mi>a</mi><mi>s</mi><mi>s</mi></mtd></mtr><mtr><mtd><mn mathvariant="normal">65.15</mn><mo>×</mo><msup><mrow><mfenced separators="|"><mrow><mi mathvariant="normal">t</mi><mi mathvariant="normal">a</mi><mi mathvariant="normal">n</mi><mtext> </mtext><mi>X</mi></mrow></mfenced></mrow><mrow><mn mathvariant="normal">2</mn></mrow></msup><mo>-</mo><mn mathvariant="normal">51.19</mn><mo>×</mo><mi mathvariant="normal">t</mi><mi mathvariant="normal">a</mi><mi mathvariant="normal">n</mi><mtext> </mtext><mi>X</mi><mo>+</mo><mn mathvariant="normal">10</mn><mo>,</mo><mtext> </mtext><msub><mrow><mi>T</mi></mrow><mrow><mi>s</mi></mrow></msub><mo>=</mo><mi>s</mi><mi>a</mi><mi>n</mi><mi>d</mi></mtd></mtr><mtr><mtd><mn mathvariant="normal">0</mn><mo>,</mo><mtext> </mtext><msub><mrow><mi>T</mi></mrow><mrow><mi>s</mi></mrow></msub><mo>=</mo><mi>w</mi><mi>a</mi><mi>t</mi><mi>e</mi><mi>r</mi></mtd></mtr></mtable></mrow></mfenced><mo>#</mo><mfenced separators="|"><mrow><mn mathvariant="normal">4</mn></mrow></mfenced></mtd></mtr></mtable></math> http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=21890516&type= http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=21890515&type= 89.83132935 45.55066681 <math display="block" id="M21"><mi>r</mi><mfenced separators="|"><mrow><msub><mrow><mi>T</mi></mrow><mrow><mi>s</mi></mrow></msub><mo>,</mo><mi>X</mi></mrow></mfenced><mo>=</mo><mfenced open="{" close="" separators="|"><mrow><mtable><mtr><mtd><mfrac><mrow><msub><mrow><mi>S</mi></mrow><mrow><mn mathvariant="normal">0</mn></mrow></msub></mrow><mrow><mi>S</mi><mfenced separators="|"><mrow><msub><mrow><mi>T</mi></mrow><mrow><mi>s</mi></mrow></msub><mo>,</mo><mi>X</mi></mrow></mfenced></mrow></mfrac><mtext> </mtext><mfenced separators="|"><mrow><msub><mrow><mi>T</mi></mrow><mrow><mi>s</mi></mrow></msub><mo>≠</mo><mi>w</mi><mi>a</mi><mi>t</mi><mi>e</mi><mi>r</mi><mo>,</mo><msub><mrow><mi>S</mi></mrow><mrow><mn mathvariant="normal">0</mn></mrow></msub><mo>=</mo><mn mathvariant="normal">30</mn><mi>k</mi><mi>m</mi><mo>/</mo><mi>h</mi></mrow></mfenced></mtd></mtr><mtr><mtd><mi mathvariant="normal">∞</mi><mtext>                   </mtext><mo stretchy="false">(</mo><msub><mrow><mi>T</mi></mrow><mrow><mi>s</mi></mrow></msub><mo>=</mo><mi>w</mi><mi>a</mi><mi>t</mi><mi>e</mi><mi>r</mi><mo stretchy="false">)</mo></mtd></mtr></mtable></mrow></mfenced><mtext>                                </mtext><mo>#</mo><mfenced separators="|"><mrow><mn mathvariant="normal">5</mn></mrow></mfenced></math> http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=21890518&type= http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=21890517&type= 99.22933960 16.93333435 其中， <math id="M22"><msub><mrow><mi>T</mi></mrow><mrow><mi>s</mi></mrow></msub></math> http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=21890536&type= http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=21890535&type= 2.96333337 3.72533321 代表不同地物类型， <math id="M23"><mi>X</mi></math> http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=21890538&type= http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=21890537&type= 2.28600001 2.62466669 为表达坡度的角度值， <math id="M24"><mi mathvariant="normal">t</mi><mi mathvariant="normal">a</mi><mi mathvariant="normal">n</mi><mtext> </mtext><mi>X</mi></math> http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=21890524&type= http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=21890523&type= 7.53533268 2.70933342 即为以百分比表示的坡度值。 图3 图3 给出了5种地物对应的二次曲线图，横轴为百分比表达的坡度值。根据以上函数关系，我们可以计算出越野车辆在不同地物类型的地表、任意坡度时的通行速度，提高了通行代价估计的准确性。 2）　基于格网单元的通行性评估模型 3 如 图4 图4 所示，我们使用边缘相互重叠的格网单元分割了整个研究区域影像（图中灰色线框表达了对部分分类影像的分割结果），并根据地物分类特点，基于3.2节所述方法，在格网边缘上选取了特征像元（图中浅黄色像元）。 使用特征像元替代了格网单元用于路径搜索时必须考虑格网单元内部的像元信息。如图5a展示了从S点到G点逐像元搜索得到的路径，图5b为基于格网单元的特征像元搜索所得到的路径，从像元级别而言，与图5a结果相比，该结果并不是最佳路径。然而，因为车辆实际通行宽度远大于一个像元，所以图5a中的路径未必具有最高的可靠性，为此，我们需要综合考虑实际路宽的范围内其他单元的通行信息。 如图5c所示，由特征像元A搜索到特征像元B基于格网单元进行路径规划时，计算通行代价时需要考虑通行路宽的需要，在A、B两个特征像元周边建立如图所示的平行四边形“通行区域”。设该平行四边形的高为 a 个像元，底边长为 b 个像元，我们用该区域内所有像元的通行阻力均值，来概括总的通行能力。为了提高可通行性的判断条件，我们在逐行或逐列扫描像元时，凡是遇到连续两行或两列像元及以上像元均不可通行的情况，该整个区域的通行阻力设为极大值。 Grid A*算法以特征像元替代格网单元的通行性，所以本研究对传统A*算法代价式（2）（3）加以改进。其具体的通行代价计算函数如下： 在Grid A*算法中，两个特征像元 i 、 j 一般不是相邻的，引入一个参数 <math id="M25"><msub><mrow><mi>α</mi></mrow><mrow><mi>i</mi><mo>,</mo><mi>j</mi></mrow></msub></math> http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=21890532&type= http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=21890531&type= 4.31799984 3.72533321 对特征像元 i 、 j 周边的平行四边形“通行区域”内的可通行性进行评估： <math display="block" id="M26"><msub><mrow><mi>α</mi></mrow><mrow><mi>i</mi><mo>,</mo><mi>j</mi></mrow></msub><mo>=</mo><mtext> </mtext><mfrac><mrow><msub><mo>∑</mo><mrow><mi>a</mi><mo>,</mo><mi>b</mi></mrow></msub><mrow><mi>r</mi><mfenced separators="|"><mrow><msub><mrow><mi>T</mi></mrow><mrow><mi>s</mi></mrow></msub><mo>,</mo><mi>X</mi></mrow></mfenced></mrow></mrow><mrow><mi>a</mi><mo>×</mo><mi>b</mi></mrow></mfrac><mo>#</mo><mfenced separators="|"><mrow><mn mathvariant="normal">6</mn></mrow></mfenced></math> http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=21890534&type= http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=21890533&type= 34.62866592 9.56733322 其中 a 、 b 是“通行区域”的高与底边长， <math id="M27"><msub><mrow><mi>T</mi></mrow><mrow><mi>s</mi></mrow></msub></math> http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=21890536&type= http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=21890535&type= 2.96333337 3.72533321 为地物类型， <math id="M28"><mi>X</mi></math> http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=21890538&type= http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=21890537&type= 2.28600001 2.62466669 为坡度， <math id="M29"><mi>r</mi><mfenced separators="|"><mrow><msub><mrow><mi>T</mi></mrow><mrow><mi>s</mi></mrow></msub><mo>,</mo><mi>X</mi></mrow></mfenced></math> http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=21890540&type= http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=21890539&type= 11.68400002 5.16466665 为根据式（4）（5）计算得出的通行阻力值。则两特征像元间通行代价计算方式为 <math display="block" id="M30"><mi>c</mi><mi>o</mi><mi>s</mi><msub><mrow><mi>t</mi></mrow><mrow><mi>i</mi><mo>,</mo><mi>j</mi></mrow></msub><mo>=</mo><msub><mrow><mi>D</mi></mrow><mrow><mi>i</mi><mo>,</mo><mi>j</mi></mrow></msub><mo>×</mo><msub><mrow><mi>α</mi></mrow><mrow><mi>i</mi><mo>,</mo><mi>j</mi></mrow></msub><mo>=</mo><msub><mrow><mi>D</mi></mrow><mrow><mi>i</mi><mo>,</mo><mi>j</mi></mrow></msub><mo>×</mo><mtext> </mtext><mfrac><mrow><msub><mo>∑</mo><mrow><mi>a</mi><mo>,</mo><mi>b</mi></mrow></msub><mrow><mi>r</mi><mfenced separators="|"><mrow><msub><mrow><mi>T</mi></mrow><mrow><mi>s</mi></mrow></msub><mo>,</mo><mi>X</mi></mrow></mfenced></mrow></mrow><mrow><mi>a</mi><mo>×</mo><mi>b</mi></mrow></mfrac><mo>#</mo><mfenced separators="|"><mrow><mn mathvariant="normal">7</mn></mrow></mfenced></math> http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=21890542&type= http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=21890541&type= 64.00800323 9.56733322 对于某条路径上的结点n而言，从起点到该结点的通行代价定义为： <math display="block" id="M31"><mi>g</mi><mfenced separators="|"><mrow><mi>n</mi></mrow></mfenced><mo>=</mo><msubsup><mo>∑</mo><mrow><mn mathvariant="normal">1</mn></mrow><mrow><mi>n</mi></mrow></msubsup><mrow><msub><mrow><mi>D</mi></mrow><mrow><mi>i</mi><mo>-</mo><mn mathvariant="normal">1</mn><mo>,</mo><mi>i</mi></mrow></msub></mrow><mi mathvariant="normal">*</mi><mtext> </mtext><mfrac><mrow><msub><mo>∑</mo><mrow><mi>a</mi><mo>,</mo><mi>b</mi></mrow></msub><mrow><mi>r</mi><mfenced separators="|"><mrow><msub><mrow><mi>T</mi></mrow><mrow><mi>s</mi></mrow></msub><mo>,</mo><mi>X</mi></mrow></mfenced></mrow></mrow><mrow><mi>a</mi><mo>×</mo><mi>b</mi></mrow></mfrac><mo>#</mo><mfenced separators="|"><mrow><mn mathvariant="normal">8</mn></mrow></mfenced></math> http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=21890547&type= http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=21890546&type= 53.34000015 9.56733322 与传统A*算法相同， <math id="M32"><mi>h</mi><mfenced separators="|"><mrow><mi>n</mi></mrow></mfenced></math> http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=21890554&type= http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=21890553&type= 6.94266701 3.72533321 表示从结点n到目标结点预估代价。 3.4　Grid A*算法计算流程 2 传统A*算法采用4邻域或8邻域逐像元搜索策略，在本文提出的Grid A*算法为了提高路径的连续性，在格网单元层面沿用了A*算法的4邻域搜索策略；在格网内部搜索时，则选择遍历进入当前格网的特征像元到其它所有特征像元之间的多种路径组合。同时，对启发函数 <math id="M33"><mi>h</mi><mfenced separators="|"><mrow><mi>n</mi></mrow></mfenced></math> http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=21890554&type= http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=21890553&type= 6.94266701 3.72533321 沿用了与A*算法的思想，表示从结点n到目标结点预估代价，由此综合公式（1）和公式（8），我们有总的通行代价函数表达式： <math display="block" id="M34"><mi>f</mi><mfenced separators="|"><mrow><mi>n</mi></mrow></mfenced><mo>=</mo><msubsup><mo>∑</mo><mrow><mn mathvariant="normal">1</mn></mrow><mrow><mi>n</mi></mrow></msubsup><mrow><msub><mrow><mi>D</mi></mrow><mrow><mi>i</mi><mo>-</mo><mn mathvariant="normal">1</mn><mo>,</mo><mi>i</mi></mrow></msub></mrow><mi mathvariant="normal">*</mi><mtext> </mtext><mfrac><mrow><msub><mo>∑</mo><mrow><mi>a</mi><mo>,</mo><mi>b</mi></mrow></msub><mrow><mi>r</mi><mfenced separators="|"><mrow><msub><mrow><mi>T</mi></mrow><mrow><mi>s</mi></mrow></msub><mo>,</mo><mi>X</mi></mrow></mfenced></mrow></mrow><mrow><mi>a</mi><mo>×</mo><mi>b</mi></mrow></mfrac><mo>+</mo><mi>h</mi><mfenced separators="|"><mrow><mi>n</mi></mrow></mfenced><mo>#</mo><mfenced separators="|"><mrow><mn mathvariant="normal">9</mn></mrow></mfenced></math> http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=21890556&type= http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=21890555&type= 64.34667206 9.56733322 在格网化的地表可通行性数字化专题地图中，确定路径搜索的起点像元S和目标像元G，以起点像元S作为本次搜索起点，算法的总体过程如下： 步骤1，图6a中，以起点像元S作为本次搜索起点，得到包含起点像元S的格网单元，如果包含起点像元S的格网单元为多个，则选取距离终点像元G最近的一个作为本次搜索到的格网单元，表示为格网单元 <math id="M35"><mi>g</mi><mi>r</mi><mi>i</mi><mi>d</mi><mfenced separators="|"><mrow><mi>S</mi></mrow></mfenced></math> http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=21890560&type= http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=21890559&type= 11.17599964 3.80999994 ，在格网单元 <math id="M36"><mi>g</mi><mi>r</mi><mi>i</mi><mi>d</mi><mfenced separators="|"><mrow><mi>S</mi></mrow></mfenced></math> http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=21890560&type= http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=21890559&type= 11.17599964 3.80999994 中，采用特征像元识别算法， <math id="M37"><msub><mrow><mi>W</mi></mrow><mrow><mn mathvariant="normal">0</mn></mrow></msub></math> http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=21890562&type= http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=21890561&type= 4.06400013 3.72533321 个特征像元，计算每个特征像元的估价函数 <math id="M38"><mi>f</mi><mfenced separators="|"><mrow><mi>n</mi></mrow></mfenced></math> http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=21890576&type= http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=21890575&type= 6.77333355 3.80999994 并加入到OPEN表中，OPEN表中的各像元被标记为蓝色； 步骤2，图6b中，Grid A*算法以OPEN表中 <math id="M39"><mi>f</mi><mfenced separators="|"><mrow><mi>n</mi></mrow></mfenced></math> http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=21890576&type= http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=21890575&type= 6.77333355 3.80999994 最小的结点作为下一步搜索的起点，并将此结点移入CLOSED表中，CLOSED表中的各像元被标记为黄色，由于特征像元一定位于被两个格网单元公用边上，所以此时被选择的结点就是两个格网单元之间的媒介，算法将继续选定前进方向上下一个格网单元 <math id="M40"><mi>g</mi><mi>r</mi><mi>i</mi><mi>d</mi><mfenced separators="|"><mrow><mi>i</mi></mrow></mfenced></math> http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=21890568&type= http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=21890567&type= 10.32933331 3.80999994 ，并将遍历获得的特征像元加入OPEN表中； 步骤3，图6c~6g中，算法每次均从OPEN表中取出 <math id="M41"><mi>f</mi><mfenced separators="|"><mrow><mi>n</mi></mrow></mfenced></math> http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=21890576&type= http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=21890575&type= 6.77333355 3.80999994 最小的特征像元，再遍历该特征像元所在格网单元，将新搜索到的特征像元加入OPEN表中，直到某一被遍历的格网单元包含目标结点为止；需要注意的是，图d中OPEN表中估价函数 <math id="M42"><mi>f</mi><mfenced separators="|"><mrow><mi>n</mi></mrow></mfenced></math> http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=21890576&type= http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=21890575&type= 6.77333355 3.80999994 最小的结点是A，并以A为起点搜索得到图e，但A的子结点 <math id="M43"><mi>f</mi><mfenced separators="|"><mrow><mi>n</mi></mrow></mfenced></math> http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=21890576&type= http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=21890575&type= 6.77333355 3.80999994 均大于B，所以下一步搜索需要以当前OPEN表中 <math id="M44"><mi>f</mi><mfenced separators="|"><mrow><mi>n</mi></mrow></mfenced></math> http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=21890576&type= http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=21890575&type= 6.77333355 3.80999994 最小的特征像元B为起点，故得到图f； 步骤4，图6h中，从目标结点依次回溯各特征像元的上一级结点，并使用线段连接，就可以得到结果路径，此时Grid A*算法运行结束，结果路径中各特征像元所构建的“通行区域”范围使用浅黄色框体标出，本研究认为越野车辆在浅黄色区域内具有最佳的可通行性。 相比于传统A*算法，Grid A*算法以格网单元作为搜索和扩展的基本单元，极大的压缩了搜索空间，提高了运算效率；并采用式（6）作为通行代价的计算方法，考虑了越野通行路宽等因素；以格网单元边上的特征像元的基本单位，充分兼顾了高分辨率影像的细节信息，提高了所搜索路径的计算速度与结果的可靠性。 图7 图7 为Grid A*算法流程图。 4　实验与分析 1 4.1　实验数据获取与处理 2 为验证本研究提出的路径规划算法的有效性，我们使用UAV获取了沙漠地带的高分辨率影像数据进行实验。实验区域位于新疆维吾尔自治区图木舒克市南郊地区（ 图8 图8 ），地处塔克拉玛干沙漠西缘，为山脉到沙漠的过渡地带，地貌复杂。航拍作业时间为2019年8月，影像覆盖范围长约1.3千米，宽约0.5千米，最高点海拔1113.58米，最低点1101.13米，地表起伏约12米。 首先对获取的影像使用Pix4D软件拼接处理并提取数字表面模型（DSM）， 图9 图9 为可见光影像的拼接图，图10为使用灰度表达的区域DSM，两张影像的大小均为9304×2972像素，空间分辨率为13.76厘米。 1;2;3; 4.2　地表可通行性计算 2 实验前利用神经网络算法对可见光影像进行分类，根据该区域内自然景观的特点，将地物分为道路、戈壁、盐碱地、低矮植物、沙地、水体等6类，分类结果如图11所示。 同时基于DSM数据，得到坡度值，基于前述3.2节中式（4）（5），得到各像元的通行阻力值，如 图12 图12 所示，亮度越高的区域通行阻力越小，亮度越低的区域通行阻力越大。 1;2; 4.3　路径规划 2 基于前述方法，我们以分类图为基础，对 图12 图12 所示整个通行性地图进行了格网划分，同时其于分类图层查找其特征像元。 本实验中，我们重新选择一次交通工具意味着选择不同的通行路径宽度，也就意味着重新选择格网单元的大小。为了简化问题，对于所有的交通工具我们都使用了一致的代价函数，即我们近似认为摩托车与越野车在荒地具有一样的通行能力。 图11 图木舒克市南郊DSM影像图 Fig11. DSM image of the southern suburb of Tumxuk City 基于3.2节提出的代价函数，并结合实验区域的实际通达性，我们选择序列5、7、9、11、13、15作为格网尺寸的大小。如图13所示，格网尺寸为5、7、9像元的情况，Grid A*算法搜索出了从S点到G点的可通行路径，即所需路宽在0.7米到1.5米间的交通工具可以在该区域通行，比如摩托车或UGV等；但对于11、13、15像元大小的格网，算法无法找到可通行的路径，换言之，对于所需1.5米路宽的车辆来说，两点间是无法通行的。这一结果与实际环境情况基本相符。 Fig10. DSM image of the southern suburb of Tumxuk City 图10 图木舒克市南郊DSM影像图 为了比较Grid A*算法与传统A*算法的优劣，我们同时使用A*算法在图13上的两点间搜索路径。 表2 表2 显示了两种算法结果的比较，A*算法和Grid A*算法分别按照公式（1）和公式（9）计算搜索路径上的通行代价。对于Grid A*算法而言，格网单元越大，算法速度越快，这一点符合我们的期望。而对于A*算法，为了保持其所搜索的像素空间分辨率与Grid A*算法格网单元大小一致，我们对原数据做了如前所述的压缩，由于压缩后A*算法搜索的像素数大为减少，故其速度较使用原始分辨率的数据提升了很多。但从表中可以看出，A*算法使用压缩图像所搜索的路径其通行代价较Grid A*算法偏高，同时，由图13可以看出，其所搜索路径也较Grid A*算法更长。 算法名称 计算时间 与传统A*算法对比 通行代价 A*算法（原始分辨率） 341.86s 100% 17445.37 Grid A*算法（ n=5 ） 52.23s 15.28% 19703.84 Grid A*算法（ n=7 ） 28.85s 7.27% 20632.59 Grid A*算法（ n=9 ） 16.66s 4.29% 21909.39 A*算法（1：5压缩） 10.12s 2.96% 20959.93 A*算法（1：7压缩） 5.34s 1.56% 25761.47 A*算法（1：9压缩） 3.61s 1.06% 28246.39 图13 不同图像分辨率下的A*算法和不同格网尺寸的Grid A*算法路径对比 图1 图1 Fig13. Paths comparison 1 between A* algorithm with different image resolutions and Grid A* algorithm with different grid cell sizes 为了考察两种算法所搜索路径的可靠性，在图14中，我们给出了以S到A、A到B和B到G等三段通行路径为例，对Grid A*算法和A*算法进行了比较。如图14所示，Grid A*算法较基于压缩图像的A*算法均有较好的表达，尤其B到G段路径，由于基于压缩图像的A*算法对格网单元做了平均，所以未能找到由B到G段早有车辆通行过的路径，即在图分类时将其分类为道路的地表。在图14d给出了局部地表及搜索路径的三维可视化效果，可以更直观地看出，Grid A*算法所搜索路径通过的地表较基于压缩图像的A*算法更为平稳通畅。 从14组图可以看出，传统A*算法基于单像元搜索的路径结果，显示不逊于Grid A*算法，但由于其找到的是一条单像元的路径，当区域存在特殊情时，其所搜索路径的可靠性难以确定。为了验证这一点，我们人为在实验数据中加入了障碍物，如图15所示黑色长条物，图中两障碍物间仅有3个像元宽度，传统A*算法依然选择从障碍物中穿行，而Grid A*算法则找到了绕过障碍物的路径，所以，Grid A*算法更符合实际应用情况，具有更好的可靠性。 4.4　讨论和分析 2 在空地协同过程中，充分利用无人机高分影像，并为地面车辆提供现势性很强的路径指引，具有非常重要的意义。但是在高分影像上单像元对应的真实地表尺寸过小，提取可通行路径时，必须兼顾通行路径的宽度，引入格网单元是提高算法效率以及解决该问题的最佳方式，我们可以通过三种情形分析这一问题： 1） 如图16a所示，使用传统A*算法四邻域或八邻域的通行策略，按期望的路宽，仅在8邻域或4邻域的方向选取矩形“通行区域”，则会忽略其余方向的可通过情况，由于地物地形的影响，最佳通行路径未必恰在4个或8个邻域方向，同时如果没有格网单元，无法选择合理的前进步长 H 。 2） 如图16b所示，在选择合适的路宽后，进行任意角度路径搜索。如果考虑在尽可能多的方向搜索最优路径，按角度增量 <math id="M45"><mi mathvariant="normal">Δ</mi><mi mathvariant="normal">α</mi></math> http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=21890616&type= http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=21890615&type= 4.74133301 2.70933342 选取搜索方向，过小的 <math id="M46"><mi mathvariant="normal">Δ</mi><mi mathvariant="normal">α</mi></math> http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=21890616&type= http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=21890615&type= 4.74133301 2.70933342 值会使得搜索方向过多，假如 <math id="M47"><mi mathvariant="normal">Δ</mi><mi mathvariant="normal">α</mi><mo>=</mo><mn mathvariant="normal">15</mn><mo>°</mo></math> http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=21890618&type= http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=21890617&type= 14.30866718 2.79399991 ，则需要搜索24个方向，从而使得搜索效率很低，同时如果没有格网的限制，则无法把握合理的前进步长 H 。 3） 如图16c所示，按本文所提方法，采用格网单元及其边缘特征，一方面可兼顾地表分类特征，因为地表覆盖物的类型是影响地表通达性的关键因子，格网边缘上有了地物类型特征，则最佳路径的搜索同等条件下会优先选取最易通行的地物类型；另一方面，有了格网单元，则有了算法可控的规则步长，易于沿用A*算法的搜索策略，充分利用A*算法本有的启发式的特性，从而尽可能找到最优路径。 另外，虽然在单元格划分时未考虑地形起伏信息，但在高分影像上，在悬崖、陡坎、突兀的山顶等较大的地形突变处，地表类型一般不连续，因此按地物图斑进行特征点选取，隐含了对异常地形起伏的处理。 对于格网单元内部存在“独立地物斑块”的情况，对该斑块采用形态学的膨胀算法，使用其范围扩展到格网单元的边上，从而可在格网单元边上选取表达该斑块类型的特征像元。 总体而言，本文提出的Grid A*算法与A*算法的本质区别在于，前者使用了由 <math id="M48"><mi>n</mi><mi>*</mi><mi>n</mi></math> http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=21890620&type= http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=21890619&type= 5.58799982 2.62466669 像元组成的格网作为计算单元，而后者则使用像元作为计算单元，当 n 取值为5、7、9、…等序列值时，Grid A*比A*算法效率要高，且 n 值越大计算效率越高，这一特点由 表2 表2 所给实验结果可以看出。 传统A*算法是一种通用的路径规划算法，与实际应用场景没有任何关系，基于栅格数据搜索时，它以像素为单元进行搜索，因此在像素分辨率的级别上，可以保证所搜索到的路径是最佳的。但由于该结果路径没有考虑实际应用的需求，因此该最佳路径的仅限于像素级别，如果实际交通工具需要覆盖多个像素的路宽，则传统A*算法无法解决这一问题。 Grid A*算法则使用了格网单元，而格网单元的选择则是依据具体应用而决定的，以应急救援场景为例，格网单元的大小取决于使用交通工具行驶所需的实际路宽。在格网单元的边缘上选取特征像元，从而确保Grid A*算法在使用格网为搜索单元的同时，兼顾了格网单元内部的地形特征，以便搜索到具有最优可通行性的路径。Grid A*算法结合了详细的地表要素分类结果，并对不同地表要素使用了不同的通达性函数，在将路宽作为参数因子进行计算搜索的情况下，与传统路径搜索算法相比，既具有更好的普适性，也具有更强的针对性。 实验表明，相比传统A*算法，Grid A*算法在保证路径规划结果可通行性的前提下，大幅度缩短了路径规划的所需的时间，且路径规划结果具有更优的通行性。 5　结论与展望 1 在野外应急救援活动中，为应急车辆在短时间内提取一条具有导航功能的路径具有重要的现实意义，通行路径的安全性和路径搜索的速度对任务的顺利完成有着重要的影响，路径规划算法的性能优劣对野外应急救援路径规划的可用性起到了决定性的作用。 通过本项研究表明，良好可靠的路径搜索必须基于：1）精准的地表要素分类结果，2）尽可能完备的通行代价函数，3）不小于实际交通工具所需的路径宽度，以及4）高效的搜索算法。本文所提方法是对这几方面的良好综合，实验也表明，本文提出的算法可以很好地解决基于无人机获取的超高分辨率影像，为不同交通工具搜索可靠通达性路径的问题。 现有基于影像或栅格的路径搜索算法往往单纯强调路径的通达性，以上几方面的处理比较模糊，严重的情况下，基本忽略了通达性必须结合交通工具所需路宽这一现实问题，代价函数构造也过于简略，无法应用于无人机获取的超高分辨率影像，也无法良好处理影响车辆真实行进代价的微地貌特征。 本文算法存在的主要不足在于格网特征像元的选取仅考虑了地表类型，而没有考虑地形起伏，因此特征像元的代表性有待提高；其实，格网单元内部像元的代价计算，除了考虑较极端情况外，对一般性的细节考虑不足。进一步的研究我们拟考虑更为合理的格网划分方法，如以高程为主，引入四叉树的方法分层次表达影响通达性的地物和地形因子，将有望使计算结果更为合理。此外，后续的研究结果我们将与户外实际驾车验证进行结合，进一步提高代价函数模型中有关参数的准确性。 参考文献（ References ） Choi K ， Lee I . 2012 . A UAV based close-range rapid aerial monitoring system for emergency responses[J]. ISPRS - International Archives of the Photogrammetry，Remote Sensing and Spatial Information Sciences，XXXVIII-1/C 22 : 247 - 252 . [ DOI: 10.5194/isprsarchives-XXXVIII-1-C22-247-2011 http://dx.doi.org/10.5194/isprsarchives-XXXVIII-1-C22-247-2011 ] A UAV based close-range rapid aerial monitoring system for emergency responses[J]. ISPRS - International Archives of the Photogrammetry，Remote Sensing and Spatial Information Sciences，XXXVIII-1/C Choi K ， Lee I ， Hong J ， Oh T ， Shin S . 2009 . Developing a UAV-based Rapid Mapping System for Emergency Response [J]. Proceedings of SPIE - The International Society for Optical Engineering . [ DOI: 10.1117/12.818492 http://dx.doi.org/10.1117/12.818492 ] Developing a UAV-based Rapid Mapping System for Emergency Response Delmerico J ， Mueggler E ， Nitsch J ， Scaramuzza D . 2017 . Active Autonomous Aerial Exploration for Ground Robot Path Planning [J]. IEEE Robotics and Automation Letters ， 2 ( 2 ): 664 - 671 . [ DOI: 10.1109/LRA.2017.2651163 http://dx.doi.org/10.1109/LRA.2017.2651163 ] Active Autonomous Aerial Exploration for Ground Robot Path Planning F Linlin . 2017 . Research on Cross-country Path Planning Technology Based on Hexagonal Grid [D]. Zhengzhou : PLA Information Engineering University ， 10 - 53 Research on Cross-country Path Planning Technology Based on Hexagonal Grid 范林林 . 2017 . 基于六角格网的越野路径规划技术方法研究 . 郑州 : 解放军信息工程大学 ， 10 - 53 基于六角格网的越野路径规划技术方法研究 Harabor D ， Grastien A . 2011 . Online graph pruning for pathfinding on grid maps.[C] . Proceedings of the Twenty-Fifth AAAI Conference on Artificial Intelligence. San Francisco, California, USA : AAAI Press , 2011 : 1114 - 1119 Online graph pruning for pathfinding on grid maps.[C] Li J ， Deng G ， Luo C ， Lin Q ， Yan Q ， Ming Z . 2016 . A Hybrid Path Planning Method in Unmanned Air/Ground Vehicle (UAV/UGV) Cooperative Systems [J]. IEEE Transactions on Vehicular Technology : 1 . [ DOI: 10.1109/TVT.2016.2623666 http://dx.doi.org/10.1109/TVT.2016.2623666 ] A Hybrid Path Planning Method in Unmanned Air/Ground Vehicle (UAV/UGV) Cooperative Systems L Xiaodong . 2017 . Terrain Traversability Analysis in Air-ground Collaborative Emergency [D]. Beijing : Peking University ， 41 - 45 Terrain Traversability Analysis in Air-ground Collaborative Emergency 黎晓东 . 2017 . 面向空地协同应急的地表可通行性分析 . 北京 : 北京大学 ， 41 - 45 面向空地协同应急的地表可通行性分析 L Xiuxian ， S Min ， L Xiaodong ， R Xiang . 2019 . Terrain traversability analysis method for Air-ground collaborative emergency [J]. Journal of Shihezi University（Natural Science） ， 37 ( 01 ): 12 - 20 Terrain traversability analysis method for Air-ground collaborative emergency 李修贤 , 孙敏 , 黎晓东 , 任翔 . 2019 . 面向空地协同应急的地表可通行性分析方法 . 石河子大学学报(自然科学版) ， 37 ( 01 ): 12 - 20 [ DOI: 10.13880/j.cnki.65-1174/n.2019.01.002 http://dx.doi.org/10.13880/j.cnki.65-1174/n.2019.01.002 ] 面向空地协同应急的地表可通行性分析方法 S Yuze . 2020 . Global path planning and trajectory tracking of unmanned wheeled vehicles on terrains [D]. Changchun : Jilin University ， 17 - 43 Global path planning and trajectory tracking of unmanned wheeled vehicles on terrains 孙玉泽 . 2020 . 无人轮式车辆越野路面全局路径规划与轨迹跟踪 . 长春 : 吉林大学 ， 17 - 43 无人轮式车辆越野路面全局路径规划与轨迹跟踪 W Tianyi ， X Jiheng ， L Jianyong ， L Wei . 2013 . Research of cross-country path planning based on improved A* algorithm [J]. Application Research of Computers ， 30 ( 06 ): 1724 - 1726 Research of cross-country path planning based on improved A* algorithm 吴天羿 , 许继恒 , 刘建永 , 廖伟 . 2013 . 基于改进A*算法的越野路径规划研究 . 计算机应用研究 ， 30 ( 06 ): 1724 - 1726 [ DOI: 10.3969/j.issn.1001-3695.2013.06.032 http://dx.doi.org/10.3969/j.issn.1001-3695.2013.06.032 ] 基于改进A*算法的越野路径规划研究 X A'Xing ， Z Jin ， Z Tao ， H Qiuxia . 2019 . Target searching and global path planning in UAV/UGV cooperative systems [J]. Application of Electronic Technique ， 45 ( 01 ): 5 - 9 Target searching and global path planning in UAV/UGV cooperative systems 席阿行 , 赵津 , 周滔 , 胡秋霞 . 2019 . UAV/UGV协同环境下的目标识别与全局路径规划研究 . 电子技术应用 ， 45 ( 01 ): 5 - 9 [ DOI: 10.16157/j.issn.0258-7998.182261 http://dx.doi.org/10.16157/j.issn.0258-7998.182261 ] UAV/UGV协同环境下的目标识别与全局路径规划研究 Yap P ， Burch N ， Holte R C ， Schaeffer J . 2011 . Block A*: Database-Driven Search with Applications in Any-Angle Path-Planning.[C] Proceedings of the Twenty-Fifth AAAI Conference on Artificial Intelligence. San Francisco, California, USA: AAAI Press , 2011 : 120 - 125 Block A*: Database-Driven Search with Applications in Any-Angle Path-Planning.[C] Proceedings of the Twenty-Fifth AAAI Conference on Artificial Intelligence. San Francisco, California, USA: Z De-Qun ， D Jian-Ying ， C Peng-Yu ， S Jin-Hai . 2017 . Optimal Path Planning for 3D Map Based on A* Algorithm [J]. Computer Systems and Applications ， 26 ( 07 ): 146 - 152 Optimal Path Planning for 3D Map Based on A* Algorithm In Chinese) (赵德群 , 段建英 , 陈鹏宇 , 苏晋海 . 2017 . 基于A*算法的三维地图最优路径规划 . 计算机系统应用 ， 26 ( 07 ): 146 - 152 [ DOI: 10.15888/j.cnki.csa.005859 http://dx.doi.org/10.15888/j.cnki.csa.005859 ] 基于A*算法的三维地图最优路径规划 10.11834/jrs.20211320 TP701 A 王修远，孙敏，李修贤，周航，赵仁亮.XXXX.Grid A*：面向野外空地协同应急处置的快速路径规划算法.遥感学报，XX（XX）： 1-15 王修远，孙敏，李修贤，周航，赵仁亮.XXXX.Grid A*：面向野外空地协同应急处置的快速路径规划算法.遥感学报，XX（XX）： 1-15 Wang xiuyuan，Sun min，Li xiuxian，Zhou hang，Zhao Renliang. XXXX. Grid A*：A Fast Path Planning Algorithm for Air-Ground Cooperative Response of Emergency Rescue in the Field. National Remote Sensing Bulletin， XX（XX）：1-15 Wang xiuyuan，Sun min，Li xiuxian，Zhou hang，Zhao Renliang. XXXX. Grid A*：A Fast Path Planning Algorithm for Air-Ground Cooperative Response of Emergency Rescue in the Field. National Remote Sensing Bulletin， XX（XX）：1-15 新疆兵团重大项目（2017DB005）。 Supported by Supported by Major project of the Xinjiang Production and Construction Corps, China(No.2017DB005) 2009-01-06 2021-11-11 2009-05-20 遥感学报