# DMAPF: A Decentralized and Distributed Solver for Multi-Agent Path Finding
Problem with Obstacles

Poom Pianpak Tran Cao Son New Mexico State University
Las Cruces, New Mexico, USA<EMAIL_ADDRESS>
###### Abstract

_Multi-Agent Path Finding_ (MAPF) is a problem of finding a sequence of
movements for agents to reach their assigned location without collision.
Centralized algorithms usually give optimal solutions, but have difficulties
to scale without employing various techniques – usually with a sacrifice of
optimality; but solving MAPF problems with the number of agents greater than a
thousand remains a challenge nevertheless. To tackle the scalability issue, we
present _DMAPF_ – a decentralized and distributed MAPF solver, which is a
continuation of our recently published work, _ros-dmapf_ [11]. We address the
issues of _ros-dmapf_ where it (i) only works in maps without obstacles; and
(ii) has a low success rate with dense maps. Given a MAPF problem, both _ros-
dmapf_ and _DMAPF_ divide the map spatially into subproblems, but the latter
further divides each subproblem into disconnected regions called areas. Each
subproblem is assigned to a distributed solver, which then individually
creates an abstract plan – a sequence of areas that an agent needs to visit –
for each agent in it, and interleaves agent migration with movement planning.
_Answer Set Programming_ , which is known for its performance in small but
complex problems, is used in many parts including problem division, abstract
planning, border assignment for the migration, and movement planning. _Robot
Operating System_ is used to facilitate communication between the solvers and
to enable the opportunity to integrate with robotic systems. _DMAPF_
introduces a new interaction protocol between the solvers, and mechanisms that
together result in a higher success rate and better solution quality without
sacrificing much of the performance. We implement and experimentally validate
_DMAPF_ by comparing it with other state-of-the-art MAPF solvers and the
results show that our system achieves better scalability.

##  1 Introduction

Robots have been making their way into human life. From household robots to
self-driving cars and industrial robots, it is expected that the number of
robots will keep increasing in the future. To cope with such growth, robot
controlling systems need to be designed with scalability in mind. We took an
inspiration from autonomous warehouse
systems111https://amazonrobotics.com,222https://locusrobotics.com where the
retrieval and storage tasks are done autonomously by mobile robots. When the
system receives an order, it assigns a set of robots to retrieve shelves
containing the products to a human operator for fulfillment of the order, then
store the shelves back in their appropriate place.

In this paper, we only consider the problem of finding a plan for agents to
reach their assigned location (i.e., goal) without collision. The problem is
called _Multi-Agent Path Finding_ (MAPF) and will be formally introduced in
Section 2.1. Most existing MAPF algorithms are centralized (i.e., having a
central unit overseeing the entire solving process) such as _WHCA*_ [14],
_asprilo_ [7], and _CBS_ [13]. While there are attempts to improve the
scalability of centralized algorithms using various techniques, such as
abstraction (e.g., planning for each agent independently then combine the
partial plans to obtain the solution – while resolving any conflict), dealing
with MAPF problems with a large number of agents (greater than a thousand)
still remains a challenge. We have designed a decentralized and distributed
MAPF algorithm, named _DMAPF_ – Distributed Multi-Agent Pathfinder – with
scalability in mind. _DMAPF_ is able to take advantage of distributed
computing to cope with the possibility of having an ever-increasing problem
size. An input problem to _DMAPF_ is encoded in _answer set program_ as
generated by the _ASPRILO_ project [7] and solved using mainly the _answer set
programming_ , which will be introduced in Section 2.2. The communication
between distributed components in _DMAPF_ is facilitated by the _Robot
Operating System_ (ROS), which will be introduced in Section 2.3.

_DMAPF_ is an improvement over our original system, _ros-dmapf_ [11]. We
address the issues in _ros-dmapf_ where it (i) only works in maps without
obstacles; and (ii) has a low success rate with dense maps. _DMAPF_ shares the
same idea with _ros-dmapf_ in that, given a MAPF problem, it divides the
problem spatially and assigns each divided subproblem to a distributed solver,
which is a ROS node. The difference is that _DMAPF_ also further divides each
subproblem into disconnected regions called areas. This, together with a few
other changes, allow _DMAPF_ to deal with having obstacles. The details of
problem division will be explained in Secion 3.1. After the subproblems have
been distributed, each solver individually creates an abstract plan – a
sequence of areas that an agent needs to visit to reach the area that contains
its goal – for each agent in the given subproblem. The details of abstract
plan creation will be explained in Section 3.2.1. After the plans have been
made for every agent, the solvers interleave communicating with neighboring
solvers to send/receive migrating agents (details in Sections 3.2.2, 3.2.3,
and 3.2.5) with movement planning (details in Section 3.2.4) along each round.
This differs from _ros-dmapf_ where it does the communication from beginning
to end first, then finds a movement plan for each round in a single attempt.
If _ros-dmapf_ is unable to make a plan during the movement planning phase, it
would be difficult to adjust the border assignment since assignments for the
next rounds have already been agreed upon, whereas _DMAPF_ can easily adjust
the assignment and retry. This, together with changes in migration protocol,
allow _DMAPF_ to achieve a higher success rate and better solution quality
than _ros-dmapf_. _DMAPF_ has been implemented and compared with other state-
of-the-art solvers. Section 4 shows results of the comparison. Section 5
concludes with discussion on the results, advantages, limitations, and future
work.

##  2 Background

###  2.1 Multi-Agent Path Finding Problem

A _Multi-Agent Path Finding_ (MAPF) problem can be defined as a quadruple
$P=(G,A,S,T)$, where $G=(V,E)$ is a graph such that $V$ is a set of vertices
corresponding to locations in the graph, and $E\subseteq V\times V$ denotes
edges between two locations; $A$ is a set of agents; and $S\subseteq A\times
V$ and $T\subseteq A\times V$ denote start and goal locations of the agents,
respectively.

