Pith. sign in

REVIEW 3 major objections 6 minor 39 references

Efficient Reconfiguration of Tile Arrangements by a Single Active Robot

T0 review · 3 major / 6 minor · reviewed 2026-08-07 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗

Pith's one-line read For every rational weight $\lambda\in[0,1]$, computing an optimal one-robot tile-reconfiguration schedule is NP-hard, while separated start and target bounding boxes admit a polynomial-time constant-factor approximation.

desk verdict Weighted NP-hardness and the disjoint-box approximation are real progress, but both load-bearing proofs—Claim 6 and Eq. (2)—are sketched, so this needs referee work, not desk rejection. read the letter →

arxiv 2502.09299 v2 pith:YPCNU42P submitted 2025-02-13 cs.CG cs.DScs.RO

Aaron T. Becker , Sándor P. Fekete , Jonas Friemel , Ramin Kosfeld , Peter Kramer , Harm Kube , Christian Rieck , Christian Scheffer
show 1 more author
Arne Schmidt
This is my paper
classification cs.CGcs.DScs.RO MSC 68Q1768W2568U05
keywords singlerobotreconfigurationpolyominoesprogrammablematterweightedmakespanNP-hardnessconstant-factorapproximationminimum-weightperfectmatchinghistogramconfigurations
verification ladder T0 review T1 audit T2 compute T3 formal

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

The paper studies a single robot that walks over a connected grid arrangement of identical tiles, picks up single tiles, and carries them to new positions while keeping the tile structure connected at every step. The goal is a schedule of minimal weighted makespan, in which a carrying move costs one unit and an empty move costs a tunable rational parameter $\lambda$ between 0 and 1. The paper's first claim is that computing an optimal schedule is NP-hard for every rational $\lambda$, extending an earlier hardness result for the unweighted case. Its second claim is that when the start and target configurations lie in disjoint bounding boxes, a polynomial-time algorithm produces a schedule within a constant factor of optimal; for 2-scaled configurations made of 2x2 tile blocks, the schedule also has minimum possible carry distance and is exactly optimal when $\lambda=0$. If these results stand, exact optimization is intractable in general, but a near-optimal guarantee is available for the separated case.

What carries the argument

The central machinery is the three-phase reduction through intermediate histograms. A histogram is a polyomino with a horizontal base strip of unit height and unit-width vertical columns attached along it; the algorithm first compresses the start configuration into a north-facing histogram, reconfigures that into a south-facing histogram inside the target bounding box, and then unpacks it into the target. Phase I uses a depth-first walk over the polyomino and translates free components one or two units in the target direction; Phase II moves tiles between opposite-facing histograms along shortest paths over a shared baseline; Phase III reverses Phase I. For 2-scaled configurations the individual moves are along shortest paths, so each phase has carry distance equal to the minimum-weight perfect matching distance, and the phases are glued by the additive identity $\sigma(C_s,C_t)=\sigma(C_s,H_s)+\sigma(H_s,H_t)+\sigma(H_t,C_t)$. This identity is what turns per-phase $O(n+\sigma)$ bounds into an overall $O(\sigma(C_s,C_t))=O(\mathrm{OPT})$ bound. General configurations replace free-component translation with a strip/corridor decomposition and two auxiliary tiles that keep the polyomino connected.

What would settle it

Take a 2-scaled pair of separated configurations, run the three-phase algorithm, and compute $\sigma(C_s,C_t)$ and $\sigma(C_s,H_s)+\sigma(H_s,H_t)+\sigma(H_t,C_t)$ for the constructed histograms; any positive difference between the sum and $\sigma(C_s,C_t)$ falsifies Equation (2) and with it the proof of the constant-factor bound.

Watch

Extended reading notes

Core claim

The paper establishes that Single Robot Reconfiguration is NP-hard for every rational weight $\lambda\in[0,1]$, via two reductions: a grid Hamiltonian-path reduction with edge gadgets whose cost balance is controlled by choosing a gadget scale $k>1/\lambda$ for $\lambda>0$, and a Planar Monotone 3SAT reduction for $\lambda=0$. Complementing this, the paper proves that when the bounding boxes of the start and target configurations are disjoint, every instance admits an efficiently computable schedule whose weighted makespan is at most a constant factor times the optimum, with the constant independent of $\lambda$ and of configuration size. The positive result is built on an intermediate histogram representation: the robot first compresses the start configuration into a north-facing histogram, translates and morphs it into a south-facing histogram inside the target bounding box, and then unpacks it into the target. For 2-scaled instances the individual phases move tiles along shortest paths, so the schedule's carry distance equals the minimum-weight perfect matching distance $\sigma(C_s,C_t)$ and is optimal when $\lambda=0$.

