Time-Independent Planning for Multiple Moving Agents

Keisuke Okumura, Yasumasa Tamura, Xavier Défago

Abstract

Typical Multi-agent Path Finding (MAPF) solvers assume that agents move synchronously, thus neglecting the reality gap in timing assumptions, e.g., delays caused by an imperfect execution of asynchronous moves. So far, two policies enforce a robust execution of MAPF plans taken as input: either by forcing agents to synchronize or by executing plans while preserving temporal dependencies. This paper proposes an alternative approach, called time-independent planning, which is both online and distributed. We represent reality as a transition system that changes configurations according to atomic actions of agents, and use it to generate a time-independent schedule. Empirical results in a simulated environment with stochastic delays of agents’ moves support the validity of our proposal.

Introduction

Multi-agent systems with physically moving agents are becoming gradually more common, e.g., automated warehouse (Wurman, D’Andrea, and Mountz 2008), traffic control (Dresner and Stone 2008), or self-driving cars. In such systems, agents must move smoothly without colliding. This is embodied by the problem of Multi-agent Path Finding (MAPF) (Stern 2019). Planning techniques for MAPF have been extensively studied in recent years.

The output of such planning is bound to be executed in real-world situations with agents (robots). Typical MAPF is defined in discrete time. Agents are assumed to do two kinds of atomic actions synchronously: move to a neighboring location or stay at their current location. Perfect executions for the planning are however difficult to ensure since timing assumptions are inherently uncertain in reality, due to the difficulty of: 1) accurately predicting the temporal behavior of many aspects of the system, e.g., kinematics, 2) anticipating external events such as faults and interference, and 3) ensuring a globally consistent and accurate notion of time in the face of clock shift and clock drift. Even worse, the potential of unexpected interference increases with the number of agents, hence the need to prepare for imperfect executions regarding the timing assumptions.

There are two intuitive ways to tackle imperfect executions of MAPF plans taken as input. The first, and conservative idea is to forcibly synchronize agents’ moves, globally or locally. Most decentralized approaches to MAPF take this approach implicitly (Wiktor et al. 2014; Kim et al. 2015; Okumura et al. 2019; Wang and Rubenstein 2020). This policy negatively affects the entire performance of the system with unexpected delays and lacks flexibility (Ma, Kumar, and Koenig 2017). The second policy makes agents preserve temporal dependencies of the planning (Hönig et al. 2016; Ma, Kumar, and Koenig 2017; Hönig et al. 2019; Atzmon et al. 2020). Two types of temporal dependencies exist: 1) internal events within one agent and, 2) order relation of visiting one node. This policy is sound but still vulnerable to delays. Consider an extreme example where one agent moves very slowly or crashes. Due to the second type of dependencies, the locations where the agent will be are constrained by the use of the other agents. Thus, the asynchrony of the movements is sensitive to the whole system.

We, therefore, propose an alternative approach, called time-independent planning, that aims at online and distributed execution focusing on agents’ moves. We represent the whole system as a transition system that changes configurations according to atomic actions of agents, namely, 1) request the next locations ( $\mathit{requesting}$ ), 2) move ( $\mathit{extended}$ ), and, 3) release the past locations, or stay ( $\mathit{contracted}$ ). In this time-independent model, any a priori knowledge for timings of atomic actions is unavailable, representing non-deterministic behaviors of the external environment. The challenge is to design algorithms tolerant of all possible sequences of actions.

(a) priority inheritance (PI)

(b) backtracking and PI again

(d) one timestep later

(e) as DFST

Figure 1: Example of PIBT. Requests for the next timestep are depicted by dashed circles, determined greedily according to agents’ destinations (omitted here). Flows of priority inheritance and backtracking are drawn as single-line and doubled-line arrows, respectively. First,

a_{7}

(blue agent) determines the next desired node (current location of

a_{6}

). Then, priority inheritance happens from

a_{7}

a_{6}

, making

a_{7}

wait for backtracking and

a_{6}

start planning;

a_{6}

a_{5}

and

a_{4}

do the same.

a_{3}

(red), however, is stuck (1). Thus,

a_{3}

backtracks as invalid to

a_{4}

(1).

a_{4}

tries to replan, however,

a_{4}

is also stuck hence

a_{4}

sends backtracking as invalid to

a_{5}

(blue with diagonal lines).

a_{5}

, with success replanning, executes other priority inheritance to

a_{1}

(1). Finally,

a_{1},a_{5},a_{6}

and

a_{7}

receives backtracking as valid (1) and then start moving (1). Fig. 1: virtual depth first search tree for this example, for explanation of Causal-PIBT.

a_{7}

is a root. Solid arrows are drawn from a parent to a child.

a_{2}

finds an empty node.

The main contributions of this paper are: 1) the formalization of the time-independent model and Causal-PIBT, a proposed time-independent planning with guaranteed reachability, i.e., all agents are ensured to reach their destinations within finite time. Causal-PIBT, as a proof-of-concept, extends a recently-developed decoupled approach that solves MAPF iteratively, Priority Inheritance with Backtracking (PIBT) (Okumura et al. 2019). We also present how an offline MAPF plan enhances Causal-PIBT. 2) experimental results demonstrating the validity and robustness of the proposal through the simulation with stochastic delays of agents’ moves, using MAPF-DP (with Delay Probabilities) (Ma, Kumar, and Koenig 2017).

The remainder of this paper consists of the following five sections: 1) preliminary including the formalization of MAPF and related work, 2) the time-independent model, 3) examples of time-independent planning, 4) empirical results of the proposals using MAPF-DP, and 5) conclusion and future directions.

Preliminaries

This section first defines MAPF. Then, we explain the MAPF variant emulating asynchrony of movements, called MAPF-DP, which we later use in experiments. We also explain two policies that execute MAPF plans and PIBT, the original form of Causal-PIBT.

MAPF

In an environment represented as a graph $G=(V,E)$ , the MAPF problem is defined as follows. Let $\pi_{i}[t]\in V$ denote the location of an agent $a_{i}$ at discrete time $t\in\mathbb{N}$ . Given distinct initial locations $\pi_{i}[0]\in V$ and destinations $g_{i}\in V$ for each agent, assign a path $\pi_{i}=(\pi_{i}[0],\pi_{i}[1],\dots,\pi_{i}[T])$ such that $\pi_{i}[T]=g_{i}$ to each agent minimizing some objective function (see below).

At each timestep $t$ , $a_{i}$ can move to an adjacent node, or, can stay at its current location, i.e., $\pi_{i}[t+1]\in\mathit{Neigh}(\pi_{i}[t])\cup\{\pi_{i}[t]\}$ , where $\mathit{Neigh}(v)$ is the set of nodes neighbor to $v\in V$ . Agents must avoid two types of conflicts (Stern et al. 2019): 1) vertex conflict: $\pi_{i}[t]\neq\pi_{j}[t]$ , and, 2) swap conflict: $\pi_{i}[t]\neq\pi_{j}[t+1]\lor\pi_{i}[t+1]\neq\pi_{j}[t]$ .

Two kinds of objective functions are commonly used to evaluate MAPF solutions: 1) sum of cost (SOC), where the cost is the earliest timestep $T_{i}$ such that $\pi_{i}[T_{i}]=g_{i},\dots,\pi_{i}[T]=g_{i},T_{i}\leq T$ , 2) makespan, i.e., $T$ . This paper focuses on the sum of cost (SOC).

MAPF-DP (with Delay Probabilities)

