Auction-Based Multi-Robot Task Allocation in ROS 2

Let $R$ be the set of $m$ robots and $J$ a stream of tasks, each with a location and a service time $s_j$. Robot $r$ drives at speed $v$ along a route $(a_0, a_1, \dots, a_n)$ of $n=n_r$ queued tasks, where $a_0$ is its current position and $d$ is Euclidean distance. Route length $L_r$ and completion time $C_r$ follow from (21); the two objectives are in (22).

Tasks are auctioned strictly one after another (sequential single-item auction, SSI), so each bid already reflects all earlier awards. Robot $r$ prices task $j$ by its cheapest insertion into its route (23). Here $i_0=1$ while $a_1$ is being executed, so a committed task is never displaced, and $i_0=0$ when the robot is idle.

The bid is either the added distance (marg) or the finish time of the whole route (span), see (24). The auctioneer gives the task to the lowest feasible bid, ties broken by robot id (25). $F_j$ is the set of robots that bid feasibly: a robot declines when its queue is full, and an unsold task is offered again after 1 s.

A bid costs $O(n_r)$ and an auction $O(m\,n)$, with $n$ the mean queue length. SSI is greedy and has no optimality guarantee; its strength is low communication: one call, $m$ bids and one award per task.

• Nodes: task_generator, auctioneer, one robot_agent per robot, auction_viz and RViz2. Six custom messages (Task, CallForBids, Bid, Award, TaskStatus, RobotState) use reliable QoS with depth 100.
• Robots publish a 10 Hz heartbeat that doubles as discovery: the auctioneer starts only after the expected number of robots has been heard. An auction closes when all known robots have answered or after 1 s (see the message sequence figure).
• The auctioneer pauses 0.2 s after every award, because DDS does not order messages across topics and the next call for bids must not overtake the previous award.
• Robots integrate point kinematics at 2 m/s (20 Hz) and dwell $s_j$ at each task. The auction maths lives in a ROS-free module (auction_core.py), so it is unit-tested and benchmarked offline.

• Tests: 21 pytest tests. System tests run the real node modules on an in-process fake of rclpy (virtual clock, FIFO bus, rclpy-style field type checks) and assert that every task is awarded exactly once, to the lowest feasible bid, that all tasks finish and that the robots end idle.
• On ROS 2 Lyrical (Ubuntu 26.04 VM): both packages built with colcon, the benchmark reproduced the table above, and the live demo ran to completion in RViz2. The only defect found was a wrong RViz view-class name in the configuration, now fixed.
• Limitations: central auctioneer (single point of failure); obstacle-free kinematic simulation, no Nav2 or Gazebo yet; no robot-failure handling or re-auction of queued tasks; no priorities or deadlines.

• Gerkey and Mataric, Int. J. Robotics Research 23(9), 2004.
• Dias et al., Proc. IEEE 94(7), 2006.
• Koenig et al., Proc. AAAI, 2006.

Mean over 200 random scenarios: 20 m arena, 4 robots, 20 tasks, $v=2$ m/s, $s=1$ s. Percentages are relative to random assignment.

• In 200 random scenarios (4 robots, 20 tasks) the auction with marginal bids cut total distance by 70% against random assignment (62.9 m versus 207.1 m); the makespan bid cut mission time by 62% (17.7 s versus 46.0 s).
• The makespan bid trades +41% distance for −50% mission time against the marginal bid. The same pattern holds for 3 robots / 12 tasks (−61% distance, −56% time) and 6 robots / 40 tasks (−78% distance, −69% time).
• In the live run shown in the figures, the four robots drove between about 3 m and 38 m each: marginal bids give the shortest total distance but an uneven load, as the benchmark predicts.

Nav2 goals, Gazebo robots, fault-tolerant re-auctioning, and a decentralised variant.