基于地形数据的长距离越野路径快速规划方法研究  

Fast Method for Long-Distance Off-Road Path Planning based on Terrain Data

作　　者：冯世盛 徐青[1] 朱新铭 邹霓霄 李帅 FENG Shisheng;XU Qing;ZHU Xinming;ZHOU Nixiao;LI Shuai(Information Engineering University,Geospatial Information Institute,Zhengzhou 450001,China)

机构地区：[1]信息工程大学,郑州450001

出　　处：《地球信息科学学报》2022年第9期1742-1754,共13页Journal of Geo-information Science

摘　　要：越野环境下机动车辆的快速路径规划在野外搜救、应急抢险及军事作战等领域均具有重要意义,在以上场景中,随着空间维数的增加,传统路径搜索算法计算复杂性急剧增长,可能无法在既定时间内求解可靠路径。为解决上述不足,本文结合越野路径规划不受路网通行限制以及两点之间直线最短的特点,提出以方向指向作为搜索策略的启发式算法,该算法搜索效率大幅提升,却难以保证求解质量。为进一步提高求解质量,提出了带有方向指向的Dijkstra分段算法,该算法在较低精度环境模型下通过Dijkstra算法找到最优路径,并将该路径进行分段,各分段以方向指向作为搜索策略进行路径搜索,从而在长距离越野路径规划中快速规划通行方案。为验证该算法的有效性,本文利用山西省某市的数字高程模型数据进行实验,引入了窗口移动法对地形进行先期的坡度计算和通行性分析,构建越野环境模型,调用路径搜索算法进行规划。实验结果表明,本文所提算法相比Dijkstra算法计算效率得到了大幅提升,且规划路径的长度接近于最优解。The fast path planning of motor vehicles in the off-road environment is of great significance in the fields of field search and rescue,emergency rescue,and military operations.In the above scenarios,with the increase of spatial dimension,the computational complexity of traditional path search algorithms increases exponentially,and may not be able to be calculated within a given time.To solve the above deficiencies,this paper proposes a heuristic algorithm with directional pointing as a search strategy,combining the characteristics of off-road path planning that is not restricted by road network traffic and the shortest straight line between two points.In order to further improve the solution quality,a Dijkstra segmentation algorithm with directional pointing is proposed.This algorithm finds the optimal path through Dijkstra algorithm in a low-precision environment model and divides the path into segments.Each segment is oriented in a direction.Route search is performed as a search strategy to quickly plan passage schemes in long-distance off-road route planning.In order to verify the effectiveness of the algorithm,this paper uses the digital elevation model data of a city in Shanxi Province to conduct experiments and introduces the window movement method to perform preliminary slope calculation and trafficability analysis of the terrain,build an off-road environment model,and call the path search algorithm to carry out path planning.The experimental results show that the computational efficiency of the algorithm proposed in this paper has been greatly improved compared to the Dijkstra algorithm,and the length of the planned path is close to the optimal solution.

关 键 词：越野环境 路径规划 长距离 环境建模 路径搜索算法 算法设计 算法效率 

分 类 号：TP18[自动化与计算机技术—控制理论与控制工程] P208[自动化与计算机技术—控制科学与工程] U495[天文地球—地图制图学与地理信息工程]