Pith. sign in

REVIEW 3 major objections 6 minor 25 references

Streaming Multi-agent Pathfinding

T0 review · 3 major / 6 minor · reviewed 2026-08-15 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗ Review JSON

Pith's one-line read Streaming multi-agent pathfinding is NP-hard, but the proposed ASCBS algorithm, using cyclic vertex and edge constraints, is complete and optimal.

desk verdict 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. read the letter →

arxiv 2505.09472 v1 pith:2YGQCV2P submitted 2025-05-14 cs.MA cs.RO

Mingkai Tang , Lu Gan , Kaichen Zhang This is my paper · ORCID
classification cs.MAcs.RO
keywords streamingmulti-agentpathfindingagentstreamsconflict-basedsearchcyclicvertexconstraintedgeassemblylineroboticsNP-hardness
verification ladder T0 review T1 audit T2 compute T3 formal

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

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.

What carries the argument

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.

What would settle it

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.

Watch

Extended reading notes

Core claim

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).

Load-bearing premise

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.

Editorial extensions

If this is right

  • 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.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

  • 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.
Share X Bluesky LinkedIn Reddit HN

Signed reviews

No signed human review yet.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Referee Report

3 major / 6 minor

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.

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 (3)
  1. [Section 4.2 and Appendix A.2] 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.
  2. [Section 4.3, disjoint splitting] 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.
  3. [Appendix A.2, proof of Theorem 2] 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.
minor comments (6)
  1. [Section 5 and Appendix B] The phrase 'circle time' should be 'cycle time' in several places, including Section 5 and the caption of Figure 5.
  2. [Algorithm 1] 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.
  3. [Appendix C heading] The heading 'Disucssion on the Strategy' contains a typo and should read 'Discussion on the Strategy'.
  4. [Theorem 1 proof] 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.
  5. [Section 3, equations (2) and (7)] 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.
  6. [Figure 4] 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.

Circularity Check

0 steps flagged · score 0.0 of 10

No circularity: ASCBS's optimality/completeness proof uses standard CBS lemmas and external A*/CBS results; the flagged termination issue is a proof gap, not circularity.

full rationale

The paper's derivation chain is self-contained with respect to circularity. Theorem 1 reduces MAPF to S-MAPF using a polynomial-time feasible-solution bound from Kornhauser et al. and external NP-hardness from Banfi et al.; the reduction does not assume the conclusion. Theorem 2 is argued from standard CBS-style lemmas: Lemma 2 shows each generated constraint eliminates the specific conflict found in a node, and Lemma 3 shows any collision-free path satisfying a parent's constraints satisfies at least one child's constraints; optimality and completeness then follow from the standard CBS argument plus A* optimality and completeness as an external property. The low-level A* search is not fitted to experimental data. The paper contains no self-citations that carry a load-bearing premise, and the experimental comparison is against an independent CBS baseline with no constants fitted to outcomes. The reader's flagged concern—A* termination over an unbounded time domain—is a proof-gap or correctness issue rather than circularity: a valid stream path cannot revisit the same vertex at the same residue modulo c, so a bounded search is possible, but the paper does not supply this argument. Theorem 2 is not equivalent to its inputs by construction, so no circular step is present.

Assumptions & free parameters 0 free parameters · 6 assumptions · 1 invented entities

No free parameters are fitted. The central contribution rests on the modeling assumption that all agents in a stream share one action sequence, plus standard search algorithms and external NP-hardness/feasibility results. The agent stream is a new abstraction with no external evidence.

assumptions (6)
  • domain assumption All agents in an agent stream share the same action sequence.
    Section 3 formally defines streams this way; Appendix D proves this assumption reduces solvability, so it is load-bearing.
  • domain assumption Agents disappear upon reaching the goal vertex, and private parking zones exist.
    Section 3 states agents disappear at goals; this avoids stream interactions at goals and is used throughout the algorithm.
  • domain assumption All agent streams share a common cycle time c.
    Section 3 fixes a single c; the non-uniform cycle time case is deferred to an extension in Section 6.2 and Appendix E.
  • standard math External NP-hardness and feasibility theorems for MAPF hold, including Banfi et al. and Kornhauser et al.
    Appendix A.1 uses these to prove Theorem 1 by reduction from MAPF to S-MAPF.
  • standard math A* and CBS are optimal and complete for their respective base problems.
    Theorem 2 in Appendix A.2 composes the low-level A* and high-level CBS correctness, treating them as established results.
  • standard math Bezout's identity for comparing periodic times in non-uniform cycle settings.
    Appendix E uses gcd and Bezout to detect whether two non-uniform streams can collide at a vertex.
