An Algorithm with Improved Complexity for Pebble Motion/Multi-Agent Path Finding on Trees
Abstract
The pebble motion on trees (PMT) problem consists in finding a feasible sequence of moves that repositions a set of pebbles to assigned target vertices. This problem has been widely studied because, in many cases, the more general Multi-Agent path finding (MAPF) problem on graphs can be reduced to PMT. We propose a simple and easy to implement procedure, which finds solutions of length O(|P|nc + n2), where n is the number of nodes, P is the set of pebbles, and c the maximum length of corridors in the tree. This complexity result is more detailed than the current best known result O(n3), which is equal to our result in the worst case, but does not capture the dependency on c and |P|.
Cite
Text
Ardizzoni et al. "An Algorithm with Improved Complexity for Pebble Motion/Multi-Agent Path Finding on Trees." Journal of Artificial Intelligence Research, 2024. doi:10.1613/JAIR.1.15249Markdown
[Ardizzoni et al. "An Algorithm with Improved Complexity for Pebble Motion/Multi-Agent Path Finding on Trees." Journal of Artificial Intelligence Research, 2024.](https://mlanthology.org/jair/2024/ardizzoni2024jair-algorithm/) doi:10.1613/JAIR.1.15249BibTeX
@article{ardizzoni2024jair-algorithm,
title = {{An Algorithm with Improved Complexity for Pebble Motion/Multi-Agent Path Finding on Trees}},
author = {Ardizzoni, Stefano and Saccani, Irene and Consolini, Luca and Locatelli, Marco and Nebel, Bernhard},
journal = {Journal of Artificial Intelligence Research},
year = {2024},
pages = {483-514},
doi = {10.1613/JAIR.1.15249},
volume = {79},
url = {https://mlanthology.org/jair/2024/ardizzoni2024jair-algorithm/}
}