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

• 学术论文 • 上一篇    下一篇

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

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

  1. 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-le1,2, SUI Ze-zhi1,2, PU Zhi-qiang2, LIU Zhen2, YI Jian-qiang2   

  1. 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: 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

中图分类号: