# Optimal Multi-Agent Path Finding for
Precedence Constrained Planning Tasks

###### Abstract

Multi-Agent Path Finding (MAPF) is the problem of finding collision-free paths
for multiple agents from their start locations to end locations. We consider
an extension to this problem, Precedence Constrained Multi-Agent Path Finding
(PC-MAPF), wherein agents are assigned a sequence of planning tasks that
contain precedence constraints between them. PC-MAPF has various applications,
for example in multi-agent pickup and delivery problems where some objects
might require multiple agents to collaboratively pickup and move them in
unison. Precedence constraints also arise in warehouse assembly problems where
before a manufacturing task can begin, its input resources must be
manufactured and delivered. We propose a novel algorithm, Precedence
Constrained Conflict Based Search (PC-CBS), which finds makespan-optimal
solutions for this class of problems. PC-CBS utilizes a Precedence-Constrained
Task-Graph to define valid intervals for each planning task and updates them
when precedence conflicts are encountered. We benchmark the performance of
this algorithm over various warehouse assembly, and multi-agent pickup and
delivery tasks, and use it to evaluate the sub-optimality of a recently
proposed efficient baseline.

111The first two authors contributed equally to this work.

##  1 Introduction

The classical Multi-Agent Path Finding (MAPF) problem considers the case where
each agent has to solve one planning task while avoiding collisions amongst
themselves. Many real world applications of MAPF require agents to complete
more than one task. Recent work has addressed Multi-Agent Pickup and Delivery
(MAPD) [1] which aims to solve sequential planning tasks for a group of
agents. The sequential nature of tasks in MAPD gives rise to in-schedule
dependencies for each agent. Further, cross-schedule dependencies between
agents can develop due to precedence constraints which require completion of
certain tasks by other agents as a prerequisite for starting other dependent
tasks. The class of problems with inter-task precedence constraints, defined
as Precedence-Constrained Multi-Agent Path Finding (PC-MAPF), models a variety
of scenarios in warehouse applications. In this paper, we are motivated by the
use cases of PC-MAPF in warehouse assembly and collaborative MAPD.

In the former setting, one can consider a warehouse with manufacturing
stations. Agents are required to transfer materials between manufacturing
locations while avoiding collisions. The overall assembly problem comprises
sub-assembly components which depend on each other. Temporal precedence
constraints exist between planning tasks because each manufacturing station
can generate its output only after receiving its required input materials.

The other setting is a generalised formulation of MAPD where objects require
more than one agent for their transport. Here, agents must arrive at the
object pickup location before moving in unison towards the drop-off point.
Thus, the beginning of the transport is constrained by the arrival of each
collaborating agent at the pickup location. Recent work [2, 3] has
demonstrated the feasibility of low-level control required for collaborative
MAPD, using multiple drones to lift objects that cannot be picked up by a
single drone.

Fig. 1: Example PC-MAPF problem where agent $R_{1}$ is assigned a transport
task from $S1$ to $G1$ and agent $R_{2}$ is assigned a transport task from
$S2$ to $G2$. $R_{2}$ can pickup the object at $S2$ only after $R_{1}$
completes delivery at $G_{1}$. (represented by a precedence constraint edge)

Conflict-Based Search (CBS) [4], a state-of-the-art optimal algorithm for
MAPF, finds shortest paths for each agent by updating their solution paths
iteratively to avoid collision conflicts between agents. Due to the additional
cross-schedule dependencies, an optimal algorithm for the PC-MAPF problem
domain will also have to consider the valid intervals for starting each
planning task. The algorithm proposed by [5] is closest to our work and
attempts to solve the PC-MAPF problem optimally using a hierarchical algorithm
based upon CBS. We shall refer to this algorithm as Hierarchical-CBS (H-CBS).
H-CBS builds plans for a group of agents by finding collision-free paths for
each task segment individually which are consistent with inter-task precedence
constraints. However, as noted by [6], due to segmented nature of planning,
H-CBS is sub-optimal for problems requiring pre-emptive delays (example shown
in Fig. 4). In such cases, though there is no constraint on the plan of an
individual task, delaying an agent’s plan pre-emptively can shorten the
duration of the overall plan.

Fig. 2: Task Graph corresponding to Fig 1. GO nodes represent movement to
pickup locations & CARRY nodes depict the transport tasks. Agents assigned to
each task are indicated. The possible valid interval for starting each task is
displayed (without considering inter-agent collisions). Despite $R_{2}$ being
able to start CARRY-2 at timestep 2, CARRY-1 cannot finish before timestep 4.
Hence, the valid interval for starting CARRY-2 begins from timestep 4.

As shown in Figure 2, any PC-MAPF can be represented a Task Graph, where each
node denotes a planning task to be completed by a set of agents from a start
location to an end location. The directed edges denote precedence constraints
between tasks, i.e, all preceding tasks must have been completing before a
task is allowed to begin. In this paper, we present the first algorithm to
solve any PC-MAPF problem optimally, Precedence Constrained Conflict Based
Search (PC-CBS), a two-level algorithm comprising a Conflict Tree (C.T) at its
high level and a multi-waypoint A* at the low level. At the high level of the
algorithm is defined the task graph for the problem along with valid intervals
of each task. As in CBS, the plans of agents are constrained and updated in a
tree-like fashion when conflicts are encountered. Apart from collision
conflicts which constraint the plans of each agent, we additionally introduce
precedence conflicts, which arise when agents’ plans are inconsistent with the
defined task graph for the problem. These conflicts constraint the valid
intervals for each task in the Task Graph. The low-level search of the
algorithm employs an optimal multi-waypoint A* search which finds paths for
each agent separately considering the start and end locations of each planning
task as waypoints. Like in H-CBS, the low-level search makes use of tie-
breaking heuristics [7] to choose paths which are likely to reduce conflicts
in future iterations of CBS. Our key contributions are summarized below:

  * •

We show that any PC-MAPF problem can be represented as a Task Graph with valid
intervals for starting each task.

  * •

We propose, PC-CBS, the first optimal algorithm to find minimum-makespan
solutions for any PC-MAPF problem.

  * •

We benchmark the performance of PC-CBS in warehouse assembly and collaborative
MAPD problem instances and evaluate the sub-optimality of a recently proposed
baseline.

The rest of the paper is organized as follows. Section 2 presents existing
works in this direction. We formulate the PC-MAPF problem setup and its task
graph representation in Section 3. In Section 4, we detail our proposed
methodology leveraging search algorithms and prove its optimatility. Further,
we discuss the Hierarchical-CBS (H-CBS) algorithm in Section 5. Section 6
presents the experimental results demonstrating the performance of our
proposed method. Finally, Section 7 concludes the paper.

##  2 Related Work

Despite the MAPF problem with fixed goals proven to be NP-Hard [8] under the
sum of costs and makespan objectives, there have been effective attempts [9,
10] at building optimal algorithms for this problem. Among them, a tree-based
algorithm, Conflict Based Search (CBS) [4], has seen wide applications in
MAPF. In recent literature, various improvements [11] have been proposed on
top of CBS including extensions to continuous time domains [12], and bounded-
subpotimal algorithms [13]. Since MAPF is a special case of the PC-MAPF
problem without inter-task precedence constraints, we claim that solving PC-
MAPF optimally for the same objectives are also at least NP-Hard. Our work
builds upon the CBS algorithm.

Instead of assuming fixed goals, the Anonymous MAPF (AMAPF) is the problem of
assigning goals for each agent. [14] show that AMAPF is no longer NP-Hard
under the makespan objective and can be reduced to a maximum-flow problem. TA-
CBS [15] uses a high-level search forest instead of a tree to optimally assign
goals to agents while minimizing the sum of costs over all the tasks. They
also propose a bounded sub-optimal version of their algorithm, which scales
gracefully with the size of the problem. The popular M* [10], an optimal MAPF
algorithm was extended in [16] by integrating it with task reassignments. Co-
CBS [17] integrates a cooperation-planning module into CBS and introduces the
problem of active collaboration by assigning ”meeting” points for transfer of
goods in a warehouse setting.

