Path planning algorithm based on distance and slope in regular Grid digital elevation model
ZHANG Runlian1,2, ZHANG Xin3, ZHANG Chuyun2, XI Yuang2
1. Guangxi Key Laboratory of Cryptography and Information Security, Guilin University of Electronic Technology, Guilin Guangxi 541004, China; 2. Guangxi Colleges and Universities Key Laboratory of Cloud Computing and Complex Systems, Guilin Guangxi 541004, China; 3. School of Electronics and Internet of Things, Chongqing College of Electronic Engineering, Chongqing 401331, China
Abstract：Aiming at the low efficiency of A* algorithm in Digital Elevation Model (DEM) path planning, an improved A* algorithm based on distance and slope was proposed. A new evaluation function were designed by using distance and slope regarded as evaluation indexes in regular grid digital elevation model, and the pathability of surface barrier was judged. And in order to ensure that the improved algorithm was adaptive to the changing of the resolution ratio for DEM data, the parameters of the evaluation function were calculated according to the DEM data of the actual scene in the path searching process. Finally, a dynamic weight was changed with the changing of path searching, which could optimize path selection by adjusting the influence of completeness function and heuristic function on evaluation result. The simulation results show that the improved algorithm can adapt to the changing of DEM resolution by parameter adjustment, search the optimized path, reduce the search time and improve the search efficiency.
[1] HART P E, NILSSON N J, RAPHAEL B. A formal basis for the heuristic determination of minimum cost paths[J].IEEE Transactions of Systems Science and Cybernetics, 2007, 4(2):101-107. [2] 田华亭,李涛,秦颖.基于A*改进算法的四向移动机器人路径搜索研究[J]. 控制与决策,2017, 32(6):1007-1012.(TIAN H T, LI T, QIN Y. Research of four-way mobile robot path search based on improved A* algorithm[J]. Control and Decision, 2017, 32(6):1007-1012.) [3] ALGFOOR Z A, SUNAR M S, ABDULLAH A. A new weighted pathfinding algorithms to reduce the search time on grid maps[J]. Expert Systems with Applications, 2017, 71:319-331. [4] 冷勋泰,孙广中.路网上异步并行加权A*最短路径算法[J]. 中国科学技术大学学报,2014, 44(10):867-873.(LENG X T, SUN G Z. Asynchronous parallelism weighted A* algorithm for the finding shortest path on road networks[J]. Journal of University of Science and Technology of China, 2014, 44(10):867-873.) [5] ANISYAH A S, RUSMIN P H, HINDERSAH H. Route optimization movement of tugboat with A* tactical pathfinding in SPIN 3D simulation[C]//Proceedings of the 20154th International Conference on Interactive Digital Media. Piscataway, NJ:IEEE, 2015:1-5. [6] 赵奇,赵阿群.一种基于A*算法的多径寻由算法[J]. 电子与信息学报,2013,35(4):952-957.(ZHAO Q, ZHAO A Q. A multi-path routing algorithm base on A* algorithm[J]. Journal of Electronics & Information Technology, 2013, 35(4):952-957.) [7] GHAFFARI A. An energy efficient routing protocol for wireless sensor networks using A-star algorithm[J]. Journal of Applied Research and Technology, 2014, 12(4):815-822. [8] 林笃斌,李欣.基于DEM格网的改进型A*路径搜索算法[J]. 计算机工程与设计, 2011, 32(10):3414-3418. (LIN D B, LI X. Improved A* path-finding algorithm based on DEM-Grid[J]. Computer Engineering and Design, 2011, 32(10):3414-3418.) [9] 张慧, 荣学文, 李贻斌, 等. 四足机器人地形识别与路径规划算法[J]. 机器人,2015, 37(5):546-556. (ZHANG H, RONG X W, LI Y B, et al. Terrain recognition and path planning for quadruped robot[J]. Robot, 2015, 37(5):546-556.) [10] 孙立国, 李世丹, 王德生, 等.基于多重分形的地形辅助导航路径规划算法[J]. 清华大学学报(自然科学版),2011, 51(1): 111-114, 121. (SUN L G, LI S D, WANG D S, et al. Flight route planning for terrain navigation using multi-fractal theory[J]. Journal of Tsinghua University (Science and Technology), 2011, 51(1): 111-114, 121.) [11] 郝振国, 王玉玫.双向A*算法在军事路径规划中的应用[J]. 计算机工程与应用, 2011, 47(29): 246-248. (HAO Z G, WANG Y M. Application of bidirectional A* method in military route planning[J]. Computer Engineering and Applications, 2011, 47(29): 246-248.) [12] PELECHANO N, FUENTES C. Hierarchical path-finding for navigation meshes (HNA*)[J]. Computers & Graphics, 2016, 59: 68-78. [13] 魏祥泉, 黄建明, 顾冬晴, 等. 火星车自主导航与路径规划技术研究[J]. 深空探测学报, 2016, 3(3): 275-281. (WEI X Q, HUANG J M, GU D Q, et al. Researches on the techniques of autonomous navigation and path planning for mars rover[J]. Journal of Deep Space Exploration, 2016, 3(3): 275-281.) [14] 张鑫. 基于规则DEM的地形识别及路径规划研究[D]. 桂林: 桂林电子科技大学, 2017. (ZHANG X. Research on terrain recognition and path planning based on regular DEM[D]. Guilin: Guilin University of Electronic Technology, 2017.) [15] 李天文, 刘学军, 陈正江,等.规则格网DEM坡度坡向算法的比较分析[J]. 干旱区地理, 2004, 27(3): 398-404.(LI T W, LIU X J, CHEN Z J, et al. Comparative analysis of slope orientation algorithm for DEM slope in regular Grid[J]. Arid Land Geography, 2004, 27(3): 398-404.) [16] 金祖孟,陈自悟,地球概论[M]. 北京: 高等教育出版社, 1997:3-5.(JIN Z M, CHEN Z W. Introduction to the Earth[M]. Beijing: Higher Education Press, 1997:3-5.)
2018, Vol. 38 
