Do We Run Large-Scale Multi-Robot Systems on the Edge? More Evidence for Two-Phase Performance in System Size Scaling

Authors: Jonas Kuckling, Robin Luckey, Viktor Avrutin, Andrew Vardy, Andreagiovanni Reina, Heiko Hamann · ICRA 2024

Licences

Open Access
Paper: CC BY 4.0

Everything below draws on the full paper under its CC BY 4.0 licence; its figure is credited to the authors.

TL;DR

Simulations of three multi-robot systems show performance splitting into near-optimal and near-zero runs at a critical swarm size; a population model ties this to bifurcations and long transients.

Why it matters

Operators who tune robot fleets or swarms for peak throughput may unknowingly run them at the edge of a breakdown, and long transients can make such a system look healthy for a while before it collapses. The model also predicts hysteresis, so adding or removing robots during operation, as some robust-scalability methods do, can cause sudden jumps in performance.

Problem

Swarm performance is usually reported as a mean over swarm density, which rises, peaks at a critical system size and then falls. That mean can hide a bimodal outcome in which, near the critical size, some runs perform almost optimally and others collapse into congestion, so a system tuned for peak mean performance may sit close to breakdown.

Proposed solution

The authors simulate three systems (a warehouse of rail-hung AFLE storage robots with more than 3000 units, swarm object clustering with the lasso method, and emergent taxis toward a light beacon) and plot the full distribution of performance over swarm size instead of the mean. They then model the effect in two ways: an M/M/1 queue whose service time depends on queue length, and a three-state population model (solo, grupo, fermo) written as ordinary differential equations and analyzed with nonlinear-dynamics tools.

Key insights

Near the critical system size, outcomes are bimodal: runs either operate near maximum performance or collapse to near-zero performance, with almost nothing in between.
In the population model a saddle-node bifurcation means one added robot can switch the system from high to low productivity, and removing robots switches it back only at a smaller swarm size (hysteresis).
Transient time grows over-exponentially near the critical state (critical slowing down), which the authors trace to a codimension-2 cusp bifurcation in the (N, k1) parameter space; a system can therefore run on 'borrowed time' before breaking down.
A simple modified M/M/1 queue already reproduces the linear increase and the breakdown at a critical arrival rate, and its curves resemble those of the population model.

Main results

Warehouse (96 repetitions per arrival rate): throughput rose linearly with arrival rate up to about 10⁴ AFLEs per hour, after which some runs collapsed into congestion with near-zero throughput while others stayed at maximum.
Object clustering (1000 runs per swarm size, 1 to 20 robots): best performance around 6 robots; from 10 robots upward the results split into successful and unsuccessful runs.
Emergent taxis (800 runs per swarm size, 2 to 40 robots, data from earlier work): maximum speed reached around 15 robots, where a second, low-speed phase appeared.
Modified M/M/1 queue (mean arrival rate 0.4 to 0.9, 500 samples each): breakdown at a critical mean arrival rate of about 0.65.
Population model with the default rates: the number of solo robots peaks at N = 31 and then drops quickly; with k1 = 0.001 two saddle-node bifurcations bound a bistable range, and Fig. 6 shows the state space at N = 40 inside it.

Limitations

The authors state that which model best describes two-phase performance remains open, and that future research must show whether the effect is real and relevant in industrial applications.
All three scenarios are simulations; the warehouse model is a grid world with one-way traffic and no physics, and storage rail sections are not modeled.
The emergent taxis results are reused from a previous publication rather than newly run.
The queue constants are described as arbitrary and both models are said to capture the behavior qualitatively; the paper does not fit them to the simulation data.

Field impact

Winner of the IEEE ICRA 2024 Best Paper Award on Multi-Robot Systems, with 14 citations. The paper links the open-source code of its object-clustering simulator and a video; no release of the warehouse simulator is mentioned.

Abstract

With increasing numbers of mobile robots arriving in real-world applications, more robots coexist in the same space, interact, and possibly collaborate. Methods to provide such systems with system size scalability are known, for example, from swarm robotics. Example strategies are self-organizing behavior, a strict decentralized approach, and limiting the robot-robot communication. Despite applying such strategies, any multi-robot system breaks above a certain critical system size (i.e., number of robots) as too many robots share a resource (e.g., space, communication channel). We provide additional evidence based on simulations, that at these critical system sizes, the system performance separates into two phases: nearly optimal and minimal performance. We speculate that in real-world applications that are configured for optimal system size, the supposedly high-performing system may actually live on borrowed time as it is on a transient to breakdown. We provide two modeling options (based on queueing theory and a population model) that may help to support this reasoning.

Open Source Robotics