Agents can move from $v_{\\_}1$ to $v_{\\_}2$ where $v_{\\_}1,v_{\\_}2\in V$
if $(v_{\\_}1,v_{\\_}2)\in E$, under the restrictions: (a) two agents cannot
swap locations in a single time step; and (b) each location can be occupied by
at most one agent at a time. A path for an agent $a$ is a sequence of vertices
$\alpha_{\\_}a=\langle v_{\\_}1,\ldots,v_{\\_}n\rangle$ if (i) agent $a$
starts at $v_{\\_}1$ (i.e., $(a,v_{\\_}1)\in S$); and (ii) there is an edge
between any two subsequent vertices $v_{\\_}i$ and $v_{\\_}{i+1}$ (i.e.,
$(v_{\\_}i,v_{\\_}{i+1})\in E$), or they are the same vertex (i.e.,
$v_{\\_}{i+1}=v_{\\_}{i}$). An agent $a$ completes its order
$T_{\\_}a=\\{v\mid(a,v)\in T\\}$ via a path $\alpha_{\\_}a=\langle
v_{\\_}1,\ldots,v_{\\_}n\rangle$ if
$T_{\\_}a\subseteq\\{v_{\\_}1,\ldots,v_{\\_}n\\}$. A _solution_ of a MAPF
problem $P$ is a collection of paths $Sol=\\{\alpha_{\\_}a\mid a\in A\\}$ such
that all orders in $T$ are completed.

In our work, we assume that (i) each agent has a different start location
(i.e., $\forall_{\\_}{a}\exists_{\\_}{v}((a\in A\to(a,v)\in
S)\land\neg\exists_{\\_}{\hat{v}\neq v}((a,\hat{v})\in
S))\land\neg\exists_{\\_}{\hat{a}\neq a}((\hat{a},v)\in S))$); (ii) each agent
either has no goal or has a distinct goal location (i.e.,
$\forall_{\\_}{a_{\\_}1,a_{\\_}2,v}((a_{\\_}1,v),(a_{\\_}2,v)\in T\to
a_{\\_}1=a_{\\_}2)$); (iii) each agent is at its goal at the last time step
(i.e., $\forall_{\\_}{a,v}(((a,v)\in T\land\alpha_{\\_}a=\langle
v_{\\_}1,\ldots,v_{\\_}n\rangle)\to v=v_{\\_}n)$); and (iv) the graph is grid-
based. These assumptions are common among most multi-agent path finding
solvers.

###  2.2 Answer Set Programming

Let us provide some general background on _Answer Set Programming_ (ASP).
Consider a logic language $L=\langle C,P,V\rangle$, where $C,P,V$ are sets of
constants, predicate symbols, and variables, respectively, and the notions of
terms, atoms, and literals are traditional.

An _answer set program_ $\Pi$ is a set of _rules_ of the form

$c\leftarrow a_{\\_}1,\ldots,a_{\\_}m,not\>\>b_{\\_}1,\ldots,not\>\>b_{\\_}n$
(1)

Each $a_{\\_}i$ and $b_{\\_}i$ is a literal from $L$, and each
$not\>\>b_{\\_}i$ is called a negation-as-failure literal (or naf-literal).
$c$ can be a literal or omitted. A program is a positive program if it does
not contain naf-literals. A _non-ground rule_ is a rule that contains
variables; otherwise, it is called a _ground rule_. A rule with variables is
simply used as a shorthand for the set of its ground instances from the
language $L$. If $n=m=0$, then the rule is called a _fact_. If $c$ is omitted,
then the rule is called an _ASP constraint_.

A set of ground literals $X$ is _consistent_ if there is no atom $a$ such that
$\\{a,\neg a\\}\subseteq X$. A literal $l$ is true (resp. false) in a set of
literals $X$ if $l\in X$ (resp. $l\not\in X$). A set of ground literals $X$
satisfies a ground rule of the form (1) if either of the following is true:
(i) $c\in X$; (ii) some $a_{\\_}i$ is false in $X$; or (iii) some $b_{\\_}i$
is true in $X$. A solution of a program, called an _answer set_ [8], is a
consistent set of ground literals satisfying the following conditions:

  * •

If $\Pi$ is a _ground program_ (i.e., a program whose rules are all ground),
then its answer set $S$ is defined by the following:

    * $\circ$

If $\Pi$ does not contain any naf-literals, then $S$ is an answer set of $\Pi$
if it is a consistent and subset-minimal set of ground literals satisfying all
rules in $\Pi$.

    * $\circ$

If $\Pi$ contains some naf-literals, then $S$ is an answer set of $\Pi$ if it
is an answer set of the _program reduct_ $\Pi^{S}$. $\Pi^{S}$ is obtained from
$\Pi$ by deleting (i) each rule that has a naf-literal _not_ $b$ in its body
with $b\in S$; and (ii) all naf-literals in the bodies of the remaining rules.

  * •

If $\Pi$ is a _non-ground program_ (i.e., a program whose rules include non-
ground rules), then $S$ is an answer set of $\Pi$ if it is an answer set of
the program consisting of all ground instantiations of the rules in $\Pi$.

The ASP language includes also language-level extensions to facilitate the
encoding of aggregates ($min$, $max$, $sum$, etc.), range specification of
variables, and allowing choice of literals. In ASP, one solves a problem by
encoding it as an ASP program whose answer sets correspond one-to-one to the
solutions of the problem [9, 10]. Answer sets of ASP programs can be computed
using ASP solvers like clasp [6] and dlv [4].

Early ASP rests upon a single-shot approach to problem solving – an ASP solver
takes a logic program, computes its answer sets, and exits. Unlike this,
recently developed multi-shot ASP solvers provide operative solving processes
for dealing with continuously changing logic programs. For controlling such
solving processes, the declarative approach of ASP is combined with imperative
means. In clingo [5], this is done by augmenting an ASP encoding with C or
Python procedures. The instrumentation includes methods for adding/grounding
rules, setting truth values of (external) atoms, computing the answer sets of
current program, etc.

###  2.3 Robot Operating System

The _Robot Operating System_ (ROS) is an open-source framework designed for
building robotics systems which is distributed in nature [12]. We adopt ROS
because of its scalability and support for the development of heterogeneous
clusters of software. ROS provides client libraries333Visit
http://wiki.ros.org/Client%20Libraries for a full list of ROS client libraries
for software written in different languages (e.g., C++, Python, Lisp) to
communicate.

A ROS system must consist of a _roscore_ at a bare minimum, and may consist of
multiple _ROS nodes_. A roscore is a set of prerequisites to run a ROS-based
system, and it consists of a _ROS master_ among a few other things. A ROS node
is an individual process that does some computation. ROS nodes working
together for a particular task may be organized as a _package_ , and they can
be on different networks. For a node $n_{\\_}1$ to communicate with another
node $n_{\\_}2$, $n_{\\_}1$ first needs to locate $n_{\\_}2$ via the ROS
master, then $n_{\\_}1$ can communicate directly with $n_{\\_}2$ as a peer-to-
peer network. There are mainly two forms of communication between ROS nodes:

  1. 1.

