Many-to-Many Multi-Agent Pickup and Delivery

The gist: The Many-to-Many Multi-Agent Pickup and Delivery (M2M) algorithm addresses the NP-hard four-dimensional assignment problem in real warehouses, achieving up to 38.8% more tasks completed compared to prior state of the art LNS-PBS in simulation results>

Problem Formulation

The Many-to-Many Multi-Agent Pickup and Delivery (M2M) problem is formally defined as computing task allocation A and a collision-free motion plan M to maximize overall performance measured as task throughput (tasks/min)> This many-to-many variant can be modeled as a 4-dimensional assignment problem involving agents, tasks, start locations, and destinations, aiming to minimize the sum of costs of the task assignments> The location of agent ai at timestep t is denoted by li(t) ∈ V, and at each timestep, agents either move to an adjacent location or wait at their current location> A solution to a M2M-MAPD problem takes the form of task allocation A and a collision-free motion plan M that meets task ordering constraints such that sp is visited prior to dq> An agent with an empty task sequence is referred to as a free agent, otherwise it is referred to as an active agent>

Many-to-Many Task Allocation

The M2M algorithm first computes an initial suboptimal many-to-many allocation Ainitial, by iteratively assigning the minimum cost agent, task, start location, destination pairing until all tasks, start, or destinations have been assigned> To encode allocation costs, a cost tensor C ∈ RM×N×P ×Q is constructed where c(m,n,p,q) ∈ C is the estimated cost of traveling from the last destination in T m to sp to destination dq> The cost function cm,n,p,q is defined as K if sp ∈/ Sn or dq ∈/ Dn or if sp ∈ Valloc and dq ∈ Valloc respectively> Otherwise, the cost of cm,n,p,q is the estimated duration of agent am traveling from the final destination of T m to sp and the estimated duration to traverse from sp to dq> The algorithm decomposes C into four cost matrices: CAS ∈ RM×P, CSD ∈ R P ×Q, CT S ∈ 0, 1 N×P, and CT D ∈ 0, 1 N×Q> These matrices are used to compute an initial suboptimal assignment of agents, tasks, start locations, and destinations> The minimum element cm,p,q in CASD is found and kept if smaller than the best previously found element> This process is repeated until either Tf ree = ∅ or every element in CT S or CT D is equal to 0>

Large Neighborhood Search (LNS)

