[1]叶小艳,钟华钧,邓可儿.一种基于改进 A*算法的室内导航路径规划方法[J].计算机技术与发展,2022,32(02):202-206.[doi:10. 3969 / j. issn. 1673-629X. 2022. 02. 033]
　YE Xiao-yan,ZHONG Hua-jun,DENG Ke-er.A Path Planning Method of Indoor Navigation Based on Improved A-Star Algorithm[J].,2022,32(02):202-206.[doi:10. 3969 / j. issn. 1673-629X. 2022. 02. 033]
点击复制

一种基于改进 A*算法的室内导航路径规划方法()
分享到：

《计算机技术与发展》[ISSN:1006-6977/CN:61-1281/TN]

卷:
32
期数:
2022年02期
页码:
202-206
栏目:
应用前沿与综合
出版日期:
2022-02-10

文章信息/Info

Title:
A Path Planning Method of Indoor Navigation Based on Improved A-Star Algorithm
文章编号:
1673-629X(2022)02-0202-05
作者:
叶小艳; 钟华钧; 邓可儿
广州软件学院 网络技术系,广东 广州 510990
Author(s):
YE Xiao-yan; ZHONG Hua-jun; DENG Ke-er
Department of Network Technology,Guangzhou Institute of Software,Guangzhou 510990,China
关键词:
A*算法; 路径规划; 室内导航; 启发函数; 寻路节点
Keywords:
A-Star algorithm; path planning; indoor navigation; heuristic function; path finding node
分类号:
TP309. 7
DOI:
10. 3969 / j. issn. 1673-629X. 2022. 02. 033
摘要:
路径规划是室内导航研究的关键技术之一。 A*算法是一种常见的路径规划算法,当区域的点数量较少时,找寻最优路径是最有效的直接搜索方法。 但当路径点规模较大时,使用数值优化算法求解最佳路径的难度急剧增加,导致规划时间所需时间过长,不符合实时性要求。 为提高路径规划方法中的效率和稳定性,在梳理室内导航路径规划已有算法和方案的基础上,分析了 A*算法的基本思想与实现步骤,并针对室内导航中 A*路径算法存在的问题,提出了一种改进型 A*算法优化的方案。 利用用户对最短距离和直行路程的需求,在位置计算中,引入同时考虑方向和距离启发信息的启发函数,把 POI 点与寻路节点分开处理,以映射的方式建立联系。 将该方案应用于室内导航中 A*算法实现伪代码,对算法改进前后进行算法效率测试。 结果表明,改进后 A*算法的整体效率提升了近 50% ,改进型 A*算法在室内导航路径规划的效率和稳定性比较优,达到了加速导航算法的目的。
Abstract:
Path planning is one of the key technologies of indoor navigation research. A - Star algorithm is a common path planningalgorithm. When the number of points in the region is small,it will? ? ?be the most effective direct search method for finding the optimalpath. However,when the scale of path points is large,it’s difficult to use numerical optimization algorithm to solve the optimal pathincreases sharply,resulting in too long planning time,which does not meet the real-time requirements. In order to improve the efficiencyand stability of the path planning method,based? ? on combing the existing algorithms and schemes of indoor navigation path planning,weanalyze the basic idea and implementation steps of A-Star algorithm,and propose an improved A-Star algorithm optimization schemeaiming at the problems of A-Star algorithm in indoor navigation. According to the user’s demand for the shortest distance and straighttravel distance,a heuristic function considering both direction and distance heuristic information is introduced in the location calculation.The POI points and the path finding nodes are processed separately, and the connection is established by mapping. The scheme is appliedto implement pseudo code of A-Star algorithm in indoor navigation,and the algorithm efficiency is tested before and after the algorithm isimproved. The results show that the overall efficiency of the improved A - Star algorithm is improved by nearly 50% , with betterefficiency and stability,so as to achieve the purpose of accelerating the navigation algorithm.

相似文献/References:

