一种改进RRT的多机器人编队路径规划算法

doi:10.3969/j.issn.0372-2112.2020.11.007

电子学报 ›› 2020, Vol. 48 ›› Issue (11): 2138-2145.DOI: 10.3969/j.issn.0372-2112.2020.11.007

一种改进RRT的多机器人编队路径规划算法

王乐乐^1,2, 眭泽智^1,2, 蒲志强², 刘振², 易建强²

1. 中国科学院大学人工智能学院, 北京 100049;
2. 中国科学院自动化研究所, 北京 100190

收稿日期:2019-11-29 修回日期:2020-05-17 出版日期:2020-11-25
- 通讯作者:
- 易建强
- 作者简介:
- 王乐乐 男,1994年5月出生,安徽亳州人.中国科学院自动化研究所博士研究生,研究方向为路径规划、机器人协同控制、群体智能等.E-mail:wanglele2017@ia.ac.cn;眭泽智 男,1992年2月出生,河北石家庄人.中国科学院自动化研究所博士研究生,研究方向为多智能体协同规划、深度强化学习、编队控制等.E-mail:suizezhi2015@ia.ac.cn;蒲志强 男,1987年5月出生.中国科学院自动化研究所副研究员、硕士生导师,主要从事非线性控制、群体智能、无人自主系统应用等方面的研究工作;刘振男,1987年11月出生.中国科学院自动化研究所副研究员、硕士生导师,主要从事非线性控制、鲁棒自适应控制等方面的研究工作.
- 基金资助:
- 科技部科技创新2030"新一代人工智能"重大项目2018年度项目 (No.2018AAA0102400）; 中国科学院轻型动力创新研究院创新引导基金重点基金 (No.CXYJJ19-ZD-02）

An Improved RRT Algorithm for Multi-Robot Formation Path Planning

WANG Le-le^1,2, SUI Ze-zhi^1,2, PU Zhi-qiang², LIU Zhen², YI Jian-qiang²

1. School of Artificial Intelligence, University of Chinese Academy of Sciences, Beijing 100049, China;
2. Institute of Automation, Chinese Academy of Sciences, Beijing 100190, China

Received:2019-11-29 Revised:2020-05-17 Online:2020-11-25 Published:2020-11-25
- Corresponding author:
- YI Jian-qiang
- Supported by:
- Ministry of Science and Technology Science and Technology Innovation 2030—"New Generation Artificial Intelligence" Major Project (No.2018AAA0102400) Generation Artificial Intelligence" Major Project (No.2018AAA0102400) Major Project (No.2018AAA0102400) (No.2018AAA0102400); Key fund of Innovation Guide Fund of Innovation Academy for Light-duty Gas Turbine, CAS (No.CXYJJ19-ZD-02)

摘要/Abstract

摘要： 多机器人路径规划是机器人领域的一个热点问题，相比于单机器人路径规划，其算法难度和复杂度都有所增加，在规划时需要兼顾多机避障、相互协作等难点问题.本文提出一种改进快速扩展随机树的多机器人编队路径规划算法，用于解决多机器人在复杂环境下的编队路径规划问题.针对多机器人在编队规划中的位置约束问题，定义机器人之间的领航-跟随结构，并对机器人队形建模.针对规划过程中编队朝向变化问题，建立搜索树扩展方向与队形方向之间的联系，通过调整队形方向改变规划时的编队朝向.针对具有质点模型和非完整约束动力学模型两种不同模型的多机器人系统，分别进行了仿真实验.仿真结果表明该算法在处理多机器人编队路径规划问题时可以取得良好的效果.

关键词: 快速随机搜索树, 编队, 路径规划, 避障

Abstract: Multi-robot path planning is one of the most attractive issues in the field of multiple robots. Compared with the algorithm for the single-robot path planning, the problem of multi-robot path planning, which takes obstacle avoidance and cooperation into account simultaneously, is more difficult and complex. Hence, a novel improved rapidly-exploring random tree algorithm for multi-robot formation path planning in this paper is proposed to address these obstacle avoidance and cooperation problems. The constraint condition of positional relationship is defined by modeling the multi-robot formation shape. Besides, the heading of formation is adjusted with the direction the exploring tree expands. Additionally, simulations are conducted for two different models of robots: the particle model and the non-holonomic constraint dynamic model. Simulation results are provided to demonstrate the effectiveness of the proposed algorithm.

Key words: rapidly-exploring random tree, formation, path planning, obstacle avoidance

中图分类号:

TP242

王乐乐, 眭泽智, 蒲志强, 等. 一种改进RRT的多机器人编队路径规划算法[J]. 电子学报, 2020, 48(11): 2138-2145.

WANG Le-le, SUI Ze-zhi, PU Zhi-qiang, et al. An Improved RRT Algorithm for Multi-Robot Formation Path Planning[J]. Acta Electronica Sinica, 2020, 48(11): 2138-2145.

参考文献

[1] YAN Z P,BAI R,CHI D N,et al.Formation coordination control of multi-UUV for object searching[J].Computer Measurement & Control,2013,(6):41-45.
[2] JAVIER A M,BAKER S,RUS D.Multi-robot formation control and object transport in dynamic environments via constrained optimization[J].The International Journal of Robotics Research,2017,36(9):1000-1021.
[3] XIDIAS E,PALIOTTA C,ASPRAGATHOS N.Path planning for formation control of autonomous vehicles[A].Proceedings of International Conference on Robotics in Alpe-Adria Danube Region[C].Belgrade:Springer,2016.302-309.
[4] HAN J L,CHEN Y Q.Multiple UAV formations for cooperative source seeking and contour mapping of a radiative signal field[J].Journal of Intelligent & Robotic Systems,2014,74(1-2):323-332.
[5] ZHANG X B,WANG J R,FANG Y C,et al.Multilevel humanlike motion planning for mobile robots in complex indoor environments[J].IEEE Transactions on Automation Science and Engineering,2018,16(3):1244-1258.
[6] 李宝磊,吕丹桔,张钦虎,等.基于多元优化算法的路径规划[J].电子学报,2016,44(9):2242-2247. LI Bao-lei,LÜ Dan-jü,ZHANG Qin-hu,et al.A path planner based on multivariant optimization algorithm[J].Acta Electronica Sinica,2016,44(9):2242-2247.(in Chinese)
[7] 路世杰.机器人协同任务规划方法研究[D].辽宁大连:大连理工大学,2018. LU S J.Research on Collaborative Task Planning Method of Robots[D].Dalian,Liaoning:Dalian University of Technology,2018.(in Chinese)
[8] YAO P,WANG H L,SU Z K.Cooperative path planning with applications to target tracking and obstacle avoidance for multi-UAVs[J].Aerospace Science and Technology,2016,54:10-22.
[9] 郑延斌,李新源,段德全.一种保持Agent团队队形的路径规划方法[J].计算机技术与发展,2009,19(7):159-162. ZHENG Y B,LI X Y,DUAN D Q.A path planning algorithm with agent team formation maintained[J].Computer Technology and Development.2009,19(7):159-162.(in Chinese)
[10] 班林林.多移动机器人群体协同编队与路径规划[D].北京:北京交通大学,2018. BAN L L.Collaborative Formation and Path Planning of Multiple Mobile Robots[D].Beijing:Beijing Jiao Tong University,2018.(in Chinese)
[11] DAI Y Y,LEE S G.The leader-follower formation control of nonholonomic mobile robots[J].International Journal of Control,Automation and Systems,2012,10(2):350-361.
[12] 王保防,张瑞雷,郭健,等.纵向打滑状态下的轮式移动机器人编队控制[J].电子学报,2017,45(1):206-212. WANG Bao-fang,ZHANG Rui-lei,GUO Jian,et al.Formation control for car-like mobile robots under slip conditions[J].Acta Electronica Sinica,2017,45(1):206-212.(in Chinese)
[13] DESARAJU V R.Decentralized path planning for multiple agents in complex environments using rapidly-exploring random trees[A].Proceedings of IEEE International Conference on Robotics and Automation[C].America:Massachusetts Institute of Technology,2011.89-94.
[14] BIRCHER A,ALEXIS K,SCHWESINGER U,et al.An incremental sampling-based approach to inspection planning:the rapidly exploring random tree of trees[J].Robotica,2017,35(6):1327-1340.
[15] WANG W,DENG H,WU X S.Path planning of loaded pin-jointed bar mechanisms using Rapidly-exploring Random Tree method[J].Computers & Structures,2018,209:65-73.
[16] 宋金泽,戴斌,单恩忠,等.一种改进的RRT路径规划算法[J].电子学报,2010,38(2A):225-228. SONG Jin-ze,DAI Bin,SHAN En-zhong,et al.An improved RRT path planning algorithm[J].Acta Electronica Sinica,2010,38(2A):225-228.(in Chinese)
[17] WEI K,REN B Y.A method on dynamic path planning for robotic manipulator autonomous obstacle avoidance based on an improved RRT algorithm[J].Sensors,2018,18(2):571.
[18] 王道威,朱明富,刘慧.动态步长的RRT路径规划算法[J].计算机技术与发展,2016,26(3):105-107. WANG D W,ZHU M F,LIU H.Rapidly exploring random tree algorithm based on dynamic step[J].Computer Technology and Development,2016,26(3):105-107.(in Chinese)
[19] 尹高扬,周绍磊,吴青坡.基于改进RRT算法的无人机航迹规划[J].电子学报,2017,45(7):1764-1769. YIN Gao-yang,ZHOU Shao-lei,WU Qing-po.An improved RRT algorithm for UAV path planning[J].Acta Electronica Sinica,2017,45(7):1764-1769.(in Chinese)
[20] CHEN M,DING M G,ZHENG T.Formation trajectory tracking control of multi-robot system based on leader-follower[J].Control Engineering of China,2019,26(1):37-42.
[21] TIAN B L,LU H C,ZUO Z Y,et al.Fixed-time leader-follower output feedback consensus for second-order multiagent systems[J].IEEE Transactions on Cybernetics,2018,49(4):1545-1550.
[22] 徐娜,陈雄,孔庆生,等.非完整约束下的机器人运动规划算法[J].机器人,2011,33(6):666-672. XU N,CHEN X,KONG Q S,et al.Motion planning for robot with nonholonomic constraints[J].Robot,2011,33(6):666-672.(in Chinese)

一种改进RRT的多机器人编队路径规划算法

An Improved RRT Algorithm for Multi-Robot Formation Path Planning

PDF

可视化

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 15

编辑推荐

Metrics

[1]	宣志玮, 毛剑琳, 张凯翔. CBS框架下面向复杂地图的低拓展度A*算法[J]. 电子学报, 2022, 50(8): 1943-1950.
[2]	段世红, 何昊, 徐诚, 殷楠, 王然. 未知环境下基于深度序列蒙特卡罗树搜索的信源导航方法[J]. 电子学报, 2022, 50(7): 1744-1752.
[3]	蒋林, 方东君, 周和文, 黄惠保. 基于射线模型的改进全局路径规划算法[J]. 电子学报, 2022, 50(3): 548-556.
[4]	马慧, 汤庸, 何怀文. 主存高效的公交网络路径规划索引[J]. 电子学报, 2021, 49(11): 2273-2278.
[5]	王秋萍, 王彦军, 戴芳. 多策略集成的樽海鞘群算法的机器人路径规划[J]. 电子学报, 2020, 48(11): 2101-2113.
[6]	葛利跃, 张聪炫, 陈震, 黎明, 陈昊. 相互结构引导滤波TV-L1变分光流估计[J]. 电子学报, 2019, 47(3): 707-713.
[7]	许凯波, 鲁海燕, 黄洋, 胡士娟. 基于双层蚁群算法和动态环境的机器人路径规划方法[J]. 电子学报, 2019, 47(10): 2166-2176.
[8]	韩博文, 姚佩阳, 钟赟, 丁云松, 刘子震. 基于QABC-IFMADM算法的有人/无人机编队作战威胁评估[J]. 电子学报, 2018, 46(7): 1584-1592.
[9]	段晓稳, 高晓光, 李波. 综合作战区同构舰载预警机巡逻策略分段滚动规划方法研究[J]. 电子学报, 2017, 45(6): 1301-1310.
[10]	蒋鹏, 冯洋, 吴锋. 果蝇启发的水下传感网部署算法[J]. 电子学报, 2017, 45(6): 1403-1407.
[11]	王保防, 张瑞雷, 郭健, 陈庆伟. 纵向打滑状态下的轮式移动机器人编队控制[J]. 电子学报, 2017, 45(1): 206-212.
[12]	李宝磊, 吕丹桔, 张钦虎, 施心陵, 陈建华, 张榆锋. 基于多元优化算法的路径规划[J]. 电子学报, 2016, 44(9): 2242-2247.
[13]	杜鹏桢, 唐振民, 陆建峰, 孙研. 不确定环境下基于改进萤火虫算法的地面自主车辆全局路径规划方法[J]. 电子学报, 2014, 42(3): 616-624.
[14]	李健, 欧阳继红, 廖梦兰. 三个简单区域间的拓扑关系的推理及应用模型[J]. 电子学报, 2014, 42(1): 125-129.
[15]	徐晓晴, 朱庆保. 动态环境下基于多人工鱼群算法和避碰规则库的机器人路径规划[J]. 电子学报, 2012, 40(8): 1694-1700.