# periodic_multiagent_path_planning__2129325f.pdf

Periodic Multi-Agent Path Planning

Kazumi Kasaura, Ryo Yonetani, Mai Nishimura

OMRON SINIC X Corporation Hongo 5-24-5, Bunkyo-ku, Tokyo, Japan kazumi.kasaura@sinicx.com, ryo.yonetani@sinicx.com, mai.nishimura@sinicx.com

Multi-agent path planning (MAPP) is the problem of planning collision-free trajectories from start to goal locations for a team of agents. This work explores a relatively unexplored setting of MAPP where streams of agents have to go through the starts and goals with high throughput. We tackle this problem by formulating a new variant of MAPP called periodic MAPP in which the timing of agent appearances is periodic. The objective with periodic MAPP is to find a periodic plan, a set of collision-free trajectories that the agent streams can use repeatedly over periods, with periods that are as small as possible. To meet this objective, we propose a solution method that is based on constraint relaxation and optimization. We show that the periodic plans once found can be used for a more practical case in which agents in a stream can appear at random times. We confirm the effectiveness of our method compared with baseline methods in terms of throughput in several scenarios that abstract autonomous intersection management tasks.

Introduction Multi-agent path planning (MAPP) refers to the problem of finding a set of collision-free trajectories from start to goal locations for a team of multiple agents. MAPP, specifically multi-agent pathfinding (MAPF) that searches for a solution on a given graph, is a fundamental problem in multi-agent systems (Stern et al. 2019). We are particularly interested in the relatively unexplored problem of MAPP in which, rather than a single agent, a stream of agents enters each start location and leaves the environment upon reaching the goal. Instead of finding a set of feasible trajectories with a small total cost, we aim to improve the throughput for agent streams passing through the environment. Such settings would be beneficial for several practical applications, such as autonomous intersection management (AIM) (Dresner and Stone 2008) and automated warehouses (Wurman, D Andrea, and Mountz 2008). Handling agent streams in such a problem setting poses a nontrivial technical challenge. As the throughput increases, the environment would be filled with a large number of agents, making it difficult to use optimal planning algorithms with limited scalability (e.g., conflict-based

Copyright 2023, Association for the Advancement of Artificial Intelligence (www.aaai.org). All rights reserved.

search (Sharon et al. 2015)). It is also not obvious if the high throughput can be maintained with scalable planners that nevertheless have to determine agent trajectories adaptively in sequence (e.g., prioritized planning (Silver 2005)). Furthermore, finding collision-free trajectories in highlycrowded environments would require consideration of planning in the continuous space (i.e., not grid maps) and with continuous time (i.e., allowing agents to start and stop at an arbitrary timing in a continuous timeline). However, such continuous setups are generally challenging and there are few established approaches (Andreychuk et al. 2021, 2022; Kasaura, Nishimura, and Yonetani 2022). In this work, we start by formulating a bit simplified but new variant of MAPP called periodic multi-agent path planning (periodic MAPP) in which the timing of agent appearances is periodic. The objective with periodic MAPP is to find a periodic plan, i.e., a set of collision-free trajectories that streams of agents can use repeatedly over periods. By finding such plans with periods that are as small as possible, we are able to improve the throughput of agent streams. Importantly, periodic plans once found can be easily used for solving a more practical problem called online MAPP, a variant of online MAPF (ˇSvancara et al. 2019) in which a stream of agents can appear at random times but can also wait until the subsequent agents enter the environment. We develop a constraint-relaxation and optimization method as a solution method to periodic MAPP. With this method, we first generate an initial periodic plan under relaxed constraints about the physical size of agents with an arbitrarily large period they appear. We then solve a continuous optimization problem to improve the initial plan such that the agent size matches the original one and the period becomes as small as possible. Therefore, our method can find a collision-free and repeatable plan while minimizing the period. We provide insights into the topological aspect of solutions obtained with the proposed method. We evaluated the effectiveness of our method on several scenarios of abstracting AIM tasks, in which the goal is to move vehicles appearing at intersections to the other side without collision. Unlike existing methods that require planning or re-planning for every appearance of a new vehicle, the proposed method using periodic plans does not necessitate communications with other vehicles to retrieve their current locations or to update their trajectories. Nev-

The Thirty-Seventh AAAI Conference on Artificial Intelligence (AAAI-23)