MAPF-DP (Ma, Kumar, and Koenig 2017) emulates imperfect executions of MAPF plans by introducing the possibility of unsuccessful moves. Time is still discrete. At each timestep, an agent $a_{i}$ can either stay in place or move to an adjacent node with a probability $p_{i}$ of being unsuccessful. The definition of conflicts is more restrictive than with normal MAPF: 1) vertex conflict is as defined in MAPF, and 2) following conflict: $\pi_{i}[t+1]\neq\pi_{j}[t]$ . The rationale is that, without the later restriction, two agents might be in the same node due to one failing to move. Note that following conflict contains swap conflict.

Execution Policies

Ma et al. (Ma, Kumar, and Koenig 2017) studied two robust execution policies using MAPF plans for the MAPF-DP setting. The first one, called Fully Synchronized Policies (FSPs), synchronizes the movements of agents globally, i.e., $a_{i}$ waits to move to $\pi_{i}[t+1]$ ( $\neq\pi_{i}[t]$ ) until all move actions of $\pi_{j}[t^{\prime}]$ , $t^{\prime}\leq t$ are completed. The second approach, called Minimal Communication Policies (MCPs), executes a plan while maintaining its temporal dependencies. There are two kinds of dependencies: 1) internal events, i.e., the corresponding action of $\pi_{i}[t]$ is executed prior to that of $\pi_{i}[t+1]$ , and 2) node-related events, i.e., if $\pi_{i}[t]=\pi_{j}[t^{\prime}]$ and $t<t^{\prime}$ , the event of $\pi_{i}[t]$ is executed prior to that of $\pi_{j}[t^{\prime}]$ . As long as an MAPF plan is valid, both policies make agents reach their destinations without conflicts, despite of delay probabilities.

state	$\sigma_{1}$	$\sigma_{2}$	$\sigma_{1}$	$\sigma_{2}$	$\sigma_{1}$	$\sigma_{2}$	$\sigma_{2}$	$\sigma_{1}$	$\sigma_{1}$	$\sigma_{1}$	$\sigma_{1}$	$\sigma_{2}$	$\sigma_{2}$	$\sigma_{2}$	$\sigma_{2}$	$\sigma_{2}$
$\mathit{mode}$	$\mathit{c}$	$\mathit{c}$	$\mathit{r}$	$\mathit{r}$	$\mathit{e}$	$\mathit{c}$	$\mathit{r}$	$\mathit{c}$	$\mathit{r}$	$\mathit{e}$	$\mathit{c}$	$\mathit{e}$	$\mathit{c}$	$\mathit{r}$	$\mathit{e}$	$\mathit{c}$
$\mathit{head}$	$\bot$	$\bot$	$v_{3}$	$v_{3}$	$v_{3}$	$\bot$	$v_{3}$	$\bot$	$v_{5}$	$v_{5}$	$\bot$	$v_{3}$	$\bot$	$v_{4}$	$v_{4}$	$\bot$
$\mathit{tail}$	$v_{1}$	$v_{2}$	$v_{1}$	$v_{2}$	$v_{1}$	$v_{2}$	$v_{2}$	$v_{3}$	$v_{3}$	$v_{3}$	$v_{5}$	$v_{2}$	$v_{3}$	$v_{3}$	$v_{3}$	$v_{4}$

Figure 2: Example of an execution of the model.

a_{1}

goes to

v_{5}

and

a_{2}

goes to

v_{4}

. In the table, time progresses from left to right. There is an interaction, which makes

a_{2}

be back to

\mathit{contracted}

Priority Inheritance with Backtracking (PIBT)

PIBT (Okumura et al. 2019) repeats one-timestep planning until it terminates, aiming at solving MAPF iteratively (without delays). Unlike complete solvers for MAPF, PIBT does not ensure that all agents are on their goals simultaneously, rather it ensures reachability; all agents are ensured to reach their destinations eventually. Thus, an agent that reaches its goal potentially moves from there while other agents are moving. Reachability plays a crucial role in situations where destinations are given continuously such as lifelong MAPF (Ma et al. 2017) because all tasks (i.e., destinations) assigned to agents are ensured to be completed.

In PIBT, for each timestep, agents are provided with unique priorities and they sequentially determine their next locations in decreasing order of priorities while avoiding to use nodes that have requested by higher-priority agents. Priority inheritance, originally considered in resource scheduling problems (Sha, Rajkumar, and Lehoczky 1990), is introduced; when a low-priority agent $X$ obstructs the movement of a higher-priority agent $Y$ , $X$ temporarily inherits the higher-priority of $Y$ . Priority inheritance can be applied iteratively. Agents giving their priority ( $Y$ ) must wait for backtracking from agents inheriting the priority ( $X$ ). Backtracking has two outcomes: valid or invalid. A valid situation occurs when $Y$ can successfully move to the location of $X$ in the next timestep. An invalid situation occurs when $X$ is stuck, i.e., neither going anywhere nor staying at its current location without colliding, forcing $Y$ to replan its path. Fig. 1 shows an example of PIBT in one timestep.

With these protocols, the agent with highest priority is ensured to move to an arbitrary neighbor node if the graph satisfies the adequate property, e.g., biconnected. Subsequently, such an agent moves to its goal along the shortest path to its goal. To ensure reachability, PIBT uses dynamic priorities, where the priority of an agent increments gradually at each timestep until it drops upon reaching its goal, meaning that, agents not reaching their goals yet eventually get the highest.

Time-Independent Model

The time-independent model and the terminology used in this paper are partly inspired by the model for distributed algorithms with synchronous message passing (Tel 2000) and the Amoebot model (Derakhshandeh et al. 2014), an abstract computational model for programmable matter. Our model is however different in that agents are physically embodied and move on a graph, have destinations, and know their locations.

Components

The system consists of a set of agents $A=\{a_{1},\dots,a_{n}\}$ and a graph $G=(V,E)$ . We assume that each agent knows $G$ to plan their respective paths.

Configuration and State

The whole system is represented as a transition system according to atomic actions of agents. Each agent $a_{i}$ is itself a transition system with its state, denoted as $\sigma_{i}$ , consisting of its internal variables, its current location, and destination. A configuration $\gamma=(\sigma_{1},\dots,\sigma_{n})$ of the whole system at a given time consists of the states of all agents at that time. A change in the state of some agents causes a change of configuration of the system, e.g., $\gamma=(\dots,\sigma_{i-1},\sigma_{i},\sigma_{i+1},\dots)\rightarrow\gamma^{\prime}=(\dots,\sigma_{i-1},\sigma_{i}^{\prime},\sigma_{i+1},\dots)$ .

Mode

Each agent at any time occupies at least one node and occupies two nodes during moves between nodes. We use two terms to represent agents’ locations: $\mathit{tail}_{i}\in V$ and $\mathit{head}_{i}\in V\cup\{\bot\}$ , where $\bot$ is void. They are associated with a mode $\mathit{mode}_{i}$ which can be: $\mathit{contracted}$ , $\mathit{requesting}$ , and $\mathit{extended}$ .

•

$\mathit{contracted}$ : $a_{i}$ stays at one node $\mathit{tail}_{i}$ , and $\mathit{head}_{i}=\bot$ ; location of $a_{i}$ is $\mathit{tail}_{i}$
•

$\mathit{requesting}$ : $a_{i}$ attempts to move to $\mathit{head}_{i}\not=\bot$ , being at $\mathit{tail}_{i}$ ; location of $a_{i}$ is $\mathit{tail}_{i}$
•