There have been numerous works in finding collision-free paths for a sequence
of pickup and delivery tasks. TCBS [18] solves the combined task allocation
and path-finding problem where agents can be assigned a sequence of tasks.
However, the performance of the algorithm significantly degrades upon an
increase in the number of tasks. Two offline algorithms for multi-agent pickup
and delivery have been proposed by [19], both of which first assign a sequence
of tasks to agents by solving a special Travelling Salesman Problem (TSP) that
does not consider collisions between agents. These algorithms then plan for
collision-free trajectories for agents that solve the assigned task sequences.
[20] consider an online setting where new pickup and delivery tasks can
arrive. It proposes two decentralized algorithms to solve this problem that
performs prioritized search over agents using token passing. However, these
algorithms are sub-optimal. Other work [21] attempts to solve this problem by
using a Multi-Level A* supported by a novel heuristic to find the shortest
path for agents given an ordered list of goals.

We are interested in solving MAPF with precedence constraints between planning
tasks. In the taxonomy for multi-robot task allocation listed by [22], PC-MAPF
belongs to a wide class of problems having cross-schedule dependencies. We
have considered the precedence constrained case where completion of a task is
pre-requisite for another, but cross-schedule dependencies can also arise when
tasks need to be synchronized or require time-windowing, i.e, a task must be
completed while a larger task is in progress. [23, 24] analyze synchronization
and precedence constraints commonly arising in vehicle routing and scheduling
problems. However, an assumption made in this line of work is that collisions
do not arise between agents, which is in contrast to the MAPF literature.

A recurring theme in Task Allocation and MAPF (TA-MAPF) consists of solving a
relaxed task assignment problem, for example without collisions, and then
finding feasible solution paths for agents given a particular assignment. The
work by [5] too, which is closest to ours, at the top level solves a task
assignment problem without considering collisions between agents. For finding
solutions to the PC-MAPF problem formed after task assignment, it proposes
H-CBS. However, this algorithm has been shown to be sub-optimal for a class of
pre-emptive delay problems by [6]. To the best of our knowledge, ours is the
first work which optimally solves the PC-MAPF problem. Since the focus of this
paper is to find optimal solutions given the task assignment, we use a greedy
strategy to assign tasks to agents during problem generation. Our PC-CBS
algorithm can be easily extended by a task assignment module.

##  3 Problem Formulation and Notation

We first discuss the classical MAPF problem, and then describe the
specifications added to it in the general PC-MAPF problem.

###  3.1 Classical MAPF

In classical MAPF, the configuration space each agent is represented by an
undirected graph $G=\\{V,E\\}$, where $V$ is the set of vertices in $G$, each
of which represents a valid configuration for the agent, and $E$ is the set of
edges, each representing possible movements from one configuration to another
for each agent. Time is assumed to be discretized into time steps, and the an
agent can move over any edge in one time step. The team of agents,
$A=\\{a_{1},\dots,a_{N}\\}$, is assigned a start configuration,
$S=\\{s_{1},\dots,s_{N}\\}\in V$ and goal configuration,
$G=\\{g_{1},\dots,g_{N}\\}\in V$. All agents start at timestep $0$ from their
start configurations. A feasible joint path for the problem is defined by
$\pi=\\{\pi_{1},\dots,\pi_{N}\\}$, where an individual path
$\pi_{i}=\\{v^{1}_{i},\dots,v^{k}_{i}\\}$ describes a sequence of
configurations for agent $a_{i}$ from $s_{i}$ to $g_{i}$ which avoids
collisions with the paths of other agents. The path cost of an individual
agent is the time taken to reach the goal. An optimal solution optimizes an
objective function over the joint path. Common objective functions include the
sum of costs, which adds up the path costs for each agent, and the makespan,
which considers the maximum path cost among all agents. Two agents are said to
be in a collision if they occupy the same vertex in $V$ at the same timestep,
or if they exchange positions between timesteps, i.e, two agents move from
opposite ends of the same edge represented by $v_{j}\leftrightarrow
v_{j},v_{i,j}\in V$, they are said to be in collision.

###  3.2 PC-MAPF

We now define PC-MAPF which incorporates multiple planning tasks for each
agent. As in classical MAPF, paths are planned over an undirected graph,
$G=\\{V,E\\}$ with unit edge costs, and agents are defined an initial starting
configuration $S$. We further define goal configurations for each agent that
act as final parking locations, i.e, their paths must end at these locations.
Additionally, a set of pickup and delivery tasks $T=\\{t_{1}\dots t_{m}\\}$
are required to be completed by a team of agents. The pickup and delivery
locations of tasks are called task endpoints. Each agent $a_{i}$ is assigned a
sequence of tasks that it must complete, called a task allotment list. There
exists a set of precedence constraints between tasks, which is defined as
$t_{i}\rightarrow t_{j}$ denoting that $t_{i}$ must be completed before
$t_{j}$ can begin. Each task $t_{i}$ $\in$ $T$ is a tuple
$(R_{i},s_{i},g_{i})$ where $R_{i}$ is the set of agents allocated to this
task, $s_{i}$ denotes the pickup location of the task, and $g_{i}$ denotes the
delivery location. Even when there are no explicit constraints between tasks,
precedence constraints exist during the planning of a task requiring more than
one agent for pickup. All agents collaborating for the task have to arrive at
the pickup location before delivery can be initiated.

A feasible solution path in PC-MAPF must avoid collision and precedence
conflicts between agents. An important distinction to classical MAPF is that
here agents are said to be in a collision if they occupy the same vertex in
$G$ and are not carrying out the same pickup and delivery task, i.e, the task
required more than one agent. To avoid precedence conflicts, for each task
$t_{i}\in T$, the set of agents allocated to this task, $R_{i}$ must start
pickup at the same timestep and tasks which are precedent to $t_{i}$ must have
been completed before $t_{i}$ begins. In this work, we find makespan optimal
solutions to PC-MAPF problems which is equivalent to the last timestep at
which an agent arrives at their final parking location.

Fig. 3: Agents $R\\{1-4\\}$ begin at their distinct initial locations at
timestep $0$ and start a collaborative ”carry” task at different timesteps
resulting in a precedence conflict

###  3.3 Task Graph Representation

A directed acyclic graph (DAG) can be constructed to define any PC-MAPF
problem called the Task Graph, $G_{T}=\\{V_{T},E_{T}\\}$. Each vertex of the
graph $v\in V_{T}$ represents any planning task consisting of a set of agent
from one position to another. This may either be a ”CARRY” vertex which is a
pickup and delivery task called a or a ”GO” vertex, requiring the agent to
arrive at the pickup location of a transport task. A directed edge,
$(v\rightarrow u)\in E_{T}$ represents a precedence constraint which means
that $v$ must be completed before $u$ can start. Each agent is assigned a task
allotment list, which contains a sequence of pickup and delivery tasks it must
execute. Along with the ”GO” tasks the agent must execute to reach the pickup
points, these tasks are all connected by edges of the Task Graph and act as
precedence constraints.

In Collaborative MAPD, multiple ”GO” tasks arrive at the same pickup and
delivery task vertex (eg. Fig 3). The end point of the ”GO” task is same as
the start point of the successor task. However, precedence constraint edges
are not required to be connected with their task end points. These edges may
also represent the arrival of input resources around manufacturing stations
after which generation of output goods can begin. For each planning task
vertex, we further define two intervals at its endpoints within which an agent
has to start and end that particular task. If the start point of a task has an
interval $(t_{min},t_{max})$, agents while executing this task can occupy
positions at the start only within this time interval. An example Task Graph
has been shown in Fig 2.

##  4 Proposed Approach

Conflict Based Search (CBS) [4] is a complete and optimal solver for classical
MAPF. It solves a given problem by finding plans for each agent separately,
detecting collision conflicts between these plans. The conflicts are resolved
by replanning for the individual agents subject to specific constraints. CBS
runs two search algorithms — a low-level search algorithm that finds paths for
individual agents subject to a given set of constraints and a high-level
search algorithm that maintains a binary tree called the conflict tree (CT).
Each node of the CT chooses conflicts to resolve, and divides the node into
two sub-nodes. If there are no more conflicts to resolve in a node, it is said
to be a leaf node which contains a feasible solution path to the problem. The
CT is searched in a best-first manner based on the makespan cost of a node.