_Publish-Subscribe_ – nodes are connected via a _topic_ , which is a named
bus. A node sending (resp. listening to) messages on a topic is called a
_publisher_ (resp. _subscriber_). One node can both be a publisher and a
subscriber on the same or multiple topics. A topic may have zero or more
publishers and/or subscribers.

  2. 2.

_Request-Response_ – two nodes follow an RPC interaction through a _service_.
A node that provides (resp. calls) a service is called a _service server_
(resp. _service client_). There can only be one service server, but possibly
multiple service clients for a single service. Calls from the service clients
will be put into a queue and processed one-by-one.

##  3 Methodology

Algorithm 1 shows an overview of _DMAPF_. The algorithm takes a MAPF problem
$P$ and the dimension $dx\times dy$ of desired subproblems as inputs, and
produces the solution if it could find one. Line 1 divides the given problem
$P$ into smaller subproblems: $P_{\\_}1,\dots,P_{\\_}n$, and provides the
$Links$ information telling which pairs of _areas_ within the subproblems are
_connected_ (i.e., there exists some border between them). This step will be
explained in Section 3.1. The problem can also be divided by hand as _DMAPF_
does not put restrictions on how the subproblems have to be divided, i.e.,
they do not have to be rectangles of dimension $dx\times dy$. Lines 2-4 create
solvers $s_{\\_}1,\dots,s_{\\_}n$ as _ROS nodes_ with the divided subproblem
$P_{\\_}i$ as their input. How the solvers work together, which is the core of
the algorithm, will be explained in Section 3.2. Solver $s_{\\_}1$ has an
extra responsibility, besides solving its own subproblem, to aggregate partial
plans from all the solvers and create the solution as an output. Therefore,
line 5 waits for $s_{\\_}1$ to finish its own task of solving $P_{\\_}1$,
combine partial plans from all the solvers, and produce the solution at line
6.

Algorithm 1 _DMAPF_

Input: $P$, $dx$, $dy$
Output: A solution or none

1: $(P=\\{P_{\\_}1,\dots,P_{\\_}n\\},Links)\leftarrow Divide(P,dx,dy)$

2: for each $P_{\\_}i\in P$ do

3: Create solver $s_{\\_}i$ for solving $P_{\\_}i$ {in parallel}

4: end for

5: Wait for $s_{\\_}1$

6: return $s_{\\_}1.solution$

Figure 1 depicts an overview of a _DMAPF_ system. In there, the problem has
been divided into subproblems $P_{\\_}1,P_{\\_}2,\dots,P_{\\_}n$ and each of
them is an input to solvers $s_{\\_}1,s_{\\_}2,\dots,s_{\\_}n$, respectively.
All solvers have _Links_ information telling which pairs of them are
_connected_. They use this information as an abstract map to find abstract
plans (details in Section 3.2.1). All solvers connect to _Track_ topic to
synchronize and exchange information to determine whether they have finished
their work, or if not, which of them still have work to do. Each of them also
provides a _Migrate_ service for connected solvers to call if there is any
robot that needs to move between them. Solver $s_{\\_}1$ provides _Aggregate_
service for the other solvers to submit their plan, which constitutes a part
of the solution, then it will combine them to produce the final solution.

Figure 1:  An overview of a _DMAPF_ system.

###  3.1 Problem Division

Figure 2 shows a set of programs used in problem division. The uses of these
programs are controlled by a C++ implementation. First, given a MAPF problem
$P$, as generated by the _ASPRILO_ project [7], and the dimension $dx\times
dy$ of desired subproblems, program `base` is called to determine the
following atoms:

  * •

$d(D,(X,Y))$ – direction $(X,Y)$ that a robot can move in each time step. $D$
is a number representing the direction, which will be later used in movement
planning (Section 3.2.4). In our setting, the robots can move one node at a
time to either left, right, up, or down, which correspond to $(-1,0)$,
$(1,0)$, $(0,-1)$, or $(0,1)$, respectively.

  * •

$goal(R,N)$ – robot $R$ has its goal at node $N$. To restrict each robot to
have at most one distinct goal, we assume that there is at most one order per
robot, where the order is to pick a distinct product $P$ on a distinct shelf
$S$, which is at node $N$ at coordinate $C$.

    #program base.
    d(0,(-1,0)). d(1,(1,0)). d(2,(0,-1)). d(3,(0,1)).
    goal(R,N) :- init(object(order,R),value(line,(P,_))),
                 init(object(product,P),value(on,(S,_))),
                 init(object(shelf,S),value(at,C)),
                 init(object(node,N),value(at,C)).

    #program divide(s, x_min, x_max, y_min, y_max).
    node(s,N,(X,Y)) :- init(object(node,N),value(at,(X,Y))),
                       X >= x_min, X < x_max, Y >= y_min, Y < y_max.
    robot(s,R,N) :- init(object(robot,R),value(at,C)), node(s,N,C).
    edge(s,N1,N2) :- node(s,N1,(X,Y)), node(s,N2,(X+DX,Y+DY)), d(_,(DX,DY)).
    edge(s,N,N) :- node(s,N,_).
    border(s,N) :- node(s,N,(x_min,Y)). border(s,N) :- node(s,N,(x_max-1,Y)).
    border(s,N) :- node(s,N,(X,y_min)). border(s,N) :- node(s,N,(X,y_max-1)).

    #program link.
    link(S1,S2,N1,N2) :- border(S1,N1), border(S2,N2), node(S1,N1,(X,Y)),
                         node(S2,N2,(X+DX,Y+DY)), S1 != S2, d(_,(DX,DY)).

    #program result.
    i(N,C) :- node(S,N,C), area(S,A,N).
    o(N2,C) :- link(S1,S2,N1,N2), area(S1,A,N1), node(S2,N2,C).
    x(N1,N2,D) :- area(S,A,N1), area(S,A,N2), node(S,N1,(X1,Y1)),
                  node(S,N2,(X2,Y2)), d(D,(X2-X1,Y2-Y1)).
    x(N2,N1,D) :- link(S1,S2,N1,N2), area(S1,A,N1), node(S1,N1,(X1,Y1)),
                  node(S2,N2,(X2,Y2)), d(D,(X1-X2,Y1-Y2)).
    l(N1,C1,N2,C2) :- link(S1,S2,N1,N2), area(S1,A1,N1), node(S1,N1,C1),
                      area(S2,A2,N2), node(S2,N2,C2).
    l(A1,A2) :- link(S1,S2,N1,N2), area(S1,A1,N1), area(S2,A2,N2).

