ODrM* optimal multirobot path planning in low dimensional search spaces

Cornelia Ferner, Glenn Wagner, Howie ChosetICRA 2013 · OpenReview

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.
BibTeX
@inproceedings{ferner2013odrm,
  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},
  year = {2013},
  url = {https://openreview.net/forum?id=DQqyYEkN3Il},
}

Loading related content...

Figure