Stigmergic Graph Memory: An Environment-Aware Approach for Many-to-Many Multi-Agent Pickup and Delivery

Summary

Automated fulfillment warehouses must continuously assign and execute pickup-and-delivery work while avoiding congestion.

Abstract Summary

Automated fulfillment warehouses must continuously assign and execute pickup-and-delivery work while avoiding congestion. In many-to-many Multi-Agent Pickup and Delivery (MAPD), a request specifies a stock-keeping unit rather than fixed endpoints, requiring the controller to select an agent, source, and destination before path planning. Existing graph-guidance methods primarily influence routing after goals are fixed, leaving endpoint instantiation uninformed by recent traffic. We introduce Stigmergic Graph Memory (SGM), a bounded, decaying memory layer that records recent execution signals on warehouse nodes and directed edges to rank feasible endpoints and route preferences without altering collision constraints or planner validity. Across paired request streams on five layouts, three load levels, and 25 seeds per condition, SGM outperforms two reconstructed many-to-many allocation baselines in all 15 map-load conditions, with paired throughput gains of 20.5-36.7%. These results show that recent execution memory can improve warehouse throughput by shaping which feasible goals enter the planner, not only how agents travel to already fixed goals.

Key Points

Automated fulfillment warehouses must continuously assign and execute pickup-and-delivery work while avoiding congestion.
In many-to-many Multi-Agent Pickup and Delivery (MAPD), a request specifies a stock-keeping unit rather than fixed endpoints, requiring the controller to select an agent, source, and destination before path planning.
Existing graph-guidance methods primarily influence routing after goals are fixed, leaving endpoint instantiation uninformed by recent traffic.
We introduce Stigmergic Graph Memory (SGM), a bounded, decaying memory layer that records recent execution signals on warehouse nodes and directed edges to rank feasible endpoints and route preferences without altering collision constraints or planner validity.
Across paired request streams on five layouts, three load levels, and 25 seeds per condition, SGM outperforms two reconstructed many-to-many allocation baselines in all 15 map-load conditions, with paired throughput gains of 20.5-36.7%.

Problem Setting

We model the warehouse as an undirected graph $G=(V,E)$ with agents $\mathcal{R}=\{a_{1},\ldots,a_{\mathcal{I}}\}$. At each discrete timestep, an agent either waits at its current vertex or moves along an adjacent edge.

A joint motion plan must satisfy the standard MAPF constraints: no two agents may occupy the same vertex at the same timestep, and no two agents may traverse the same edge in opposite directions during the same timestep. Tasks arrive online.

Stigmergic Graph Memory

SGM operates within an event-driven rolling-horizon controller based on Rolling-Horizon Collision Resolution (RHCR) ( Li et al. 2021 ) , using Priority-Based Search (PBS) as the MAPF backend ( Ma et al. 2019a ) . Figure 1 shows a schematic of SGM architecture.

At each control cycle, the system updates memory from recent execution events, instantiates eligible requests, computes collision-free paths for active goals, executes one action from each path, and updates pickup, delivery, and completion states.

Experimental Protocol

We evaluate SGM and its adaptive variant, ASGM, against M2M and its SKU-aware variant, M2M-wSKU. The main small-map benchmark contains $5\times 3\times 25\times 4=1500$ method–map–fleet-level–seed runs: five warehouse layouts (Figure 2 ), three parking-normalized fleet levels, and 25 paired seeds. Each layout contains 93 designated parking cells.

We evaluate low, medium, and high fleet levels with 28, 56, and 84 agents, corresponding to 30.1%, 60.2%, and 90.3% of parking capacity, respectively.

Results

Table 3 reports cumulative completed tasks at three checkpoints on the restricted, open-top, and open benchmark layouts. SGM is the best method in 26 of the 27 displayed map–fleet–checkpoint cells. The only exception is the earliest checkpoint on the high-fleet open layout, where M2M-wSKU is ahead at timestep 600; SGM overtakes it by timestep 1800 and remains ahead at the end of the horizon.

Sources and Demonstrations

Figures are reproduced from Dutta et al. See the full paper for experimental details and the project page, when the paper links one, for demonstrations and videos.