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

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]. 计算机应用, 2021, 41(9): 2560-2568.
[2]	管其杰, 张挺, 李德亚, 周绍景, 杜奕. 基于多分辨率生成对抗网络的空间数据不确定性重建方法[J]. 计算机应用, 2021, 41(8): 2306-2311.
[3]	牛康力, 谌雨章, 沈君凤, 曾张帆, 潘永才, 王绎冲. 基于深度学习的双通道夜视图像复原方法[J]. 计算机应用, 2021, 41(6): 1775-1784.
[4]	梁敏, 王昊榕, 张瑶, 李杰. 基于加速残差网络的图像超分辨率重建方法[J]. 计算机应用, 2021, 41(5): 1438-1444.
[5]	卞鹏程, 郑忠龙, 李明禄, 何依然, 王天翔, 张大伟, 陈丽媛. 基于注意力融合网络的视频超分辨率重建[J]. 计算机应用, 2021, 41(4): 1012-1019.
[6]	段友祥, 张含笑, 孙歧峰, 孙友凯. 基于拉普拉斯金字塔生成对抗网络的图像超分辨率重建算法[J]. 计算机应用, 2021, 41(4): 1020-1026.
[7]	王永金, 左羽, 吴恋, 崔忠伟, 赵晨洁. 基于注意力机制的图像超分辨率重建[J]. 计算机应用, 2021, 41(3): 845-850.
[8]	王家亮, 李树华, 张海涛. 基于贝叶斯估计与区域划分遍历的四轴飞行器避障路径规划算法[J]. 计算机应用, 2021, 41(2): 384-389.
[9]	黄书召, 田军委, 乔路, 王沁, 苏宇. 基于改进遗传算法的无人机路径规划[J]. 计算机应用, 2021, 41(2): 390-397.
[10]	魏博, 杨茸, 舒思豪, 万勇, 苗建国. 基于离子运动-人工蜂群算法的移动机器人路径规划[J]. 计算机应用, 2021, 41(2): 379-383.
[11]	李萌, 秦品乐, 曾建潮, 李俊伯. 基于磁共振影像层间插值的超分辨率及多视角融合[J]. 《计算机应用》唯一官方网站, 2021, 41(11): 3362-3367.
[12]	李伟, 金世俊. 基于人工势场法和启发式采样的最优路径收敛方法[J]. 计算机应用, 2021, 41(10): 2912-2918.
[13]	刘思嘉, 童向荣. 基于强化学习的城市交通路径规划[J]. 计算机应用, 2021, 41(1): 185-190.
[14]	林静, 黄玉清, 李磊民. 基于球形矩匹配与特征判别的图像超分辨率重建[J]. 计算机应用, 2020, 40(8): 2345-2350.
[15]	杨佳义, 陈勇. 低照度视频图像自适应补偿增强的设计与实现[J]. 计算机应用, 2020, 40(8): 2372-2377.