融合A*的改进RRT机械臂路径规划

doi:10.3778/j.issn.1002-8331.2303-0157

摘要/Abstract

摘要： 针对RRT（rapidly-exploring random tree）路径规划算法在高维空间的机械臂避障路径规划时随机产生巨量节点，导致算法运行负担大、避障性能差、容易陷入局部极值的问题，提出一种结合A*判断函数的改进RRT算法。对RRT的采样方式进行更改，每次生成一个包含多个随机采样点的序列，并利用改进的A*判断函数进行排序；对每次生成节点进行距离判断，防止陷入局部搜索；利用重复贪心策略删除冗余节点，利用三次B样条平滑路径。在二维、三维地图及机械臂仿真与样机实验中进行算法性能分析，改进RRT算法能够大量减少到达目标位姿时产生的节点，缓解了局部极值，快速稳定地避开障碍物并到达目标位姿，证明了改进RRT算法的有效性和优越性。

关键词: 机械臂, 路径规划, A*判断函数, 快速扩展随机树（RTT）

Abstract: For the problem that the RRT (rapidly-exploring random tree) path planning algorithm generates a huge number of nodes when planning the obstacle avoidance path of robotic arm in high-dimensional space, resulting in a large burden of algorithm operation, poor obstacle avoidance performance, and easy to fall into local extremes, an improved RRT algorithm combining A* judgment function is proposed. The sampling method of RRT is changed to generate a sequence of multiple randomly sampled points each time, and the improved A* judgment function is used for sorting. Distance judgment is performed on each generated node to prevent it from falling into local search. Finally, a repetitive greedy strategy is used to remove redundant nodes, and cubic B-spline is used to make path smooth. The performance of the algorithm is analyzed in 2D and 3D maps and robot arm simulations and prototype experiments. The improved RRT algorithm can effectively reduce the number of nodes for the robotic arm to reach the target poses, alleviate the local extremes, and avoid obstacles to reach the target poses quickly and stably, which proves the effectiveness and superiority of the improved RRT algorithm.

Key words: robotic arm, path planning, A* judgment function, rapidly-exploring random tree (RTT)

龙厚云, 李光, 谭薪兴, 薛晨慷, 易静. 融合A*的改进RRT机械臂路径规划[J]. 计算机工程与应用, 2024, 60(4): 366-374.

LONG Houyun, LI Guang, TAN Xinxing, XUE Chenkang, YI Jing. Path Planning of Robotic Arm Based on Improved RRT Algorithm Combined with A*[J]. Computer Engineering and Applications, 2024, 60(4): 366-374.

参考文献

