平滑ARA*算法在智能车辆路径规划的应用

摘要: A*算法是一种经典的启发式搜索算法，广泛应用于智能车辆的路径规划问题。但A*算法效率低，不具有实时性。针对A*算法的缺点，改进得到一种高效、实时的路径搜索算法ARA*，ARA*算法首先在一个松弛的约束条件下快速搜索到一条次优路径；然后在规划时间内逐渐加强约束条件，利用已搜索过的节点信息连续改进次优解，直到找到最优解或规划时间结束。其次，针对ARA*算法得到的路径存在折线多、转折次数多等问题，对ARA*算法得到的路径进行基于关键点的平滑处理。给出了平滑ARA*算法流程，分析对比了各自的特点，通过栅格地图路径规划的MATLAB仿真结果验证了理论分析，同时仿真结果也说明平滑ARA*算法的高效性、实时性。
- 路径规划 /
- A*算法 /
- 平滑ARA*算法
Abstract: A* algorithm is a classical heuristic search algorithm, which is widely used in the path planning of intelligent vehicles. However, the efficiency of A* algorithm is low, and also it has no real time performance. Anytime repairing A*(ARA*), an efficient and real-time path searching algorithm, can solve the shortcoming of the A* algorithm. First, ARA* algorithm searches the suboptimal path in a relaxed constraint condition. Then, within the planning time, the constraint condition is gradually enhanced, and the solution is improved by using the information that has been searched until the optimal solution is found or planning time is run out. Next, because the path planned by ARA* algorithm is flaw with much broken lines, frequently turning points, we give a smooth method based on key points to make the path smoothly. The flow of smoothing ARA*algorithm is given, meanwhile, analyzing and comparing their respective characteristics. The theoretical analysis is verified by Matlab simulation results of path planning in the grid map. The simulation results also show that the smoothing ARA* algorithm is efficient and real-time.
- path planning /
- A* algorithm /
- smoothing ARA* algorithm

HTML全文

参考文献(16)

[1]	陈慧岩,熊光明,龚建伟,等.无人驾驶汽车概论[M].北京:北京理工大学出版社,2014 Chen H Y, Xiong G M, Gong J W, et al. Introduction to self-driving car[M]. Beijing:Beijing University of Technology Press, 2014(in Chinese)
[2]	曲道奎,杜振军,徐殿国,等.移动机器人路径规划方法研究[J].机器人,2008,30(2):97-101,106 Qu D K, Du Z J, Xu D G, et al. Research on path planning for a mobile robot[J]. Robot, 2008,30(2):97-101,106(in Chinese)
[3]	Hart P E, Nilsson N J, Raphael B. A formal basis for the heuristic determination of minimum cost paths[J]. IEEE Transactions on Systems Science and Cybernetics, 1968,4(2):100-107
[4]	Dechter R, Pearl J. Generalized best-first search strategies and the optimality of A*[J]. Journal of the ACM, 1985,32(3):505-536
[5]	Likhachev M, Ferguson D, Gordon G, et al. Anytime search in dynamic graphs[J]. Artificial Intelligence, 2008,172(14):1613-1643
[6]	Koenig S, Likhachev M, Furcy D. Lifelong planning A*[J]. Artificial Intelligence, 2004,155(1-2):93-146
[7]	吴天羿,许继恒,刘建永,等.基于改进A算法的越野路径规划研究[J].计算机应用研究,2013,30(6):1724-1726 Wu T Y, Xu J H, Liu J Y, et al. Research of cross-country path planning based on improved A algorithm[J]. Application Research of Computers, 2013,30(6):1724-1726(in Chinese)
[8]	谭宝成,王培.A路径规划算法的改进及实现[J].西安工业大学学报,2012,32(4):325-329 Tan B C, Wang P. Improvement and implementation of A path planning algorithm[J]. Journal of Xi'an Technological University, 2012,32(4):325-329(in Chinese)
[9]	王殿君.基于改进A算法的室内移动机器人路径规划[J].清华大学学报(自然科学版),2012,52(8):1085-1089 Wang D J. Indoor mobile-robot path planning based on an improved A algorithm[J]. Journal of Tsinghua University (Science & Technology), 2012,52(8):1085-1089(in Chinese)
[10]	Ebendt R, Drechsler R. Weighted A* search-unifying view and application[J]. Artificial Intelligence, 2009,173(14):1310-1342
[11]	Likhachev M, Gordon G, Thrun S. ARA*:formal analysis[R]. Technical Report of the Carnegie Mellon University, Pittsburgh:Carnegie Mellon University, 2003
[12]	Likhachev M, Gordon G J, Thrun S. ARA:anytime A with provable bounds on sub-optimality[M]//Thrun S, Saul L, Schölkopf B. Advances in Neural Information Processing Systems, Vol. 16. Cambridge, MA:MIT Press, 2004
[13]	王红卫,马勇,谢勇,等.基于平滑A算法的移动机器人路径规划[J].同济大学学报(自然科学版),2010,38(11):1647-1650,1655 Wang H W, Ma Y, Xie Y, et al. Mobile robot optimal path planning based on smoothing A algorithm[J]. Journal of Tongji University (Natural Science), 2010,38(11):1647-1650,1655(in Chinese)
[14]	单伟,孟正大.基于改进A算法的平滑路径设计[J].东南大学学报(自然科学版),2010,40(S1):155-161 Shan W, Meng Z D. Smooth path design for mobile service robots based on improved A algorithm[J]. Journal of Southeast University (Natural Science Edition), 2010,40(S1):155-161(in Chinese)
[15]	张豫南,闫永宝.基于平滑A算法的6×6轮式车最优路径规划[J].制造业自动化,2012,34(13):1-4,14 Zhang Y N, Yan Y B. 6×6 Wheeled vehicle optimal path planning based on smoothing A algorithm[J]. Manufacturing Automation, 2012,34(13):1-4,14(in Chinese)
[16]	Xie Y, Cheng W S. AGV path planning based on smoothing A* algorithm[J]. International Journal of Software Engineering & Applications, 2015,6(5):1-8