Figure 1: Example of periodic MAPP problem with N = 2 (left) and periodic plans with M = 1 (middle) and M = 2 (right). Solid lines show trajectories. Numbered circles indicate where agents are at each elapsed period after their appearance.

ertheless, the solutions derived from the proposed method are comparably good or sometimes even better in terms of the throughput, compared with those from baseline methods that combine online MAPP algorithms (ˇSvancara et al. 2019) and MAPP algorithms for continuous spaces and times (Andreychuk et al. 2022, 2021; Kasaura, Nishimura, and Yonetani 2022).

Periodic MAPP

Overview. We consider a two-dimensional (2D) environment with several pairs of start and goal locations. For each start location, a stream of agents appears periodically with a user-defined period (i.e., time interval). Each agent must move to its goal while avoiding collisions with the borders of the environment and other agents and disappear from the environment upon reaching the goal. We assume that there exists a certain cycle, the number of periods within which we can find a periodic plan (i.e., a set of collision-free trajectories that can be used periodically over cycles). Therefore, a periodic plan may span multiple periods as collision-free trajectories for agents appearing at the same locations that are not necessarily the same across periods (see agents shown in red/orange or those in blue/cyan in Fig. 1.) Informally, the objective with periodic MAPP is to find such periodic plans for a given cycle with periods that are as small as possible. In other words, we wish to produce a high throughput plan that enables us to move agents from their respective start to the goal even if they appear in rapid succession. Note that, if the non-periodic version of a given problem instance (i.e., standard MAPP with a single agent appearing from each start) has a solution, the problem instance has a periodic plan for any cycle with the period given by the arrival time of the last agent. For simplicity, we assume that all agents have bodies modeled by circles with the same fixed radius and follow a simple kinodynamic constraint in which the velocity cannot exceed a certain maximum limit.

Problem instances. Formally, we model a problem instance of periodic MAPP by a tuple (E, {(s1, g1), . . . , (s N, g N)}, r, vmax), where E R2 is a set of valid states in the 2D environment. The set {(s1, g1), . . . , (s N, g N)}, where sn, gn E, describes N pairs of start and goal locations for agent streams. The variables r and vmax are the radius and maximum velocity

of each agent, respectively.

Periodic plans. We refer to a period as τ R+, a time interval with which a new set of agents can appear at respective start locations s1, . . . , s N. While denoting cycle as M N+, we describe a periodic plan with M periods by a set of M N trajectories ΓM = (γn,m : [0, Tn,m] E)1 n N,0 m<M. The periodic plan should satisfy the following conditions: (Start and goal locations) For all 1 n N, 0 m < M, γn,m(0) = sn, and γn,m(Tn,m) = gn. (Maximum velocity) For all 1 n N, 0 m < M, and t [0, Tn,m], the velocity of agents satisfies dγn,m

dt (t) vmax. (1)

(Clearance from boundaries) Let dist E(x) be the distance of x E from the boundary of E. Then, for all 1 n N, 0 m < M, and t [0, Tn,m],

dist E(γn,m(t)) r. (2)

(Collision-free)1 For all 1 n, n N, 0 m, m < M, and t [0, Tn,m], t [0, Tn ,m ] such that (m m )τ + (t t ) MτZ and (n, m, t) = (n , m , t ),

|γn,m(t) γn ,m (t )| 2r. (3)

Objective of periodic MAPP. Given a problem instance (E, {(s1, g1), . . . , (s N, g N)}, r, vmax) and a cycle M, our objective is to find periodic plans ΓM with periods τ that are as small as possible.

Solution Method In this section, we explain the proposed solution method for producing periodic plans for periodic MAPP. Specifically, we use a two-step approach that first derives initial solution trajectories for a relaxed problem that ignores the constraints about r and the objective for τ. We then optimize them by solving a continuous optimization problem to satisfy all the original conditions and improve the solution quality with respect to τ. This is a reasonable approach to derive solution trajectories in a continuous space and time setup while aiming to minimize the continuous period value that affects the solution.

Trajectory Representation We represent each trajectory γn,m by a sequence of K + 1 timed locations with a timestep tn,m, i.e., ((xn,m,0, 0), (xn,m,1, tn,m), . . . , (xn,m,K, K tn,m)) where xn,m,k E, xn,m,0 = sn, xn,m,K = gn, and K tn,m = Tn,m. Agents are assumed to move between