Figure 2: The collection of programs used for problem division.

Subproblems are determined in an iterative manner. Suppose $x_{\\_}{min}$,
$x_{\\_}{max}$, $y_{\\_}{min}$, and $y_{\\_}{max}$ are the left, right, top,
and bottom-most points of a given problem $P$, there would be a total of
$\lceil\frac{x_{\\_}{max}-x_{\\_}{min}+1}{dx}\rceil\cdot\lceil\frac{y_{\\_}{max}-y_{\\_}{min}+1}{dy}\rceil$
subproblems (if the map is rectangular). The map of the top-left subproblem
would be bounded within the range of $x=[x_{\\_}{min},~{}x_{\\_}{min}+dx)$ and
$y=[y_{\\_}{min},~{}y_{\\_}{min}+dy)$. The boundaries of the other subproblems
can be determined by adjusting $x_{\\_}{min}$, $x_{\\_}{max}$ (resp.
$y_{\\_}{min}$, $y_{\\_}{max}$) by $dx$ (resp. $dy$). Program `divide` is
repeatedly called (with external atoms which we omit) to determine the
information pertaining to each subproblem $S$ as follows:

  * •

$node(S,N,C)$ – node $N$ is in subproblem $S$ at coordinate $C$.

  * •

$robot(S,R,N)$ – robot $R$ starts at node $N$ which is in subproblem $S$.

  * •

$edge(S,N_{\\_}1,N_{\\_}2)$ – nodes $N_{\\_}1$ and $N_{\\_}2$ are next to each
other in subproblem $S$.

  * •

$border(S,N)$ – node $N$ is a border in subproblem $S$.

Program `link` is then called after all the subproblems have been created from
the calls to program `divide`. It determines the following atom:

  * •

$link(S_{\\_}1,S_{\\_}2,N_{\\_}1,N_{\\_}2)$ – node $N_{\\_}1$ in subproblem
$S_{\\_}1$ is next to node $N_{\\_}2$ in subproblem $S_{\\_}2$. Solvers of
$S_{\\_}1$ and $S_{\\_}2$ are considered to be _neighbors_ if there is a link
between them.

Atoms $edge/3$ acquired from the calls to program `divide` are used to
determined areas within each subproblem. An _area_ is a region where the nodes
inside are all connected. Atoms $area(S,A,N)$ are added to denote that node
$N$ is a part of area $A$ which is in subproblem $S$. Then, program `result`
is repeatedly called (with external atoms which we omit) to determine a set of
information pertaining to each area $A$ as follows:

  * •

$i(N,C)$ – node $N$ at coordinate $C$ is in area $A$.

  * •

$o(N,C)$ – node $N$ at coordinate $C$ is right outside of area $A$ (only one
_direction_ away).

  * •

$x(N_{\\_}1,N_{\\_}2,D)$ – node $N_{\\_}1$ is next to node $N_{\\_}2$, and
they are in area $A$. $N_{\\_}1$ can be a node in either $i/2$ or $o/2$, but
$N_{\\_}2$ can only be a node in $i/2$.

  * •

$l(N_{\\_}1,C_{\\_}1,N_{\\_}2,C_{\\_}2)$ – node $N_{\\_}1$ at coordinate
$C_{\\_}1$ in area $A$ is next to node $N_{\\_}2$ at coordinate $C_{\\_}2$ in
another area.

Each subproblem $P_{\\_}i$ consists of information about its areas, which
includes the atoms acquired from the call to program `result`. Besides the
atoms, a subproblem also contains auxiliary information such as the number of
nodes in different areas (within the subproblem), a list of its neighboring
areas (and their solvers), and a list of nodes that are _corners_ (i.e., a
node that connects to multiple areas) and the areas which they connect to. A
set of atoms $l(A_{\\_}1,A_{\\_}2)$, which denotes that areas $A_{\\_}1$ and
$A_{\\_}2$ are connected, is the content of $Links$ (in figure 1) which is an
input to every solver.

###  3.2 Problem Solving

After a MAPF problem $P$ has been divided into subproblems
$P_{\\_}1,P_{\\_}2,\dots,P_{\\_}n$ as explained in Section 3.1, a solver
$s_{\\_}i$ is created for each subproblem $P_{\\_}i$. The solvers
$s_{\\_}1,s_{\\_}2,\dots,s_{\\_}n$ execute algorithm 2 in parallel to solve
their own subproblem $P_{\\_}i$, and at the end $s_{\\_}1$ will combine their
partial plans to produce the solution of the original problem $P$. The
algorithm requires a few explanations as follows:

  1. 1.

The lines where the first word is underlined denote that they involve
communication with other solvers. Lines 9 and 30 publish a message to the
_Track_ topic. Lines 15, 17, and 20 send a migration request to the _Migrate_
service of the solver that contains area $a$, for each $a\in Send$. Lines 16,
18, and 21 wait to receive a number of $Migrate$ service calls according to
the number of areas in $Recv$.

  2. 2.

The global variables: $Active$, $Send$, and $Recv$ (defined at line 1), are
determined from the communication between solvers. $Active$ keeps track of
solvers that still have work to do, i.e., there is a movement plan to be made
or there exists a robot that needs to migrate; and has the same content across
all the solvers. $Send$ (resp. $Recv$) stores areas that $s_{\\_}i$ needs to
send (resp. receive) migration requests to (resp. from). The contents of the
variables are determined at lines 9 and 30 by having each solver publishes
whether it still has any robot that has not reached its goal (determines
$Active$), and if so, which area they would need to leave and enter if the
current area does not have their goal (determines $Send$ and $Recv$). Every
solver (and area) can be uniquely identified by a number (i.e., an ID). A
solver (resp. area) with an ID $i$ is denoted as $s_{\\_}i$ (resp.
$a_{\\_}i$). For every pair of solvers $s_{\\_}i$ and $s_{\\_}j$, if $i<j$,
then all areas in $s_{\\_}i$ also have smaller IDs than those in $s_{\\_}j$.
When a solver $s_{\\_}i$ wants to send a service request to another solver
$s_{\\_}j$, it can only do so if $i<j$ – this does not mean that $s_{\\_}j$
cannot send information to $s_{\\_}i$, as it can do so in the response message
– RPC style. This design ensures that there is only one direction of service
calls between each pair of neighboring solvers, thus reducing the overhead in
communication by half.

  3. 3.