PC-CBS extends CBS to PC-MAPF problems. We note that CBS assigns collision
constraints only to specific agents. Our key contribution is the introduction
of precedence conflicts between tasks and constraints that arise from these
conflicts. While collision conflicts arise when the position of agents at the
same location are intersecting in time, precedence conflicts arise where the
combined plan of the agents does not adhere to the Task Graph of the problem.
The constraints are imposed at the task level and apply to all agents. The
low-level search of PC-CBS ensures that agents adhere not only to the
collision constraints imposed on them, but also begin and end tasks within
defined intervals.

An example of a precedence conflict is shown in Fig 3. Here, collaborating
agents pick up an assigned object at different timesteps in their individual
plans. In order to resolve precedence conflicts between agents, PC-CBS
branches out into nodes that contain constraints over task intervals that aim
to invalidate the earlier found joint plan. These constraints update defined
valid intervals of the task’s end-points, and also influences the intervals of
tasks connected to this task node in the Task Graph. In this section, we first
explain the high level search for building the conflict tree and then we show
how the constraints are imposed on the low level multi-waypoint A* search by
precedence conflicts. Finally, we prove that our proposed algorithm is
complete and optimal.

###  4.1 High Level Search

1

Input : Task Graph $G_{T}=\\{V_{T},E_{T}\\}$

2

3$Root$.constraints $\leftarrow$ $\emptyset$ ;

4 $Root$.intervals $\leftarrow$ Initialize Valid Task Intervals() ;

$Root$.solution $\leftarrow$ invoke low-Level search for each agent $r_{i}$ ;

// find individual plans for agent using low level search in decreasing order
of estimated execution times

5 insert $Root$ in OPEN list ;

6 while  _solution not found_ do

P $\leftarrow$ pop best node from OPEN ;

// lowest makespan cost

7 for  _$t_{i}$ $\in$ topological_sort($G_{T}$)_ do

8 if  _$t_{i}\ consistent\ with\ G_{T}$_ then

9 continue ;

10

11 children $=$ Resolve Precedence Conflict() ;

12 OPEN.insert(children) ;

13 Goto next iteration of while ;

14

15 Validate paths in P until a collision conflict;

16 if  _P has collision conflict_ then

17 ($R_{p}$, $R_{q}$, $v$, timestep) $\leftarrow$ first collision conflict ;

18 children $=$ Resolve Collision Conflict() ;

19 OPEN.insert(children) ;

20 continue ;

21

return P.solution ;

// P is goal node

22

Algorithm 1 High - Level Search of PC-CBS

The High Level Search is a Conflict Tree (C.T). A node $N$ of the PC-CBS C.T
is defined by three attributes:

  1. 1.

$N.constraints\rightarrow$ Set of vertices or edges invalidated for agents at
particular timesteps.

  2. 2.

$N.intervals\rightarrow$ Valid intervals for endpoints in each planning task
of the Task Graph.

  3. 3.

$N.solution\rightarrow$ Solution paths for each agent which are consistent
with the constraints and task intervals.

At the root node (Lines 1-3 in Alg. 1), there are no constraints and the valid
intervals for each task are initialised by solving the planning problem
without considering collisions with each other. Hence, all task endpoints have
a defined minimum time before which they cannot be reached but there is no
maximum bound yet, i.e, all intervals have a lower bound and an infinite upper
bound. The solution paths are then computed by invoking the low level search.
The tree is searched using a best-first strategy, expanding the nodes whose
solution paths have the lowest makespan, thus ensuring makespan-optimal
solutions.

Following the work on prioritized motion planning by [25], whenever paths have
to be computed for multiple agents, the low-level search is called in
decreasing order of the estimated execution times of their task sequences. For
the first calls of the low-level search, the estimate of an agent’s total
execution time is the minimum time at which an agent can complete the last
task in its itinerary. In following iterations, whenever a child node in the
C.T is expanded, the path costs in the parent’s solution paths are used for
this purpose. The tie breaking heuristics of the low-level search find
solutions with the minimum number of conflicts provided the path does not
increase the makespan cost of the overall plan. This allows agents whose path
costs are low to delay their plans in order to avoid conflicts with other
agents.

Conflicts are detected in a hierarchical manner by the high-level search which
first checks the path for precedence conflicts. If there are any present, it
splits into child CBS nodes that inherit the constraints of their parents
along with additional constraints that aim to invalidate the plan found by its
parent. The node is first checked for the existence of any precedence
conflicts. If there exists a predecessor for any task which ends after it
begins, a precedence conflict is detected and the intervals for this task are
updated by Algorithm 2. Once a node does not have any more precedence
conflicts, it is checked for collision conflicts. In case collision conflicts
are present, it splits with nodes with collision constraints on the agents.
Prioritization of precedence conflicts over collision conflicts is essential
to the validity of the algorithm as it ensures that the paths of individual
agents carrying out the same collaborative task do not differ and the Task
Graph is not violated.

###  4.2 Resolving Precedence Conflicts

Similar to how CBS resolves collision conflicts, we aim to eliminate invalid
solutions from the search space. This is done by changing the valid intervals
for starting or ending any task. For example, consider the precedence conflict
in Fig 3 where the agents be assigned the same collaborative carry task. Due
to being at different initial locations, the first node expanded in by the
high-level search returns a set of paths where the agents execute pickup at
different timesteps - namely $R1$ at $t=5$, $R2$ at $t=10$, $R3$ at $t=7$, and
$R4$ at $t=12$. As there is a precedence conflict, this CBS node is
invalidated and its child nodes must be generated. We propose to split by
generating two child nodes which breaks the start point intervals of this task
into two disjoint intervals (Algorithm 2). Any timestep can be chosen for
splitting this interval as long as the original interval shrinks. Empirically
we find that taking the maximum timestep among the predecessor tasks works the
best. The new C.T. node whose interval is upper bounded by the maximum time of
the preceding task is often infeasible and gets killed in the next iteration
of invoking the low-level search. This keeps the branching factor of the tree
in check while mantaining completeness. In 3, let’s say the initial valid
interval for starting the CARRY task is $[0,\infty)$. This interval is broken
down into $[0,11]$ and $[12,\infty)$ by our expansion procedure.

Input : Task Graph $G_{T}$, Parent Node P, Conflict Task T

split_timestep = max end-time for Pred(T) ;

// for predecessors of T in $G_{T}$, find the maximum timestep violation

old_interval = P.intervals[T].start ;

// extract previous valid interval of start point of task from parent node

1 if  _split_timestep $>$ old_interval.maxTime_ then

2 split_timestep = old_interval.maxTime;

3

4 maxInterval = [old_interval.minTime, split_time-1] ;

5 minInterval = [split_time, old_interval.maxTime] ;

6 Spawn children nodes with updated Intervals ;

7 return children ;

Algorithm 2 Resolve Precedence Conflict

It is noted that dividing the valid intervals of a task into disjoint sets
preserves all possible sets of solutions. However, the effectiveness of CBS is
achieved by being able to delete invalid solutions from the search space. PC-
CBS does this while resolving precedence conflicts by exploiting the structure
of the Task Graph. By updating the task interval of one task, it is possible
to deduce update rules for the task intervals of other tasks as shown in
Algorithm 4. In Lines 1-6, the task graph is iterated in topological order.
For each task node it is inferred that its minimum starting time must be
greater than or equal the minimum end-time of all its predecessors. Further,
we know the minimum cost required to complete each task is the path length of
a task without considering any collisions. This is used to update the end-
time. Similarly, in Lines 7-12, the maximum times of each task are updated via
a reverse topological sort by leveraging the fact that the maximum end-time of
a task must be less than or equal to the maximum start-time of a successor
task.

Input : C.T. Node $N$

1

2for  _$t_{i}$ $\in$ topological_sort($G_{T}$)_ do

3 for  _$t_{pred}$ $\in$ predecessors($t_{i}$)_ do

4 if  _N.intervals[ $t_{pred}$].endpoint.minTime ¿
N.intervals[$t_{i}$].startpoint.minTime _ then

5 N.intervals[$t_{i}$].startpoint.minTime =
N.intervals[$t_{pred}$].endpoint.minTime ;

6

7