Load-bearing premise

The entire constant-factor approximation rests on the unproven identity that the shortest travel distance between the start and target configurations decomposes cleanly into the three stage distances through the intermediate histogram shapes; if that equality fails even for one separated configuration, the guaranteed closeness to optimal may collapse.

Editorial extensions

If this is right

  • For every rational $\lambda\in[0,1]$, computing an optimal reconfiguration schedule is NP-hard, so no polynomial exact algorithm exists unless P=NP.
  • For configurations with disjoint bounding boxes, a schedule with weighted makespan at most a constant times optimal can be computed in polynomial time, for both 2-scaled and general configurations.
  • For 2-scaled separated configurations, the computed schedule has optimal carry distance; when $\lambda=0$, this schedule is exactly optimal.
  • The same three-phase machinery lets a robot build a target polyomino from a depot of tiles rather than dismantling a start configuration.
  • In the disjoint-box case, $n\in O(\sigma(C_s,C_t))$, so the algorithm's total $O(n+\sigma)$ runtime is asymptotically linear in the unavoidable carry distance.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

  • A natural check the authors leave implicit: computing the three $\sigma$ terms on random separated 2-scaled instances would directly test the additive identity; a single instance with $\sigma(C_s,H_s)+\sigma(H_s,H_t)+\sigma(H_t,C_t)>\sigma(C_s,C_t)$ would break the proof of the constant-factor bound.
  • For intersecting or nested bounding boxes, the minimum-weight matching distance is not a usable lower bound because the empty-move cost can be arbitrarily larger, so extending the constant-factor result would require a different lower-bound measure; the histogram decomposition itself may still be the right construction.
  • The algorithm is centralized and sequential; a distributed adaptation would need local rules for the strip/corridor translations, and a parallel version would need to schedule multiple carriers so their auxiliary tiles and paths do not conflict.
Share X Bluesky LinkedIn Reddit HN

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Referee Report

3 major / 6 minor

Summary. The paper studies the problem of reconfiguring a connected polyomino from a start configuration Cs to a target configuration Ct using a single robot that walks on tiles and can carry at most one tile at a time. The objective is to minimize the weighted makespan λ·dE + dC for a rational λ∈[0,1], where dE is empty travel and dC is carry distance. The paper claims two main results: (1) the problem is NP-hard for every rational λ∈[0,1], proved by a reduction from Hamiltonian path in grid graphs for λ∈(0,1] and by a separate reduction from Planar Monotone 3SAT for λ=0; and (2) for configurations with disjoint bounding boxes, there is a polynomial-time constant-factor approximation, with optimal carry distance (and hence exact optimality for λ=0) in the 2-scaled case. The algorithmic part uses intermediate histograms and minimum-weight perfect matchings as a lower bound, with a three-phase schedule: transform Cs into a histogram Hs, reconfigure histograms Hs to Ht, and then transform Ht into Ct.

Significance. If the proof gaps were closed, the paper would make a solid contribution: it extends the known NP-hardness of unweighted reconfiguration to arbitrary weighting between empty and carrying moves, and it provides the first constant-factor approximation for the natural disjoint-bounding-box case, with an appealing optimal-carry-distance property for 2-scaled instances. The histogram decomposition is elegant, the use of MWPM as a lower bound is appropriate, and the paper contains several self-contained lemmas with explicit O(n+σ) bounds. The authors also give credit to their own prior ICRA 2024 construction for the λ∈(0,1] case, which is acceptable as a published hardness result. However, two load-bearing steps are currently asserted rather than proved: the exact-threshold lower bound in Claim 6 for λ=0, and the exact matching decomposition in Eq. (2) that underpins the approximation analysis. These gaps are central to the paper's main claims.

