{"id":"6e9b8a4e-7c39-4002-8141-577ea6c069a8","arxiv_id":"2502.09299","paper_version":2,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":7.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":0,"one_line_summary":"For any weighting between empty and loaded robot moves, single-robot tile reconfiguration is NP-hard, and disjoint start/target boxes admit a constant-factor approximation with optimal carry distance for 2-scaled shapes.","lead":"This paper studies how one robot can rearrange connected grids of passive tiles into a target shape as quickly as possible. It proves the weighted version of this problem is NP-hard and gives a constant-factor approximation when the start and target shapes are in separate boxes.","discovery_kind":"extension","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Claim 6's gadget lower bound for the λ=0 reduction is asserted rather than proved; the exact threshold 29m+9n depends on an unproven '+4 per unsatisfied clause' argument, so Theorem 1's λ=0 case is not yet established.","rationale":"The reader's Eq. (2) concern is reasonable as a proof gap, but I do not think it is the most load-bearing: the intended Phase III constructs Ht by pulling Ct tiles toward the shared baseline, so within each column Ht is a prefix of Ct from above; the one-directional movement in Phase I/III gives a natural matching that should make Eq. (2) a monotonicity statement, though the paper should spell this out. The λ=0 NP-hardness gadget lower bound is a different kind of gap: it is an exact optimization threshold, and the proof of Claim 6 relies on qualitative assertions. Since the abstract's first claimed contribution is NP-hardness for every rational λ, including λ=0, this is the step whose failure would most directly undermine a headline result. I therefore flag Claim 6, while agreeing with the reader that the paper is CONDITIONAL rather than ACCEPT or REJECT: both gaps are repairable, but neither is presently carried out.","tokens_in":15734,"tokens_out":34038,"duration_ms":359782,"concrete_test":"Take the smallest unsatisfiable formula satisfying the Planar Monotone 3SAT restrictions, construct the tile instance from Section 2, and compute the minimum λ=0 weighted makespan with an exact ILP or BFS over the gadget-sized state space. If any schedule achieves 29m+9n for an unsatisfiable formula, Claim 6 is false. If the state space is too large, first prove the '+4 per unsatisfied clause' lower bound by an exchange argument on a single clause gadget and its incident variable gadgets, checking whether one traversal can satisfy two clauses at once.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The λ=0 branch of Theorem 1 (Lemma 4) hinges on Claim 6, but the proof of Claim 6 is a sketch, not an argument. It states without derivation that no variable gadget can be solved in less than 9(δ(xi)+1), that tiles can be confined to their respective variable gadgets 'by spacing them appropriately,' and that each unsatisfied clause incurs 'an extra cost of at least 4 units.' The last assertion is the entire gap between satisfiable and unsatisfiable instances: the target makespan in Eq. (1) is exactly 29m+9n, so the lower bound must rule out every schedule that interleaves gadget operations or uses one movement to serve several clauses. The text does not analyze alternative traversals of the variable gadget, nor does it prove that the +4 penalty is unavoidable when a clause is unsatisfied. Because these are exact-threshold claims, not asymptotic ones, a single unanticipated shortcut of 1–3 units would break the reduction. This is a repair gap rather than a demonstrated falsehood, but it is the most load-bearing unproved step in the NP-hardness contribution.","agreement_with_reader":"partial"},"referee_report":{"model":"deepseek-v4-flash","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.","tokens_in":15994,"tokens_out":9483,"duration_ms":86198,"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":[{"comment":"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.","section":"Section 2, Claim 6 (proof of Lemma 4)"},{"comment":"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.","section":"Section 3.4, Eq. (2) in the proof of Theorem 7"},{"comment":"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.","section":"Section 3.4, Corollary 13"}],"minor_comments":[{"comment":"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.","section":"Section 2, Lemma 4"},{"comment":"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.","section":"Section 2, reference [15]"},{"comment":"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'.","section":"Section 3.4, Theorem 7 proof"},{"comment":"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.","section":"Section 3.2, proof of Lemma 9"},{"comment":"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.","section":"Figure 8 and Section 3.4"},{"comment":"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'.","section":"Section 5, open problems"}],"recommendation":"major_revision","confidential_remarks":"The two gaps identified above are load-bearing: Claim 6 underpins the λ=0 NP-hardness and Eq. (2) underpins the constant-factor approximations. Both appear repairable in principle—Claim 6 needs a rigorous gadget-level lower-bound proof, and Eq. (2) needs either a geometric proof or a modified construction of the intermediate histograms that guarantees geodesic concatenation—but the current manuscript does not yet establish the main theorems. The paper is otherwise well organized, and the λ∈(0,1] reduction is credible in its reliance on the published ICRA 2024 construction. I recommend major revision rather than rejection, with the understanding that the revised version must contain complete proofs of both steps."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Two things to know before you read it. The weighted NP-hardness result and the disjoint-box approximation are substantive; this is not a repackaging of [24]. But the two most load-bearing pieces of the proof are sketched rather than proved, and a referee should push hard on both before accepting the theorems as stated.\n\nWhat is new: the λ∈(0,1] reduction uses an edge gadget with red and blue paths so the robot chooses between empty travel and a short carry detour, which cleanly extends the unweighted result to rational weights. The λ=0 reduction from Planar Monotone 3SAT is genuinely new, and the gadget idea—variable gadgets encoding truth assignments, clause gadgets requiring a closed cycle to be solved cheaply—is plausible. On the positive side, the histogram method for disjoint bounding boxes is a real algorithmic contribution: Lemmas 9 and 12 have actual arguments, the crossing-path exchange in Observation 8 is sound, and optimal carry distance for 2-scaled instances is the kind of concrete guarantee that matters in this model. The self-citation to [24] for the vertex gadget is legitimate; that is a published, independent hardness result.\n\nThe soft spots are exact. Claim 6, which separates satisfiable from unsatisfiable instances in the λ=0 reduction, is not proved. The text says it is \"easy to observe\" that no variable gadget can be solved faster, that tiles can be confined \"by spacing them appropriately,\" and that each unsatisfied clause incurs \"an extra cost of at least 4 units.\" None of those assertions is derived. Since the threshold is exact—29m+9n—one unanticipated shortcut of even a single unit would break the reduction. The stress-test note is right that this is the most fragile step.\n\nEquation (2) in Theorem 7 is the second gap. The equality σ(Cs,Ct)=σ(Cs,Hs)+σ(Hs,Ht)+σ(Ht,Ct) is asserted in a few lines, and the given justification does not rule out overshooting in the intermediate histogram Ht. The concern is valid: Ht is built inside Ct's bounding box but can sit at lower y-coordinates than tiles it is later matched to, so the decomposition is not an automatic property of L1 matchings. Theorem 7, Corollary 13, and Theorem 15 all lean on this equality. These are repair gaps, not demonstrated falsehoods, but they are load-bearing, not cosmetic.\n\nThis paper is for people working on programmable matter and single-robot reconfiguration; they will want it as the weighted generalization and as a benchmark for what a constant-factor approximation can look like. Send it to peer review. Require a proof of Claim 6, either prove Eq. (2) under explicit histogram choices or restrict the theorem accordingly, and clarify what remains of Corollary 13 if Eq. (2) fails.","headline":"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.","tokens_in":16507,"tokens_out":2374,"would_cite":true,"duration_ms":24644,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["68Q17","68W25","68U05"],"pacs":[],"model":"deepseek-v4-flash","headline":"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.","keywords":["single robot reconfiguration","polyominoes","programmable matter","weighted makespan","NP-hardness","constant-factor approximation","minimum-weight perfect matching","histogram configurations"],"falsifier":"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.","tokens_in":15533,"feed_emoji":"🤖","tokens_out":9093,"duration_ms":77630,"temperature":0.7,"pith_summary":"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.","feed_headline":"One robot moving tiles: perfect plans hard, good plans fast","feed_subtitle":"Separated start and goal boxes let a polynomial algorithm get within a constant factor of optimal.","key_machinery":"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.","core_discovery":"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$.","pith_inferences":["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."],"forward_implications":["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."],"supporting_citations":[{"why":"Supplies the earlier NP-hardness result for the unweighted case and the vertex/edge gadget construction that the $\\lambda>0$ reduction modifies with blue and red paths.","marker":"[24]"},{"why":"Gives the Hamiltonian path problem in induced grid graphs, the source problem for the $\\lambda\\in(0,1]$ reduction.","marker":"[30]"},{"why":"Defines Planar Monotone 3SAT, the source problem for the $\\lambda=0$ reduction.","marker":"[15]"},{"why":"Shows that deciding minimal makespan for sequential sliding-square reconfiguration is NP-complete and provides gadget ideas used in the $\\lambda=0$ construction.","marker":"[3]"},{"why":"Supplies the two-auxiliary-tile patching technique for preserving connectivity while translating non-2-scaled components.","marker":"[2]"},{"why":"Provides the feasible-mechanisms model and auxiliary-tile method for programmable matter used in the strip/corridor translation lemma.","marker":"[37]"}],"fun_headline_variants":["Tile reconfig by one robot: NP-hard general, constant-factor when boxes separate","One robot tile reconfig: NP-hard with weights, but disjoint boxes yield O(1) approx","Tile rearranging by one robot: NP-hard general, but constant-factor when boxes disjoint","Single robot tile moves: NP-hard with costs, but separated boxes get constant-factor plan"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"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.","fun_headline_variants_meta":{"raw":{"variants":["Tile reconfig by one robot: NP-hard general, constant-factor when boxes separate","One robot tile reconfig: NP-hard with weights, but disjoint boxes yield O(1) approx","Tile rearranging by one robot: NP-hard general, but constant-factor when boxes disjoint","Single robot tile moves: NP-hard with costs, but separated boxes get constant-factor plan"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.00237,"raw_usage":{"total_tokens":9101,"prompt_tokens":896,"completion_tokens":8205,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":512,"completion_tokens_details":{"reasoning_tokens":8112}},"tokens_in":512,"tokens_out":8205,"duration_ms":49438,"temperature":1.0,"reasoning_tokens":8112,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-07T22:02:28.109476+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"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.","supporting_citations":[{"cited_title":"Fekete, and Aaron T","cited_arxiv_id":null,"evidence_quote":"Supplies the earlier NP-hardness result for the unweighted case and the vertex/edge gadget construction that the $\\lambda>0$ reduction modifies with blue and red paths."},{"cited_title":"Akitaya, Erik D","cited_arxiv_id":null,"evidence_quote":"Shows that deciding minimal makespan for sequential sliding-square reconfiguration is NP-complete and provides gadget ideas used in the $\\lambda=0$ construction."},{"cited_title":"Akitaya, Esther M","cited_arxiv_id":null,"evidence_quote":"Supplies the two-auxiliary-tile patching technique for preserving connectivity while translating non-2-scaled components."}],"review_version":1}