基于A~＊算法的三维地图最优路径规划

Optimal Path Planning for 3D Map Based on A~＊ Algorithm

研究了基于A~*算法的适合人步行行走的山地环境下三维地图最优路径规划算法及实现.本文考虑了三维山地无路网信息覆盖的条件较差环境,对A~*算法进行改进,并利用三维地形DEM数据计算出一条相对平缓且长度较短的三维路径.改进算法对三维条件下路径最短的评价标准由原有的空间距离累加最短改进为先将空间等效成水平距离,再计算距离是否最短.同时,本文充分考虑了搜索点周围环境的整体坡度信息作为启发信息,来降低算法寻找的路径走在陡坡上的概率.实验表明,本算法最终计算出的三维最优路径在平缓度及路径最短上有所改善,基本符合人步行行走的习惯.

The optimal path planning algorithm and implementation of 3D map based on A＊ algorithm in mountainous environment are studied in this paper. It considers the condition of poor coverage of 3D mountain-free network information coverage, improves the A＊ algorithm and uses 3D terrain DEM data to calculate a relatively smooth and short three-dimensional path. The improved algorithm can improve the shortest path evaluation criterion in threedimensional space from the original spatial distance accumulation to the shortest distance, and then calculates whether the distance is the shortest. At the same time, the global gradient information of the surroundings of the search point is considered as the heuristic information to reduce the probability that the path the algorithm looks for is steep.Experimental results show that the proposed algorithm can improve the smoothness and shortest path of the threedimensional optimal path, which accords with the walking habits of human beings.