$\mathit{extended}$ : $a_{i}$ is moving from $\mathit{tail}_{i}$ to $\mathit{head}_{i}$ ; locations of $a_{i}$ are both $\mathit{tail}_{i}$ and $\mathit{head}_{i}$ .

Initially, all agents are $\mathit{contracted}$ and have distinct initial locations. $\mathit{head}_{i}$ ( $\neq\bot$ ) is always adjacent to $\mathit{tail}_{i}$ .

Transition

Agents move by changing modes. These transitions are accompanied by changing $\mathit{tail}$ and $\mathit{head}$ as described below.

•

from $\mathit{contracted}$ , $a_{i}$ can become $\mathit{requesting}$ by setting $\mathit{head}_{i}$ to $u\in\mathit{Neigh}(\mathit{tail}_{i})$ , to move to a neighbor node.
•

from $\mathit{requesting}$ , $a_{i}$ can revert to $\mathit{contracted}$ by changing its $\mathit{head}_{i}$ to $\bot$ .
•

from $\mathit{requesting}$ , agent $a_{i}$ can become $\mathit{extended}$ when $\lnot\mathit{occupied}({\mathit{head}_{i}})$ , where $\mathit{occupied}({v})$ holds when there is no agent $a_{j}$ such that $\mathit{tail}_{j}=v$ and no agent $a_{j}$ in $\mathit{extended}$ such that $\mathit{head}_{j}=v$ .
•

from $\mathit{extended}$ , $a_{i}$ can become $\mathit{contracted}$ , implying that the movement is finished. This comes with $\mathit{tail}_{i}\leftarrow\mathit{head}_{i}$ , then $\mathit{head}_{i}\leftarrow\bot$ .

Transitions are atomic so, e.g., if agents in $\mathit{contracted}$ become $\mathit{extended}$ through $\mathit{requesting}$ , at least two actions are required; see an example later. Other modes transitions are disallowed, e.g., an agent in $\mathit{contracted}$ cannot become $\mathit{extended}$ directly.

Conflict-freedom and Deadlock

In the above transition rules, the model implicitly prohibits vertex and following conflicts of MAPF. Rather, the model is prone to deadlocks; A set of agents $\{a_{k},\ldots,a_{l}\}$ are in a deadlock when all of them are $\mathit{requesting}$ and are in a cycle $\mathit{head}_{k}=\mathit{tail}_{k+1}$ , $\cdots$ , $\mathit{head}_{l}=\mathit{tail}_{k}$ .

Activation

Agents perform a single atomic action as a result of being activated. The nature and outcome of the action depend on the state of the agent (e.g., mode transition, local variable update). Activations occur non-deterministically, and there is no synchronization between agents. For simplicity, we assume that at most one agent is activated at any time. In other words, the simultaneous activation of two agents $a_{i}$ and $a_{j}$ results in a sequence $(\dots,\sigma_{i},\dots,\sigma_{j},\dots)\rightarrow(\dots,\sigma_{i}^{\prime},\dots,\sigma_{j},\dots)\rightarrow(\dots,\sigma_{i}^{\prime},\dots,\sigma_{j}^{\prime},\dots)$ . Activations are supposed to be fair in the sense that, in any sufficiently long period, all agents must be activated at least once.

Interaction

An activation may affect not only variables of the activated agent, but also affect nearby agents indirectly. For instance, if two $\mathit{requesting}$ agents have the same $\mathit{head}$ , one wins and becomes $\mathit{extended}$ whereas the other loses and becomes $\mathit{contracted}$ , atomically. This type of activation is called an interaction. Interactions include activations such that the activated agents change their variables referring to the variables of other agents. We say that the agents involved in the interaction, except $a_{i}$ itself, are interacted agents. Given an activated agent $a_{i}$ and an interacted agent $a_{j}$ , the system transitions as follows: $(\dots,\sigma_{i},\dots,\sigma_{j},\dots)\rightarrow(\dots,\sigma_{i}^{\prime},\dots,\sigma_{j}^{\prime},\dots)$ with the state of all other agents unchanged. Except for interactions, the configuration is changed by the state change of a single agent. We assume that interactions are performed by communication between agents, but the detailed implementation is not relevant to this paper.

Termination

Assuming that each agent $a_{i}$ has its own destination $g_{i}\in V$ , termination can be defined in two different ways.

•

Strong termination occurs when reaching a configuration such that $\mathit{mode}_{i}=\mathit{contracted}\land\mathit{tail}_{i}=g_{i}$ for any agent $a_{i}$ .
•

Weak termination is when all agents have been at least once in a state where $\mathit{mode}_{i}=\mathit{contracted}\land\mathit{tail}_{i}=g_{i}$ .

Strong termination corresponds to usual MAPF termination, whereas weak termination corresponds to the reachability property of PIBT. Strong termination implies weak termination.

In this paper, we refer to weak termination as reachability. Note that the properties of either deadlock-freedom or deadlock-recovery are required to ensure reachability.

Remarks

Figure 2 illustrates an execution in the time-independent model. Although the example focuses on (classical) MAPF, many other problem variants, e.g., iterative MAPF (Okumura et al. 2019), can be addressed simply by adapting termination and goal assignments.

Algorithm

This section presents two examples of time-independent planning: GREEDY and Causal-PIBT. We also present how to enhance Causal-PIBT with offline MAPF plans.

Greedy Approach

GREEDY performs only basic actions; it can be a template for another time-independent planning. We simply describe its implementation for $a_{i}$ as follows.

•

when $\mathit{contracted}$ : Choose the nearest node to $g_{i}$ from $\mathit{Neigh}(\mathit{tail}_{i})$ as new $\mathit{head}_{i}$ , then become $\mathit{requesting}$ .
•

when $\mathit{requesting}$ : Become $\mathit{extended}$ when the $\mathit{head}_{i}$ is unoccupied, otherwise, do nothing.
•

when $\mathit{extended}$ : Become $\mathit{contracted}$ .

Obviously, GREEDY is prone to deadlocks, e.g, when two adjacent agents try to swap their locations, they block eternally. The time-independent planning without deadlock-freedom or deadlock-recovery properties is impractical, motivating the next algorithm.

Causal-PIBT

The Causal-PIBT algorithm extends both algorithms PIBT and GREEDY. Although PIBT is timing-based relying on synchronous moves, Causal-PIBT is event-based relying on causal dependencies of agents’ actions.

Concept

Two intuitions are obtained from PIBT to design a time-independent algorithm that ensures reachability; 1) Build a depth-first search tree rooted at the agent with highest priority, using the mechanism of priority inheritance and backtracking. 2) Drop priorities of agents that arrive at their goals to give higher priorities to all agents not having reached their goals yet, thus resulting in that all agents eventually reach their goals. We complement the first part as follows.

The path adjustment of PIBT in one timestep can be seen as the construction of a (virtual) depth-first search tree consisting of agents and their dependencies. The tree is rooted at the first agent starting priority inheritance, i.e., locally highest priority agent, e.g., $a_{7}$ in Fig. 1. When an agent $a_{j}$ inherits a priority from another agent $a_{i}$ , $a_{j}$ becomes a child of $a_{i}$ and $a_{i}$ becomes its parent. We show this virtual tree in Fig. 1. Once an empty node adjacent to the tree is found, all agents on the path from the root to that empty node can move toward one step forward ( $a_{2},a_{1},a_{5},a_{6}$ and $a_{7}$ ). This enables the agent with highest priority, being always a root, to move from the current node to any arbitrary neighbor nodes. The invalid outcome in backtracking works as backtracking in a depth-first search, while the valid outcome notifies the search termination.

