Streaming Multi-agent Pathfinding

1 Introduction

The assembly line is a manufacturing process where workpieces are moved between workstations for semi-assembly until final assembly. It is commonly applied in industries such as cars, airplanes, and consumer electronics [Boysen et al., 2022]. Workpieces can be transferred using a conveyor, which can only move them along fixed paths, making adjustments difficult. An alternative method involves using a team of robots to transport workpieces. The main challenge is navigating robots between workstations without collisions. This challenge is known as the multi-agent pathfinding (MAPF) problem and has been extensively studied. The MAPF problem is applied in various real-world scenarios, including warehouse management [Li et al., 2021; Xu et al., 2022; Zhang et al., 2024], traffic control [Ho et al., 2019; Li et al., 2023], and pipe design [Belov et al., 2020].

The assembly line operates with a production rhythm. Each workstation periodically receives a workpiece and produces a higher assembly workpiece. The time interval for the period is defined as the cycle time. In the view of the robot team, they need to transport the workpiece between workstations every cycle time. The traditional MAPF problem can be adapted for planning in a periodic scenario with finite working hours, which describes the agent by the start point, the goal point, and the start time. However, in assembly line factories with long working hours, the number of agents grows rapidly, implying that the running time for computing the optimal solution increases exponentially due to the NP-hardness of the MAPF problem [Banfi et al., 2017]. Additionally, in environments where humans and robots share space, the predictability of robot motions is crucial, which cannot be achieved by the traditional MAPF problem setup.

Hence, we suggest planning with agent streams to solve the problems of long working hours and predictability. An agent stream is an agent group containing an infinite number of agents, where agents in an agent stream depart from the start vertex every cycle time and share the same action sequence. At both the start and goal points, there are designated private parking zones for robot loading and unloading. This setup ensures that agents disappear after reaching their goals without disrupting others. It is also adopted in the online MAPF problem [ˇSvancara et al., 2019]. Formally describing an agent stream, let s be the initial start time of the agent stream and c be the cycle time. Within the agent stream, there exists an agent departing at time step k · c + s, where k ∈ N. We term the task of finding a collision-free path for each agent stream from its start point to its goal point as streaming multiagent pathfinding (S-MAPF). Figure 1 shows an example of the S-MAPF problem. The S-MAPF solution offers endless working hours availability and predictable agent movement when collaborating with humans due to the consistent action sequence. To solve the S-MAPF problem, the Agent Stream Conflict-Based Search (ASCBS) algorithm is proposed, ensuring both optimality and completeness. To resolve the conflict between different agent streams in ASCBS, we introduce the cyclical vertex constraint and the cyclical edge constraint. Additionally, the disjoint splitting strategy [Li et al., 2019b] is tailored to suit the S-MAPF problem setting. The main contributions of this paper are as follows.

• We propose the formalization of the S-MAPF problem, which can be adopted in the scenario with unlimited working hours.
• We present a two-level approach, ASCBS, to optimally solve the S-MAPF problem. The cyclical vertex constraint and cyclical edge constraint are proposed to resolve agent stream conflicts. We also explore the potential use of disjoint splitting within ASCBS.
• We conduct a comprehensive experimental evaluation to compare the computational efficiency of different ASCBS variants. Additionally, an experiment is done that demonstrates ASCBS's high computational efficiency over traditional MAPF solvers in scenarios with long working hours.
• We introduce several extensions of the S-MAPF problem that relax certain assumptions.

2 RelatedWork

Some MAPF problem variants are introduced to address realworld applications. For example, the MAPF problem with delay probabilities [Ma et al., 2017] accounts for situations where agents may experience delays in their paths. The MAPF problem for large agents [Li et al., 2019c] assumes that the agent may occupy more than one vertex. In this study, we introduce the S-MAPF problem tailored to the assembly line scenario, where agents can form streams to continuously transport workpieces. To our knowledge, there are two closely related works for a similar scenario. The Precedence Constrained Multi-Agent Task Assignment and PathFinding Problem [Brown et al., 2020] is also applied in assembly, but it focuses on planning for a single final product and emphasizes precedence constraints for operations. The Periodic Multi-Agent Path Planning Problem [Kasaura et al., 2023] assumes agents' periodic appearances but is defined in continuous space. It is solved as a continuous optimization problem, limiting its applicability to small-scale instances.