1The agent appearing at sn at time (a M +m)τ follows the trajectory γn,m for any a Z. Since there exists an agent at γn,m(t) when the time is . . . , ( 2M + m)pτ + t, ( M + m)τ + t, mτ + t, (M + m)τ + t, (2M + m)τ + t, . . ., there exist two agents at γn,m(t) and γn ,m (t ) at the same time if (m m )τ +(t t ) MτZ, except when (n, m, t) = (n , m , t ). To avoid a collision between them, their distance must be at least 2r.

two locations xn,m,k, xn,m,k+1 in a straight line with constant velocity. This discretized representation should also satisfy the maximum velocity condition in Eq. (1) that is rewritten as

vn,m,k := xn,m,k+1 xn,m,k

and that for the clearance from boundaries in Eq. (2):

dist E(xn,m,k) r. (5)

Note that satisfying the collision-free condition in Eq. (3) is a bit non-trivial. Let us define

rq(t) := t t

C := {(n, m, k, n , m , k )|

1 n, n N, 0 m, m < M, 0 k, k < K,

0 r Mτ((m m )τ + k tn,m k tn ,m ) < tn ,m ,

(n, m, k) = (n , m , k ).}. (7)

Then, the collision-free condition is rewritten as, for all (n, m, k, n , m , k ) C,

dn,m,k,n ,m ,k := |xn,m,k ((1 α)xn ,m ,k + αxn ,m ,k +1)| 2r, (8)

α = r Mτ((m m )τ + k tn,m k tn ,m )

tn ,m . (9)

Note that by setting t = k tn,m, t = (k + α) tn ,m , the inequality in Eq. (8) reduces to the original one of Eq. (3).

Optimization

Initial periodic plans. We first create an initial periodic plan while setting r smaller than that of the original condition and τ large enough. This makes it easy to find feasible trajectories that satisfy the above conditions. Concrete algorithms used to produce such plans depend on task setups, which we present in Appendix B.

Objective. Given an initial periodic plan for ΓM = (γn,m)1 n N,0 m<M, we optimize it with respect to r, τ, and each trajectory γn,m to satisfy the original conditions. We denote the original agent radius as r0. By imposing the cost to violate the original conditions, solving periodic MAPP reduces to a continuous optimization problem with the following objective:

V (τ, r, ΓM) := τ 2r vmax

n,m,k v2 n,m,k+c(τ, r, ΓM),

c(τ, r,ΓM) := σr(r r0)2

n,m,k (max {0, vn,m,k vmax})2

max 0, dist E(xn,m,k) 1 r 1 2

max n 0, d 1 n,m,k,n ,m ,k (2r) 1o 2 ,

where σt, σr, σv, σo and σc are constants. With this objective, we aim to decrease τ to the minimum 2r/vmax where two agents are adjacent to each other. We also impose costs of trajectories defined by the sums of the squares of velocity to prevent vanishing of the gradients on the trajectories.

Optimization method. We solve this optimization problem by using the Levenberg-Marquardt algorithm (Levenberg 1944; Marquardt 1963). To force solutions to strictly satisfy the original conditions, we make the constants σr, σv, σp, σc gradually increase to become large enough during the optimization. We also gradually decrease σt up to zero because the corresponding velocity term is necessary only for preventing vanishing gradients and is not included in the original conditions.

Topological Remark The quality of final solutions is dependent on initial periodic plans, while some initial plans will result in the same optimization results. One considerable feature of solutions is their equivalent classes with respect to continuous deformation, including optimizations, from topological perspectives. To analyze this, we introduce an additional constraint in which no agents can pass through any start and goal locations, including those of themselves, instead of considering the conditions of the velocity and size of agents. This is necessary to ensure sufficiently different plans to be distinct enough in terms of their homotopy class. Let:

C := (E \ {s1, g1, . . . , s N, g N}) R/Z. (12)

A trajectory γn,m can be considered an embedding γn,m of an open interval (0, 1) to C:

γn,m(t Tn,m),

(13) where the overline means the equivalent class. Then, a periodic plan (γn,m)1 n N,0 m<M can be considered an embedding ( γn,m)1 n N,0 m<M of the disjoint union of N M open intervals (0, 1) to C, satisfying the following conditions for any 1 n N and 0 m < M:

limα 0 γn,m(α) = (sn, m/M) and limα 1 γn,m(α) = (gn, A) for some A R/Z. The second component of γn,m(α) is locally strictly increasing with respect to α.