Function $A$ (defined at line 2) maps a round (denoted as a number starting
from $0$) to a set of area instances. An _area instance_ (or _instance_ , for
short) consists of necessary information about everything in the area such as
nodes, corners, border assignment constraints, current robots ($R$), outgoing
robots ($R_{\\_}i$), incoming robots ($R_{\\_}o$), and a movement plan. An
instance can be constructed either from either (i) an _area_ , as obtained
after the problem division (line 4 and 10); or (ii) another instance (lines 22
and 31). When an instance $\alpha_{\\_}2$ is constructed from another instance
$\alpha_{\\_}1$, the information about the robots in $\alpha_{\\_}2$ is
determined from $\alpha_{\\_}1$ as
$\alpha_{\\_}2.R=(\alpha_{\\_}1.R\setminus\alpha_{\\_}1.R_{\\_}o)\cup\alpha_{\\_}1.R_{\\_}i$.
The other information is straightforward to determine, so we omit the details.
Lines 10 deals with the case where an instance $\alpha$ for area $a$ has not
been constructed (because area $a$ contains no robot), but there are some
robot in another area that wants to migrate to $a$ – so $\alpha$ needs to be
constructed. Line 31 deals with the case where an instance $\alpha_{\\_}2$
needs to be constructed based on another instance $\alpha_{\\_}1$ of the same
area $a$ in the most recent previous round; the problem is, $\alpha_{\\_}1$
may not have been constructed at all. If such case happens, $\alpha_{\\_}2$
would be constructed from area $a$.

The algorithm revolves around the notions of (i) abstract planning (line 6);
(ii) migration; and (iii) movement planning (line 19). The migration process
is divided into three steps: (i) negotiation (lines 15-16); (ii) rejection
(lines 17-18); and (iii) confirmation (lines 20-21). The details of each
notion will be explained sequentially – as how the algorithm works – in the
following subsections.

Algorithm 2 $Solve$

Input: $P_{\\_}i$, $Links$
Output: A solution or none
Parameters: $s_{\\_}i$ – a number denoting this solver

1: global $Active=Send=Recv=\\{\\}$

2: $A=\\{\\}$

3: for each area $a$ in $P_{\\_}i$ that exists a robot do

4: $A=A\cup\\{(0,\alpha)\\}$ where an instance $\alpha$ is constructed from
$a$

5: for each robot $r$ in $\alpha$ do

6: Create an abstract plan for $r$ using $Links$ as an abstract map

7: end for

8: end for

9: Determine $Active$, $Send$, and $Recv$ from $A(0)$ of all the solvers

10: $A=A\cup\\{(0,\alpha)\\}$ where an instance $\alpha$ is constructed from
an area $a$ (resp. $b$) that will be sending (resp. receiving) a request to
(resp. from) the solver of area $c\in Send$ (resp. $d\in Recv$) – where such
an instance has not been created

11:

12: $i=0$

13: while true do

14: if $s_{\\_}i\in Active$ then

15: Send a negotiation request to the solver of area $a$ for each $a\in Send$

16: Wait until $|Recv|$ negotiation requests have been received

17: Send a rejection request to the solver of area $a$ for each $a\in Send$

18: Wait until $|Recv|$ rejection requests have been received

19: Make a movement plan for each instance in $A(i)$

20: Send a confirmation request to the solver of area $a$ for each $a\in Send$

21: Wait until $|Recv|$ confirmation requests have been received

22: $A=A\cup\\{(i+1,\alpha_{\\_}{i+1})\\}$ where an instance
$\alpha_{\\_}{i+1}$ is constructed from $\alpha_{\\_}i\in A(i)$ if there
exists a robot in $\alpha_{\\_}i$ that still needs to move

23: else

24: Wait for active solvers to finish their work

25: end if

26:

27: if $Active=\emptyset$ then

28: return $solution\leftarrow$ aggregated partial plans from all the solvers

29: else

30: Determine $Active$, $Send$, and $Recv$ from $A(i+1)$ of all the solvers

31: $A=A\cup\\{(i+1,\alpha_{\\_}{i+1})\\}$ where an instance
$\alpha_{\\_}{i+1}$ is constructed from an instance $\alpha_{\\_}j$ of area
$a$ (resp. $\beta_{\\_}j$ of area $b$) for the most recent round $j$ where
$\alpha_{\\_}j$ (resp. $\beta_{\\_}j$) $\in A(j)$, and $a$ (resp. $b$) will be
sending (resp. receiving) a request to (resp. from) the solver of area $c\in
Send$ (resp. $d\in Recv$) – where such an instance (i.e., $\alpha_{\\_}{i+1}$)
has not been created; if such $j$ does not exist, then $\alpha_{\\_}{i+1}$ is
constructed from $a$ (resp. $b$)

32: $i=i+1$

33: end if

34: end while

####  3.2.1 Abstract Planning

An _abstract plan_ is a sequence of connected areas that takes a robot from
its initial area to reach the area that contains its goal. The program shown
in figure 3 is used to make an abstract plan for a robot $r$. $r(A,I)$ denotes
that $r$ is in area $A$ at round $I$; and $g(A)$ denotes that the goal of $r$
is in area $A$. Program `abstract(i)` is solved sequentially from
$i=0,\dots,h_{\\_}a$ or until an answer set if found. If no answer set is
found after $i=h_{\\_}a$, then we consider there is no way for $r$ to reach
its goal, and the algorithm terminates. $h_{\\_}a$ is set to be the total
number of areas across all the subproblems, so an abstract plan has to exist
if it is possible for a robot to reach its goal (without considering the other
robots).

    #program abstract(i).
    #external q(i).
    1 { r(A2,i) : l(A1,A2) } 1 :- r(A1,i-1).
    :- q(i), not r(A,i), g(A).
    #show r/2.

Figure 3: The program to make an abstract plan for a single robot.

####  3.2.2 Negotiation

