涡流人工势场引导下的RRT*移动机器人路径规划

doi:10.3778/j.issn.1673-9418.2004037

摘要/Abstract

摘要：

为了解决快速扩展随机树（RRT）在障碍物密集、通道狭窄的环境中收敛速度缓慢、采样节点密集、路径曲折复杂等问题，围绕RRT的一种常见的变体算法RRT*，设计了一种由人工势场（APF）引导RRT*进行路径规划的方法。首先，使用涡流约束向外发散的斥力场，沿着切向梯度方向形成涡流场，并利用涡流人工势场（VAPF）在RRT*偏向区域中引导采样节点进行偏向采样，以减少执行时间，加快收敛速度；同时，利用节点拒绝技术去除高成本节点和无效节点，生成节点更为集中的轨迹树，降低内存需求；最后，通过修剪路径中的多余节点，并利用涡流势场的特性对路径进行平滑处理，达到路径优化的效果。考虑到RRT类算法具有概率随机性，对RRT算法、改进RRT*算法和VAPF-RRT*算法分别进行了32次对比实验。仿真结果表明，提出的VAPF-RRT*算法明显降低了迭代次数，以更少的采样节点和执行时间收敛到更短更平滑的路径，提高了内存利用率，加快了收敛速度。

关键词: 路径规划, 快速扩展随机树（RRT）, 人工势场法（APF）, 移动机器人, 涡流

Abstract:

The rapidly-exploring random tree (RRT) has the problems of slow convergence, dense sampling nodes, and complicated path twists under the condition of dense obstacles and narrow channels. In this paper, a common variant of the RRT algorithm, RRT*, is designed with atificial potential fields (APF) to guide RRT* for path planning. First, vortex is used to constrain the repulsive field that diverges outward to form a vortex field along the tangential gradient. And vortex-APF (VAPF) is used to guide the sampling node to perform directional sampling in the RRT* deflection area, so as to reduce the execution time and accelerate the convergence speed. Simultaneously, the node rejection is used to remove high cost nodes and invalid nodes and a more centralized tree can be generated to reduce memory requirements. Finally, the extra nodes are pruned and the path is smoothed by vortex potential field to achieve the path optimization. Considering that the RRT algorithm has probabilistic randomness, 32 experi-ments are carried out on the RRT, the improved RRT* and the VAPF-RRT* respectively. The simulation results show that the VAPF-RRT* method significantly reduces the number of iterations, converges to shorter and smoother paths with fewer sampling nodes and execution time, and thus leads to more efficient memory utilization and an accelerated convergence rate.

Key words: path planning, rapidly-exploring random tree (RRT), arti?cial potential ?elds (APF), mobile robot, vortex

曹凯, 陈阳泉, 高嵩, 高佳佳. 涡流人工势场引导下的RRT*移动机器人路径规划[J]. 计算机科学与探索, 2021, 15(4): 723-732.

CAO Kai, CHEN Yangquan, GAO Song, GAO Jiajia. Vortex Artificial-Potential-Field Guided RRT* for Path Planning of Mobile Robot[J]. Journal of Frontiers of Computer Science and Technology, 2021, 15(4): 723-732.

参考文献

