M*: A complete multirobot path planning algorithm with performance bounds

Glenn Wagner and Howie Choset
Conference Paper, IEEE/RSJ International Conference on Intelligent Robots and Systems, September, 2011

Copyright notice: This material is presented to ensure timely dissemination of scholarly and technical work. Copyright and all rights therein are retained by authors or by other copyright holders. All persons copying this information are expected to adhere to the terms and constraints invoked by each author's copyright. These works may not be reposted without the explicit permission of the copyright holder.


Multirobot path planning is difficult because the full configuration space of the system grows exponentially with the number of robots. Planning in the joint configuration space of a set of robots is only necessary if they are strongly coupled, which is often not true if the robots are well separated in the workspace. Therefore, we initially plan for each robot separately, and only couple sets of robots after they have been found to interact, thus minimizing the dimensionality of the search space. We present a general strategy called subdimensional expansion, which dynamically generates low dimensional search spaces embedded in the full configuration space. We also present an implementation of subdimensional expansion for robot configuration spaces that can be represented as a graph, called M*, and show that M* is complete and finds minimal cost paths.


author = {Glenn Wagner and Howie Choset},
title = {M*: A complete multirobot path planning algorithm with performance bounds},
booktitle = {IEEE/RSJ International Conference on Intelligent Robots and Systems},
year = {2011},
month = {September},
keywords = {path planning, multi agent path finding},
} 2017-09-13T10:40:07-04:00