宁宇铭, 李团结, 姚聪, 邵继升. 基于快速扩展随机树—贪婪边界搜索的多机器人协同空间探索方法[J]. 机器人, 2022, 44(6): 708-719. DOI: 10.13973/j.cnki.robot.210318
引用本文: 宁宇铭, 李团结, 姚聪, 邵继升. 基于快速扩展随机树—贪婪边界搜索的多机器人协同空间探索方法[J]. 机器人, 2022, 44(6): 708-719. DOI: 10.13973/j.cnki.robot.210318
NING Yuming, LI Tuanjie, YAO Cong, SHAO Jisheng. Multi-robot Cooperative Space Exploration Method Based on Rapidly-exploring Random Trees and Greedy Frontier-based Exploration[J]. ROBOT, 2022, 44(6): 708-719. DOI: 10.13973/j.cnki.robot.210318
Citation: NING Yuming, LI Tuanjie, YAO Cong, SHAO Jisheng. Multi-robot Cooperative Space Exploration Method Based on Rapidly-exploring Random Trees and Greedy Frontier-based Exploration[J]. ROBOT, 2022, 44(6): 708-719. DOI: 10.13973/j.cnki.robot.210318

基于快速扩展随机树—贪婪边界搜索的多机器人协同空间探索方法

Multi-robot Cooperative Space Exploration Method Based on Rapidly-exploring Random Trees and Greedy Frontier-based Exploration

  • 摘要: 传统多机协同探索算法存在鲁棒性较差、探索效率较低、环境障碍感知不完全等问题,为此本文提出一种基于快速扩展随机树-贪婪边界搜索(RRT-GFE)的多机器人协同空间探索方法。首先,采用Thiessen多边形对环境进行建模与划分,利用RRT边界探索算法依次对所有Thiessen多边形进行探索;其次,在RRT边界探索算法的基础上,引入GFE算法进行细化搜索,并提取连续边界域的形心作为探索目标点;再次,利用划分所形成的多边形区域以及所提取出的边界点,采用基于改进市场机制的多机器人任务分配方法对探索目标点进行动态分配,并在探索过程中采用地图融合算法进行局部地图的实时融合;最后,基于机器人操作系统(ROS)搭建仿真/样机测试平台并进行了一系列实验验证。结果表明,无论在仿真还是样机实验中,基于RRT-GFE的多机器人协同探索算法均能取得更加省时高效的探索效果。

     

    Abstract: Aiming at the problems of poor robustness, low exploration efficiency and incomplete perception of environmental obstacles in traditional multi-robot cooperative exploration algorithm, a novel multi-robot cooperative space exploration method is proposed based on rapidly-exploring random tree and greedy frontier-based exploration (RRT-GFE). Firstly, Thiessen polygons are used to model and partition the environments, and RRT frontier exploration algorithm is used to explore all Thiessen polygons in turn. Secondly, GFE algorithm is introduced to refine the search results based on the RRT frontier exploration algorithm, and the centroid of continuous frontier region is extracted as the exploration target point. Then, a multi-robot task assignment method based on the improved market mechanism is introduced to dynamically assign the exploration target points based on the divided polygon regions and the extracted frontier points, and the map-merging algorithm is used in the exploration process to merge several local maps in real time. Finally, a simulation/prototype experiment platform is built based on the Robot Operating System (ROS) and a series of experiments are carried out. The results show that the multi-robot cooperative exploration algorithm based on RRT-GFE can reduce the time cost and improve the exploration efficiency in both the simulations and the prototype experiments.

     

/

返回文章
返回