_Negotiation_ is the first phase of the migration process. Its purpose is to
find a set of distinct border assignments for migrating robots. The program
shown in figure 4 is used to make such assignments. It is designed to minimize
_makespan_ – the time step that all robots reach their goal. When a solver
$s_{\\_}1$ of an area $a_{\\_}1$ sends a negotiation request to a neighboring
solver $s_{\\_}2$ of an area $a_{\\_}2$, the message contains a set of robots
that want to migrate, called $a_{\\_}1.R_{\\_}m$, with their current location,
grouped and ordered by the number of steps left in their abstract plan to
reach the last area (longest first); the result of the grouping will be
referred to as _tier_ After $s_{\\_}2$ receives the request from $s_{\\_}1$,
it merges $a_{\\_}1.R_{\\_}m$ with $a_{\\_}2.R_{\\_}m$ and orders them by tier
from high to low; the result of the merging will be referred to as $R_{\\_}m$.
It then computes two variables: the number of incoming (resp. outgoing)
borders available, $n_{\\_}{ai}$ (resp. $n_{\\_}{ao}$). Let $n_{\\_}l$,
$n_{\\_}{bi}$, and $n_{\\_}{bo}$ denote the number of pairs of connected
borders between $a_{\\_}1$ and $a_{\\_}2$, the number of incoming borders that
have been blocked, and the number of outgoing borders that have been blocked,
respectively, then $n_{\\_}{ai}=n_{\\_}l-n_{\\_}{bi}$, and
$n_{\\_}{ao}=n_{\\_}l-n_{\\_}{bo}$. Then, $s_{\\_}2$ goes through $R_{\\_}m$
tier-by-tier. In each tier, if the robots are in $a_{\\_}2$, then they are
used to create either atoms $a/2$ or $b/2$; otherwise, they are used to create
either atoms $c/2$ or $d/2$. Atoms $a/2$, $b/2$, $c/2$, and $d/2$ in program
`migrate` denote the current location of a robot. Whether to encode the robots
in $a/2$ (resp. $c/2$) or $b/2$ (resp. $d/2)$ depends on the current number of
robots that have been assigned out (resp. in), which we will refer to as
$n_{\\_}o$ (resp. $n_{\\_}i$). If the number of robots in the tier is less
than or equal to $n_{\\_}o$ (resp. $n_{\\_}i$), then they are used to create
$a/2$ (resp. $c/2$); otherwise, they are used to create $b/2$ (resp. $d/2)$.
After the robots in the considering tier have been used to create the atoms,
then the value of either $n_{\\_}o$ or $n_{\\_}i$ is increased by the number
of robots added accordingly, and the tier is removed from $R_{\\_}m$.
$s_{\\_}2$ will stop going though $R_{\\_}m$ when either (i)
$R_{\\_}m=\emptyset$; or (ii) $n_{\\_}o\geq n_{\\_}{ao}$ and $n_{\\_}i\geq
n_{\\_}{ai}$. The atom $l(L)$ in program `migrate` denotes the limit – the
number of robots expected to get the border assigned. $L$ could be calculated
as
$\min(\min(n_{\\_}i,n_{\\_}{ai})+\min(n_{\\_}o,n_{\\_}{ao}),\max(n_{\\_}{ai},n_{\\_}{ao}))$.
A collection of atoms $m(R,N_{\\_}1,N_{\\_}2,D)$, where it denotes that robot
$R$ can migrate from border $N_{\\_}1$ in its current area to border
$N_{\\_}2$ in another area and the distance from its current node to
$N_{\\_}1$ is $D$, is obtained from program `migrate`. Each atom $m/4$ is
checked whether $R$ is in area $a_{\\_}1$ or $a_{\\_}2$. $N_{\\_}1$ if $R\in
a_{\\_}2$ (resp. $N_{\\_}2$ if $R\in a_{\\_}1$) is checked whether it is a
_corner_ node (i.e., a node that connects to more than two areas); if so, a
constraint `:- m(_,N1,_,_).` (resp. `:- m(_,_,N2,_).`) will be added, and the
value of $n_{\\_}{bo}$ (resp. $n_{\\_}{bi}$) is increased by one. These
constraints prevent $s_{\\_}2$ from making border assignments for the next
negotiation requests (within the same round) that would result in conflict at
the corners. Finally, $s_{\\_}2$ remembers the resulting border assignments
and also send them to the caller, $s_{\\_}1$.

    #program migrate.
    1 { m(R,N2,N3,|X1-X2|+|Y1-Y2|) : l(N2,(X2,Y2),N3,C3) } 1 :- a(R,(X1,Y1)).
    0 { m(R,N2,N3,|X1-X2|+|Y1-Y2|) : l(N2,(X2,Y2),N3,C3) } 1 :- b(R,(X1,Y1)).
    1 { m(R,N2,N3,|X1-X2|+|Y1-Y2|) : l(N3,C3,N2,(X2,Y2)) } 1 :- c(R,(X1,Y1)).
    0 { m(R,N2,N3,|X1-X2|+|Y1-Y2|) : l(N3,C3,N2,(X2,Y2)) } 1 :- d(R,(X1,Y1)).
    :- m(R1,N,_,_), m(R2,N,_,_), R1!=R2.
    :- m(R1,_,N,_), m(R2,_,N,_), R1!=R2.
    :- m(_,N1,N2,_), m(_,N2,N1,_).
    :- C = #count { R : m(R,_,_,_) }, C!=L, l(L).
    d(S) :- S = #sum { D : m(_,_,_,D) }.
    #minimize { S : d(S) }.
    #show m/4.

Figure 4: The program to make border assignments for multiple robots.

####  3.2.3 Rejection

_Rejection_ is the second phase of the migration process. Its purpose is to
prevent collision at corners that reside between areas with lower and higher
IDs. Suppose there are three solvers: $s_{\\_}1$, $s_{\\_}2$, and $s_{\\_}3$,
which contain areas $a_{\\_}1$, $a_{\\_}2$, and $a_{\\_}3$, respectively; two
connected pairs of the areas: (1) $a_{\\_}1$ and $a_{\\_}2$, and (2)
$a_{\\_}2$ and $a_{\\_}3$; and a corner $c$ in $a_{\\_}2$ that connects to
both $a_{\\_}1$ and $a_{\\_}3$. In the negotiation phase, if there are robots
from $a_{\\_}1$ and $a_{\\_}3$ that want to migrate to $a_{\\_}2$, there would
be requests from $s_{\\_}1$ to $s_{\\_}2$, and from $s_{\\_}2$ to $s_{\\_}3$.
$s_{\\_}2$ (resp. $s_{\\_}3$) will take care of border assignment between
$a_{\\_}1$ and $a_{\\_}2$ (resp. $a_{\\_}2$ and $a_{\\_}3$). This could result
in a collision at $c$ because $s_{\\_}3$ would not know which borders
$s_{\\_}2$ has assigned for the robots in $a_{\\_}1$ to come into $a_{\\_}2$ –
the corner $c$ could be among them. The collision will happen if $s_{\\_}3$
also assigns a robot in $a_{\\_}3$ to come into $a_{\\_}2$ at $c$. In the
rejection phase, every active solver checks for this case and report to the
neighboring solvers their robots that will cause the collision. The reported
solvers will keep the robots in their area for the current round and attempt
to migrate them again in the next round, while the reporting solvers will
treat them as not coming in (in this round).