major comments (3)
  1. [Section 2, Claim 6 (proof of Lemma 4)] The lower-bound proof for the λ=0 reduction is not a proof. Claim 6 asserts without derivation that no variable gadget can be solved in fewer than 9(δ(xi)+1) moves, that tiles can be confined to their respective gadgets 'by spacing them appropriately', and that each unsatisfied clause incurs 'an extra cost of at least 4 units'. These are exact-threshold claims: the target makespan in Eq. (1) is exactly 29m+9n, so a single unaccounted shortcut of 1–3 units would break the reduction. The text does not analyze alternative traversals of the variable gadget, interleavings of gadget operations, or schedules that use one movement to serve multiple clauses. This is the most load-bearing unproved step in the NP-hardness contribution and needs a formal exchange argument or a complete case analysis.
  2. [Section 3.4, Eq. (2) in the proof of Theorem 7] The exact decomposition σ(Cs,Ct)=σ(Cs,Hs)+σ(Hs,Ht)+σ(Ht,Ct) is asserted without proof. The surrounding text argues that tiles are moved monotonically toward the target in Phases (I) and (III), but monotone movement within each phase only shows that each phase's matching is optimal for that subproblem; it does not show that the concatenated path Cs→Hs→Ht→Ct is an L1 geodesic between Cs and Ct. In particular, Ht is constructed inside Ct's bounding box and can lie at lower y-coordinates than the Ct tiles it is later matched to, so the route may overshoot. This equality is not a general property of L1 matchings; it must be proved directly, or the choice of Hs and Ht must be modified to enforce it. This gap affects Theorem 7, Theorem 15, and Corollary 13.
  3. [Section 3.4, Corollary 13] The claim that an optimal schedule can be computed efficiently for 2-scaled disjoint-box instances with λ=0 depends on two unproved assertions: Lemma 12's schedule having optimal carry distance, and the exact equality in Eq. (2). Since Eq. (2) is not established, Corollary 13 is not established. The authors should either prove that their intermediate histograms satisfy the equality by construction, or weaken the corollary to a constant-factor approximation.
minor comments (6)
  1. [Section 2, Lemma 4] The sentence 'We can show that a weighted makespan of 29m+9n can be achieved exactly if φ is satisfiable' appears as a standalone statement before the 'Proof of Lemma 4' header, and the proof then contains Claims 5 and 6. This layout is confusing; the statement and proof should be contiguous.
  2. [Section 2, reference [15]] The reference for Planar Monotone 3SAT is listed as a paper on optimal binary space partitions. The authors should verify that this is the correct source for the NP-completeness of Planar Monotone 3SAT, or cite the standard reference for that problem.
  3. [Section 3.4, Theorem 7 proof] The phrase 'proving asymptotic optimality for Cs⇒Ct' is inaccurate; the theorem proves a constant-factor approximation, not asymptotic optimality in the usual sense. The wording should be changed to avoid confusion, e.g., 'proving that the three-phase schedule is within a constant factor of OPT'.
  4. [Section 3.2, proof of Lemma 9] In the accounting for walk modifications, the sentence 'For any free component Fi, there are at most 2|Fi| edges between Fi and the rest of the configuration' should be more precise: it means boundary edges incident to Fi, and the subsequent factor of 8 in 'at most 8|Fi| movements' should be derived explicitly.
  5. [Figure 8 and Section 3.4] The figure and caption do not clearly indicate the vertical relationship between Ht and Ct's bounding box, which is exactly what the unproved equality in Eq. (2) concerns. A small diagram showing the y-coordinates of the bases and the direction of movement in each phase would help the reader verify the intended geodesic argument.
  6. [Section 5, open problems] In the discussion of the MWPM lower bound for intersecting bounding boxes, the text says 'at least k−1≫4 empty moves' with Figure 15, but for small k the symbol ≫ is misleading. Consider rephrasing to 'can be arbitrarily larger than the MWPM weight'.

Circularity Check

0 steps flagged · score 1.0 of 10

No circularity found; the reused ICRA 2024 gadget construction is an independent published result, and the unproved steps (Claim 6, Eq. 2) are correctness gaps rather than input-output equivalences.

full rationale