8 if  _N.intervals[ $t_{i}$].startpoint.minTime + min-cost($t_{i}$) ¿
N.intervals[$t_{i}$].endpoint.minTime_ then

9 N.intervals[$t_{i}$].endpoint.minTime =
N.intervals[$t_{i}$].startpoint.minTime + min-cost($t_{i}$) ;

10

11

12for  _$t_{i}$ $\in$ reverse_topological_sort($G_{T}$)_ do

13 for  _$t_{succ}$ $\in$ successors($t_{i}$)_ do

14 if  _N.intervals[ $t_{succ}$].startpoint.maxTime ¡
N.intervals[$t_{i}$].endpoint.maxTime _ then

15 N.intervals[$t_{i}$].endpoint.maxTime =
N.intervals[$t_{succ}$].startpoint.maxTime ;

16

17

18 if  _N.intervals[ $t_{i}$].endpoint.maxTime - min-cost($t_{i}$) ¡
N.intervals[$t_{i}$].startpoint.maxTime_ then

19 N.intervals[$t_{i}$].startpoint.maxTime =
N.intervals[$t_{i}$].endpoint.maxTime - min-cost($t_{i}$) ;

20

21

22return N ;

Algorithm 3 Update Task Intervals

###  4.3 Low Level Search

The primary goal of the low-level search is to find a path for an agent that
adheres to its collison conflicts and respects the valid intervals for each of
its assigned tasks. If an agent executes the sequence of actions in its path
starting from its initial location, then it will pick up and deliver each of
the object tasks assigned to it in a sequential manner. This can be done by
running a variation of A∗ planning algorithm which is forced to visit a
sequence of waypoint configurations in its path. Let the set of ordered tasks
of size $K$ assigned to agent a be $\\{t_{1}^{a},t_{2}^{a},…,t_{K}^{a}\\}$.
The state representation for path finding for is { position, timestep,
tasks_completed}, where:

  1. 1.

position $\rightarrow$ the configuration of agent A in the graph

  2. 2.

timestep $\rightarrow$ the current timestep of A

  3. 3.

tasks_completed $\rightarrow$ the set of completed tasks
$\\{t_{1}^{a},t_{2}^{a},\dots,t_{k}^{a}\\}$

The low level search problem for agent $a$ which starts at $v_{s}^{a}$ and has
been assigned the task sequence $\\{t_{1}^{a},t_{2}^{a},…,t_{K}^{a}\\}$ then
becomes to find the minimum cost path from start to goal where, start =
($v_{s}^{a}$, 0, $\emptyset$) and, the goal condition for a node { position,
timestep, tasks_completed = $\\{t_{1}^{a},t_{2}^{a},\dots,t_{k}^{a}\\}$} is
that $k=K$ (all assigned tasks have been completed). However, the ultimate
objective of PC-CBS is to find makespan-optimal paths for all agents. We use
this insight to make use of possible delays in paths of an agent to avoid
conflicts which would have been detected in future iterations of the high
level search. A tuple of heuristics are defined for this purpose in Algorithm
4. These are checked from the first to last, with the later values checked
only if there is a tie. This cascaded tie-breaking procedure [7] has been
successfully used to tune the efficiency of A* search. In our case, however,
we are interested in using the heuristics to guide search towards solutions
which avoid conflicts.

The first heuristic, called the delay cost, is the minimum time that the path
is guaranteed to delay the entire plan. This heuristic maintains the makespan-
optimality of the algorithm. The second and third heuristics aim to reduce the
number of precedence and collision conflicts by preemptively comparing paths
with that of other agents. The fourth heuristic is the variation of the
standard $f-value$ used in $A*$. It uses $moveActions$ as the cost-to-come
measure which is equivalent to the distance travelled by the agent instead of
travel time. Finally, paths with lower cost-to-go measures are prioritised
over nodes with lower $f-values$. The cost-to-go function is looked up from a
pre-computed table of shortest path costs between any two vertices. This is
obtained as a pre-processing step by running the Floyd-Warshall algorithm [26]
on the configuration space graph without considering collisions with other
agents.

1

Input : Plans P, Current node v, Current path p

2

3$C1=max(CostToCome(v)+CostToGo(v)-makespan,0)$;

4 $C2=countPrecedenceConflicts(p,P)$;

5 $C3=countCollisionConflicts(p,P)$;

6 $C4=MoveActions(p)+CostToGo(v)$;

7 $C5=CostToGo(v)$;

8 $C6=CostToCome(v)+CostToGo(v)$;

9

10return $(C1,C2,C3,C4,C5,C6)$;

Algorithm 4 Heuristics for Low Level Search

###  4.4 Proof of Optimality

In this section, we prove the optimality of PC-CBS.

[Definition 1] For given node $N$ in the C.T., let $CV(N)$ be the set of all
solutions that are consistent with the collision constraints and task
intervals of $N$ and are don’t have any collision or precedence conflicts.

If $N$ is not a goal node, then the solution at N will not be part of $CV(N)$
because it is not valid, i.e, it has a conflict.

[Definition 2] For any solution $p\in CV(N)$ we say that node $N$ permits the
solution $p$ if it is consistent with its constraints.

The root node having no constraints permits all valid solutions. The cost of a
solution in $CV(N)$ is the lowest makespan cost among the set of its permitted
paths. Let $minCost(CV(N))$ be the minimum cost over all valid solutions in
$CV(N)$.

[Lemma 1] The cost of a node $N$ in the CT is a lower bound on
$minCost(CV(N))$.

Proof: $N.cost$ is the lowest makespan cost among the set of paths that
satisfy the collision constraints and task intervals of $N$. These set of
paths need not be valid. Thus, $N.cost$ is a lower bound on the cost of any
set of paths that make a valid solution for $N$. $\Box$

[Lemma 2] For a valid solution p, there exists a CT node N in OPEN List that
permits p at all time.

Proof: For the base case, OPEN only contains the root node, which has no
constraints. Consequently, the root node permits all valid solutions and also
$p$. The statement holds true iff when branching at a node $N$, the union of
all valid solutions permitted by its children is same as the set of valid
solutions permitted at node $N$. Any invalid solution may be discarded while
branching to ensure the algorithm terminates. This is satisfied while
resolving precedence conflicts as discussed in Section 4.2. While resolving
collision conflicts [4], the only solution invalidated is the one where agents
are in collision due to the chosen conflicts. $\Box$

[Theorem 1] PC-CBS returns the optimal solution.

Proof: Since the high-level search explores solution costs in a best-first
manner, the first goal node that is arrived in the CT will be the optimal
solution. This results as a consequence of Lemma 1, which shows that $N.cost$
is a valid lower-bound for the best-first search and Lemma 2 which ensures
completeness. $\Box$

##  5 Hierarchical-CBS

Fig. 4: An example PC-MAPF problem (left) and its Task Graph (right) where
H-CBS is sub-optimal as $R_{b}$ needs to pre-emptively delay its path to
achieve the optimal makespan cost solution (7) .

(a) Empty Grid

(b) Warehouse Grid

(c) Maze-Gap

(d) Maze-Tunnel

Fig. 5: Visualization of 9x9 Grid Environments used for Warehouse Assembly and
Collaborative MAPD Problems Table 1: Performance Metrics in Warehouse Assembly
Problems over 4 Different Grid Environments

