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

Background

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), each 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.

Core Innovation

Stigmergic Graph Memory (SGM) is a bounded, decaying memory layer inspired by biological stigmergy (pheromone-based coordination):

• Records recent execution signals (traversal counts, wait times) on warehouse nodes and directed edges
• Ranks feasible endpoints and route preferences for many-to-many allocation
• Does not alter collision constraints or planner validity — orthogonal to existing planners, easy to integrate
• Bounded size and decay ensure adaptation to changing traffic patterns

Results

Evaluated on paired request streams across five warehouse layouts, three load levels, and 25 seeds per condition:

• Outperforms two reconstructed many-to-many allocation baselines in all 15 map-load conditions
• Throughput gains of 20.5–36.7%
• Conclusion: recent execution memory improves throughput by shaping which feasible goals enter the planner, not only how agents travel to already fixed goals

Limitations

Evaluation is simulation-only, without real-world warehouse validation. Sensitivity analysis of SGM parameters (memory capacity, decay rate) is limited. Comparison against more sophisticated learned scheduling approaches is also relatively constrained.

Industry Implications

This work offers direct practical value for warehouse automation and logistics. SGM as a lightweight add-on module can be integrated into existing warehouse management systems without modifying core planners. The 20%+ throughput improvement translates to significant cost savings and efficiency gains in large-scale warehouse operations. The bio-inspired approach also provides a template for coordination problems in other multi-agent domains.