ODrM* optimal multirobot path planning in low dimensional search spaces

Cornelia Ferner, Glenn Wagner and Howie Choset
Conference Paper, IEEE International Conference on Robotics and Automation (ICRA), pp. 3854 - 3859, May, 2013

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.


We believe the core of handling the complexity of coordinated multiagent search lies in identifying which subsets of robots can be safely decoupled, and hence planned for in a lower dimensional space. Our work, as well as those of others take that perspective. In our prior work, we introduced an approach called subdimensional expansion for constructing low-dimensional but sufficient search spaces for multirobot path planning, and an implementation for graph search called M*. Subdimensional expansion dynamically increases the dimensionality of the search space in regions featuring significant robot-robot interactions. In this paper, we integrate M* with Meta-Agent Constraint-Based Search (MA-CBS), a planning framework that seeks to couple repeatedly colliding robots allowing for other robots to be planned in low-dimensional search space. M* is also integrated with operator decomposition (OD), an A*-variant performing lazy search of the outneighbors of a given vertex. We show that the combined algorithm demonstrates state of the art performance.


author = {Cornelia Ferner and Glenn Wagner and Howie Choset},
title = {ODrM* optimal multirobot path planning in low dimensional search spaces},
booktitle = {IEEE International Conference on Robotics and Automation (ICRA)},
year = {2013},
month = {May},
pages = {3854 - 3859},
publisher = {IEEE},
keywords = {multirobot path planning, optimal path planning},
} 2017-09-13T10:39:21-04:00