PaperlayerView exact revision on arXiv

Source-linked AI summary

Integrated Task Assignment and Path Planning for Capacitated Multi-Agent Pickup and Delivery

Zhe Chen, Javier Alonso-Mora, Xiaoshan Bai, Daniel D. Harabor, Peter J. Stuckey

arXiv:2110.14891v1cs.MAcs.RO

TL;DR

MAPD requires assigning continuously arriving transport tasks to robots and planning collision-free paths, yet leading approaches separate these difficult decisions. The paper couples them using real coordination costs, marginal-cost assignment, and Large Neighbourhood Search, and reports efficient, timely solutions with improvements over recent methods while also studying multi-task robot capacity.

  • Problem

    MAPD combines intractable task assignment and collision-free path finding in online logistics settings where tasks arrive continuously.

  • Method

    The approach jointly assigns tasks and plans paths using real collision-free costs, a marginal-cost heuristic, and Large Neighbourhood Search, including a multiple-task-per-robot variant.

  • Results

    The approach yields efficient and timely solutions, improves on TPTS in numerical simulations, and achieves lower total travel delay with better real-time suitability than CENTRAL and TPTS.

  • Takeaways & Limitations

    Coupling assignment with path planning and allowing higher robot capacity can reduce solution costs and improve warehouse throughput and efficiency.

Abstract

from arXiv · show

Multi-agent Pickup and Delivery (MAPD) is a challenging industrial problem where a team of robots is tasked with transporting a set of tasks, each from an initial location and each to a specified target location. Appearing in the context of automated warehouse logistics and automated mail sortation, MAPD requires first deciding which robot is assigned what task (i.e., Task Assignment or TA) followed by a subsequent coordination problem where each robot must be assigned collision-free paths so as to successfully complete its assignment (i.e., Multi-Agent Path Finding or MAPF). Leading methods in this area solve MAPD sequentially: first assigning tasks, then assigning paths. In this work we propose a new coupled method where task assignment choices are informed by actual delivery costs instead of by lower-bound estimates. The main ingredients of our approach are a marginal-cost assignment heuristic and a meta-heuristic improvement strategy based on Large Neighbourhood Search. As a further contribution, we also consider a variant of the MAPD problem where each robot can carry multiple tasks instead of just one. Numerical simulations show that our approach yields efficient and timely solutions and we report significant improvement compared with other recent methods from the literature.

I. INTRODUCTION

MAPD models logistics systems in which robots must assign tasks and coordinate collision-free paths under difficult, often online operating conditions. The paper motivates coupled assignment and path planning because existing methods either sacrifice scalability or solution quality, while real warehouse settings also violate non-interference assumptions.

  • Applications: MAPD captures warehouse fulfillment and mail sortation, where robots transport orders or parcels through logistics operations.In fulfillment centers, items move to picking stations; in sortation centers, parcels move from emitter stations to sorted bins.
  • Problem: Each MAPD instance requires assigning every task to a robot and finding collision-free paths that complete those assignments.Both task assignment and multi-agent path finding are themselves intractable, and new tasks arrive continuously in the online setting.
  • Prior approaches: Existing methods trade off solution quality and scalability: optimal CBS-TA handles only small instances, while decentralized TPTS scales but uses greedy assignments.TA-Hybrid provides a centralized sequential alternative, but the literature also includes approaches that assume agents do not interfere, an assumption that fails in warehouses and sortation centers.
  • Proposed direction: The paper couples task assignment with path planning by evaluating assignment costs through the associated coordination problem using prioritised planning.Its assignment process uses a marginal-cost heuristic and explores alternatives through Large Neighbourhood Search.
  • Extension: The study extends MAPD to robots carrying multiple tasks simultaneously, unlike prior work that assumes capacity 1 and immediate delivery after each pickup.The authors report that this generalized case can substantially reduce solution costs and increase system performance with the same number of agents.

B. Multi-agent Pickup and Delivery