Algorithm 1 Causal-PIBT

\mathit{parent}_{i}\in A

: initially

a_{i}

;

\mathit{children}_{i}\subset A

: initially

\emptyset

\mathit{pori}_{i}

: original priority;

\mathit{ptmp}_{i}

: temporal priority, initially

\mathit{pori}_{i}

C_{i}\subseteq V

: candidate nodes, initially

\mathit{Neigh}(\mathit{tail}_{i})\cup\{\mathit{tail}_{i}\}

S_{i}\subseteq V

: searched nodes, initially

\emptyset

1:when

\mathit{mode}_{i}=\mathit{contracted}

2: if

C_{i}=\emptyset\land\mathit{parent}_{i}=a_{i}

then

3: ReleaseChildren, Reset

4: end if

5: PriorityInheritance

6: if

C_{i}=\emptyset

then

7: let

a_{j}

\mathit{parent}_{i}

8: if

\mathit{head}_{j}=\mathit{tail}_{i}

then

S_{j}\leftarrow S_{j}\cup S_{i}

C_{j}\leftarrow C_{j}\setminus S_{j}

\triangleright

with

a_{j}

10:

\mathit{head}_{j}\leftarrow\bot

\mathit{mode}_{j}\leftarrow\mathit{contracted}

11: end if

12: return

13: end if

14:

u\leftarrow

the nearest node to

g_{i}

C_{i}

15: if

u=\mathit{tail}_{i}

then

16: ReleaseChildren, Reset

17: return

18: end if

19:

C_{i}\leftarrow C_{i}\setminus\{u\}

S_{i}\leftarrow S_{i}\cup\{u,\mathit{tail}_{i}\}

20:

\mathit{head}_{i}\leftarrow u

\mathit{mode}_{i}\leftarrow\mathit{requesting}

21:end when

22:when

\mathit{mode}_{i}=\mathit{requesting}

23: PriorityInheritance

24: if

\mathit{parent}_{i}\neq a_{i}\land\mathit{head}_{i}\in S_{\mathit{parent}_{i}}

then

\triangleright

\mathit{parent}_{i}

25:

\mathit{head}_{i}\leftarrow\bot

\mathit{mode}_{i}\leftarrow\mathit{contracted}

26: return

27: end if

28: if

\mathit{occupied}({\mathit{head}_{i}})

then return

29:

A^{\prime}\leftarrow\{a_{j}\;|\;a_{j}\in A,\mathit{mode}_{j}=\mathit{requesting},\mathit{head}_{j}=\mathit{head}_{i}\}

30:

a^{\star}\leftarrow\mathop{\rm arg~{}max}\limits_{a_{j}\in A^{\prime}}\mathit{ptmp}_{j}

31: for

a_{j}\in A^{\prime}\setminus\{a^{\star}\}

\triangleright

agents in

A^{\prime}

32:

\mathit{head}_{j}\leftarrow\bot

\mathit{mode}_{j}\leftarrow\mathit{contracted}

33: end for

34: if

a^{\star}\neq a_{i}

then return

35:

\mathit{children}_{\mathit{parent}_{i}}\leftarrow\mathit{children}_{\mathit{parent}_{i}}\setminus\{a_{i}\}

\triangleright

\mathit{parent}_{i}

36:

\mathit{parent}_{i}\leftarrow a_{i}

37: ReleaseChildren

38:

\mathit{mode}_{i}\leftarrow extended

39:end when

40:when

\mathit{mode}_{i}=\mathit{extended}

41:

\mathit{tail}_{i}\leftarrow\mathit{head}_{i}

\mathit{head}_{i}\leftarrow\bot

\mathit{mode}_{i}\leftarrow\mathit{contracted}

42: update

\mathit{pori}_{i}

, Reset

43:end when

Description

Causal-PIBT basically performs GREEDY, i.e., at each activation an agent $a_{i}$ tries to move towards its goal; in addition, Causal-PIBT uses priority inheritance. When $a_{i}$ is $\mathit{contracted}$ or $\mathit{requesting}$ , $a_{i}$ potentially inherits priority from another agent $a_{j}$ in $\mathit{requesting}$ with $\mathit{head}_{j}=\mathit{tail}_{i}$ . We now explain the details. The pseudocode is split into Algorithm 1 and 2. Interactions and the corresponding interacted agents are explicitly marked in comments. In Algo. 1, procedures with activation are denoted for each mode.

Variants: We first introduce local variants of $a_{i}$ .

•

$\mathit{parent}_{i}$ and $\mathit{children}_{i}$ : for maintaining tree structures. $a_{i}$ is a root when $\mathit{parent}_{i}=a_{i}$ . The algorithm updates these variants so that $a_{i}=\mathit{parent}_{j}\Leftrightarrow a_{j}\in\mathit{children}_{i}$ .
•

$C_{i}$ and $S_{i}$ : for searching unoccupied neighbor nodes. $C_{i}$ is candidate nodes of next locations. $a_{i}$ in $\mathit{contracted}$ selects $\mathit{head}_{i}$ from $C_{i}$ . $S_{i}$ represents already searched nodes by a tree to which $a_{i}$ belongs. $S_{i}$ is propagated in the tree. $C_{i}$ is updated to be disjoint from $S_{i}$ .
•

$\mathit{pori}_{i}$ and $\mathit{ptmp}_{i}$ : priorities. They are components of a total order set. $\mathit{ptmp}_{i}$ is basically equal to $\mathit{pori}_{i}$ , however, it is changed by priority inheritance. $\mathit{ptmp}_{i}\geq\mathit{pori}_{i}$ in any time, and only $\mathit{ptmp}_{i}$ is used for interaction.

Structure: The procedures in $\mathit{contracted}$ consist of:

•

Relaying release [Line 2–4]. An agent in stuck like $a_{4}$ in Fig. 1 is “released” when its parent ( $a_{5}$ ) moves. If it has children ( $a_{3}$ ), it needs to relay the release to its children, then initialize.
•

Priority inheritance [Line 5]. When $a_{i}$ is activated and there exists an agent $a_{j}$ with higher priority such that $\mathit{head}_{j}=\mathit{tail}_{i}$ , then priority inheritance happens from $a_{j}$ to $a_{i}$ , e.g., from $a_{7}$ and $a_{6}$ in Fig. 1.
•

Backtracking [Line 6–13]. When $a_{i}$ detects stuck ( $C_{i}=\emptyset$ ), making its parent $a_{j}$ $\mathit{contracted}$ while propagating already searched nodes $S_{i}$ , then stops. This procedures correspond to invalid case of backtracking in PIBT, e.g., from $a_{3}$ to $a_{4}$ in Fig. 1.
•

Prioritized planning [Line 14–20]. Pickup one node $u$ for the next location from $C_{i}$ , update searched nodes, and become $\mathit{requesting}$ . Initialize when $u$ is $\mathit{tail}_{i}$ .

The procedures in $\mathit{requesting}$ consist of:

•

Priority inheritance [Line 23]. The condition is the same as priority inheritance in $\mathit{contracted}$ . This implicitly contributes to detecting deadlocks.
•

Deadlock detection and resolving [Line 24–27]. This part detects the circle of requests, then go back to $\mathit{contracted}$ .
•

Winner determination [Line 28–33]. When $\mathit{head}_{i}$ is unoccupied, there is a chance to move there. First, identify agents requesting the same node then select one with highest priority as a winner. Let losers back to be contracted. See “interaction” in Fig. 2.
•

