Main Track

AAMAS 2022, May 9–13, 2022, Online

Standby-Based Deadlock Avoidance Method for Multi-Agent
Pickup and Delivery Tasks
Tomoki Yamauchi

Yuki Miyashita

Toshiharu Sugawara

Waseda University
Tokyo, Japant.yamauchi@isl.cs.waseda.ac.jp

Waseda University
Tokyo, Japany.miyashita@isl.cs.waseda.ac.jp

Waseda University
Tokyo, Japansugawara@isl.cs.waseda.ac.jp

ABSTRACTThe multi-agent pickup and delivery (MAPD) problem, in which
multiple agents iteratively carry materials without collisions, hasreceived significant attention. However, many conventional MAPD
algorithms assume a specifically designed grid-like environment,such as an automated warehouse. Therefore, they have many pickup
and delivery locations where agents can stay for a lengthy period, as well as plentiful detours to avoid collisions owing to thefreedom of movement in a grid. By contrast, because a maze-likeenvironment such as a search-and-rescue or construction site has
fewer pickup/delivery locations and their numbers may be unbalanced, many agents concentrate on such locations resulting in inefficient operations, often becoming stuck or deadlocked. Thus,
to improve the transportation efficiency even in a maze-like restricted environment, we propose a deadlock avoidance method,
called standby-based deadlock avoidance (SBDA). SBDA uses standby
nodes determined in real-time using the articulation-point-finding
algorithm, and the agent is guaranteed to stay there for a finite
amount of time. We demonstrated that our proposed method outperforms a conventional approach. We also analyzed how the parameters used for selecting standby nodes affect the performance.

KEYWORDS
Multi-agent pickup and delivery tasks; Multi-agent path finding;Deadlock avoidance; Decentralized robot path planning
ACM Reference Format:
Tomoki Yamauchi, Yuki Miyashita, and Toshiharu Sugawara. 2022. StandbyBased Deadlock Avoidance Method for Multi-Agent Pickup and Delivery
Tasks. In Proc. of the 21st International Conference on Autonomous Agentsand Multiagent Systems (AAMAS 2022), Online, May 9–13, 2022, IFAAMAS,
9 pages.

1

INTRODUCTION

The use of multi-agent systems (MAS) for complex and enormous
tasks in real-world applications has recently attracted considerable attention. Examples include transport robots in automatedwarehouses [34], autonomous aircraft-towing vehicles [18], ridesharing services [12, 37], office robots [31], and delivery systems
with multiple drones [10]. However, simply increasing the numberof agents may lead to inefficiency owing to redundant movements
and resource conflicts such as collisions. Therefore, to improve theoverall performance, it is essential to have coordinated actions that
Proc. of the 21st International Conference on Autonomous Agents and Multiagent Systems (AAMAS 2022), P. Faliszewski, V. Mascardi, C. Pelachaud, M.E. Taylor (eds.), May
9–13, 2022, Online. © 2022 International Foundation for Autonomous Agents and Multiagent Systems (www.ifaamas.org). All rights reserved.

1427

avoid negative effects among agents. In particular, collision avoidance is essential in our application, which is a pickup and delivery
system applied in a restricted environment where the agents arelarge heavy-duty robots carrying heavy and large-sized materials.
This problem is formulated as a multi-agent pickup and delivery(MAPD) problem, where pickup and delivery tasks are assigned toindividual agents simultaneously. The assigned agent then needs
to move to the material storage area, load a specified material,deliver it to the required location, and unload it. Therefore, because there are numerous tasks to fulfill, the MAPD problem can beconsidered as an iteration of multi-agent path-finding (MAPF), in
which multiple agents generate collision-free paths to their targets
without collisions. Unfortunately, the MAPF problem is known tobe an NP-hard problem to obtain the optimal solution [17], andthus the MAPD problem is more time-consuming.
There have been many studies focusing on MAPF/MAPD problems [11, 13, 14, 16, 19, 21, 28], and their results have been used inreal-world applications. With these applications, generating plans
without collisions and deadlocks becomes the central issue. For
example, Okumura et al. [21] proposed priority inheritance withbacktracking (PIBT) in which the agents decide the actions withina short time window to avoid deadlocks based on priorities andthrough local communication. Ma et al. [16] proposed token passing (TP) with using the holding task endpoints (HTE) [11, 13], which
exclusively holds the endpoints including the pickup/delivery nodesof the tasks, to avoid collisions. Liu et al. [13] introduced reserving
dummy paths (RDP), which consistently reserve dummy paths to aunique parking location of each agent, allowing the agents to fulfill
their tasks with the same endpoint simultaneously.
However, these methods cannot be used in our target environments. For example, to guarantee completeness, PIBT requires theenvironment to be bi-connected; however, our environment cannot meet this requirement. For efficient movement, HTE and RDP
assume a grid-like environment, which has many endpoints where
agents can stay for any time length and/or many detours whose
lengths are almost identical. Such requirements are possible in specially designed environments such as an automated warehouse.
However, our environments are ad hoc and maze-like, such as asearch-and-rescue or construction site, and usually have fewer pickup
and/or delivery locations whose numbers may be unbalanced, resulting in congestion near a few of the endpoints. Moreover, detours are limited and often become much longer.
Therefore, we propose a deadlock avoidance method, i.e., standbybased deadlock avoidance (SBDA), for improving the transportation efficiency while allowing agents to conduct their tasks withthe same endpoint even in a maze-like environment. We integrate
this method with TP although the number of endpoints is quite

Main Track

AAMAS 2022, May 9–13, 2022, Online

al. [5] proposed pathfinding via reinforcement and imitation multiagent learning - lifelong (PRIMAL2 ), a distributed reinforcement
learning framework for a lifelong MAPF (LMAPF), which is a variant of the MAPF in which agents are repeatedly assigned new destinations. However, they assumed that tasks are sparsely generated
at random locations, and thus, unlike our environment, no local
congestion occurs. Although other studies in the area of trajectory
planning and robotics also assume maze-like environments [6, 26,29], our study differs because we aim at completing the MAPD instance efficiently in a restrictive maze-like environment.
Previous studies have focused on deadlock avoidance in the MAPD
problem [11, 13, 16, 19], similar to our approach. For example,
HTE [11, 13] method assumes that the environment has many endpoints where agents can remain for a finite length of time; otherwise, the performance will decrease because fewer tasks can be executed in parallel. By contrast, RDP [13] always reserves dummypaths to the unique parking location of each agent to allow theagents to conduct their tasks with the same endpoint simultaneously; hence, numerous detours whose lengths are almost identical are necessary for achieving efficiency. However, our environment is maze-like and has fewer endpoints, and thus the use of
endpoints is limited [19]. It also has a limited number of detours
whose lengths may differ considerably.