[1] RAJA P, PUGAZHENTHI S. Optimal path planning of mobile robots: a review[J]. International Journal of Physical Sciences, 2012, 7(9): 1314-1320.
[2] MASEHIAN E. Review and taxonomies of assembly and disassembly path planning problems and approaches[J]. Com-puter-Aided Design, 2015, 67: 58-59.
[3] ALEJO D, COBANO J A, HEREDIA G, et al. Efficient trajectory planning for WSN data collection with multiple UAVs[M]//KOUB?A A, MARTíNEZ-DE DIOS J. Studies in Computational Intelligence. Berlin, Heidelberg: Springer, 2015.
[4] XIA K F, LI P F, CHEN X P. Pedestrian tracking for mobile robots based on improved particle filtering[J]. Journal of Fron-tiers of Computer Science and Technology, 2017, 11(11): 1849-1859.
夏克付, 李鹏飞, 陈小平. 基于改进粒子滤波的移动机器人行人跟踪[J]. 计算机科学与探索, 2017, 11(11): 1849-1859.
[5] GONZáLEZ D, PéREZ J, MILANéS V, et al. A review of motion planning techniques for automated vehicles[J]. IEEE Transactions on Intelligent Transportation Systems, 2016, 17(4): 1135-1145.
[6] CHEN Y, LUO G, MEI Y, et al. UAV path planning using artificial potential field method updated by optimal control theory[J]. International Journal of Systems Science, 2016, 47(6): 1407-1420.
[7] REN Y, ZHAO H B. Improved robot path planning based on artificial potential field method[J]. Computer Simulation, 2020, 37(2): 360-364.
任彦, 赵海波. 改进人工势场法的机器人避障及路径规划[J]. 计算机仿真, 2020, 37(2): 360-364.
[8] PAN H, GUO C, WANG Z D. Research for path planning based on improved astart algorithm[C]//Proceedings of the 4th International Conference on Information, Cybernetics and Computational Social Systems, Dalian, Jul 24-26, 2017. Piscataway: IEEE, 2017: 225-230.
[9] ZHANG K, LIU P P, KONG W R, et al. An improved heu-ristic algorithm for UCAV path planning[C]//Proceedings of the 11th International Conference on Bio-Inspired Com-puting Theories and Applications, Xi’an, Oct 28-30, 2016. Berlin, Heidelberg: Springer, 2016: 54-59.
[10] DUAN H B, HUANG L Z. Imperialist competitive algorithm optimized artificial neural networks for UCAV global path planning[J]. Neurocomputing, 2014, 125: 166-171.
[11] MAC T T, COPOT C, TRAN D T, et al. Heuristic approaches in robot path planning: a survey[J]. Robotics and Autonomous Systems, 2016, 86: 13-28.
[12] WANG X, SHI Y, DING D, et al. Double global optimum genetic algorithm particle swarm optimization-based welding robot path planning[J]. Engineering Optimization, 2016, 48(2): 299-316.
[13] LIU X Y, TAN L M, YANG C X, et al. Self-adjustable dynamic path planning of unknown environment based on ant colony-clustering algorithm[J]. Journal of Frontiers of Computer Science and Technology, 2019, 13(5): 846-857.
刘新宇, 谭力铭, 杨春曦, 等. 未知环境下的蚁群-聚类自适应动态路径规划[J]. 计算机科学与探索, 2019, 13(5): 846-857.
[14] ELBANHAWI M, SIMIC M. Sampling-based robot motion planning: a review[J]. IEEE Access, 2014, 2(1): 56-77.
[15] BRANICKY M S, CURTISS M M, LEVINE J, et al. Sampling-based planning, control and verification of hybrid systems[J]. IEE Proceedings-Control Theory and Applications, 2005, 38(1): 271-276.
[16] GE S S, CUI Y J. New potential functions for mobile robot path planning[J]. IEEE Transactions on Robotics and Auto-mation, 2000, 16(5): 615-620.
[17] KAVRAKI L E, ?VESTKA P, LATOMBE J C, et al. Pro-babilistic roadmaps for path planning in high-dimensional configuration spaces[J]. IEEE Transactions on Robotics and Automation, 1994, 12(4): 566-580.
[18] LAVALLE S M. Rapidly-exploring random trees: a new tool for path planning: TR 98-11[R]. Ames: Iowa State University, 1998.
[19] KUFFNER J J, LAVALLE S M. RRT-connect: an efficient approach to single-query path planning[C]//Proceedings of the 2000 IEEE International Conference on Robotics and Automation, San Francisco, Apr 24-28, 2000. Piscataway: IEEE, 2002: 995-1001.
[20] ADIYATOV O, VAROL H A. Rapidly-exploring random tree based memory efficient motion planning[C]//Proceedings of the 2013 International Conference on Mechatronics and Automation, Takamatsu, Aug 4-7, 2013. Piscataway: IEEE, 2013: 354-359.
[21] KARAMAN S, FRAZZOLI E. Sampling-based algorithms for optimal motion planning[J]. The International Journal of Robotics Research, 2011, 30(7): 846-894.
[22] CHOUDHURY S, GAMMELL J D, BARFOOT T D, et al. Regionally accelerated batch informed trees (RABIT*): a framework to integrate local information into optimal path planning[C]//Proceedings of the 2016 International Confer-ence on Robotics and Automation, Stockholm, May 16-21, 2016. Piscataway: IEEE, 2016: 4207-4214.
[23] GAMMELL J D, SRINIVASA S S, BARFOOT T D. Infor-med RRT*: optimal sampling-based path planning focused via direct sampling of an admissible ellipsoidal heuristic[C]//Proceedings of the 2014 International Conference on Intel-ligent Robots and Systems, Chicago, Sep 14-18, 2014. Pis-cataway: IEEE, 2014: 2997-3004.
[24] YANG Y, FU K C, JIANG T, et al. AGV path planned with heuristic RRT[J]. Computer Engineering and Applications, 2020, 56(12): 125-133.
杨瑶, 付克昌, 蒋涛, 等. 启发式RRT算法的AGV路径规划[J]. 计算机工程与应用, 2020, 56(12): 125-133.
[25] LIU Z Y, ZHANG J. Path planning using improved RRT algorithm for indoor mobile robot[J]. Computer Engineering and Applications, 2020, 56(9): 190-197.
刘紫燕, 张杰. 改进RRT算法的室内移动机器人路径规划[J]. 计算机工程与应用, 2020, 56(9): 190-197.
[26] KHATIB O. Real-time obstacle avoidance for manipulators and mobile robots[M]//COX I J, WILFONG G T. Autono-mous Robot Vehicles. Berlin, Heidelberg: Springer, 1986: 396-404.