{"id":"b260e39d-f44f-4cad-a865-c9d0cc54496f","arxiv_id":"2505.09472","paper_version":1,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":7.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":0,"one_line_summary":"The paper formalizes streaming MAPF with periodic agent streams, presents the optimal ASCBS algorithm using cyclic constraints, and demonstrates runtime advantages over standard CBS as the working horizon grows.","lead":"This paper introduces streaming multi-agent pathfinding, where an infinite queue of robots departs from the same start point on a fixed schedule and must follow one shared action sequence. The authors propose an optimal conflict-based search algorithm using periodic constraints and show it scales better than ordinary MAPF planning when work shifts are long.","discovery_kind":"new_method","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Theorem 2 rests on an unproved termination/finite-search condition for the low-level A* solver over an unbounded time domain.","rationale":"The reader's weakest_assumption is exactly the condition I find most load-bearing: the low-level A* search is asserted to be optimal and complete without a termination argument over the unbounded time domain. I agree with the CONDITIONAL verdict. The paper's experimental contribution, code release, and NP-hardness reduction are not in question; the issue is confined to the formal proof of Theorem 2. The missing piece is a finite bound on the low-level search, and the natural bound (no repeated vertex/residue pair in any valid stream path, hence path length at most |V|·c) is never stated or used. This is a fixable gap rather than a demonstrated counterexample, so the appropriate disposition is to keep the reader's CONDITIONAL verdict rather than reject the paper. My concrete test targets the smallest primitive that would settle the concern: whether the unbounded A* implementation actually terminates on an infeasible constrained stream. If it does not, the theorem as written is incomplete; if it does, the paper still needs to state the bound explicitly for the proof to be complete.","tokens_in":16202,"tokens_out":12113,"duration_ms":150035,"concrete_test":"Run the released ASCBS code (github.com/tangmingkai/S-MAPF) on a single-stream instance with cycle time c=2 on a 3x3 graph, adding cyclic vertex constraints that forbid the goal vertex for residues 0 and 1, so no feasible low-level path exists. Record whether the low-level A* terminates with NULL within |V|·c expansions or continues expanding states without bound; non-termination would confirm the missing termination proof, while termination on this case would indicate that the gap is fixable but still absent from the written proof.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The proof of Theorem 2 (Appendix A.2) asserts optimality and completeness by combining Lemmas 2 and 3 with the optimality and completeness of the A* algorithm. That invocation is the load-bearing step. The low-level solver (Section 4.2) must find a shortest path for one stream under cyclic vertex/edge constraints and exact constraints, with no stated bound on path length or search depth. Because the time domain is unbounded, A* is not automatically complete: on an infeasible constrained instance it can keep waiting or cycling and never terminate, and if it returns arbitrarily long self-conflicting paths, the high-level constraint tree can generate arbitrarily large exact constraints, making the search space infinite. A valid S-MAPF stream path cannot visit the same (vertex, residue modulo c) twice, so every feasible stream path has length at most |V|·c; this pigeonhole bound would make the low-level search space finite and also bound the high-level constraint set. The paper never states or uses this bound, and the A* variant deliberately does not prune same-stream conflicts, so it is not searching only over the bounded valid set. Theorem 2's central claim therefore depends on an unproved termination/finite-ness condition that the current proof does not supply.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","summary":"This paper introduces the Streaming Multi-Agent Pathfinding (S-MAPF) problem, in which an infinite sequence of agents departs from a start vertex every c time steps and all agents in a stream must follow the same action sequence. The authors define cyclic vertex and edge conflicts, prove NP-hardness of S-MAPF, and propose ASCBS, a two-level CBS-style algorithm with cyclic constraints, including a disjoint-splitting variant. They claim that ASCBS with A* as the low-level solver is optimal and complete (Theorem 2), and report experiments on grid maps showing that ASCBS variants outperform a CBS baseline as the time horizon grows.","tokens_in":16422,"tokens_out":13470,"duration_ms":138356,"significance":"The S-MAPF formalization addresses a genuine and underexplored setting — periodic, predictable multi-agent routing in assembly-line-like environments — and the cyclic-constraint extension of CBS is a natural and potentially useful algorithmic idea. The paper's main theoretical claim, if fully established, would be a valuable result: exact optimal planning for infinite-horizon periodic streams. The experimental section is a real strength: code is publicly available, variants are compared on standard MAPF benchmarks, and the comparison against CBS under growing time horizons is appropriate for the motivating scenario. The main weakness is that Theorem 2 is not proven as written; the proof depends on unstated finiteness and termination conditions and on a disjoint-splitting construction that is under-specified.","major_comments":[{"comment":"The proof of Theorem 2 never establishes that the low-level A* terminates or that the search space is finite. Since the time domain is unbounded, A* over time-expanded states is not automatically complete; on an infeasible constrained instance it could keep waiting or cycling forever, and if it returns arbitrarily long paths the high-level constraint tree could also be infinite. The paper should state and use the pigeonhole bound that a feasible stream path visits no (vertex, step mod c) pair twice, hence has length at most |V|*c. This would also bound the set of possible cyclic and ordinary constraints and make the constraint tree finite. Without such a lemma, the invocation of 'the optimality and completeness of A*' in the proof of Theorem 2 is not supported.","section":"Section 4.2 and Appendix A.2"},{"comment":"The first child in the disjoint-splitting construction is not well defined. The text says: 'Add the positive vertex constraint (ask, v, qk), the cyclic vertex constraints (ask, v, qk, qk) and {(aso, v, ts_k + qk - ts_o, ∅) : o≠k} to the constraint set and replan the path of as′_k.' When the conflict is between two distinct streams, ask and as′_k differ, so this node imposes new constraints on ask and on every other stream but replans only as′_k; the un-replanned paths may violate the newly added constraints, and the positive constraint on ask is not enforced on any path that is actually replanned. If the intention is that positive constraints restrict future low-level searches, the low-level solver for as′_k should only receive its own constraints. The edge version has the same issue. This must be corrected and the disjoint-splitting cases of Lemmas 2 and 3 re-verified; as written, Theorem 2 does not cover the ASCBS-A-D variant.","section":"Section 4.3, disjoint splitting"},{"comment":"The proof of Theorem 2 is a single sentence that combines Lemmas 2 and 3 with the optimality and completeness of A* and CBS. It does not argue that the high-level constraint tree is finite, that Lemmas 2 and 3 suffice for completeness when constraints are cyclic, or that cost-ordered expansion combined with the CAT tie-breaker yields optimality of the first returned solution. A rigorous proof should be supplied, including the finite-path bound from the first comment and an induction over constraint-tree expansion that shows both completeness and optimality.","section":"Appendix A.2, proof of Theorem 2"}],"minor_comments":[{"comment":"The phrase 'circle time' should be 'cycle time' in several places, including Section 5 and the caption of Figure 5.","section":"Section 5 and Appendix B"},{"comment":"Line 12 says 'if F is N one' which should be 'if F is NONE'; also 'OP EN' is a formatting artifact of the pseudocode.","section":"Algorithm 1"},{"comment":"The heading 'Disucssion on the Strategy' contains a typo and should read 'Discussion on the Strategy'.","section":"Appendix C heading"},{"comment":"The claim that the optimal S-MAPF solution equals the optimal MAPF solution when c exceeds the makespan should be stated more explicitly: because only one agent per stream is active at any time, the shared-action-sequence assumption is vacuous for those instances.","section":"Theorem 1 proof"},{"comment":"Equation (7) is presented as a derivation of equation (2); it may be worth noting explicitly that the congruence is necessary and sufficient for the existence of nonnegative k_i and k_j, since the conflict detection in Algorithm 1 relies on this equivalence.","section":"Section 3, equations (2) and (7)"},{"comment":"Section 5.2 states that ASCBS-A-ND is compared with CBS, but the legend of Figure 4 labels the ASCBS curve as 'ASCBS-A-D'. Please align the label with the algorithm actually used.","section":"Figure 4"}],"recommendation":"major_revision","confidential_remarks":"I would not accept the paper in its current form. The experimental contribution and the problem formulation are solid, and the central algorithm is plausible, but Theorem 2 needs a rigorous proof and the disjoint-splitting construction needs to be corrected or the corresponding claims restricted to the non-disjoint variant. I recommend asking the authors to supply the missing finiteness/termination lemma and to clarify the implementation of the disjoint-splitting constraints, including a check of whether the public code matches the description."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Read the streaming MAPF paper. The headline is: it is a genuinely new problem variant and a plausible optimal algorithm, but Theorem 2's proof has a gap that is fixable, not fatal.\n\nWhat's new: the S-MAPF formalization (infinite periodic agent streams sharing one action sequence) and the cyclic vertex/edge constraint machinery are not in the cited periodic or precedence-constrained MAPF literature. The algorithm is a CBS adaptation, but the cyclic constraints are a real new technique. They also ship code and run experiments comparing four ASCBS variants plus a CBS baseline, which supports the central practical claim: per-stream planning scales better than traditional MAPF as the horizon grows. The extension sections, especially the solvability trade-off under the same-action-sequence assumption (Appendix D), are honest and useful.\n\nSoft spots, in order of real concern:\n\n1. Theorem 2 proof is not complete. The proof invokes \"optimality and completeness of A*\" as if the low-level search operates on a finite graph. It doesn't: the time domain is unbounded, and the low-level A* purposely does not prune same-stream conflicts during search. A valid stream path cannot visit the same (vertex, residue modulo c) twice, so every feasible path has length at most |V|·c. That pigeonhole bound would make the low-level state space finite and bound the high-level constraint set. The paper never states it. Without it, an infeasible constrained stream can make A* loop forever, and the CT can grow without bound. This is an omission in the proof, not a contradiction in the algorithm; adding the bound and a proper termination argument should suffice.\n\n2. Disjoint splitting (Section 4.3) is badly written. There is a notational muddle around k and k', and the first bullet puts a positive constraint on ask but says to replan as'_k. It's likely just a typo, but as written it is not a precise description. A careful referee will need the authors to rewrite it.\n\n3. Experimental reporting. No error bars or variance measures, so the differences between ASCBS-A-ND and ASCBS-A-D could be noise. The CBS comparison is reasonable but runtime is not apples-to-apples since CBS solves a different (finite-horizon) problem; the relative-error analysis helps, but a broader set of baselines would strengthen the case.\n\nWho this is for: anyone working on MAPF variants, periodic or lifelong planning, and assembly-line robot coordination. It deserves a serious referee: the problem is well-motivated, the idea is new, and the issues are addressable. I would accept for peer review and require a revision that closes the termination argument and cleans up the disjoint-splitting presentation.","headline":"Genuinely new periodic MAPF variant with a plausible CBS-style solver; the proof of optimality has a fixable termination gap, so it deserves peer review with revision.","tokens_in":16919,"tokens_out":3995,"would_cite":true,"duration_ms":39068,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":[],"pacs":[],"model":"deepseek-v4-flash","headline":"Streaming multi-agent pathfinding is NP-hard, but the proposed ASCBS algorithm, using cyclic vertex and edge constraints, is complete and optimal.","keywords":["streaming multi-agent pathfinding","agent streams","conflict-based search","cyclic vertex constraint","cyclic edge constraint","assembly line robotics","multi-agent pathfinding","NP-hardness"],"falsifier":"On a small graph, force a single stream to revisit a vertex at the same phase of the cycle under every valid action sequence, impose the corresponding cyclic constraint, and run ASCBS. If the low-level A* search does not terminate or returns a path that repeats a forbidden $(v, q \\bmod c)$ pair, Theorem 2 fails. If an instance with a known collision-free stream plan is given but ASCBS never returns a plan, that also refutes the claimed completeness.","tokens_in":16018,"feed_emoji":"🤖","tokens_out":11304,"duration_ms":105206,"temperature":0.7,"pith_summary":"This paper formalizes the streaming multi-agent pathfinding (S-MAPF) problem, in which each agent stream releases a new agent at a fixed start vertex every $c$ time steps and all agents in the stream must execute the same action sequence. The authors argue this is the right model for assembly-line robot transport, which runs for effectively unlimited working hours and needs predictable motion. The paper's central claim is that the proposed Agent Stream Conflict-Based Search (ASCBS) is complete and optimal for S-MAPF, using cyclic vertex and edge constraints that forbid entire residue classes of steps modulo $c$. If correct, this gives an exact planner for an infinite-horizon periodic MAPF variant, and the experiments indicate that it keeps runtime constant as the planning horizon grows while standard MAPF solvers slow down. The paper also proves the problem is NP-hard to solve optimally.","feed_headline":"Planner proves optimal routes for never-ending robot streams","feed_subtitle":"A cycle-time constraint handles every future stream agent at once, beating horizon-limited solvers on long runs.","key_machinery":"The load-bearing object is the cyclic vertex/edge constraint, a restriction placed on a residue class of steps modulo the cycle time $c$ rather than on one point in time. It converts an infinite periodic conflict into a finite constraint on the path of one agent stream, so the high-level constraint tree can split on which stream must avoid the recurring conflict. The companion machinery is the low-level A* search, which plans a shortest constrained path for a single stream under these residue-class constraints, and the constraint tree that repeatedly resolves the best remaining conflict. These pieces together carry the optimality and completeness argument of Theorem 2.","core_discovery":"The central discovery is that conflict resolution can be lifted from individual time steps to residue classes modulo the cycle time. A cross-stream collision at step $q_i$ of one stream and $q_j$ of another recurs at every pair of steps satisfying $t_i^s + q_i \\equiv t_j^s + q_j \\pmod c$, so forbidding only one step cannot remove it. ASCBS therefore records a cyclic vertex constraint $(as, v, q_r, q_e)$ or cyclic edge constraint, forbidding the stream from occupying $v$ (or traversing an edge) at any step $q \\equiv q_r \\pmod c$ unless $q = q_e$. Same-stream collisions are handled with ordinary vertex/edge constraints, because cyclic constraints would break completeness for that case. The paper proves that this two-level search, with A* for single-stream planning, is optimal and complete (Theorem 2), and that optimally solving S-MAPF is NP-hard (Theorem 1).","pith_inferences":["A natural next step the paper leaves implicit is to treat any periodic lifelong MAPF task with repeating trajectories as a stream, making residue-class constraints a general coordination layer for cyclic robot schedules.","Because Theorem 2 is tied to A* as the low-level solver, replacing A* with a bounded-suboptimal search would require a fresh proof; comparing such a variant would reveal how much of ASCBS's runtime gain comes from the stream encoding itself.","The experiments suggest that larger cycle times make S-MAPF easier, so an asymptotic analysis of running time as a function of $c$ and graph size could identify when the streaming formulation beats ordinary MAPF in practice."],"forward_implications":["An S-MAPF plan produced by ASCBS covers every future agent in a stream at once, so the same action sequence can be reused for each cycle and runtime does not grow with the number of workpieces moved.","Because each stream uses one periodic action sequence, robot motion is predictable, which matters when humans and robots share the workspace.","The cyclic-constraint mechanism extends to agents that remain in the environment after reaching their goal, and to streams with different cycle times, where conflicts are checked through the greatest common divisor of the cycle times.","ASCBS keeps the classical MAPF objective of minimizing the sum of path costs, now applied to streams rather than to a finite set of agents.","In the reported experiments, ASCBS runtime stays flat as the working horizon grows, while traditional CBS slows down, with only a small relative error in solution cost."],"supporting_citations":[{"why":"supplies the conflict-based search constraint-tree template that ASCBS adapts to agent streams with cyclic constraints.","marker":"[Sharon et al., 2015]"},{"why":"defines the A* algorithm used as the low-level single-stream solver whose optimality Theorem 2 depends on.","marker":"[Hart et al., 1968]"},{"why":"provides the disjoint splitting strategy adapted with positive vertex and edge constraints in one ASCBS variant.","marker":"[Li et al., 2019b]"},{"why":"establishes NP-hardness of optimal MAPF, the reduction base for Theorem 1.","marker":"[Banfi et al., 2017]"},{"why":"supplies the polynomial-time feasible MAPF solution and its $O(|V|^3)$ makespan bound, used to set a safe cycle time in the NP-hardness reduction.","marker":"[Kornhauser et al., 1984]"},{"why":"gives the Prioritize Conflicts rule the ASCBS high level uses to choose which conflict to resolve.","marker":"[Boyarski et al., 2015]"},{"why":"provides the convention that agents disappear after reaching their goals, which the stream model adopts.","marker":"[Svancara et al., 2019]"},{"why":"defines the benchmark graphs and scenario format used in the experimental evaluation.","marker":"[Stern et al., 2019]"}],"fun_headline_variants":["Cyclic constraints prove optimal for infinite agent streams","ASCBS: optimal pathfinding for periodic agent streams","Residue-class conflicts beat horizon-limited solvers","Never-ending robot streams solved with periodic constraints","Streaming MAPF: lifting conflicts to residue classes"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The load-bearing premise is that the low-level A* search over the unbounded time domain always terminates with an optimal constrained stream path; the paper supplies no finite bound on search depth, even though a valid path could never revisit the same vertex at the same phase of the cycle.","fun_headline_variants_meta":{"raw":{"variants":["Cyclic constraints prove optimal for infinite agent streams","ASCBS: optimal pathfinding for periodic agent streams","Residue-class conflicts beat horizon-limited solvers","Never-ending robot streams solved with periodic constraints","Streaming MAPF: lifting conflicts to residue classes"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000582,"raw_usage":{"total_tokens":2703,"prompt_tokens":872,"completion_tokens":1831,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":488,"completion_tokens_details":{"reasoning_tokens":1758}},"tokens_in":488,"tokens_out":1831,"duration_ms":15260,"temperature":1.0,"reasoning_tokens":1758,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-15T21:31:24.581370+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"On a small graph, force a single stream to revisit a vertex at the same phase of the cycle under every valid action sequence, impose the corresponding cyclic constraint, and run ASCBS. If the low-level A* search does not terminate or returns a path that repeats a forbidden $(v, q \\bmod c)$ pair, Theorem 2 fails. If an instance with a known collision-free stream plan is given but ASCBS never returns a plan, that also refutes the claimed completeness.","supporting_citations":[{"cited_title":"Conflict-based search for optimal multi-agent pathfinding","cited_arxiv_id":null,"evidence_quote":"supplies the conflict-based search constraint-tree template that ASCBS adapts to agent streams with cyclic constraints."},{"cited_title":"A formal basis for the heuristic determination of minimum cost paths","cited_arxiv_id":null,"evidence_quote":"defines the A* algorithm used as the low-level single-stream solver whose optimality Theorem 2 depends on."},{"cited_title":"Intractability of time-optimal mul- tirobot path planning on 2d grid graphs with holes","cited_arxiv_id":null,"evidence_quote":"establishes NP-hardness of optimal MAPF, the reduction base for Theorem 1."},{"cited_title":"Coordinating pebble motion on graphs, the diameter of permutation groups, and applications","cited_arxiv_id":null,"evidence_quote":"supplies the polynomial-time feasible MAPF solution and its $O(|V|^3)$ makespan bound, used to set a safe cycle time in the NP-hardness reduction."},{"cited_title":"Icbs: The improved conflict-based search algorithm for multi-agent pathfinding","cited_arxiv_id":null,"evidence_quote":"gives the Prioritize Conflicts rule the ASCBS high level uses to choose which conflict to resolve."},{"cited_title":"Online multi-agent pathfinding","cited_arxiv_id":null,"evidence_quote":"provides the convention that agents disappear after reaching their goals, which the stream model adopts."},{"cited_title":"Sturtevant, Ariel Felner, Sven Koenig, Hang Ma, Thayne T","cited_arxiv_id":null,"evidence_quote":"defines the benchmark graphs and scenario format used in the experimental evaluation."}],"review_version":1}