M*: A complete multirobot path planning algorithm with performance bounds - Robotics Institute Carnegie Mellon University

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

Conference Paper, Proceedings of (IROS) IEEE/RSJ International Conference on Intelligent Robots and Systems, pp. 3260 - 3267, September, 2011

Abstract

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.

Notes
http://ieeexplore.ieee.org/xpls/abs_all.jsp?arnumber=6095022&tag=1

BibTeX

@conference{Wagner-2011-7385,
author = {Glenn Wagner and Howie Choset},
title = {M*: A complete multirobot path planning algorithm with performance bounds},
booktitle = {Proceedings of (IROS) IEEE/RSJ International Conference on Intelligent Robots and Systems},
year = {2011},
month = {September},
pages = {3260 - 3267},
keywords = {path planning, multi agent path finding},
}