I found no step in which a claimed derivation or prediction is equivalent by construction to its inputs. The NP-hardness proof for λ∈(0,1] (Lemma 2) reuses the gadget construction of [24], which shares authors with the present paper; this is self-citation, but [24] is a peer-reviewed, externally checkable hardness result for the λ=1 case, and the present reduction adds a new two-path edge gadget with explicit cost arithmetic depending on k>1/λ. The only direct reliance on [24] ('see also [24]' for the claim about bridge lengths) is a checkable geometric statement about the gadgets, not an imported uniqueness theorem, so it is not load-bearing circularity. The λ=0 reduction (Lemma 4) follows the external sliding-squares construction of [3] and introduces its own variable and clause gadgets with explicit makespan targets; no parameters are fitted. The approximation algorithm (Theorems 7 and 15) is self-contained: it defines histograms, proves Lemmas 9, 10, 12 with explicit subroutines, and uses the standard L1 crossing inequality (Observation 8) and minimum-weight perfect matching lower bounds. I do flag three load-bearing correctness gaps, but none is circular: (i) Equation (2) is asserted without a complete proof, and the equality σ(Cs,Hs)+σ(Hs,Ht)+σ(Ht,Ct)=σ(Cs,Ct) may fail because Ht is constructed inside Ct's bounding box and can require northward movement relative to later matched Ct tiles; the constant-factor claim depends on this equality. (ii) Claim 6's lower bound for unsatisfiable φ is a sketch: 'we incur an extra cost of at least 4 units per unsatisfied clause' is asserted without ruling out interleaved schedules, so the exact threshold 29m+9n is not fully established. (iii) dC(S) is defined to include pickups and drop-offs while σ is a pure L1 matching sum, so the repeated statement dC(S)=σ(Cs,Ct) needs a consistent accounting convention; this could affect the λ=0 optimality corollary. These are proof-completeness and correctness concerns, not circularity, because no theorem is shown to reduce to its own assumptions by definition or by a self-citation chain.

Assumptions & free parameters 0 free parameters · 5 assumptions · 0 invented entities

No fitted constants appear. The central theoretical claims rest on standard metric lower bounds plus several unproved geometric assertions about the lambda=0 gadgets and the intermediate histograms.

assumptions (5)
  • standard math L1 distance is a metric and the minimum-weight perfect matching weight sigma(Cs,Ct) lower-bounds the optimal carry distance.
    Introduced in Section 3.1 and used as the OPT lower bound throughout Sections 3 and 4.
  • domain assumption 2-scaled polyominoes have no cut vertices, so free components can be translated without disconnecting.
    Stated at the start of Section 4 to justify replacing Lemma 10 with the general Lemma 14.
  • domain assumption Two tiles that are leaves of a spanning tree of the dual graph can be removed without breaking connectivity.
    Used in Theorem 15 to procure auxiliary tiles; no proof is supplied in the paper.
  • ad hoc to paper In the lambda=0 reduction, variable gadgets cannot be solved in fewer than 9(delta(xi)+1) moves, and each unsatisfied clause adds at least 4.
    Claim 6 asserts these bounds with 'It is easy to observe' and 'clearly'; the argument depends on unshown gadget figures.
  • ad hoc to paper The chosen intermediate histograms Hs and Ht satisfy Equation (2).
    Theorem 7's proof asserts this equality with no construction or proof of the intermediate histograms.

how reviews work

0 comments
Cite this review

Pith. "Pith review of Efficient Reconfiguration of Tile Arrangements by a Single Active Robot." pith.science (2026). https://pith.science/paper/YPCNU42P

@misc{pith2026250209299,
  author       = {Pith},
  title        = {Pith review of: Efficient Reconfiguration of Tile Arrangements by a Single Active Robot},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/YPCNU42P}},
  note         = {Machine review of arXiv:2502.09299}
}
read the original abstract

We consider the problem of reconfiguring a two-dimensional connected grid arrangement of passive building blocks from a start configuration to a goal configuration, using a single active robot that can move on the tiles, remove individual tiles from a given location and physically move them to a new position by walking on the remaining configuration. The objective is to determine a schedule that minimizes the overall makespan, while keeping the tile configuration connected. We provide both negative and positive results. (1) We generalize the problem by introducing weighted movement costs, which can vary depending on whether tiles are carried or not, and prove that this variant is NP-hard. (2) We give a polynomial-time constant-factor approximation algorithm for the case of disjoint start and target bounding boxes, which additionally yields optimal carry distance for 2-scaled instances.

Discussion (0). Sign in to comment.

Reference graph

Works this paper leans on