small in our target environments. The SBDA algorithm employs
standby nodes, where an agent is guaranteed to wait for a finite
amount of time near its destination (i.e., its endpoint). The set ofstandby nodes changes while the agents reserve such nodes to staythere; however, they can be determined efficiently in real-time using the articulation-point-finding algorithm (APF algorithm) in thegraph theory [30]. When an agent moves toward the endpoint
where other agents have already arrived and/or are traveling as
their destination, SBDA enables the agent to temporarily wait at
one of standby nodes remaining near the endpoint to avoid becoming stuck or entering a deadlock and head toward its destination in turn. Herein, we evaluate the performance of our proposed method and compare it with that using HTE as a baseline
under various experimental conditions. We then demonstrate thatour proposed method outperforms the baseline method in mazelike restricted environments. Finally, we analyze the features ofthe proposed method by conducting experiments under various
parameter settings and applying an ablation study.

2

RELATED WORK

Studies on the MAPF/MAPD problem have been approached froma variety of perspectives [7, 15, 27]. One main approach is centralized planning and scheduling [1–3, 13, 28]. For example, Sharon
et al. [28] proposed the conflict-based search (CBS) algorithm for
the MAPF problem. CBS is a two-stage search approach, consisting of a low-level search in which agents generate their paths independently, and a high-level search in which a centralized planner generates optimal collision-free paths by receiving local plansfrom all agents. CBS and its extensions are used in many othercentralized planners [1–3, 13]. Although we can expect optimal
solutions/paths for the MAPD instances, the computational costof a centralized planner rapidly increases with an increase in thenumber of agents [16].
Decentralized methods are more scalable and robust, and thus
many studies have been conducted from this perspective [16, 21,
32, 33]. However, because the plans are generated individually,such methods for the MAPD problem must have completeness aswell as the ability to detect and resolve conflicts between them under certain restrictions. For example, Okumura et al. [21] proposed
PIBT for the MAPF/MAPD problem, in which agents determine
the next nodes in accord with their priorities through communication with local agents. PIBT is effective and has been extended foruse in more general cases [22, 23]; however, the completeness isguaranteed only in bi-connected environments. Ma et al. [16] proposed TP in which an agent selects tasks whose endpoints have
not yet been reserved by other agents, and generates its collisionfree plan by exclusively referring to the token, i.e., a synchronizedshared block of memory. However, many of these studies also assume that the environments are grid-like such that, to avoid collisions, there are many escape nodes and the same-length of detours
between two points. However, applying them to our maze-like environments may lead to a reduced efficiency of transportation andplanning owing to the small number of endpoints and few detours,
whose lengths are quite different.
By contrast, some studies [5, 8, 9, 24, 25, 38] have also considered
an application to maze-like environments. For example, Damani et

3 PRELIMINARIES
3.1 Problem Formulation
The MAPD problem consists of an agent set A = {1, . . . , M }, atask set T = {τ1 , . . . , τ N }, and an undirected connected graph
G = (V , E) embeddable in a two-dimensional Euclidean space.
Node v ∈ V corresponds to a location, and an edge (u, v) ∈ E(u, v ∈ V ) corresponds to a path along which an agent can move
between locations u and v. We can naturally define the length ofedge (u, v) by denoting l(u, v). The distance between nodes v 1 andv 2 is defined as the sum of the lengths of edges appearing in the
shortest path from v 1 to v 2 . We assume that an endpoint is set to adead-end in G. Our agent is a heavy-duty forklift-like autonomous
robot with a picker in front, which carries a heavy material (500 kg
to 1 ton) and can pick up (load) or put down (unload) this materialusing a picker in a specific direction at a specific node. We introduce discrete-time t ∈ Z+ , where Z+ is the set of positive integers.
For agent i ∈ A, we define the orientation oit ∈ Z+ and moving
direction dit ∈ Z+ of i at time t, where 0 ≤ oit , dit < 360 in D increments, and oit = 0 and dit = 0 indicate the northward orientationand direction of G. In addition, the set of possible orientations is denoted as D. For example, if D = 90, D = {0, 90, 180, 270} ∋ oit , dit .
We assume D = 90 for simplicity, whereas D can have any number
depending on the environmental structure.
Agents can conduct the following actions: move, rotate, wait,
load, and unload on any node. Using the length l = l(u, v), therotation angle θ ∈ Z+ , and the waiting time t, the durations ofactions move, rotate, wait, load, and unload are denoted by Tmo (l),Tr o (θ ), Twa (t), Tld , and Tul , respectively. Suppose that i is on v attime t. By action move, i moves forward or backward along edge(u, v) to u after appropriately changing its orientation oit througha rotation. By rotate, i rotates D degrees clockwise (D) or countert +T (D)clockwise (−D) from oit , i.e., oi r o= oit ± D, at v. Agent i has a1428

Main Track

AAMAS 2022, May 9–13, 2022, Online

unique parking node parki ∈ V [13], which is the starting location
at t = 0, and returns and remains there if i has no tasks to execute.
Parking nodes are expressed by the red squares in Fig. 2.
The task τ j is specified by the tuple τ j = (στldj , στulj , φτ j ), whereστldj = (vτldj , old
τ j ) (∈ V × D) are the location and orientation whenloading a material φτ j , and στulj = (vτulj , oul
τ j ) (∈ V × D) are thelocation and orientation when unloading a material φτ j . When an
agent loads and unloads a material, it needs to be oriented in a
specific direction, considering the direction of the picker. Agents
have to complete all tasks in T without collisions or deadlocks andthen return to their own parki .

3.2

Token Passing

Although the proposed SBDA can be adapted to some existing
MAPD algorithms, in this paper, we show that it can be integrated
into TP to efficiently solve an MAPD instance. TP [16] is a wellknown MAPD algorithm, in which agents choose tasks themselvesand generate paths using the information in the token. A token is asynchronized shared memory block containing the current pathsof all agents, tasks currently assigned agents, and the remaining
tasks that are not assigned agents.
The set of endpoints Vep (⊂ V ) of an MAPD problem consistsof all task endpoints that are possible pickup/delivery locations of
the tasks and non-task endpoints including the initial location (i.e.,parki ) of each agent. TP assumes that any agent can stay at an
endpoint for any finite length of time without blocking the movement of other agents for their current tasks. We denote the set oftask endpoints by Vtsk (⊂ Vep ). It is assumed that the locations of
all endpoints are given to the agents in advance. Hence, when an
agent chooses one task whose pickup/delivery locations are open
endpoints, meaning that they do not appear as the endpoints ofthe executing plans in the current token, a collision-free path isgenerated by looking at the content of the token. HTE in TP thenholds the task endpoints to avoid collisions.
Although not all MAPD instances are solvable, well-formed MAPD
instances are always solvable [4]. For TP, an MAPD instance iswell-formed if and only if (a) the number of tasks is finite, (b)there are not fewer non-task endpoints than agents, and (c) a pathexists between any two endpoints that does not traverse otherendpoints [16]. In well-formed MAPD instances, agents can moveto non-task endpoints (e.g., parki ) at any time and stay there aslong as necessary to avoid collisions with other agents. This action might be able to reduce the number of agents to avoid anoverly crowded environment. Obviously, the assumption regarding the endpoints makes these requirements hold. However, agentscannot conduct tasks simultaneously if their endpoints are overlapped; hence, this approach reduces the efficiency considerably inmaze-like environments such as our considered environment.