MAPD combines task assignment with collision-free path planning under online arrivals, capacity limits, and robot-interaction constraints. The formulation minimizes total travel delay while enforcing task, timing, capacity, and collision requirements.

  • Multi-agent Pickup and Delivery: MAPD methods must assign tasks to robots and plan collision-free paths, while existing approaches often address these stages separately.Centralized and optimal methods face scalability or online-adaptation limitations, while some decentralized approaches sacrifice solution quality.
  • Practical considerations: The MAPF solver’s plans do not model robots’ kinematic constraints, although compatible postprocessing can derive executable schedules.Unexpected execution delays can likewise be addressed through robust execution policies or k-robust planning.
  • Multi-agent Pickup and Delivery: The problem includes online task arrivals, robot capacity limits, dispersed origins and destinations, and collision avoidance during transport.Each task has a release time, and each robot can carry at most C tasks simultaneously.
  • Multi-agent Pickup and Delivery: The objective is to minimize total travel delay while transporting every task and avoiding collisions.The model represents robot movements and task operations over a graph of vertices and edges.
  • Multi-agent Pickup and Delivery: The formulation uses path-planning and task-assignment mappings to encode robot movements, task ownership, pickup timing, and load changes.The constraints require task completion by one robot, respect release times and travel times, maintain capacity, and prevent vertex or edge collisions.
  • Multi-agent Pickup and Delivery: The assignment algorithm initializes potential assignment heaps and repeatedly selects assignments until every task is assigned, updating affected heaps and paths.Figure 2 illustrates the current assignment set, priority heap, potential assignment heaps, and robot action sequences.

IV. TASK ASSIGNMENT AND PATH PLANNING

The paper couples task assignment with path planning by using path costs to support assignment decisions, replacing a strictly sequential treatment with simultaneous algorithms.

  • TASK ASSIGNMENT AND PATH PLANNING: The proposed algorithms perform task assignment and path planning simultaneously, using costs from path planning to support task assignment.This directly couples assignment choices with the coordination costs of the resulting paths.

A. Task Assignment Framework

The task assignment framework evaluates candidate task–robot assignments through marginal costs and planned paths, then iteratively updates the assignment structures as choices change.

  • Task Assignment Framework: The current assignment set stores each robot’s task sequence, collision-free path, and total travel delay for its assigned tasks.Each robot’s ordered action sequence begins at its current location.
  • Task Assignment Framework: For each unassigned task, a potential assignment heap stores candidate assignments to every robot based on the robots’ current assignments.Each candidate includes an updated action sequence, revised path, and cost after adding the task.
  • Task Assignment Framework: The algorithm selects the top candidate assignment, removes its task from the unassigned set, and deletes that task’s heap from the priority structure.It continues until no unassigned tasks remain.
  • Task Assignment Framework: When an assignment changes a robot’s action sequence or path, affected candidate assignments are recalculated to reflect the updated path.For other robots, the method can update only the top v heap elements to reduce recalculation overhead when collisions arise.
  • Task Assignment Framework: Each potential assignment heap is ordered by increasing marginal cost, while the priority heap’s ordering depends on the task-selection method.Path planning uses prioritised planning with space-time A* for each robot’s ordered action sequence.

B. Marginal-cost Based Task Selection

MCA assigns each unassigned task to the robot and insertion positions that minimize the task’s marginal transport cost, then evaluates the resulting collision-free path cost.

  • MCA selection: MCA selects an unassigned task, robot, and pickup and delivery insertion positions by minimizing marginal transport time.The marginal cost compares the route’s transport time after insertion with its current transport time.
  • Route insertion: The insertion operator places pickup location s_i and delivery location g_i at specified positions in the robot’s current route.When q_1 = |o_k|, pickup is inserted before the mandatory return-to-start action.
  • Cost evaluation: MCA initially minimizes marginal TTD while ignoring collisions and respecting the robot’s capacity limit.The resulting route is then passed to path planning for collision-aware evaluation.
  • Cost evaluation: planPath() uses space-time A* to generate a collision-free path and calculate the real marginal TTD for the candidate assignment.Potential assignment heaps are sorted by the marginal cost of their top candidate.

C. Regret-based Task Selection

