cs.ROAug 27, 2026

Pass the Bucket: Efficient, Robust, Local Load Balancing for Teams of Heterogeneous Robots

Authors: Tobias Wallner, Dominik Krupke, Arne Schmidt, Sándor P. Fekete

Organizations: Department of Computer Science, TU Braunschweig, Braunschweig, Germany. · L3S Research Center, Germany

Read PDF
Ask AI
Cite

Copy citation

DOINot available for this paper

Abstract

We study the problem of decentralized, self-organized task sharing for a swarm of heterogeneous robots that collaborate in transportation or other objectives that require coordinated motion planning. To this end, we present theoretical and practical results for the simple but effective mechanism of bucket brigades for load balancing, in which a team of heterogenous robots share a spatial task in a confined, one-dimensional space, while only being able to sense collisions with neighbors or walls. The goal is to optimize throughput of the overall system, without central control or information, aiming at an interval partition proportional to robot velocities. We address possible chaotic system behavior by developing a stabilization mechanism based on simple local aid, a ``token'', that temporarily decelerates robots after an encounter. This purely local change eliminates persistent oscillations, resulting in convergence towards a stable system state. We accelerate system convergence by comparing a single boundary token to ubiquitous two-directional tokens and optimizing the deceleration factor. Event-driven simulations report convergence times and robustness: For a large variety of perturbations (such as robot deletion, position or velocity jittering), the system reliably re-converges. The results suggest a local, practical mechanism for robust load balancing for heterogeneous teams of robots that promises an effective tool as basis for more complex scenarios.

Figures & tables

Fig. 1: Example configuration: 3 robots; velocities 1, 2, 3; starting positions 0.1, 0.6, 0.7; starting directions left, right, right. The dashed gray vertical lines indicate the equilibrium borders of the robot pairs.
Fig. 2: Collision positions for the configuration of Fig. 1 . Dashed lines: equilibrium borders xi∗x_{i}^{*} .
Fig. 3: Collision positions for another start configuration of 5 robots. Dashed lines: equilibrium borders xi∗x_{i}^{*} .
Fig. 4: Closed time-matching quadrilaterals around pair (i,i+1)(i,i{+}1) (shown for odd ii ) yield the two linear relations for (xi′,xi±1′)(x_{i}^{\prime},x_{i\pm 1}^{\prime}) in one alternating sweep.
Fig. 5: Collision positions of both pairs for exemplary start configuration of Fig. 1 . This illustrates the rotational evolution of (x,y)(x,y) .
Fig. 6: Collision positions for exemplary start configuration of Fig. 1 with one-directional token in-between the first pair ( Token-1 ). The system approaches the equilibrium quickly.
Fig. 7: Ratio of catch-up events to total collisions per clock time bucket, here shown for n=5n=5 (other nn look similar). Even without tokens, the system reaches the rotational, catch-up free state quickly.
Fig. 8: Empirical CCDFs for n∈{3,5,7}n\in\{3,5,7\} . Token-all induces faster convergence than just Token-1 . More robots take longer to converge.
Fig. 9: Empirical CCDFs for n=5n=5 with Token-all , varying the maximum velocity.
Fig. 10: Mean convergence times with Token-all , varying the slow-down factor α\alpha . The α\alpha inducing the fastest convergence depends on nn .
Fig. 11: Perturbation of adding/removing one randomly chosen robot from an equilibrium-like state, resulting in n∈{5,7}n\in\{5,7\} after the change. Reconvergence after removing a robot is faster than reconvergence after adding one; Token-all induces faster reconvergence than Token-1 .
Fig. 12: Mean convergence time vs. position jitter amplitude (all robots perturbed) with Token-all , for n∈{3,5,7,9}n\in\{3,5,7,9\} . Growth is at most linear; no catastrophic degradation occurs even at 25%25\% displacement.
Fig. 13: Reconvergence CCDFs after velocity perturbation (factor 0.50.5 or 22 ) of one robot from equilibrium, for n=5n=5 , vs. random-start baseline. Reconvergence is faster than baseline (Mann–Whitney U, p<0.0125p<0.0125 ).
More in this topic

Multi-Robot Systems

Multi-robot systems coordinate teams of robots to plan, perceive, communicate, and act together in shared tasks and environments.

See all 206 papers

Explore similar work

CardsList

  1. Capability-Aware Heterogeneous Control Barrier Functions for Decentralized Multi-Robot Safe Navigation

    Apr 14, 2026Joonkyung Kim, Yanze Zhang, Wenhao Luo +1Safe Robot NavigationControl Barrier Functions

    Department of Computer Science and Engineering, Texas A&M University · Department of Computer Science, University of Illinois Chicago

  2. Dynamic Multi-Robot Task Allocation under Uncertainty and Communication Constraints: A Game-Theoretic Approach

    Apr 13, 2026Maria G. Mendoza, Pan-Yang Su, Bryce L. Ferguson +1Multi-Robot Task AllocationMulti-Agent Resource Allocation

    Department of Mechanical Engineering, University of California, Berkeley, Berkeley, CA, United States · Department of Electrical Engineering and Computer Science, University of California, Berkeley, Berkeley, CA, United States · Thayer School of Engineering, Dartmouth College, Hanover, NH, United States

  3. FORMICA: Decision-Focused Learning for Communication-Free Multi-Robot Task Allocation

    Feb 20, 2026Antonio Lopez, Jack Muirhead, Carlo PinciroliMulti-Robot Task AllocationMulti-Agent Resource Allocation

    Dept. of Robotics Engineering, Worcester Polytechnic Institute, Worcester MA 01609, USA