In the field of MAPF, conflict-based search [Sharon et al., 2015] is a well-studied optimal solver, with techniques proposed to accelerate the search process, such as Prioritize Conflicts [Boyarski et al., 2015], Disjoint Splitting [Li et al., 2019b], and Mutex Reasoning [Zhang et al., 2022]. This study introduces a variant of conflict-based search to solve the S-MAPF problem, incorporating some of these acceleration techniques into the algorithm.

3 ProblemDefinition

The S-MAPF problem instance is denoted by the tuple ⟨G, c,AS⟩. In this case, G = (V,E) is an undirected graph with unit edge length, and c denotes the cycle time shared by all agent streams. The set AS = {as0, as1, ..., asn-1} represents the agent streams, where n is the number of agent streams. Each asi can be described as {vs i , vg i , tsi } where vs i and vg i are the start and goal vertices, respectively. The initial start time of asi is denoted by tsi ∈ [0, c - 1]. At each time step k · c + tsi for all k ∈ N, an agent of asi will appear at vs i . After that, at each time step, the agent can take an action to move to the neighboring vertex or wait at the current vertex. Agents in the same agent stream are assumed to share the same action sequence, which implies that they also have the same path. In addition, the agent is assumed to disappear after reaching its goal vertex.

The objective of the S-MAPF problem is to find a collision-free path for each agent stream from its start vertex to its goal vertex. The solution can be denoted as P = {p0, p1, ..., pn-1}, and the path of asi is pi = [p0i , p1i , ..., pli-1 i ], with li as the path length. We name pji the j-th step of agent stream asi. For an agent whose start time is k · c + tsi for a specific k, this agent will be at the vertex pt-(k·c+tsi ) i at the time step t when k·c+tsi ≤ t < k·c+tsi +li. A solution is collision-free if and only if there are no cyclic vertex conflicts and cyclic edge conflicts. Formally, the cyclic vertex conflict is denoted as ⟨asi, asj, qi, qj, v⟩. It occurs if and only if there exist two nonnegative integers ki, kj such that the following equations are satisfied:

It means that the agent of asi with start time ki · c + tsi is located at the same vertex v at the time step (ki · c + tsi ) + qi as the agent of asj with start time kj · c + tsj . In addition, when asi and asj are the same agent stream (j - i = 0), ki equal to kj won't cause a conflict because these two agents are the same agent. We use ⟨asi, asj , qi, qj , vx, vy⟩ to denote the cyclic edge conflict. It occurs if and only if there exist two non-negative integers ki, kj such that the following equations are satisfied:pqi i = vx = pqj+1 j ∧ pqi+1 i = vy = pqj j (4)

It implies that the agent of asi with start time ki ·c+tsi crosses the same edge (vx, vy) at the time step (ki · c + tsi ) + qi with the agent of asj with start time kj ·c+tsj . Similar to the cyclic vertex conflict, when asi and asj are the same agent stream, ki equal to kj won't cause a conflict. Notably, Equations 2 and 5 are the same and can be further derived:

Algorithm 1 ASCBShigh

