Organizations: Sibley School of Mechanical and Aerospace Engineering, Cornell University, Ithaca, NY, USA, 14853 · Department of Mechanical Engineering, Massachusetts Institute of Technology, Cambridge, MA, USA
In this chapter, we explore how a team of autonomous agents can flexibly reconfigure the distribution of its members across many spatially embedded tasks using a task allocation strategy grounded in a generalization of the recently proposed Nonlinear Opinion Dynamics model. Motivated by an adaptive maritime survey application, we couple opinion dynamics directly to spatial movement and examine how the emergent macroscopic allocation is shaped by the interplay between environmental geometry, nature of social interactions, and task demands. We illustrate in simulation how social coupling in the model tunes group cohesion, producing macroscopic allocation patterns ranging from maximally dispersed states, to intermediate semi-dispersed states with a smaller number of distinct subgroups, to maximally cohesive consensus states, in distinct and interpretable parameter regimes. Furthermore, we demonstrate with illustrative examples how a team can reconfigure itself in real time under changing task demands. For allocation scenarios with distance-based task preference and matched number of agents and tasks, we relate numerically the final allocation in the group to the Hungarian optimum, illustrating close-to-optimal performance. We illustrate performance of this method under realistic communication constraints in the MOOS-IvP-Multi simulation environment with simulated autonomous underwater vehicles (AUVs). Together, these examples show how a common set of local interaction rules can support a large range of interpretable macroscopic allocation states and flexible transitions between them.
Figures & tables
Figure 1: Concept of operations for hypothetical cooperative USV–AUV surveying of tuna crab aggregations. (a) USVs (blue) survey the area using hydroacoustic backscatter surveys to detect adult tuna crabs in the water column. (b) A USV detects mass in the water column and deploys AUVs (red) to investigate, providing one-way travel time messages with GPS information; the AUVs communicate between each other with a broadcast message (orange) without confirmation. (c) Other USVs decide to help search the area and deploy their AUVs, which work together to either sample an existing cluster of crabs or search for nearby clusters. (d) When an AUV is almost out of battery power it surfaces to transmit data to the USV(s), which recovers the AUV if possible and recharges it for another deployment.
Notation
Space
Description
Na
N
Number of agents.
No
N
Number of sampling sites (options).
G
–
Communication graph of agents.
V
–
Node set of agents.
E
–
Edge set of agents.
Aa
{0,1}Na×Na
Adjacency matrix of the communication graph.
Table 1: Summary of notations used in this chapter.
Figure 2: One agent, two/three option bifurcation diagrams with parameters α=1.0 , d=1.0 , βs=2.0 , and τz=0.15 . Blue (red) curves denote stable (unstable) equilibria. (a) and (b) show three-dimensional bifurcation diagrams in which the equilibrium opinions of the agents’ two options are plotted for varying u . For the unbiased case (a), at u∗=1.0 , two stable equilibrium branches emerge, each corresponding to the agent selecting one of the two distinct options (tasks). In the biased case (b), the unfolding favors option 1. (c) and (d) show three-dimensional bifurcation diagrams in which the equilibrium opinions of the first two options are plotted for varying u . For the unbiased case (c), with sufficiently large u , three stable equilibrium branches emerge, each corresponding to the agent selecting one of the three distinct options (tasks). In the biased case (d), the unfolding favors option 1. Numerical bifurcation diagrams were computed with BifurcationKit.jl [ 46 ] .
Figure 3: Simulation results for Na=10 agents and No=10 sample sites. The first three trajectory subplots show agent trajectories for three distinct values of γ , illustrating the formation of clusters of varying sizes. The bottom right subplot shows the number of distinct sample sites occupied by the agents as a function of γ . At each value of γ , simulated agents start from the same initial positions and sample site distribution. An inset shows the agents interacting over a complete graph, the communication topology used in these simulations. Yellow stars denote the No sample sites, while black crosses denote the centroid of the initial agent positions. Agent trajectories are shown in different colors, with circles and squares marking the initial and final positions, respectively.
Figure 4: Numerical evaluation of optimality gap with all-to-all communication. Histograms show the percentage difference of the cost from the Hungarian optimal assignment cost obtained from 5,000 simulations from random initial conditions with indicated parameters and a fixed sample site distribution over the domain [−1,1]×[−1,1] , pictured as an inset in each subplot.
Figure 5: Consensus site selection for γ=2 and No=9 sampling sites with all-to-all communication. Each histogram shows the rank of the site selected by the group over 5,000 simulations, with initial agent positions sampled uniformly at random from [−0.9,0.9]×[−0.9,0.9] . Sites are ranked by increasing distance from the centroid of the agents’ initial positions, with rank 1 denoting the nearest site. Columns correspond to Na=4,9,20 agents; rows correspond to the two site configurations shown in the insets, where yellow stars mark sampling sites in [−1,1]×[−1,1] . The nearest site is the most frequently selected in all cases, while the distribution of selected ranks depends on the site geometry and group size.
Figure 6: Simulation results for Na=10 agents and No=10 sample sites. The first three trajectory subplots show agent trajectories for three distinct values of γ , illustrating the formation of clusters of varying sizes. The bottom right subplot shows the number of distinct sample sites occupied by the agents as a function of γ . At each value of γ , simulated agents start from the same initial positions with the same task distribution. An inset shows the interaction graph among the agents that documents the communication topology used in the simulations. Yellow stars denote the No sample sites, while black crosses denote the centroid of the initial agent positions. Agent trajectories are shown in different colors, with circles and squares marking the initial and final positions, respectively.
Figure 7: Parameter sweep simulation results for Na=10 agents and No=10 sample sites. At each value of γ , simulated agents start from the same initial positions and sample site distribution used in Fig. 6 . The subplots show the number of distinct sample sites occupied by the agents as a function of γ for a given r0 . The inset shows the interaction graph among the agents for the presented set of simulations.
Figure 8: Simulation results for Na=10 agents interacting over a complete graph and No=10 sample sites, with τz=0.1 , and γ=−1.4 in all the simulations. (I) shows convergence to Na distinct sample sites under the dynamics in Eqn. ( 9 ). (II) − (IV) show the subsequent agent trajectories initialized at the final positions obtained in (I), under the capacity-dependent bias dynamics in Eqn. ( 11 ). The capacities are set such that site G0 is closed (cj=0) , site G1 can accommodate two agents (cj=2) , and all other sample sites can accommodate one agent each (cj=1) . In (II), sites G0 and G1 are close to each other, allowing the agent initially at G0 to move directly to G1. In (III) and (IV), these sites are farther apart, causing the agent to pass through multiple intermediate sample sites before reaching G1. Depending on ϵ , the agent may switch its selected site at these intermediate locations, with multiple such switches occurring in (IV). Yellow stars denote the No sample sites. Agent trajectories are shown in different colors, with circles and squares marking the initial and final positions, respectively.
Figure 9: Simulation results for Na=5 agents interacting over a complete graph and No=5 sample sites, with τz=0.8 , and γ=−1.5 in both simulations. (I) shows convergence to Na distinct sites under the dynamics in Eqn. ( 9 ). (II) shows the subsequent agent trajectories, initialized at the final positions obtained in (I), under the capacity-dependent bias dynamics in Eqn. ( 11 ). The capacities are set such that sites marked G0 are closed (cj=0) , and site G1 can accommodate all Na agents (cj=Na) . In (II), the values of τz , γ , and ϵ are chosen such that agents initially located at G0 move directly to G1 . Yellow stars denote the No sample sites. Agent trajectories are shown in different colors, with circles and squares marking the initial and final positions, respectively.
Figure 10: Three simulation trails for ten AUVs and ten sample sites using the MOOS-IvP-Multi marine autonomy software. The maximum communication range r0=3.5km and each vehicle broadcasts a communication of opinion state every 30s . The optimality gap was a) 5.0%, b) 15.7% c) 0%. Key parameters for all runs: γ=−1.4 , κ=2 , ε=100 , βl=βq=βs=2 , vmax=1.0 , and all inputs bij were multiplied by 3e−4 .
Multi-robot task allocation (MRTA) in dynamic environments faces a fundamental tension: effective coordination requires learned structure, but that structure must adapt when conditions change. Existing methods resolve this by assuming prior task knowledge, a utility function, a cost matrix, or a trained policy making them brittle when deployed without such knowledge or when task distributions shift. We present MORPH(Multi-agent Online Rewiring through Plasticity-guided Hierarchy), a training-free MRTA framework where global allocation quality emerges from 4 local plasticity rules (synaptic, homeostatic, structural, and metaplasticity) applied to a directed pairwise preference matrix updated from runtime co-occurrence and task-completion feedback. MORPH requires no task model, no bid computation, and no offline training; response decisions use learned AGV-to-Picker preferences rather than a fixed proximity rule. Within the Gerkey-Mataric MRTA taxonomy, MORPH is the first method in the single-task, single-robot, instantaneous-assignment class to learn directed pairwise allocation preferences online. Evaluated on the TA-RWARE warehouse benchmark (8-24 agents, 4 maps, 800 steps per episode, 5 seeds), MORPH achieves 110% of all-to-all throughput at N=24 while using only 21% of possible coordination links as an efficiency advantage that grows monotonically with fleet size. Under spatial task distribution shift, MORPH degrades 3x less than proximity-based methods while its learned preferences remain uncorrelated with Manhattan distance. Systematic ablation confirms all four plasticity rules contribute measurably. Two allocation properties emerge without programming: cross-type preference dominance and progressive preference sparsification, mirroring the developmental refinement of biological neural circuits. Learned preferences are driven by task co-occurrence history, not spatial proximity.
Xuezhi Niu, Didem Gürdür Broo
Department of Information Technology, Uppsala University, 751 05 Uppsala, Sweden
Autonomous Surface Vehicles (ASVs) have been increasingly deployed to perform different kinds of maritime tasks in recent years, which motivates the need for a reliable task allocation policy that can adapt to heterogeneous tasks and maritime disturbances. In this work, we formulate a multi-robot task allocation problem in which a team of ASVs with heterogeneous capabilities needs to complete tasks of different types and appearance times under unknown stochastic spatio-temporal uncertainties from maritime disturbances. We propose a decentralized Reinforcement Learning (RL) based policy network that is trained to be robust towards uncertainty-induced observation deviations, and is able to perform individual decision making that leads to efficient execution behaviors toward heterogeneous task requirements. We evaluate the proposed policy and four baseline methods in simulated experiments with varied proportions of different tasks types, numbers of tasks, robot species and robots per species. Experiment results show that our proposed policy achieves the lowest makespan and can be deployed to address scenarios with 100 robots and 400 tasks.
Xi Lin, Yaxuan Li, Paul Szenher +1
Department of Mechanical Engineering, Stevens Institute of Technology, 1 Castle Point Terrace, Hoboken, NJ 07030, USA
Most multi-robot task allocation methods rely on communication to resolve conflicts and reach consistent assignments. In environments with limited bandwidth, degraded infrastructure, or adversarial interference, existing approaches degrade sharply. We introduce a learning-based framework that achieves high-quality task allocation without any robot-to-robot communication. The key idea is that robots coordinate implicitly by predicting teammates' bids: if each robot can anticipate competition for a task, it can adjust its choices accordingly. Our method predicts bid distributions to correct systematic errors in analytical mean-field approximations. While analytical predictions assume idealized conditions (uniform distributions, known bid functions), our learned approach adapts to task clustering and spatial heterogeneity. Inspired by Smart Predict-then-Optimize (SPO), we train predictors end-to-end to minimize Task Allocation Regret rather than prediction error. To scale to large swarms, we develop a mean-field approximation where each robot predicts the distribution of competing bids rather than individual bids, reducing complexity from O(NT) to O(T). We call our approach FORMICA: Field-Oriented Regret-Minimizing Implicit Coordination Algorithm. Experiments show FORMICA substantially outperforms a natural analytical baseline. In scenarios with 16 robots and 64 tasks, our approach improves system reward by 17% and approaches the optimal MILP solution. When deployed on larger scenarios (256 robots, 4096 tasks), the same model improves performance by 7%, demonstrating strong generalization. Training requires only 21 seconds on a laptop, enabling rapid adaptation to new environments.
Antonio Lopez, Jack Muirhead, Carlo Pinciroli
Dept. of Robotics Engineering, Worcester Polytechnic Institute, Worcester MA 01609, USA