Multi-Agent Path Finding with Delay Probabilities

Introduction

• Current MAPF solvers do not use estimable delay probabilities, which often leads to frequent, runtime-intensive replanning or plan-execution failures.MAPF seeks collision-free paths from agents’ starts to goals in an environment.Source: Introduction · p. 1
• MAPF-DP models agents moving on an undirected graph with wait and potentially delayed move actions, and requires paths plus an execution policy that avoids collisions.Collisions include agents sharing a vertex at the same time or traversing an edge in opposite directions.Source: Introduction · p. 1
• The paper proposes Fully Synchronized and Minimal Communication Policies to prevent collisions during execution, and Approximate Minimization in Expectation to generate valid plans.The contributions target small average makespans.Source: Introduction · p. 1

Background and Related Work

• MAPF is NP-hard to solve optimally for flowtime minimization and hard to approximate within any constant factor below 4/3 for makespan minimization.Search-based solvers may be optimal, bounded suboptimal, or suboptimal.Source: Background and Related Work · p. 1
• Current MAPF solvers typically assume perfect execution, whereas using probabilistic information about imperfect execution can reduce replanning and plan-execution failures.The passage presents this as a potential benefit of exploiting execution uncertainty.Source: Background and Related Work · p. 2
• POMDPs can model MAPF-DP but are tractable only for very small settings, while decentralized approaches cannot prevent collisions and centralized approaches can scale poorly.The passage also notes limitations of sparse-interaction and fully decentralized alternatives.Source: Background and Related Work · p. 2

Problem Definition: Planning

• The environment is an undirected graph G = (V, E), with vertices representing locations and edges representing transitions.Source: Problem Definition: Planning · p. 2
• Each of the m agents has a unique start vertex, unique goal vertex, and delay probability between 0 and 1.Source: Problem Definition: Planning · p. 2
• An agent path maps each time index from 0 through its final index to a vertex, beginning at its start and ending at its goal, with consecutive locations identical or edge-connected.A MAPF plan consists of one such path per agent.Source: Problem Definition: Planning · p. 2

Problem Definition: Plan Execution

• An agent’s local state tracks its time index along its path, and its policy maps its knowledge, including received messages, to GO or STOP.Source: Problem Definition: Plan Execution · p. 2
• A GO command advances past a wait action without failure, while a move can fail with probability p_i and leave the agent in its current vertex; STOP also leaves it there.Successful moves advance the local state; wait actions never fail.Source: Problem Definition: Plan Execution · p. 2
• The execution objective is to minimize average makespan, defined as the expected earliest time when all agents have entered their last local states.When all delay probabilities are zero and policies always issue GO, MAPF is a special case.Source: Problem Definition: Plan Execution · p. 2

• A valid MAPF-DP plan never schedules two agents in the same vertex at the same time index.Source: Valid MAPF-DP Plans · pp. 2–3
• It also prevents an agent’s next vertex from matching another agent’s current vertex, guarding against collisions when a delayed agent fails to leave.This condition is also necessary to avoid edge collisions under perfect or imperfect execution.Source: Valid MAPF-DP Plans · pp. 2–3
• A plan valid for MAPF can fail the MAPF-DP conditions when one agent’s next vertex is another agent’s current vertex.The example has l2(1) = l1(0) = v3, violating the second property.Source: Valid MAPF-DP Plans · p. 3

Robust Plan-Execution Policies

• Both Fully Synchronized Policies and Minimal Communication Policies are decentralized robust policies that prevent collisions when executing valid MAPF-DP plans imperfectly.Source: Robust Plan-Execution Policies · p. 3

Fully Synchronized Policies (FSPs)

• Fully Synchronized Policies let an agent proceed only after every other agent has advanced beyond preceding local states, but can cause unnecessary waiting and many messages.Agents send one another messages on entering new local states.Source: Fully Synchronized Policies (FSPs) · p. 3, Minimal Communication Policies (MCPs) · p. 3

Minimal Communication Policies (MCPs)

• Minimal Communication Policies encode critical cross-agent dependencies as a partial order, then use its transitive reduction to minimize cross-agent messages.In the example, agent a2 waits at local state 3 for one message from a1, then proceeds without further waiting.Source: Minimal Communication Policies (MCPs) · pp. 3–4, Figure 2 · p. 4, Figure 3 · p. 4

Properties of FSPs and MCPs

• Both policy classes avoid deadlock and are robust because valid-plan properties constrain the order in which agents can enter shared vertices and traverse edges.The paper sketches proofs that MCPs prevent vertex and edge collisions during execution.Source: Properties of FSPs and MCPs · p. 4

Approximate Minimization in Expectation

• AME combines valid MAPF-DP plans with MCPs to target small average makespans, approximating expectation-of-maximum completion times with maxima of expectations.The authors report that this approximation typically underestimates the expectation but is close in their experiments.Source: Approximate Minimization in Expectation · p. 4

High-Level Search

• The high-level search branches on the earliest conflict, adding constraints to separate the agents’ locations and replanning for the constrained agent.Each node stores constraints, a labeled plan, and an approximate-makespan priority key.Source: High-Level Search · p. 5

Low-Level Search

• The low-level search plans over vertex–local-state pairs, using expected action times and other agents’ labels to estimate arrival times.Its two phases first seek a path within the parent node’s makespan key with few conflicts, then seek a small approximate arrival time; it succeeds upon reaching the goal without a later goal constraint.Source: Low-Level Search · pp. 5–6

Future Work

• The authors identify the low-level search as AME’s weakest component because runtime considerations require many approximations.They suggest updating other agents’ approximate time labels as one way to improve accuracy.Source: Future Work · p. 6

Experiment 1: MAPF Solvers

• AME seems to find smaller average makespans than Adapted CBS, which seems to outperform Push and Swap; AME and Push and Swap also seem faster than Adapted CBS.Adapted CBS did not solve instances with more than 35 agents within the five-minute limit, while AME and Push and Swap appeared to scale to larger instances.Source: Experiment 1: MAPF Solvers · p. 6, Table 1 · p. 7

Experiment 2: Delay Probability Ranges

• As delay-probability ranges increase, AME runtimes and both approximate and observed average makespans tend to rise, with noisy observed results.The difference between AME's approximate and observed average makespans also grows but remains reasonable.Source: Figure 5 · p. 7, Table 2 · p. 7, Experiment 2: Delay Probability Ranges · p. 7

Experiment 3: Numbers of Agents

• AME solves most tested instances with 50 agents and then degrades gracefully as the number of agents increases.The measures are averaged over instances solved within a five-minute runtime limit.Source: Table 3 · p. 7, Experiment 3: Numbers of Agents · p. 7

Experiment 4: Plan-Execution Policies

• MCP average makespans seem only slightly larger than those with collision-prone dummy policies, and MCP makespans and message counts seem lower than with FSPs.Dummy policies do not prevent collisions; the reported comparisons use averages over 1,000 plan-execution runs with 95%-confidence intervals.Source: Experiment 4: Plan-Execution Policies · p. 7

Conclusions

• The conclusion presents AME as a two-level solver for generating valid MAPF-DP plans and MCPs as decentralized robust policies for executing them without collisions.The cited table covers 18 solved instances from Experiment 1 and different plan-execution policies.Source: Conclusions · p. 7, Table 4 · p. 8