Preparation for moves [Line 34–38]. If $a_{i}$ itself is a winner, after isolating itself from a tree belonged to, $a_{i}$ becomes $\mathit{extended}$ .

The procedures in $\mathit{extended}$ are to update priority and back to $\mathit{contracted}$ .

Subprocedures: We use three subprocedures, as shown in Algo. 2. PriorityInheritance first determines whether priority inheritance should occur [Line 2–5], then updates the tree structure and inherits both the priority and the searched nodes from the new parent [Line 6–10]. ReleaseChildren just cuts off the relationship with the children of $a_{i}$ . Reset initializes the agent’s status.

Overview: Causal-PIBT constructs depth-first search trees, each rooted at the agents with locally highest priorities, using $\mathit{parent}$ and $\mathit{children}$ . They are updated through priority inheritance and backtracking mechanisms. All agents in the same tree have the same priority $\mathit{ptmp}$ , equal to the priority $\mathit{pori}$ of the rooted agent. When a tree with higher priority comes in contact with a lower-priority tree (by some agent becoming $\mathit{requesting}$ ), the latter tree is decomposed and is partly merged into the former tree (by PriorityInheritance). In the reverse case, the tree with lower priority just waits for the release of the area. Backtracking occurs when a child has no candidate node to move due to requests from agents with higher priorities [Line 8–11 in Algo. 1].

Dynamic Priorities: We assume that $\mathit{pori}_{i}$ is unique between agents in any configuration and updated upon reaching a goal to be lower than priorities of all agents who have not yet reached their goals [Line 42 in Algo. 1]. This is realized by a prioritization scheme similar to PIBT.

Properties

Next, two useful properties of Causal-PIBT are shown: deadlock-recovery and the reachability. We also state that Causal-PIBT is quick enough as atomic actions in terms of time complexity.

Theorem 1 (deadlock-recovery).

Causal-PIBT ensures no deadlock situation can last forever.

Proof.

Assume that there is a deadlock. When an agent $a_{i}$ changes from $\mathit{contracted}$ to $\mathit{requesting}$ , it updates $S_{i}$ such that $S_{i}$ includes $\mathit{head}_{i}$ and $\mathit{tail}_{i}$ [Line 19 in Algo. 1]. After finite activations, all agents involved in the deadlock must have the same priority $\mathit{ptmp}$ due to priority inheritance. Every priority inheritance is accompanied by the propagation of $S_{i}$ [Line 10 in Algo. 2]. When an agent in $\mathit{requesting}$ detects its head in $S_{\mathit{parent}_{i}}$ , it changes back to $\mathit{contracted}$ [Line 24–27 in Algo. 1]. These imply the statement. ∎

Once an agent $a_{i}$ in a deadlock comebacks to $\mathit{contracted}$ , $a_{i}$ cannot request the same place as before due to the update of $C_{i}$ [Line 19 in Algo. 1], preventing a reoccurrence of the deadlock situation; i.e., a livelock situation if repeated indefinitely.

Theorem 2 (reachability).

Causal-PIBT has the reachability in biconnected graphs if $|A|<|V|$ .

Proof sketch.

Let $a_{i}$ be the agent with highest priority $\mathit{pori}$ . If $a_{i}$ is $\mathit{contracted}$ , this agent does not inherit any priority. Thus, $a_{i}$ can be $\mathit{requesting}$ so that $\mathit{head}_{i}$ is any neighbor node of $\mathit{tail}_{i}$ . If $a_{i}$ is $\mathit{requesting}$ , $a_{i}$ eventually moves to $\mathit{head}_{i}$ due to the construction of the depth-first search tree in a biconnected graph. These imply that $a_{i}$ can move to an arbitrary neighbor node in finite activations. By this, $a_{i}$ moves along the shortest path to its goal. Due to the prioritization scheme, an agent that has not reached its goal eventually inherits the highest priority $\mathit{pori}$ , and then starts moving along its shortest path to its goal. This ensures reachability. The detailed proof is found in the long version (Okumura, Tamura, and Défago 2020). ∎

Algorithm 2 Procedures of Causal-PIBT

1:procedure PriorityInheritance

A^{\prime\prime}\leftarrow\{a_{j}\;|\;a_{j}\in A,\mathit{mode}_{j}=\mathit{requesting},\mathit{tail}_{i}=\mathit{head}_{j}\}

3: if

A^{\prime\prime}=\emptyset

then return

a_{k}\leftarrow\mathop{\rm arg~{}max}\limits_{a_{j}\in A^{\prime\prime}}\mathit{ptmp}_{j}

5: if

\mathit{ptmp}_{k}\leq\mathit{ptmp}_{i}

then return

6: ReleaseChildren

\mathit{children}_{\mathit{parent}_{i}}\leftarrow\mathit{children}_{\mathit{parent}_{i}}\setminus\{a_{i}\}

\triangleright

\mathit{parent}_{i}

\mathit{parent}_{i}\leftarrow a_{k}

\mathit{children}_{k}\leftarrow\mathit{children}_{k}\cup\{a_{i}\}

\triangleright

a_{k}

\mathit{ptmp}_{i}\leftarrow\mathit{ptmp}_{k}

10:

S_{i}\leftarrow S_{k}\cup\{\mathit{head}_{i}\}

C_{i}\leftarrow\mathit{Neigh}(\mathit{tail}_{i})\cup\{\mathit{tail}_{i}\}\setminus S_{i}

11:end procedure

12:procedure ReleaseChildren

13: for

a_{j}\in\mathit{children}_{i}

\mathit{parent}_{j}\leftarrow a_{j}

\triangleright

a_{j}

14:

\mathit{children}_{i}\leftarrow\emptyset

15:end procedure

16:procedure Reset

17:

S_{i}\leftarrow\emptyset

C_{i}\leftarrow\mathit{Neigh}(\mathit{tail}_{i})\cup\{\mathit{tail}_{i}\}

18:

\mathit{ptmp}_{i}\leftarrow\mathit{pori}_{i}

19:end procedure

Proposition 1 (time complexity).

Assume that the maximum time required for one operation to update $S_{i}$ or $C_{i}$ (i.e., union, set minus) is $\alpha$ and for an operation of Line 14 in Algo. 1 is $\beta$ . Let $\Delta(G)$ denote the maximum degree of $G$ . For each activation, time complexity of Causal-PIBT in $\mathit{contracted}$ is $O(\Delta(G)+\alpha+\beta)$ , in $\mathit{requesting}$ is $O(\Delta(G)+\alpha)$ , and in $\mathit{extended}$ is $O(1)$ .

Proof sketch.

$|\mathit{children}_{i}|$ , $|A^{\prime}|$ used in $\mathit{requesting}$ , and $|A^{\prime\prime}|$ used in PriorityInheritance are smaller than equal to $\Delta(G)$ . Then, the complexity of PriorityInheritance is $O(\Delta(G)+\alpha)$ . ReleaseChildren is $O(\Delta(G))$ . Reset is $O(1)$ . We can derive the statements using the above. ∎

Refer to caption — Figure 3: The results in small benchmarks, shown as boxplots. The number of successful instances for GREEDY are 0, 5, 8, 11, 17, 26, 30, 36, 40, 51 for each $\bar{p}$ (from $0$ to $0.9$ ) in the upper plot. GREEDY failed all cases in the lower plot.

MAPF Plans as Hints