####  3.2.4 Movement Planning

A _movement plan_ is a sequence of movements for robots to reach their goal
without collision. The program shown in figure 5 is used by every active
solver to make a movement plan for its area that exists some robot that has
not reached its goal or assigned border yet. It is similar to the encoding
used by the _ASPRILO_ project [7], except that it has the following
constraints:

  * •

`:- r(R,N,0), o(N,_), not m(R,_,_,1), q(t).` – forces incoming robots to move
into the area at the first time step ($t=1$).

  * •

`:- q(t), g(t), r(R,N,t), c(N), not g(R,N).` – prohibits robots to stay at any
node that will be migrated into unless it is their goal.

The second constraint helps to increase the success rate of _DMAPF_ , but it
could make movement planning unsuccessful unless there is sufficient free
spaces in the area to enforce it. Therefore, we only add atoms $c(N)$ when
$(n_{\\_}a-n_{\\_}r-n_{\\_}i)\geq n_{\\_}f$, where, for an area $a$;
$n_{\\_}a$, $n_{\\_}m$, $n_{\\_}i$, and $n_{\\_}f$ denote the number of nodes;
the number of robots currently in it; the number of robots assigned to come
in; and the minimum number of free nodes required, set by the user (currently
$n_{\\_}f=4$), respectively. Most of the atoms come directly from $P_{\\_}i$,
except:

  * •

$r(R,N,T)$ – robot $R$ is at node $N$ at time step $T$. An atom
$r(R,N_{\\_}0,0)$ needs to be added for each robot $R$ in the area to denote
its starting node $N_{\\_}0$.

  * •

$c(N)$ – denotes that there will be a robot migrating into node $N$ in the
next round. The set of such nodes is determined from the result of the
_negotiation_ and the _rejection_ phases.

    #program movement(t).
    #external q(t).
    { m(R,D,N2,t) : x(N1,N2,D) } :- r(R,N1,t-1).
    :- m(R,D1,_,t), m(R,D2,_,t), D1 != D2.
    :- r(R,N,0), o(N,_), not m(R,_,_,1), q(t).
    r(R,N2,t) :- r(R,N1,t-1), m(R,D,N2,t), x(N1,N2,D).
    r(R,N,t) :- r(R,N,t-1), not m(R,_,_,t).
    w(N1,N2,t) :- r(R,N1,t-1), m(R,D,N2,t), x(N1,N2,D).
    :- w(N1,N2,t), w(N2,N1,t).
    :- { r(_,N,t) } > 1, i(N,_).
    g(t) :- r(R,N,t) : g(R,N).
    :- q(t), not g(t).
    :- q(t), g(t), r(R,N,t), c(N), not g(R,N).
    #show m/4.

Figure 5: The program to make a movement plan for multiple robots.

Program `movement(t)` is solved sequentially from $i=0,\dots,h_{\\_}m$ or
until an answer set is found. $h_{\\_}m$ is set to $(\sqrt{n_{\\_}a}+1)\cdot
2.0\cdot F$, where $n_{\\_}a$ is the number of nodes in area $a$, and $F$ is a
sensitivity constant set by the user (currently $F=2$). The lower the value of
$F$ is, the less chance that a movement plan will be found, but it could
terminate earlier if there is actually no plan, and vice versa. If no answer
set is found after $i=h_{\\_}m$, then we consider it to be impossible to make
a movement plan for the given configuration, and _DMAPF_ will try to relax the
configuration by removing the goal of a migrating robot one at a time, ordered
by the Manhattan distance of the robot to its assigned border (longest first),
and restarts the call to the program from $t=0$. _DMAPF_ terminates (and
returns no solution) if it cannot relax the configuration any further.

####  3.2.5 Confirmation

_Confirmation_ is the third, and the last phase of the migration process.
After every active solver has finished movement planning, it will send the
information of all the robots that are actually able to move out to the next
area, in the neighboring solver, accordingly. The information of the robots
remains mostly the same, except that their abstract plan will be shorten by
one step because the current area will be removed as they have already been
able to move out, and their current location is updated to the border node
that they will be migrating from.

##  4 Experiment

Table 1 provides comparison between three MAPF solvers: (i)  _DMAPF_ ; (ii)
_ros-dmapf_ [11]; and (iii) _ECBS_
444https://github.com/whoenig/libMultiRobotPlanning [3] – a relaxed version of
_CBS_ [13] where the solution quality is bounded-suboptimal instead of
optimal. We also tried _asprilo_ [7] – an ASP encoding that solves MAPF
problems optimally – but it cannot solve any of the problem instances within
the timeout, so it has been excluded from the table. There are 15 problem
configurations according to each row. Their map size is denoted in the first
column (from the left). Each configuration contains a different number of
robots according to the second column ($n_{\\_}R$), and each robot is randomly
assigned a different goal location. The problem instances do not include
obstacles because we would be unable to compare with _ros-dmapf_ since it does
not support having obstacles. The last three main columns contain results from
the three solvers, which are _Time_ – the solving time in seconds; _Span_ –
makespan of the solution; and _Moves_ – the total number of moves from all the
robots. The size of subproblems for both _DMAPF_ and _ros-dmapf_ is set to
8x8. The suboptimality bound for _ECBS_ is set to $1.2$. The tests were
performed on Ubuntu 20.04 with _Clingo_ 5.5.0, running on a Dell
Precision-3630 Tower with Intel i9-9900K CPU and 64 GB of RAM.

Map | $n_{\\_}R$ | _DMAPF_ | _ros-dmapf_ | _ECBS_
---|---|---|---|---
Time | Span | Moves | Time | Span | Moves | Time | Span | Moves
24 x 24 | 23 | 2.5 | 41 | 443 | 1.6 | 46 | 419 | 0.1 | 38 | 412
46 | 2.6 | 44 | 960 | 1.8 | 58 | 884 | 0.1 | 39 | 797
69 | 2.8 | 51 | 1432 | 2.0 | 69 | 1278 | 0.7 | 40 | 1132
92 | 3.6 | 57 | 2119 | 2.2 | 80 | 1883 | 1.4 | 40 | 1574
120 | 3.9 | 61 | 2751 | 2.5 | 82 | 2595 | 2.5 | 39 | 1973
48 x 48 | 92 | 6.8 | 104 | 2890 | 3.8 | 118 | 2768 | 2.2 | 76 | 2651
184 | 9.8 | 117 | 6815 | 4.9 | 137 | 6625 | 11.8 | 81 | 5929
276 | 10.4 | 128 | 11683 | 7.7 | 187 | 11223 | 87.7 | 87 | 9387
368 | 13.2 | 124 | 16090 | 8.3 | 187 | 15858 | 191.7 | 86 | 12481
460 | 15.6 | 125 | 20920 | 11.0 | 210 | 20428 | - | - | -
96 x 96 | 369 | 31.8 | 225 | 25041 | 30.0 | 242 | 24513 | - | - | -
737 | 41.7 | 240 | 52916 | - | - | - | - | - | -
1106 | 61.8 | 280 | 88943 | - | - | - | - | - | -
1474 | 83.2 | 282 | 124374 | - | - | - | - | - | -
1843 | 175.4 | 282 | 165573 | - | - | - | - | - | -
Table 1: Comparison between _DMAPF_ , _ros-dmapf_ , and _ECBS_. The timeout is
180 seconds.

