@inproceedings{cd3b5f57827347c19c6f8b1dd6e491a8,
title = "ODrM* optimal multirobot path planning in low dimensional search spaces",
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. {\textcopyright} 2013 IEEE.",
keywords = "Combined algorithms, Constraint-based, Dimensional spaces, Low dimensional, Multi-robot path planning, Operator decomposition, Planning framework, State-of-the-art performance, Industrial robots, Motion planning, Multi agent systems, Robotics, Robot programming",
author = "C. Ferner and G. Wagner and H. Choset",
note = "Conference code: 100673 Cited By :34 Export Date: 14 December 2023 CODEN: PIIAE Correspondence Address: ITS, , 5412 Puch/Salzburg, Austria References: Felner, A., Goldenberg, M., Sharon, G., Stern, R., Beja, T., Sturtevant, N., Schaeffer, J., Holte, R.C., Partial-expansion A with selective node generation (2012) Proceedings of the 26th AAAI Conference on Artificial Intelligence (AAAI); Kavraki, L.E., Svestka, P., Latombe, J.-C., Overmars, M.H., Probabilistic roadmaps for path planning in high-dimensional configurations spaces (1996) IEEE Transactions on Robotics and Automation, 12, pp. 566-580. , June; Kornhauser, D.M., Miller, G., Spirakis, P., Coordinating pebble motion on graphs, the diameter of permutation groups, and applications (1984) Proceedings of the 25th Symposium on Foundations of Computer Science (FOCS), pp. 241-250; Lavalle, S.M., Kuffner, J.J., Randomized kinodynamic planning (1999) Proceedings IEE International Conference on Robotics and Automation; Luna, R., Bekris, K.E., Push and swap: Fast cooperative path-finding with completeness guarantees (2011) International Joint Conference on Artificial Intelligence (IJCAI); Peasgood, M., McPhee, J., Clark, C.M., (2006) Complete and Scalable Multi-robot Planning in Tunnel Environments, , In First IFAC Workshop on Multivehicle Systems; Sajid, Q., Luna, R., Bekris, K.E., Multi-agent pathfinding with simultaneous execution of single-agent primitives (2012) SoCS; Sharon, G., Stern, R., Felner, A., Sturtevant, N., Conflict-based search for optimal multi-agent path finding (2012) AAAI, , (to appear); Sharon, G., Stern, R., Felner, A., Sturtevant, N., Meta-agent conflictbased search for optimal multi-agent path finding (2012) SoCS; Sharon, G., Stern, R., Goldenberg, M., Felner, A., Beer-Sheva, I., The increasing cost tree search for optimal multi-agent pathfinding (2011) Twenty-Second International Joint Conference on Artificial Intelligence; Standley, T., Finding optimal solutions to cooperative pathfinding problems (2010) Proceedings of the 24th AAAI Conference on Artificial Intelligence (AAAI); Wagner, G., Howie, C.M., A complete multirobot path planning algorithm with performance bounds (2011) Proceedings of IEEE International Conference on Intelligent Robots and Systems 2011, , September; Wagner, G., Kang, M., Choset, H., Probabilistic path planning for multiple robots with subdimensional expansion (2012) Proceedings of IEEE/RSJ International Conference on Robotics and Automation, , May; Wang, K.H.C., Botea, A., Tractable multi-agent path planning on grid maps (2009) Proceedings of the International Joint Conference on Artificial Intelligence IJCAI-09, pp. 1870-1875; 2013 IEEE International Conference on Robotics and Automation, ICRA 2013, ICRA 2013 ; Conference date: 06-05-2013 Through 10-05-2013",
year = "2013",
doi = "10.1109/ICRA.2013.6631119",
language = "English",
isbn = "978-1-4673-5641-1",
pages = "3854--3859",
booktitle = "2013 IEEE International Conference on Robotics and Automation",
publisher = "Institute of Electrical and Electronics Engineers Inc.",
address = "United States",
url = "https://www.icra2013.org/index.html",
}