Input: agent streams AS, graph G, cycle time c 1: R←new node 2: R.cons←∅ 3: for each agent stream as in AS do 4: R.paths[as] ←ASCBSlow(as,R.cons, c) 5: end for 6: R.cost ← calculate the SOC of R.paths. 7: OPEN ←{R} 8: while OPEN ̸= ∅ do 9: N ←minimum cost node fromOPEN. 10: OPEN ←OPEN\{N} 11: F ← the best collision in N 12: if F is None then 13: return N.paths 14: end if 15: Cons←build cyclic vertex / edge constraints or vertex / edge constraints from F 16: for constraint con = (as, v, qr, qe) / (as, vi, vj , qr, qe)/ (as, v, q) / (as, vi, vj , q) in Cons do 17: D←new node 18: D.cons←N.cons ∪ con 19: D.paths[as] ←ASCBSlow(as,D.cons, c) 20: if D.paths[as] is not NULL then 21: D.cost ← calculate the SOC of D.paths 22: OPEN ← OPEN ∪ {D} 23: end if 24: end for 25: end while 26: return NULL

conflict and the edge conflict. A multi-value decision diagram (MDD) is constructed for each agent stream to evaluate conflict priority. By examining the number of occurrences of conflicts at a layer with a width of 1 in the MDD of two associated agent streams, a conflict with a larger number is given higher priority. In Lines 12∼14, if no conflicts are found, the optimal solution is reached, and the algorithm terminates. In the case of a conflict that involves two distinct agent streams, two cyclic vertex constraints or cyclic edge constraints are generated to resolve the conflict. Alternatively, if the conflict is from the same agent stream, two vertex constraints or edge constraints are established (Line 15). Further details will be explained in the following paragraph. In Lines 16 ∼ 24, two

It should be noted that asi and asj in the cyclic vertex conflict ⟨asi, asj, qi, qj, v⟩ and cyclic edge conflict ⟨asi, asj , qi, qj , vx, vy⟩ are not necessarily different, because the agents of the same agent stream might have vertex and edge conflicts. Figure 2 presents several examples of the conflicts.

Referencing the MAPF problem, we adopt the sum-of-cost (SOC) for the objective function. Let C(P) denote the SOC of the solution P. It can be computed by the equation:

An optimal solution is the one that is collision-free and has the lowest SOC compared to other collision-free solutions.

Theorem 1. The S-MAPF problem is NP-hard to solve optimally.

Theorem 1 can be proven by reduction, and the details are provided in the Supplementary Material.

4 Agent StreamConflict-Based Search

We present a two-level algorithm, ASCBS, designed to solve the S-MAPF problem. The high-level solver creates a constraint tree (CT) to resolve conflicts from different or the same agent streams. The low-level solver uses the A* algorithm [Hart et al., 1968] to plan the shortest path for an individual agent stream.

4.1 High-Level Solver

The high-level solver uses CT to avoid conflicts. Each node in the CT stores the constraint set, the path of each agent stream, and the corresponding SOC.

The pseudocode of the high-level solver is presented in Algorithm 1. In lines 1 ∼ 4, the low-level solver is invoked at the root node to calculate the shortest path for each agent stream without considering the conflict. During each iteration, the algorithm obtains the CT node with the minimum cost (Line 9) and detects and selects the best conflict (Line 11). The algorithm detects vertex conflicts by Equations 1, 7, 3 and edge conflicts by Equations 4, 7, 6. The selection of the best conflicts is based on Prioritize Conflicts [Boyarski et al., 2015]. The prioritization process for cyclic vertex conflicts and cyclic edge conflicts is similar to that for the vertex child CT nodes are generated, each with one of the two additional constraints. The low-level solver is then utilized to determine the path for the newly constrained agent stream (Line 19). After constructing the child nodes, the algorithm proceeds to the next iteration.

We propose the cyclic vertex constraint and the cyclic edge constraint to resolve the conflict between different agent streams. The cyclic vertex constraint is denoted as (as, v, qr, qe), indicating that the agent stream as cannot occupy the vertex v at the q-th step if q satisfies the equations:

The cyclic edge constraint is denoted as (as, v, u, qr, qe), meaning that the agent stream as cannot go through the edge from v to u with the q-th step if q satisfies the equations:

Notably, qe in a cyclic vertex/edge constraint might be ∅, and in this case, Equations 10 and 12 are always satisfied.

