cs.DSMar 11, 2026

Sublinear-Time Reconfiguration of Programmable Matter with Joint Movements

Authors: Manish Kumar, Othon Michail, Andreas Padalkin, Christian Scheideler

Organizations: Paderborn University, Germany

Read PDF
Ask AI
Cite

Copy citation

DOINot available for this paper

Abstract

We study centralized reconfiguration problems for geometric amoebot structures. A set of nn amoebots occupy nodes on the triangular grid and can reconfigure via expansion and contraction operations. We focus on the joint movement extension, where amoebots may expand and contract in parallel, enabling coordinated motion of larger substructures. Prior work introduced this extension and analyzed reconfiguration under additional assumptions such as metamodules. In contrast, we investigate the intrinsic dynamics of reconfiguration without such assumptions by restricting attention to centralized algorithms, leaving distributed solutions for future work. We study the reconfiguration problem between two classes of amoebot structures AA and BB: For every structure S∈AS\in A, the goal is to compute a schedule that reconfigures SS into some structure S′∈BS'\in B. Our focus is on sublinear-time algorithms. We affirmatively answer the open problem by Padalkin et al. (Auton. Robots, 2025) whether a within-the-model sublinear-time universal reconfiguration algorithm is possible, by proving that any structure can be reconfigured into a canonical line-segment structure in O(nlog⁡n)O(\sqrt{n}\log n) rounds. Additionally, we give a constant-time algorithm for reconfiguring any spiral structure into a line segment. These results are enabled by new constant-time primitives that facilitate efficient parallel movement. Our findings demonstrate that the joint movement model supports sublinear reconfiguration without auxiliary assumptions. A central open question is whether universal reconfiguration within this model can be achieved in polylogarithmic or even constant time.

Figures & tables

Figure 1: Amoebot model and axes. The black nodes and edges indicate the nodes and edges occupied by amoebots. The red edges indicate bonds between the amoebots. The gray edges indicate the triangular grid GΔG_{\Delta} . We omit the grid in all other figures.
Figure 2: Movements. The yellow amoebot in (a) and (c) indicates amoebot cc . The blue amoebot in (b) and (c) indicates amoebot xx .
Figure 3: Results. Classes with a thicker frame indicate canonical classes. Red arrows point to superclasses and with that indicate trivial solutions. Note that we do not depict all superclasses. Black arrows indicate results by Padalkin et al. [ 14 ] . Note that their superconstant algorithms simulate algorithms from [ 5 , 12 ] . They define rhombical and hexagonal metamodules. Rhombical ( Hexagonal ) contains all amoebot structure that consist of rhombical (hexagonal) metamodules. RhombicalLine ( HexagonalLine ) contains all amoebot structure forming a line of rhombical (hexagonal) metamodules. Ring contains canonical amoebot structures forming a ring (see [ 5 ] for details). mm denotes the number of metamodules. Blue edges indicate our results. Note that our algorithm that reconfigures bounded structures into histograms simulates an algorithm from [ 4 ] .
Figure 4: Tunneling primitive. In each round, adjacent amoebots of the same color perform a handover. The gray node is unoccupied. In all figures, a simple arrow between two subfigures indicates the execution of the first step of a round (i.e., the removal of bonds) after establishing the adjacency closure, and a double arrow the execution of the second step of a round (i.e., the movements) unless stated otherwise. Note that only the fully completed rounds (i.e., both steps were executed) count to the total number of rounds.
Figure 5: Shearing primitive. The blue amoebots indicate the connection points. The yellow area indicates the triangle within the primitive is performed from the perspective of the bottom connection points.
Figure 6: Parallelogram primitive. The blue amoebots indicate the connection points.
Figure 7: First phase of the triangle primitive. The blue amoebots indicate the connection points.
Figure 8: Second phase of the triangle primitive on a triangle of side length ℓ=17\ell=17 . Note that k=4k=4 holds. The blue amoebots indicate the connection points.
Figure 9: Third phase of the triangle primitive. The blue amoebots indicate the connection points. The first two and last two double arrows indicate 22 rounds.
Figure 10: Fourth phase of the triangle primitive. The blue amoebots indicate the connection points.
Figure 11: Trapezoid primitive. The orange node/amoebot indicates the starting point. The blue amoebots indicate the connection points. Each double arrow indicates a phase consisting of 22 rounds.
Figure 12: Preprocessing phase of the Monotone2LineSegment algorithm.
Figure 13: Rules used in the Monotone2LineSegment algorithm.
Figure 14: State graph. The termination state is not shown. Any other state has an edge to the termination state.
Figure 15: Rule 4. We omit the first phase, i.e., the application of Rule 3d (see Figure 13 ), and only show the second and third phase.
Figure 16: Histograms in a star-convex structures. The yellow amoebot indicates the center amoebot. The blue amoebots indicate the connection points used by the Histogram2LineSegment algorithm. The yellow triangles indicate the area for each instance from which no amoebot is moved out, respectively. The double arrow indicates multiple rounds.
Figure 17: First phase of the Arbitrary2Bounded algorithm. The amoebot structure has n=49n=49 . Hence, each pair of rows that we want to merge has at least one row with less than n=7\sqrt{n}=7 amoebots. The blue amoebots indicate the pairs of amoebots that are unable to expand.
Figure 18: Single iteration of the second phase of the Arbitrary2Bounded algorithm. The blue amoebots indicate a pair of amoebots that were unable to expand in the first phase. The gray nodes are initially adjacent to the participating amoebots.
Figure 19: Third phase of the Arbitrary2Bounded algorithm. All amoebots contract again.
Figure 20: Combing algorithm by Aloupis et al. [ 4 ] . The blue amoebots indicate the sweep line.
Figure 21: Unrolling algorithm. The blue amoebots indicate the corners in the initial amoebot structure. The double arrow indicates a phase consisting of 22 rounds.
Figure 22: Base line construction. The blue amoebots indicate the left and right corners. The green path indicates the base line. The yellow areas indicate the parallelograms. The orange areas indicate the areas where parallelograms intersect. Each double arrow indicates multiple rounds.
Figure 23: Alignment of the zz -segments. The blue amoebots indicate the amoebots on the base line connected to a zz -segment of an arm. The green path indicates the base line. The yellow areas indicate the shearing primitive. The second double arrow indicates 22 rounds.
Figure 24: Alignment of the xx -segments. The blue amoebots indicate all left and right corners on the base line and all corners in the arms. The green path indicates the base line. The yellow areas indicate the shearing primitive. The second double arrow indicates 22 rounds.