invented entities (1)
  • agent stream
    purpose: An infinite group of agents with the same start and goal that depart every c timesteps and follow one shared action sequence, enabling a finite description of an infinite-horizon MAPF instance.
    Introduced in Section 3 as a modeling device; there is no falsifiable prediction outside the model, and the paper itself shows in Appendix D that identical action sequences reduce solvability.

how reviews work

0 comments
Cite this review

Pith. "Pith review of Streaming Multi-agent Pathfinding." pith.science (2026). https://pith.science/paper/2YGQCV2P

@misc{pith2026250509472,
  author       = {Pith},
  title        = {Pith review of: Streaming Multi-agent Pathfinding},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/2YGQCV2P}},
  note         = {Machine review of arXiv:2505.09472}
}
read the original abstract

The task of the multi-agent pathfinding (MAPF) problem is to navigate a team of agents from their start point to the goal points. However, this setup is unsuitable in the assembly line scenario, which is periodic with a long working hour. To address this issue, the study formalizes the streaming MAPF (S-MAPF) problem, which assumes that the agents in the same agent stream have a periodic start time and share the same action sequence. The proposed solution, Agent Stream Conflict-Based Search (ASCBS), is designed to tackle this problem by incorporating a cyclic vertex/edge constraint to handle conflicts. Additionally, this work explores the potential usage of the disjoint splitting strategy within ASCBS. Experimental results indicate that ASCBS surpasses traditional MAPF solvers in terms of runtime for scenarios with prolonged working hours.

Figures

Figures reproduced from arXiv: 2505.09472 by the authors.

Figure 1
Figure 1. A snapshot of the S-MAPF problem where the cycle time [PITH_FULL_IMAGE:figures/full_fig_p001_1.png] view at source ↗
Figure 2
Figure 2. Examples of the conflicts where the cycle time is 2. The time step for the snapshot is [PITH_FULL_IMAGE:figures/full_fig_p003_2.png] view at source ↗
Figure 3
Figure 3. Success rate and average running time for different implementations of ASCBS on the instances with cycle time [PITH_FULL_IMAGE:figures/full_fig_p006_3.png] view at source ↗
Figures from the paper (3 more)
Figure 4
Figure 4. Figure 4: Average running time of ASCBS and CBS, the number of feasible instances by both two algorithms, and average relative error of [PITH_FULL_IMAGE:figures/full_fig_p007_4.png]
Figure 5
Figure 5. Figure 5: Success rate and average running time for different implementations of ASCBS on the instances with [PITH_FULL_IMAGE:figures/full_fig_p011_5.png]
Figure 6
Figure 6. Figure 6: An instance whose cycle time is 1. (a) There is no feasible solution with the assumption that the agent in the same agent stream should share the same action sequence, while (b) and (c) can form a solution without this assumption. (b) and (c) are the snapshots at the s…

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