[1]熊力 方康玲 刘永祥.GPS导航系统在道路巡检中的应用研究[J].计算机技术与发展,2010,(06):246.
　XIONG Li,FANG Kang-ling,LIU Yong-xiang.Research of GPS Navigation System in Road Patrol Line[J].,2010,(02):246.
[2]胡佳 汪峥.工业机器人路径规划的双目标优化策略[J].计算机技术与发展,2009,(05):16.
　HU Jia,WANG Zheng.Bi- objective Optimization of Path Planning for Manipulators[J].,2009,(02):16.
[3]张荣松 包家汉.基于改进遗传算法的机器人路径规划[J].计算机技术与发展,2009,(07):20.
　ZHANG Rong-song,BAO Jia-han.Robot Path Planning Based on Modified Genetic Algorithm[J].,2009,(02):20.
[4]冯晓辉 马光思.数码谜题求解的算法设计及其扩展研究[J].计算机技术与发展,2009,(08):110.
　FENG Xiao-hui,MA Guang-si.Algorithm Design and Extension Research of N - Puzzle Problem[J].,2009,(02):110.
[5]李培 何中市.基于ArcGIS和GPS的水电气管理系统设计与实现[J].计算机技术与发展,2009,(01):172.
　LI Pei,HE Zhong-shi.Design and Implementation Water, Electricity and Gas Management System Based on ArcGIS and GPS[J].,2009,(02):172.
[6]刘雁菲 邵晓东 李申.基于Vega的虚拟漫游场景中的路径规划研究[J].计算机技术与发展,2008,(06):9.
　LIU Yan-fei,SHAO Xiao-dong,LI Shen.Path Planning Based on Vega of Navigation in Virtual Environment[J].,2008,(02):9.
[7]陈得宝 李庆 李群 李峥.基于内分泌思想的改进粒子群算法[J].计算机技术与发展,2008,(10):61.
　CHEN De-bao,LI Qing,LI Qun,et al.An Improved Particle Swarm Algorithm Based on Endocrine Idea[J].,2008,(02):61.
[8]范莉丽 王奇志.改进的生物激励神经网络的机器人路径规划[J].计算机技术与发展,2006,(04):19.
　FAN Li-li,WANG Qi-zhi.Robot Path Planning of Modified Biologically Inspired Neural Networks[J].,2006,(02):19.
[9]王肖青 王奇志.传统人工势场的改进[J].计算机技术与发展,2006,(04):96.
　WANG Xiao-qing,WANG Qi-zhi.An Evolutionary Method of Traditional Artificial Potential Field[J].,2006,(02):96.
[10]朱永红 张燕平.用VC＋＋实现基于A＊算法的八数码问题[J].计算机技术与发展,2006,(09):32.
　ZHU Yong-hong,ZHANG Yan-ping.Programming for Eight - Figure Puzzle Problem Based on Algorithm A ＊ with Visual C ＋ ＋[J].,2006,(02):32.
[11]郑延斌 李新源 段德全.一种保持Agent团队队形的路径规划方法[J].计算机技术与发展,2009,(07):159.
　ZHENG Yan-bin,LI Xin-yuan,DUAN De-quan.A Path Planning Algorithm with Agent Team Formation Maintained[J].,2009,(02):159.
[12]刘钰 陆建峰 蔡海舟.基于改进A＊算法的机器人路径规划方法研究[J].计算机技术与发展,2012,(12):108.
　LIU Yu,LU Jian-feng,CAI Hai-zhou.Research on Path Planning Method of Robot Based on Improved A ＊ Algorithm[J].,2012,(02):108.
[13]马静,王佳斌,张雪. A*算法在无人车路径规划中的应用[J].计算机技术与发展,2016,26(11):153.
　MA Jing,WANG Jia-bin,ZHANG Xue. Application of A* Algorithm in Unmanned Vehicle Path Planning[J].,2016,26(02):153.
[14]程 杰,陈姚节.基于正六边形建模的无人水面艇路径规划[J].计算机技术与发展,2020,30(11):37.[doi:10. 3969 / j. issn. 1673-629X. 2020. 11. 007]
　CHENG Jie,CHEN Yao-jie.Path Planning of Unmanned Surface Vehicle Based on Regular Hexagon Modeling[J].,2020,30(02):37.[doi:10. 3969 / j. issn. 1673-629X. 2020. 11. 007]

更新日期/Last Update: 2022-02-10