Gespeichert in:
| Hauptverfasser: | , , , |
|---|---|
| Format: | Preprint |
| Veröffentlicht: |
2026
|
| Schlagworte: | |
| Online-Zugang: | https://arxiv.org/abs/2603.23503 |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| _version_ | 1866911542741565440 |
|---|---|
| author | Calvi, Annalisa Bodic, Pierre Le McGuire, Samuel Lam, Edward |
| author_facet | Calvi, Annalisa Bodic, Pierre Le McGuire, Samuel Lam, Edward |
| contents | Given a tree, a set of pebbles initially stationed at some nodes of the tree, and a set of target nodes, the Unlabeled Pebble Motion on Trees problem (UPMT) asks to find a plan to move the pebbles one-at-a-time from the starting nodes to the target nodes along the edges of the tree while minimizing the number of moves. This paper proposes the first optimal algorithm for UPMT that is asymptotically as fast as possible, as it runs in a time linear in the size of the input (the tree) and the size of the output (the optimal plan). We extend this to solve unlabeled Multi-Agent Path Finding (MAPF) in trees, providing novel bounds on optimal makespan, sum of costs, and pebble motion plan length. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2603_23503 |
| institution | arXiv |
| publishDate | 2026 |
| record_format | arxiv |
| spellingShingle | Optimal Unlabeled Pebble Motion on Trees and its Application to Multi-Agent Path Finding Calvi, Annalisa Bodic, Pierre Le McGuire, Samuel Lam, Edward Data Structures and Algorithms Given a tree, a set of pebbles initially stationed at some nodes of the tree, and a set of target nodes, the Unlabeled Pebble Motion on Trees problem (UPMT) asks to find a plan to move the pebbles one-at-a-time from the starting nodes to the target nodes along the edges of the tree while minimizing the number of moves. This paper proposes the first optimal algorithm for UPMT that is asymptotically as fast as possible, as it runs in a time linear in the size of the input (the tree) and the size of the output (the optimal plan). We extend this to solve unlabeled Multi-Agent Path Finding (MAPF) in trees, providing novel bounds on optimal makespan, sum of costs, and pebble motion plan length. |
| title | Optimal Unlabeled Pebble Motion on Trees and its Application to Multi-Agent Path Finding |
| topic | Data Structures and Algorithms |
| url | https://arxiv.org/abs/2603.23503 |