We found a match
Your institution may have rights to this item. Sign in to continue.
- Title
An Algorithm with Improved Complexity for Pebble Motion/Multi-Agent Path Finding on Trees.
- Authors
Ardizzoni, Stefano; Saccani, Irene; Consolini, Luca; Locatelli, Marco; Nebel, Bernhard
- 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 + n²), 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(n³), which is equal to our result in the worst case, but does not capture the dependency on c and |P|.
- Subjects
PEBBLES; GEOMETRIC vertices; DIRECTED graphs; COMPUTER algorithms; PROBLEM solving
- Publication
Journal of Artificial Intelligence Research, 2024, Vol 79, p483
- ISSN
1076-9757
- Publication type
Article
- DOI
10.1613/jair.1.15249