Journal of Computer Applications ›› 2018, Vol. 38 ›› Issue (11): 3188-3192.DOI: 10.11772/j.issn.1001-9081.2018041340

Previous Articles     Next Articles

Path planning algorithm based on distance and slope in regular Grid digital elevation model

ZHANG Runlian1,2, ZHANG Xin3, ZHANG Chuyun2, XI Yuang2   

  1. 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
  • Received:2018-04-30 Revised:2018-06-05 Online:2018-11-10 Published:2018-11-10
  • Supported by:
    This work is partially supported by the Guangxi Key Laboratory of Cryptography and Information Security of China (GCIS201623, GCIS201705), the Guangxi Key Laboratory of Wireless Wideband Communication and Signal Processing (GXKL061510, GXKL0614110), the Guangxi Colleges and Universities Key Laboratory of Cloud Computing and Complex Systems (YF16205), the Innovation Project of Guangxi Graduate Education (YCSW2018138, 2017YJCX26).

规则网格数字高程模型中基于距离与坡度的路径规划算法

张润莲1,2, 张鑫3, 张楚芸2, 奚玉昂2   

  1. 1. 桂林电子科技大学 广西密码学与信息安全重点实验室, 广西 桂林 541004;
    2. 广西高校云计算与复杂系统重点实验室, 广西 桂林 541004;
    3. 重庆电子工程职业学院 电子与物联网学院, 重庆 401331
  • 通讯作者: 张润莲
  • 作者简介:张润莲(1974-),女,山西介休人,副教授,博士,主要研究方向:分布式计算、信息安全;张鑫(1990-),男,重庆人,硕士,主要研究方向:路径规划;张楚芸(1993-),女,广西贺州人,硕士研究生,主要研究方向:信任计算;奚玉昂(1991-),男,山东单县人,硕士研究生,主要研究方向:路径规划。
  • 基金资助:
    广西密码学与信息安全重点实验室(GCIS201623,GCIS201705);广西无线宽带通信与信号处理重点实验室基金资助项目(GXKL061510,GXKL0614110);广西高校云计算与复杂系统重点实验室(YF16205);广西研究生教育创新计划资助项目(YCSW2018138,2017YJCX26)。

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.

Key words: path planning, A* algorithm, Digital Elevation Model (DEM), resolution ratio, dynamic weight

摘要: 针对A*算法在数字高程模型(DEM)路径规划中的低效问题,提出一种基于距离与坡度的改进A*寻路算法。该算法面向规则网格DEM,以距离和坡度作为路径搜索评估指标,设计新的评价函数,并以地表障碍评判路径的可通行性。在寻路过程中,根据实际场景DEM数据计算相匹配的参数,使得改进算法能自适应不同场景下DEM数据分辨率的变化;采用动态权值调整完备性函数和启发性函数对评价结果的影响,优化路径选择。仿真测试结果表明,改进算法能够通过参数调整适应DEM分辨率的变化,搜索出优化的路径,降低搜索时间,提高搜索效率。

关键词: 路径规划, A*算法, 数字高程模型, 分辨率, 动态权值

CLC Number: