Reconfiguration of Squares Using a Constant Number of Moves Each
Fuente:
arXiv
Saved in:
| Main Authors: | , , , |
|---|---|
| Format: | Preprint |
| Published: |
2026
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866911489016725504 |
|---|---|
| author | van der Horst, Thijs Löffler, Maarten Ophelders, Tim Peters, Tom |
| author_facet | van der Horst, Thijs Löffler, Maarten Ophelders, Tim Peters, Tom |
| contents | Multi-robot motion planning is a hard problem. We investigate restricted variants of the problem where square robots are allowed to slide over an arbitrary curve to a new position only a constant number of times each. We show that the problem remains NP-hard in most cases, except when the squares have unit size and when the problem is unlabeled, i.e., the location of each square in the target configuration is left unspecified. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2603_05203 |
| institution | arXiv |
| publishDate | 2026 |
| record_format | arxiv |
| spellingShingle | Reconfiguration of Squares Using a Constant Number of Moves Each van der Horst, Thijs Löffler, Maarten Ophelders, Tim Peters, Tom Computational Geometry Multi-robot motion planning is a hard problem. We investigate restricted variants of the problem where square robots are allowed to slide over an arbitrary curve to a new position only a constant number of times each. We show that the problem remains NP-hard in most cases, except when the squares have unit size and when the problem is unlabeled, i.e., the location of each square in the target configuration is left unspecified. |
| title | Reconfiguration of Squares Using a Constant Number of Moves Each |
| topic | Computational Geometry |
| url | https://arxiv.org/abs/2603.05203 |