Regret-based MCA uses look-ahead by comparing each task’s best and second-best robot costs, then assigns the task with the strongest regret under absolute or relative ranking.

  • Regret calculation: RMCA compares the marginal costs of inserting each task into its best and second-best robot routes.The best robot is the one with the smallest collision-aware marginal travel cost.
  • Regret calculation: RMCA assigns the selected task to the robot with the lowest marginal cost for transporting it.This preserves MCA’s lowest-cost robot choice after the task-selection step.
  • Absolute regret: RMCA(a) ranks tasks by absolute regret, defined from the difference between the best and second-best marginal costs.Absolute regret is the first of the two task-selection methods introduced for RMCA.
  • Relative regret: RMCA(r) ranks tasks using relative regret rather than absolute regret.Both regret variants use the same insertion procedure for each potential assignment.
  • Heap maintenance: RMCA keeps the top two candidates in each potential-assignment heap up to date, whereas MCA maintains only the top candidate.The heap is therefore ordered by absolute or relative regret for RMCA.

D. Anytime Improvement Strategies

After constructing an initial RMCA solution, the anytime strategy repeatedly destroys and repairs task assignments with RMCA until the time limit, retaining only non-worse solutions.

  • Large Neighbourhood Search: The LNS-based strategy removes some assigned tasks, reassigns them with RMCA, and accepts the new solution when its cost is no greater.The destroy-and-repair cycle continues until timeout.
  • Large Neighbourhood Search: The strategy starts from an initial RMCA solution and iteratively improves the current assignment during the available runtime.A worse repaired solution is discarded in favor of the current assignment.

1) Destroy random:

The random-destroy strategy selects a task group uniformly from assigned tasks, removes those tasks from their robots, and repairs the assignment using RMCA.

  • Destroy random: Random destroy selects a group of tasks from all currently assigned tasks.The selected group defines the neighborhood removed before repair.
  • Destroy random: The selected tasks are removed from their assigned agents and reassigned using RMCA.This provides the repair step following random destruction.

2) Destroy worst:

The experiments evaluate algorithm variants across warehouse instances, agent capacities, and task loads, using relative TTD to compare solution quality.

  • The warehouse map contains 21 x 35 tiles with task endpoints, robot starting locations, corridors, and static obstacles.
  • Offline experiments initially release all tasks to assess scalability and how task counts and other parameters affect performance.
  • The first experiment compares decoupled MCA and decoupled RMCA(r), assigning tasks using optimal path length before route planning.
  • Relative TTD is real TTD minus collision-free RMCA(r) TTD, providing a clearer baseline because absolute one-shot TTD values vary little relatively.
  • Decoupled methods are never best, supporting coupled task assignment and routing rather than solving them separately.

1) Relative TTD and Runtime:

The paper evaluates relative TTD, runtime, anytime improvement, and lifelong settings across capacities, agent counts, and task-release frequencies. Results show quality gains from coupled and neighborhood-search approaches, alongside runtime trade-offs.

  • Relative TTD and Runtime: For Cap=3, RMCA(r) becomes superior as agents increase, while for Cap=5 it is clearly best; MCA is preferable for Cap=1.
  • Relative TTD and Runtime: RMCA(a) performs poorly because absolute regret can produce uneven task loads, whereas relative regret is more stable to these changes.
  • Relative TTD and Runtime: Decoupled approaches run faster, especially with many tasks and small capacity, although MCA and RMCA remain competitive in runtime.
  • Anytime Improvement Methods: Anytime improvement is tested for 60 seconds on 25 instances with 500 tasks, varying destroy strategies, group sizes, capacities, and agent counts.
  • Anytime Improvement Methods: All three destroy methods improve MCA and RMCA(r) solution quality; destroy random and destroy worst outperform destroy multiple.
  • Lifelong Experiment: The lifelong experiment applies RMCA(r) whenever tasks arrive, with destroy random, group size 5, and one second of improvement time per timestep.

1) Result:

RMCA(r) improves normalized total travel delay over CENTRAL and TPTS, and normalized makespan over TPTS, while remaining suited to lifelong operations. Increasing robot capacity further reduces travel delay and makespan.

  • RMCA(r) achieves better solution quality than CENTRAL while consuming less runtime per timestep, supporting real-time lifelong operations.
  • Increasing robot capacity significantly reduces both total travel delay and makespan, increasing warehouse throughput and efficiency.
  • Normalized TTD accounts for task count, agent count, and task frequency, while normalized makespan scales with agent count and task frequency.
  • RMCA(r) significantly improves normalized TTD compared with CENTRAL and TPTS, and normalized makespan compared with TPTS.
  • MCA and RMCA simultaneously perform task assignment and path planning using real collision-free costs, and their anytime improvement strategy substantially improves solutions.
Loading 2110.14891v1…