4 STANDBY-BASED DEADLOCK AVOIDANCE
4.1 Status Management Tokenan extension of a token [16] and a synchronized block of information [35], to manage the status of the planning, agents, and standby
nodes and to detect conflicts with other agents, where we definea conflict as a situation in which multiple agents occupy the samenode v ∈ V or cross the same edge simultaneously. SMT contains
the reservation table (RT), the task execution status table (TEST),and the standby-node status table (SST). RT is the set of RT tuples(v, [svi , evi ], i), which are valid reservation data used to generate
collision-free plans, where [svi , evi ] is the occupancy intervals of
agent i for node v. When evi < tc (tc is the current time), thetuple has been expired and deleted from RT. TEST is the set of
TEST tuples (τ , v, i), where τ is the task currently being executedby i, and v is the associated destination, which is the load or unload node specified in τ . Therefore, two TEST tuples (τ , vτld , i) and(τ , vτul , i) are added when i selects task τ , and when i arrived atvτld or vτul , the corresponding entry is removed from TEST. SST is
used to manage the status of all standby nodes, which are dynamically referred to and modified by SBDA. The structure of SST is
described in Section 4.2.
SMT is a sharable memory area, and similar to a token in TP,
only one agent can exclusively access it at a particular time. Although SMT may incur a slight performance bottleneck, the movement speeds of the robots are not fast and thus the time required
for an overhead owing to a mutual exclusion is negligible for a realistic number of agents (e.g., less than 30 agents in the experimentenvironments as shown in Fig. 2).

4.2

Finding Potential Standby Nodes

Standby nodes are intuitively nodes by which, similar to non-task
endpoints in TP, an agent is guaranteed to wait for a finite length oftime on its way to the endpoint of the assigned task; however, they
can be identified dynamically. We assume that, except for parking
nodes, non-task endpoints are not given in advance. Let us define
an articulation point (AP) and a potential standby node, which will
be used as a standby node when needed:
Definition 4.1. A node in graph G is an articulation point iff removing it and the associated edges will split the connected area of
G and increase the number of connected components.
Definition 4.2. A potential standby node in graph G is a node thatis neither an AP, an endpoint, nor a dead-end in G.
Let us denote the set of all potential standby nodes in G = (V , E)
by Spsn (G) (⊂ V ). The next proposition is obvious from this definition.
Proposition 4.3. If G = (V , E) is a connected graph and Spsn (G) ,, then the subgraph generated by eliminating any node v psn in
Spsn (G) from G is connected.
Therefore, even if an agent remains at a potential standby node,other agents can generate paths to reach their destinations without
passing that node. We therefore have the following:
Corollary 4.4. Any agent reserving a standby node can remain
there for a finite length of time without blocking the movements ofother agents.

We propose a novel deadlock avoidance method, i.e., SBDA, to improve the transportation efficiency while allowing agents to conduct tasks having the same endpoints even in a maze-like environment. We introduce the status management token (SMT), which is

The set of all potential standby nodes Spsn (G) is efficiently identified using the APF algorithm such as Tarjan’s algorithm [30],1429

Main Track

AAMAS 2022, May 9–13, 2022, Online

Agent i delivers to v2 (vdi = v2)

Algorithm 1 Task selection by agent i

Agent i in v1

1: function SelectTask(i)2:T ′ = Set of tasks satisfying Cond. 1.
3:
4:
5:

Agent j in v2

st(vdi ) = Ø & st(vdj ) = Ø// where τ = (στld , στul , φτ ), and στld = (vτld , oldτ )if T ′ ,  thenτ ∗ ← arg min dist(vci , vτld ) // vci : current location

Agent j delivers to v1 (vdj = v1)

τ ∈T ′T ← T \ τ ∗ ; return τ ∗7:else return false
8:
end if
9: end function

Figure 1: Deadlock state (i and j are on the same graph)

6:

4.3

Task Selection Process

After the agents start the tasks in an MAPD problem, an agent
with SBDA selects a task to conduct based on the potential standby
nodes in SMT, decides its destination by selecting a standby node
if necessary, and generates a path to it. The agent exclusively accesses the current SMT during this process.
The pseudo-code of the task selection process SelectTask(i)based on the potential standby nodes is shown in Algorithm 1. Thisis applied only when T , ; otherwise, agent i returns to its parking node parki . For v psn ∈ Spsn (G t ), let ev∗ psn,t be the last time that
all agents will pass v psn for all current plans. This can be calculatedjj
by looking at the elements (v psn , [svpsn , evpsn ], j) in RT of SMT, andif such an element does not exist in RT, we set ev∗ psn,t = tc , wheretc is the time when calculating ev∗ psn,t .

whose time complexity is O(|V|+|E|) [20]. Now, we define a standby
node, where G t is the modified subgraph of G at time t, as below.
Definition 4.5. The potential standby node v ∈ Spsn (G t ) is astandby node when agent i ∈ A reserves v to remain there.
When the agent leaves standby node v, v is no longer in standby
node. We denote the set of all standby nodes with a reserving agent
as St = {(v, i)) | i ∈ A reserves v as standby node}.
When agents make a reservation to stay at a number of standby
nodes (how such a reservation is created is explained in Section 4.4),other agents are prohibited to pass through them. This means thatthe structure of graph G is temporally modified by eliminating thestandby nodes (and the associated edges). This modified graph attime t is then denoted by G t = (Vt , Et ). Thus, the set of potential standby nodes in G t is denoted by Spsn (G t ), which is also efficiently identified using the APF algorithm. Note that G = G 0 .
Before agents start the tasks in an MAPD problem, SBDA generates the set of associated potential standby nodes s(v tsk ) for every
endpoint v tsk . For endpoint ∀v tsk (∈ Vtsk ), SBDA calculates s(v tsk )(⊂ Spsn (G)) using

Agent i selects tasks τ = (στld , στul , φτ ) ∈ T that hold the following conditions (Cond. 1) at time t, where vci is the current loulul ulcation of i, στld = (vτld , old
τ ) and στ = (vτ , oτ ).
(1) If i remains at its parking node (vci = parki ), the crowded
list, CL, is empty.
(2) Its load node vτld is open (i.e., it does not appear as an endpoint in RT ), or vτld has non-empty associated potential standby
nodes (i.e., st (vτld ) , ) and ∃v psn ∈ st (vτld ) such thatev∗ psn − tc ≤ δ .

s(v tsk ) = {v psn ∈ Spsn (G)|dist(v psn , v tsk ) ≤ α },(3) |st (vτul )| +1 is greater than the number of tuples that appear
in T EST , whose destination is vτul .