Note that the collision-free condition can be interpreted as injectivity. Now, a set of plans that are equivalent with respect to continuous deformations is the set of homotopy classes of the embeddings that satisfy the above conditions, and the following proposition holds.

Proposition 1 When E is open and connected, the above set is independent of the positions of s1, g1, . . . , s N, g N.

For the proof, see Appendix A.

Application to Online MAPP

While it is assumed with periodic MAPP that the appearance timing of agents in a stream is periodic, the periodic plans once found can be used for solving a more practical problem called online MAPP, where agents appear at random times.

Online MAPP Problem

While sharing certain settings with periodic MAPP, the problem of online MAPP can be viewed as a variant of online MAPF (ˇSvancara et al. 2019) with the following features. Like periodic MAPP, there are several pairs of starts and goals in the environment through which streams of agents have to pass while avoiding collisions. Following online MAPF, we assume that agents can appear at random times but are also allowed to wait at their start locations in a finite or infinite queue until the subsequent agents enter the environment. This assumption is similar to the concept of garage (ˇSvancara et al. 2019) and realistic for practical applications such as AIM.

Proposed Method

Adopting periodic plans to agents with random timing of appearances is straightforward. We first divide a timeline into periods of the interval τ obtained with the periodic plan. We then allow at most one agent for each period to enter each start location and follow the corresponding trajectory. Therefore, agents can avoid collisions with other agents in the same stream. Formally, by using the notations of periodic MAPP introduced earlier, we say that an agent is assigned to the nth trajectory in the a-th period when it waits until time aτ and moves along γn,a a/M M. Let us denote as t, the time of appearance of a new agent at the start position sn. Let a := t/τ . If the n-th trajectory in the a-th period has not yet been assigned by any agent, the new agent will follow that trajectory. Otherwise, the agent will wait to follow the next trajectory in the a + 1-th period, where a is the order of the period assigned to the last agent that appeared at sn before t if the queue has a room. Note that if the length of the queue is finite and the number of currently waiting agents exceeds its limit, the planning for the new agent is considered a failure.

Queueing Theoretical Analysis

We theoretically analyze the waiting times of agents for the proposed method.

Assumptions. We assume that agents are managed by queues of infinite length. We also model time intervals of agent appearances as c + α, where c is a constant2 and α is a random variable drawn from the exponential distribution with a rate parameter λ. We also assume that all agents wait for (the maximum) time τ until they start moving. Note that this assumption corresponds to the deterministic service time in terms of the queueing theory (Kendall 1953) and is more conservative than in actuality.

Waiting time analysis. For theoretical analysis, we remove a constant term from the above model by subtracting c from time intervals between arrivals and service time temporarily. This operation does not change the number of agents in a queue but reduces waiting times for all the agents. The resulting model then reduces to the M/D/1 queue in terms of the queueing theory (Kendall 1953). By denoting the rate of arrivals as λ and the service time as D := τ c, and when ρ = Dλ < 1, the average waiting time is given as

W = D + ρ 2(1 ρ)D. (14)

Moreover, the probability that the waiting time exceeds a limit t decreases exponentially with respect to t (Erlang 1909). By again considering c we subtracted earlier, the average time now becomes

W = W + c = τ + λ(τ c)2

2(1 λ(τ c)). (15)

Experiments To evaluate the effectiveness of our method for first solving periodic MAPP then using periodic plans for online MAPP problems, we focus on scenarios of abstracting AIM tasks (Dresner and Stone 2008).

Experimental Setups Environments. Our AIM scenario involves a single intersection with several entrances and exits. Figure 2 shows the six environments used in the experiments. Each environment abstracts one of the typical situations of intersections with different sizes. The circles with letters s and g are the start and goal locations, respectively. Specifically, environment (a) is a crossing of two one-way roads, while environment (b) is a crossing of one-way and two-way roads. Environments (c) and (d) are modeling the crossing of two two-way roads of different sizes. Finally, environments (e) and (f) model the T-junction with different sizes. We also assume that each start location is equipped with a corridor , as illustrated in Fig. 4, which we can use as a queue (with unlimited or limited capacity) to keep agents waiting until entering the intersection. Agents (i.e., vehicles) are modeled by a circle and follow a simple holonomic kinodynamics model that enable them to move in any direction under a given maximum velocity. Trajectories for a new agent must be planned immediately once that agent appears in the environment. Nevertheless, it is possible to replan trajectories

