Rapidly-exploring Random Trees multi-robot map exploration under optimization framework

Rapidly-exploring Randomized Trees (RRT) is a kind of probabilistically complete exploration algorithm based on the tree structure. It has been widely used in the robotic navigation since it guarantees the complete discovery and the exploration of environment maps through robots. In the present study, the RRT algorithm is extended to propose an optimization-based map exploration strategy for multiple robots to actively explore and build environment maps. The present study adopts a market-based task allocation strategy, which to maximize the profit, for the coordination between robots. In the extension of the RRT, the cost function consists the unknown region and the passed unknown region. The unknown region is explored for a given frontier point, while the passed unknown region is the area, where the robot moves towards the target frontier point. When the robot moves from the start position to the target frontier point, the trajectory length is defined as a constraint for the optimization. The main contributions of the present study can be summarized in optimizing the frontier points, defining a new task allocation strategy and applying different evaluation rules, including the running time and the trajectory length. These rules are applied to explore the multi-robot map in simulated and practical environments. Then the Robot Operating System (ROS) is utilized to evaluate the application of the proposed exploration strategy on Turtlebots in a 270 m(2) room. Obtained results from the simulation and the experiment demonstrate that the proposed method outperforms the Umari's approach from both the running time and the trajectory length aspects. (C) 2020 Elsevier B.V. All rights reserved.