Me- an Ta- sks No. of Age- nts Empty Grid Warehouse Grid Maze-Gap Maze-Tunnel
PC- CBS Sol. H- CBS Sol. % sub- opt. avg. reg- ret PC- CBS ~Sol. H- CBS Sol. %
sub- opt avg. ~reg- ret PC- CBS ~Sol. H- CBS ~Sol. % sub- opt avg. ~reg- ret
PC- CBS ~Sol. H- CBS Sol. % sub- opt avg. reg- ret 2 2 1.00 1.00 0% 0 1.00
1.00 0% 0 1.00 1.00 2% 0.02 0.99 1.00 7% 0.14 4 1.00 1.00 0% 0 1.00 1.00 4%
0.07 1.00 1.00 15% 0.23 0.96 0.93 31% 0.61 6 1.00 1.00 5% 0.08 0.98 0.99 9%
0.13 0.97 0.96 33% 0.59 0.89 0.44 41% 0.68 3 2 1.00 1.00 0% 0 1.00 1.00 1%
0.02 0.99 1.00 3% 0.05 1.00 1.00 16% 0.29 4 1.00 1.00 0% 0 0.99 0.98 9% 0.16
0.99 0.97 27% 0.45 0.89 0.68 41% 0.75 6 0.99 1.00 3% 0.03 0.96 0.94 11% 0.16
0.91 0.88 20% 0.34 0.62 0.29 39% 0.89 4 2 1.00 1.00 2% 0.02 1.00 1.00 3% 0.04
1.00 1.00 9% 0.17 0.99 0.99 21% 0.36 4 1.00 1.00 2% 0.02 1.00 0.96 15% 0.22
0.99 0.98 21% 0.37 0.85 0.65 39% 0.88 6 0.99 1.00 3% 0.05 0.89 0.85 17% 0.19
0.71 0.76 20% 0.38 0.40 0.29 50% 1.10

Table 2: Performance Metrics in Collaborative MAPD Problems over 4 Different
Grid Environments

Col. Deg -ree Me- an Ta- sks No. of age- nts Empty Grid Warehouse Grid Maze-
Gap Maze-Tunnel PC- CBS Sol. H- CBS Sol. % sub- opt. avg. reg- ret PC- CBS
Sol. H- CBS Sol. % sub- opt avg. reg- ret PC- CBS Sol. H- CBS Sol. % sub- opt
avg. reg- ret PC- CBS Sol. H- CBS Sol. % sub- opt. avg. reg- ret 2 2 4 1.00
1.00 2% 0.02 1.00 1.00 4% 0.04 1.00 1.00 4% 0.05 0.99 0.99 16% 0.29 6 1.00
1.00 6% 0.06 0.83 0.98 7% 0.07 0.96 1.00 14% 0.20 0.84 0.92 30% 0.44 3 4 1.00
1.00 6% 0.07 0.73 1.00 11% 0.12 0.93 1.00 14% 0.20 0.78 0.98 12% 0.31 6 0.99
1.00 8% 0.08 0.42 0.99 24% 0.29 0.66 1.00 28% 0.37 0.54 0.90 45% 0.68 3 2 3
1.00 1.00 0% 0.00 1.00 1.00 0% 0.00 1.00 1.00 0% 0.00 1.00 1.00 0% 0.00 6 0.93
0.99 2% 0.02 0.72 1.00 1% 0.01 0.73 0.96 15% 0.17 0.65 0.90 12% 0.13 3 3 0.15
0.96 0% 0.00 0.20 1.00 0% 0.00 0.11 0.88 0% 0.00 0.26 1.00 0% 0.00 6 0.20 0.98
30% 0.40 0.13 0.92 33% 0.50 0.13 0.91 23% 0.31 0.12 0.77 36% 0.45

In this section, we briefly explain Hierarchical-CBS (H-CBS) [5], a recently
proposed algorithm that solves the PC-MAPF problem and demonstrate an example
case where H-CBS fails to find an optimal path. In its pre-processing step,
H-CBS finds the time required for completion of each of the tasks without
taking into account collisions between agents. It then calculates the slack
available at each task by calculating the amount of extra time that can be
spent in doing that task without increasing the global makespan cost of the
solution. To find a valid solution to the PC-MAPF problem, H-CBS performs a
three-level hierarchical search which involve in order of level from top to
down: CBS, Incremental Slack Prioritized Search (ISPS) and A*. At the top
level, CBS is used to detect collision conflicts between plans of individual
tasks and resolve them by propagating collision constraints to the lower level
algorithms. Given a set of constraints, ISPS traverses the precedence
constrained task graph in topological order, and calls A* to find the shortest
collision-free plan of each task segment prioritized by the amount of slack
available to a task.

Consider the PC-MAPF problem presented in Fig 4. This denotes a pickup and
delivery problem where, agent $R_{a}$ must go to the position S1 (denoted by a
GO-1 task), and then pickup, carry object 1 over and deliver it at G1 (denoted
by a CARRY-1 task), and agent $R_{b}$ must go to the position S2 (denoted by a
GO-2 task), and then pickup, carry object 2 over and deliver it at G2 (denoted
by a CARRY-2 task). The Task Graph shown in the figure consists of the four
tasks: GO-1, CARRY-1, GO-2 and CARRY-2 and the in-schedule precedence
constraints between these tasks are denoted by directed edges. The optimal
solution requires $R_{b}$ to pre-emptively delay its path, allowing $R_{a}$ to
enter the narrow passage first and has a makespan cost of 7. In the first
iteration of H-CBS, paths are computed without considering collisions. When
these paths are collision checked, a collision conflict is found at timestep 6
at G2. However, this conflict is between tasks CARRY-1 and CARRY-2. In fact,
conflicts always arise between these two tasks in future iterations. The GO
tasks have no collisions and do not need to replan their paths. Hence, in the
eventual solution found by H-CBS, the agents will greedily enter ($R_{b}$
first) the passage and then have to come out again to reorder themselves in
the correct order ($R_{a}$ first). Since the makespan of this solution is 11,
it is an example of a class of problems in which H-CBS cannot guarantee
optimality.

##  6 Experimental Results

The PC-CBS and H-CBS algorithms are implemented in C++ using the Boost Graph
library [27] for standard graph operations. Experiments are run on an Intel
Core i7-1165G7 CPU @ 2.80GHz×8 processor with 15.3 GB of memory. The timeout
is set to 300s for each run on an individual problem instance. Results are
shown over four 9x9 grid-worlds (Fig. 5). We consider the following
performance metrics in our tables. The last two metrics are computed over
problems solved by both algorithms.

  1. 1.

(PC-CBS, H-CBS)_Sol. is defined as the number of problems solved by an
algorithm divided by the total number of problems. (100 for each problem set)

  2. 2.

% sub-opt.  is defined as the number of problems where H-CBS is sub-optimal
divided by the number of problems solved by both algorithms. (expressed as a
percentage)

  3. 3.

Avg. regret is the mean surplus makespan, the amount of extra timesteps needed
by H-CBS compared to the optimal makespan found by PC-CBS. ( $=1/(Solved\\_$
$by\\_both)\sum H\\-CBS_{mkspn}-PC\\-CBS_{mkspn}$)

Cells which are colored black represent obstacles and cannot be occupied by
any agents. At any timestep, an agent may either wait at its current cell, or
move to its four-connected neighbourhood in the grid. The environments
represent diverse scenarios to evaluate the optimality of our algorithm. The
empty-grid does not contain any obstacles, providing maximum free space to
agents to move in while the maze-tunnel is highly constricted requiring
passage through narrow tunnels to move between quadrants. We choose two
domains of PC-MAPF problems for testing our algorithm. Warehouse Assembly
problems are a special class of PC-MAPF where only one agent is assigned per
task. Collaborative MAPD problems are a special class of PC-MAPF where
precedence constraints arise only bcecause of multiple agents being assigned
to pickup and delivery tasks. Each problem set consists of 100 randomly
generated instances. The results in Table 1 and Table 2 show these performance
metrics over different number of agents in the grid and mean number of tasks
alloted to each agent. Additionally for collaborative MAPD, the number of
agents required for each task (collaboration degree) is varied between 2 and
3.

We assign random initial locations for each agent, and random pickup &
delivery locations for transport tasks to create problems. The Task Graph
edges, representing precedence constraints between tasks, are randomly
generated for warehouse assembly problems. Agents are allotted to their task
sequences using a greedy assignment scheme. Among each task that can begin, we
consider the set of agents that can reach it’s start location. The task which
can be started earliest is picked for allocation. This assignment strategy
does not consider collisions between agents but it respects the precedence
constraints between tasks.