2We add c to account for the time margin needed to avoid collisions between agents.

2.5 0.0 2.5 2

4 2 0 2 4 4

4 2 0 2 4 4

Figure 2: Environments that abstract AIM tasks. Letters s and g indicate start and goal locations, respectively.

2.5 0.0 2.5 2

4 2 0 2 4 4

4 2 0 2 4 4

Figure 3: Optimized periodic plans for each environment with best M. Best viewed in videos in the Appendix.

Figure 4: Environment (a) with corridors used as queues for five agents.

for some agents that have already been moving in the environment to take into account the new agent.

Parameters. We evaluated two different configurations for the queues: unlimited or limited capacity with five agents at most. The time interval between agent appearances is modeled as 1.0 + α, where α follows the exponential distribution with a rate parameter λ. We sampled appearance times until the last time reached 1000 for infinite queues and 100 for finite queues. For each environment and each λ [0.25, 0.5, 0.75, . . . , 2.5], we generated 10 different problem instances. Throughout the experiment, r and vmax were respectively fixed to 0.5 and 1.0.

Evaluation metrics. The quality of plans is measured by the following two metrics.

Throughput measured as the number of agents entering the environment in unit time. Average delay calculated as the incremental travel time compared with the shortest possible trajectory averaged over agents. Note that this metric includes the time for

the agent waiting in a queue.

Initial Periodic Plans With periodic MAPP, we generated and evaluated three periodic plans for each problem instance with cycles M {1, 2, 3}. We constructed the plans by carefully designing the order of passing at intersection points such that, after M agents of one direction pass at the intersection, M agents of another direction pass alternately. Formally, the initial plan for M was created on the basis of the following rules:

Let πn be the shortest path connecting sn and gn. Each agent appearing at sn follows πn, while adjusting its velocity to satisfy the next condition. Let two paths πn and πn intersect at point p. We assume that the length of the part of πn from sn to p is shorter than that of the part of πn from sn to p (and assume i < i if they are equal). Then, for any a Z, M agents appearing at sn at time a Mτ, (a M + 1)τ, . . . , (a M + M 1)τ must pass p at the time between times when agents appearing at sn at (a M 1)τ and at a Mτ pass p. The differences between times when two agents pass are set to be not smaller than 1.0 to prevent optimization failures.

Note that such initial plans can always be constructed as long as the initial τ is taken to be large and r is small enough. See Appendix B for details of the generation algorithm.

Baseline Methods Because the same problem setup (i.e., improving throughput of agent streams for MAPP in continuous space and time) has not been explicitly addressed, we developed two baseline methods called first-come and first-serve (FCFS) and snapshot optimal (SO), which combine general strategies of online MAPF (ˇSvancara et al. 2019) and the state-of-the-art

Environment M (a) (b) (c) (d) (e) (f)

1 2.03 2.08 2.45 2.44 2.34 2.13

2 1.27 1.54 1.87 1.86 3.02 1.86

3 1.56 1.45 1.86 1.63 3.04 3.54

Table 1: Periods for optimized periodic plans with different cycle M

MAPP algorithms in continuous space and time (Andreychuk et al. 2022; Kasaura, Nishimura, and Yonetani 2022). For both baselines, we first used probabilistic roadmap with the fixed number of neighbors (k-PRM) (Karaman and Frazzoli 2011) as a standard approach to approximate the continuous space into a roadmap and find collision-free paths on the constructed roadmap. Implementation details are presented in Appendix C. FCFS: This baseline incrementally plans a collision-free trajectory for every new agent that appears while regarding trajectories of other agents already present in the environment as space-time obstacles. This is a natural application of prioritized planning (Silver 2005) for the replan single strategy introduced in the context of online MAPF (ˇSvancara et al. 2019). Specifically, we used prioritized safe-interval path planning (Kasaura, Nishimura, and Yonetani 2022) to handle continuous space and time. SO: By contrast, this baseline uses the replan all strategy (ˇSvancara et al. 2019) and finds the optimal solution using continuous conflict-based search (Andreychuk et al. 2022) for all the agents presenting in the environment each time a new agent appears.

Results Optimization results. Table 1 shows the periods of optimized plans for cycle M = 1, 2, 3 and Fig. 3 illustrates the optimized periodic plans with the best choice of M. We would like to emphasize that this optimization is required only once for each combination of environments and M. Unlike the other baselines, our method can be used without requiring agents to communicate with other agents to retrieve their current locations or replanning to adjust their trajectories for each appearance of new agents.