Here we consider using the constraint to resolve the conflict between different agent streams. Recall that the cyclic vertex conflict ⟨asi, asj, qi, qj, v⟩ is caused by the qi-th step of the path of asi and the qj-th step of the path of asj . When replanning asi's path, it is not sufficient to just avoid asi occupying at vertex v at qj-th step to resolve the conflict at vertex v. This is because the conflict might also occur at v in the q-th step of asi's path where q ≡ qi (mod c), according to Equation 7. We should add constraints on all the q-th steps that satisfy q ≡ qi (mod c). It is symmetric for asj. Specifically, the two child CT nodes are generated respectively as follows to resolve the cyclic vertex conflict ⟨asi, asj , qi, qj , v⟩ where asi ̸= asj :

• Add the cyclic vertex constraint (asi, v, qi, ∅) to the constraint set and replan the path of asi.
• Add the cyclic vertex constraint (asj, v, qj, ∅) to the constraint set and replan the path of asj .

Similarly, to resolve the cyclic edge conflict ⟨asi, asj, qi, qj, vi, vj⟩ where asi ̸= asj, the two child CT nodes are operated respectively as follows:

• Add the cyclic edge constraint (asi, vi, vj, qi, ∅) to the constraint set and replan the path of asi.
• Add the cyclic edge constraint (asj, vj, vi, qj, ∅) to the constraint set and replan the path of asj .

However, when a conflict arises within the same agent stream, we cannot adopt a similar strategy to resolve the conflict using cyclic vertex/edge constraints. This is because the strategy cannot preserve the completeness of the algorithm, as discussed in the Technical Appendix. Instead, we resolve the conflict through the vertex constraint and the edge constraint. The notation (as, v, q) represents the vertex constraint, indicating that the agent stream as cannot be located at the vertex v at the q-th step. Similarly, the notation (as, v, u, q) denotes the edge constraint, which means that the agent stream as cannot go through the edge from the vertex v to the vertex u in the q-th step. To resolve the cyclic vertex conflict ⟨asi, asj , qi, qj , v⟩ where asi = asj , two child CT nodes are generated:

• Add the vertex constraint (asi, v, qi) to the constraint set and replan the path of asi.
• Add the vertex constraint (asi, v, qj) to the constraint set and replan the path of asi.

The two child CT nodes are generated to resolve the cyclic edge conflict ⟨asi, asj , qi, qj , vi, vj ⟩ where asi = asj .

• Add the edge constraint (asi, vi, vj, qi) to the constraint set and replan the path of asi.
• Add the edge constraint (asi, vj, vi, qj) to the constraint set and replan the path of asi.

4.2 Low-Level Solver

The low-level solver of ASCBS uses an A* algorithm to compute the optimal path of an agent stream under constraints. It is similar to the low-level solver of CBS, where the search progressively explores nodes until reaching the goal vertex. A key distinction is that the ASCBS algorithm's low-level search additionally considers cyclic vertex/edge constraints instead of only vertex/edge constraints. In addition, the Conflict Avoidance Table (CAT) [Sharon et al., 2015] is employed to help break ties by favoring nodes with fewer conflicts with other agent streams when their f values are equal. Specifically, the nodes use a designated variable to mark the number of collisions along the path from the start vertex to the current vertex. The conflicts with other agent streams at the current step are checked by Equations 1, 4, 7. Notably, conflicts within the same agent stream are not counted because it needs to construct the entire path from the start vertex to the current vertex, significantly increasing the runtime.

There is an alternative implementation in that the lowlevel solver uses the Iterative-Deepening-A* (IDA*) algorithm [Korf, 1985] to generate the path. The IDA* algorithm utilizes a depth-first search approach, which allows it to maintain the entire path to the current search state. This capability enables the pruning of states when a cyclic vertex/edge conflict arises from the same agent stream during the search. Consequently, the IDA* algorithm can ensure that no collision exists from the same agent stream in the result path. As a result, the high-level solver only needs to resolve the conflict between agents of different agent streams when adopting the IDA* algorithm as the low-level solver. In contrast, the A* algorithm is unable to prune states with a cyclic vertex/edge conflict during the search because it does not maintain the entire path at every state. Such conflicts can only be resolved by the high-level solver.