Although GREEDY and Causal-PIBT are for online situations, they can optionally use offline MAPF plans as hints while still being online and distributed schemes during execution. This can contribute to relaxing congestion because time-independent planning is shortsighted, i.e., planning paths anticipating only a single step ahead. Finding optimal MAPF plans is NP-hard (Yu and LaValle 2013; Ma et al. 2016), however, powerful solvers have been developed so far (Stern 2019); time-independent planning can use them. We describe how Causal-PIBT is enhanced by MAPF plans. Note that GREEDY can be extended as well. The intuition is to make agents follow original plans whenever possible.

Given a MAPF plan $\bm{\pi}$ , assume that $a_{i}$ knows $\pi_{i}$ a priori. Before execution, $a_{i}$ makes a new path $\tilde{\pi}_{i}$ by removing a node $\pi_{i}[t]$ such that $\pi_{i}[t]=\pi_{i}[t-1]$ from $\pi_{i}$ while keeping the order of nodes, since the action “stay” is meaningless in the time-independent model. During execution, $a_{i}$ manages its own discrete time $t_{i}$ internally (initially $t_{i}=0$ ).

The node selection phase [Line 14 in Algo. 1] is modified as follows. If $t_{i}\geq|\tilde{\pi}_{i}|-1$ , i.e., $a_{i}$ finished $\tilde{\pi}_{i}$ , $a_{i}$ follows the original policy; chooses a next node greedily from $C_{i}$ . Otherwise, if $\mathit{tail}_{i}=\pi_{i}[t_{i}]$ and $\pi_{i}[t_{i}+1]\in C_{i}$ , i.e., when $a_{i}$ can follow $\tilde{\pi}_{i}$ , $a_{i}$ selects $\pi_{i}[t_{i}+1]$ . Or else, $a_{i}$ selects the nearest node on the rest of $\tilde{\pi}_{i}$ , formally; $\mathop{\rm arg~{}min}\limits_{v\in C_{i}}\left\{\mathop{\rm min}\limits_{u\in\tilde{\pi}[t_{i}+1\colon]}\text{cost}(v,u)\right\}$ where $\tilde{\pi}[t\colon]=(\tilde{\pi}[t],\tilde{\pi}[t+1],\dots)$ .

$t_{i}$ is updated when $a_{i}$ in $\mathit{extended}$ is activated. If $\mathit{head}_{i}\in\tilde{\pi}_{i}[t_{i}+1\colon]$ , $t_{i}$ becomes the corresponding timestep $t^{\prime}$ such that $\tilde{\pi}_{i}[t^{\prime}]=\mathit{head}_{i}$ ; otherwise, do nothing.

Evaluation

The experiments aim at: 1) showing the robustness of time-independent planning, i.e., even though delays of agents are unpredictable, their trajectories are kept efficient, and, 2) verifying the usefulness to use MAPF plans as hints during executions.

We used the MAPF-DP problem because it can emulate imperfect executions. To adapt the time-independent model to MAPF-DP, rules of activation are required. We repeated the following two phases: 1) Each agent $a_{i}$ in $\mathit{extended}$ is activated with probability $1-p_{i}$ . As a result, $a_{i}$ successfully moves to $\mathit{head}_{i}$ with probability $1-p_{i}$ and becomes $\mathit{contracted}$ . 2) Pickup one agent in $\mathit{contracted}$ or in $\mathit{requesting}$ randomly then makes it activated, and repeat this until the configuration becomes stable, i.e, all agents in $\mathit{contracted}$ and $\mathit{requesting}$ do not change their states unless any agent in $\mathit{extended}$ is activated. The rationale is that time required by executing atomic actions except for agents’ moves is much smaller than that of the moves. We regard a pair of these two phases as one timestep. The strong termination was used to compare with existing two approaches for MAPF-DP: FSPs (Fully Synchronized Policies) and MCPs (Minimum Communication Policies). The evaluation is based on the sum of cost (SOC) metric. The simulator was developed in C++ ¹¹1 https://github.com/Kei18/time-independent-planning , and all experiments were run on a laptop with Intel Core i9 2.3GHz CPU and 16GB RAM. In all settings, we tried $100$ repetitions.

Small Benchmarks

First, we tested the time-independent planning in two small benchmarks shown in Fig. 3. The delay probabilities $p_{i}$ were chosen uniformly at random from $[0,\bar{p}]$ , where $\bar{p}$ is the upper bound of $p_{i}$ . The higher $\bar{p}$ means that agents delay often. $\bar{p}{=}0$ corresponds to perfect executions without delays. We manipulated $\bar{p}$ . GREEDY, Causal-PIBT, and the enhanced one using MAPF plans as hints (Causal-PIBT+) were performed. Those three were regarded to fail after $10000$ activations in total, implying occurring deadlocks or livelocks. FSPs and MCPs were also tested as comparisons. To execute FSPs, MCPs, and Causal-PIBT+, valid MAPF plans such that minimize SOC, which assumes following conflicts, were computed by an adapted version of Conflict-based Search (CBS) (Sharon et al. 2015), prior to performing MAPF-DP.

The results are shown in Fig. 3. Although GREEDY failed in most cases due to deadlocks, Causal-PIBT (+) succeeded in all trials due to the deadlock-recovery and the reachability. FSPs resulted in larger SOC compared to MCPs. The results of Causal-PIBT (+) were competitive to those of MCPs.

Random Grid

Next, we tested Causal-PIBT (+) using one scenario from MAPF benchmarks (Stern et al. 2019), shown in Fig. 4. We manipulated two factors: 1) changing $\bar{p}$ while fixing the number of agents ( ${=}35$ ), and, 2) changing the number of agents while fixing $\bar{p}$ ( ${=}0.5$ ). When the number of agents increases, the probability that someone delays also increases. We set sufficient upper bounds of activations. FSPs and MCPs were also tested. In this time, an adapted version of Enhanced CBS (ECBS) (Barer et al. 2014), bounded sub-optimal MAPF solver, was used to obtain valid MAPF-DP plans, where the suboptimality was $1.1$ .

Fig. 4 shows the results. The proposals succeeded in all cases even though the fields were not biconnected. The results demonstrated the time-independent planning outputs robust executions while maintaining the small SOC in the severe environment as for timing assumptions. In precisely, when $\bar{p}$ or the number of agents is small, MCPs was efficient, on the other hand, when these number increases, the time-independent plannings had an advantage.

Large Fields

Finally, we tested proposals using large fields from the MAPF benchmarks, as shown in Fig. 5. We respectively picked one scenario for each field, then tested while changing the number of agents. $\bar{p}$ is fixed to $0.1$ . Regular ECBS (suboptimality: $1.1$ ) was used for Causal-PIBT+. Note that Causal-PIBT+ does not require MAPF plans that assume following conflicts.

The results (in Fig. 5) demonstrate the advantage of using MAPF plans in Causal-PIBT. The proposed methods succeeded in all cases. We observed a very large SOC in map den312d due to the existence of a bottleneck. Such a structure critically affects execution delays.

Conclusion

This paper studied the online and distributed planning for multiple moving agents without timing assumptions. We abstracted the reality of the execution as a transition system, then proposed time-independent planning, and Causal-PIBT as an implementation that ensures reachability. Simulations in MAPF-DP demonstrate the robustness of time-independent planning and the usefulness of using MAPF plans as hints.

Future directions include the following: 1) Develop time-independent planning with strong termination, e.g., by adapting Push and Swap (Luna and Bekris 2011) to our model. 2) Address communication between agents explicitly. In particular, this paper neglects delays caused by communication by treating interactions as a black box, and the next big challenge is there.