Case I: Infinite queues. Figures 5 and 6 respectively show the changes in throughput and average delays with respect to λ when the capacity of queues is infinite. With the exception of the environment (e), our method, especially for M = 2 or M = 3, consistently outperformed FCFS as λ became higher. Note that it was not possible to use SO because the number of agents present in the environment could quickly become very large. We observed that the limited performance of the proposed method for (e) is possibly due to the difficulty of finding enough room for periodic intersections in the environment.

Case II: Finite queues. We set the length of queues to be five. Note that planning for a new agent is regarded as

FCFS M=1 M=2 M=3

Figure 5: Throughput with respect to λ for infinite queues (bars represent standard derivations)

FCFS M=1 M=2 M=3

Figure 6: Average delay with respect to λ for infinite queues (bars represent standard derivations)

failed if the number of agents waiting to enter their starts exceeded the length of queues or when the planning time exceeds a predefined limit (1.0 s). Agents resulting in such planning failures are discarded and degrade throughput. Figures 7 and 8 respectively show the throughput and average delays changing with respect to λ. Regarding throughput, our method for M = 2 and M = 3 performed better than FCFS and clearly outperformed SO, except for environment (e). The performance of SO degraded mainly due to the planning failures. By contrast, our method showed limited performances in terms of average delays, indicating the limitation of our method that trajectories obtained using periodic plans would be relatively redundant compared with those from FCFS and SO.

Related Work MAPP and its variants. MAPP has historically been studied in the fields of artificial intelligence and robotics. Many studies have considered planning particularly in discrete spaces such as grid maps, which are often referred to as MAPF (e.g., Silver (2005); Sharon et al. (2015), and see Stern et al. (2019) for an extensive survey.) There are a number of variants of MAPF problems, such as Anonymous MAPF (i.e., no correspondences between starts and goals) (Kloder and Hutchinson 2006; Yu and La Valle

FCFS SO M=1 M=2 M=3

Figure 7: Throughput with respect to λ for finite queues (bars represent standard derivations)

FCFS SO M=1 M=2 M=3

Figure 8: Average delay with respect to λ for finite queues, (bars represent standard derivations)

2013), MAPF with kinodynamic constraints (H onig et al. 2018; Walker, Sturtevant, and Felner 2018a), and online MAPF (ˇSvancara et al. 2019; Ma et al. 2017; Li et al. 2021), also known as lifelong MAPF. As summarized by Ma (2021), online MAPF is an online version of MAPF in which a team of agents is asked to solve a stream of tasks. Agents are assigned a new task whenever they appear in the environment (ˇSvancara et al. 2019) or upon reaching their goal (Ma et al. 2017). In contrast, periodic MAPP and our version of online MAPP are different in that streams of agents are asked to solve a certain task, with the unique objective that aims for high throughput. We introduced a challenging problem setup that solves online MAPP in the continuous space and with continuous time. Studies on such continuous setups have significantly been limited compared with discrete cases (Walker, Sturtevant, and Felner 2018b; H onig et al. 2018; Andreychuk et al. 2021, 2022; Kasaura, Nishimura, and Yonetani 2022; Okumura et al. 2022).

Application to AIM. As reviewed by Stern et al. (2019); Ma (2021), AIM is a common application of online MAPF. Typical approaches include the first-come and firstserve for repeatedly determining trajectories for every new agent (Dresner and Stone 2008) and the application of optimal solvers for a set of all agents present at the mo-

ment (ˇSvancara et al. 2019), which we compared in our experiments. For a given trajectory (or simply lane), there are studies that used deep reinforcement learning to achieve an optimal policy for vehicle acceleration control (Kreidieh, Wu, and Bayen 2018; Jang et al. 2019; Cui et al. 2021).

Optimization for MAPP. Similar to this work, other studies uses continuous optimization of trajectories (i.e., trajectory deformation (Kurniawati and Fraichard 2007)), especially for single-agent cases. For example, the idea of avoiding collisions on the basis of the optimization has existed for a long time (Khatib 1986). Another widely used motivation for optimization is to take into account kinodynamic constraints, e.g., that in R osmann, Hoffmann, and Bertram (2017) for a single-agent case and that in H onig et al. (2018) for a multi-agent case. Our study is unique in that we optimized trajectories as well as the period for their repeated use.