4.3 Disjoint Splitting

Referencing the improvement technique of the CBS algorithm, we consider adopting the disjoint splitting strategy [Li et al., 2019b] into the ASCBS algorithm. This strategy involves applying asymmetric constraints to two child CT nodes to divide the problem into two separate subproblems, which helps prevent redundant searches.

In this context, (as, v, q) represents a positive vertex constraint, indicating that the agent stream as must be placed at the vertex v in the q-th step. Similarly, (as, v, u, q) denotes a positive edge constraint, indicating that the agent stream as must pass through the edge from vertex v to vertex u at the q-th step. The positive vertex/edge constraint can impact other agent streams' paths as well as other steps of the current agent stream's path. For example, when (asi, v, qi) is added into the constraint set, it restricts another agent stream asj from being at the vertex v in the qj-th step, where tsi + qi ≡ tsj + qj (mod c). Furthermore, the path of asi cannot be at vertex v at qi ′ -th step where qi ≡ qi ′ (mod c) and qi ̸= qi ′ .

Specifically, the two child CT nodes are generated to resolve the cyclic vertex conflict ⟨asi, asj , qi, qj , v⟩. Let k represent the agent stream ID for the positive constraint. Let k′ denote the ID of the newly constrained agent stream in the other child CT node. Formally, If asi ̸= asj, then k′ = {i, j}\k; otherwise, k′ = k.

• Add the positive vertex constraint (ask, v, qk), the cyclic vertex constraints (ask, v, qk, qk) and {(aso, v, tsk + qk - tso , ∅) : o ̸= k} to the constraint set and replan the path of as′k .
• Add the vertex constraint (ask, v, qk) to the constraint set and replan the path of ask.

To resolve the cyclic edge conflict ⟨asi, asj, qi, qj, vi, vj⟩, two child CT nodes are generated.

• Add the positive edge constraint (ask, vi, vj, qk), the cyclic edge constraints (ask, vj, vi, qk, qk) and {(aso, vj , vi, tsk + qk - tso , ∅) : o ̸= k} to the constraint set and replan the path of as′k .
• Add edge constraint (ask, vi, vj , qk) to the constraint set and replan the path of ask.

For the selection of k, we randomly choose k from {i, j} if asi ̸= asj. Otherwise, k ← argmino∈{i,j}(qo), where the motivation is that the later step of the path depends on the earlier step of the same path, and it is unreasonable to keep still the agent stream in the later step while altering it in the earlier step.

4.4 Theoretical Analysis

Based on the implementation of the ASCBS, the following theorem holds:

Theorem 2. The ASCBS algorithm that employs A* as the low-level solver is an optimal and complete solution for the S-MAPF problem.

The proof of Theorem 2 is provided in the Supplementary Material.

5 Experiment

This section presents experiments conducted to evaluate the computational efficiency and solution quality of the ASCBS on three grid-like graphs selected from the MAPF Benchmark Set [Stern et al., 2019], with varying scaling and features. The three chosen graphs are 'empty-8-8' (size: 8 ×

8), 'random-64-64-10' (size: 64 × 64), and 'Paris 1 256' (size: 256 × 256). Each graph includes 25 scenario files that specify the start and goal points of the agents. For every scenario, 4 instances are generated with a randomly assigned initial start time for each agent streamwithin the range of [0, c - 1] for the setting of circle time c and agent number n, resulting in a total of 100 instances for each setting. All experiments are performed on a Ubuntu 20.04 computer equipped with an Intel Core i7-8700 CPU running at 3.2 GHz with 32GB of main memory. The code is publicly available at https://github.com/tangmingkai/S-MAPF.

The following algorithms are used in the experiments:

