Learn all about Multi-Agent Path Finding (MAPF)
C. Ferner, G. Wagner and H. Choset. ODrM*: Optimal Multirobot Path Planning in Low Dimensional Search Spaces. In Proceedings of the International Conference on Robotics and Automation (ICRA), pages 3854-3859, 2013.
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.