Standard Multi-Agent Pathfinding (MAPF) sends a finite set of agents from start locations to goal locations while avoiding collisions. That formulation does not directly capture an assembly line operating for a long time, where robots or workpiece carriers can be introduced repeatedly according to a production cycle. S-MAPF models this situation with agent streams: agents belonging to the same stream appear periodically at the same start vertex and use the same action sequence, and therefore the same path. An agent disappears after reaching its goal. The objective is to find a collision-free path for every stream whose repeated executions remain safe over the continuing operation.
The first contribution is a formal problem definition for S-MAPF, tailored to periodic transportation in assembly-like environments. The second is Agent Stream Conflict-Based Search, or ASCBS, a conflict-based search variant that represents conflicts caused by periodic repetitions. Its conflict handling covers both agents from different streams and repeated agents belonging to the same stream. The paper also investigates the use of disjoint splitting inside ASCBS and compares variants using A* or IDA* as the low-level solver. Finally, it introduces extensions that relax assumptions of the basic model, including agents that remain in the environment and streams with non-uniform cycle times.
ASCBS has the two-level structure familiar from Conflict-Based Search. At the high level, it builds a constraint tree whose nodes contain a set of constraints and one path for each agent stream. At the low level, it plans a shortest path for an individual stream using A* in the main optimality claim, with IDA* also evaluated experimentally. The root is obtained by planning each stream without conflicts; the high-level search repeatedly selects a minimum-cost node, detects a best conflict, and creates child nodes by adding constraints that resolve it. Because a path is executed repeatedly, ordinary one-time vertex and edge constraints are supplemented by cyclic vertex and cyclic edge constraints. A cyclic vertex conflict occurs when periodic appearances of agents occupy the same vertex at corresponding times separated by an integer number of cycles. A cyclic edge conflict captures the analogous repeated traversal of the same edge, including an opposing traversal. The paper states that ASCBS with A* as its low-level solver is optimal and complete for S-MAPF, although the supplied excerpt does not include the proof details.
The experiments use three grid-like maps from the MAPF Benchmark Set: empty-8-8, random-64-64-10, and Paris_1_256. Each map is associated with 25 scenario files, and the paper says that four instances are generated per scenario and setting, with random initial stream start times, giving 100 instances for each setting. The ASCBS variants differ in their low-level solver and in whether they use disjoint splitting: A* or IDA*, each with or without that strategy. ASCBS-A-ND is also compared with conventional CBS in both computational efficiency and solution quality. Average runtime and success rate are used for one evaluation, with runs exceeding 60 seconds treated as unsuccessful and assigned a runtime of 60 seconds. The supplied evidence does not provide the individual numeric averages, success percentages, relative errors, or all parameter values for every setting.
The findings show that the value of disjoint splitting depends on map scale and on the low-level algorithm. On empty-8-8 and random-64-64-10, ASCBS-A-D is reported to outperform ASCBS-A-ND, with the difference more visible on smaller maps. On the larger Paris_1_256 map, the non-disjoint ASCBS-A-ND variant performs better. The paper explains the IDA* result differently: the runtime of IDA* is a substantial part of total computation and is strongly affected by constraints, so ASCBS-IDA-ND outperforms ASCBS-IDA-D. For long working horizons, a periodic ASCBS solution can be applied across all horizons, keeping its runtime consistent, whereas CBS becomes slower as it must consider more agents. The reported relative solution-quality error of ASCBS compared with CBS is very small and decreases as the horizon grows. Nevertheless, the excerpt does not establish the exact scalability boundary, the precise trade-off at every stream count, or how the method behaves under operational uncertainty.
Assembly lines move workpieces between workstations for partial and final assembly, and are used in industries such as automobiles, aircraft, and consumer electronics. Conveyors offer fixed routes but are difficult to adjust, motivating the use of teams of robots for flexible transport. Collision-free robot navigation creates a MAPF problem, a problem family also used in warehouses, traffic control, and pipe design. Related variants address probabilistic delays or agents occupying multiple vertices. Other nearby formulations focus on precedence-constrained assembly planning or periodic appearances in continuous space, whereas this paper targets periodic streams on a discrete graph and adapts conflict-based search to that setting.
An S-MAPF instance contains an undirected graph with unit-length edges, a cycle time shared by the streams in the basic model, and a set of agent streams. Each stream has a start vertex, a goal vertex, and an initial start time. At its scheduled times, a new agent appears at the stream’s start vertex; at every step it can move to a neighboring vertex or wait. All appearances from one stream share an action sequence and thus a path, and an appearance leaves the environment after reaching its goal. A solution must prevent both vertex and edge collisions across the repeated operation.
The key technical issue is that a conflict may occur between appearances whose absolute times differ by one or more complete cycles. Cyclic constraints encode these recurring conflicts without expanding the plan into an explicitly infinite time horizon. The two streams in a cyclic conflict need not be distinct, because different appearances of the same stream may collide with one another. High-level branching can add ordinary vertex or edge constraints, or their cyclic counterparts, depending on the detected conflict. The conclusion also states that resolving same-stream conflicts in the high-level solver is more effective than attempting to handle them only in the low-level solver.
The reported hardware and software environment is Ubuntu 20.04 on an Intel Core i7-8700 CPU at 3.2 GHz with 32 GB of memory. The study uses the three benchmark maps and 25 scenarios per map, generating 100 instances per setting as described in the excerpt. It compares four ASCBS configurations: A* versus IDA*, crossed with disjoint versus non-disjoint splitting, and separately compares ASCBS-A-ND with CBS. Runtime, success rate, and relative solution quality are the stated evaluation measures. The excerpt says that implementation code is publicly available, but it does not establish all random seeds, complete parameter schedules, or every experimental condition needed for exact reproduction.
For the two smaller maps, the A*-based disjoint-splitting variant ASCBS-A-D is reported to be faster than ASCBS-A-ND. On the larger Paris_1_256 map, ASCBS-A-ND is reported to be faster than its disjoint-splitting counterpart. Among the IDA* variants, the non-disjoint version performs better because constraint-sensitive IDA* computation contributes substantially to total runtime. In the long-horizon comparison, ASCBS keeps a stable runtime because one periodic solution applies across horizons, while CBS runtime grows with the number of agents considered. ASCBS has slightly lower or equal solution quality than CBS according to the conclusion, with a very small relative error that decreases as the horizon becomes longer.
The paper introduces S-MAPF as a discrete, periodic extension of MAPF for continuing streams of agents and proposes ASCBS with cyclic vertex and edge constraints. It claims that the A*-based ASCBS is an optimal and complete solver for the basic problem. The experiments support the practical conclusion that ASCBS is more computationally suitable than CBS for long working hours while retaining nearly the same solution quality. They also indicate that the best splitting strategy depends on map size and on the low-level search method.
The basic formulation relies on strong assumptions: agents in one stream share a cycle time and action sequence, all streams in the basic version use a common cycle time, and agents disappear at their goals. The supplied evidence does not show how delays, failures, changing tasks, different paths within one stream, capacity limits, or dynamic production demands are handled. The paper presents extensions for agents that stay in the environment and for non-uniform cycle times, but the excerpt does not provide their detailed algorithms or empirical results. It also does not provide enough numeric data to determine exact runtime thresholds or the largest reliably solved instances.
S-MAPF connects one-shot MAPF planning with the repeated operation of a production or transport system. Representing a stream by a reusable periodic path can avoid treating every future appearance as an unrelated agent and can make long-horizon planning more stable. The cyclic-conflict formulation is therefore a useful conceptual and 提案手順c basis for MAPF and MAPD researchers studying recurring traffic patterns. Its results also illustrate that search enhancements cannot be evaluated independently of map scale and the selected low-level solver.
This paper is recommended for researchers studying assembly-line transport, warehouse flows, or other discrete environments with recurring agent arrivals. It is especially relevant to readers interested in CBS, constraint-tree search, disjoint splitting, and finite representations of periodic conflicts. Readers applying it to real systems should consult the complete paper and additional experiments before assuming robustness to uncertainty, heterogeneous behavior, or very large instances.