• ASCBS-A-ND: ASCBS with A* as the low-level solver and without the disjoint splitting strategy.
• ASCBS-A-D: ASCBS with A* as the low-level solver and adopting the disjoint splitting strategy.
• ASCBS-IDA-ND: ASCBS with IDA* as the low-level solver and without the disjoint splitting strategy.
• ASCBS-IDA-D: ASCBS with IDA* as the low-level solver and adopting the disjoint splitting strategy.
• CBS: The conflict-based search with WDG guidance [Li et al., 2019a] and mutex reasoning [Zhang et al., 2022], with the setting that agents disappear upon reaching their goals. It is the solver for the traditional MAPF problem, but ignore the assumption that agents in the same agent streammust share the same action sequence.

5.1 Various Number of Agent Streams

We assessed the computational efficiency of the different implementations of ASCBS on the instances with varying numbers of agent streams, where the circle time is set at 3. The average running time and the success rate are used as evaluation metrics. An instance is considered unsuccessful if the running time exceeds 60 seconds, in which case the running time is set at 60 seconds directly.

The results are presented in Figure 3. The performance of ASCBS-A-ND and ASCBS-A-D surpasses that of ASCBSIDA-ND and ASCBS-IDA-D. This difference in performance arises because the IDA* algorithm repeatedly executes the search from the start vertex of an agent stream whenever the bound of the f-value increases. The overhead associated with using the IDA* algorithm as the low-level solver outweighs its advantage, which is that the high-level solver does not need to resolve conflicts from the same agent stream. This finding suggests that resolving conflicts from the same agent streams at the high-level solver is more efficient than resolving them at the low-level solver. In the empty-8-8 and random-64-64-10, ASCBS-A-D outperforms ASCBS-A-ND, with the gap more pronounced in smaller maps. In contrast, on the larger map (Paris 1 256), ASCBS-A-ND outperforms ASCBS-A-D. We believe that the reason is as follows. On the one hand, the strategy that imposes a larger additional constraint set on child CT nodes has a higher efficiency because it is more likely to elevate the lower bound of the optimal SOC of the CT node. A cyclic vertex/edge constraint on the agent stream with path length l and cycle time c can be extracted to approximately ⌊ lc ⌋ vertex/edge constraint. In the solver with the disjoint splitting strategy, one of the child CT nodes has an additional constraint set that only contains a vertex/edge constraint, which is smaller than that in the solver without disjoint splitting. This makes the non-disjoint splitting strategy more beneficial than the disjoint splitting strategy in terms of computational efficiency. Consequently, the advantage caused by non-disjoint splitting diminishes in a smaller size map due to the shorter path length l, resulting in a smaller value ⌊ lc ⌋. On the other hand, the disjoint splitting prevents the same conflict recurrence in the subtree rooted by two child CT nodes. In this view, the disjoint splitting strategy is more beneficial than the non-disjoint splitting strategy. Considering the above two factors, when the map size is small, the advantage caused by the disjoint splitting from the solver with A* search is larger than the disadvantage. Nonetheless, ASCBS-IDA-D is outperformed by ASCBS-IDA-ND, as the computing time of IDA* constitutes a significant portion of the total computing time and is heavily influenced by constraints. Therefore, the advantage of the disjoint splitting strategy in the solver with IDA* cannot cover the disadvantage.

5.2 Comparing ASCBS with CBS

We evaluate the computational efficiency and quality of the solution of ASCBS-A-ND compared to CBS. Since CBS is unable to generate solutions for unlimited working hours, we introduce an integer variable called the time horizon. This variable restricts CBS to considering only the agents whose start time is less than or equal to the time horizon. Our evaluation includes instances with 10 agent streams and circle time 3. We measure computational efficiency using average running time. We named the instance feasible by the algorithm if its running time is within 60 seconds and can produce a feasible solution. To evaluate solution quality, we calculate the average relative error of the SOC among instances feasible by both algorithms. Notably, the traditional MAPF problem has less constraint than the S-MAPF problem, resulting in a no larger SOC in CBS than in ASCBS.

