A feedback-based planner improves target assignments for simulated robot fleets

Why distance alone falls short

In Travel Cost Calibration for Multi-Agent Target Assignment and Pathfinding, Yu Kumagai, Ryohei Banno and Keisuke Okumura investigate a combined planning problem: choose an eligible destination for every agent, then find collision-free routes to those destinations. Published on arXiv on November 6, 2026, the work is a preprint, not established peer-reviewed evidence.

A straightforward approach assigns destinations to minimize total shortest-path distance, ignoring other agents, and then plans the routes. But individually short journeys can interfere. The authors’ method, Target Assignment with Calibrated Travel costs, or TACT, repeatedly revises those distance estimates using feedback from planned routes.

The objective is to minimize flowtime: the sum of the time each agent takes to reach its destination and stop moving. This is different from minimizing the time until the last agent finishes.

How TACT uses feedback

TACT starts with a table estimating the cost of each eligible agent–destination pairing from its shortest-path distance. It adds random noise to the estimates, computes a one-to-one destination assignment that minimizes their sum, and asks a fast multi-agent path planner to produce collision-free routes.

The resulting routes reveal costs that distance alone misses. TACT blends these observations into the table, then repeats. By default, it evaluates eight candidates in parallel and gives new observations a 20% weight when updating an estimate. Noise encourages alternative assignments; feedback helps steer subsequent trials.

Importantly, the feedback measures travel loss, counting steps when an agent is not resting at its target. That differs from travel time, which runs until the agent finally settles. Temporary rests at the target do not add travel loss, even if the agent later moves again. Appendix experiments found that using travel time instead worsened results on some maps.

TACT retains the best complete assignment and routes actually evaluated, rather than simply returning an assignment derived from its final estimates. Each pairing’s cost depends on everyone else’s destinations and routes, so the table remains an approximation. The implementation uses LaCAM to evaluate candidates and can use LaCAM3 afterward to improve routes for the selected assignment.

What the experiments found

The researchers tested simulated agents on standard four-connected grid maps, including warehouse layouts. Agents move to adjacent cells or wait in discrete time steps. They cannot share a cell simultaneously or cross the same edge in opposite directions.

Two main scenarios gave each agent ten candidate targets. In EQ-DIST, an agent’s candidates were equally distant from its start, exposing differences that distance-based assignment cannot distinguish. HOTSPOT concentrated targets in a crowded region with substantial overlap between agents’ choices.

Most comparisons used a ten-second planning budget and averages over 30 runs per map and agent count; the small-instance optimality assessment used ten instances. Experiments ran on an M1 Ultra Mac Studio with 20 cores and 64 GB of memory.

On the small EQ-DIST benchmark, TACT reached the optimum through 32 agents and stayed within 1% at 64 agents. In HOTSPOT, exact optimal references were available for only four solved 16-agent instances; TACT averaged within 0.5% of their optimum.

For larger benchmarks, the authors report that TACT outperformed DBS-Hungarian, which revises assignments within small groups. A variant combining six seconds of assignment search with four seconds of LaCAM3 route improvement achieved the best solution quality in nearly all tested combinations.

For example, on one 800-agent warehouse EQ-DIST benchmark, that variant’s flowtime was 1.10 times a distance-based lower bound, compared with 2.02 for DBS-Hungarian plus route improvement and 2.44 for distance-only assignment plus route improvement. A lower bound is not necessarily achievable, so these ratios do not establish the exact gap from optimality.

Limits and practical meaning

TACT provides no guarantee on solution quality. Its near-optimal results apply where small-instance references existed, not automatically to larger problems.

A separate scalability test reached 10,000 agents on one warehouse map using a five-minute budget. That demonstrates benchmark scalability, not instantaneous planning or operation of 10,000 physical robots. The study does not establish performance under real-world motion uncertainty or sensing errors.

The complete source also reports less separation between methods in fully random and shared-target scenarios. The strongest advantages therefore should not be assumed universal. Within the tested settings, the contribution is concrete: reusing route-planning feedback can improve destination choices, rather than leaving all congestion management to the routing stage.