25 extracted references · 25 canonical work pages

  1. [1]

    Intractability of time-optimal mul- tirobot path planning on 2d grid graphs with holes

    [Banfi et al., 2017] Jacopo Banfi, Nicola Basilico, and Francesco Amigoni. Intractability of time-optimal mul- tirobot path planning on 2d grid graphs with holes. IEEE Robotics and Automation Letters, 2(4):1941–1947,

    work page 2017

  2. [6]

    A multi-label a* algorithm for multi-agent pathfinding

    [Grenouilleau et al., 2019] Florian Grenouilleau, Willem- Jan Van Hoeve, and John N Hooker. A multi-label a* algorithm for multi-agent pathfinding. In Proceedings of the international conference on automated planning and scheduling, volume 29, pages 181–185,

    work page 2019

  3. [9]

    Periodic multi-agent path planning

    [Kasaura et al., 2023] Kazumi Kasaura, Ryo Yonetani, and Mai Nishimura. Periodic multi-agent path planning. In Proceedings of the AAAI Conference on Artificial Intelli- gence, volume 37, pages 6183–6191,

    work page 2023

  4. [13]

    Lifelong multi-agent path finding in large-scale ware- houses

    [Li et al., 2021] Jiaoyang Li, Andrew Tinka, Scott Kiesel, Joseph W Durham, TK Satish Kumar, and Sven Koenig. Lifelong multi-agent path finding in large-scale ware- houses. In Proceedings of the AAAI Conference on Artifi- cial Intelligence, volume 35, pages 11272–11281,

    work page 2021

  5. [15]

    Multi-agent path finding with delay probabilities

    [Ma et al., 2017] Hang Ma, TK Satish Kumar, and Sven Koenig. Multi-agent path finding with delay probabilities. In Proceedings of the AAAI Conference on Artificial Intel- ligence, volume 31,

    work page 2017

  6. [16]

    Certify- ing algorithms

    [McConnell et al., 2011] Ross M McConnell, Kurt Mehlhorn, Stefan N ¨aher, and Pascal Schweitzer. Certify- ing algorithms. Computer Science Review, 5(2):119–161,

    work page 2011

  7. [18]

    Sturtevant, Ariel Felner, Sven Koenig, Hang Ma, Thayne T

    [Stern et al., 2019] Roni Stern, Nathan R. Sturtevant, Ariel Felner, Sven Koenig, Hang Ma, Thayne T. Walker, Jiaoyang Li, Dor Atzmon, Liron Cohen, T. K. Satish Kumar, Eli Boyarski, and Roman Bartak. Multi-agent pathfinding: Definitions, variants, and benchmarks. Sym- posium on Combinatorial Search (SoCS), pages 151–158,

    work page 2019

  8. [19]

    Online multi-agent pathfinding

    [ˇSvancara et al., 2019] Jiˇr´ı ˇSvancara, Marek Vlk, Roni Stern, Dor Atzmon, and Roman Bart ´ak. Online multi-agent pathfinding. In Proceedings of the AAAI conference on artificial intelligence, volume 33, pages 7732–7739,

    work page 2019