Other related work. Finally, our study has several more connections to other prior works. Solving path planning while relaxing constraints is a technique for single-agent cases (Bonilla et al. 2015; Bonilla, Pallottino, and Bicchi 2017; Fusco, Kermorgant, and Martinet 2018). The homotopical aspect of path planning has been studied by Bhattacharya (2010) for single-agent and by Bhattacharya and Ghrist (2018) for multi-agent cases. However, these studies are not directly applicable to our problem setup due to the difficulty of considering collisions for agents appearing in a periodic fashion.

Conclusion We presented a new variant of MAPP called periodic MAPP in which a stream of agents can appear periodically at each start location and leave the environment once they arrive at the goal. We also proposed a solution method of periodic MAPP that generates a periodic plan, i.e., a set of collisionfree trajectories that can be used repeatedly over periods while maintaining high throughput. We showed that the periodic plans can further be used for solving the online MAPP problem in which agents in each stream appear at a random time, and demonstrated its effectiveness on scenarios of abstracting AIM tasks. Currently, our formulation of periodic MAPP as well as our solution method can cover only situations in which agents follow a simple kinodynamics model that takes into account only maximum velocity. Promising future work is to address more realistic kinodynamics of wheeled robots or drones. This would require extending an optimization technique for solution methods such as ones used to plan trajectories for swarms (H onig et al. 2018). Another interesting direction from an application perspective is to tackle a more challenging AIM task in which human-driven vehicles also exist. In such a case, it will be important to combine the proposed method with state-of-the-art AIM methods that can reactively control acceleration on a given trajectory (Kreidieh, Wu, and Bayen 2018; Jang et al. 2019; Cui et al. 2021).

References Andreychuk, A.; Yakovlev, K.; Boyarski, E.; and Stern, R. 2021. Improving continuous-time conflict based search. In AAAI Conference on Artificial Intelligence, volume 35, 11220 11227. Andreychuk, A.; Yakovlev, K.; Surynek, P.; Atzmon, D.; and Stern, R. 2022. Multi-agent pathfinding with continuous time. Artificial Intelligence, 103662. Bhattacharya, S. 2010. Search-based path planning with homotopy class constraints. In AAAI conference on artificial intelligence, volume 24, 1230 1237. Bhattacharya, S.; and Ghrist, R. 2018. Path homotopy invariants and their application to optimal trajectory planning. Annals of Mathematics and Artificial Intelligence, 84(3): 139 160. Bonilla, M.; Farnioli, E.; Pallottino, L.; and Bicchi, A. 2015. Sample-based motion planning for soft robot manipulators under task constraints. In IEEE International Conference on Robotics and Automation, 2522 2527. Bonilla, M.; Pallottino, L.; and Bicchi, A. 2017. Noninteracting constrained motion planning and control for robot manipulators. In IEEE International Conference on Robotics and Automation, 4038 4043. IEEE. Cui, J.; Macke, W.; Yedidsion, H.; Goyal, A.; Urieli, D.; and Stone, P. 2021. Scalable Multiagent Driving Policies for Reducing Traffic Congestion. In International Conference on Autonomous Agents and Multi Agent Systems. Dresner, K.; and Stone, P. 2008. A multiagent approach to autonomous intersection management. Journal of Artificial Intelligence Research, 31: 591 656. Erlang, A. K. 1909. The theory of probabilities and telephone conversations. Nyt Tidsskrift for Matematik B, 20: 33 39. Fusco, F.; Kermorgant, O.; and Martinet, P. 2018. Improving relaxation-based constrained path planning via quadratic programming. In International Conference on Intelligent Autonomous Systems, 15 26. Springer. H onig, W.; Preiss, J. A.; Kumar, T. S.; Sukhatme, G. S.; and Ayanian, N. 2018. Trajectory planning for quadrotor swarms. IEEE Transactions on Robotics, 34(4): 856 869. Jang, K.; Vinitsky, E.; Chalaki, B.; Remer, B.; Beaver, L.; Malikopoulos, A. A.; and Bayen, A. 2019. Simulation to Scaled City: Zero-Shot Policy Transfer for Traffic Control via Autonomous Vehicles. In ACM/IEEE International Conference on Cyber-Physical Systems, 291 300. Karaman, S.; and Frazzoli, E. 2011. Sampling-based algorithms for optimal motion planning. The International Journal of Robotics Research, 30(7): 846 894. Kasaura, K.; Nishimura, M.; and Yonetani, R. 2022. Prioritized safe interval path planning for multi-agent pathfinding with continuous time on 2D roadmaps. IEEE Robotics and Automation Letters, 7(4): 10494 10501. Kendall, D. G. 1953. Stochastic processes occurring in the theory of queues and their analysis by the method of the imbedded Markov chain. The Annals of Mathematical Statistics, 338 354.