Acknowledgments

We thank the anonymous reviewers for their many insightful comments and suggestions. This work was partly supported by JSPS KAKENHI Grant Numbers 20J23011 and 20K11685, and Yoshida Scholarship Foundation.

References

Atzmon et al. (2020) Atzmon, D.; Stern, R.; Felner, A.; Wagner, G.; Barták, R.; and Zhou, N.-F. 2020. Robust multi-agent path finding and executing. Journal of Artificial Intelligence Research 67: 549–579.
Barer et al. (2014) Barer, M.; Sharon, G.; Stern, R.; and Felner, A. 2014. Suboptimal variants of the conflict-based search algorithm for the multi-agent pathfinding problem. In Proc. Annual Symp. on Combinatorial Search (SoCS), 19–27.
Derakhshandeh et al. (2014) Derakhshandeh, Z.; Dolev, S.; Gmyr, R.; Richa, A. W.; Scheideler, C.; and Strothmann, T. 2014. Brief announcement: amoebot–a new model for programmable matter. In Proc. Symp. on Parallelism in Algorithms and Architectures, 220–222. ACM.
Dresner and Stone (2008) Dresner, K.; and Stone, P. 2008. A multiagent approach to autonomous intersection management. Journal of artificial intelligence research 31: 591–656.
Hönig et al. (2019) Hönig, W.; Kiesel, S.; Tinka, A.; Durham, J. W.; and Ayanian, N. 2019. Persistent and robust execution of mapf schedules in warehouses. IEEE Robotics and Automation Letters 4(2): 1125–1131.
Hönig et al. (2016) Hönig, W.; Kumar, T. S.; Cohen, L.; Ma, H.; Xu, H.; Ayanian, N.; and Koenig, S. 2016. Multi-agent path finding with kinematic constraints. In Proc. Intl. Conf. on Automated Planning and Scheduling (ICAPS), 477–485.
Kim et al. (2015) Kim, K.; Campbell, J.; Duong, W.; Zhang, Y.; and Fainekos, G. 2015. DisCoF+: Asynchronous DisCoF with flexible decoupling for cooperative pathfinding in distributed systems. In Proc. IEEE Intl. Conf. on Automation Science and Engineering (CASE), 369–376.
Luna and Bekris (2011) Luna, R.; and Bekris, K. E. 2011. Push and swap: Fast cooperative path-finding with completeness guarantees. In Proc. Intl. Joint Conf. on Artificial Intelligence (IJCAI), 294–300.
Ma, Kumar, and Koenig (2017) Ma, H.; Kumar, T. S.; and Koenig, S. 2017. Multi-agent path finding with delay probabilities. In Proc. AAAI Conf. on Artificial Intelligence, 3605–3612.
Ma et al. (2017) Ma, H.; Li, J.; Kumar, T.; and Koenig, S. 2017. Lifelong multi-agent path finding for online pickup and delivery tasks. In Proc. Intl. Joint Conf. on Autonomous Agents & Multiagent Systems (AAMAS), 837–845.
Ma et al. (2016) Ma, H.; Tovey, C.; Sharon, G.; Kumar, T. S.; and Koenig, S. 2016. Multi-agent path finding with payload transfers and the package-exchange robot-routing problem. In Proc. AAAI Conf. on Artificial Intelligence, 3166–3173.
Okumura et al. (2019) Okumura, K.; Machida, M.; Défago, X.; and Tamura, Y. 2019. Priority Inheritance with Backtracking for Iterative Multi-agent Path Finding. In Proc. Intl. Joint Conf. on Artificial Intelligence (IJCAI), 535–542.
Okumura, Tamura, and Défago (2020) Okumura, K.; Tamura, Y.; and Défago, X. 2020. Time-Independent Planning for Multiple Moving Agents. CoRR abs/2005.13187. URL https://arxiv.org/abs/2005.13187.
Sha, Rajkumar, and Lehoczky (1990) Sha, L.; Rajkumar, R.; and Lehoczky, J. P. 1990. Priority inheritance protocols: An approach to real-time synchronization. IEEE Transactions on Computers 39(9): 1175–1185.
Sharon et al. (2015) Sharon, G.; Stern, R.; Felner, A.; and Sturtevant, N. R. 2015. Conflict-based search for optimal multi-agent pathfinding. Artificial Intelligence 219: 40–66.
Stern (2019) Stern, R. 2019. Multi-Agent Path Finding–An Overview. In Artificial Intelligence - 5th RAAI Summer School, volume 11866 of LNCS, 96–115. Springer.
Stern et al. (2019) Stern, R.; Sturtevant, N.; Felner, A.; Koenig, S.; Ma, H.; Walker, T.; Li, J.; Atzmon, D.; Cohen, L.; Kumar, T.; et al. 2019. Multi-Agent Pathfinding: Definitions, Variants, and Benchmarks. In Proc. Intl. Symp. on Combinatorial Search (SoCS), 151–159.
Tel (2000) Tel, G. 2000. Introduction to distributed algorithms. Cambridge university press.
Wang and Rubenstein (2020) Wang, H.; and Rubenstein, M. 2020. Walk, Stop, Count, and Swap: Decentralized Multi-Agent Path Finding With Theoretical Guarantees. IEEE Robotics and Automation Letters 5(2): 1119–1126.
Wiktor et al. (2014) Wiktor, A.; Scobee, D.; Messenger, S.; and Clark, C. 2014. Decentralized and complete multi-robot motion planning in confined spaces. In Proc. IEEE/RSJ Intl. Conf. on Intelligent Robots and Systems (IROS), 1168–1175.
Wurman, D’Andrea, and Mountz (2008) Wurman, P. R.; D’Andrea, R.; and Mountz, M. 2008. Coordinating hundreds of cooperative, autonomous vehicles in warehouses. AI magazine 29(1): 9–20.
Yu and LaValle (2013) Yu, J.; and LaValle, S. M. 2013. Structure and Intractability of Optimal Multi-Robot Path Planning on Graphs. In Proc. AAAI Conf. on Artificial Intelligence.

Appendix: Proof of Reachability

In this section, we formally derive Theorem 2. We will use $V(G^{\prime})$ and $E(G^{\prime})$ as vertices and edges on a graph $G^{\prime}$ to clarify the graph that we mention.

At first, let us define a subgraph $H$ of $G$ , called a parent-child graph, to grasp the relationship between agents in Causal-PIBT. Although $H$ is defined by a configuration formally, we just denote $H$ when we mention an invariant property of the parent-child graph.

Definition 1 (parent-child graph).

Given a configuration $\gamma^{k}$ , a parent-child graph $H^{k}$ is a subgraph of $G$ with the following properties. Let $B^{k}\subseteq A$ be a set of agents occupying only one node in $\gamma^{k}$ , i.e., $B^{k}=\{a_{j}\;|\;a_{j}\in A,\mathit{mode}_{j}\neq\mathit{extended}\}$ . Then, $H^{k}=(V(H^{k}),E(H^{k}))$ , where $V(H^{k})=\{\mathit{tail}_{j}\;|\;a_{j}\in B^{k}\}$ and $E(H^{k})=\{(\mathit{tail}_{j},\mathit{tail}_{k})\;|\;a_{j}\in B^{k},a_{k}\in\mathit{children}_{j}\}$ .

The next lemma states that $H$ transits while keeping its graph property; forest.

Lemma 1.

