FF-RRT*: a sampling-based planner for multi-robot global formation path planning

Abstract

This paper presents a collision-free global path planning approach for multi-robot 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 multi-robot 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 non-holonomic wheeled mobile robots and is effective in planning the collective motion of the robots. It was shown that robots could collectively reach goals by squeezing through narrow gaps and splitting and merging around large obstacles.