An algorithm with improved complexity for pebble motion/multi-agent path finding on trees
Fuente:
arXiv
Gespeichert in:
| Hauptverfasser: | , , , , |
|---|---|
| Format: | Preprint |
| Veröffentlicht: |
2023
|
| Schlagworte: | |
| Online-Zugang: | |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| _version_ | 1866914745408290816 |
|---|---|
| author | Ardizzoni, Stefano Saccani, Irene Consolini, Luca Locatelli, Marco Nebel, Bernhard |
| author_facet | Ardizzoni, Stefano Saccani, Irene Consolini, Luca Locatelli, Marco Nebel, Bernhard |
| contents | 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(knc + n^2), where n is the number of nodes, $k$ is the number 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^3), which is equal to our result in the worst case, but does not capture the dependency on c and k. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2307_12770 |
| institution | arXiv |
| publishDate | 2023 |
| record_format | arxiv |
| spellingShingle | An algorithm with improved complexity for pebble motion/multi-agent path finding on trees Ardizzoni, Stefano Saccani, Irene Consolini, Luca Locatelli, Marco Nebel, Bernhard Multiagent Systems 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(knc + n^2), where n is the number of nodes, $k$ is the number 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^3), which is equal to our result in the worst case, but does not capture the dependency on c and k. |
| title | An algorithm with improved complexity for pebble motion/multi-agent path finding on trees |
| topic | Multiagent Systems |
| url | https://arxiv.org/abs/2307.12770 |