{"id":"1581372e-2ff1-4101-a0bc-63e05355d897","arxiv_id":"2508.21205","paper_version":1,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":5.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":1,"one_line_summary":"Anonymous multi-robot path finding is solved as a discrete optimal transport problem over a cell grid, yielding integral, non-overlapping paths, plus an MPC layer for tracking and replanning.","lead":"This paper casts anonymous multi-robot path planning as an optimal transport problem over a discretized map, producing collision-free assignments and paths in one step. It then wraps the transport plan in a model predictive controller so robots with real dynamics can track those paths and replan when obstacles move.","discovery_kind":"extension","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Definition 1 only assumes a feasible unit-step plan exists; it does not force the P1 minimizer to use unit-step transitions, so the optimal Π can contain long-range jumps and the claimed non-overlapping cell trajectories are not guaranteed.","rationale":"The reader's weakest_assumption focuses on the existence of a practically feasible discretization (Def. 1) and the missing proof of Lemma 2. That is a real issue. However, the more directly load-bearing gap is that Def. 1's condition (iii) is existential over a feasible plan, whereas the central claim ('optimal and non-overlapping cell transitions') concerns the optimal plan returned by P1. Even if Lemma 2 were fully proved, P1 could still return a minimizer containing long-range jumps with c_ij > 1, because jumps are allowed by P1 and may be cheaper than any unit-step path. This would invalidate the path interpretation and the non-overlap guarantee in the strongest form stated in the abstract and Lemma 1. The issue is fixable by constraining the support of Π to admissible transitions or by designing the cost matrix so that jumps are never cheaper than the corresponding adjacent path, but the paper currently includes neither condition. I therefore agree with the conditional verdict, but for a somewhat different reason than the reader's; the paper needs a precise statement and proof that the P1 minimizer (or a selected optimal plan) uses only unit-step transitions. The LP/integrality core is mathematically sound, and the gap is an omission rather than a demonstration that the approach is fundamentally wrong.","tokens_in":11303,"tokens_out":13945,"duration_ms":163567,"concrete_test":"Use the 1-robot, 3×2 grid example from §3. Set adjacent transition costs to 1, set c_05 = 1.5, and set all other non-adjacent costs large. A feasible unit-step plan 0→4→5 exists with cost 2, so Def. 1 is satisfied. Solve P1 exactly as an LP (e.g., scipy.optimize.linprog) and inspect Π*. If Π*[0,5] = 1, the computed plan is a jump, not a cell-by-cell trajectory. Then recompute with c_05 = 2 (shortest-path cost) and check whether an off-the-shelf solver returns the jump plan on a tie; if it does, an implementation without a unit-support tie-break violates the guarantee. The minimal fix would be to add the constraint π_ij = 0 whenever c_ij > 1 and verify that the optimum is unchanged under an appropriately designed cost matrix.","verdict_should_be":"UNCHANGED","load_bearing_attack":"In §3, Definition 1 is formalized as existence of some transport plan whose positive entries have c_ij ≤ 1, but Lemma 1 is about the P1 minimizer Π*. Nothing in the definition or the lemma forces the minimizer to be that well-behaved plan. If the cost matrix assigns a non-adjacent jump a smaller cost than every adjacent path (e.g., c_05 = 2 while the only adjacent path costs 10), then Def. 1 holds because a unit-step feasible plan exists, yet Π* will contain π_05 = 1, a teleport. The claimed 'successively sliding into nearby cells' and 'readily deployed without scheduling' then fail. Moreover, two such jumps can geometrically cross without sharing any support cell, so the non-overlap proof in Lemma 1(ii), which counts only shared cells of the support, does not rule out trajectory overlap. The informal paragraph after Def. 1 states that 'Π does not require a cell transition where a robot jumps more than one cell,' but the formal definition guarantees this only for an unspecified feasible Π, not for the optimal Π*. This gap is independent of Lemma 2: even a proven, finer, practically feasible discretization would not prevent P1 from selecting a jump plan unless the cost matrix or the feasible set is constrained.","agreement_with_reader":"partial"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper proposes MPC-OT, a three-stage method for anonymous multi-robot path planning. The space is discretized into K cells, and a K×K cost matrix C encodes cell-to-cell transition costs. A transport plan Π is computed by solving a transportation LP (P1, or P2 for unbalanced cases) with row/column marginals constructed so that robot and target cells have zero demand/supply, respectively. The paper claims that the optimal transport plan gives minimum-cost, non-overlapping paths that can be deployed without scheduling. It then adds simple replans and a finer-discretization argument (Lemma 2), and finally integrates a contractive MPC scheme to track the OT paths (Theorem 1). The central theoretical claims are Lemma 1 (integrality, non-overlap, optimality, complexity) and the MPC convergence result.","tokens_in":11618,"tokens_out":7414,"duration_ms":89933,"significance":"If the main claims held, the paper would provide a strikingly simple reduction of anonymous MAPF to a transportation LP with polynomial complexity and no separate scheduling layer. The total-unimodularity argument for integrality is standard and correct in spirit, and the idea of encoding free space as virtual mass is original. However, the central non-overlap guarantee is not established as stated: Definition 1 only assumes existence of some feasible unit-step plan, while the optimal plan is not shown to use only unit-step transitions. Since two key proofs (Lemma 2 and Theorem 1) are explicitly deferred, the paper's main theoretical contribution is currently conditional. The practical MPC-OT architecture is plausible and the simulations are illustrative, but the absence of a rigorous core limits the paper's significance in its present form.","major_comments":[{"comment":"Definition 1 guarantees the existence of a feasible transport plan whose positive entries have c_ij ≤ 1. It does not constrain the optimal plan Π* of P1. Since non-adjacent transitions have finite costs, P1 can select a plan containing long-range jumps whenever such a jump is cheaper than any unit-step path. For example, if c_05 = 2 while the only adjacent-step path costs 10, Definition 1 is satisfied by some unit-step plan, but the minimizer will contain π_05 = 1. The sentence after Definition 1 that 'Π does not require a cell transition where a robot jumps more than one cell' is therefore not justified. Moreover, Lemma 1(ii) only proves that no cell is shared by two paths in the support of Π*. It does not rule out geometric overlap of two long jumps whose straight segments cross an intermediate cell that is not in the support. Thus the abstract's claim of 'guarantees non-overlapping tr","section":"Section 3, Definition 1 and Lemma 1"},{"comment":"Lemma 2 states that a finer practically feasible discretization always exists under a simple path-existence condition. The proof is explicitly deferred ('A formal proof is beyond the scope of this paper'). This lemma is load-bearing for the replanning strategy: without it, the claim that replans can resolve infeasible or overlapping situations is unsupported. The provided sketch does not address combinatorial conflicts between many simultaneous paths, nor does it show that a single common refinement works for all robots and targets. A lemma of this centrality needs a complete proof, not a sketch.","section":"Section 4.1, Lemma 2"},{"comment":"Theorem 1's proof is deferred ('will be provided elsewhere'). More importantly, Assumption 4 assumes that the OT replanning eventually generates the same final trajectories. This is essentially assuming the convergence that the theorem is supposed to prove. The theorem is therefore conditional on an untested assumption about the replanning dynamics. To make the result meaningful, the authors must either prove Assumption 4 from the OT replanning procedure and the environment assumptions, or state clearly that the theorem only applies to settings where replanning has already settled.","section":"Section 5, Assumption 4 and Theorem 1"}],"minor_comments":[{"comment":"The complexity statement is inconsistent: the abstract says O(K^2 log K) for well-behaved problems, while Section 3.1(v) says O(K^2). Please harmonize and define 'well-behaved' precisely.","section":"Abstract and Section 3.1"},{"comment":"The displayed cost matrix in the example is difficult to read (entries such as '102' and '103' appear to be formatting errors for 10^2 and 10^3, and the matrix dimensions are unclear). Please typeset it cleanly.","section":"Section 3, example cost matrix"},{"comment":"Condition (iii) says 'if π_ij = 1', but the plan described in Definition 1 may in general have fractional entries; it should say 'if π_ij > 0' if that is the intended meaning, or explicitly restrict the plan to {0,1} entries.","section":"Definition 1"},{"comment":"The notation Π(A, B) = µ(A), Π(A, B) = ν(B) is missing the arguments B and A, respectively; the correct marginal constraints should be written as Π(A, B) = µ(A) and Π(A, B) = ν(B).","section":"Section 2.1"}],"recommendation":"major_revision","confidential_remarks":"The manuscript has an appealing idea and some correct components (the total-unimodularity observation), but the main theorem's proof rests on an unjustified step: nothing in Definition 1 forces the optimal transport plan to use only unit-step transitions. This is not a minor gap—it invalidates the non-overlap guarantee as stated. The paper could be repaired by changing the formulation to restrict feasible transitions to adjacent cells and proving the path-interpretation theorem under that restriction, but that is a substantive revision. I would not reject outright because the underlying approach may be salvageable, but the current version is not acceptable. I also recommend that the editor insist on complete proofs for Lemma 2 and Theorem 1, as deferring two of the paper's central proofs is not appropriate for a journal publication."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"What you should know: this paper has a genuinely interesting idea—encode the whole free space as mass and let optimal transport decide both robot-target matching and routing in one LP. The virtual-mass construction is new to me in the MAPF literature, and the integrality argument from total unimodularity is standard but applied neatly. The unbalanced extension is a sensible touch.\n\nThat said, there are real soft spots. The most basic one is that Definition 1 only requires some feasible transport plan to use unit-cell transitions; it says nothing about the optimal Π*. The cost matrix is intended to discourage jumps, but the formal statement doesn't force the minimizer to avoid them. If the LP picks a jump, two such jumps can cross geometrically without sharing a support cell, so the column-sum argument in Lemma 1(ii) does not establish non-overlap. That's not a nitpick—it undermines the paper's central claim as stated.\n\nThen there are the deferred proofs. Theorem 1 (MPC bounded tracking and exponential convergence) is explicitly \"provided elsewhere,\" which is not acceptable in a submitted paper. Lemma 2, the existence of a finer practically feasible discretization, is only sketched with the phrase \"beyond the scope of this paper.\" These are load-bearing, not optional extras.\n\nThe complexity statement is also inconsistent: the abstract says O(K^2 log K) for well-behaved problems, while Section 3.1 says O(K^2). Minor, but it should be fixed. The simulations are purely illustrative—no baselines, no quantitative metrics—so they add little evidence.\n\nBalancing that: the core LP formulation is sound, the limits of the approach are acknowledged honestly (e.g., the replanning discussion in Section 4), and the paper is clearly written. The authors appear to know what they're doing; the gaps are incompleteness rather than confusion.\n\nMy recommendation: send it to peer review, but expect major revision. The idea deserves referee time, and the flaws are addressable. A desk reject would be too harsh. For me, I wouldn't cite it in its current state because the non-overlap guarantee isn't established, but I'd read a revised version.","headline":"A clean and appealing reformulation of anonymous MAPF as an OT LP, but the optimal transport plan can, as written, contain jumps that break the non-overlap guarantee, and two load-bearing proofs are deferred.","tokens_in":12132,"tokens_out":3120,"would_cite":false,"duration_ms":34193,"reading_group":"maybe","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["49Q22","90C05"],"pacs":[],"model":"deepseek-v4-flash","headline":"Anonymous multi-robot path finding reduces to one optimal-transport linear program whose solution assigns robots to distinct targets along non-overlapping paths, provided the grid is 'practically feasible.'","keywords":["optimal transport","multi-robot path planning","anonymous multi-agent path finding","model predictive control","linear programming","collision-free trajectories","unbalanced optimal transport","workspace discretization"],"falsifier":"Take a layout with two robots and two targets in a single corridor, with the first robot between the second robot and its target. Solve the transport problem P1 on progressively finer grids; if at every resolution the optimal plan contains a long jump (a positive entry with cost greater than 1) or two paths sharing a cell, then the practically-feasible-discretization premise fails and Lemma 1's conclusion does not follow.","tokens_in":11168,"feed_emoji":"🤖","tokens_out":9536,"duration_ms":98560,"temperature":0.7,"pith_summary":"The paper tries to show that anonymous multi-robot path finding—where any robot may go to any target—can be solved as a single optimal-transport linear program over a discretized workspace. The transport plan itself simultaneously chooses the robot-target matching and the paths, so no separate scheduling step is needed when the discretization is 'practically feasible.' The central result, Lemma 1, claims the optimal plan has integer entries, never splits a robot, gives non-overlapping trajectories, and conserves mass so every robot reaches a distinct target. Unbalanced fleets are handled by an inequality-constrained variant, and model predictive control is added to track the planned paths under robot dynamics. If correct, the usual two-step pipeline of assignment followed by collision-aware scheduling collapses into one linear program with a formal guarantee.","feed_headline":"One optimal-transport plan routes every robot without overlap","feed_subtitle":"A single linear program both assigns robots to targets and keeps their trajectories from overlapping.","key_machinery":"The load-bearing object is the transport plan, a K x K matrix of nonnegative entries solving the linear program P1. The companion object is the cost matrix, in which full robot paths are not precomputed; instead, every possible path is a sequence of cheap single-cell transitions. The key constraint is Definition 1's 'practically feasible discretization,' which requires every positive entry of an optimal plan to correspond to a cost of at most 1, i.e., a local one-cell move. Total unimodularity of the constraint matrix then forces integrality, and integrality combined with the marginal constraints forces non-overlap and distinct target assignment.","core_discovery":"The paper's central claim is that anonymous multi-robot path finding becomes a mass-reconfiguration problem. The workspace is split into K cells, and two binary distributions are defined: cells that are not targets carry one unit of source mass, while cells that are not robots carry one unit of target mass. A K x K cost matrix charges 1 for moving between neighboring cells, 0 for staying put, and a very large cost for entering an obstacle. The optimal transport plan P1 must push the source distribution to the target distribution under row- and column-sum constraints. Lemma 1 asserts that, for a 'practically feasible' discretization, this optimal plan is integral ({0,1}), respects those margi","pith_inferences":["Editorial inference: The 'no scheduling' claim is spatial, not temporal. If robots have different speeds, delays, or kinematic limits inside a cell, the same marginals do not prevent temporal overlap, so scheduling would re-enter the problem.","Editorial inference: The manuscript itself says the formal proof of Lemma 2 is beyond its scope and states that the proof of Theorem 1 will be provided elsewhere; until those gaps close, the MPC-OT guarantees are conditional on those deferred arguments.","Editorial inference: The same reconfiguration formulation could be pointed at different objectives by changing the cost matrix, such as anisotropic costs for preferred lanes or density penalties for congestion, without changing the linear-program structure—an extension the paper gestures at but does not test."],"forward_implications":["If Lemma 1 holds, robot-target matching and collision-free path planning are achieved in one linear program; no separate assignment step, shortest-path precomputation, or scheduling layer is needed when the discretization is practically feasible.","Because the cost matrix accounts for every cell-to-cell transition, alternative paths with the same cost are not excluded; the planner can use any path that respects the local-move constraint.","For unequal numbers of robots and targets, the unbalanced formulation still assigns the maximum feasible number of robots to targets at minimum cost.","The MPC loop with replanning can track OT-generated paths under robot dynamics with bounded error and exponential convergence to targets, and can react to moving obstacles by re-solving the transport problem.","Worst-case computation is O(K^3 log K), so the practical ceiling is set by the grid size K rather than the number of robots or targets directly."],"supporting_citations":[{"why":"Supplies the total-unimodularity result used to conclude that the transport LP has integral, non-splitting solutions.","marker":"[22]"},{"why":"Supplies the algorithmic complexity facts behind the O(K^3 log K) and faster well-behaved running times.","marker":"[23]"},{"why":"Provides the Kantorovich optimal-transport formulation and mass-conservation framework on which P1 is built.","marker":"[4]"},{"why":"Provides the computational optimal-transport background for discrete plans and marginal constraints.","marker":"[5]"},{"why":"Grounds the unbalanced transport extension P2 used when the numbers of robots and targets differ.","marker":"[24]"},{"why":"Supplies the partial and unbalanced OT machinery for the inequality-marginal formulation.","marker":"[25]"},{"why":"Gives the model-predictive control framework used for trajectory tracking in Algorithm 1.","marker":"[19]"},{"why":"Provides the control background underlying the bounded-error exponential-convergence claim.","marker":"[20]"},{"why":"Introduces the 'valid infrastructure' concept used to argue that finer discretizations can make an unblocked instance practically feasible.","marker":"[26]"}],"fun_headline_variants":["Optimal transport routes robots without overlap","Mass-flow planning keeps robot paths collision-free","One optimal-transport plan assigns and schedules robots","Multirobot navigation as reconfiguring mass on a grid","MPC-optimal transport: non-overlapping paths with replanning"],"cache_read_input_tokens":2688,"weakest_assumption_plain":"The whole guarantee rests on being able to find a grid where the optimal plan only ever moves a robot one cell at a time; the paper sketches, but does not fully prove, that such a grid always exists.","fun_headline_variants_meta":{"raw":{"variants":["Optimal transport routes robots without overlap","Mass-flow planning keeps robot paths collision-free","One optimal-transport plan assigns and schedules robots","Multirobot navigation as reconfiguring mass on a grid","MPC-optimal transport: non-overlapping paths with replanning"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.00019,"raw_usage":{"total_tokens":1189,"prompt_tokens":769,"completion_tokens":420,"prompt_tokens_details":{"cached_tokens":256},"prompt_cache_hit_tokens":256,"prompt_cache_miss_tokens":513,"completion_tokens_details":{"reasoning_tokens":344}},"tokens_in":513,"tokens_out":420,"duration_ms":4734,"temperature":1.0,"reasoning_tokens":344,"cache_read_input_tokens":256,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-05T14:30:40.034157+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Take a layout with two robots and two targets in a single corridor, with the first robot between the second robot and its target. Solve the transport problem P1 on progressively finer grids; if at every resolution the optimal plan contains a long jump (a positive entry with cost greater than 1) or two paths sharing a cell, then the practically-feasible-discretization premise fails and Lemma 1's conclusion does not follow.","supporting_citations":[{"cited_title":"Theory of Linear and Integer Programming","cited_arxiv_id":null,"evidence_quote":"Supplies the total-unimodularity result used to conclude that the transport LP has integral, non-splitting solutions."},{"cited_title":"Veinott, A","cited_arxiv_id":null,"evidence_quote":"Supplies the algorithmic complexity facts behind the O(K^3 log K) and faster well-behaved running times."},{"cited_title":"Topics in Optimal Transportation, volume 58 of Graduate Studies in Mathe- matics","cited_arxiv_id":null,"evidence_quote":"Provides the Kantorovich optimal-transport formulation and mass-conservation framework on which P1 is built."},{"cited_title":"Computational optimal transport: With applications to data science","cited_arxiv_id":null,"evidence_quote":"Provides the computational optimal-transport background for discrete plans and marginal constraints."},{"cited_title":"Scaling al- gorithms for unbalanced optimal transport problems","cited_arxiv_id":null,"evidence_quote":"Grounds the unbalanced transport extension P2 used when the numbers of robots and targets differ."},{"cited_title":"Alaya, and Gilles Gasso","cited_arxiv_id":null,"evidence_quote":"Supplies the partial and unbalanced OT machinery for the inequality-marginal formulation."},{"cited_title":"Rossiter","cited_arxiv_id":null,"evidence_quote":"Gives the model-predictive control framework used for trajectory tracking in Algorithm 1."},{"cited_title":"Learning-Based Adaptive Control: An Extremum Seeking Approach","cited_arxiv_id":null,"evidence_quote":"Provides the control background underlying the bounded-error exponential-convergence claim."},{"cited_title":"Complete decentralized method for on-line multi-robot trajectory planning in well-formed infrastructures","cited_arxiv_id":null,"evidence_quote":"Introduces the 'valid infrastructure' concept used to argue that finer discretizations can make an unblocked instance practically feasible."}],"review_version":1}