Source-linked AI summary
Lifelong Multi-Agent Path Finding for Online Pickup and Delivery Tasks
Hang Ma, Jiaoyang Li, T. K. Satish Kumar, Sven Koenig
TL;DR
MAPF does not capture online, lifelong streams of pickup-and-delivery tasks in which agents must avoid collisions. This paper formulates MAPD and presents TP and TPTS, proving both solve all well-formed instances and comparing them experimentally with CENTRAL. TP favors real-time computation and distribution, while TPTS offers a communication-limited balance between TP and CENTRAL.
Problem
MAPF omits domains where agents continuously receive online pickup-and-delivery tasks requiring collision-free travel.
Method
The paper formalizes MAPD and develops two decoupled algorithms, Token Passing (TP) and Token Passing with Task Swaps (TPTS), using token-based path and task information.
Results
Both TP and TPTS solve all well-formed MAPD instances; experiments compare them with the centralized strawman CENTRAL in a simulated warehouse system.
Takeaways & Limitations
TP is suited to real-time computation and can be extended to a fully distributed algorithm, while TPTS uses limited communication and balances between TP and CENTRAL.
Takeaways & Limitations
The guarantees apply to well-formed MAPD instances, which require finite tasks, enough non-task endpoints, and endpoint paths avoiding other endpoints.
Abstract
from arXiv · showhide
The multi-agent path-finding (MAPF) problem has recently received a lot of attention. However, it does not capture important characteristics of many real-world domains, such as automated warehouses, where agents are constantly engaged with new tasks. In this paper, we therefore study a lifelong version of the MAPF problem, called the multi-agent pickup and delivery (MAPD) problem. In the MAPD problem, agents have to attend to a stream of delivery tasks in an online setting. One agent has to be assigned to each delivery task. This agent has to first move to a given pickup location and then to a given delivery location while avoiding collisions with other agents. We present two decoupled MAPD algorithms, Token Passing (TP) and Token Passing with Task Swaps (TPTS). Theoretically, we show that they solve all well-formed MAPD instances, a realistic subclass of MAPD instances. Experimentally, we compare them against a centralized strawman MAPD algorithm without this guarantee in a simulated warehouse system. TP can easily be extended to a fully distributed MAPD algorithm and is the best choice when real-time computation is of primary concern since it remains efficient for MAPD instances with hundreds of agents and tasks. TPTS requires limited communication among agents and balances well between TP and the centralized MAPD algorithm.
1. INTRODUCTION
MAPF models one-shot navigation, but many real-world systems continuously assign agents new tasks. The paper introduces lifelong MAPD to represent online pickup, delivery, and collision avoidance in domains such as warehouses.
- Motivation: Real-world systems such as warehouse robots continuously navigate between locations where new tasks must be executed.Examples include aircraft-towing vehicles, office robots, and video-game characters.
- Gap in MAPF: MAPF ends when agents reach their destinations, so it omits domains where agents remain engaged with new tasks.MAPF uses the same number of agents and destinations in a one-shot setting.
- MAPD formulation: MAPD models an online stream of delivery tasks requiring an assigned agent to travel first to pickup and then to delivery while avoiding collisions.Tasks may enter the system at any time in a known common environment modeled as an undirected graph.
- Contributions: The paper presents Token Passing and Token Passing with Task Swaps, proves both solve all well-formed MAPD instances, and compares them with a centralized strawman in simulation.The comparison uses a simulated warehouse system.
2. BACKGROUND AND RELATED WORK
MAPD combines online task assignment with collision-free path planning during execution. Prior work studied these components separately, while MAPF addressed collision-free navigation mainly as a one-shot problem.
- MAPD requirements: In lifelong MAPD, agents continue receiving tasks instead of resting after completing a destination.The lifelong setting requires agents to attend to a stream of tasks.
- MAPD requirements: Because tasks can arrive at any time, task assignment and path planning must occur during execution rather than in advance.This requirement follows from MAPD's online setting.
- Related work: Prior research studied decentralized task assignment and collision-free path planning in isolation.Reactive and prioritized path-planning approaches can result in deadlocks.
- Related work: MAPF is the one-shot counterpart of MAPD, with optimal solution and approximation problems that are computationally hard.The passage reports NP-hardness for optimal flowtime and for approximating makespan within any constant factor below 4/3.
3. PROBLEM DEFINITION
MAPD formalizes online task execution and collision-free movement on a connected graph. Solvability is guaranteed for well-formed instances, which provide enough non-task endpoints and suitable paths between endpoints.
- MAPD problem: A MAPD instance contains agents and an undirected connected graph whose vertices are locations and edges are traversable connections.Agents may stay put or move to adjacent vertices each timestep while avoiding vertex and edge-swap collisions.
- MAPD problem: Each newly added task specifies pickup and delivery locations, and a free agent must travel through pickup before delivery.The task leaves the unexecuted set when the assigned agent reaches its pickup location.
- Objective: MAPD algorithms are evaluated by service time, the average timesteps needed to finish tasks after they enter the task set.An algorithm solves an instance when the resulting service time of all tasks is bounded.
- Solvability: Not every MAPD instance is solvable because agents may be unable to complete a task without blocking one another.Figure 1 illustrates two free agents for which neither can finish the task.
- Well-formed instances: A well-formed instance has finitely many tasks, at least as many non-task endpoints as agents, and an endpoint-to-endpoint path that traverses no other endpoint.Endpoints include initial, pickup, delivery, and possibly designated parking locations.
- Well-formed instances: Figure 2 distinguishes blocked cells, agent initial locations, task endpoints, and non-task endpoints across three MAPD instances.The left instance is well-formed; the center lacks enough non-task endpoints, and the right violates the endpoint-path condition.
4. DECOUPLED MAPD ALGORITHMS
The paper presents two decoupled MAPD algorithms, TP and TPTS, that use token-based coordination to assign tasks and plan collision-free paths. Both algorithms solve all well-formed MAPD instances, while TPTS can improve task assignments through swaps.
- Overview: Decoupled MAPD algorithms let agents assign themselves to tasks and compute collision-free paths using shared global information.TP and TPTS coordinate through token-based information about paths, tasks, and assignments.
- Token Passing (TP): TP passes a synchronized token containing agents’ paths, unassigned tasks, and assignments, allowing agents to plan sequentially.Each agent uses Path1 to route through pickup and delivery locations, or Path2 to move to an endpoint when it cannot take a task.
- Token Passing (TP): A* searches in location-timestep space produce paths that avoid collisions with the other paths stored in the token.States and transitions causing vertex or edge collisions are excluded from the search space.
- Token Passing (TP): TP’s Path1 and Path2 functions succeed on well-formed instances, yielding the theorem that TP solves all well-formed MAPD instances.The guarantee relies on endpoint structure and agents eventually requesting the token so tasks can be assigned and executed.
- Token Passing with Task Swaps (TPTS): TPTS extends TP by allowing an agent to take a task already assigned to another agent when it can reach the pickup location sooner.The displaced agent receives the token and can seek a new task; TPTS also solves all well-formed MAPD instances.
- Token Passing with Task Swaps (TPTS): TPTS is often more effective than TP but not universally better: one illustrated instance gives TP service time two and TPTS service time three.The example uses two agents and two tasks whose pickup and delivery locations coincide for each task.
5. CENTRALIZED ALGORITHM
CENTRAL is a centralized strawman that assigns endpoints to free agents and plans collision-free paths for all agents simultaneously. Its path-planning procedure is guaranteed to succeed for well-formed MAPD instances.
- Centralized procedure: CENTRAL repeatedly assigns endpoints to agents and replans paths for all agents from their current locations.At each timestep, it assigns endpoints, solves the resulting MAPF instance, and moves agents one timestep.
- Endpoint construction: CENTRAL greedily selects task pickup locations and adds distinct parking endpoints for free agents when necessary.Parking locations minimize the cost of a cost-minimal path from each free agent’s current location.
- Endpoint assignment: The Hungarian Method assigns free agents to endpoints while prioritizing task pickup locations over parking locations.Modified costs make pickup assignment more important than rest-location assignment, and closer pickups more important than closer parking locations.
- Path planning: Path planning for newly occupied agents returns paths successfully for well-formed MAPD instances.The construction avoids collisions with the most recently calculated paths of other agents.
- Path planning: Path planning for free agents also returns paths successfully for well-formed MAPD instances.Free agents are moved to assigned endpoints without colliding with other agents’ most recently calculated paths.
6. EXPERIMENTAL EVALUATION
The evaluation compares TP, TPTS, and CENTRAL in a 50-agent simulated warehouse using 500 online delivery tasks across six task frequencies. CENTRAL generally achieves the shortest service times, TP the lowest runtimes, and TPTS occupies an intermediate position.
- Experimental setup: 500 delivery tasks were generated in a 50-agent warehouse across six task frequencies from 0.2 to 10 tasks per timestep.Pickup and delivery locations were randomly selected from task endpoints.
- Makespans and service times: 42%: TPTS service time was up to about 42 percent smaller than TP’s in some experimental runs.CENTRAL’s service time was up to about 48 percent smaller than TP’s in some runs.
- Makespans and service times: CENTRAL, TPTS, and TP were generally ordered from smallest to largest makespan and service time.Makespans and service times tended to decrease as the number of agents increased, although congestion could increase with more agents.
- Runtimes per timestep: TP, TPTS, and CENTRAL were generally ordered from smallest to largest runtime per timestep.Runtimes were below 10, 200, and 4,000 milliseconds, respectively, in all experimental runs.
7. CONCLUSIONS
The paper studies lifelong MAPD through TP and TPTS, proves both solve all well-formed instances, and evaluates them against CENTRAL. The conclusions characterize trade-offs in throughput-related performance, runtime, scalability, and communication.
- 7. CONCLUSIONS: The paper studies lifelong MAPD using Token Passing (TP) and Token Passing with Task Swaps (TPTS), extending MAPF to online pickup-and-delivery tasks.MAPD requires agents to serve task streams while moving first to pickup locations and then to delivery locations without collisions.
- 7. CONCLUSIONS: Both TP and TPTS solve all well-formed MAPD instances, unlike the centralized strawman CENTRAL, which lacks this guarantee.The theoretical guarantee applies to the realistic subclass of well-formed instances.
- 7. CONCLUSIONS: The algorithms were evaluated against CENTRAL in simulated warehouse environments, including a 81 × 81 grid with 500 agents.Figure 6 depicts the large simulated warehouse layout used for the 500-agent experiment.
- 7. CONCLUSIONS: TP has the lowest runtime per timestep, while CENTRAL, TPTS, and TP tend to have increasing makespans and service times in that order.The reported runtime ordering is TP, TPTS, CENTRAL; the makespan and service-time ordering is CENTRAL, TPTS, TP.
- 7. CONCLUSIONS: TP is suited to real-time computation and scales to MAPD instances with hundreds of agents and tasks, whereas TPTS balances TP and CENTRAL with limited communication.TP can be extended to a fully distributed algorithm; TPTS occupies an intermediate practical position.