Abstract

Deploying a fleet of heterogeneous robots on a shared task graph requires allocating work dynamically as tasks complete, robots fail, and priorities shift. Centralized schedulers are a single point of failure and do not scale gracefully beyond a few dozen robots. Auction-based protocols, where robots bid on tasks and a lightweight auctioneer awards them, have emerged as a practical middle ground between fully centralized and fully decentralized allocation, offering provable approximation bounds on makespan in restricted settings and strong empirical performance in warehouse and outdoor logistics environments.

Combinatorial vs. Sequential Auctions

Single-item sequential auctions are simple to implement and converge quickly, but they allocate tasks one at a time without accounting for synergies between co-located tasks. A robot that wins a task near the dock should also bid more aggressively on nearby tasks. Combinatorial auctions let robots bid on bundles, capturing those synergies, but the winner-determination problem is NP-hard in general. In practice, bundle auctions with a restricted bid language, limiting bids to contiguous route segments or time-windowed clusters, make winner determination tractable while recovering most of the efficiency gain. Amazon Robotics and 6 River Systems (acquired by Shopify) both run variants of this approach in production fulfillment centers.

Bid Computation and Robot Heterogeneity

Bid computation is where robot capabilities enter the allocation. A robot bids the negative of its cost-to-go for a task given its current state: battery level, current position, current payload, and kinematic constraints. Heterogeneous fleets complicate this because bid costs are not directly comparable across robot types without a shared cost normalization. Research teams at MIT CSAIL and at KU Leuven’s robotics group have published normalization schemes based on opportunity cost, where a robot’s bid is expressed as the incremental cost above what it could earn on its best unallocated task. This produces bids that are comparable across types and avoids systematic bias toward faster or lighter robots in mixed fleets.

Fault Tolerance and Dynamic Reallocation

Auction protocols handle robot failure cleanly: when a robot drops out, its assigned tasks are re-auctioned with a priority boost proportional to deadline urgency. The re-auction overhead depends on how many tasks the failed robot held; designs that cap per-robot task holding depth (a soft cap, enforced by auction timing rather than hard limits) distribute this failure cost across more robots and reduce reallocation spikes. DARPA’s OFFSET program, which ran multi-robot urban operations exercises, produced several public datasets from auction-based allocation under simulated failures that have become standard benchmarks for protocol evaluation.

Open Challenges

Communication-constrained environments, where robots operate in tunnels, warehouses with RF dead zones, or GPS-denied outdoor sites, break assumptions about timely bid collection. Asynchronous auction variants that tolerate delayed or missing bids at the cost of slightly suboptimal allocation are an active research area, with work from the MIT Multi-Robot Systems Lab and from the German Aerospace Center (DLR) showing promise in simulation but limited field validation so far.