More Like this

1. A Universal In-Place Reconfiguration Algorithm for Sliding Cube-Shaped Robots in a Quadratic Number of Moves

   https://doi.org/10.4230/LIPIcs.SoCG.2024.1  

   Abel, Zachary; A_Akitaya, Hugo; Kominers, Scott Duke; Korman, Matias; Stock, Frederick (January 2024, Schloss Dagstuhl – Leibniz-Zentrum für Informatik)

   Mulzer, Wolfgang; Phillips, Jeff M (Ed.)

   In the modular robot reconfiguration problem, we are given n cube-shaped modules (or robots) as well as two configurations, i.e., placements of the n modules so that their union is face-connected. The goal is to find a sequence of moves that reconfigures the modules from one configuration to the other using "sliding moves," in which a module slides over the face or edge of a neighboring module, maintaining connectivity of the configuration at all times. For many years it has been known that certain module configurations in this model require at least Ω(n²) moves to reconfigure between them. In this paper, we introduce the first universal reconfiguration algorithm - i.e., we show that any n-module configuration can reconfigure itself into any specified n-module configuration using just sliding moves. Our algorithm achieves reconfiguration in O(n²) moves, making it asymptotically tight. We also present a variation that reconfigures in-place, it ensures that throughout the reconfiguration process, all modules, except for one, will be contained in the union of the bounding boxes of the start and end configuration. 

   more » « less
2. A universal in-place reconfiguration algorithm for sliding cube-shaped robots in a quadratic number of moves

   https://doi.org/10.20382/jocg.v16i2a11  

   Abel, Zachary; Akitaya, Hugo A; Kominers, Scott Duke; Korman, Matias; Stock, Frederick (December 2025, Journal of Computational Geometry)

   {"Abstract":["In the modular robot reconfiguration problem, we are given $$n$$ cube-shaped modules (or robots) as well as two configurations, i.e., placements of the $$n$$ modules so that their union is face-connected. The goal is to find a sequence of moves that reconfigures the modules from one configuration to the other using "sliding moves", in which a module slides over the face or edge of a neighboring module, maintaining connectivity of the configuration at all times.\n\n\nFor many years it has been known that certain module configurations in this model require at least $$\\Omega(n^2)$ moves to reconfigure between them, and works for any dimension $$d\\ge 3$$. In this paper, we introduce the first universal reconfiguration algorithm—i.e., we show that any $$n$$-module configuration can reconfigure itself into any specified $$n$$-module configuration using just sliding moves. Our algorithm achieves reconfiguration in $O(n^2)$ moves, making it asymptotically tight. We also present a variation that reconfigures in-place, it ensures that throughout the reconfiguration process, all modules, except for one, will be contained in the union of the bounding boxes of the start and end configuration."]} 

   more » « less
3. On Computing Makespan-Optimal Solutions for Generalized Sliding-Tile Puzzles

   https://doi.org/10.1609/aaai.v38i9.28895  

   Gozon, Marcus; Yu, Jingjin (March 2024, Proceedings of the AAAI Conference on Artificial Intelligence)

   In the 15-puzzle game, 15 labeled square tiles are reconfigured on a 4 × 4 board through an escort, wherein each (time) step, a single tile neighboring it may slide into it, leaving the space previously occupied by the tile as the new escort. We study a generalized sliding-tile puzzle (GSTP) in which (1) there are 1+ escorts and (2) multiple tiles can move synchronously in a single time step. Compared with popular discrete multi-agent/robot motion models, GSTP provides a more accurate model for a broad array of high-utility applications, including warehouse automation and autonomous garage parking, but is less studied due to the more involved tile interactions. In this work, we analyze optimal GSTP solution structures, establishing that computing makespan optimal solutions for GSTP is NP-complete and developing polynomial time algorithms yielding makespans approximating the minimum with expected/high probability constant factors, assuming randomized start and goal configurations. 

   more » « less
4. Relocation with uniform external control in limited directions

   Balanza-Martinez, Jose; Caballero, David; Cantu, Angel; Gomez, Timothy; Luchsinger, Austin; Schweller, Robert; Wylie, Tim (September 2019, The 22nd Japan Conference on Discrete and Computational Geometry, Graphs, and Games, JCDCGGG)

   We study a model where particles exist within a board and move single units based on uniform external forces. We investigate the complexity of deciding whether a single particle can be relocated to another position in the board, and whether a board configuration can be transformed into another configuration. We prove that the problems are NP-complete with 1× 1 particles even when only allowed to move in 2 or 3 directions. 

   more » « less
5. Breaking the All Subsets Barrier for Min k-Cut

   https://doi.org/10.4230/LIPIcs.ICALP.2023.90  

   Lokshtanov, Daniel; Saurabh, Saket; Surianarayanan, Vaishali (January 2023, Schloss Dagstuhl – Leibniz-Zentrum für Informatik)

   Etessami, Kousha; Feige, Uriel; Puppis, Gabriele (Ed.)

   In the Min k-Cut problem, the input is a graph G and an integer k. The task is to find a partition of the vertex set of G into k parts, while minimizing the number of edges that go between different parts of the partition. The problem is NP-complete, and admits a simple 3ⁿ⋅n^𝒪(1) time dynamic programming algorithm, which can be improved to a 2ⁿ⋅n^𝒪(1) time algorithm using the fast subset convolution framework by Björklund et al. [STOC'07]. In this paper we give an algorithm for Min k-Cut with running time 𝒪((2-ε)ⁿ), for ε > 10^{-50}. This is the first algorithm for Min k-Cut with running time 𝒪(cⁿ) for c < 2. 

   more » « less