39 extracted references · 30 canonical work pages

  1. [24]

    Fekete, and Aaron T

    Javier Garcia, Michael Yannuzzi, Peter Kramer, Christian Rieck, Sándor P. Fekete, and Aaron T. Becker. Reconfiguration of a 2D structure using spatio-temporal planning and load transferring. In International Conference on Robotics and Automation (ICRA) , pages 8735--8741, 2024. https://doi.org/10.1109/ICRA57147.2024.10611057 doi:10.1109/ICRA57147.2024.10611057

    work page arXiv 2024

  2. [1]

    Akitaya, Scott Duke Kominers, Matias Korman, and Frederick Stock

    Zachary Abel, Hugo A. Akitaya, Scott Duke Kominers, Matias Korman, and Frederick Stock. A universal in-place reconfiguration algorithm for sliding cube-shaped robots in a quadratic number of moves. In Symposium on Computational Geometry (SoCG) , pages 1:1--1:14, 2024. https://doi.org/10.4230/LIPICS.SOCG.2024.1 doi:10.4230/LIPICS.SOCG.2024.1

    work page doi:10.4230/lipics.socg.2024.1 2024

  3. [2]

    Akitaya, Esther M

    Hugo A. Akitaya, Esther M. Arkin, Mirela Damian, Erik D. Demaine, Vida Dujmovic, Robin Y. Flatland, Matias Korman, Bel \' e n Palop, Irene Parada, Andr \' e van Renssen, and Vera Sacrist \' a n. Universal reconfiguration of facet-connected modular robots by pivots: The O (1) musketeers. Algorithmica , 83:1316--1351, 2021. https://doi.org/10.1007/s00453-02...

    work page doi:10.1007/s00453-020-00784-6 2021

  4. [3]

    Akitaya, Erik D

    Hugo A. Akitaya, Erik D. Demaine, Matias Korman, Irina Kostitsyna, Irene Parada, Willem Sonke, Bettina Speckmann, Ryuhei Uehara, and Jules Wulms. Compacting squares: Input-sensitive in-place reconfiguration of sliding squares. In Scandinavian Symposium on Algorithm Theory (SWAT) , pages 4:1--4:19, 2022. https://doi.org/10.4230/LIPICS.SWAT.2022.4 doi:10.42...

    work page doi:10.4230/lipics.swat.2022.4 2022

  5. [4]

    Akitaya, Sándor P

    Hugo A. Akitaya, Sándor P. Fekete, Peter Kramer, Saba Molaei, Christian Rieck, Frederick Stock, and Tobias Wallner. Sliding squares in parallel. In European Symposium on Algorithms (ESA) , 2025. https://doi.org/10.48550/arXiv.2412.05523 doi:10.48550/arXiv.2412.05523

    work page doi:10.48550/arxiv.2412.05523 2025

  6. [5]

    Pushing lines helps: Efficient universal centralised transformations for programmable matter

    Abdullah Almethen, Othon Michail, and Igor Potapov. Pushing lines helps: Efficient universal centralised transformations for programmable matter. Theoretical Computer Science , 830:43--59, 2020. https://doi.org/10.1016/j.tcs.2020.04.026 doi:10.1016/j.tcs.2020.04.026

    work page doi:10.1016/j.tcs.2020.04.026 2020

  7. [6]

    On efficient connectivity-preserving transformations in a grid

    Abdullah Almethen, Othon Michail, and Igor Potapov. On efficient connectivity-preserving transformations in a grid. Theoretical Computer Science , 898:132--148, 2022. https://doi.org/10.1016/j.tcs.2022.09.016 doi:10.1016/j.tcs.2022.09.016

    work page doi:10.1016/j.tcs.2022.09.016 2022

  8. [7]

    Becker, S \'a ndor P

    Aaron T. Becker, S \'a ndor P. Fekete, Phillip Keldenich, Dominik Krupke, Christian Rieck, Christian Scheffer, and Arne Schmidt. Tilt assembly: Algorithms for micro-factories that build objects with uniform external forces. Algorithmica , 82(2):165--187, 2020. https://doi.org/10.1007/S00453-018-0483-9 doi:10.1007/S00453-018-0483-9

    doi:10.1007/s00453-018-0483-9 2020