From the results in Table 1, it is observed that PC-CBS not only finds optimal
makespan paths but also matches or outperforms (marked in bold) H-CBS in 30/36
of the problem sets chosen for evaluation. In spite of PC-CBS computing longer
A* searches, it is seen that the sub-optimality of H-CBS makes it prone to
getting stuck in large search trees, especially in the maze environments which
are similar to the example shown in Fig. 4. The surplus makespan (regret) and
the percentage of problems where H-CBS is sub-optimal increases with the
complexity of the environment. In the empty-grid, H-CBS is almost always close
to the optimal cost which is expected since planning individual tasks in a
free region will avoid situations requiring pre-emptive delays. Despite the
warehouse-grid having more obstacle cells than the maze-gap environment, it is
generally seen that solutions found by H-CBS are closer to optimal in this
environment. The existence of multiple equal quality pathways from one cell to
another helps the segmented planner, whereas in the maze-gap environment, the
agents are constricted to move through gaps to move across quadrants. The
bottleneck problem is only exaggerated in the maze-tunnel environment where
the percentage of sub-optimal solutions goes as high as $50\%$.

Table 2 highlights the benefit of segmented planning in finding feasible
solution paths for collaborative MAPD tasks. H-CBS matches or outperforms PC-
CBS in finding more feasible solutions in all problem-sets. The amount of sub-
optimality, however, is still significantly large in some case and shows the
same variation with environments as shown in Fig 6. The problem sets where
three agents collaborate for pickup tasks requiring three agents show no
difference in makespan in any of the problems. This is expected since pre-
emptive delays are never required in the case. Collaborative transport can
start only when all agents arrive at the pickup location together. It is also
observed that the performance of PC-CBS degrades quickly with increasing
number of agents assigned to a task. For collaborative tasks, a cluster of
conflicts can form around the pickup and delivery. Since the low-level search
of PC-CBS employs a longer multi-waypoint search, the number of conflicts
grows exponentially faster than in H-CBS.

Fig. 6: Surplus makespan, i.e, regret of H-CBS is visualized over the
different gridworld environments using a Violin plot. The thick line in the
middle indicates the mean regret. The problem set chosen here consisted of 6
agents with 3 mean tasks for both problem domains. The degree of collaboration
is 2 for Collaborative MAPD.

### Extensions

While PC-CBS has been proposed for precedence constrained tasks, the
algorithmic framework can be adapted for other types of cross-schedule
dependencies like synchronization and time-windowing constraints. Since the
valid duration for tasks are represented by intervals, PC-CBS can integrate
Safe-Interval Path Planning (SIPP) [28] in its low-level search and be
extended to continuous time domains similar to the work by [12]. Recent work
in improving CBS have significantly improved its run-time by choosing
promising conflicts [11]. Other works [13] have proposed a highly efficient
and bounded sub-optimal version of the algorithm. [29] found an order of
magnitude improvement by incorporating positive constraints, which act as
waypoints, to resolve collision conflicts in CBS. All of these improvements
can be applied to PC-CBS, especially in the context of precedence conflicts.

##  7 Conclusion

This work proposed an optimal algorithm for PC-MAPF based on a state-of-the-
art MAPF solver, CBS. We represent warehouse assembly and collaborative MAPD
problems as a Task Graph, which is input to our solver. We prove the
optimality of our algorithm and evaluate the sub-optimality of another
recently proposed PC-MAPF solver. Next steps include integration of a task
assignment module on top of the path planner. The use of a multi-goal variant
of A* can be used to find paths for a set of unordered tasks assigned to each
agent reducing the burden on the Task Allocation search problem. Another
promising direction of work includes the combination of collaborative
transport tasks with precedence constraints. In the future, we also intend to
explore design of intelligent warehouses through PC-CBS, which is pertinent to
recent MAPF research [30].

## References

  * [1] M. Liu, H. Ma, J. Li, and S. Koenig, “Task and path planning for multi-agent pickup and delivery,” in _AAMAS_ , 2019.
  * [2] Z. Wang, S. Singh, M. Pavone, and M. Schwager, “Cooperative object transport in 3d with multiple quadrotors using no peer communication,” in _2018 IEEE International Conference on Robotics and Automation (ICRA)_ , 2018, pp. 1064–1071.
  * [3] G. Loianno and V. Kumar, “Cooperative transportation using small quadrotors using monocular vision and inertial sensing,” _IEEE Robotics and Automation Letters_ , vol. 3, no. 2, pp. 680–687, 2018.
  * [4] G. Sharon, R. Stern, A. Felner, and N. R. Sturtevant, “Conflict-based search for optimal multi-agent pathfinding,” _Artificial Intelligence_ , vol. 219, pp. 40–66, 2015. [Online]. Available: https://www.sciencedirect.com/science/article/pii/S0004370214001386
  * [5] K. Brown, O. Peltzer, M. A. Sehr, M. Schwager, and M. J. Kochenderfer, “Optimal sequential task assignment and path finding for multi-agent robotic assembly planning,” in _2020 IEEE International Conference on Robotics and Automation (ICRA)_ , 2020, pp. 441–447.
  * [6] K. Brown, E. Darve, M. Kochenderfer, M. Pavone, M. Schwager, and S. U. D. of Mechanical Engineering, “Algorithms for multi-agent robotic assembly planning,” Ph.D. dissertation, 2021. [Online]. Available: http://purl.stanford.edu/qf931ph2309
  * [7] M. Asai and A. S. Fukunaga, “Tiebreaking strategies for a* search: How to explore the final frontier,” in _AAAI_ , 2016.
  * [8] J. Yu and S. LaValle, “Structure and intractability of optimal multi-robot path planning on graphs,” _Proceedings of the AAAI Conference on Artificial Intelligence_ , vol. 27, no. 1, Jun. 2013. [Online]. Available: https://ojs.aaai.org/index.php/AAAI/article/view/8541
  * [9] G. Sharon, R. Stern, M. Goldenberg, and A. Felner, “The increasing cost tree search for optimal multi-agent pathfinding,” _Artificial Intelligence_ , vol. 195, pp. 470–495, 2013. [Online]. Available: https://www.sciencedirect.com/science/article/pii/S0004370212001543
  * [10] G. Wagner and H. Choset, “M*: A complete multirobot path planning algorithm with performance bounds,” in _2011 IEEE/RSJ International Conference on Intelligent Robots and Systems_ , 2011, pp. 3260–3267.
  * [11] E. Boyarski, A. Felner, R. Stern, G. Sharon, O. Betzalel, D. Tolpin, and S. E. Shimony, “Icbs: The improved conflict-based search algorithm for multi-agent pathfinding,” in _SOCS_ , 2015.
  * [12] A. Andreychuk, K. S. Yakovlev, D. Atzmon, and R. Stern, “Multi-agent pathfinding with continuous time,” _arXiv: Artificial Intelligence_ , 2019\.
  * [13] M. Barer, G. Sharon, R. Stern, and A. Felner, “Suboptimal variants of the conflict-based search algorithm for the multi-agent pathfinding problem,” in _SOCS_ , 2014.
  * [14] J. Yu and S. M. LaValle, “Multi-agent path planning and network flow,” in _WAFR_ , 2012.
  * [15] W. Hönig, S. Kiesel, A. Tinka, J. W. Durham, and N. Ayanian, “Conflict-based search with optimal task assignment,” in _Proceedings of the 17th International Conference on Autonomous Agents and MultiAgent Systems_ , ser. AAMAS ’18. Richland, SC: International Foundation for Autonomous Agents and Multiagent Systems, 2018, p. 757–765.
  * [16] G. Wagner, H. Choset, and N. Ayanian, “Subdimensional expansion and optimal task reassignment,” in _SOCS_ , 2012.
  * [17] N. Greshler, O. Gordon, O. Salzman, and N. Shimkin, “Cooperative multi-agent path finding: Beyond path planning and collision avoidance,” in _SOCS_ , 2021\.
  * [18] C. Henkel, J. Abbenseth, and M. Toussaint, “An optimal algorithm to solve the combined task allocation and path finding problem,” _2019 IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS)_ , pp. 4140–4146, 2019.
  * [19] M. Liu, H. Ma, J. Li, and S. Koenig, “Task and path planning for multi-agent pickup and delivery,” in _Proceedings of the 18th International Conference on Autonomous Agents and MultiAgent Systems_ , ser. AAMAS ’19. Richland, SC: International Foundation for Autonomous Agents and Multiagent Systems, 2019, p. 1152–1160.
  * [20] H. Ma, J. Li, T. K. S. Kumar, and S. Koenig, “Lifelong multi-agent path finding for online pickup and delivery tasks,” in _AAMAS_ , 2017.
  * [21] F. Grenouilleau, W. V. Hoeve, and J. Hooker, “A multi-label a* algorithm for multi-agent pathfinding,” in _ICAPS_ , 2019.
  * [22] G. A. Korsah, A. Stentz, and M. B. Dias, “A comprehensive taxonomy for multi-robot task allocation,” _The International Journal of Robotics Research_ , vol. 32, pp. 1495 – 1512, 2013.
  * [23] D. Bredström and M. Rönnqvist, “Combined vehicle routing and scheduling with temporal precedence and synchronization constraints,” _Eur. J. Oper. Res._ , vol. 191, pp. 19–31, 2008.
  * [24] ——, “A branch and price algorithm for the combined vehicle routing and scheduling problem with synchronization constraints,” 2007.
  * [25] J. P. van den Berg and M. H. Overmars, “Prioritized motion planning for multiple robots,” _2005 IEEE/RSJ International Conference on Intelligent Robots and Systems_ , pp. 430–435, 2005.
  * [26] R. W. Floyd, “Algorithm 97: Shortest path,” _Commun. ACM_ , vol. 5, no. 6, p. 345, Jun. 1962. [Online]. Available: https://doi.org/10.1145/367766.368168
  * [27] J. G. Siek, L.-Q. Lee, and A. Lumsdaine, “The boost graph library - user guide and reference manual,” in _C++ in-depth series_ , 2002.
  * [28] M. Phillips and M. Likhachev, “Sipp: Safe interval path planning for dynamic environments,” _2011 IEEE International Conference on Robotics and Automation_ , pp. 5628–5635, 2011.
  * [29] J. Li, D. D. Harabor, P. J. Stuckey, H. Ma, and S. Koenig, “Disjoint splitting for multi-agent path finding with conflict-based search,” in _ICAPS_ , 2019\.
  * [30] O. Salzman and R. Stern, “Research challenges and opportunities in multi-agent path finding and multi-agent pickup and delivery problems,” in _AAMAS_ , 2020\.