##  5 Conclusion and Discussion

The experiment in Section 4 shows that, while _ECBS_ performs very fast on the
small problem instances, its performance becomes noticeably worse in a 48x48
map with 276 robots, and is unable to find the solution within the timeout in
the bigger problems. _ros-dmapf_ is generally slightly faster than _DMAPF_ ,
but it is due to its simpler solver interaction protocol. It is unable to
scale further when the maps get denser – in terms of the ratio between the
number of robots to the number of borders within an area. When this ratio
increases, there is more chance for border assignments that will result in no
movement plan to be selected. Since _ros-dmapf_ randomly assigns borders to
migrating robots and cannot change the assignment afterwards, it has
difficulties to scale further. The resulting makespan of _DMAPF_ is
consistent, and better than _ros-dmapf_ due to the better border assignment
mechanism, but it comes with a slight increase in the number of moves. The
solution quality of _ECBS_ is still better than the other two solvers due to
its centralized nature, but not by much in many cases. We believe _DMAPF_ can
scale further given a better hardware and/or the use of clusters. To scale
_DMAPF_ even further, the question whether it is feasible to also backtrack
when movement planning fails even after all the relaxation should be
addressed. Mechanisms that can balance the density of robots across the areas
may also be helpful.

## References

  * [1]
  * [2] Benjamin Andres, David Rajaratnam, Orkunt Sabuncu & Torsten Schaub (2015): _Integrating ASP into ROS for Reasoning in Robots_.  In: Proceedings of the 13th International Conference on Logic Programming and Nonmonotonic Reasoning, 9345, Springer, Lexington, Kentucky, pp. 69–82, 10.1007/978-3-319-23264-57.
  * [3] Max Barer, Guni Sharon, Roni Stern & Ariel Felner (2014): _Suboptimal Variants of the Conflict-Based Search Algorithm for the Multi-Agent Pathfinding Problem_.  In: Seventh Annual Symposium on Combinatorial Search, 10.3233/978-1-61499-419-0-961.
  * [4] Simona Citrigno, Thomas Eiter, Wolfgang Faber, Georg Gottlob, Christoph Koch, Nicola Leone, Cristinel Mateis, Gerald Pfeifer & Francesco Scarcello (1997): _The dlv System: Model Generator and Application Frontends_.  In: Proceedings of the 12th Workshop on Logic Programming, 128137, pp. 128–137.  Available at https://www.wfaber.com/research/papers/wlp97.pdf.
  * [5] Martin Gebser, Roland Kaminski, Benjamin Kaufmann & Torsten Schaub (2014): _Clingo = ASP + Control: Preliminary Report_.  In: Technical Communications of the 13th International Conference on Logic Programming, 14(4-5).  Available at https://arxiv.org/abs/1405.3694.
  * [6] Martin Gebser, Benjamin Kaufmann, André Neumann & Torsten Schaub (2007): __clasp_ : A Conflict-Driven Answer Set Solver_.  In: Proceedings of the 9th International Conference on Logic Programming and Nonmonotonic Reasoning, 4483, Springer, Tempe, Arizona, pp. 260–265, 10.1007/978-3-540-72200-723.
  * [7] Martin Gebser, Philipp Obermeier, Thomas Otto, Schaub Torsten, Orkunt Sabuncu, Van Nguyen & Tran Cao Son (2018): _Experimenting with robotic intra-logistics domains_.  Theory and Practice of Logic Programming 18(3-4), pp. 502–519, 10.1017/S1471068418000200.
  * [8] Michael Gelfond & Vladimir Lifschitz (1990): _Logic Programs with Classical Negation_.  In: Logic Programming, Proceedings of the Seventh International Conference, MIT Press, Jerusalem, Israel, pp. 579–597.  Available at https://dl.acm.org/doi/10.5555/87961.88030.
  * [9] Victor W. Marek & Miroslaw Truszczynski (1999): _Stable Models and an Alternative Logic Programming Paradigm_.  In: The Logic Programming Paradigm - A 25-Year Perspective, Springer, pp. 375–398, 10.1007/978-3-642-60085-217.
  * [10] Ilkka Niemelä (1999): _Logic Programs with Stable Model Semantics as a Constraint Programming Paradigm_.  Annals of Mathematics and Artificial Intelligence 25(3-4), pp. 241–273, 10.1023/A:1018930122475.
  * [11] Poom Pianpak, Tran Cao Son, Z O Toups & William Yeoh (2019): _A Distributed Solver for Multi-Agent Path Finding Problems_.  In: Proceedings of the First International Conference on Distributed Artificial Intelligence, pp. 1–7, 10.1145/3356464.3357702.
  * [12] Morgan Quigley, Ken Conley, Brian Gerkey, Josh Faust, Tully Foote, Jeremy Leibs, Rob Wheeler & Andrew Y. Ng (2009): _ROS: an open-source Robot Operating System_.  In: ICRA workshop on open source software, 3, Kobe, Japan, p. 5.  Available at http://www.cim.mcgill.ca/~dudek/417/Papers/quigley-icra2009-ros.pdf.
  * [13] Guni Sharon, Roni Stern, Ariel Felner & Nathan R. Sturtevant (2015): _Conflict-based search for optimal multi-agent pathfinding_.  Artificial Intelligence 219, pp. 40–66, 10.1016/j.artint.2014.11.006.
  * [14] David Silver (2005): _Cooperative Pathfinding_.  In: Proceedings of the 1st Artificial Intelligence and Interactive Digital Entertainment Conference, 1, Marina Del Rey, pp. 117–122.  Available at https://www.aaai.org/Library/AIIDE/2005/aiide05-020.php.