where dist(v 1 , v 2 ) is the distance between v 1 and v 2 , i.e., the lengthof the shortest path between them. Parameter α (≥ 0) is the limitof the distance to a standby node from the endpoint v tsk . Note′ ) ,  forthat it is possible that s(v tsk ) =  and s(v tsk ) ∩ s(v tsk′
v tsk , v tsk ∈ Vtsk . Similarly, the set of potential standby nodes forv tsk at t is denoted by st (v tsk ) = s(v tsk ) ∩ Spsn (G t ). Therefore,s(v tsk ) = s 0 (v tsk ) is the set of the initial potential standby nodes
for G (= G 0 ). We also define the set of potential standby nodes thatare not included in the associated potential standby nodes as∪c
Spsn(G t ) = Spsn (G t ) \st (v).

Here, because i cannot begin to stay at v psn before ev∗ psn , δ (≥ 0) is a
threshold parameter of the margin time for reserving the standby
node. The set of tasks that satisfies these conditions is denoted by
T ′ [Line 2].
Then, i selects the closest task τ ∗ , i.e., dist(vci , vτld∗ ) in G t is thesmallest, where vci is the current location of i [Lines 4–6]. If i cannot find such tasks, i returns to parki . However, it is possible for i
to occasionally check whether other agents have completed theirtasks and for some endpoints/standby nodes to become open while
i is going back and remains at parki .

v ∈Vtskc (G ) is called a free potential standby node at t.
An element in Spsntc (G ) = .
Note that it is possible that Spsnt

4.4

Use of Standby Nodes

After the previous process of task selection, agent i calls the path
planning process to generate a path to move to vτld or vτul of theselected task τ . However, it is probable that these nodes are notopen, and i may instead have to generate the path to the temporary destination. Thus, before generating a path, i calls function
DecideDest(i,vdi ,vci ) in Algorithm 2 at current time tc to decide
the next actual destination, where vdi is the destination of i, which

Information regarding the standby nodes is stored in SST. SST
at t consists of (1) the initial set of potential standby nodes, Spsn (G),(2) the initial set of all pairs of endpoints and their potential standby
nodes {(v tsk , s(v tsk )) | v tsk ∈ Vtsk }, (3) the set of pairs of standby
nodes and agents i that reserve such nodes in the form of (vsn , i) ∈St , and (4) the crowded list, CL (⊂ A), which is the set of agents ic (G).
that temporally remain at a free potential standby node in Spsn

1430

Main Track

AAMAS 2022, May 9–13, 2022, Online

and 15], (vd , i) is added to St , whereas (vc , i) is removed from St
in SST if i leaves the current standby node [Line 7].
The temporal evacuation at a free potential standby node orparking node [Lines 14–18] allows an agent to avoid a deadlock,which occurs when agents i and j try to simultaneously exchange
their unloading nodes and current locations and both nodes haveno associated potential standby nodes. An example is shown in
Fig. 1, in which two agents wait until their destinations become
open or st (vd ) , , and this situation cannot be solved if theirdestinations remain unchanged. However, when one agent sets another node as a temporary destination, one of the unloading nodes
become open and another agent can start to move. After i arrives
at standby node vsn instead of the endpoint specified by τ , it invokes function DecideDest to identify when i can move to theactual endpoint when i can obtain the right to access SMT. Then,
agent i generates the path to the next destination by using a pathi , removes the corresponding entry
finding algorithm, releases vsn
i , i) from S , unlocks SMT, and finally, leaves v .
(vsn
t
sn
Because only one agent can access SMT at a time, other agentsthat generate paths after agent i reserves standby node vsn areprohibited to pass through vsn . However, if j, which previously
generates a path before agent i reserves vsn , can pass through it, imust begin to wait at vsn after j passes through vsn ; thus, i shouldreach vsn with an appropriate delay by waiting somewhere, which
may cause other delays to other agents. To reduce such a waiting
time, the SBDA algorithm introduces Cond. 1 (2).
Finally, we prove that our proposed method is complete for ourwell-formed MAPD instances. In our SBDA, we modify the wellformed condition (c) of TP described in Section 3.2 as follows:

Algorithm 2 Destination decision by agent i
1: function DecideDest(i, vd , vc )2:// vd : vτld , vτul , or parki ,3:// vτld : pickup, vτul : delivery, parki : parking node
4:
5:
6:
7:
8:
9:
10:
11:
12:
13:
14:
15:

if i ∈ CL then remove i from CL
end ifif vd satisfies one of Cond. 2, and vd is open thenreturn vd
else if vc ∈ s(vd ) then return vc
else
G t∗ = G t ∪ {vc } // if vc < Spsn , G t = G t∗
′ (G ∗ ) = {v ∈ S (G ∗ ) | e ∗ − t ≤ δ }
Vpsn
psn t
c
v
t
′ (G ∗ ) ∩ s(v ) ,  thenif S = Vpsndtvd ← arg min(ev∗ − tc )v ∈S

′ (G ∗ ) ∩ S c (G ∗ ) ,  thenelse if S ′ = Vpsn
psn tt
vd ← arg min dist(vd , v)
v ∈S ′

CL = {i} ∪ CL
17:
else
18:
vd ← parki // i returns to its parking nodes.
19:
end if20:
end if21:
return vd
22: end function
16:

is vτld , vτul , or parki , and vci is the current node of i, which is an
endpoint, a standby node, or its parking node.
Before describing Algorithm 2, for ∀i ∈ A, we introduce the setof second conditions (Cond. 2) mainly to prevent a side entry for
approaching the endpoint.

(c’) When any agent generates a plan at time t, there exists apath between any two nodes of the endpoints or potential
standby nodes at t that does not traverse other endpoints or
standby nodes registered at t.

(1) dist(vci , vdi ) ≤ β, where β (> α) is a threshold for directly
heading toward the endpoint.
(2) No agent heads to an st (vdi ).
(3) vdi == parki

It is clear that the algorithm described thus far always satisfies condition (c’). In fact, the structure of graph G is temporarily modified
when agent i selects a standby node to remain in from the potential
standby nodes; however, another agent can always find a path toits destination without passing the standby nodes or endpoints in
SBDA. This is because SBDA uses the APF algorithm to generate
Spsn (G t ) when i selects the next task or a standby node insteadof the destination in the task. Moreover, similar to TP, the agent
exclusively accesses the current SMT and generates a path in turn.
Therefore, we obtain the following theorem:

If i can satisfy one of these conditions, it heads directly toward vdi
if possible; otherwise, it heads toward a standby node of vdi . Notethat β is also the threshold preventing other agents from being
forced to wait too long at standby nodes owing to a cutting in line.
We briefly describe Algorithm 2. If vd satisfies one of the conditions in Cond. 2, and vd is open, i determines vd as the destination[Lines 6–7]. Note that parki is always open. If vc is a standby nodeof vd , and vd is not open, it returns vc , remaining there for a while
longer [Line 8]. If not, i tries to move a potential standby node of′ (G ∗ )vd as the temporary destination. Thus, it first calculates Vpsnt∗[Line 11] by referring to RT and SST, where G t = G t ∪ {vc } is a
subgraph of G [Line 10]. If there is a potential standby node whereother agents will pass through within a time of δ , the most appropriate node is selected [Lines 12–13] (see (2) in Cond. 1). If such astandby node does not exist, i instead tries to select another freec (G ∗ ). If it can select such a node, i ispotential standby node in Spsntadded to the crowded list, CL, demonstrating that it cannot selectthe element of s(vd ) because the environment is crowded [Line14–16]. Otherwise, it returns to its parking node [Line 18]. Notethat when i selects and reserves the standby node as vd [Lines 13

Theorem 4.6. SBDA solves all well-formed MAPD instances.
Proof. First, from functions SelectTask and DecideDest, any
agent will leave from any endpoint, v ep ∈ Vep , immediately after
a load or unload task regardless of whether it has the next task.
Suppose that agent i is now an endpoint or a standby node. If i has
no task to conduct, i can generate a path to its parking node parki .
Otherwise, i heads to one of the endpoints, v ep . If v ep is open, ican generate a path to v ep . If not, i selects a standby node or its
parking node to head toward and generates a path to the selected
node. Finally, i can remain at the reserved standby node or theparking node for any finite length of time (Corollary 4.4), and ican generate a path to v ep if v ep becomes open.
□

1431

Main Track

AAMAS 2022, May 9–13, 2022, Online

25

40000

HTE
SBDA (α = 0)
SBDA (α = 4)
SBDA (α = 8)
SBDA (α = 12)

Value

No. of agents
No. of tasks
Orientation/direction increments
Duration of move per length 1
Duration of rotate
Durations of load and unload
Durations of wait
Margin time for reserving standby nodeThreshold for direct heading endpointMN
D
Tmo (1)Tr o (D)
Tld ,Tul
Twa (t)δβ

2 to 30
100
90
10
20
20
t
100
20

30000

20

25000

15

HTE
SBDA (α = 0)
SBDA (α = 4)
SBDA (α = 8)
SBDA (α = 12)

10
5

20000

0

15000
2 4 6 8 10 12 14 16 18 20
Number of agents25

2 4 6 8 10 12 14 16 18 20
Number of agents

30(a) Makespan2530(b) Runtime

Figure 3: Comparison of SBDA and HTE (Env. 1)

70000

HTE
SBDA (α = 0)
SBDA (α = 4)
SBDA (α = 8)
SBDA (α = 12)

60000
50000

Runtime [s]Parameter

MakespanDescription

Makespan

35000

Runtime [s]Table 1: Parameter values used in the experiments

40000
30000
20000
2 4 6 8 10 12 14 16 18 20
Number of agents(a) Makespan

25

30

40
35
30
25
20
15
10
5
0

HTE
SBDA (α = 0)
SBDA (α = 4)
SBDA (α = 8)
SBDA (α = 12)

2 4 6 8 10 12 14 16 18 20
Number of agents

2530(b) Runtime

Figure 4: Comparison of SBDA and HTE (Env. 2)(a) Environment 1

only load their materials, and the purple squares are the delivery
locations where agents can only unload their materials. The initial locations of the agents are randomly assigned to the parking
nodes, which are expressed by the red squares in both environments. One hundred tasks are initially generated by randomly selecting pickup and/or delivery locations from the blue, orange, andpurple squares according to the experimental setting, and added to
the T . Note that Envs. 1 and 2 are not clearly bi-connected.
To evaluate our proposed method, we measured the makespan,i.e., the time required to complete all tasks in T , and the runtime,i.e., the total CPU time for task selection, destination decision, andpath planning for all tasks by all agents. Makespan indicates thetransportation efficiency, whereas the runtime indicates the planning efficiency. Other parameter values are shown in Table 1. We
conducted our experiments on a 3.00-GHz Intel 8-Core Xeon E5
with 64 GB of RAM. The experiment results below are the average of 50 trials with different random seeds. Sample videos of
our experiments can be found at https://youtube.com/playlist?list=
PLKufA_6vumDU01_hYNWihEN4IGlTh_oZ8.

(b) Environment 2

Figure 2: Experiment environments (red, parking nodes;
blue, task endpoints; orange, pickup only locations; purple,
delivery only locations; hollow green, nodes; black, edges)

5 EXPERIMENTS AND DISCUSSION
5.1 Experiment Setting
To evaluate the performance of our proposed method for executing the MAPD problem, we conducted the experiments under two
different environments and compared the results with those using
HTE as a baseline. In HTE, the agent selects the task whose loading and unloading nodes do not overlap with other endpoints oftasks that are currently being executed by other agents and whose
loading node is the closest to the current node, vci . Then, the agent
generates the path to the loading node, followed by the path fromthe loading node to the unloading node of the task. If it cannot select such a task, it returns to the parking node. We used the spacetime A∗ as the path finding algorithm for both methods, whichis also used in TP. The first environment (Env. 1) is a maze-likeenvironment with few task endpoints (|Vtsk | = 6), assuming a construction site (Fig. 2a). Nodes are set at the intersections and endsof the edges. Agents can rotate, wait, and load/unload materials
only at nodes. Task endpoints are expressed by the blue squares
in Fig. 2a, where agents can both load and unload their materials.
A break in the edge in this figure indicates the length of a block
having a length of 1.
The second environment (Env. 2) is also a maze-like environment with fewer task endpoints (|Vtsk | = 8), and the number ofpickup/delivery locations is skewed, as shown in Fig. 2b. In thisfigure, orange squares are the pickup locations in which agents can

5.2

Exp. 1: Performance Comparison

In the first experiment (Exp. 1), we compared the performances ofour proposed SBDA method and the baseline HTE under Envs. 1
and 2. We plotted the results of Env. 1 in Fig. 3. We focus particularly on the results when α = 8, which exhibited the highest
transportation efficiency (a detailed discussion of the effect of theparameter α of SBDA is given in Section 5.3).
Figure 3a indicates that SBDA significantly reduces the makespancompared to the HTE method. In particular, when the number of
agents is M = 8, SBDA reduces the makespan of HTE by approximately 39%. In HTE, agents cannot simultaneously execute tasks
that have the same endpoint. Hence, only three or four agents can
execute tasks in parallel even if M is larger because |Vt sk | = 61432

Main Track

AAMAS 2022, May 9–13, 2022, Online

crowded (Cond. 1 (1)), resulting in an increase in the parallelism
during the task executions and a decrease of the makespan.
However, when α was too large, such as α = 12, the makespanworsened. There seem to be three possible reasons for this. First,
too much parallelism in a task execution causes congestion in theenvironment, leading to larger waiting times and longer detours.
In SBDA, agents need to move toward their destinations without
passing through the standby nodes. Although the connectivity of
the graph G t is maintained because of the property of the standby
nodes, if more nodes in G t are eliminated, the paths to the endpoints will be lengthened and the agents will be forced to make significant detours, resulting in long wait times at the standby nodes.
As the second reason, the agents have to remain in standby nodes
far from their task endpoints. Hence, when an agent starts toward
an endpoint, the endpoint is exclusively held for a slightly longer
period of time until the agent arrives, resulting in a chain reactionof reduced transportation efficiency. Finally, because more agentscan fulfill their tasks, local congestion is likely to occur, particularly biasing the destinations.
We can also see from Figs. 3a and 4a that the number of agentsfor achieving the highest efficiency depends on the value of α aswell as the structure of the environment. However, it seems thatin all cases, except for α = 0 in Env. 2, SBDA exhibited a better
performance than HTE for M ≥ 4. Note that under Env. 2, theperformance was the highest when M = 10 - 12, which is slightly
larger than that of Env. 1, and did not decrease significantly whenM > 12, unlike the performance under Env. 1 when M > 8. Thisis because Env. 2 has only two pickup locations, which are thus
more prone to localized congestion than Env. 1. Nevertheless, as
the number of agents increases, Cond. 1 (2) of task selection cansteer agents to tasks whose pickup nodes are less crowded and ultimately eliminate the congestion bias, thus reducing the makespan.
In particular, this effect appeared more strongly under Env. 2 thanunder Env. 1, and thus, Cond. 1 (2) can prevent the agents fromentering too much of the work area, averting a loss in efficiency.
If we look at Figs. 3b and 4b, the runtime required for planningis quite large when α = 0 and M is between 6 and 10 under Env. 1
and when M ≥ 4 under Env. 2, although the number of agentsmoving in the work area seemed small. This may be because agentsin the parking nodes frequently probe for a possible task selection,
whereas agents with tasks do not do so.

under Env. 1. By contrast, because multiple agents can simultaneously execute tasks whose loading and unloading nodes overlapping with other executing tasks by using the standby nodes effectively, SBDA considerably improves the makespan through thehigher parallelism of the task executions. As an exception, when
M = 2, the makespan of SBDA is higher than that of HTE because
when M is extremely small compared to the number of task endpoints |Vt sk |, agents can easily find tasks whose endpoints do not
overlap and can always execute pickup-and-delivery tasks simultaneously without considering the standby nodes.
Figure 3b shows that the runtime for SBDA slightly increases
compared to HTE. The only CPU usage in HTE comes from thetask selection and path planning that generate a collision-free pathin the less crowded environment. Hence, even if the number of
agents increases, the runtime does not significantly increase, andis only used for a confirmation of the task selection. Meanwhile,in SBDA, many agents can select the tasks to execute and generatemany paths mainly to endpoints and standby nodes, thus increasing the runtime. However, considering the parallel behavior, theCPU time spent per agent is not large.
The experiment results under Env. 2, which is plotted in Fig. 4,
indicate that SBDA can improve the performance much more thanHTE, and the length of the makespan, i.e., the average time required to complete the MAPD instances, is less than half that of
HTE. For example, when M = 10, SBDA reduces the makespan ofHTE by approximately 53%, which is a larger improvement thanthat under Env. 1. Because there are only two loading nodes, thenumber of agents working simultaneously is limited in HTE, andthe makespan remains high. For SBDA, instead of many agentsmoving toward a small number of loading locations without any
control, the agents can automatically wait at the standby nodes
close to the loading nodes and move there in turn, which can increase the number of agents working at the same time. Furthermore, because Cond. 1 prevents too many agents from entering
the work area, and Cond. 2 prevents the agents from ignoring theagents waiting at the standby nodes and cutting in to move toward
the endpoint first, such conditions prevent excessive congestion,and thus contribute to the high efficiency.

5.3

Exp. 2: Features of SBDA

We conducted a number of experiments to confirm the impact ofparameter α, which limits the distance between standby nodes andthe endpoint v tsk under Exp. 1, and then, Cond. 1 through an ablation study in the second experiment (Exp. 2). We also report theeffect of Cond. 2 elsewhere [36].

5.3.2 Ablation study. Focusing on Cond. 1 of the task selection(Section 4.3), we compared SBDA with SBDA without Cond. 1 (1)(SBDA-w/o-1), SBDA without Cond. 1 (2) (SBDA-w/o-2), and SBDA
without Cond. 1 (3) (SBDA-w/o-3) as an ablation study to verify theeffect of each condition. Figs. 5 and 6 show the comparative resultsof SBDA and ablation methods under Env. 1 and Env. 2, respectively. First, from Fig. 5a, the makespan of SBDA-w/o-1 was almost
the same as that of SBDA under M ≤ 10, whereas the makespanincreased as M increased after M = 12, particularly under Env. 1.
This indicates that Cond. 1 (1) contributed significantly to preventing many agents from entering the work area and crowding it. Under Env. 2, there are only two pickup nodes, and Cond. 1 (2) also
prevents agents from entering the crowded work area; thus, themakespan did not increase significantly. This analysis also supports the fact that the runtime of SBDA-w/o-1 rapidly increases

5.3.1 Impact of parameter α. First, to analyze the features of SBDA
in Exp. 1, we examined the impact of the parameter α on the performance. We conducted the same experiments under Envs. 1 and
2 with values of α = 0, 4, 8, and 12. The results are also shown in
Figs. 3 and 4. From Figs. 3a and 4a, the makespan of both environments decreases as the value of α increases from zero to 8, andconversely, increases when α = 12. The larger the value of α, thelarger the number of associated potential standby nodes for eachtask endpoint. This means that (2) and (3) in Cond. 1 of the task selection (Section 4.3) are more easily satisfied. Hence, more agentsleft their parking nodes as long as the environment was not too

1433

Makespan

40000

SBDA
SBDA-w/o-1
SBDA-w/o-2
SBDA-w/o-3

35000
30000
25000
20000
15000
2 4 6 8 10 12 14 16 18 20
Number of agents

25

80
70
60
50
40
30
20
10
0

30

Operational time per task

AAMAS 2022, May 9–13, 2022, Online

Runtime [s]Main Track

SBDA
SBDA-w/o-1
SBDA-w/o-2
SBDA-w/o-3

2 4 6 8 10 12 14 16 18 20
Number of agents(a) Makespan

25

3000

SBDA
SBDA-w/o-1
SBDA-w/o-2
SBDA-w/o-3

2400
1800
1200
600

2 4 6 8 10 12 14 16 18 20
Number of agents

30(b) Runtime

2530(c) Operational time

100
SBDA
SBDA-w/o-1
SBDA-w/o-2
SBDA-w/o-3

60000

80
Runtime [s]Makespan

70000

50000
40000

60

Operational time per task

Figure 5: Ablation study with task selection conditions (Env. 1)
SBDA
SBDA-w/o-1
SBDA-w/o-2
SBDA-w/o-3

40
20

30000

0

20000
2 4 6 8 10 12 14 16 18 20
Number of agents(a) Makespan2530

2 4 6 8 10 12 14 16 18 20
Number of agents

2530(b) Runtime

2400
2100
1800
SBDA
SBDA-w/o-1
SBDA-w/o-2
SBDA-w/o-3

1500
1200
2 4 6 8 10 12 14 16 18 20
Number of agents2530(c) Operational time

Figure 6: Ablation study with task selection conditions (Env. 2)
to temporarily remain at free potential standby nodes or parking
nodes with carrying the materials. Such interruptions in task execution lengthened the operation time.

(Figs. 5b and 6b). Second, the minimum values of the makespan of
SBDA-w/o-2 and SBDA-w/o-3 were larger than those of SBDA. If
Cond. 1 (2) or (3) was removed, the agent selected a task without
considering the status of the load or unload node or the associated potential standby nodes, resulting in a temporary evacuation
when heading toward the load or unload node. However, this did
not frequently occur in SBDA.
In Figs. 5c and 6c, we also plot the operational time per task or
simply the operational time, which is the average time required
to complete one task. In general, as the parallelism increases, theenvironment becomes more crowded and the operational time increases. However, SBDA-w/o-2 has the smallest value under Env. 1(Fig. 5c). Because Cond. 1 (2) was ineffective, many agents evacuated the free potential standby nodes and CL was likely to be nonempty. As the results indicate, Cond. 1 (1) limited the number of
agents entering the work area, reducing the parallelism. However,in Env. 2, the operational time of SBDA-w/o-2 increased because
the agents had to stay at the free potential standby nodes much
longer because of the limited number of loading nodes. Moreover,this also occurred because, by removing Cond. 1 (2), the agents always selected the tasks with the closest loading nodes without considering congestion; in particular, the agents in the parking nodes
were biased toward to the upper-left loading node under Env. 2. Inother cases, i.e., in SBDA-w/o-1 and SBDA-w/o-3, the operationaltime was large because too many agents entered the work area.
Finally, Figs. 5c and 6c show that the operational time of SBDAw/o-3 tended to be large under both environments. Through theremoval of Cond. 1 (3), the agents were likely to select tasks without considering the status of the unload nodes. Hence, they could
not move to the unload nodes or their associated potential standby
nodes after the load was completed and were repeatedly forced

6

CONCLUSION

We presented a deadlock avoidance method, called SBDA, for the
MAPD problem to improve the transportation efficiency even ina maze-like environment. The central idea of SBDA is the use ofstandby nodes in which, even if an agent stays there, the connectivity of the environment remains. Furthermore, standby nodes canbe identified with a low computational cost using the articulationpoint-finding algorithm used in graph theory and are thereby foundin real-time. SBDA guarantees completeness for well-formed MAPD
instances by effectively using standby nodes that are guaranteed
to wait for any finite amount of time. We evaluated the proposed
method in comparison with a well-known conventional method,
HTE, in restricted maze-like environments based on our envisioned
applications. Our experiment results demonstrated that SBDA considerably outperforms the conventional method. We also analyzed
the features of our proposed method and observed that the parallelism of the task execution can be controlled by changing thevalue of α, the parameter used for selecting standby nodes, andthat the transportation efficiency can be significantly improved byappropriately setting the value of α.
To improve the flexibility and usability of SBDA for real-world
applications, we plan to study a method for determining the appropriate value of α from a graph structure.

ACKNOWLEDGMENTS
This work was partly supported by JSPS KAKENHI Grant Numbers
20H04245 and 17KT0044.

1434

Main Track

AAMAS 2022, May 9–13, 2022, Online

REFERENCES[19] Zhenbang Nie, Peng Zeng, and Haibin Yu. 2020. Effective Decoupled Planning
for Continuous Multi-Agent Pickup and Delivery. In 2020 Chinese Control And
Decision Conference (CCDC). IEEE, 2667–2672.
[20] Esko Nuutila and Eljas Soisalon-Soininen. 1994. On finding the strongly connected components in a directed graph. Inform. Process. Lett. 49, 1 (1994), 9–14.
https://doi.org/10.1016/0020-0190(94)90047-7[21] Keisuke Okumura, Manao Machida, Xavier Défago, and Yasumasa Tamura. 2019.
Priority Inheritance with Backtracking for Iterative Multi-agent Path Finding.
In Proceedings of the Twenty-Eighth International Joint Conference on Artificial
Intelligence, IJCAI-19. International Joint Conferences on Artificial Intelligence
Organization, 535–542. https://doi.org/10.24963/ijcai.2019/76[22] Keisuke Okumura, Yasumasa Tamura, and Xavier Défago. 2019. winPIBT: Extended Prioritized Algorithm for Iterative Multi-agent Path Finding. arXiv
preprint arXiv:1905.10149 (2019).
[23] Keisuke Okumura, Yasumasa Tamura, and Xavier Défago. 2021.
TimeIndependent Planning for Multiple Moving Agents. In Proceedings of the AAAI
Conference on Artificial Intelligence, Vol. 35. 11299–11307.
[24] Zhongqiang Ren, Sivakumar Rathinam, and Howie Choset. 2021. MS*: A New
Exact Algorithm for Multi-agent Simultaneous Multi-goal Sequencing and Path
Finding. arXiv preprint arXiv:2103.09979 (2021).
[25] Zhongqiang Ren, Sivakumar Rathinam, and Howie Choset. 2021. Multiobjective Conflict-based Search Using Safe-interval Path Planning. arXiv
preprint arXiv:2108.00745 (2021).
[26] D Reed Robinson, Robert T Mar, Katia Estabridis, and Gary Hewer. 2018. An efficient algorithm for optimal trajectory generation for heterogeneous multi-agent
systems in non-convex environments. IEEE Robotics and Automation Letters 3, 2
(2018), 1215–1222.
[27] Oren Salzman and Roni Stern. 2020. Research Challenges and Opportunities
in Multi-Agent Path Finding and Multi-Agent Pickup and Delivery Problems.
In Proceedings of the 19th International Conference on Autonomous Agents andMultiAgent Systems. 1711–1715.
[28] Guni Sharon, Roni Stern, Ariel Felner, and Nathan R. Sturtevant. 2015. Conflictbased search for optimal multi-agent pathfinding. Artificial Intelligence 219(2015), 40–66. https://doi.org/10.1016/j.artint.2014.11.006[29] Haseeb Tahir, Mujahid N Syed, and Uthman Baroudi. 2019. Heuristic approachfor real-time multi-agent trajectory planning under uncertainty. IEEE Access 8(2019), 3812–3826.
[30] Robert Tarjan. 1972. Depth-first search and linear graph algorithms. SIAM journal on computing 1, 2 (1972), 146–160. https://doi.org/10.1137/0201010[31] Manuela Veloso, Joydeep Biswas, Brian Coltin, and Stephanie Rosenthal. 2015.
CoBots: Robust Symbiotic Autonomous Mobile Service Robots. In Proceedingsof the 24th International Conference on Artificial Intelligence (Buenos Aires, Argentina) (IJCAI’15). AAAI Press, 4423–4429.
[32] Hanlin Wang and Michael Rubenstein. 2020. Walk, Stop, Count, and Swap: Decentralized Multi-Agent Path Finding With Theoretical Guarantees. IEEE Robotics and Automation Letters 5, 2 (2020), 1119–1126. https://doi.org/10.1109/LRA.
2020.2967317[33] Ko-Hsin Cindy Wang and Adi Botea. 2011. MAPP: a scalable multi-agent path
planning algorithm with tractability and completeness guarantees. Journal of
Artificial Intelligence Research 42 (2011), 55–90.
[34] Peter R Wurman, Raffaello D’Andrea, and Mick Mountz. 2008. Coordinating
hundreds of cooperative, autonomous vehicles in warehouses. AI magazine 29,
1 (2008), 9–9. https://doi.org/10.1609/aimag.v29i1.2082[35] Tomoki Yamauchi, Yuki Miyashita, and Toshiharu Sugawara. 2021. Path andAction Planning in Non-uniform Environments for Multi-agent Pickup and Delivery Tasks. In European Conference on Multi-Agent Systems. Springer, 37–54.
https://doi.org/10.1007/978-3-030-82254-5_3[36] Tomoki Yamauchi, Yuki Miyashita, and Toshiharu Sugawara. 2022. StandbyBased Deadlock Avoidance Method for Multi-Agent Pickup and Delivery Tasks.
arXiv preprint arXiv:2201.06014 (2022).
[37] Naoki Yoshida, Itsuki Noda, and Toshiharu Sugawara. 2020. Multi-agent Service
Area Adaptation for Ride-Sharing Using Deep Reinforcement Learning. In International Conference on Practical Applications of Agents and Multi-Agent Systems.
Springer, 363–375. https://doi.org/10.1007/978-3-030-49778-1_29[38] Han Zhang, Jiaoyang Li, Pavel Surynek, Sven Koenig, and TK Satish Kumar.
2020. Multi-Agent Path Finding with Mutex Propagation. In Proceedings of theInternational Conference on Automated Planning and Scheduling, Vol. 30. 323–
332.

[1] Matteo Bellusci, Nicola Basilico, and Francesco Amigoni. 2020. Multi-Agent Path
Finding in Configurable Environments. In Proceedings of the 19th International
Conference on Autonomous Agents and MultiAgent Systems. 159–167.
[2] Eli Boyarski, Ariel Felner, Roni Stern, Guni Sharon, David Tolpin, Oded Betzalel, and Eyal Shimony. 2015. ICBS: improved conflict-based search algorithm
for multi-agent pathfinding. In Twenty-Fourth International Joint Conference on
Artificial Intelligence.
[3] Eli Boyrasky, Ariel Felner, Guni Sharon, and Roni Stern. 2015. Don’t split, try
to work it out: bypassing conflicts in multi-agent pathfinding. In Twenty-Fifth
International Conference on Automated Planning and Scheduling.
[4] Michal Čáp, Jiří Vokřínek, and Alexander Kleiner. 2015. Complete decentralized method for on-line multi-robot trajectory planning in well-formed infrastructures. In Twenty-Fifth International Conference on Automated Planning and
Scheduling. 324–332.
[5] Mehul Damani, Zhiyao Luo, Emerson Wenzel, and Guillaume Sartoretti. 2021.
PRIMAL2 : Pathfinding Via Reinforcement and Imitation Multi-Agent LearningLifelong. IEEE Robotics and Automation Letters 6, 2 (2021), 2666–2673.
[6] Harshal S Dewang, Prases K Mohanty, and Shubhasri Kundu. 2018. A robust path
planning for mobile robot using smart particle swarm optimization. Procedia
computer science 133 (2018), 290–297.
[7] Ariel Felner, Roni Stern, Solomon Eyal Shimony, Eli Boyarski, Meir Goldenberg, Guni Sharon, Nathan Sturtevant, Glenn Wagner, and Pavel Surynek. 2017.
Search-based optimal solvers for the multi-agent pathfinding problem: Summary and challenges. In Tenth Annual Symposium on Combinatorial Search.
[8] Taoan Huang, Bistra Dilkina, and Sven Koenig. 2021. Learning Node-Selection
Strategies in Bounded-Suboptimal Conflict-Based Search for Multi-Agent Path
Finding. In Proceedings of the 20th International Conference on Autonomous
Agents and MultiAgent Systems. 611–619.
[9] Rahul Kala. 2012. Multi-robot path planning using co-evolutionary genetic programming. Expert Systems with Applications 39, 3 (2012), 3817–3831.
[10] Daniel Krakowczyk, Jannik Wolff, Alexandru Ciobanu, Dennis Julian Meyer, andChristopher-Eyk Hrabia. 2018. Developing a Distributed Drone Delivery Systemwith a Hybrid Behavior Planning System. In Joint German/Austrian Conferenceon Artificial Intelligence (Künstliche Intelligenz). Springer, 107–114.
[11] Jiaoyang Li, Andrew Tinka, Scott Kiesel, Joseph W Durham, TK Satish Kumar,and Sven Koenig. 2021. Lifelong Multi-Agent Path Finding in Large-Scale Warehouses. In Proceedings of the AAAI Conference on Artificial Intelligence, Vol. 35.
11272–11281.
[12] Minne Li, Zhiwei Qin, Yan Jiao, Yaodong Yang, Jun Wang, Chenxi Wang, Guobin
Wu, and Jieping Ye. 2019. Efficient Ridesharing Order Dispatching with Mean
Field Multi-Agent Reinforcement Learning. In The World Wide Web Conference.
ACM, 983–994. https://doi.org/10.1145/3308558.3313433[13] Minghua Liu, Hang Ma, Jiaoyang Li, and Sven Koenig. 2019. Task and Path Planning for Multi-Agent Pickup and Delivery. In Proceedings of the 18th International
Conference on Autonomous Agents and MultiAgent Systems. International Foundation for Autonomous Agents and Multiagent Systems, 1152–1160.
[14] Hang Ma, Wolfgang Hönig, TK Satish Kumar, Nora Ayanian, and Sven Koenig.
2019. Lifelong Path Planning with Kinematic Constraints for Multi-Agent
Pickup and Delivery. In Proceedings of the AAAI Conference on Artificial Intelligence, Vol. 33. 7651–7658. https://doi.org/10.1609/aaai.v33i01.33017651[15] Hang Ma, Sven Koenig, Nora Ayanian, Liron Cohen, Wolfgang Hönig, TK Kumar, Tansel Uras, Hong Xu, Craig Tovey, and Guni Sharon. 2017. Overview: Generalizations of multi-agent path finding to real-world scenarios. arXiv preprint
arXiv:1702.05515 (2017).
[16] Hang Ma, Jiaoyang Li, TK Kumar, and Sven Koenig. 2017. Lifelong multi-agent
path finding for online pickup and delivery tasks. In Proceedings of the 16th Conference on Autonomous Agents and MultiAgent Systems. International Foundation
for Autonomous Agents and Multiagent Systems, 837–845.
[17] Hang Ma, Craig Tovey, Guni Sharon, TK Satish Kumar, and Sven Koenig. 2016.
Multi-agent path finding with payload transfers and the package-exchange
robot-routing problem. In Thirtieth AAAI Conference on Artificial Intelligence.
[18] Robert Morris, Corina S Pasareanu, Kasper Luckow, Waqar Malik, Hang Ma,
TK Satish Kumar, and Sven Koenig. 2016. Planning, scheduling and monitoring
for airport surface operations. In Workshops at the Thirtieth AAAI Conference on
Artificial Intelligence.

1435