# UV-IR interplay in axion flavour violation

Luca Di Luzio  Alfredo Walter Mario Guerrera
Xavier Ponce Díaz 111Speaker Stefano Rigolin  Istituto Nazionale di Fisica
Nucleare (INFN), Sezione di Padova,
Dipartimento di Fisica e Astronomia ‘G. Galilei’, Università di Padova,
Via F. Marzolo 8, 35131 Padova, Italy

###### Abstract

Flavour-violating axions appear in models where the Peccei-Quinn(PQ) charges
are generation non-universal. Consequently, this charge arrangement will also
generate flavour violation in the UV sector. The typical way of implementing
such an axion in a UV completion is with a DFSZ model, containing 2 Higgs
doublets. In this talk we will present how to parameterize the flavour
violation in the UV such that we can find a direct correlation with the
flavour violation of the axion. Finally, we show in an example how this
connection can help in giving information about the UV completion if an axion
is found in a flavour-violating channel.

##  1 Introduction

A flavour-violating axion (IR-source) appears when the $U(1)_{\textrm{PQ}}$
couples non-universally (i.e. in a generation-dependent way) to the Standard
Model (SM) fermions. Such type of axion models can be motivated in several
respects: i) the connection to the Flavour puzzle [1, 2, 3]; ii) the
possibility of achieving an “astrophobic” scenario [4, 5, 6] (where nucleon
and electron couplings are suppressed); and iii) the opportunity of finding
the axion in flavour-violating searches [7, 8, 9]. These previous points have
in common that a flavour-violating axion must be accompanied by a UV
completion, which in general is also flavour-violating. Here, we show how in a
class of models, such as a non-universal DFSZ models, we can correlate in a
one-to-one way the flavour violating observables of the axion with those of
the UV completion, in this case a PQ-2 Higgs Doublet Model (PQ-2HDM). We use
this correspondence between IR and UV observables in a practical example of
what information could be inferred from the UV if an axion is observed in a
flavour-violating golden channel, e.g. $K\to\pi a$.

##  2 Flavour violation in axion models

###  2.1 Flavour violation in the IR: the axion

Axions coupling to the SM fermions arise as complex phases in the mass matrix.
Typically this term is removed by a field redefinition along the charges of
the SM fermions, appearing as a derivative coupling of the form

$\mathcal{L}_{a}=\sum_{f}\frac{\partial_{\mu}a}{f_{a}}\,\bar{f}\,{\mathcal{X}}_{f}\gamma^{\mu}f\,,\quad\textrm{with
}f=\\{q_{L},\,d_{R},\,u_{R},\,\ell_{L},\,e_{R}\\}\,.$ (1)

Here, the couplings ${\mathcal{X}}_{f}$ are the charges of the SM fermions
with respect to the $U(1)_{\rm PQ}$ in flavour space. After rotation of the
fermions into the mass basis, one finds that to have flavour violation in the
axion sector it is necessary to have non-universal charges, or conversely, the
charges must not be proportional to the identity,

$\frac{\partial_{\mu}a}{f_{a}}\,\bar{f}\,{\mathcal{X}}_{f}\gamma^{\mu}f\quad\longrightarrow\quad\frac{\partial_{\mu}a}{f_{a}}\,\bar{f}\,V_{f}^{\dagger}{\mathcal{X}}_{f}V_{f}\gamma^{\mu}f\,.$
(2)

The matrices $V_{f}$ correspond to the bi-unitary transformations which
diagonalize the fermion mass matrix
$\hat{M}_{f}=V_{f_{L}}^{\dagger}M_{f}V_{f_{R}}$. It is useful to define these
couplings as

$C^{R,L}_{f}=\frac{1}{2N}V_{f_{R,L}}^{\dagger}{\mathcal{X}}_{f_{R,L}}V_{f_{R,L}}\,,$
(3)

where $N$ is the QCD anomaly coefficient.

###  2.2 Flavour violation in the UV: the PQ-2HDM

Generally, this axion can be generated as a variation of the classic DFSZ
model [10, 11], implemented with non-universal charges. This model contains 2
Higgs doublets, which introduce an additional Yukawa matrix coupling to the
fermions

$\mathcal{L}_{\rm
PQ-2HDM}=\bar{f}_{L}\left(Y_{1}^{f}\tilde{H}_{1}+Y_{2}^{f}\tilde{H}_{2}\right)f_{R}+\rm
h.c.\,.$ (4)

In this type of models one cannot generally diagonalize simultaneously the
mass matrix and individual Yukawas, leading to the appearance of flavour
violation in the UV-completion. This can be seen by noting that the mass
matrix is a combination of the Yukawas and vacuum expectation values of the
two Higgs, $v_{1}=vc_{\beta}$ and $v_{2}=vs_{\beta}$ with
$s_{\beta}\equiv\sin\beta$, $c_{\beta}\equiv\cos\beta$ and
$t_{\beta}\equiv\tan\beta=\frac{v_{2}}{v_{1}}$,

$M_{f}=\frac{v}{\sqrt{2}}\left(Y_{1}^{f}\,c_{\beta}+Y_{2}^{f}\,s_{\beta}\right)\,,$
(5)

while the interactions of the radial modes follow different combinations (see
reference [12]), generating flavour-violating couplings. However, there is no
apparent direct connection between the flavour violation in the IR and UV
sectors. Such a connection can be made explicitly manifest by noting that the
structure of the Yukawas is given by the charge arrangement. Thus, by imposing
the $U(1)_{\rm PQ}$ on the Yukawa matrices, one can obtain the following sum
rules,

$-{\mathcal{X}}_{f_{L}}Y_{1,2}^{f}+Y_{1,2}^{f}\,{\mathcal{X}}_{f_{R}}+{\mathcal{X}}_{1,2}Y_{1,2}^{f}=0\,.$
(6)

These expressions combined with the definition of the mass matrix in Eq. 5,
fix the specific shape of the Yukawas

