ODrM*: Optimal Multirobot Path Planning in Low Dimensional Search Spaces. Ferner, C., Wagner, G., & Choset, H. In Proceedings of the International Conference on Robotics and Automation (ICRA), pages 3854–3859, 2013.
abstract   bibtex   
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.
@INPROCEEDINGS{GWagn13a,
 AUTHOR= "C. Ferner and G. Wagner and H. Choset",
 TITLE= "{ODrM}*: Optimal Multirobot Path Planning in Low Dimensional Search Spaces",
 BOOKTITLE= "Proceedings of the International Conference on Robotics and Automation (ICRA)",
 PAGES= "3854--3859",
 YEAR= "2013",
 PDF= "http://biorobotics.ri.cmu.edu/papers/paperUploads/ICRA2013_Ferner_ODrM_Optimal_Multirobot_Path_Planning_in_Low_Dimensional_Search_Spaces.pdf",
 FLAGS= ":2013:,:glennwagner:,:howiechoset:",
 ABSTRACT= 
"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.",
}

Downloads: 0