$H$ is always a forest.

Proof.

Given the initial configuration $\gamma^{0}$ , $H^{0}$ is obviously a forest. Assume that $H^{k-1}$ is a forest, where $k>0$ . Assume further that $a_{i}$ is activated and the configuration transits from $\gamma^{k-1}$ to $\gamma^{k}$ . We now show that $H^{k}$ is also a forest. There are three kinds of causes for changing edges in $H^{k}$ from $H^{k-1}$ .

The first case is the procedure ReleaseChildren. This removes all edges in $H^{k-1}$ from $\mathit{tail}_{i}$ to its children’s tail. This is a decomposition of a subtree in $H^{k-1}$ , thus, $H^{k}$ is still a forest.

The second case is the procedure PriorityInheritance. If there exists an agent $a_{k}$ as a new parent, this procedure first $\mathit{tail}_{i}$ be isolated in $H^{k-1}$ . Then, $a_{i}$ updates its parent, i.e., a new edge between $\mathit{tail}_{i}$ and $\mathit{tail}_{k}$ is added to $H^{k}$ . This update still keeps $H^{k}$ being a forest. Note that cycles are not constructed; agents in one component have the same $\mathit{ptmp}$ due to priority inheritance. Priority inheritance occurs only between agents with different $\mathit{ptmp}$ .

The third case is that $a_{i}$ transits from $\mathit{requesting}$ to $\mathit{extended}$ . Before being $\mathit{extended}$ , $a_{i}$ makes $\mathit{tail}_{i}$ isolated. This is a decomposition of a subtree in $H^{k-1}$ , thus, $H^{k}$ is kept as a forest.

By induction, $H$ is always a forest. ∎

We next introduce a dominant agent/tree. Intuitively, it is an agent or a tree with the highest priority in one configuration. Note that there exists a configuration without a dominant agent/tree, e.g., when the agent with highest $\mathit{pori}$ is $\mathit{extended}$ .

Definition 2 (dominant agent/tree).

Assume an agent $a_{d}$ in
$\mathit{contracted}$ such that $\mathit{pori}_{d}>\mathit{pori}_{j},\forall a_{j}\in A\setminus\{a_{d}\}$ . $a_{d}$ is a dominant agent when it becomes $\mathit{requesting}$ , until it becomes $\mathit{extended}$ . A component of the parent-child graph $H$ containing $\mathit{tail}_{d}$ is a dominant tree $T_{d}$ .

Since $H$ is a forest from Lemma 1, $T_{d}$ is a tree. Subsequently, we state the condition where the dominant agent can move to its desired node, then derive reachability.

Definition 3 (movable agent).

An agent $a_{m}$ is said to be movable in a given configuration when $\mathit{mode}_{m}=\mathit{requesting}$ and $\lnot\mathit{occupied}({\mathit{head}_{m}})$ .

Lemma 2.

If there is a dominant tree $T_{d}$ and a movable agent $a_{m}$ such that $\mathit{tail}_{m}\in V(T_{d})$ , then a dominant agent $a_{d}$ eventually becomes $\mathit{extended}$ without being $\mathit{contracted}$ .

Proof.

Only the procedure PriorityInheritance adds new edges to $H$ as shown in the proof of Lemma 1. Thus, all agents in $T_{d}$ have the same temporal priority, i.e., $\mathit{ptmp}_{d}$ . This means that no agents outside of $T_{d}$ can disrupt $T_{d}$ .

Considering the construction of $T_{d}$ , all agents on a path from $\mathit{tail}_{d}$ to $\mathit{tail}_{m}$ in $T_{d}$ are $\mathit{requesting}$ . The other agents in $T_{d}$ are $\mathit{contracted}$ and do nothing if they are activated. Moreover, if agents in $\mathit{requesting}$ in $T_{d}$ excluding $a_{m}$ are activated, they do nothing. As a result, only the activation of $a_{m}$ can update states of agents in $T_{d}$ .

Let $a_{m^{\prime}}$ be $\mathit{parent}_{m}$ . Any agent $a_{i}$ in $\mathit{requesting}$ with $\mathit{head}_{i}=\mathit{head}_{m}$ will defeat since $\mathit{ptmp}_{m}=\mathit{ptmp}_{d}$ . As a result, when $a_{m}$ is activated, it certainly becomes $\mathit{extended}$ and departs from $T_{d}$ . $a_{m}$ becomes $\mathit{contracted}$ in finite activations. During this transition, any agent $a_{i}$ in $\mathit{requesting}$ with $\mathit{head}_{i}=\mathit{head}_{m^{\prime}}$ will defeat since $\mathit{ptmp}_{m^{\prime}}=\mathit{ptmp}_{d}$ . Now, $\mathit{head}_{m^{\prime}}$ is not occupied by any agents. We have a new movable agent, namely, $a_{m^{\prime}}$ . By the same procedure, $a_{m^{\prime}}$ moves to its head in finite time. By induction, $a_{d}$ eventually becomes $\mathit{extended}$ without being $\mathit{contracted}$ . ∎

Lemma 3.

If $G$ is biconnected and $|A|<|V|$ , a dominant agent $a_{d}$ eventually becomes $\mathit{extended}$ without being $\mathit{contracted}$ .

Proof.

First, we show that $a_{d}$ does not become $\mathit{contracted}$ . Assume by contradiction that $a_{d}$ becomes $\mathit{contracted}$ . Considering the process of the construction of the dominant tree $T_{d}$ , all agents $a_{i}$ in $T_{d}$ excluding $a_{d}$ are $\mathit{contracted}$ and $C_{i}=\emptyset$ . This implies that there exists no neighbor nodes of $V(T_{d})\setminus\{\mathit{tail}_{d}\}$ in $V(G)$ . Since $G$ is biconnected, although $\mathit{tail}_{d}$ is removed from $G$ , there exists a path between any two nodes in $V(G)$ . Thus, $V(T_{d})$ must spans $G$ , i.e., $|V|=|A|$ . This is a contradiction, so, $a_{d}$ never becomes $\mathit{contracted}$ .

Since $T_{d}$ tries to expand so that it spans $G$ , and $|A|<|V|$ , we have eventually a movable agent in $T_{d}$ . According to lemma 2, $a_{d}$ eventually becomes $\mathit{extended}$ . ∎

Theorem 2 (reachability).

Causal-PIBT ensures reachability in biconnected graphs if $|A|<|V|$ .

Proof.

Let an agent be $a_{h}$ with the highest $\mathit{pori}$ . If $a_{h}$ is $\mathit{contracted}$ , this agent does not inherit any priority. Thus, $a_{h}$ can be $\mathit{requesting}$ so that $\mathit{head}_{h}$ is any neighbor nodes of $\mathit{tail}_{h}$ . If $a_{h}$ is $\mathit{requesting}$ , $a_{h}$ is a dominant agent. According to lemma 3, $a_{h}$ eventually moves to $\mathit{head}_{h}$ . These imply that $a_{h}$ can move to an arbitrary neighbor node in finite activations. By this, $a_{h}$ moves along the shortest path to its goal, then drops its priority $\mathit{pori}_{h}$ .

Due to the above mechanism, an agent that has not reached its goal eventually gets the highest $\mathit{pori}$ , then it starts moving along its shortest path to its goal. This satisfies reachability. ∎

It is interesting to note that the necessary condition to ensure reachability in Causal-PIBT is more restrictive than in PIBT. This is due to the prohibition of rotations (cyclic conflicts) by the time-independent model.