{"id":"2b405b27-db78-4344-8d5b-a9d06477841f","arxiv_id":"2506.23333","paper_version":1,"verdict":"CONDITIONAL","confidence":"HIGH","novelty_score":4.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":0,"one_line_summary":"A practical evaluation shows the CH2C histogram-based algorithm outperforms GLC and MWPMexpand on total cost for separated shapes, at the price of more pick-and-place operations, plus a partial hardware demo.","lead":"This paper benchmarks an algorithm that reconfigures connected tile shapes with a single inchworm-style robot, comparing it to existing planners in simulation and on hardware. It finds the new approach wins on total travel cost when shapes are well separated, but uses many more pickups and dropoffs, and the hardware demo needed manual help.","discovery_kind":"extension","skeptic_critique":{"model":"deepseek-v4-flash","headline":"The Boxy/Snakey map generators may oversample histogram-friendly shapes, so the reported cost advantage of CH2C may not generalize to arbitrary separated configurations.","rationale":"The reader's weakest assumption identified benchmark representativeness and the unit-cost model as concerns. I agree with the representativeness concern but sharpen it: the Boxy generation rule (adding only to the right and top) is not just an arbitrary random process; it produces directed polyominoes that are structurally aligned with the CH2C histogram construction, making it plausible that the cost advantage is an artifact of the map family. The Snakey rule is less extreme but still an anisotropic growth process. The unit-cost model is explicitly stated as a condition of the claim and is therefore not a hidden flaw. A more severe issue, such as an internal inconsistency in the algorithm or a clear sign of biased cost counting, would be needed to reject the paper. Since the paper is honest about its limitations and the theoretical guarantee from Becker et al. supports the algorithm's worst-case performance, the existing CONDITIONAL verdict remains appropriate. The stress-test concern reinforces that the empirical generalization needs to be tested against a more diverse benchmark before the claim can be accepted as broadly true.","tokens_in":8671,"tokens_out":10298,"duration_ms":112618,"concrete_test":"Sample start and target configurations uniformly from all connected polyominoes of size n (using Redelmeier's algorithm) for n in {20, 40, 60}, place them in disjoint bounding boxes with varying horizontal/vertical gaps, and rerun the CH2C, GLC, and MWPMexpand comparison exactly as in Section III. If CH2C does not yield lower total cost than GLC on a substantial majority of these maps, the empirical claim should be restricted to the directed-growth map families rather than stated generally. Also report the exact generation parameters (seeds, tile counts, separation distributions) for the original Boxy/Snakey sets to allow reproduction.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The paper's central empirical claim is that CH2C achieves lower total cost than GLC and MWPMexpand for configurations separated by a horizontal or vertical line under unit operation costs. This rests entirely on the two 1000-map benchmarks described in Section III-B. The generation procedures are only loosely specified: Boxy adds tiles randomly only to the right and top of existing tiles, yielding directed/staircase polyominoes with many branches pointing toward the separator, which are exactly the 'free components' the histogram subroutine moves efficiently. Snakey prioritizes recently placed tiles, another anisotropic growth process. No seeds, tile counts, or separation distances are reported, so the map distributions are not reproducible and cannot be shown to be representative of typical separated start/target pairs. If these families are structurally easy for histogram-based reconfiguration, the concluding claim 'CH2C results in lower costs when the starting and target configurations can be separated by a horizontal or vertical line' may hold only for this narrow class rather than for well-separated configurations in general.","agreement_with_reader":"partial"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper evaluates CH2C, a recently proposed constant-factor approximation algorithm for reconfiguring connected tile configurations with a single robot, against two existing heuristic planners (GLC and MWPMexpand) from prior work. The evaluation is carried out in simulation on three sets of 1000 maps (Boxy, Snakey, Overlapping) under a unit-cost model for move, pickup, and dropoff operations, and is complemented by a hardware demonstration using a Bill-E inchworm robot. The authors report that CH2C achieves the lowest total cost on the separated map sets with 100% completion, at the price of more pickup/dropoff operations, and that its advantage vanishes on overlapping configurations. The paper concludes that CH2C is superior when start and target can be separated by a horizontal or vertical line and when pickup/dropoff costs equal movement costs.","tokens_in":8796,"tokens_out":5130,"duration_ms":46642,"significance":"The paper provides the first practical evaluation of a theoretically grounded reconfiguration algorithm (CH2C) with a constant-factor guarantee, comparing it to established heuristics in a relevant robotic model. The inclusion of a physical demonstration on an inchworm robot, even with disclosed manual assistance, is a useful step toward bridging theory and hardware. The qualitative trends in the scatter plots are suggestive and the comparison against independent baselines (GLC, MWPMexpand) is sensible. However, the strength of the empirical conclusions is limited by the loosely specified map generation, the lack of any statistical measures, and an unresolved gap between the 2-scaled theoretical setting and the unit-tile simulations. If the reported trends are confirmed under better-specified and more diverse benchmarks, the paper would be a valuable reference for practitioners selecting reconfiguration planners.","major_comments":[{"comment":"The description of the Boxy and Snakey map generators is insufficient for reproducibility and potentially unrepresentative: no random seeds, tile counts, or separation distances are given, and the growth rules ('tiles were randomly added to the right and top of existing tiles' for Boxy; 'prioritizing recently placed tiles' for Snakey) are anisotropic and may systematically favor shapes for which the histogram subroutine is efficient. Because the central conclusion that CH2C yields lower costs for horizontally or vertically separated configurations rests entirely on these two 1000-map benchmarks, the representativeness of the generated maps needs to be justified with concrete parameters, or the claim must be restricted to the tested shape families.","section":"Section III-B"},{"comment":"The theoretical algorithm in Becker et al. [5] is presented for 2-scaled configurations (2×2 tiles rooted at even grid coordinates), but the simulation maps in Section III-B appear to be ordinary unit-size tile polyominoes. The paper does not state whether the implementation scales the inputs or modifies the algorithm to handle unit tiles. Without this clarification, the connection between the implemented CH2C and the constant-factor guarantee is unclear, and the evaluation may not be testing the algorithm whose performance is claimed in the abstract.","section":"Section II and Section III-B"},{"comment":"The empirical comparison reports only scatter plots and completion rates, with no error bars, confidence intervals, or statistical tests. Statements such as 'CH2C displays a strongly linear relationship with the TSP cost' and the conclusion that CH2C 'results in lower costs' are not quantified, so the reader cannot assess the variability across the 1000 maps or determine whether the observed differences are robust to map-generation randomness. The authors should provide at least the variance of the costs or a statistical comparison (e.g., paired tests or confidence intervals) to support the qualitative claims.","section":"Section III-A, Figures 5-7"},{"comment":"The sentence 'All maps belong to the cases shown in Figures 4a and 4c' is ambiguous: it is unclear whether each of the Boxy and Snakey sets uses only a horizontal bisector, only the two-bisector case, or a mixture. This ambiguity matters because Section III-F later introduces yet another 1000-map set specifically for the two-bisector case, and the central claim concerns separation by a horizontal or vertical line. Please clarify the separation geometry of each benchmark set and state explicitly which of Figures 4a, 4b, or 4c each map family belongs to.","section":"Section III-B and Section III-F"}],"minor_comments":[{"comment":"The hardware demonstration required manual assistance for picking up and placing tiles; the Conclusion acknowledges this, but the abstract's phrase 'practical setting' and the claim of demonstrating feasibility should be qualified to avoid overstatement.","section":"Section IV"},{"comment":"The definition of schedule says pickup, dropoff, and movement are 'weighted equally'; consider using 'counted equally' for clarity, since the term 'weighted' might suggest tunable weights.","section":"Section I-C"},{"comment":"The phrase 'strongly linear relationship' in the captions would be more informative with a reported slope, intercept, or R² value for the CH2C versus TSP cost scatter.","section":"Figures 5 and 6"},{"comment":"Please specify the number of tiles (or the range) and the spatial separation in the generated maps; these parameters are essential for interpreting the cost scales and for reproducing the experiments.","section":"Section III-B"},{"comment":"The Concorde TSP solver is mentioned without a citation; please add the appropriate reference so that readers can identify the exact solver version used.","section":"Section III-A"},{"comment":"Consider adding a data and code availability statement. Releasing the map generators, seeds, and simulation code would greatly enhance the reproducibility of the empirical claims.","section":"General"}],"recommendation":"major_revision","confidential_remarks":"The paper evaluates an algorithm from a companion paper by substantially overlapping authors. This is not improper in itself, but the referees should be alert to potential selection bias in the benchmark design. The lack of detailed map-generation parameters and statistical analysis currently makes it difficult to assess whether the reported cost advantage of CH2C is robust. The fit to the journal's scope is appropriate for a robotics venue, though the empirical nature of the contribution should be emphasized in the final version."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"You should know this paper is an evaluation study, not a new algorithm. CH2C comes from a companion CCCG 2025 paper by mostly the same authors. What is new here is the first systematic comparison of CH2C against GLC and MWPMexpand on random maps, plus a hardware demo. That comparison is genuinely useful for anyone working on single-robot tile reconfiguration in the Bill-E model.\n\nThe paper does several things well. The scatter plots are clear and the qualitative story holds up: CH2C is cheaper on separated configurations, comparable to GLC on overlapping ones, and MWPMexpand frequently fails. The authors also explicitly show the countervailing trend — CH2C uses many more pickup/dropoff pairs — so the central conclusion is properly scoped to the unit-cost model. They are honest in the text that the hardware demo required manual assistance for lifting and placing tiles. That is a real limitation, and they state it.\n\nThe soft spots are reproducibility and generality of the map benchmarks. No code or data are released, no seeds are given, and the generation procedures in Section III-B are loose: Boxy adds tiles only to the right and top, Snakey prioritizes recent tiles. The stress-test concern is fair here — those generators may produce shapes that are unusually histogram-friendly, so the reported cost advantage for separated configurations might not extend to the full class of separated shapes. The paper already scopes its claim to \"can be separated by a horizontal or vertical line,\" which helps, but the map sampling still looks selection-prone. Also, there are no error bars or statistical tests; statements like \"significantly outperforms\" are informal. That said, the trends in the raw scatter plots are strong, so the lack of statistics is a weakness in presentation, not a sign the qualitative result is wrong.\n\nThe citation pattern is benign: the self-citation is to the paper that defines the algorithm being evaluated, and the comparisons to GLC and MWPMexpand are appropriate. The manuscript is honest about limitations, including obstacle handling and 3D adaptation, which I appreciate.\n\nWho should read this: people working on Bill-E-like reconfiguration or on empirical algorithm evaluation in programmable matter. It is not a theory contribution, but it gives a fair baseline comparison that could inform algorithm choice.\n\nRecommendation: send it to peer review. It deserves serious referee time. The main conditions for acceptance are releasing code and data, documenting the map generation precisely, and adding error bars or a statistical test. The central empirical claim is believable and the authors have already disclosed the main caveats.","headline":"A useful, honest empirical comparison of CH2C against prior planners, with real reproducibility gaps around map generation and statistics.","tokens_in":9409,"tokens_out":1849,"would_cite":false,"duration_ms":23128,"reading_group":"maybe","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":[],"pacs":[],"model":"deepseek-v4-flash","headline":"In simulation, the histogram-based CH2C planner beats the GLC and MWPMexpand heuristics on cost when start and target shapes are linearly separable and all operations cost one unit; it also runs on a Bill-E robot with some manual help.","keywords":["polyomino reconfiguration","single-robot manipulation","histogram intermediate configurations","Bill-E robot","connected tile structures","schedule cost","heuristic comparison","programmable matter"],"falsifier":"Run an exhaustive search for optimal schedules on all small polyomino pairs (up to, say, eight tiles) that are separable by a horizontal or vertical line under the unit-cost model, and compare CH2C's schedule cost to optimal and to GLC; if CH2C is not consistently below GLC and within a small constant of optimal on a large majority of instances, the paper's central performance claim fails. A cheaper probe is to re-run the Boxy and Snakey benchmarks with pickup and dropoff cost set to twice the move cost and locate the crossover where CH2C becomes worse than GLC.","tokens_in":8441,"feed_emoji":"🤖","tokens_out":6294,"duration_ms":64004,"temperature":0.7,"pith_summary":"At bottom, this paper is a practical stress test of a theoretical promise. It implements the recently proposed CH2C algorithm, which reconfigures a connected set of tiles using a single robot that walks on the tiles and carries one tile at a time while keeping the structure connected, and measures it against two existing planners, GLC and MWPMexpand. In 1000-map simulated test sets, CH2C completes every map and achieves the lowest total cost whenever the start and target shapes can be separated by a horizontal or vertical line and pickup, dropoff, and movement each cost one unit. The advantage disappears when the shapes overlap, and it reverses if tile pickups or dropoffs are much more expensive than moving, because CH2C performs many more of those operations. A hardware demonstration on a Bill-E inchworm robot shows that the method is physically executable, with manual assistance needed for some tile placements.","feed_headline":"Histogram planner wins on separated tile reconfiguration","feed_subtitle":"CH2C beats GLC and MWPMexpand in simulation when pickup and move costs are equal; hardware demo follows.","key_machinery":"The mechanism is a three-phase schedule built around histograms, intermediate shapes made of a unit-height base strip with unit-width columns attached. Phase I transforms the start configuration into a histogram by iteratively moving 'free components'—parts of the configuration that can be shifted without disconnecting it—downward; Phase II reconfigures between two opposing histograms by repeatedly moving the topmost, leftmost surplus tile to the topmost, leftmost deficit position; Phase III reverses Phase I to reach the target. This decomposition replaces the full polyomino reconfiguration problem with two easier conversions and is what carries the constant-factor approximation guarantee inherited from the original algorithm.","core_discovery":"Central claim: the histogram-based approximation algorithm, whose worst-case guarantee was already known, is also the best practical choice in the regime its theory covers. Specifically, the paper reports that on the Boxy and Snakey benchmark sets, where the bounding boxes of start and target are separated by a line, CH2C yields lower total schedule cost than GLC and MWPMexpand under unit operation costs, with a 100% completion rate while MWPMexpand finishes only 71.4% and 50.5% of the maps and GLC tends to give the highest costs. The same advantage does not hold for overlapping configurations, where CH2C drops to roughly the level of GLC, and it depends on pickup and dropoff costing no more than movement; the paper reports that CH2C uses significantly more pickup/dropoff pairs than the other planners. The authors therefore position CH2C as the method of choice precisely when the separation condition holds and the cost model is uniform, and as less attractive when lifting and placing tiles dominates robot travel.","pith_inferences":["The separation condition in the benchmarks is stricter than the theory requires; testing CH2C on configurations separated by a line but with highly elongated or concave shapes would reveal how the practical advantage degrades as histogram creation becomes more expensive.","Because the paper shows a sharp dependence on the pickup/dropoff cost ratio, a natural extension is a hybrid that uses CH2C's shortest-path group moves but selects free components to minimize tile lifts; the paper does not explore this.","The linearity of CH2C cost against the TSP baseline in the Boxy and Snakey plots suggests the algorithm's practical makespan may scale predictably with instance size; a scaling study over the number of tiles would test whether the constant-factor guarantee translates into a useful asymptotic advantage over GLC."],"forward_implications":["If start and target shapes are linearly separable, CH2C offers a complete planner with lower schedule cost than GLC and MWPMexpand under equal unit operation costs, so the separation condition can serve as a cheap pre-check before choosing a planner.","CH2C's 100% completion on the Boxy, Snakey, and Overlapping test sets makes it a more dependable fallback than MWPMexpand, which fails on up to half of the harder maps, even when its cost advantage is small.","When the robot platform makes pickups or dropoffs costlier than movement, the planner of choice shifts to GLC or MWPMexpand, since CH2C's lower travel cost is paid for with many more tile lifts.","The Bill-E hardware demonstration shows the schedule class is physically achievable for small translations, but real-robot constraints (magnet strength and front clearance) must be handled before the method becomes fully autonomous."],"supporting_citations":[{"why":"Supplies the CH2C algorithm and the constant-factor approximation guarantee that this paper implements and benchmarks.","marker":"[5]"},{"why":"Supplies the GLC and MWPMexpand baseline planners and the original single-robot polyomino reconfiguration problem formulation.","marker":"[13]"},{"why":"Establishes NP-hardness of optimal Bill-E reconfiguration schedules, motivating the approximation and heuristic comparison.","marker":"[14]"},{"why":"Introduces the Bill-E inchworm robot concept used in the hardware demonstration.","marker":"[19]"},{"why":"Describes the material-robot system and Bill-E platform actually used for the physical demo.","marker":"[20]"}],"fun_headline_variants":["Histogram planner beats heuristics on separated tile maps","Single robot reconfiguration: histogram planner wins on separated starts","CH2C outperforms other planners when tile layouts are separated","Histogram method solves separated tile reconfiguration best in tests"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The benchmark conclusions rest on the generated Boxy and Snakey maps being representative of real reconfiguration tasks, but the generation procedure is only loosely described (randomly adding tiles to the right and top, or in all directions, with no seeds or tile counts given), and the cost model assumes pickup, dropoff, and movement each cost exactly one unit; if real maps or real robot costs differ, the reported advantage may not hold.","fun_headline_variants_meta":{"raw":{"variants":["Histogram planner beats heuristics on separated tile maps","Single robot reconfiguration: histogram planner wins on separated starts","CH2C outperforms other planners when tile layouts are separated","Histogram method solves separated tile reconfiguration best in tests"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000552,"raw_usage":{"total_tokens":2594,"prompt_tokens":868,"completion_tokens":1726,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":484,"completion_tokens_details":{"reasoning_tokens":1659}},"tokens_in":484,"tokens_out":1726,"duration_ms":12405,"temperature":1.0,"reasoning_tokens":1659,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-06T21:44:20.246716+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Run an exhaustive search for optimal schedules on all small polyomino pairs (up to, say, eight tiles) that are separable by a horizontal or vertical line under the unit-cost model, and compare CH2C's schedule cost to optimal and to GLC; if CH2C is not consistently below GLC and within a small constant of optimal on a large majority of instances, the paper's central performance claim fails. A cheaper probe is to re-run the Boxy and Snakey benchmarks with pickup and dropoff cost set to twice the move cost and locate the crossover where CH2C becomes worse than GLC.","supporting_citations":[{"cited_title":"Efficient reconfiguration of tile arrange- ments by a single active robot,","cited_arxiv_id":null,"evidence_quote":"Supplies the CH2C algorithm and the constant-factor approximation guarantee that this paper implements and benchmarks."},{"cited_title":"Connected reconfiguration of polyominoes amid obstacles using RRT ∗,","cited_arxiv_id":null,"evidence_quote":"Supplies the GLC and MWPMexpand baseline planners and the original single-robot polyomino reconfiguration problem formulation."},{"cited_title":"Reconfiguration of a 2D structure using spatio-temporal planning and load transferring,","cited_arxiv_id":null,"evidence_quote":"Establishes NP-hardness of optimal Bill-E reconfiguration schedules, motivating the approximation and heuristic comparison."},{"cited_title":"BILL-E: Robotic platform for locomotion and manipulation of lightweight space structures,","cited_arxiv_id":null,"evidence_quote":"Introduces the Bill-E inchworm robot concept used in the hardware demonstration."},{"cited_title":"Material–robot system for assembly of discrete cellular structures,","cited_arxiv_id":null,"evidence_quote":"Describes the material-robot system and Bill-E platform actually used for the physical demo."}],"review_version":1}