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

doi:10.11772/j.issn.1001-9081.2018041340

计算机应用 ›› 2018, Vol. 38 ›› Issue (11): 3188-3192.DOI: 10.11772/j.issn.1001-9081.2018041340

• 第七届中国数据挖掘会议(CCDM 2018) • 上一篇下一篇

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

张润莲^1,2, 张鑫³, 张楚芸², 奚玉昂²

1. 桂林电子科技大学广西密码学与信息安全重点实验室, 广西桂林 541004;
2. 广西高校云计算与复杂系统重点实验室, 广西桂林 541004;
3. 重庆电子工程职业学院电子与物联网学院, 重庆 401331

收稿日期:2018-04-30 修回日期:2018-06-05 发布日期:2018-11-10 出版日期:2018-11-10
通讯作者: 张润莲
作者简介:张润莲(1974-),女,山西介休人,副教授,博士,主要研究方向:分布式计算、信息安全;张鑫(1990-),男,重庆人,硕士,主要研究方向:路径规划;张楚芸(1993-),女,广西贺州人,硕士研究生,主要研究方向:信任计算;奚玉昂(1991-),男,山东单县人,硕士研究生,主要研究方向:路径规划。
基金资助:
广西密码学与信息安全重点实验室（GCIS201623，GCIS201705）；广西无线宽带通信与信号处理重点实验室基金资助项目（GXKL061510，GXKL0614110）；广西高校云计算与复杂系统重点实验室（YF16205）；广西研究生教育创新计划资助项目（YCSW2018138，2017YJCX26）。

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

ZHANG Runlian^1,2, ZHANG Xin³, ZHANG Chuyun², XI Yuang²

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).

摘要/Abstract

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

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

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

中图分类号:

TP301.6

张润莲, 张鑫, 张楚芸, 奚玉昂. 规则网格数字高程模型中基于距离与坡度的路径规划算法[J]. 计算机应用, 2018, 38(11): 3188-3192.

ZHANG Runlian, ZHANG Xin, ZHANG Chuyun, XI Yuang. Path planning algorithm based on distance and slope in regular Grid digital elevation model[J]. Journal of Computer Applications, 2018, 38(11): 3188-3192.

参考文献

[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.)

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

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

PDF

可视化

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 15

编辑推荐

Metrics

[1]	田润泽, 周宇龙, 朱洪, 薛岗. 基于局部信息的服务迁移路径选择算法[J]. 《计算机应用》唯一官方网站, 2024, 44(7): 2168-2174.
[2]	马天, 席润韬, 吕佳豪, 曾奕杰, 杨嘉怡, 张杰慧. 基于深度强化学习的移动机器人三维路径规划方法[J]. 《计算机应用》唯一官方网站, 2024, 44(7): 2055-2064.
[3]	郭琳, 刘坤虎, 马晨阳, 来佑雪, 徐映芬. 基于感受野扩展残差注意力网络的图像超分辨率重建[J]. 《计算机应用》唯一官方网站, 2024, 44(5): 1579-1587.
[4]	刘子涵, 周登文, 刘玉铠. 基于全局依赖Transformer的图像超分辨率网络[J]. 《计算机应用》唯一官方网站, 2024, 44(5): 1588-1596.
[5]	李建强, 何舟. 面向多行程取送货车辆路径问题的混合NSGA-Ⅱ[J]. 《计算机应用》唯一官方网站, 2024, 44(4): 1187-1194.
[6]	刘扬, 刘蓉, 方可, 张心月, 王光旭. 基于帧间跨越光流的视频超分辨率重建网络[J]. 《计算机应用》唯一官方网站, 2024, 44(4): 1277-1284.
[7]	黄海新, 于广威, 程寿山, 李春明. 基于改进灰狼优化的桥梁检测爬壁机器人全覆盖路径规划[J]. 《计算机应用》唯一官方网站, 2024, 44(3): 966-971.
[8]	邓辅秦, 官桧锋, 谭朝恩, 付兰慧, 王宏民, 林天麟, 张建民. 基于请求与应答通信机制和局部注意力机制的多机器人强化学习路径规划方法[J]. 《计算机应用》唯一官方网站, 2024, 44(2): 432-438.
[9]	宋紫阳, 李军怀, 王怀军, 苏鑫, 于蕾. 基于路径模仿和SAC强化学习的机械臂路径规划算法[J]. 《计算机应用》唯一官方网站, 2024, 44(2): 439-444.
[10]	邓辅秦, 谭朝恩, 黎俊炜, 钟家铭, 付兰慧, 张建民, 王宏民, 李楠楠, 姜炳春, 林天麟. 面向大型仓储环境的基于冲突搜索算法[J]. 《计算机应用》唯一官方网站, 2024, 44(12): 3854-3860.
[11]	孙鉴, 马宝全, 吴隹伟, 杨晓焕, 武涛, 陈攀. 地震场景下无人机群路径规划与任务分配均衡联合优化[J]. 《计算机应用》唯一官方网站, 2024, 44(10): 3232-3239.
[12]	陈豪, 夏振平, 程成, 林李兴, 张博文. 基于Transformer-CNN的轻量级图像超分辨率重建网络[J]. 《计算机应用》唯一官方网站, 2024, 44(1): 292-299.
[13]	路琨婷, 费蓉蓉, 张选德. 融合卷积神经网络的遥感图像全色锐化[J]. 《计算机应用》唯一官方网站, 2023, 43(9): 2963-2969.
[14]	申利华, 李波. 基于特征金字塔网络和密集网络的肺部CT图像超分辨率重建[J]. 《计算机应用》唯一官方网站, 2023, 43(5): 1612-1619.
[15]	苏亚婷, 刘翠响. 基于高分辨率网络和图卷积网络的三维人体重建模型[J]. 《计算机应用》唯一官方网站, 2023, 43(2): 583-588.