$Y_{1}^{d}=\frac{\sqrt{2}}{vc_{\beta}}V_{d_{L}}\left(C^{L}_{d}\hat{M}_{d}-\hat{M}_{d}C^{R}_{d}+{\mathcal{X}}_{2}\hat{M}_{d}\right)V^{\dagger}_{d_{R}}\,,\,Y_{2}^{d}=\frac{\sqrt{2}}{vs_{\beta}}V_{d_{L}}\left(-C^{L}_{d}\hat{M}_{d}+\hat{M}_{d}C^{R}_{d}-{\mathcal{X}}_{1}\hat{M}_{d}\right)V^{\dagger}_{d_{R}}\,,$
(7)

where we took the specific case of the $d-$type quarks. Similar expressions
hold for the $u-$type quarks and leptons 222These expressions are given for
$2N=1$ axion models.. These relations, are the main result of reference [12],
and it is important to emphasize several points: i) the structure of flavour
violation is contained in the couplings $C_{f}^{R,L}\sim
V_{R,L}^{\dagger}{\mathcal{X}}_{f_{R,L}}V_{R,L}$, and it is shared across
scales; ii) these relations don’t assume any particular PQ-charge or Yukawa
structure (unlike in other works where Yukawa ansatzs are used); and iii) the
charges of the Higgs will not play any role in flavour-violating couplings.

##  3 An example of the flavour connection across scales

To emphasize the importance of these relations, we give a particular example
of the information one could obtain of the UV-completion after a positive
detection of an axion in the golden channels: $K\to\pi\,a$ and $B\to K\,a$.

Using Eq. 7 it is possible to relate observables of flavour-violating axions
and the PQ-2HDM. To simplify, we use models with $2+1$ charge arrangements
[4], which exhibit flavour violation in just one of the two couplings,
$C^{R,L}_{f}$. This allows to write the following direct relations which link
the axion golden channels with the associated 2HDM meson mixing contribution
in the alignment limit [12]

$\displaystyle\left(\frac{f_{a}}{10^{11}\,\textrm{GeV}}\right)^{2}\left(\frac{1\,\textrm{TeV}}{s_{2\beta}\,m_{H}}\right)^{2}\left(\frac{\textrm{BR}(K\to\pi
a)}{7.3\cdot 10^{-11}}\right)=\frac{2\,|M^{\textrm{NP}}_{12}|}{3.5\cdot
10^{-15}\,\textrm{GeV}}\,,$ (8) $\displaystyle\left(\frac{f_{a}}{8.8\cdot
10^{7}\,\textrm{GeV}}\right)^{2}\left(\frac{1\,\textrm{TeV}}{s_{2\beta}\,m_{H}}\right)^{2}\left(\frac{\textrm{BR}(B\to
Ka)}{7.1\cdot 10^{-6}}\right)=\frac{2\,|M^{\textrm{NP}}_{12}|}{1.2\cdot
10^{-11}\,\textrm{GeV}}\,.$ (9)

If an axion is found in one of these decay channels, the branching ratio is
set. If we fix the branching ratio, then meson-mixing imposes a lower bound in
the $f_{a}-m_{H}$ plane. This is shown in Fig. 1, where the light coloured
region is the parameter space between the current and projected sensitivity of
the bounds. The dark coloured region is the bound imposed by meson mixing, the
black horizontal band is the collider bound on the 2HDM and in brown we show
the astrophysical bounds for a model with order one coupling to electrons, and
the most astrophobic model [4]. This plot shows the important interplay
between axion and 2HDM bounds, and we see how we could extract information
about the 2HDM after detecting an axion: if the axion is found in a $s-d$
transition, then there is plenty parameter space to cover with future LHC
searches. However, if an axion is found in a $b-s$ transition, then either the
model is up to some extent astrophobic or the LHC would not be able to observe
heavy modes of the 2HDM.

This is one particular example in which the general connection of Eq. 7 can be
used. Other examples, including how to relate lepton flavour-violating decays
of the SM-like Higgs $h\to l_{i}^{+}\,l_{j}^{-}$ and lepton decays $l_{i}\to
l_{j}\,a$ are found in Ref. [12]. We remark that these relations are most
useful when there are signs of new physics, since they allow to fix at least
one of the observables.

Figure 1: Allowed parameters space after fixing the branching ratio of the
axion to the current (solid), projected sensitivity (dotted) and imposing the
meson mixing bound on each channel. Bounds on collider searches of 2HDM are
shown in black, and astrophysical bounds for different axion scenarios are
coloured in brown.

##  4 Conclusions

In this talk we presented the results of reference [12]. Here, a new way of
rewriting the Yukawa matrices of a non-universal DFSZ is found, allowing to
link the flavour violating couplings of the heavy radial modes in terms of the
axion couplings. This minimal flavour structure allows to connect flavour
violating observables between the two sectors, the axion and the PQ-2HDM, that
is a UV-IR connection. We have shown in an example, that information about the
heavy modes can be obtained if a flavour violating axion is found.
Specifically, if an axion is found in the $K\to\pi\,a$ channel then the
parameter space still allows for a detection in the future runs of LHC, while
if this discovery happens in other channels, e.g. $B\to Ka$, the parameter of
the LHC would be already ruled out by astrophysics unless the model is
astrophobic.

## Acknowledgments

This work received funding from the European Union’s Horizon 2020 research and
innovation programme under the Marie Skłodowska-Curie grant agreement N∘
860881-HIDDeN, grant agreement N∘ 101086085–ASYMMETRY and by the INFN
Iniziative Specifica APINE. The work of LDL is also supported by the project
“CPV-Axion” under the Supporting TAlent in ReSearch@University of Padova
(STARS@UNIPD).

## References

## References

  * [1] Y. Ema, K. Hamaguchi, T. Moroi, and K. Nakayama, “Flaxion: a minimal extension to solve puzzles in the standard model,” JHEP 01 (2017) 096,  arXiv:1612.05492 [hep-ph].
  * [2] L. Calibbi, F. Goertz, D. Redigolo, R. Ziegler, and J. Zupan, “Minimal axion model from flavor,” Phys. Rev. D 95 no. 9, (2017) 095009,  arXiv:1612.08040 [hep-ph].
  * [3] F. Arias-Aragon and L. Merlo, “The Minimal Flavour Violating Axion,” JHEP 10 (2017) 168,  arXiv:1709.07039 [hep-ph]. [Erratum: JHEP 11, 152 (2019)].
  * [4] L. Di Luzio, F. Mescia, E. Nardi, P. Panci, and R. Ziegler, “Astrophobic Axions,” Phys. Rev. Lett.  120 no. 26, (2018) 261803,  arXiv:1712.04940 [hep-ph].
  * [5] F. Bjorkeroth et al., “Axion-electron decoupling in nucleophobic axion models,” Phys. Rev. D 101 no. 3, (2020) 035027,  arXiv:1907.06575 [hep-ph].
  * [6] L. Di Luzio, F. Mescia, E. Nardi, and S. Okawa, “Renormalization group effects in astrophobic axion models,” Phys. Rev. D 106 no. 5, (2022) 055016,  arXiv:2205.15326.
  * [7] J. M. Camalich, M. Pospelov, P. N. H. Vuong, R. Ziegler, and J. Zupan, “Quark Flavor Phenomenology of the QCD Axion,” Phys. Rev. D 102 no. 1, (2020) 015023,  arXiv:2002.04623 [hep-ph].
  * [8] L. Calibbi, D. Redigolo, R. Ziegler, and J. Zupan, “Looking forward to lepton-flavor-violating ALPs,” JHEP 09 (2021) 173,  arXiv:2006.04795 [hep-ph].
  * [9] Y. Jho, S. Knapen, and D. Redigolo, “Lepton-flavor violating axions at MEG II,” JHEP 10 (2022) 029,  arXiv:2203.11222 [hep-ph].
  * [10] A. R. Zhitnitsky, “On Possible Suppression of the Axion Hadron Interactions. (In Russian),” Sov. J. Nucl. Phys.  31 (1980) 260. [Yad. Fiz.31,497(1980)].
  * [11] M. Dine, W. Fischler, and M. Srednicki, “A Simple Solution to the Strong CP Problem with a Harmless Axion,” Phys. Lett. B104 (1981) 199–202.
  * [12] L. Di Luzio, A. W. M. Guerrera, X. P. Díaz and S. Rigolin, “On the IR/UV flavour connection in non-universal axion models,” arXiv:2304.04643 [hep-ph].