Show all 25 references
  1. [20]

    Multi-goal multi-agent pickup and deliv- ery

    [Xu et al., 2022] Qinghong Xu, Jiaoyang Li, Sven Koenig, and Hang Ma. Multi-goal multi-agent pickup and deliv- ery. In 2022 IEEE/RSJ International Conference on In- telligent Robots and Systems (IROS) , pages 9964–9971. IEEE,

    2022

  2. [21]

    Multi-agent path finding with mutex propagation

    [Zhang et al., 2022] Han Zhang, Jiaoyang Li, Pavel Surynek, TK Satish Kumar, and Sven Koenig. Multi-agent path finding with mutex propagation. Artificial Intelligence , 311:103766,

    2022

  3. [22]

    Guidance graph op- timization for lifelong multi-agent path finding

    [Zhang et al., 2024] Yulun Zhang, He Jiang, Varun Bhatt, Stefanos Nikolaidis, and Jiaoyang Li. Guidance graph op- timization for lifelong multi-agent path finding. In Pro- ceedings of the Thirty-Third International Joint Confer- ence on Artificial Intelligence, pages 311–320,

    2024

  4. [23]

    The MAPF problem, in which agents disappear upon reaching their goals, is NP-hard to solve optimally. Proof. The proof of NP-hardness for optimally solving the MAPF problem is provided by [Banfi et al., 2017].In this proof, a reduction from the satisfiability problem (SAT) is ...

    2017

  5. [24]

    The S-MAPF problem is NP-hard to solve opti- mally. Proof. The MAPF problem can be reduced to the S-MAPF problem through the following steps. Initially, a feasible so- lution of any solvable MAPF problem instance can be cal- culated in a polynomial-time complexity, and its SOC...

    1984

  6. [25]

    E Discussion of Non-Uniform Cycle Time In this section, we present the extended definitions of cyclic conflict and constraints for the ASCBS algorithm with non- uniform cycle time

    In conclusion, the S-MAPF problem is a practical model for navigating in assembly line scenarios. E Discussion of Non-Uniform Cycle Time In this section, we present the extended definitions of cyclic conflict and constraints for the ASCBS algorithm with non- uniform cycle time...

    2011

  7. [1968]

    Multi-agent path finding for uav traffic management

    [Ho et al., 2019] Florence Ho, Ana Salta, Ruben Geraldes, Artur Goncalves, Marc Cavazza, and Helmut Prendinger. Multi-agent path finding for uav traffic management. In Proceedings of the 18th International Conference on Au- tonomous Agents and MultiAgent Systems, pages 131–139,

    2019

  8. [1984]

    Improved heuristics for multi- agent path finding with conflict-based search

    [Li et al., 2019a] Jiaoyang Li, Ariel Felner, Eli Boyarski, Hang Ma, and Sven Koenig. Improved heuristics for multi- agent path finding with conflict-based search. In IJCAI, volume 2019, pages 442–449,

    2019

  9. [1985]

    Coordinating pebble motion on graphs, the diameter of permutation groups, and applications

    [Kornhauser et al., 1984] D Kornhauser, G Miller, and P Spi- rakis. Coordinating pebble motion on graphs, the diameter of permutation groups, and applications. In 25th Annual Symposium onFoundations of Computer Science,

    1984

  10. [2011]

    Conflict-based search for optimal multi-agent pathfinding

    [Sharon et al., 2015] Guni Sharon, Roni Stern, Ariel Fel- ner, and Nathan R Sturtevant. Conflict-based search for optimal multi-agent pathfinding. Artificial intelligence , 219:40–66,

    2015

  11. [2015]

    Assembly line balancing: What happened in the last fifteen years? European Journal of Operational Research, 301(3):797–814,

    [Boysen et al., 2022] Nils Boysen, Philipp Schulze, and Armin Scholl. Assembly line balancing: What happened in the last fifteen years? European Journal of Operational Research, 301(3):797–814,

    2022

  12. [2017]

    From multi-agent pathfinding to 3d pipe routing

    [Belov et al., 2020] Gleb Belov, Wenbo Du, Maria Garcia De La Banda, Daniel Harabor, Sven Koenig, and Xinrui Wei. From multi-agent pathfinding to 3d pipe routing. In Proceedings of the International Symposium on Combina- torial Search, volume 11, pages 11–19,

    2020

  13. [2019]

    A formal basis for the heuristic determination of minimum cost paths

    [Hart et al., 1968] Peter E Hart, Nils J Nilsson, and Bertram Raphael. A formal basis for the heuristic determination of minimum cost paths. IEEE transactions on Systems Sci- ence and Cybernetics, 4(2):100–107,

    1968

  14. [2020]

    Icbs: The improved conflict-based search algorithm for multi-agent pathfinding

    [Boyarski et al., 2015] Eli Boyarski, Ariel Felner, Roni Stern, Guni Sharon, Oded Betzalel, David Tolpin, and Eyal Shimony. Icbs: The improved conflict-based search algorithm for multi-agent pathfinding. In Proceedings of the International Symposium on Combinatorial Search , v...

    2015

  15. [2021]

    Intersection coordination with priority-based search for autonomous vehicles

    [Li et al., 2023] Jiaoyang Li, Eugene Lin, Hai L Vu, Sven Koenig, et al. Intersection coordination with priority-based search for autonomous vehicles. In Proceedings of the AAAI Conference on Artificial Intelligence , volume 37, pages 11578–11585,

    2023

  16. [2022]

    Opti- mal sequential task assignment and path finding for multi- agent robotic assembly planning

    [Brown et al., 2020] Kyle Brown, Oriana Peltzer, Martin A Sehr, Mac Schwager, and Mykel J Kochenderfer. Opti- mal sequential task assignment and path finding for multi- agent robotic assembly planning. In 2020 IEEE Interna- tional Conference on Robotics and Automation (ICRA) ,...

    2020

  17. [2023]

    Depth-first iterative- deepening: An optimal admissible tree search

    [Korf, 1985] Richard E Korf. Depth-first iterative- deepening: An optimal admissible tree search. Artificial intelligence, 27(1):97–109,

    1985

Pith tools

Reviewed August 15, 2026 · model on record in the stance chip above.