Given Ainitial, the algorithm uses LNS to iteratively attempt to improve the current solution Acurr until a specified time is reached, when LNS returns the best found solution, Af inal> During improvement, LNS first destroys a portion of the current solution via a destroy operator and then reassigns the removed tasks via a repair operator> The Shaw Removal operator removes interrelated tasks by computing an interrelatedness score r(τi, τj) defined as ω1(dist(di, dj) + dist(si, sj))+ω2(t(si) − t(sj) + t(di) − t(dj)) where ω1 is the weight for spatial distance and ω2 is for temporal relatedness> The M2M Repair operator then allocates the tasks in Tf ree or until every element in CT S or CT D is equal to 0> A new solution Anew is accepted as Acurr with a metropolis acceptance criterion defined by (accept if f(Anew) > f(Acurr) else rand[0, 1]

M2M with SKU Distribution

The M2M-wSKU variant further improves performance by reasoning about spacial item distribution when selecting source and destination locations> To incentivize choosing start locations and destinations which improve a SKU’s distribution, the cost function is modified by performing a nearest neighbor search at sp or dq depending on if τn ∈ Tout or τn ∈ Tin respectively> The cost function is then modified as wb(cost(am, sp) + cost(sp, dq))−wsNearestNeighbor(sp) if τn ∈ Tout and wb(cost(am, sp) + cost(sp, dq))+wsNearestNeighbor(dq) if τn ∈ Tin> Locations of each SKU are stored as a KD-Tree to compute the nearest neighbor search in O(log(n)) time on average>

Multi-Agent Path Finding

Once Af inal is returned from LNS, the algorithm utilizes Multi-Agent Path Finding (MAPF) to compute a corresponding motion plan M for the agents to execute> In this work, path plans are computed segment-by-segment, rather than from lm(t) to the final destination in T m> M2M and M2M-wSKU were evaluated using Enhanced Conflict Based Search (ECBS) and Priority Based Search (PBS), with PBS performing better with the task allocation method>

Experimental Setup

The experiments are conducted in a simulated warehouse environment modeled as a discrete two-dimensional grid, using three warehouse layouts: Restricted, Open-Top, and Open maps> The simulation operates under assumptions including perfect localization of agents and SKUs, noiseless sensing, lossless communication, and no actuation errors or task failures> Performance is reported as an average over 10 simulations for each experimental condition> Metrics evaluated include Throughput (tasks completed per unit time), Computation Time for the task allocation step, and Scalability regarding the computation time required to obtain Ainitial with increases values of M and N> M2M scales to 150 agents and 150 tasks within the 1-second compute limit window in the restricted map>

Conclusion

M2M consistently outperforms or maintains comparable throughput against LNS-PBS across all map types, with all methods maintaining low standard deviation throughput> M2M remains robust to increasing inventory density, while the mean throughput of LNS-PBS degrades significantly in high-density inventory scenarios> M2M strictly outperforms our variant M2M-wSKU, which suggests the additional time for M2M-wSKU to distribute items through the warehouse does not result in additional performance gains> The algorithm demonstrates scalability up to 150 agents and 150 tasks given a 1 second computation budget in the restricted map>

--- Page 1 ---

Many-to-Many Multi-Agent Pickup and Delivery

Ethan Schneider, Jingkai Chen, Tianyi Gu, Kunlei Lian, Seth Hutchinson, Sonia Chernova >

--- Page 2 ---

Fig. 1: (a) Multi-location inventory management is common practice in warehouse settings, where multiple source and destination locations are available for storing and retrieving goods. In multi-agent pickup and delivery contexts, the choice of source and destination locations can significantly impact system performance (e.g., for agent ai (center above) the sequence s3d1s4d5 is far more efficient than s1d3s4d4). (b) Current state-of-the-art methods focus on one-to-one allocation between agents and tasks, ignoring multi-location inventory options. (c) We introduce Many-to-Many Multi-Agent Pickup and Delivery, which accounts for agents, tasks, and multiple source and destination locations per item. Our computationallyefficient approach yields significant improvements in task throughput in long-horizon simulations across 3 warehouse layouts.

--- Page 3 ---

Method online assign seq. of tasks many-to-many

CENTRAL [16]

TA-Hybrid [14]

HBH+MLA[7]

RMCA [4]

LNS-PBS [24]

M2M / M2M-wSKU (ours)

--- Page 4 ---

Fig. 2: Overview of M2M method and M2M-wSKU variant.

--- Page 5 ---

A. Many-to-Many Task Allocation

Our algorithm, M2M, is initiated when the system has unassigned tasks (Tf ree ̸= ∅). M2M first computes an initial task allocation Ainitial, by iteratively assigning the minimum cost agent, task, start location, destination pairing until all tasks, start, or destinations have been assigned> To encode allocation costs, we construct a cost tensor C ∈ RM×N×P ×Q in which an element c(m,n,p,q) ∈ C is the estimated cost of traveling from the last destination in T m to sp to destination dq> In addition to the estimated duration cost, C must encode whether sp ∈ Sn and dq ∈ Dn, and whether sp ∈ Talloc and dq ∈ Talloc> We define the cost function as: cm,n,p,q = K if sp ∈/ Sn or dq ∈/ Dn or if sp ∈ Valloc and dq ∈ Valloc> K is a very large cost (e.g.

1. Bold task allocation through 4D assignment modeling allows agents to jointly decide which task to execute and which pickup and delivery sites to use, addressing prior work that focused only on one-to-one assignments. This enables systems to handle many-to-many MAPD scenarios, where items can be retrieved from or stored at multiple locations, solving the NP-hard problem.

2. Bold cost function optimization via M2M and M2M-wSKU allows for dynamic task sequencing based on estimated durations and spatial distribution. Specifically, M2M minimizes the sum of estimated task durations, encouraging agents to complete tasks sooner, while M2M-wSKU modifies this by incorporating SKU distribution to incentivize assignments that remove items which are close together while encouraging destinations which place SKUs further away from existing items of the same SKU.

3. Bold solution improvement via Large Neighborhood Search (LNS) metaheuristic enhances allocation quality iteratively. The algorithm employs a destroy operator, such as Shaw Removal, to remove Nremove interrelated tasks from the current solution, followed by a repair operator to reallocate them, ensuring that the final allocation is optimized for long-horizon performance.

4. Bold collision-free path planning via Priority Based Search (PBS) computes motion plans based on task allocation. The system uses PBS to address the MAPF problem after obtaining the task allocation, and results show that PBS performed better with our task allocation method and setting.

5. Bold enhanced resilience to inventory density is achieved by using M2M over LNS-PBS in dense environments. The paper shows that M2M remains resilient in highly dense warehouse inventory conditions, whereas LNS-PBS experiences significant performance degradation as density increases, leading to a substantial increase in mean throughput (up to 38.77% at 90% density).

6. Bold scalability is demonstrated by the M2M algorithm's ability to handle large-scale problems. M2M scales to 150 agents and 150 tasks within the 1-second compute limit window in a restricted map, showing that the method remains computationally feasible for complex environments with many agents and tasks.