[1] SUN X, CAI C, SHEN X. A new cloud model based human-machine cooperative path planning method[J]. Journal of Intelligent & Robotic Systems, 2015, 79(1): 3-19.
[2] JIANG H, PI J, LI A, et al. Dynamic local path planning for intelligent vehicles based on sampling area point discrete and quadratic programming[J]. IEEE Access, 2022, 10: 70279-70294.
[3] NYAKUNDI G M. Use of the Hester Davis falls risk assessment scale in medical-surgical patients[D]. Walden University, 2022.
[4] 张立. 工业机械臂的智能运动规划与避障方法研究[D]. 广州: 华南理工大学, 2018.
ZHANG L. Research on intelligent motion planning and obstacle avoidance method of industrial manipulator[D]. Guangzhou: South China University of Technology, 2018.
[5] 陈超, 唐坚, 靳祖光, 等. 一种基于可视图法导盲机器人路径规划的研究[J]. 机械科学与技术, 2014, 33(4): 490-495.
CHEN C, TANG J, JIN Z G, et al. A study on path planning of a guided robot based on visual graph method[J]. Mechanical Science and Technology, 2014, 33(4): 490-495.
[6] 李珺,?段钰蓉,?郝丽艳,?等.?混合优化算法求解同时送取货车辆路径问题[J].?计算机科学与探索,?2022,?16(7):?1623-1632.
LI J, DUAN Y R, HAO L Y, et al. Hybrid optimization algorithm for vehicle routing problem with simultaneous delivery-pickup[J]. Journal of Frontiers of Computer Science and Technology, 2022, 16(7): 1623-1632.
[7] 张硕航,?郭改枝.?多旅行商模型及其应用研究综述[J].?计算机科学与探索,?2022,?16(7):?1516-1528.
ZHANG S H, GUO G Z. Review of multiple traveling salesman model and its application[J]. Journal of Frontiers of Computer Science and Technology,?2022, 16(7): 1516-1528.
[8] BARBEHENN M. A note on the complexity of Dijkstra??s algorithm for graphs with weighted vertices[J]. IEEE Transactions on Computers, 1998, 47(2): 263.
[9] 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.
[10] HSU D, KINDEL R, LATOMBE J C, et al. Randomized kinodynamic motion planning with moving obstacles[J]. The International Journal of Robotics Research, 2002, 21(3): 233-255.
[11] KAVRAKI L E, SVESTKA P, LATOMBE J C, et al. Probabilistic roadmaps for path planning in high-dimensional configuration spaces[J]. IEEE Transactions on Robotics and Automation, 1996, 12(4): 566-580.
[12] LAVALLE S M, KUFFNER JR J J. Randomized kino-dynamic planning[J]. The International Journal of Robotics Research, 2001, 20(5): 378-400.
[13] 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, 2000, 2: 995-1001.
[14] KARAMAN S, FRAZZOLI E. Sampling-based algorithms for optimal motion planning[J]. The International Journal of Robotics Research, 2011, 30(7): 846-894.
[15] GAMMELL J D, BARFOOT T D, SRINIVASA S S. Informed sampling for asymptotically optimal path planning[J]. IEEE Transactions on Robotics, 2018, 34(4): 966-984.
[16] PALMIERI L, ARRAS K O. A novel RRT extend function for efficient and smooth mobile robot motion planning[C]//Proceedings of the 2014 IEEE/RSJ International Conference on Intelligent Robots and Systems, 2014: 205-211.
[17] 贾浩铎, 房立金, 王怀震. 融合人工势场和Informed-RRT*算法的机械臂自适应路径规划[J/OL]. 计算机集成制造系统 [2023-02-18]. http://kns.cnki.net/kcms/detail/11.5946.TP.20230117.1454.008.html.
JIA H D, FANG L J, WANG H Z. Adaptive path planning for robotic arm incorporating artificial potential field and Informed-RRT* algorithm[J/OL]. Computer Integrated Manufacturing Systems [2023-02-18]. http://kns.cnki.net/kcms/detail/11.5946.TP.20230117.1454.008.html.
[18] 王雨, 刘延俊, 贾华. 基于强化RRT算法的机械臂路径规划[J]. 山东大学学报（工学版）, 2022, 52(6): 123-130.
WANG Y, LIU Y J, JIA H. Robotic arm path planning based on enhanced RRT algorithm[J]. Journal of Shandong University (Engineering Edition), 2022, 52(6): 123-130.
[19] 张立彬, 林后凯, 谭大鹏. 基于栅格空间的自适应GB_RRT机械臂路径规划[J]. 计算机集成制造系统, 2022, 28(6): 1638-1649.
ZHANG L B, LIN H K, TAN D P. Adaptive GB_RRT robot arm path planning based on raster space[J]. Computer Integrated Manufacturing Systems, 2022, 28(6): 1638-1649.
[20] 李耀仲, 王书亭, 蒋立泉. 基于稀疏节点快速扩展随机树的移动机械臂运动规划[J]. 中国机械工程, 2021, 32(12): 1462-1470.
LI Y Z, WANG S T, JIANG L Q. Mobile robotic arm motion planning based on fast expanding random tree with sparse nodes[J]. China Mechanical Engineering, 2021, 32(12): 1462-1470.
[21] 谭薪兴, 李光, 易静, 等. 改进RRT算法的机械臂路径规划[J/OL]. 计算机集成制造系统 [2022-11-29]. http://kns.cnki.net/kcms/detail/11.5946.TP.20220906.1011.002.html.
TAN X X, LI G, YI J, et al. Improved RRT algorithm for robotic arm path planning[J/OL]. Computer Integrated Manufacturing Systems [2022-11-29]. http://kns.cnki.net/kcms/detail/11.5946.TP.20220906.1011.002.html.
[22] LAVALLE S M, KUFFNER J J. Rapidly-exploring random trees: progress and prospects[M]//Algorithmic and computational robotics. Boca Raton: CRC Press, 2001: 303-307.
[23] 徐亚之. 冗余机械臂运动避障与路径规划[D]. 沈阳: 东北大学, 2015.
XU Y Z. Obstacle avoidance and path planning for a redundant manipulator[D]. Shenyang: Northeastern University, 2015.
[24] PAN J, CHITTA S, MANOCHA D. FCL: a general purpose library for collision and proximity queries[C]//Proceedings of the 2012 IEEE International Conference on Robotics and Automation, Saint Paul, 2012: 3859-3866.
[25] 魏坤. 机械臂混杂场景动态路径规划与多目标识别研究[D]. 哈尔滨: 哈尔滨工业大学, 2019.
WEI K. Research on dynamic path planning and multi-objective recognition for robotic arm mixed scenes[D]. Harbin: Harbin Institute of Technology, 2019.
[26] 龙樟, 李显涛, 帅涛, 等. 工业机器人轨迹规划研究现状综述[J]. 机械科学与技术, 2021, 40(6): 853-862.
LONG Z, LI X T, SHUAI T, et al. Review of research state of trajectory planning for industrial robots[J]. Mechanical Science and Technology for Aerospace Engineering, 2021, 40(6): 853-862.
[27] 王兆光, 高宏力, 宋兴国. 基于GB_RRT算法的机械臂路径规划[J]. 机械设计与制造, 2019(7): 1-4.
WANG Z G, GAO H L, SONG X G. Robotic arm path planning based on GB_RRT algorithm[J]. Machine Design and Manufacture, 2019(7): 1-4.
[28] 谭薪兴, 李光, 薛晨慷, 等. 改进适应度函数的CMA-ES算法在机器人逆运动学中的应用[J]. 智能计算机与应用, 2022, 12(2): 18-23.
TAN X X, LI G, XUE C K, et al. Application CMA-ES algorithm with improved fitness function to solve inverse kinematics of robot[J]. Intelligent Computer and Applications, 2022, 12(2): 18-23.