# Periodic Multi-Agent Path Planning

Kazumi Kasaura, Ryo Yonetani, Mai Nishimura

###### Abstract

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 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 highly-crowded 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 (Švancara 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. Nevertheless, 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 (Švancara
et al. 2019) and MAPP algorithms for continuous spaces and times (Andreychuk
et al. 2022, 2021; Kasaura, Nishimura, and Yonetani 2022).

## Periodic MAPP

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.

##### 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
$(\mathcal{E},\\{(s_{1},g_{1}),\dots,(s_{N},g_{N})\\},r,v_{\mathrm{max}})$,
where $\mathcal{E}\subseteq\mathbb{R}^{2}$ is a set of valid states in the 2D
environment. The set $\\{(s_{1},g_{1}),\dots,(s_{N},g_{N})\\}$, where
$s_{n},g_{n}\in\mathcal{E}$, describes $N$ pairs of start and goal locations
for agent streams. The variables $r$ and $v_{\mathrm{max}}$ are the radius and
maximum velocity of each agent, respectively.

##### Periodic plans.

We refer to a _period_ as $\tau\in\mathbb{R}_{+}$, a time interval with which
a new set of agents can appear at respective start locations
$s_{1},\dots,s_{N}$. While denoting cycle as $M\in\mathbb{N}_{+}$, we describe
a _periodic plan with $M$ periods_ by a set of $M\times N$ trajectories
$\Gamma_{M}=(\gamma_{n,m}:[0,T_{n,m}]\rightarrow\mathcal{E})_{1\leq n\leq
N,0\leq m<M}$. The periodic plan should satisfy the following conditions:

  * •

(Start and goal locations) For all $1\leq n\leq N$, $0\leq m<M$,
$\gamma_{n,m}(0)=s_{n}$, and $\gamma_{n,m}(T_{n,m})=g_{n}$.

  * •

(Maximum velocity) For all $1\leq n\leq N$, $0\leq m<M$, and
$t\in[0,T_{n,m}]$, the velocity of agents satisfies

$\left|\frac{d\gamma_{n,m}}{dt}(t)\right|\leq v_{\mathrm{max}}.$ (1)

  * •

(Clearance from boundaries) Let $\mathrm{dist}_{\mathcal{E}}(x)$ be the
distance of $x\in\mathcal{E}$ from the boundary of $\mathcal{E}$. Then, for
all $1\leq n\leq N$, $0\leq m<M$, and $t\in[0,T_{n,m}]$,

$\mathrm{dist}_{\mathcal{E}}(\gamma_{n,m}(t))\geq r.$ (2)

  * •

(Collision-free)111The agent appearing at $s_{n}$ at time $(aM+m)\tau$ follows
the trajectory $\gamma_{n,m}$ for any $a\in\mathbb{Z}$. Since there exists an
agent at $\gamma_{n,m}(t)$ when the time is
$\ldots,(-2M+m)p\tau+t,(-M+m)\tau+t,m\tau+t,(M+m)\tau+t,(2M+m)\tau+t,\ldots$,
there exist two agents at $\gamma_{n,m}(t)$ and
$\gamma_{n^{\prime},m^{\prime}}(t^{\prime})$ at the same time if
$(m-m^{\prime})\tau+(t-t^{\prime})\in M\tau\mathbb{Z}$, except when
$(n,m,t)=(n^{\prime},m^{\prime},t^{\prime})$. To avoid a collision between
them, their distance must be at least $2r$. For all $1\leq n,n^{\prime}\leq
N$, $0\leq m,m^{\prime}<M$, and $t\in[0,T_{n,m}]$,
$t^{\prime}\in[0,T_{n^{\prime},m^{\prime}}]$ such that
$(m-m^{\prime})\tau+(t-t^{\prime})\in M\tau\mathbb{Z}$ and
$(n,m,t)\neq(n^{\prime},m^{\prime},t^{\prime})$,

$\left|\gamma_{n,m}(t)-\gamma_{n^{\prime},m^{\prime}}(t^{\prime})\right|\geq
2r.$ (3)

##### Objective of periodic MAPP.

Given a problem instance
$(\mathcal{E},\\{(s_{1},g_{1}),\dots,(s_{N},g_{N})\\},r,v_{\mathrm{max}})$ and
a cycle $M$, our objective is to find periodic plans $\Gamma_{M}$ with periods
$\tau$ 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 $\tau$. We then
optimize them by solving a continuous optimization problem to satisfy all the
original conditions and improve the solution quality with respect to $\tau$.
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 $\gamma_{n,m}$ by a sequence of $K+1$ timed
locations with a timestep $\Delta t_{n,m}$, i.e.,
$((x_{n,m,0},0),(x_{n,m,1},\Delta t_{n,m}),\ldots,(x_{n,m,K},K\Delta
t_{n,m}))$ where $x_{n,m,k}\in\mathcal{E}$, $x_{n,m,0}=s_{n}$,
$x_{n,m,K}=g_{n}$, and $K\Delta t_{n,m}=T_{n,m}$. Agents are assumed to move
between two locations $x_{n,m,k},x_{n,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

$v_{n,m,k}:=\left|\frac{x_{n,m,k+1}-x_{n,m,k}}{\Delta t_{n,m}}\right|\leq
v_{\mathrm{max}},$ (4)

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

$\mathrm{dist}_{\mathcal{E}}(x_{n,m,k})\geq r.$ (5)

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

$\mathrm{r}_{q}(t):=t-\left\lfloor\frac{t}{q}\right\rfloor q,$ (6)

and

$\begin{split}C:=\\{&(n,m,k,n^{\prime},m^{\prime},k^{\prime})|\\\ &1\leq
n,n^{\prime}\leq N,\;0\leq m,m^{\prime}<M,\;0\leq k,k^{\prime}<K,\\\
&0\leq\mathrm{r}_{M\tau}((m-m^{\prime})\tau+k\Delta t_{n,m}-k^{\prime}\Delta
t_{n^{\prime},m^{\prime}})<\Delta t_{n^{\prime},m^{\prime}},\\\
&(n,m,k)\neq(n^{\prime},m^{\prime},k^{\prime}).\\}.\end{split}$ (7)

Then, the collision-free condition is rewritten as, for all
$(n,m,k,n^{\prime},m^{\prime},k^{\prime})\in C$,

$\begin{split}d_{n,m,k,n^{\prime},m^{\prime},k^{\prime}}:=&\left|x_{n,m,k}-((1-\alpha)x_{n^{\prime},m^{\prime},k^{\prime}}+\alpha
x_{n^{\prime},m^{\prime},k^{\prime}+1})\right|\\\ \geq&2r,\end{split}$ (8)

where

$\alpha=\frac{\mathrm{r}_{M\tau}((m-m^{\prime})\tau+k\Delta
t_{n,m}-k^{\prime}\Delta t_{n^{\prime},m^{\prime}})}{\Delta
t_{n^{\prime},m^{\prime}}}.$ (9)

Note that by setting $t=k\Delta t_{n,m}$,
$t^{\prime}=(k^{\prime}+\alpha)\Delta t_{n^{\prime},m^{\prime}}$, 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 $\tau$ 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 $\Gamma_{M}=(\gamma_{n,m})_{1\leq n\leq
N,0\leq m<M}$, we optimize it with respect to $r$, $\tau$, and each trajectory
$\gamma_{n,m}$ to satisfy the original conditions. We denote the original
agent radius as $r_{0}$. By imposing the cost to violate the original
conditions, solving periodic MAPP reduces to a continuous optimization problem
with the following objective:

$V(\tau,r,\Gamma_{M}):=\left(\tau-\frac{2r}{v_{\mathrm{max}}}\right)^{2}+\frac{\sigma_{\mathrm{t}}}{K}\sum_{n,m,k}v_{n,m,k}^{2}+c(\tau,r,\Gamma_{M}),$
(10)

$\begin{split}c(\tau,r,&\Gamma_{M}):=\sigma_{\mathrm{r}}(r-r_{0})^{2}\\\
&+\frac{\sigma_{\mathrm{v}}}{K}\sum_{n,m,k}\left(\max\left\\{0,v_{n,m,k}-v_{\mathrm{max}}\right\\}\right)^{2}\\\
&+\frac{\sigma_{\mathrm{o}}}{K}\sum_{n,m,k}\left(\max\left\\{0,\mathrm{dist}_{\mathcal{E}}(x_{n,m,k})^{-1}-r^{-1}\right\\}\right)^{2}\\\
&+\frac{\sigma_{\mathrm{c}}}{K}\sum_{C}\left(\max\left\\{0,d_{n,m,k,n^{\prime},m^{\prime},k^{\prime}}^{-1}-(2r)^{-1}\right\\}\right)^{2},\end{split}$
(11)

where $\sigma_{\mathrm{t}}$, $\sigma_{\mathrm{r}}$, $\sigma_{\mathrm{v}}$,
$\sigma_{\mathrm{o}}$ and $\sigma_{\mathrm{c}}$ are constants. With this
objective, we aim to decrease $\tau$ to the minimum $2r/v_{\mathrm{max}}$
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
$\sigma_{\mathrm{r}},\sigma_{\mathrm{v}},\sigma_{\mathrm{p}},\sigma_{\mathrm{c}}$
gradually increase to become large enough during the optimization. We also
gradually decrease $\sigma_{\mathrm{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:

$\mathcal{C}:=(\mathcal{E}\setminus\\{s_{1},g_{1},\ldots,s_{N},g_{N}\\})\times\mathbb{R}/\mathbb{Z}.$
(12)

A trajectory $\gamma_{n,m}$ can be considered an embedding
$\tilde{\gamma}_{n,m}$ of an open interval $(0,1)$ to $\mathcal{C}$:

$(0,1)\ni\alpha\mapsto\left(\gamma_{n,m}(tT_{n,m}),\overline{\left(\frac{m\tau+\alpha
T_{n,m}}{M\tau}\right)}\right)\in\mathcal{C}.$ (13)

where the overline means the equivalent class. Then, a periodic plan
$(\gamma_{n,m})_{1\leq n\leq N,0\leq m<M}$ can be considered an embedding
$(\tilde{\gamma}_{n,m})_{1\leq n\leq N,0\leq m<M}$ of the disjoint union of
$N\times M$ open intervals $(0,1)$ to $\mathcal{C}$, satisfying the following
conditions for any $1\leq n\leq N$ and $0\leq m<M$:

  * •

$\lim_{\alpha\rightarrow
0}\tilde{\gamma}_{n,m}(\alpha)=(s_{n},\overline{m/M})$ and
$\lim_{\alpha\rightarrow 1}\tilde{\gamma}_{n,m}(\alpha)=(g_{n},\mathcal{A})$
for some $\mathcal{A}\in\mathbb{R}/\mathbb{Z}$.

  * •

The second component of $\tilde{\gamma}_{n,m}(\alpha)$ is locally strictly
increasing with respect to $\alpha$.

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 $\mathcal{E}$ is open and connected, the above set is independent of the
positions of $s_{1},g_{1},\ldots,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 (Švancara 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’ (Švancara 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
$\tau$ 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 $n$-th trajectory in the $a$-th period when
it waits until time $a\tau$ and moves along $\gamma_{n,a-\lfloor a/M\rfloor
M}$. Let us denote as $t$, the time of appearance of a new agent at the start
position $s_{n}$. Let $a:=\left\lceil t/\tau\right\rceil$. 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^{\prime}+1$-th period, where $a^{\prime}$
is the order of the period assigned to the last agent that appeared at $s_{n}$
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+\alpha$, where $c$ is a
constant222We add $c$ to account for the time margin needed to avoid
collisions between agents. and $\alpha$ is a random variable drawn from the
exponential distribution with a rate parameter $\lambda$. We also assume that
all agents wait for (the maximum) time $\tau$ 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 $\lambda$ and the service time as $D:=\tau-c$, and
when $\rho=D\lambda<1$, the average waiting time is given as

$W^{\prime}=D+\frac{\rho}{2(1-\rho)}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^{\prime}+c=\tau+\frac{\lambda(\tau-c)^{2}}{2(1-\lambda(\tau-c))}.$ (15)

## Experiments

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

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.

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 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+\alpha$, where $\alpha$ follows the exponential
distribution with a rate parameter $\lambda$. We sampled appearance times
until the last time reached $1000$ for infinite queues and $100$ for finite
queues. For each environment and each $\lambda\in[0.25,0.5,0.75,\dots,2.5]$,
we generated $10$ different problem instances. Throughout the experiment, $r$
and $v_{\mathrm{max}}$ 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\in\\{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 $\pi_{n}$ be the shortest path connecting $s_{n}$ and $g_{n}$. Each agent
appearing at $s_{n}$ follows $\pi_{n}$, while adjusting its velocity to
satisfy the next condition.

  * •

Let two paths $\pi_{n}$ and $\pi_{n^{\prime}}$ intersect at point $p$. We
assume that the length of the part of $\pi_{n}$ from $s_{n}$ to $p$ is shorter
than that of the part of $\pi_{n^{\prime}}$ from $s_{n^{\prime}}$ to $p$ (and
assume $i<i^{\prime}$ if they are equal). Then, for any $a\in\mathbb{Z}$, $M$
agents appearing at $s_{n}$ at time $aM\tau,(aM+1)\tau,\ldots,(aM+M-1)\tau$
must pass $p$ at the time between times when agents appearing at
$s_{n^{\prime}}$ at $(aM-1)\tau$ and at $aM\tau$ 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
$\tau$ 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
(Švancara et al. 2019) and the state-of-the-art 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 (Švancara 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 (Švancara 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.

| 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$

##### Case I: Infinite queues.

Figures 5 and 6 respectively show the changes in throughput and average delays
with respect to $\lambda$ 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 $\lambda$ 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.

Figure 5: Throughput with respect to $\lambda$ for _infinite_ queues (bars
represent standard derivations) Figure 6: Average delay with respect to
$\lambda$ for _infinite_ queues (bars represent standard derivations)

##### Case II: Finite queues.

We set the length of queues to be five. Note that planning for a new agent is
regarded as 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 $\lambda$. 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.

Figure 7: Throughput with respect to $\lambda$ for _finite_ queues (bars
represent standard derivations) Figure 8: Average delay with respect to
$\lambda$ for _finite_ queues, (bars represent standard derivations)

## 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 LaValle 2013), MAPF with kinodynamic constraints
(Hönig et al. 2018; Walker, Sturtevant, and Felner 2018a), and online MAPF
(Švancara 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 (Švancara 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önig 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 first-serve 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 moment (Švancara 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ösmann, Hoffmann, and Bertram
(2017) for a single-agent case and that in Hönig 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 collision-free
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önig 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).

## A: Proof of Proposition 1

Let $s_{1}^{\prime},g_{1}^{\prime},\ldots,s_{N}^{\prime},g_{N}^{\prime}$ be
another collection of start and goal locations. It is enough to show that
there exists a homeomorphism $F:\mathcal{E}\rightarrow\mathcal{E}$ such that
$F(s_{n})=s_{n}^{\prime}$ and $F(g_{n})=g_{n}^{\prime}$ for all $1\leq n\leq
N$. This is proven by Michor and Vizman (1994).

## B: Generation Algorithm of Initial Plans

First, we set $r=0$ to relax the clearance from boundaries and collision-free
constraints. Let $s_{n}=p_{n,0},p_{n,1},\ldots,p_{n,K_{n}}=g_{n}$ be start and
goal locations and all intersection points with other paths on $\pi_{n}$
ordered from $s_{n}$ to $g_{n}$. Also, let $t_{n,m,k}$ be the traveling time
from $s_{n}$ to $p_{n,k}$ in the initial plan, and $L_{n,k}$ be the minimum
traveling time from $p_{n,k}$ to $p_{n,k+1}$. Then, the following condition
must hold:

$t_{n,m,0}=0,$ (16) $t_{n,m,k}+L_{n,k}\leq t_{n,m,k+1},$ (17)

We also consider constraints of the forms “the $m$-th agent appeared $s_{n}$
must pass through $p_{n,k}=p_{n^{\prime},k^{\prime}}$ earlier than
$m^{\prime}$-th agent appeared $s_{n}$”, where $0\leq m,m^{\prime}<M$, which
is written by:

$m\tau+t_{n,m,k}<m^{\prime}\tau+t_{n^{\prime},m^{\prime},k^{\prime}}.$ (18)

We describe these constraints using tuple
$C_{1}:=(n,m,k,n^{\prime},m^{\prime},k^{\prime})$. Likewise, there exist
constraints of the forms “the $(M-1)$-th agent appeared $s_{n}$ must pass
through $p_{n,k}=p_{n^{\prime},k^{\prime}}$ earlier than $M$-th agent appeared
$s_{n^{\prime}}$”. They are given as follows:

$(M-1)\tau+t_{n,M-1,k}<M\tau+t_{n^{\prime},0,k^{\prime}},$ (19)

which we describe them using tuple $C_{2}:=(n,k,n^{\prime},k^{\prime})$.

Moreover, we set a redundancy parameter $R=1.0$ and make these constraints
stricter:

$m\tau+t_{n,m,k}+R\leq m^{\prime}\tau+t_{n^{\prime},m^{\prime},k^{\prime}}.$
(20) $(M-1)\tau+t_{n,M-1,k}+R\leq M\tau+t_{n^{\prime},0,k^{\prime}}.$ (21)

After the values of $t_{n,m,k}$ satisfying the above conditions are
determined, the initial value of $\gamma_{n,m}$ can be constructed by
connecting $p_{n,k}$ and $p_{n,k+1}$ with constant velocity motions.

Now, we construct a directed graph such that its vertices are tuples $(n,m,k)$
and its edges connect from $(n,m,k)$ to $(n,m,k+1)$ or from $(n,m,k)$ to
$(n^{\prime},m^{\prime},k^{\prime})$ for
$(n,m,k,n^{\prime},m^{\prime},k^{\prime})\in C$. Then, for the constraints
given in this paper, the graph is acyclic and the indegrees of vertices of the
form $(n,m,0)$ are zero. So we can compute the minimum values of $t_{n,m,k}$
satisfying (16), (17), and (20) by dynamic programming after the value of
$\tau$ is determined.

Since the value of $\tau$ is not determined yet, we write
$t_{n,m,k}=a_{n,m,k}\tau+b_{n,m,k}$ and define the order of pairs of
$(a,b)\in\mathbb{Z}\times\mathbb{R}$ by the lexicographical order. Then, we
can compute the minimum values of $a_{n,m,k},b_{n,m,k}$ by dynamic programming
satisfying the following conditions:

$(a_{n,m,0},b_{n,m,0})=(0,0),$ (22)
$(a_{n,m,k}.b_{n,m,k}+L_{n,m})\leq(a_{n,m,k+1},b_{n,m,k+1}),$ (23)
$(a_{n,m,k}+m,b_{n,m,k}+R)\leq(a_{n^{\prime},m^{\prime},k^{\prime}}+m^{\prime},b_{n^{\prime},m^{\prime},k^{\prime}})$
(24)

for all $(n,m,k,n^{\prime},m^{\prime},k^{\prime})\in C_{1}$.

We determine the values of $a_{n,m,k},b_{n,m,k}$ as the minimum ones.
Furthermore, we can prove that these values hold the following inequality by
the forms of conditions:

$a_{n,m,k}+m\leq M-1.$ (25)

Thus, when $\tau$ is large enough, $t_{n,m,k}=a_{n,m,k}\tau+b_{n,m,k}$ while
satisfying the conditions (16), (17), (20), and (21). We determine the value
of $\tau$ as the minimum one of such values.

## C: Implementation Details

All the methods are implemented in C++ and evaluated with Intel Core i9-9900K
CPU and 32 GB RAM.

##### Optimization method.

For optimization, we use Levenberg-Marquardt (LM) Algorithm implemented in g2o
(Kümmerle et al. 2011). Parameters for the optimization are set as the default
values of the library.

We set
$\sigma_{\mathrm{r}}=\sigma_{\mathrm{v}}=\sigma_{\mathrm{o}}=\sigma_{\mathrm{c}}=10^{4}$
and $\sigma_{\mathrm{t}}=1$ as the initial values. Since the set $C$ in Eq.(7)
of the main paper may change depending on the value of $p$ or $T_{i,j}$, we
have to reset the explicit constraints repeatedly during optimization. The
number of iteration of LM algorithm and intervals of resetting constraints are
as follows:

  1. 1.

The first $500$ iterations: we recalculate $C$ after each iteration.

  2. 2.

The next $39500$ iterations: we recalculate $C$ for $10$ iterations.

  3. 3.

The following $1000$ iterations: we recalculate $C$ and increase
$\sigma_{\mathrm{r}},\sigma_{\mathrm{v}},\sigma_{\mathrm{o}}$, and
$\sigma_{\mathrm{c}}$ by multiplying $1.01$ and decrease $\sigma_{\mathrm{t}}$
by dividing $1.01$ after each iteration.

  4. 4.

The remaining iterations: we recalculate $C$ after each iteration. This phase
lasts until the plan converges, more precisely, until the difference of costs
for $100$ iterations goes below $10^{-6}$.

| Environment
---|---
$M$ | (a) | (b) | (c) | (d) | (e) | (f)
$1$ | 44537 | 42899 | 41113 | 45025 | 41133 | 46111
| 2 | 4 | 5 | 13 | 29 | 54
$2$ | 74280 | 97481 | 84898 | 49504 | 43514 | 73906
| 15 | 69 | 59 | 50 | 69 | 277
$3$ | 41910 | 83786 | 52978 | 85698 | 61067 | 41973
| 8 | 96 | 57 | 281 | 188 | 107
Table 2: Number of iterations (top) and required time [min] (bottom) for until
the optimization converges for the proposed approach.

Table 2 reports the number of iterations until the optimization converges and
required times in minutes.

#### Baseline methods.

For the FCFS approach, we modify the implementation of Prioritized SIPP by
Kasaura, Nishimura, and Yonetani (2022) to our problem setting. For the SO
approach, we modify the implementation of CCBS by the authors, which is
available online333github.com/PathPlanning/Continuous-CBS, to our problem
setting. For each query, planning was considered a failure if the runtime
exceeded $1.0$ seconds. For PRM, We also use the implementation by Kasaura,
Nishimura, and Yonetani (2022). As the parameters for PRM, the number of
roadmap vertices is $1000$ for the FCFS approach and $20$ for the SO approach.
We limit the number of vertices for the SO because CCBS is generally time-
consuming when the density of vertices is high and the environments are small.
The number of neighbors is $15$ for the FCFS approach and $10$ for the SO
approach.

## References

  * Andreychuk et al. (2021) 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 et al. (2022) Andreychuk, A.; Yakovlev, K.; Surynek, P.; Atzmon, D.; and Stern, R. 2022.  Multi-agent pathfinding with continuous time.  _Artificial Intelligence_ , 103662.
  * Bhattacharya (2010) Bhattacharya, S. 2010.  Search-based path planning with homotopy class constraints.  In _AAAI conference on artificial intelligence_ , volume 24, 1230–1237.
  * Bhattacharya and Ghrist (2018) 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 et al. (2015) 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, Pallottino, and Bicchi (2017) 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 et al. (2021) 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 MultiAgent Systems_.
  * Dresner and Stone (2008) Dresner, K.; and Stone, P. 2008.  A multiagent approach to autonomous intersection management.  _Journal of Artificial Intelligence Research_ , 31: 591–656.
  * Erlang (1909) Erlang, A. K. 1909.  The theory of probabilities and telephone conversations.  _Nyt Tidsskrift for Matematik B_ , 20: 33–39.
  * Fusco, Kermorgant, and Martinet (2018) 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önig et al. (2018) Hönig, 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 et al. (2019) 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 and Frazzoli (2011) Karaman, S.; and Frazzoli, E. 2011.  Sampling-based algorithms for optimal motion planning.  _The International Journal of Robotics Research_ , 30(7): 846–894.
  * Kasaura, Nishimura, and Yonetani (2022) 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 (1953) 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 (1986) Khatib, O. 1986.  Real-time obstacle avoidance for manipulators and mobile robots.  In _Autonomous Robot Vehicles_ , 396–404. Springer.
  * Kloder and Hutchinson (2006) Kloder, S.; and Hutchinson, S. 2006.  Path planning for permutation-invariant multirobot formations.  _IEEE Transactions on Robotics_ , 22(4): 650–665.
  * Kreidieh, Wu, and Bayen (2018) 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.
  * Kümmerle et al. (2011) Kümmerle, R.; Grisetti, G.; Strasdat, H.; Konolige, K.; and Burgard, W. 2011\.  g 2 o: A general framework for graph optimization.  In _2011 IEEE International Conference on Robotics and Automation_ , 3607–3613. IEEE.
  * Kurniawati and Fraichard (2007) Kurniawati, H.; and Fraichard, T. 2007.  _From path to trajectory deformation_.  Ph.D. thesis, INRIA.
  * Levenberg (1944) 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 et al. (2021) 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 (2021) Ma, H. 2021.  A Competitive Analysis of Online Multi-Agent Path Finding.  In _International Conference on Automated Planning and Scheduling_.
  * Ma et al. (2017) 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 MultiAgent Systems_ , 837–845.
  * Marquardt (1963) 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.
  * Michor and Vizman (1994) Michor, P. W.; and Vizman, C. 1994.  $n$-transitivity of certain diffeomorphism groups.  _Acta Mathematica Universitatis Comenianae. New Series_ , 63(2): 221–225.
  * Okumura et al. (2022) 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ösmann, Hoffmann, and Bertram (2017) Rösmann, 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 et al. (2015) 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 (2005) Silver, D. 2005.  Cooperative pathfinding.  In _AAAI Conference on Artificial Intelligence and Interactive Digital Entertainment_ , volume 1, 117–122.
  * Stern et al. (2019) 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.
  * Švancara et al. (2019) Švancara, J.; Vlk, M.; Stern, R.; Atzmon, D.; and Barták, R. 2019.  Online multi-agent pathfinding.  In _AAAI Conference on Artificial Intelligence_ , volume 33, 7732–7739.
  * Walker, Sturtevant, and Felner (2018a) 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, Sturtevant, and Felner (2018b) 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, D’Andrea, and Mountz (2008) 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 and LaValle (2013) Yu, J.; and LaValle, 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.


* [147] J. Pavur, D. Moser, V. Lenders, and I. Martinovic, “Secrets in the sky: On privacy and infrastructure security in DVB-S satellite broadband,” in _Proceedings of the 12th Conference on Security and Privacy in Wireless and Mobile Networks_ , ser. WiSec ’19. New York, NY, USA: Association for Computing Machinery, 2019, p. 277–284. [Online]. Available: https://doi.org/10.1145/3317549.3323418
  * [148] “CCSDS space link protocols over ETSI DVB-S2 standard,” The Consultative Committee for Space Data Systems, Recommended Standard CCSDS 131.3-B-1, Mar 2013\. [Online]. Available: https://ccsds.org
  * [149] “Security architecture for space data systems,” The Consultative Committee for Space Data Systems, Recommended Practice CCSDS 351.0-M-1, Nov 2012. [Online]. Available: https://ccsds.org
  * [150] “Unified space data link protocol,” The Consultative Committee for Space Data Systems, Recommended Standard CCSDS 732.1-B-1, Oct 2018. [Online]. Available: https://ccsds.org
  * [151] “Space packet protocol,” The Consultative Committee for Space Data Systems, Recommended Standard CCSDS 133.0-B-2, Jun 2020. [Online]. Available: https://ccsds.org
  * [152] “Space data link security protocol,” The Consultative Committee for Space Data Systems, Recommended Standard CCSDS 355.0-B-1, Sept 2015. [Online]. Available: https://ccsds.org
  * [153] A. Satapathy and J. Livingston, “A comprehensive survey on SSL/ TLS and their vulnerabilities,” _International Journal of Computer Applications_ , vol. 153, pp. 31–38, 11 2016.
  * [154] G. Caparra, S. Ceccato, F. Formaggio, N. Laurenti, and S. Tomasin, “Low power selective denial of service attacks against gnss,” 09 2018.
  * [155] C. Gibson, “Iot and satellite security in the age of 5g,” Available at https://www.trendmicro.com/en_us/research/18/f/attack-vectors-in-orbit-need-for-satellite-security-in-5g-iot.html (2020/10/12).
  * [156] Y. Afek, M. Merritt, and G. Taubenfeld, “Benign failure models for shared memory,” in _International Workshop on Distributed Algorithms_. Springer, 1993, pp. 69–83.
  * [157] R. H. Zielinski, I. Worley, Robert M, D. S. Black, S. A. Henderson, and D. C. Johnson, “Star tek - exploiting the final frontier: Counterspace operations in 2025,” Tech. Rep., 1996. [Online]. Available: http://www.dtic.mil/docs/citations/ADA392588