Khatib, O. 1986. Real-time obstacle avoidance for manipulators and mobile robots. In Autonomous Robot Vehicles, 396 404. Springer. Kloder, S.; and Hutchinson, S. 2006. Path planning for permutation-invariant multirobot formations. IEEE Transactions on Robotics, 22(4): 650 665. Kreidieh, A. R.; Wu, C.; and Bayen, A. M. 2018. Dissipating stop-and-go waves in closed and open networks via deep reinforcement learning. In International Conference on Intelligent Transportation Systems, 1475 1480. Kurniawati, H.; and Fraichard, T. 2007. From path to trajectory deformation. Ph.D. thesis, INRIA. Levenberg, K. 1944. A method for the solution of certain non-linear problems in least squares. Quarterly of Applied Mathematics, 2(2): 164 168. Li, J.; Tinka, A.; Kiesel, S.; Durham, J. W.; Kumar, T. K. S.; and Koenig, S. 2021. Lifelong Multi-Agent Path Finding in Large-Scale Warehouses. In AAAI Conference on Artificial Intelligence. Ma, H. 2021. A Competitive Analysis of Online Multi Agent Path Finding. In International Conference on Automated Planning and Scheduling. Ma, H.; Li, J.; Kumar, T. S.; and Koenig, S. 2017. Lifelong multi-agent path finding for online pickup and delivery tasks. In Conference on Autonomous Agents and Multi Agent Systems, 837 845. Marquardt, D. W. 1963. An algorithm for least-squares estimation of nonlinear parameters. Journal of the society for Industrial and Applied Mathematics, 11(2): 431 441. Okumura, K.; Yonetani, R.; Nishimura, M.; and Kanezaki, A. 2022. CTRMs: Learning to construct cooperative timed roadmaps for multi-agent path planning in continuous spaces. In International Conference on Autonomous Agents and Multiagent Systems, 972 981. R osmann, C.; Hoffmann, F.; and Bertram, T. 2017. Kinodynamic trajectory optimization and control for car-like robots. In 2017 IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS), 5681 5686. IEEE. Sharon, G.; Stern, R.; Felner, A.; and Sturtevant, N. R. 2015. Conflict-based search for optimal multi-agent pathfinding. Artificial Intelligence, 219: 40 66. Silver, D. 2005. Cooperative pathfinding. In AAAI Conference on Artificial Intelligence and Interactive Digital Entertainment, volume 1, 117 122. Stern, R.; Sturtevant, N. R.; Felner, A.; Koenig, S.; Ma, H.; Walker, T. T.; Li, J.; Atzmon, D.; Cohen, L.; Kumar, T. S.; et al. 2019. Multi-agent pathfinding: Definitions, variants, and benchmarks. In Annual Symposium on Combinatorial Search, 151 158. ˇSvancara, J.; Vlk, M.; Stern, R.; Atzmon, D.; and Bart ak, R. 2019. Online multi-agent pathfinding. In AAAI Conference on Artificial Intelligence, volume 33, 7732 7739. Walker, T. T.; Sturtevant, N. R.; and Felner, A. 2018a. Extended Increasing Cost Tree Search for Non-Unit Cost Domains. In International Joint Conference on Artificial Intelligence, 534 540.

Walker, T. T.; Sturtevant, N. R.; and Felner, A. 2018b. Extended increasing cost tree search for non-unit cost domains. In International Joint Conference on Artificial Intelligence, 534 540. Wurman, P. R.; D Andrea, R.; and Mountz, M. 2008. Coordinating hundreds of cooperative, autonomous vehicles in warehouses. AI Magazine, 29(1): 9 9. Yu, J.; and La Valle, S. M. 2013. Multi-agent Path Planning and Network Flow. In Frazzoli, E.; Lozano-Perez, T.; Roy, N.; and Rus, D., eds., Algorithmic Foundations of Robotics X, 157 173.