《计算机应用研究》|Application Research of Computers

应用于机器人路径规划的双向时效A*算法

Bidirectional time-efficient A* algorithm for robot path planning

免费全文下载 (已被下载 次)  
获取PDF全文
作者 高民东,张雅妮,朱凌云
机构 重庆理工大学 计算机科学与工程学院,重庆 400054
统计 摘要被查看 次,已被下载
文章编号 1001-3695(2019)03-030-0792-04
DOI 10.19734/j.issn.1001-3695.2017.10.0982
摘要 针对时效A*算法为了大幅减少算法时间,导致路径规划长度增加和路径锯齿过多的问题,提出一种改进的双向时效A*算法,该方法从起点和终点同时运行时效A*算法寻找路径,并采用多近邻栅格距离计算方案;同时,根据不同环境地图对传统A*算法、时效A*算法和双向时效A*算法运行结果进行对比研究及分析;最后,制定算法时间、路径长度两个指标来评判算法的优劣。实验结果显示,双向时效A*算法相对于传统A*算法,算法时间最大减少76.8%,相对于时效A*算法,时间最大减少55.4%,并解决了时效A*算法规划路径距离增加、路径不够平滑的问题。
关键词 路径规划;启发式算法;时效A*算法
基金项目 国家自然科学基金资助项目(61502064)
重庆市教委科学技术研究项目(KJ1709206)
重庆理工大学研究生创新基金资助项目(YCX2016228)
本文URL http://www.arocmag.com/article/01-2019-03-030.html
英文标题 Bidirectional time-efficient A* algorithm for robot path planning
作者英文名 Gao Mindong, Zhang Yani, Zhu Lingyun
机构英文名 CollegeofComputerScience&Engineering,ChongqingUniversityofTechnology,Chongqing400054,China
英文摘要 As for the tme-efficient A* algorithm significantly reduces the algorithm time, lead to the problem of increase path planning length and path sawtooth.This paper proposed an improved bidirectional time-efficient A* algorithm, which ran the A* algorithm from the start and the end point to find the path and applied the multiple neighbor grid distance computation scheme.At the same time, according to different environment map, this paper compared and analyzed the A* algorithm, time-efficient A* algorithm and bidirectional time-efficient A* algorithm.Finally, it chose the index of algorithm time and path length as two indicators to evaluate the merits and demerits of the algorithm.Experimental results show that compared with traditional A* algorithm, the bidirectional time-efficient A* decreases the time of the algorithm by 76.8% at the maximum, and reduces the maximum time by 55.4% compared with time-efficient A* algorithm.It also solves the problem that the path distance of the time-efficient A* algorithm is augmented and the path is not smooth enough.
英文关键词 path planning; heuristic algorithm; time-efficient A* algorithm
参考文献 查看稿件参考文献
  [1] 徐飞. 基于改进人工势场法的机器人避障及路径规划研究[J] . 计算机科学, 2016, 43(12):293-296. (Xu Fei. Research on robot obstacle avoidance and path planning based on improved artificial potential field method[J] . Computer Science, 2016, 43(12):293-296. )
[2] 徐腾飞, 罗琦, 王海. 基于向量场的移动机器人动态路径规划[J] . 计算机科学, 2015, 42(5):237-244. (Xu Tengfei, Luo Qi, Wang Hai. Dynamic path planning for mobile robot based on vector field[J] . Computer Science, 2015, 42(5):237-244. )
[3] 郑健, 黄敏, 张腾, 等. 求解指路标志指引路径规划问题的改进人工蜂群算法[J] . 计算机应用研究, 2017, 34(8):2355-2359. (Zheng Jian, Huang Min, Zhang Teng, et al. Modified artificial bee colony algorithm for solving path planning problem of guide signs[J] . Application Research of Computers, 2017, 34(8):2355-2359. )
[4] Sariff N, Buniyamin N. An overview of autonomous mobile robot path planning algorithms[C] //Proc of the 4th Student Conference on Research and Development. Piscataway, NJ:IEEE Press, 2006:183-188.
[5] Wang Haifeng, Zhou Jiawei, Zheng Guifeng, et al. HAS:hierarchical A* algorithm for big map navigation in special areas[C] //Proc of the 5th International Conference on Digital Home. Piscataway, NJ:IEEE Press, 2014:222-225.
[6] Lyu Min, Gao Tong, Zhang Nian. Research of AGV scheduling and path planning of automatic transport system[J] . International Journal of Control and Automation, 2016, 9(4):1-10.
[7] 李冲, 张安, 毕文豪. 单边矩形扩展A*算法[J] . 机器人, 2016, 39(1):46-56. (Li Chong, Zhang An, Bi Wenhao. Single-boundary rectangle expansion A* algorithm[J] . Robot, 2016, 39(1):46-56. )
[8] 刘大瑞, 钱程, 林涛. 基于多目标A*算法的游戏NPC路径规划[J] . 计算机应用研究, 2014, 31(8):2279-2282. (Liu Darui, Qian Cheng, Lin Tao. Pathfinding using new multi-objective A* for video game NPC[J] . Application Research of Computers, 2014, 31(8):2279-2282. )
[9] Guruji A K, Agarwal H, Parsediya D K. Time-efficient A* algorithm for robot path planning[J] . Procedia Technology, 2016, 23(3):144-149.
[10] 辛煜, 梁华为, 杜明博, 等. 一种可搜索无限个邻域的改进A*算法[J] . 机器人, 2014, 36(5):627-633. (Xin Yu, Liang Huawei, Du Mingbo, et al. An improved A* algorithm for searching infinite neighbourhoods[J] . Robot, 2014, 36(5):627-633. )
[11] Fernandes E, Costa P, Lima J, et al. Towards an orientation enhanced A* algorithm for robotic navigation[C] //Proc of IEEE International Conference on Industrial Technology. Piscataway, NJ:IEEE Press, 2015:3320-3325.
[12] Ueland E S, Skjetne R, Dahl A R. Marine autonomous exploration using a lidar and SLAM[C] //Proc of the 36th International Conference on Ocean, Offshore and Arctic Engineering-Volume 6:Ocean Space Utilization. New York:American Society of Mechanical Engineers, 2017.
收稿日期 2017/10/25
修回日期 2017/12/9
页码 792-795,800
中图分类号 TP18
文献标志码 A