Explore similar work

CardsList
Aug 18, 2026

Reconfiguration-Complete Motion Primitives with Constructive Planning for Deformable Planar Modular Robots

The continuously deformable geometry of modular robots makes it difficult to define a fixed representation for reconfiguration planning and analysis. This letter introduces a square-cell abstraction that maps deformable rhombus modules to fixed-size grid cells while retaining physically interpretable local motions through two primitives, pivoting and shearing. Under this abstraction, we prove that every non-straight edge-connected configuration with N≥7N \geq 7 can be transformed to a fixed canonical staircase using only admissible primitive motions. Since these motions are reversible, any two configurations in this class are mutually reconfigurable. The proof is constructive and directly yields a staircase-canonicalization planner that transports removable boundary modules while preserving connectivity. As a practical enhancement, we further introduce a boundary-to-delivery lookahead selector that ranks admissible high level choices without affecting the completeness guarantee. Experiments demonstrate the constructive reconfiguration process and show that the selector substantially reduces planning time, while reference comparisons indicate lower planning times than the prior framework over the shared module counts.

Jie Gu, Tingting Wang, Hongrun Gao +4

Institute of AI and Robotics, Academy for Engineering & Technology, Fudan University, Shanghai 200433, China · Department of Mechanical Engineering, The Hong Kong Polytechnic University, Hung Hom, Hong Kong SAR, China

Modular RoboticsRobot Motion PlanningConstrained Motion Planning
AskPDF
Aug 11, 2026

Deployment Is Not Destiny: Robot Recomposition in the Field with Unseen Software, Hardware, and Compute Payloads

The tight coupling of subsystems in most robots, though a natural consequence of their complexity, leads to monolithic designs that are time-consuming and difficult to adapt after initial deployment. To address this challenge, we present a framework and supporting abstractions for recomposition during runtime that enable robots to quickly integrate previously unseen modular software, hardware, and compute payloads. Our approach allows non-expert users to quickly add new capabilities in the field through a true plug-and-play process. Crucially, new resources are not only immediately available to a host robot but are also shared with distributed peers, enabling compute-constrained systems to access powerful new remote capabilities. Our framework reduces reconfiguration time to a matter of minutes with no developer intervention, in stark contrast to the hours of expert effort often required for traditional manual integration. We demonstrate our method in two disaster response scenarios, including radioactive source localization at an operational nuclear reactor facility and a thermal-guided search for people in dark, difficult-to-reach spaces. These demonstrations show how in-field recomposition provides timely, flexible, and accessible adaptation to dynamic requirements, representing a critical step toward creating robots that can quickly evolve alongside the tasks, technologies, and environments they support.

Steven Swanbeck, Jonathan Salfity, Jeffery Gunawan +3

Texas Robotics and the Walker Department of Mechanical Engineering, The University of Texas at Austin, Austin, TX 78712, USA

Modular RoboticsRoboticsSearch-and-Rescue Robotics
AskPDF
Sep 29, 2026

Recompositional Robotics: Cross-Domain, Open-set, and Lifelong Modularity Beyond Morphology

Research in modular robotics has produced capable approaches allowing a robot's morphology to change online, with recent efforts also developing approaches to decide which morphology to assume and automatically propagate that decision into the robot's motion planning and control. These approaches are powerful and increase adaptability in the field. However, an alternative objective is not to build robots whose structures can change, but robots whose fundamental capabilities can change, where capability is a joint function across several domains, including kino-dynamics, perception, compute, and high-level coordinating behaviors. A robot designed to be reconfigured across these domains has a greater capacity to alter its capability than one that can be reconfigured in a single domain. We refer to this cross-domain reconfigurability as integration span, and recognize a complementary measure of the resistance to reconfiguration, which we refer to as integration inertia. Current modular robots have reduced integration inertia in the structural domain while it remains high in the other domains that contribute to integration span. We assert that the systems that can provide the most utility through reconfiguration in practice are those maximizing span and minimizing inertia and call this general problem recompositional robotics: adaptation over a heterogeneous set of modules including hardware, software, compute, and behavior that abstracts each component by the interfaces it requires and provides such that they can be reasoned over holistically. We define the problem, ground it in two deployed systems and active research efforts, and pose open questions about the future of recompositional robotics.

Steven Swanbeck, Jonathan Salfity, Corrie Van Sice +2

Texas Robotics and the Walker Department of Mechanical Engineering, The University of Texas at Austin, Austin, TX 78712, USA

Modular RoboticsRobotics
AskPDF