Figure 4 displays the average running time of ASCBS and CBS, the number of instances feasible by both algorithms and the average relative error of ASCBS compared to CBS. It is noteworthy that the solution of ASCBS can be applied across all time horizons, leading to consistent average running times. As the time horizon increases, CBS's running time scales due to the larger number of agents considered. In contrast, the relative error of ASCBS compared to CBS is very small and decreases as the time horizon grows. This trend suggests that when the working hours are extended, the difference in solution quality between ASCBS and CBS diminishes, supporting the assumption that ASCBS is more suitable to apply in the scenario with long working hours compared to CBS.

6 Extensions

The formalization of the S-MAPF problem is based on several strong assumptions. In this section, we introduce extensions of the S-MAPF problem to relax these assumptions. It is evident that the solver for the basic S-MAPF problem can be adapted to solve the extended problem. We denote the basic S-MAPF problem as P 1.

6.1 Stay in the Environment

The S-MAPF problem assumes that agents in the agent stream appear at the starting vertex at specific time steps and disappear upon reaching the goal vertex. This assumption is suitable for the intersection scenarios and the environments that have some private parking zones at both the start and goal vertices for robot loading and unloading [ˇSvancara et al., 2019]. An extension of the S-MAPF problem (denoted as P2) relaxes this assumption, by requiring all agents to remain in the environment throughout the entire working process.

Several methods can be employed to solve the extended problem. One method is to generate a return path for each agent stream, dividing the P2 into two stages. In the first stage, a path is generated for each agent stream from its start vertex to its goal vertex, similar to P1. The second stage focuses on generating a path for each agent stream from the goal vertex back to the start vertex, ensuring that this path avoids conflicts with the paths established in the first stage. Additionally, the path length in the second stage must adhere to a specific constraint to maintain the cyclic pattern. Let li1 and li2 represent the length of the path generated in the first and second stages for agent stream i, receptively. These path lengths must satisfy the condition ∀i, li1 +li2 ≡ 0 (mod c). In the implementation, the ASCBS algorithm can enhance the goal-reaching conditions in the low-level solver to ensure that this condition is met.

An alternative method for the P2 is to jointly generate the paths in both stages, ensuring that the path lengths are multiples of c. This can be achieved by employing a multi-label A* algorithm [Grenouilleau et al., 2019] as the low-level solver within the ASCBS algorithm.

A more advanced method for the P2 is to allow for the concentration of multiple agent streams. In this method, an agent that has reached the goal vertex of an agent stream can subsequently move to the start vertex of another agent stream. Future research will focus on this category of methods.

6.2 Non-UniformCycle Time

In the context of P1, we assume that all agent streams operate on the same cycle time. This assumption restricts the applicability of the S-MAPF problem to scenarios that require non-uniform cycle times. In the case of the problemwith nonuniform cycle time agent streams (denoted as P3), conflicts also display in a periodic pattern, similar to that observed in P 1. Consequently, we can extend the definition of cyclic conflict and constraints of the ASCBS algorithm to accommodate non-uniform cycle times. Further details are available in the Supplementary Material.

7 Conclusion

This work formalized the S-MAPF problem, which assumes that agents in the same agent stream have a periodic start time and use the same action sequence. To solve the SMAPF problem, an optimal and complete algorithm, ASCBS, was introduced, which includes cyclic vertex/edge constraints. The potential of the disjoint splitting strategy in the ASCBS algorithm was also investigated. Experimental comparisons were conducted to evaluate the performance of different implementations of ASCBS, indicating that resolving conflicts within the same agent stream in the high-level solver is more effective than in the low-level solver, and disjoint splitting is advantageous when the map size is small. Moreover, experiments demonstrated that when the working hour is long, ASCBS outperforms CBS in terms of runtime while maintaining a slightly lower or equal solution quality. Finally, we presented several extensions of the S-MAPF problem. The solver developed for the basic S-MAPF problem can be adapted to solve these extended problems.