FF-RRT*: A Sampling-Based Planner for Multirobot Global Formation Path Planning

Abstract

This article presents a collision-free global path planning approach for multirobot systems called flexible formation—rapidly exploring randomized trees* (FF-RRT*). The algorithm is based on RRT* and provides a flexible and efficient representation of the formation geometry independent of the number of robots. It is designed to generate optimal paths for multirobot systems in a five-dimensional configuration space comprising the formation centroid, orientation, and scaling. An affine transformation is used to convert the path in the configuration space to the workspace of the robots. The proposed method employs a new distance function that eliminates the need for tuning weights and a sampling scheme for scaling factors to avoid inter-robot collisions. FF-RRT* is experimentally demonstrated using nonholonomic wheeled mobile robots and is effective in planning the collective motion of the robots. Robots could collectively reach goals by squeezing through narrow gaps and splitting and merging around large obstacles.