{"id":"a40df820-423f-4395-a1be-c37255a46dc0","arxiv_id":"2508.20095","paper_version":1,"verdict":"REJECT","confidence":"MODERATE","novelty_score":6.0,"correctness_risk":"high","formal_verification":"none","parameter_count":4,"one_line_summary":"DGD uses MAPF plans to guide diffusion sampling inside convex regions and claims scalable multi-robot motion planning, but the cross-region collision assumption is not supported.","lead":"Discrete-guided diffusion (DGD) couples a discrete multi-agent path finding schedule with generative diffusion models to plan collision-free multi-robot trajectories in continuous spaces. The authors claim the hybrid reaches state-of-the-art success at up to 100 robots, but the safety guarantee depends on a decomposition assumption that is not valid across adjacent regions.","discovery_kind":"new_method","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Proposition 1(c) is false: inter-robot separation (1b) is global, so robots in adjacent convex regions can violate collision constraints; the formal feasibility guarantee collapses.","rationale":"The reader's weakest_assumption identifies Proposition 1(c) as the load-bearing premise, and my analysis confirms this is the correct locus. The paper's abstract and Section 2 claim 'formal feasibility' and 'preserved formal guarantees'; the entire decomposition-based argument depends on cross-region robot pairs being irrelevant. That is false as stated because constraint (1b) is global. The paper's own Section 5.5 admits the absence of cross-subproblem consistency constraints, which is direct in-scope evidence of the gap. I considered whether the more pressing concern is the unsupported 100-robot claim, but that is an empirical-evidence issue: Section 5.3 lacks a table with success rates for the 100-robot setting. If the safety guarantee were sound, the scalability claim could still be weak but the central contribution would partially stand. The Proposition 1(c) flaw, by contrast, undermines the formal guarantee and the safety framing, so it is the single most load-bearing concern. The concrete test I propose would settle the question directly: a two-region counterexample where region-local planning succeeds but the global trajectory violates (1b). I agree with the reader's verdict of reject, so no verdict change is needed. My assessment does not rely on questioning the authors' honesty; it is a structural argument about the constraint formulation and the decomposition proof.","tokens_in":15801,"tokens_out":3474,"duration_ms":42467,"concrete_test":"Construct a minimal counterexample: a rectangular free space partitioned by PBD into two convex cells sharing a boundary segment, and two robots whose MAPF schedule places robot 1 in cell A and robot 2 in cell B during a common time interval, with start/goal positions within r1+r2+epsilon of the shared boundary. Run DGD's per-region diffusion generation and constraint repair (Sections 4.3--4.4) on this instance. If the output concatenated trajectory has min_h ||pi_h^1 - pi_h^2||_2 < r1+r2 while each per-region solver reports success, then Proposition 1(c) is falsified and the feasibility guarantee fails. Equivalently, an analytic check suffices: take two points on opposite sides of the shared boundary at distance epsilon < r1+r2 and note that (1b) is violated while both points are in their respective regions.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The paper's central feasibility claim rests on Proposition 1(c), which asserts that 'there are no inter-region constraints at any time step, so each region defines an independent subproblem.' This is the load-bearing premise for Sections 4.3 and 4.4, where every diffusion step and every repair projection is performed per region. But Eq. (1b) is a pairwise constraint over all robot pairs, with no dependence on region membership. Since PBD partitions a connected free space into adjacent convex polygons, two robots whose centers lie in different regions can be arbitrarily close to each other across a shared boundary at the same time step; nothing in the per-region generation or repair enforces separation between them. The proof in Appendix A.2 simply asserts that feasibility constraints 'only involve robots sharing the same region,' which is precisely the claim needing proof. This is not a minor technicality: a concatenation of independently feasible per-region trajectories can violate (1b), so the claimed 'formal feasibility' and the associated safety guarantee are unsupported. The text in Section 5.5—'absence of explicit consistency constraints across subproblems'—is an acknowledgment of this gap, not a harmless limitation. The 100-robot scalability claim is also under-evidenced: Section 5.3 shows only representative trajectories and gives no quantitative success-rate or runtime data for 100 robots. The theoretical gap in Proposition 1(c) is the more load-bearing issue because it undermines the method's core guarantee.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper proposes Discrete-Guided Diffusion (DGD), a multi-robot motion planning framework that combines a discrete MAPF solver with continuous diffusion models. The method has four stages: (S1) a priority-based convex decomposition (PBD) partitions free space into disjoint convex regions; (S2) a MAPF solution is used to extract entry/exit events for each robot and region; (S3) per-region diffusion models generate trajectories guided by this spatiotemporal structure; (S4) a constraint-aware refinement step attempts to repair infeasible trajectories. The central claims are that DGD preserves formal feasibility of constraints (1a)-(1c) and that it scales to 100 robots while achieving state-of-the-art success rates and runtime.","tokens_in":16219,"tokens_out":4938,"duration_ms":57297,"significance":"If the formal guarantees were correct, DGD would be an important step toward making diffusion-based MRMP scalable: the idea of using a MAPF solution only as a spatiotemporal skeleton and then synthesizing continuous trajectories per convex region is attractive, and the PBD algorithm with its O(|V| log |V|) runtime is a reasonable contribution. The empirical comparison against MPD, MMD, and SMD on 3-18 robot benchmarks is useful, and the paper provides trajectory visualizations and an appendix with additional tables. However, the formal core is not sound as written. The decomposition independence claim in Proposition 1(c) is false because the inter-robot separation constraint (1b) is global and couples robots across region boundaries. Since both trajectory generation and repair are performed per region, the claimed safety guarantee is unsupported. The 100-robot scalability claim is also not backed by quantitative results in the manuscript.","major_comments":[{"comment":"Proposition 1(c) asserts 'There are no inter-region constraints at any time step, so each region defines an independent subproblem.' This is false as stated. Constraint (1b) is a pairwise separation constraint over all robot pairs i<j at every time h, with no dependence on region membership. PBD produces adjacent convex polygons sharing boundaries, so two robots whose centers lie in different regions at the same time can be arbitrarily close across a shared boundary. Neither the per-region generation in Section 4.3 nor the per-region repair in Section 4.4 evaluates or enforces such pairs. The proof in Appendix A.2 simply restates the claim ('collision and feasibility constraints only involve robots sharing the same region'), which is exactly the point at issue. A concatenation of independently feasible per-region trajectories can therefore violate (1b). Section 5.5's acknowledgment of 'a","section":"Section 4.2, Proposition 1(c), and Appendix A.2"},{"comment":"The feasibility guarantee also depends on the projection PΠ returning a trajectory satisfying (1b)-(1c). The paper does not prove this. PΠ is solved via an augmented Lagrangian dual ascent with a quadratic penalty, but there is no convergence analysis for this nonconvex projection, no theorem that the returned y satisfies the constraints, and the stopping rule is a threshold on the residual, which is an implementation parameter rather than a certificate. Moreover, the refinement is applied per region, so even a converged projection would not repair cross-region violations of (1b). Thus the claimed 'lightweight repair mechanism ensures trajectory feasibility' is not backed by a formal argument.","section":"Section 4.4, PΠ and constraint-aware refinement"},{"comment":"The abstract and Section 5.3 claim that DGD 'scales to 100 robots' and achieves high success rates in large-scale environments, but no quantitative results are provided for that setting. Table 1 and Table 2 report experiments with at most 18 robots, and Section 5.3 includes only representative trajectory plots. Success rate, runtime, and feasibility statistics for the 100-robot instances are absent. This central empirical claim is therefore not evidenced by the manuscript.","section":"Section 5.3, Figure 5"},{"comment":"The obstacle-avoidance guarantee is not self-contained. The proof invokes Corollary 3 of Christopher et al. [2025], a same-group preprint, without stating or deriving the result. In addition, the theorem statement ('there exist t such that Σ ∇x do ≤ ξ') does not match the proof's conclusion about expected distance to the feasible set. The manuscript should either provide the missing argument or explicitly state the result as an empirical claim rather than a formal guarantee.","section":"Theorem 2 and Appendix A.3"}],"minor_comments":[{"comment":"CC_f is defined as a set of regions {R1,...,Rk}, but the projection PCc_f(x)=argmin_{y∈Cc_f} ||x-y||^2 should be over the union ∪R∈Cc_f R. Projection onto a nonconvex union is not uniquely defined; clarify the intended operation.","section":"Notation, Section 4.3"},{"comment":"The augmented Lagrangian is written as Lalm(y,ν)=L(y,ν)+ρ||Σ ∇y da||^2. It is unclear why the linear multiplier term is absent and whether ν is a scalar or a vector. A cleaner formulation would help the reader assess the claimed convergence behavior.","section":"Section 4.4, augmented Lagrangian"},{"comment":"Table 2 includes a method 'DM' that is not listed among the competing methods in Section 5.2. Please add its description to the comparison list.","section":"Section 5.2 and Table 2"},{"comment":"The DGD diffusion model is trained using trajectories generated by MMD, which is also a baseline. This potential advantage in the comparison should be discussed explicitly, since it may affect the fairness of the success-rate comparison.","section":"Appendix C.2"},{"comment":"There are several typos: 'Diffusion modesl' (Section 4.3), 'obatin' and 'anther' (Section 4.4), 'Beacause' (Appendix A.3), and 'Limitation Anslysis' (Section 5.5). Theorem 1 statement also uses 'S R∈Cc_f R ∈ Cf' where subset inclusion is meant.","section":"Typos and phrasing"}],"recommendation":"reject","confidential_remarks":"The Proposition 1(c) issue is not a local or presentational flaw; it invalidates the decomposition independence on which the safety claim rests. Enforcing cross-region constraints would reintroduce the global coupling that the method is designed to avoid, so the fix is not a minor revision. The 100-robot scalability claim is also underreported. I recommend rejection, though the PBD decomposition and the general hybrid MAPF-diffusion direction may be worth revisiting if the formal core is reworked and large-scale quantitative results are added."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Short version: the paper has a genuinely new pipeline and the empirical trends on standard benchmarks are impressive, but the central formal claim—that DGD preserves feasibility—doesn't survive scrutiny. Proposition 1(c) says there are no inter-region constraints, so each region is independent. That's not true: Eq. (1b) applies to every pair of robots, regardless of which convex region they are in, and adjacent regions share boundaries. Two robots on opposite sides of a boundary can be arbitrarily close. The proof in A.2 just asserts that collision constraints only couple robots in the same region; that's the very point needing proof. Section 5.5's 'absence of explicit consistency constraints across subproblems' is an admission of the gap. The repair step is also ambiguous: PΠ is written against global constraints (1b)-(1c), but the text says it runs per region. If it's global, the 'lightweight' claim is unsupported; if per-region, it doesn't prevent cross-region collisions.\n\nNone of that makes the engineering idea worthless. Combining MAPF-derived entry/exit events with region-restricted diffusion is new and sensible. The PBD decomposition, while simple, is a reasonable answer to the overlap and subproblem-coupling problems of VCC. The up-to-18-agent comparisons are meaningful: DGD matches or beats SMD's success rates at a fraction of the runtime, and it does this across dense, room, and shelf maps. If the decomposition is viewed as a heuristic, the empirical story is decent.\n\nSoft spots, beyond the main one: Theorem 2 leans on a same-group unpublished result and is about expected error, not a hard guarantee; the 100-robot result is presented only as trajectories, with no success-rate or runtime numbers; and the training data is generated by a baseline (MMD) method, which deserves more discussion.\n\nWho this is for: people building diffusion-based MRMP solvers. They should read it as a heuristic decomposition baseline, not as a safety-certified planner. I'd send it back for major revision—add explicit cross-region consistency checks, remove or reword the formal claims, and quantify the large-scale results. Still, it deserves a serious referee; the core integration is promising and the empirical setup is reusable.","headline":"Doesn't hold together as a formal feasibility guarantee: Proposition 1(c) is false, but the MAPF-guided decomposition is a real heuristic worth knowing.","tokens_in":16616,"tokens_out":3325,"would_cite":false,"duration_ms":36226,"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":"DGD, a hybrid of discrete MAPF guidance and constrained diffusion, decomposes multi-robot motion planning into independent convex subproblems and is claimed to be the first diffusion-based planner to scale to 100 robots in cluttered environ","keywords":["multi-robot motion planning","multi-agent path finding","diffusion models","convex decomposition","constraint repair","trajectory generation","scalability"],"falsifier":"Run DGD on a two-region partition where the shared boundary is long, giving robot A an exit event at the boundary of region R1 at time t and robot B an entry event into the neighboring region R2 at the same time t, with their centers closer than the sum of their radii. If the returned trajectories violate constraint (1b), the independence premise is false.","tokens_in":15738,"feed_emoji":"🤖","tokens_out":8594,"duration_ms":78535,"temperature":0.7,"pith_summary":"This paper tries to establish that multi-robot motion planning can be made both scalable and safe by merging two traditions: discrete multi-agent path finding (MAPF), which supplies a collision-free schedule, and continuous diffusion models, which generate smooth trajectories. The proposed framework, Discrete-Guided Diffusion (DGD), cuts the global nonconvex problem into independent subproblems inside convex regions, uses the MAPF solution to fix each robot's entry and exit events per region, and repairs any residual collisions with a lightweight projection step. If the claim holds, it would give the first diffusion-based planner that handles 100 robots in cluttered environments, at runtimes far below prior diffusion-based multi-robot planners.","feed_headline":"Diffusion planner scales to 100 robots with MAPF-guided splitting","feed_subtitle":"Splitting motion planning into independent convex pieces lets diffusion solve maps other planners could not.","key_machinery":"Four components carry the argument: (1) Priority-Based Decomposition (PBD), a greedy Hertel–Mehlhorn-style merge of triangulation cells that produces a non-overlapping convex partition of free space biased toward robot traffic; (2) the transition set T, which records each robot's entry/exit time and position per region from the MAPF solution, converting the spatial partition into temporally independent subproblems; (3) projected score-based diffusion, which uses SGLD updates plus a Euclidean projection onto the subproblem's convex region to maintain obstacle avoidance; and (4) constraint-aware diffusion refinement, an augmented-Lagrangian projection PΠ that enforces inter-robot separation an","core_discovery":"DGD's central claim is that the MRMP problem can be reduced to independent convex-region subproblems by using a MAPF solution as a spatiotemporal skeleton. Each subproblem is solved by a score-based diffusion model that samples trajectories inside a convex region, guided by entry and exit events extracted from the MAPF plan; a Euclidean projection onto the region's convex set guarantees obstacle avoidance. Inter-robot separation is enforced by a constraint-aware diffusion refinement step that runs an augmented-Lagrangian projection onto the separation and kinematic constraints, but only for subproblems flagged as infeasible. The authors claim this preserves formal feasibility while scaling t","pith_inferences":["My inference: the independence guarantee in Proposition 1(c) presupposes that robots in different convex regions can never approach within the sum of their radii across the shared boundary; a partition that merely tiles free space does not ensure that, so the formal feasibility claim may need a boundary-separation condition or a global cross-region verification pass.","My inference: adding cross-region consistency constraints, such as matching boundary arrival times, would likely remove the sharp velocity discontinuities the paper reports in Section 5.5, at modest additional cost.","My inference: the same discrete-skeleton-to-diffusion pattern could apply to other high-dimensional coordination tasks, such as warehouse traffic or drone swarms, wherever a coarse discrete schedule exists and continuous refinement is needed.","My inference: because the MAPF solution fixes the spatiotemporal corridor, DGD's trajectory quality is bounded by MAPF's routing choices; using multiple MAPF skeletons or an iterative refinement loop could further shorten paths."],"forward_implications":["On the four benchmark map families (basic, dense, room, shelf), DGD maintains near-100% success through 18 robots; on dense maps with 6 robots it matches the SMD baseline's 100% success at roughly 4% of SMD's runtime.","DGD generates feasible trajectories for 100 robots in a cluttered map with 104 obstacles, a 2.5x increase in robot count over the prior diffusion-based multi-robot baseline.","Initializing the diffusion reverse process with the MAPF solution rather than noise improves sampling efficiency and lets DGD shorten grid-bound MAPF paths into continuous trajectories.","The per-region repair step keeps constraint enforcement cheap because the Lagrangian projection runs only on infeasible subproblems in low-dimensional convex spaces, not on the global problem.","PBD's non-overlapping convex partition eliminates the mode-switch explosion caused by overlapping convex covers such as VCC, reducing the number of diffusion calls."],"supporting_citations":[{"why":"supplies the MRMP benchmark maps and the SMD baseline; defines the central comparison","marker":"Liang et al. [2025]"},{"why":"provides the MMD baseline, the MAPF-diffusion integration DGD builds on, and the codebase used for training","marker":"Shaoul et al. [2024]"},{"why":"defines the MPD baseline, a single-robot motion planning diffusion adapted for multi-robot comparison","marker":"Carvalho et al. [2023]"},{"why":"supplies the graph-of-convex-sets premise that DGD extends to the multi-robot setting","marker":"Marcucci et al. [2023]"},{"why":"defines the VCC decomposition baseline that PBD improves on by avoiding overlap","marker":"Werner et al. [2024a]"},{"why":"provides the triangulation-merging algorithm underlying Priority-Based Decomposition","marker":"Hertel and Mehlhorn [1983]"},{"why":"supplies the projection-convergence corollary used in the proof of Theorem 2 for obstacle-avoidance feasibility","marker":"Christopher et al. [2025]"},{"why":"defines the denoising diffusion probabilistic model framework used for trajectory generation","marker":"Ho et al. [2020]"}],"fun_headline_variants":["MAPF skeleton guides diffusion for 100-robot motion","Diffusion + MAPF: splitting for scalable multi-robot planning","Discrete-guided diffusion scales to 100-robot planning","Split and conquer: diffusion solves large MRMP","Diffusion with MAPF guide scales to 100 robots"],"cache_read_input_tokens":2688,"weakest_assumption_plain":"The formal feasibility claim rests on the premise that robots in different convex regions can never collide, so constraint repair can be performed independently region by region; if two robots can sit near a shared boundary at the same time, the per-region check never examines that pair.","fun_headline_variants_meta":{"raw":{"variants":["MAPF skeleton guides diffusion for 100-robot motion","Diffusion + MAPF: splitting for scalable multi-robot planning","Discrete-guided diffusion scales to 100-robot planning","Split and conquer: diffusion solves large MRMP","Diffusion with MAPF guide scales to 100 robots"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000236,"raw_usage":{"total_tokens":1322,"prompt_tokens":709,"completion_tokens":613,"prompt_tokens_details":{"cached_tokens":256},"prompt_cache_hit_tokens":256,"prompt_cache_miss_tokens":453,"completion_tokens_details":{"reasoning_tokens":532}},"tokens_in":453,"tokens_out":613,"duration_ms":7210,"temperature":1.0,"reasoning_tokens":532,"cache_read_input_tokens":256,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-05T15:14:23.560643+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Run DGD on a two-region partition where the shared boundary is long, giving robot A an exit event at the boundary of region R1 at time t and robot B an entry event into the neighboring region R2 at the same time t, with their centers closer than the sum of their radii. If the returned trajectories violate constraint (1b), the independence premise is false.","supporting_citations":[{"cited_title":"Motion planning diffusion: Learning and planning of robot motions with diffusion models","cited_arxiv_id":null,"evidence_quote":"defines the MPD baseline, a single-robot motion planning diffusion adapted for multi-robot comparison"},{"cited_title":"Fast triangulation of simple polygons","cited_arxiv_id":null,"evidence_quote":"provides the triangulation-merging algorithm underlying Priority-Based Decomposition"}],"review_version":1}