{"id":"29ab37b9-5208-4abe-8e0b-51ff7d945e5b","arxiv_id":"2412.15398","paper_version":2,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":2.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":3,"one_line_summary":"Running-buffer minimization for tabletop rearrangement is NP-hard, can require Ω(√n) buffers even for identical cylinders in the worst case, and exact search algorithms scale to over 100 objects.","lead":"Kai Gao's Rutgers dissertation analyzes how many temporary parking spots a robot needs when rearranging objects on a tabletop, showing the problem is hard but solvable in practice with efficient search algorithms. It combines complexity bounds, exact planners, and real-robot demonstrations for single-arm, dual-arm, and mobile robot setups.","discovery_kind":"review","skeptic_critique":{"model":"deepseek-v4-flash","headline":"No significant objection identified","rationale":"The reader's weakest assumption was Proposition 2.3.1 and the TORI greedy recovery. I examined these and found that Proposition 2.3.1 is a faithful abstraction for the TORE model as defined: with overhand grasps and unconstrained external buffers, lifting an object above all others removes path constraints, and the only blocking conditions are pairwise overlaps at goal poses. The NP-hardness proof for TORE uses object gadgets that are non-circular but the construction correctly creates bidirectional dependencies while keeping start and goal arrangements feasible. The URBM upper bound via planar separators is consistent with known vertex-separation bounds for grids, and the recurrence yields O(sqrt(n)). The TORI recovery (Algorithms 6 and 7) is indeed heuristic without completeness guarantees, but that is presented as an empirical framework rather than a formal exact algorithm, so it does not undermine the core theoretical claims. The remaining concerns are reproducibility and deferred proofs, which the reader already captured in the conditional verdict. I found no new load-bearing flaw, so I leave the verdict unchanged.","tokens_in":55481,"tokens_out":23669,"duration_ms":226977,"concrete_test":"Run exact brute-force enumeration on all TORE instances with n <= 8 uniform cylinders, comparing the minimal running buffer over all dependency-graph linear orderings with the minimal running buffer over all physically executable pick-n-place sequences in a physics simulator (e.g., PyBullet). If the two minima agree on every instance, Proposition 2.3.1's abstraction is empirically confirmed for small dense cases; a counterexample would reveal a missing physical constraint.","verdict_should_be":"UNCHANGED","load_bearing_attack":"After reviewing the dependency-graph reduction, the NP-hardness proofs, and the separator-based upper bound, I do not find an internal inconsistency that would undermine the central TORE claims. The abstraction in Proposition 2.3.1 is valid under the stated overhand-grasp/external-buffer model: pairwise start-goal overlap is the only constraint because objects are lifted above the workspace and external buffers are unconstrained. The lower-bound construction and the SEPPLAN recurrence are standard and plausible; the main risks are deferred appendix proofs and absent code/data, which affect reproducibility but not the argument's logic. The TORI greedy buffer-allocation lacks a completeness theorem, but this is an acknowledged heuristic component, not a load-bearing part of the exact TORE results.","agreement_with_reader":"partial"},"referee_report":{"model":"deepseek-v4-flash","summary":"The dissertation studies tabletop object rearrangement with overhand grasps (TORO) under four settings: external buffers (TORE), internal buffers (TORI), dual-arm coordination (CDR), and mobile-robot rearrangement (ORLA*). The central theoretical contribution is a structural analysis of the minimum running buffer (MRB) problem for TORE. The thesis proves that computing MRB is NP-hard (Theorems 2.4.1 and 2.4.2), establishes an Omega(sqrt(n)) lower bound on MRB for uniform cylinders in both labeled and unlabeled settings, provides a matching O(sqrt(n)) upper bound for the unlabeled setting via a separator-based algorithm (SEPPLAN), and develops exact search algorithms (DP, DFDP, PQS) that scale to over 100 objects on random and structured instances. The later chapters extend these ideas to internal-buffer rearrangement with lazy buffer allocation (TRLB), dual-arm task and motion planning (MCHS/MODAP), and A*-based lazy buffer allocation on mobile platforms (ORLA*). The manuscript is a PhD thesis and largely consolidates the author's previously published work.","tokens_in":55610,"tokens_out":6379,"duration_ms":58691,"significance":"If the TORE results are fully rigorous, they provide a valuable bridge between rearrangement planning and graph layout problems: the running-buffer objective is connected to vertex separation, the dependency graph abstraction is shown to be the right combinatorial object for overhand-grasp manipulation with external buffers, and the exact algorithms with witnessed plans are practically useful and parameter-free. The empirical evaluation is extensive, including physical robot demonstrations, and the DFDP algorithm's scaling to over a hundred objects is genuinely impressive. The later chapters are more heuristic in nature but the experimental methodology is generally sound. The thesis does not overclaim exactness for the TORI/TRLB framework, framing it as a high-quality heuristic, which is appropriate. The main risk is not circularity or fitted constants but the completeness of several load-bearing proofs, which are deferred to the appendix or stated informally.","major_comments":[{"comment":"The equivalence between arbitrary rearrangement plans and linear orderings of the dependency graph is asserted as 'straightforward to see' but is not proved. A formal argument must show that for any plan using b running buffers there exists a linear ordering phi with RB(G^l, phi) <= b, and conversely that the greedy execution of any ordering uses exactly the computed number of running buffers. The forward direction is the nontrivial part: one must prove that an optimal plan can be assumed to move each object from its start pose at most once, either directly to its goal or to a buffer, and that buffered objects are placed at their goals at the earliest possible time, without increasing the maximum running-buffer count. This equivalence is load-bearing because the DP in Algorithm 2 and the hardness reduction in Theorem 2.4.1 both search only over such restricted linear-order plans.","section":"Section 2.4.2 (around the equation MRB(G^l) = min_phi RB(G^l, phi))"},{"comment":"The reduction from planar vertex separation to TORE is described informally with 'object gadgets' and a rotation by 'some small angle epsilon'. To constitute a valid NP-hardness proof for TORE instances (as opposed to arbitrary dependency graphs), the construction must specify the exact object footprint geometry, the epsilon value, and a proof that the resulting labeled dependency graph contains exactly the bidirectional edges of the original planar graph with no extraneous dependencies between non-adjacent gadgets. The sentence 'It is straightforward to check' is not sufficient for a complexity-theoretic claim, especially because the construction must work for all planar graphs, including those with vertices of degree up to five.","section":"Section 2.4.3, Theorem 2.4.2 and Figure 2.7"},{"comment":"The main text states 'As shown in detail in the appendix, SEPPLAN guarantees an MRB upper bound of 20/(1-sqrt(2/3)) sqrt(n)' but the derivation of this constant and the proof of the key invariant (that after removing the separator C and the neighbors of goal vertices in C, the subgraphs A' and B' are independent and can be solved recursively without exceeding the claimed bound) are not presented in the main text. If the appendix contains a complete proof, the manuscript should refer to it explicitly; if not, this is a gap in a central upper-bound theorem. The proof of Lemma 2.5.1 is similarly deferred, which is acceptable for a thesis but should be flagged in a journal version.","section":"Section 2.5.2, Theorem 2.5.2 and the SEPPLAN sketch"},{"comment":"The TRLB framework's two-step procedure, which computes a primitive plan using the external-buffer abstraction and then greedily allocates internal buffers with random restarts, has no completeness guarantee. The manuscript states that randomness allows recovery from failures, but there is no theorem ensuring that a feasible internal-buffer plan will be found when one exists, nor a bound on the number of restarts. The chapter is consequently a heuristic contribution, which is acceptable given the experimental evidence, but the limitation should be stated explicitly in Section 3.4 and in the chapter summary to avoid the impression that TRLB is an exact planner.","section":"Section 3.4, Algorithms 6 and 7 (TRLB)"}],"minor_comments":[{"comment":"The abstract and Chapter 1 promise 'efficient combinatorial search-based solutions' and 'exact algorithms' for TORE, but the later chapters (TORI, CDR, ORLA*) are largely heuristic or approximate; a brief sentence clarifying which parts are exact and which are heuristic would help the reader.","section":"Abstract and Chapter 1"},{"comment":"Gurobi is cited as 'Gurobi 9.16.0', which does not match the known version numbering (Gurobi 9.1.x is a plausible intended version); please verify the version number.","section":"Section 2.7.1 (experimental setup)"},{"comment":"The caption contains a duplicated phrase: 'A counterexample of the proof of Prop.Proposition 2.3.3' should read 'A counterexample to the proof of Proposition 2.3.3'.","section":"Appendix A, Figure A.2 caption"},{"comment":"The density measure is denoted rho in Chapter 2 and D in Chapter 4; using consistent notation across chapters would reduce confusion, even though the definitions are analogous.","section":"Chapter 4 (notation)"},{"comment":"The empirical results would be easier to reproduce if the code and benchmark instance generators were made available; the thesis currently provides only textual descriptions and videos.","section":"General (reproducibility)"}],"recommendation":"major_revision","confidential_remarks":"The thesis is a compilation of the author's published papers, and the self-citation density is high; however, the dependency-graph and running-buffer results are not circular because they rely on independently published derivations. The main adjustment I would ask the editor to enforce is that the load-bearing proofs called out in my major comments be either fully included in the main text or clearly identified as complete in the appendix. The TORI/TRLB and dual-arm chapters are heuristic but well-evaluated; they should be framed as such. Overall, the TORE core is a solid contribution that warrants publication after the proof gaps are closed."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Kai, quick read of the Gao dissertation (arXiv:2412.15398). The thing to know: the TORE chapter (running buffer minimization) is the real meat, and it holds up. The rest is a faithful compilation of the author's own prior papers—useful as a thesis, not as new material.\n\nWhat's new and good: the reduction from vertex separation to MRB (Lemma 2.4.1, Theorem 2.4.1) is clean and correct in outline. The NP-hardness for TORE via planar graph gadgets is plausible; I'd want to see the gadget details, but they are in the appendix. The Omega(sqrt n) lower bound via dependency grids and the matching O(sqrt n) separator-based algorithm for the unlabeled case are genuinely nice: they give the first tight bounds I know for uniform cylinders. The exact DP/DFDP algorithms are not conceptually deep but scale to 100 objects, which is more than prior practical limits. I don't see a load-bearing flaw in the central TORE argument.\n\nWhere it gets softer. First, several load-bearing proofs (Lemma 2.5.1, Theorem 2.5.2, Propositions 2.3.2/2.3.3) are deferred to Appendix A and given only as sketches in the main text. In the arXiv version, the appendix is not even included, so an external reader cannot verify them. That is fixable, but it is a real reproducibility gap. Second, no code or data is released. The experimental claims—exactness, success rates, speedups—are not independently checkable. Given that the dissertation explicitly compiles P1-P7, some of these experiments are already published, but the arXiv artifact itself does not ship them. Third, the ORLA* chapter (Chapter 5) is truncated in the copy under review; I can't assess it fully. Fourth, the TORI lazy buffer allocation (Algorithms 6-7) is heuristic: the greedy buffer generation with random restarts has no completeness theorem. That doesn't undermine the TORE results, but it means the TORI/dual-arm chapters should be read as engineering contributions with empirical support, not as guaranteed-solve planners.\n\nThe citation pattern is fine: self-citation is appropriate here because the results are the author's own and are independently published. No circularity red flag.\n\nWho this is for: someone working on rearrangement planning, especially the buffer-space literature, will get value from the TORE chapter. The other chapters are useful as a consolidated reference to the author's TRLB/MODAP/ORLA* line.\n\nMy recommendation: send it to a serious referee, but the referee should be told to focus on the TORE structural results and to request the appendix proofs and a code/data release before acceptance. Would I cite it? Yes, for the MRB bounds and the DFDP algorithm. For a reading group, I'd assign only Chapter 2.","headline":"The TORE running-buffer chapter is genuinely solid; the rest is a compilation of the author's previously published work, with the usual dissertation-level reproducibility gaps.","tokens_in":805,"tokens_out":1207,"would_cite":true,"duration_ms":31886,"reading_group":"maybe","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["68T40","68Q17","05C85"],"pacs":[],"model":"deepseek-v4-flash","headline":"Computing the minimum running buffer for tabletop rearrangement is NP-hard, yet exact search can handle over 100 objects.","keywords":["tabletop object rearrangement","running buffer minimization","dependency graph","NP-hardness","lazy buffer verification","depth-first dynamic programming","dual-arm coordination","motion planning"],"falsifier":"A concrete TORE instance whose optimal plan moves an object to a buffer more than once before reaching its goal, achieving a smaller running-buffer peak than any single linear vertex ordering of the dependency graph, would refute the claimed reduction of MRB to linear ordering. Constructing such an instance is the direct test of Proposition 2.3.1 and Theorem 2.4.1.","tokens_in":55279,"feed_emoji":"🤖","tokens_out":5700,"duration_ms":48290,"temperature":0.7,"pith_summary":"This thesis argues that the minimum number of temporary storage slots (\"running buffers\") needed to rearrange objects on a tabletop is governed entirely by the ordering of objects in a dependency graph built from start and goal poses. It proves that computing this minimum is NP-hard, that for uniform cylinders the required buffer count can grow to about the square root of the number of objects, and that this growth rate is the best possible bound for unlabeled objects. On the practical side, it develops exact depth-first dynamic-programming searches that compute optimal buffer plans for instances with over a hundred densely packed objects, and a \"lazy buffer verification\" strategy that turns those plans into collision-free moves inside the workspace. The same machinery extends to dual-arm coordination and mobile-base rearrangement. A sympathetic reader would care because buffer space is the scarce resource in cluttered rearrangement, and the paper shows both why it is provably hard to minimize and that exact minimization is nonetheless computationally accessible at realistic scales.","feed_headline":"Running-buffer minimization is NP-hard; exact search still scales","feed_subtitle":"Paper proves buffer needs grow only about √n for uniform cylinders and exact planners beat heuristic baselines.","key_machinery":"The dependency graph is the central object: a directed graph whose arcs record that object i occupies object j's goal pose in the labeled setting, and a planar bipartite graph between start and goal poses in the unlabeled setting. The paper's key identity is that MRB equals the minimum over linear vertex orderings of the number of vertices whose dependency edges cross the moving boundary (vertex separation), up to an additive-one slack; this connects running buffers to vertex separation, links NP-hardness to planar vertex separation, and lets separator-based recursion and depth-first dynamic programming carry the algorithms.","core_discovery":"The paper's central claim is that the running-buffer problem for tabletop object rearrangement with overhand grasps (TORO) reduces to a graph-ordering problem: every rearrangement plan corresponds to a linear ordering of the vertices of a labeled or unlabeled dependency graph, and the maximum number of objects stored simultaneously equals the \"cut\" size of that ordering. Computing the minimum such cut (MRB) is NP-hard even when only collision-free placement between any two poses is assumed, so no polynomial-time optimal algorithm exists unless P = NP. The paper also establishes that MRB can be as large as Ω(√n) for n uniform cylinders in both labeled and unlabeled settings, and that the unlabeled bound is tight because a separator-based algorithm always produces plans with O(√n) running buffers. For the labeled setting the gap between lower and upper bounds is left open. It then shows that exact depth-first dynamic programming finds MRB-optimal plans and witness sequences for random and adversarially constructed instances with over 100 objects, and that the same planning primitives, combined with lazy buffer verification, produce state-of-the-art solutions for internal-buffer, heterogeneous-object, dual-arm, and mobile-robot variants.","pith_inferences":["The linear-ordering reduction suggests a direct connection to graph layout problems such as pathwidth and search number; an exact polynomial algorithm for bounded-treewidth dependency graphs is a natural next step that follows from existing separator structure.","Because random instances have MRB values near zero or a small constant, practical systems can probabilistically rely on a small constant number of buffer slots; a testable extension is to characterize the distribution of MRB under random geometric placements.","The lazy buffer verification idea could be applied to other task-and-motion planning settings where a coarse combinatorial schedule is refined into geometric feasibility, such as rearrangement with pushing actions or with deformable objects."],"forward_implications":["For any TORE instance, the minimum number of external buffer slots needed for feasibility is exactly the MRB of its dependency graph, so hardware designers can size buffer space from graph structure.","Unlabeled instances of uniform cylinders are always solvable with O(√n) running buffers, and that bound cannot be improved in the worst case.","Exact MRB computation is NP-hard, so large arbitrary instances cannot be solved exactly in polynomial time unless P = NP.","Depth-first dynamic programming (DFDP) computes optimal MRB and witness plans for instances with over 100 objects, and can also minimize total buffers subject to the MRB constraint.","Lazy buffer verification converts these external-buffer plans into feasible internal-buffer plans reliably and up to two orders of magnitude faster than prior baselines."],"supporting_citations":[{"why":"Establishes that TORO action sequencing is NP-hard via feedback vertex set and traveling salesperson reductions, and introduces the labeled dependency graph and total-buffer model that this thesis extends.","marker":"[1]"},{"why":"Surveys vertex separation, path width, gate matrix layout, and linear ordering problems, providing the graph-layout connection used to frame MRB as an ordering problem.","marker":"[50]"},{"why":"Proves vertex separation is NP-complete for planar graphs with maximum degree three, the hardness reduction used in Theorem 2.4.2 for TORE.","marker":"[67]"},{"why":"Supplies the planar vertex separator theorem that underpins the O(√n) SEPPLAN algorithm for unlabeled running buffer minimization.","marker":"[57]"},{"why":"Introduces the running-buffer objective for TORE that Chapters 2 and 3 build on, including the labeled and unlabeled formulations.","marker":"[74]"},{"why":"Provides the lazy buffer allocation idea that TRLB and the later dual-arm and mobile-robot chapters adopt for internal buffers.","marker":"[97]"},{"why":"BiRRT(fmRS), a dependency-graph-based baseline planner for TORI, serves as the main comparison method in Chapter 3.","marker":"[47]"},{"why":"A Monte Carlo tree search planner for TORI, used as a state-of-the-art baseline for the homogeneous and heterogeneous internal-buffer experiments.","marker":"[81]"},{"why":"A GPU-accelerated motion planning framework that MODAP leverages for fast dual-arm trajectory generation.","marker":"[96]"}],"fun_headline_variants":["Exact search solves NP-hard buffer problem for 100+ objects","Buffer poses: NP-hard to minimize, but exact DP scales","Running buffer size ~√n; labeled case bound remains open","Tabletop rearrangement: exact planners beat heuristics"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The dependency-graph abstraction assumes that any object can be moved from any collision-free pose to any other by an overhand pick-n-place, so pairwise footprint overlap is the only constraint that determines whether one object blocks another.","fun_headline_variants_meta":{"raw":{"variants":["Exact search solves NP-hard buffer problem for 100+ objects","Buffer poses: NP-hard to minimize, but exact DP scales","Running buffer size ~√n; labeled case bound remains open","Tabletop rearrangement: exact planners beat heuristics"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000566,"raw_usage":{"total_tokens":2675,"prompt_tokens":928,"completion_tokens":1747,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":544,"completion_tokens_details":{"reasoning_tokens":1678}},"tokens_in":544,"tokens_out":1747,"duration_ms":11192,"temperature":1.0,"reasoning_tokens":1678,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-11T11:29:23.320467+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"A concrete TORE instance whose optimal plan moves an object to a buffer more than once before reaching its goal, achieving a smaller running-buffer peak than any single linear vertex ordering of the dependency graph, would refute the claimed reduction of MRB to linear ordering. Constructing such an instance is the direct test of Proposition 2.3.1 and Theorem 2.4.1.","supporting_citations":[{"cited_title":"A survey of graph layout problems,","cited_arxiv_id":null,"evidence_quote":"Surveys vertex separation, path width, gate matrix layout, and linear ordering problems, providing the graph-layout connection used to frame MRB as an ordering problem."},{"cited_title":"Min cut is np-complete for edge weighted trees,","cited_arxiv_id":null,"evidence_quote":"Proves vertex separation is NP-complete for planar graphs with maximum degree three, the hardness reduction used in Theorem 2.4.2 for TORE."},{"cited_title":"A separator theorem for planar graphs,","cited_arxiv_id":null,"evidence_quote":"Supplies the planar vertex separator theorem that underpins the O(√n) SEPPLAN algorithm for unlabeled running buffer minimization."},{"cited_title":"Fast High-Quality Tabletop Rearrangement in Bounded Workspace","cited_arxiv_id":"2110.12325","evidence_quote":"Provides the lazy buffer allocation idea that TRLB and the later dual-arm and mobile-robot chapters adopt for internal buffers."},{"cited_title":"Efficiently solving general rearrangement tasks: A fast extension primitive for an incremental sampling-based planner,","cited_arxiv_id":null,"evidence_quote":"BiRRT(fmRS), a dependency-graph-based baseline planner for TORI, serves as the main comparison method in Chapter 3."},{"cited_title":"Monte-carlo tree search for efficient visually guided rearrangement planning,","cited_arxiv_id":null,"evidence_quote":"A Monte Carlo tree search planner for TORI, used as a state-of-the-art baseline for the homogeneous and heterogeneous internal-buffer experiments."}],"review_version":1}