Ant-Colony-Inspired Dwell Memory for Traffic-Aware Idle Repositioning in Multi-Agent Pickup and Delivery

In lifelong Multi-Agent Pickup and Delivery (MAPD), an agent that has just delivered must occupy some cell while it waits, and that cell fixes the distance to its next pickup; current solvers leave the choice to the path planner as a by-product. The choice is cheap to optimise—given estimated demand it is a weighted 1-median, solvable in polynomial time—but its myopic solution is collectively poor: the best cell for one agent lies on the corridor that loaded traffic must cross, so agents that each decide well obstruct one another, and more accurate demand prediction sharpens the convergence rather than relieving it. An ant colony meets the same difficulty when a trail crowds, and resolves it through a medium that is shared, that evaporates, and that is written by events in the world rather than by the individuals reading it, so that acting on it cannot corrupt it. This paper isolates idle repositioning as a third decision layer, below task assignment and space–time path finding, and equips it with such a medium: a single decaying field of task-arrival intensity, written by releases alone and called the dwell memory, which drives a weighted 1-median in which every candidate cell also carries a price, computed once and offline from the map, for the loaded traffic it intercepts. Decay is adapted online, and a bounded reachability filter whose fallback scans the admissible free cells restores the reachability invariant whenever the fleet’s own occupancy has not already broken it—exactly, at fleets up to sixteen agents, and with a residual below 0.06 of decisions up to thirty-two. Across nine layouts and 8499 runs, with assignment and path finding untouched, mean service time falls by up to 32: the gain accrues to the response leg rather than to the delivery leg, demand memory and the structural price dominate opposite ends of the fleet-size range instead of accumulating, and the boundary of the effect tracks idle time rather than map size. The operating envelope is part of the result rather than an omission: nothing is gained below about 10 idle time, where no agent has an interval in which to move, and the layer loses in one of the twenty-four scale cells—the largest fleet on the densest benchmark map, at 74 idle—by 24.3 , through a planner-congestion channel that the structural price does not cover.