Show all 39 references
  1. [9]

    Fekete, Christian Schurig, and Enrico Stoll

    Mohamed Khalil Ben-Larbi, Kattia Flores Pozo , Tom Haylok, Mirue Choi, Benjamin Grzesik, Andreas Haas, Dominik Krupke, Harald Konstanski, Volker Schaus, Sándor P. Fekete, Christian Schurig, and Enrico Stoll. Towards the automated operations of large distributed satellite syste...

    2021 doi

  2. [10]

    Cameron, Zach Fredin, and Neil Gershenfeld

    Christopher G. Cameron, Zach Fredin, and Neil Gershenfeld. Discrete assembly of unmanned aerial systems. In International Conference on Unmanned Aircraft Systems (ICUAS) , pages 339--344, 2022. https://doi.org/10.1109/ICUAS54217.2022.9836082 doi:10.1109/ICUAS54217.2022.9836082

    2022

  3. [11]

    Assembly order planning for modular structures by autonomous multi-robot systems

    Kenneth Cheung, Irina Kostitsyna, and Tom Peters. Assembly order planning for modular structures by autonomous multi-robot systems. In International Conference on Robotics and Automation (ICRA) , 2025

    2025

  4. [12]

    Cheung and Neil Gershenfeld

    Kenneth C. Cheung and Neil Gershenfeld. Reversibly assembled cellular composite materials. Science , 341(6151):1219--1221, 2013. https://doi.org/10.1126/science.1240889 doi:10.1126/science.1240889

    2013 doi

  5. [13]

    Transformation of modular robots by rotation: 3+1 musketeers for all orthogonally convex shapes

    Matthew Connor and Othon Michail. Transformation of modular robots by rotation: 3+1 musketeers for all orthogonally convex shapes. Journal of Computer and System Sciences , 150:103618, 2025. https://doi.org/10.1016/j.jcss.2024.103618 doi:10.1016/j.jcss.2024.103618

    2025

  6. [14]

    Daymude, Kristian Hinnenthal, Andr \'e a W

    Joshua J. Daymude, Kristian Hinnenthal, Andr \'e a W. Richa, and Christian Scheideler. Computing by programmable particles. Distributed Computing by Mobile Entities: Current Research in Moving and Computing , pages 615--681, 2019. https://doi.org/10.1007/978-3-030-11072-7_22 d...

    2019 doi

  7. [15]

    Optimal binary space partitions for segments in the plane

    Mark de Berg and Amirali Khosravi. Optimal binary space partitions for segments in the plane. International Journal on Computational Geometry and Applications , 22(3):187--206, 2012. https://doi.org/10.1142/S0218195912500045 doi:10.1142/S0218195912500045

    2012 doi

  8. [16]

    S \'a ndor P. Fekete. Coordinating swarms of objects at extreme dimensions. In International Workshop on Combinatorial Algorithms (IWOCA) , pages 3--13, 2020. https://doi.org/10.1007/978-3-030-48966-3_1 doi:10.1007/978-3-030-48966-3_1

    2020 doi

  9. [17]

    Fekete, Phillip Keldenich, Ramin Kosfeld, Christian Rieck, and Christian Scheffer

    S \' a ndor P. Fekete, Phillip Keldenich, Ramin Kosfeld, Christian Rieck, and Christian Scheffer. Connected coordinated motion planning with bounded stretch. Autonomous Agents and Multi-Agent Systems , 37(2), 2023. https://doi.org/10.1007/S10458-023-09626-5 doi:10.1007/S10458-...

    2023 doi

  10. [18]

    Fekete, Peter Kramer, Christian Rieck, Christian Scheffer, and Arne Schmidt

    S \' a ndor P. Fekete, Peter Kramer, Christian Rieck, Christian Scheffer, and Arne Schmidt. Efficiently reconfiguring a connected swarm of labeled robots. Autonomous Agents and Multi-Agent Systems , 38(2), 2024. https://doi.org/10.1007/s10458-024-09668-3 doi:10.1007/s10458-024-09668-3

    2024 doi

  11. [19]

    Fekete, Eike Niehs, Christian Scheffer, and Arne Schmidt

    S \'a ndor P. Fekete, Eike Niehs, Christian Scheffer, and Arne Schmidt. Connected reconfiguration of lattice-based cellular structures by finite-memory robots. Algorithmica , 84(10):2954--2986, 2022. https://doi.org/10.1007/s00453-022-00995-z doi:10.1007/s00453-022-00995-z

    2022 doi

  12. [20]

    Butler, and Daniela Rus

    Robert Fitch, Zack J. Butler, and Daniela Rus. Reconfiguration planning for heterogeneous self-reconfiguring robots. In International Conference on Intelligent Robots and Systems (IROS) , pages 2460--2467, 2003. https://doi.org/10.1109/IROS.2003.1249239 doi:10.1109/IROS.2003.1249239

    2003 arXiv

  13. [21]

    Butler, and Daniela Rus

    Robert Fitch, Zack J. Butler, and Daniela Rus. Reconfiguration planning among obstacles for heterogeneous self-reconfiguring robots. In International Conference on Robotics and Automation (ICRA) , pages 117--124, 2005. https://doi.org/10.1109/ROBOT.2005.1570106 doi:10.1109/ROB...

    2005

  14. [22]

    Efficient shape reconfiguration by hybrid programmable matter

    Jonas Friemel, David Liedtke, and Christian Scheffer. Efficient shape reconfiguration by hybrid programmable matter. In European Workshop on Computational Geometry ( EuroCG ) , pages 14:1--14:8, 2025. https://arxiv.org/abs/2501.08663 arXiv:2501.08663

    2025

  15. [25]

    Shape recognition by a finite automaton robot

    Robert Gmyr, Kristian Hinnenthal, Irina Kostitsyna, Fabian Kuhn, Dorian Rudolph, and Christian Scheideler. Shape recognition by a finite automaton robot. In International Symposium on Mathematical Foundations of Computer Science ( MFCS ) , pages 52:1--52:15, 2018. https://doi....

    2018 doi

  16. [26]

    Forming tile shapes with simple robots

    Robert Gmyr, Kristian Hinnenthal, Irina Kostitsyna, Fabian Kuhn, Dorian Rudolph, Christian Scheideler, and Thim Strothmann. Forming tile shapes with simple robots. Natural Computing , 19(2):375--390, 2020. https://doi.org/10.1007/s11047-019-09774-2 doi:10.1007/s11047-019-09774-2

    2020 doi

  17. [27]

    Gregg, Damiana Catanoso, Olivia Irene B

    Christine E. Gregg, Damiana Catanoso, Olivia Irene B. Formoso, Irina Kostitsyna, Megan E. Ochalek, Taiwo J. Olatunde, In Won Park, Frank M. Sebastianelli, Elizabeth M. Taylor, Greenfield T. Trinh, and Kenneth C. Cheung. Ultralight, strong, and self-reprogrammable mechanical me...

    2024 doi

  18. [28]

    Gregg, Joseph H

    Christine E. Gregg, Joseph H. Kim, and Kenneth C. Cheung. Ultra-light and scalable composite lattice materials. Advanced Engineering Materials , 20(9):1800213, 2018. https://doi.org/10.1002/adem.201800213 doi:10.1002/adem.201800213

    2018 doi

  19. [29]

    Efficient shape formation by 3D hybrid programmable matter: An algorithm for low diameter intermediate structures

    Kristian Hinnenthal, David Liedtke, and Christian Scheideler. Efficient shape formation by 3D hybrid programmable matter: An algorithm for low diameter intermediate structures. In Symposium on Algorithmic Foundations of Dynamic Networks ( SAND ) , pages 15:1--15:20, 2024. http...

    2024 doi

  20. [30]

    Papadimitriou, and Jayme Luiz Szwarcfiter

    Alon Itai, Christos H. Papadimitriou, and Jayme Luiz Szwarcfiter. Hamilton paths in grid graphs. SIAM Journal on Computing , 11(4):676--686, 1982. https://doi.org/10.1137/0211056 doi:10.1137/0211056

    1982 doi

  21. [31]

    BILL-E : Robotic platform for locomotion and manipulation of lightweight space structures

    Ben Jenett and Kenneth Cheung. BILL-E : Robotic platform for locomotion and manipulation of lightweight space structures. In Adaptive Structures Conference (ASC) , 2017. https://doi.org/10.2514/6.2017-1876 doi:10.2514/6.2017-1876

    2017 doi

  22. [32]

    Material--robot system for assembly of discrete cellular structures

    Benjamin Jenett, Amira Abdel-Rahman, Kenneth Cheung, and Neil Gershenfeld. Material--robot system for assembly of discrete cellular structures. IEEE Robotics and Automation Letters , 4(4):4019--4026, 2019. https://doi.org/10.1109/LRA.2019.2930486 doi:10.1109/LRA.2019.2930486

    2019

  23. [33]

    Meso-scale digital materials: modular, reconfigurable, lattice-based structures

    Benjamin Jenett, Daniel Cellucci, Christine Gregg, and Kenneth Cheung. Meso-scale digital materials: modular, reconfigurable, lattice-based structures. In International Manufacturing Science and Engineering Conference (MSEC) , 2016. https://doi.org/10.1115/MSEC2016-8767 doi:10...

    2016 doi

  24. [34]

    Design of multifunctional hierarchical space structures

    Benjamin Jenett, Christine Gregg, Daniel Cellucci, and Kenneth Cheung. Design of multifunctional hierarchical space structures. In Aerospace Conference , pages 1--10, 2017. https://doi.org/10.1109/AERO.2017.7943913 doi:10.1109/AERO.2017.7943913

    2017

  25. [35]

    Fekete, and Aaron T

    Matthias Konitzny, Yitong Lu, Julien Leclerc, S \'a ndor P. Fekete, and Aaron T. Becker. Gathering physical particles with a global magnetic field using reinforcement learning. In International Conference on Intelligent Robots and Systems (IROS) , pages 10126--10132, 2022. htt...

    2022

  26. [36]

    Optimal in-place compaction of sliding cubes

    Irina Kostitsyna, Tim Ophelders, Irene Parada, Tom Peters, Willem Sonke, and Bettina Speckmann. Optimal in-place compaction of sliding cubes. In Scandinavian Symposium on Algorithm Theory (SWAT) , pages 31:1--31:14, 2024. https://doi.org/10.4230/LIPICS.SWAT.2024.31 doi:10.4230...

    2024 doi

  27. [37]

    Spirakis

    Othon Michail, George Skretas, and Paul G. Spirakis. On the transformation capability of feasible mechanisms for programmable matter. Journal of Computer and System Sciences , 102:18--39, 2019. https://doi.org/10.1016/j.jcss.2018.12.001 doi:10.1016/j.jcss.2018.12.001

    2019 doi

  28. [38]

    Biediger, Michael Yannuzzi, Benjamin Jenett, Amira Abdel-Rahman, Kenneth C

    Eike Niehs, Arne Schmidt, Christian Scheffer, Daniel E. Biediger, Michael Yannuzzi, Benjamin Jenett, Amira Abdel-Rahman, Kenneth C. Cheung, Aaron T. Becker, and Sándor P. Fekete. Recognition and reconfiguration of lattice-based cellular structures by simple robots. In Internat...

    2020

  29. [39]

    Santos, Dongdong Liu, Anna K

    Ana L. Santos, Dongdong Liu, Anna K. Reed, Aaron M. Wyderka, Alexis van Venrooy, John T. Li, Victor D. Li, Mikita Misiura, Olga Samoylova, Jacob L. Beckham, Ciceron Ayala-Orozco, Anatoly B. Kolomeisky, Lawrence B. Alemany, Antonio Oliver, George P. Tegos, and James M. Tour. Li...

    2022 doi

  30. [40]

    Robotic micromanipulation: Fundamentals and applications

    Zhuoran Zhang, Xian Wang, Jun Liu, Changsheng Dai, and Yu Sun. Robotic micromanipulation: Fundamentals and applications. Annual Review of Control, Robotics, and Autonomous Systems , 2:181--203, 2019. https://doi.org/10.1146/ANNUREV-CONTROL-053018-023755 doi:10.1146/ANNUREV-CON...

    2019 doi

  31. [41]

    A 5-mm untethered crawling robot via self-excited electrostatic vibration

    Yangsheng Zhu, Mingjing Qi, Zhiwei Liu, Jianmei Huang, Dawei Huang, Xiaojun Yan, and Liwei Lin. A 5-mm untethered crawling robot via self-excited electrostatic vibration. IEEE Transactions on Robotics , 38(2):719--730, 2022. https://doi.org/10.1109/TRO.2021.3088053 doi:10.1109...

    2022

Pith tools

Reviewed August 7, 2026 · model on record in the stance chip above.