Saved in:
| Main Authors: | , |
|---|---|
| Format: | Preprint |
| Published: |
2024
|
| Subjects: | |
| Online Access: | https://arxiv.org/abs/2410.14947 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866909354521788416 |
|---|---|
| author | Gozon, Marcus Yu, Jingjin |
| author_facet | Gozon, Marcus Yu, Jingjin |
| contents | The Generalized Sliding-Tile Puzzle (GSTP), allowing many square tiles on a board to move in parallel while enforcing natural geometric collision constraints on the movement of neighboring tiles, provide a high-fidelity mathematical model for many high-utility existing and future multi-robot applications, e.g., at mobile robot-based warehouses or autonomous garages. Motivated by practical relevance, this work examines a further generalization of GSTP called the Colored Generalized Sliding-Tile Puzzle (CGSP), where tiles can now assume varying degrees of distinguishability, a common occurrence in the aforementioned applications. Our study establishes the computational complexity of CGSP and its key sub-problems under a broad spectrum of possible conditions and characterizes solution makespan lower and upper bounds that differ by at most a logarithmic factor. These results are further extended to higher-dimensional versions of the puzzle game. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2410_14947 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Optimally Solving Colored Generalized Sliding-Tile Puzzles: Complexity and Bounds Gozon, Marcus Yu, Jingjin Robotics Artificial Intelligence Multiagent Systems The Generalized Sliding-Tile Puzzle (GSTP), allowing many square tiles on a board to move in parallel while enforcing natural geometric collision constraints on the movement of neighboring tiles, provide a high-fidelity mathematical model for many high-utility existing and future multi-robot applications, e.g., at mobile robot-based warehouses or autonomous garages. Motivated by practical relevance, this work examines a further generalization of GSTP called the Colored Generalized Sliding-Tile Puzzle (CGSP), where tiles can now assume varying degrees of distinguishability, a common occurrence in the aforementioned applications. Our study establishes the computational complexity of CGSP and its key sub-problems under a broad spectrum of possible conditions and characterizes solution makespan lower and upper bounds that differ by at most a logarithmic factor. These results are further extended to higher-dimensional versions of the puzzle game. |
| title | Optimally Solving Colored Generalized Sliding-Tile Puzzles: Complexity and Bounds |
| topic | Robotics Artificial Intelligence Multiagent Systems |
| url | https://arxiv.org/abs/2410.14947 |