Collaborative and multi-robot systems: coordination, allocation, and consensus

Why this subject matters now

For two decades multi-robot coordination was mostly a control-theory subject studied on paper and demonstrated on a handful of ground robots. Three things changed it into an engineering discipline with deployed systems at scale. First, warehouse automation put hundreds to thousands of mobile robots on a single floor, which turned multi-agent path planning from an academic benchmark into a throughput-critical production problem: a fulfillment center that plans paths poorly loses orders per hour. Second, cheap radios and onboard compute made genuinely decentralized estimation and control practical, so the field moved from a fictional central controller that sees everything to protocols that must work over a communication graph that loses edges as robots move out of range. Third, multi-agent reinforcement learning matured enough that learned coordination policies now compete with hand-designed controllers on tasks where the interaction structure is too complex to model, which forced the classical coordination results and the learning results into the same conversation.

A practitioner today is expected to know both halves. The classical half gives guarantees: a consensus protocol provably converges at a rate you can compute from the graph spectrum, a Hungarian solve is optimal, conflict-based search returns a certified-optimal joint plan. The learning half gives reach: a value-factorized team policy handles partial observability and reward structure that no closed-form controller captures, at the cost of the guarantees. The interesting systems combine them, using a learned high-level allocator over a provably-safe low-level controller. This page is the classical spine of that combination, with the learning connections drawn out and cross-linked to the reinforcement-learning material where the multi-agent equilibria and value factorization are developed in full.

The boundary of this page is coordination between robots. The reinforcement-learning treatment of multi-agent equilibria, the non-stationarity problem, and QMIX-style value factorization lives in the companion page on advanced reinforcement-learning topics; the spectral-graph machinery, the Fiedler vector, and the Cheeger inequality are developed from first principles in the page on the modern algorithmic toolbox, which this page leans on for consensus; and the human side of shared workspaces, where the other agent is a person rather than a robot, is the subject of the page on interactive robotics. Here the agents are all robots and the question is how they agree, divide work, and share space.

Core theory

The material below is organized as a layered coordination stack. Agreement (consensus, formation) is the substrate; allocation (assignment, auctions) decides who does what; motion (MAPF, coverage, collision avoidance) realizes it in space; and estimation and learning sit alongside as the perception and adaptation the other layers rely on. The single object that constrains every layer is the communication graph, and its algebraic connectivity recurs as the quantity that bounds how well each layer performs.

   LEARN      team policy / value factorization (CTDE, QMIX)     <- reach, no guarantee
   ESTIMATE   consensus fusion, distributed Kalman filter        <- shared belief
   MOTION     MAPF / CBS, coverage (Lloyd), ORCA avoidance       <- realize in space
   ALLOCATE   assignment (Hungarian), auctions (Bertsekas, SSI)  <- who does what
   AGREE      consensus  xdot = -Lx ,  formation = offset consensus <- substrate
   ---------------------------------------------------------------------------------
   GRAPH G    communication topology; rate bounded by lambda_2(L) throughout

Graphs, the Laplacian, and what a robot team can compute locally

Model a team of \( n \) robots as the nodes of an undirected graph \( G = (V, E) \). An edge \( (i,j) \in E \) means robots \( i \) and \( j \) can exchange messages, which in practice means they are within communication range and have line of sight. The graph is the single object that determines what the team can compute without a central coordinator: a robot can only ever combine its own state with the states of its neighbors, so every decentralized algorithm is, structurally, a rule for updating each node from its one-hop neighborhood, iterated.

Write \( A \) for the adjacency matrix, \( A_{ij} = 1 \) if \( (i,j) \in E \) and \( 0 \) otherwise, and \( D = \diag(d_1, \ldots, d_n) \) for the degree matrix with \( d_i = \sum_j A_{ij} \). The graph Laplacian is

Two properties do all the work. First, \( L \) is symmetric and positive semidefinite, because for any vector \( x \) the quadratic form is a sum over edges of squared differences,

To see the identity, expand: \( \sum_{(i,j)} (x_i - x_j)^2 = \sum_{(i,j)} (x_i^2 - 2 x_i x_j + x_j^2) \). Each node \( i \) appears \( d_i \) times contributing \( x_i^2 \), giving \( \sum_i d_i x_i^2 = x^{\top} D x \), and the cross terms give \( -2 \sum_{(i,j)} x_i x_j = -x^{\top} A x \) when the sum over unordered edges is doubled to a sum over ordered pairs. Halving recovers the stated form. Second, the all-ones vector \( \mathbf{1} \) is in the kernel: \( L \mathbf{1} = 0 \) since every row sums to zero. If the graph is connected, the kernel is exactly one-dimensional, spanned by \( \mathbf{1} \), so the eigenvalues order as

The second-smallest eigenvalue \( \lambda_2 \), the algebraic connectivity named by Fiedler, is strictly positive exactly when the graph is connected, and its magnitude measures how strongly connected the graph is. The algorithmic-toolbox page proves the Fiedler vector relaxes the balanced graph cut and sandwiches conductance through the Cheeger inequality; here the same eigenvalue reappears as the convergence rate of the fundamental coordination protocol, which is not a coincidence. A team whose communication graph is a bad cut, two dense clusters joined by one link, has a small \( \lambda_2 \) and coordinates slowly for exactly the reason the cut is cheap.

The consensus protocol and convergence to the average

The canonical distributed agreement rule is that each robot moves its scalar state toward the states of its neighbors,

which stacks into the linear system

Each robot needs only its neighbors' values, so the protocol is implementable with one-hop communication and no coordinator. The question is what it converges to and how fast. Because \( L \) is symmetric it has an orthonormal eigenbasis \( u_1, \ldots, u_n \) with \( L u_k = \lambda_k u_k \), and \( u_1 = \mathbf{1}/\sqrt{n} \). Expand the initial state in this basis, \( x(0) = \sum_k c_k u_k \) with \( c_k = u_k^{\top} x(0) \). The linear ODE has the closed-form solution

Since \( \lambda_1 = 0 \) and every other \( \lambda_k > 0 \) for a connected graph, every term except the first decays to zero as \( t \to \infty \), leaving

where \( \bar{x} = \frac{1}{n}\sum_i x_i(0) \) is the average of the initial states. Every robot converges to the same value, and that value is the average of what the team started with. This is average consensus: a fully decentralized way to compute a global mean, which is the workhorse behind distributed estimation later on. The average is preserved for all time, not just in the limit, because \( \frac{d}{dt}(\mathbf{1}^{\top} x) = -\mathbf{1}^{\top} L x = 0 \); the quantity \( \mathbf{1}^{\top} x \) is a conserved invariant of the flow.

The rate is set by \( \lambda_2 \). Define the disagreement vector \( \delta(t) = x(t) - \bar{x}\mathbf{1} \), which is the projection of \( x \) onto the orthogonal complement of \( \mathbf{1} \). It lives in the span of \( u_2, \ldots, u_n \), and on that subspace the smallest eigenvalue is \( \lambda_2 \). Differentiating, \( \dot{\delta} = -L\delta \) (the average part is annihilated), so

using the Rayleigh bound \( \delta^{\top} L \delta \ge \lambda_2 \|\delta\|^2 \) valid because \( \delta \perp \mathbf{1} \). Grönwall's inequality integrates this to

The disagreement decays exponentially with rate exactly the algebraic connectivity. A well-connected team agrees fast; a nearly-disconnected team agrees slowly, and the time constant is \( 1/\lambda_2 \). This is the single most important fact in distributed coordination, and it is why the spectral gap of the communication graph, not its size, governs how a team behaves. The result and its extensions to directed graphs, switching topologies, and communication delays are due to Olfati-Saber, Fax, and Murray, whose 2007 survey is the standard reference.

The discrete-time protocol and the step-size bound

Robots run at a fixed control rate, so the implementable protocol is a discrete iteration. Forward-Euler discretization of \( \dot{x} = -Lx \) with step \( \varepsilon \) gives

\( W \) is symmetric with row sums equal to one, so \( W\mathbf{1} = \mathbf{1} \); it is a doubly stochastic averaging matrix whenever \( \varepsilon \) is small enough to keep all entries nonnegative. Its eigenvalues are \( \mu_k = 1 - \varepsilon\lambda_k \), sharing the eigenvectors of \( L \). The mode along \( \mathbf{1} \) has \( \mu_1 = 1 \) and is preserved; every other mode must contract, which requires \( |1 - \varepsilon\lambda_k| < 1 \) for \( k \ge 2 \), i.e.

If \( \varepsilon \) exceeds this the largest-eigenvalue mode has \( |\mu_n| > 1 \) and the iteration diverges by oscillation, the discrete-time signature of an overlarge gain. Given stability, the per-step contraction factor is the spectral radius of \( W \) restricted to the disagreement subspace,

and \( \|\delta_k\| \le \rho^k \|\delta_0\| \). Minimizing \( \rho \) over \( \varepsilon \) balances the slowest and fastest modes, giving the optimal step \( \varepsilon^\star = 2/(\lambda_2 + \lambda_n) \) and optimal factor \( \rho^\star = (\lambda_n - \lambda_2)/(\lambda_n + \lambda_2) \), a ratio that is small when the spectrum is tightly clustered. The condition number \( \lambda_n/\lambda_2 \) of the Laplacian, restricted to the disagreement subspace, is the object that controls both the stable step size and the achievable rate, exactly as it does for gradient descent on a quadratic.

Rendezvous and formation control as offset consensus

Plain consensus drives every robot to the same point, which is rendezvous: useful for gathering a team, useless for holding a shape. Formation control asks the team to converge to a rigid arrangement in which robot \( i \) sits at a fixed offset \( d_i \) from the team centroid. The trick is to run consensus not on positions but on the offset-corrected coordinates \( z_i = x_i - d_i \):

By the consensus theorem \( z \) converges to \( \bar{z}\mathbf{1} \), meaning \( x_i - d_i \to c \) for a common constant \( c \), so at steady state \( x_i - x_j \to d_i - d_j \): every pair of robots holds exactly the prescribed relative offset, and the shape is the formation encoded by \( d \). The constant \( c \) is the centroid \( \bar{z} = \frac{1}{n}\sum_i (x_i(0) - d_i) \), which is conserved by the same invariant argument, so the formation locks onto wherever the offset-corrected centroid started and does not drift. Rendezvous is the special case \( d = 0 \). Moving formations follow by letting the whole team track a time-varying centroid reference added on top of the offsets, a construction developed at length in Ren and Beard's book on distributed multi-vehicle control.

Task allocation: the assignment problem

Coordination is not only agreement; it is the division of labor. The cleanest version is the linear assignment problem: \( n \) robots, \( n \) tasks, a cost \( c_{ij} \) for robot \( i \) to do task \( j \), and the goal of a one-to-one assignment minimizing total cost. Writing the decision as a permutation matrix \( X \) with \( X_{ij} = 1 \) if robot \( i \) is assigned task \( j \),

Gerkey and Mataric's taxonomy places this at the base of multi-robot task allocation: single task per robot, single robot per task, instantaneous assignment. It looks like an integer program, but it is not hard, and the reason is a structural fact worth stating precisely. Relax \( X_{ij} \in \{0,1\} \) to \( X_{ij} \ge 0 \). The feasible set becomes the set of doubly stochastic matrices, the Birkhoff polytope, and the Birkhoff–von Neumann theorem says its vertices are exactly the permutation matrices. A linear objective is minimized at a vertex, so the LP relaxation has an integral optimum with no rounding needed: the assignment problem is solvable in polynomial time.

The LP dual exposes the algorithm. Assign a price \( u_i \) to each robot and \( v_j \) to each task:

Complementary slackness ties the two: an optimal assignment uses only tight edges, those with \( u_i + v_j = c_{ij} \). The Hungarian algorithm of Kuhn (1955), building on König and Egerváry, is exactly a method that maintains a dual-feasible \( (u, v) \) and grows a matching on the tight-edge subgraph until it is perfect. The row and column reductions everyone learns as the mechanical Hungarian steps are the dual variables: subtracting the row minimum sets \( u_i \) to that minimum, subtracting the column minimum sets \( v_j \), and the covering-lines step is the primal-dual update that increases the dual objective when the current matching is not yet perfect. The algorithm runs in \( O(n^3) \). A worked Hungarian solve on a \( 3 \times 3 \) matrix is Problem 3.

Market and auction-based allocation

The Hungarian algorithm is centralized: it needs the whole cost matrix in one place. Multi-robot teams often cannot pay that, either because assembling the matrix costs too much communication or because there is no coordinator. Market-based methods, surveyed by Dias, Zlot, Kalra, and Stentz (2006), decentralize allocation by having robots bid. Bertsekas's auction algorithm is the cleanest example and, remarkably, is exact. Convert the minimization to benefit maximization with \( a_{ij} = C_{\max} - c_{ij} \). Maintain a price \( p_j \) on each task. Each unassigned robot \( i \) finds its most profitable task,

and bids an increment equal to how much better \( j^\star \) is than its second-best option, plus a small \( \varepsilon \):

The robot takes \( j^\star \), bumping whatever robot held it back into the unassigned pool. Prices only rise, and each rise is at least \( \varepsilon \), so the process terminates. At termination every robot is within \( \varepsilon \) of its best response given the prices, which makes the assignment within \( n\varepsilon \) of optimal; for integer benefits and \( \varepsilon < 1/n \) the gap is below one and the assignment is exactly optimal. The algorithm is naturally distributed: a robot needs only the current prices of the tasks it cares about, and bidding is asynchronous. Problem 4 runs the auction to optimality on the same matrix the Hungarian solves.

Auctions become genuinely approximate, not merely decentralized, when tasks interact. In sequential single-item (SSI) auctions for multi-robot routing, each robot may take several targets and its cost is the length of the tour that visits them, so the value of a target depends on which others the robot already holds. Each round, every robot bids the cheapest marginal increase in its tour length to insert one more unallocated target, and the globally cheapest bid wins. For travel costs obeying the triangle inequality, this greedy insertion is a 2-approximation of the optimal minimum-sum allocation: the total tour length is at most twice the optimum. The proof relates the sum of winning insertion bids to a spanning structure over the targets and bounds the optimal allocation below by half of it, in the same spirit as the classic double-a-minimum-spanning-tree argument for the metric traveling salesman; the full argument is given by Lagoudakis and colleagues (2005) and is out of scope here. What matters is the shape of the result: decentralization is free for the plain assignment problem but costs a factor of two once tasks couple, and that factor is the price of never assembling the joint problem in one place.

The fully general case, where robots bid on bundles of tasks whose joint value is not additive, is a combinatorial auction. Winner determination there is NP-hard as an instance of weighted set packing, so practical systems restrict the biddable bundles or accept heuristic winners. This is also where distributed constraint optimization (DCOP) enters: when allocation is entangled with hard inter-robot constraints, the problem is posed as minimizing a sum of local cost functions over a constraint graph, and algorithms such as max-sum pass messages along that graph to reach a joint assignment. DCOP and combinatorial auctions are two views of the same difficulty, that coupling between agents' choices is what turns a polynomial allocation into an NP-hard one. Max-sum, the most-used DCOP solver, is belief propagation on the factor graph of local cost functions: variable nodes (each robot's choice) and factor nodes (each shared constraint) exchange messages that summarize the best achievable cost conditioned on each candidate value, and a robot picks the value minimizing the sum of its incoming factor messages. On an acyclic constraint graph the messages converge to the exact optimum in two passes, the same guarantee belief propagation enjoys on trees; on a graph with cycles it becomes a well-behaved heuristic, which is the regime most robot teams operate in. The connection to consensus is structural: both are local message-passing schemes on the communication graph whose behavior is dictated by that graph's topology, and both trade the centralized optimum for the ability to run with one-hop information only.

Multi-robot path planning and conflict-based search

Once tasks are assigned, robots must move to them without colliding. Multi-agent pathfinding (MAPF) asks for paths on a shared graph, one per agent, minimizing a team objective (sum of path costs, or makespan) subject to no two agents ever occupying the same vertex at the same time and no two swapping across an edge. There is a fundamental tradeoff in how to solve it. The coupled formulation searches the joint configuration space, whose size is the product of the individual state spaces and therefore exponential in the number of robots; it is optimal and complete but does not scale. The decoupled formulation plans each robot separately and patches conflicts, which scales but sacrifices optimality and even completeness. Prioritized planning is the simplest decoupled method: order the robots, plan each in turn treating already-planned robots as moving obstacles. It is fast and usually good, but it is incomplete, because a bad priority order can make a solvable instance look infeasible when a low-priority robot is boxed in.

Optimal MAPF sits between these. Yu and LaValle (2013) proved that computing a makespan-optimal or sum-of-costs-optimal MAPF solution on a general graph is NP-hard, so no algorithm optimally solves every instance in polynomial time; the art is in solving the instances that arise. Conflict-based search (CBS), by Sharon, Stern, Felner, and Sturtevant (2015), is the dominant optimal solver, and its idea is to search over conflicts rather than over the joint configuration space. CBS is a two-level algorithm. The high level maintains a binary constraint tree. Each node holds a set of constraints, each of the form “agent \( a \) may not occupy vertex \( v \) at time \( t \)” (or the edge analogue), and the paths obtained by planning each agent optimally under only its own constraints. The node's cost is the sum of those path costs, which is an admissible lower bound on any solution consistent with the node's constraints, because relaxing the inter-agent coupling can only lower cost. The high level expands the lowest-cost node best-first; when a node's paths contain a conflict, say agents \( a \) and \( b \) both at vertex \( v \) at time \( t \), it splits the node into two children, one adding the constraint \( (a, v, t) \) and one adding \( (b, v, t) \). Every solution must respect one of the two, so the split loses nothing, and best-first expansion over admissible lower bounds makes the first conflict-free node CBS returns provably optimal. The low level is a single-agent A\* in space-time \( (\text{vertex}, \text{time}) \) that respects that agent's constraint set. A full CBS trace on a small grid, resolving a two-robot swap, is Problem 5; the point it makes concrete is that CBS pays only for the conflicts that actually occur, which is why it beats joint-space search on the sparse-conflict instances that dominate practice.

The two-level structure is worth seeing as a picture. The high level is a best-first search over a binary tree of constraints; the low level is an ordinary single-agent A\* that each node calls once per affected agent. The admissible node cost drives the expansion order, and the first conflict-free node is optimal.

   HIGH LEVEL  (constraint tree, expand lowest cost first)

              [ constraints = {} ]  cost = sum of low-level paths
                       |  find first conflict  (a, b, v, t)
              +--------+---------+
              |                  |
     [ +(a: not v@t) ]   [ +(b: not v@t) ]     each child adds ONE constraint
         replan a            replan b           via the low level, recompute cost
              |                  |
             ...                ...  until a node has no conflict  ->  OPTIMAL

   LOW LEVEL  (per agent, per node)
        A* over (vertex, time) states, obeying that agent's constraint set,
        returns a single-agent time-optimal path or reports infeasible.

Coverage control and Lloyd's algorithm

A different coordination task is to spread a team out to monitor a region: place robots so that every point of a domain \( Q \) is close to some robot, weighted by an importance density \( \phi(q) \ge 0 \) that says where sensing matters most. Formalize “close” through the cost of serving a point by its nearest robot,

where \( V_i = \{ q \in Q : \|q - p_i\| \le \|q - p_j\|\ \forall j \} \) is the Voronoi cell of robot \( i \), the set of points it is the nearest robot to. Cortes, Martinez, Karatas, and Bullo (2004) showed how to descend this cost with purely local information. Differentiate \( H \) with respect to \( p_i \). The subtlety is that moving \( p_i \) also moves the Voronoi boundary, so the integration domain depends on the variable. But the boundary between \( V_i \) and a neighbor \( V_j \) is by definition the set of points equidistant from \( p_i \) and \( p_j \), where the two integrands \( \|q-p_i\|^2 \) and \( \|q-p_j\|^2 \) are equal, so the boundary-motion terms from adjacent cells cancel exactly. Only the explicit dependence survives, and

where \( m_i = \int_{V_i} \phi\, dq \) is the mass of the cell and \( c_i = \frac{1}{m_i}\int_{V_i} q\,\phi(q)\,dq \) is its centroid. The gradient vanishes exactly when every robot sits at the centroid of its own Voronoi cell, a configuration called a centroidal Voronoi tessellation. Lloyd's algorithm is the resulting descent: each robot computes its Voronoi cell from its neighbors, moves toward the cell's centroid, and repeats. Every quantity a robot needs, its neighbors' positions and its own cell, is local, so coverage control is decentralized for the same reason consensus is. Problem 6 iterates Lloyd on a one-dimensional interval and shows the robots converging to the evenly-spaced centroidal configuration.

Coverage assumes the region is known. When it is not, the team must explore, and the standard decentralized rule is Yamauchi's (1997) frontier-based exploration: maintain an occupancy map, identify frontiers, the boundaries between mapped-free and unknown cells, and send each robot to its nearest frontier. Assigning robots to frontiers so they do not redundantly explore the same region is itself a task-allocation problem, which closes the loop back to auctions: production multi-robot exploration systems allocate frontiers by auction and plan paths to them with a MAPF-style planner.

Decentralized estimation over a communication graph

Robots sense noisily and locally, and a team wants a shared estimate better than any single robot's. Average consensus is the primitive. Suppose robot \( i \) has a private measurement \( y_i \) of a common quantity with independent noise; the minimum-variance fusion is the average \( \bar{y} = \frac{1}{n}\sum_i y_i \), which the team computes with no coordinator by running consensus initialized at \( x_i(0) = y_i \) until it converges to \( \bar{y}\mathbf{1} \). The convergence-rate analysis says the estimate is accurate to tolerance \( \tau \) after about \( \log(1/\tau)/\lambda_2 \) rounds, so a poorly connected team fuses slowly, the same spectral penalty again. Distributed Kalman filtering, developed by Olfati-Saber (2007), extends this to dynamic estimation: each robot runs a local Kalman update on its own measurements and reaches consensus on the information-form quantities (the inverse-covariance and the information vector) between updates, so the team tracks a moving target with a filter no node could run alone.

The information form is what makes fusion a consensus problem. A Gaussian belief with mean \( \hat{x} \) and covariance \( P \) is equivalently described by the information matrix \( Y = P^{-1} \) and information vector \( y = P^{-1}\hat{x} \). The key algebraic fact is that independent Gaussian measurements combine additively in this form: if robot \( i \) contributes information \( (Y_i, y_i) \), the centralized fused estimate is \( Y_{\text{fused}} = \sum_i Y_i \) and \( y_{\text{fused}} = \sum_i y_i \). A sum over robots is \( n \) times an average, and an average is exactly what consensus computes locally. Each robot therefore initializes a consensus at its own \( (Y_i, y_i) \), runs the protocol to reach the average \( (\bar{Y}, \bar{y}) \), and multiplies by \( n \) to recover the fused information, which it inverts back to mean-covariance form. The dynamic case interleaves this information-consensus step with each robot's local time- and measurement-update, so the team's estimate stays synchronized as the target moves, and the accuracy after a fixed number of rounds is again governed by \( \lambda_2 \): a poorly connected team fuses a stale average, which is why estimation quality and communication topology cannot be designed separately.

Range-limited communication breaks the clean picture in a specific, analyzable way. As robots move, edges appear and vanish, so the graph is time-varying, \( G(t) \), and at any instant it may be disconnected. Consensus still converges to the average provided the graph is jointly connected over time: the union of the edge sets over any sufficiently long window is connected. Jadbabaie, Lin, and Morse (2003) proved this for the discrete switching case, and it is the reason a swarm whose instantaneous graph is fragmented can still agree, as long as robots meet often enough that information eventually flows between every pair. The design consequence is that connectivity is a resource to be maintained: some multi-robot controllers add a term that keeps \( \lambda_2(G(t)) \) above a threshold, trading task performance for the connectivity that coordination needs.

Learning to coordinate: CTDE and value factorization

When the interaction is too complex to model, teams are trained rather than designed. The reinforcement-learning treatment lives in the advanced RL page; the coordination-relevant summary is this. Independent learners, each treating the others as part of the environment, face a non-stationary target, because the others' policies change during training, and they do not reliably converge. Centralized training with decentralized execution (CTDE) resolves the tension: a critic that sees the joint state and joint action is trained offline, while each agent's executable policy conditions only on its own observation. Team credit assignment, the problem of deciding which agent's action deserves credit for a shared reward, is the core difficulty, and QMIX (Rashid et al., 2018) is the canonical answer for cooperative teams. It factors the joint action-value as a monotone mixing of per-agent utilities,

with the mixing weights produced by a network conditioned on the global state. Monotonicity is the crucial constraint: it guarantees that the joint action maximizing \( Q_{\text{tot}} \) is obtained by each agent independently maximizing its own \( Q_i \), so decentralized greedy execution recovers the centralized greedy action. The price is representational: monotone mixing cannot express coordination tasks whose optimal joint value is non-monotone in the individual utilities, which is why later factorizations (QTRAN, weighted QMIX, QPLEX) relax it. The through-line to the classical half of this page is that QMIX's monotonicity constraint plays the same structural role as the Birkhoff integrality of assignment or the admissibility of CBS bounds: a restriction on the solution space chosen precisely so that a decentralized or greedy procedure recovers the centralized optimum.

Flocking and the stability of emergent behavior

Reynolds (1987) produced coordinated flocking from three local rules applied by each agent to its neighbors: separation, steer away from crowding; alignment, steer toward the average heading of neighbors; and cohesion, steer toward the average position of neighbors. The flock is emergent, no agent computes it, and the model became the template for swarm robotics. The alignment rule is exactly velocity consensus. If \( v_i \) is robot \( i \)'s velocity and it updates \( \dot{v}_i = k\sum_{j \in N_i}(v_j - v_i) \), the stacked dynamics are \( \dot{v} = -kLv \), the consensus flow on velocities, which converges to a common heading at rate \( k\lambda_2 \) and inherits the same discrete-time step-size bound \( \varepsilon k < 2/\lambda_{\max} \). This is why flocks align: the alignment rule is a provably-convergent consensus protocol wearing a biological name, a connection made rigorous by the Vicsek model analysis of Jadbabaie, Lin, and Morse and by Olfati-Saber's flocking control laws. Cohesion is a position-attraction term and separation a short-range repulsion, and the stability of the full flock requires the attractive and repulsive terms to balance; adding a potential field whose minimum is the desired inter-agent spacing turns Reynolds's heuristic into a controller with a Lyapunov function.

Reciprocal collision avoidance: velocity obstacles and ORCA

Sharing space safely is the last coordination primitive, and the decentralized standard is the reciprocal velocity-obstacle construction of van den Berg, Lin, Manocha, and Guy. Model each robot as a disc; robot \( A \) at position \( p_A \) with radius \( r_A \) must pick a velocity that avoids robot \( B \) at \( p_B \) with radius \( r_B \). The set of relative velocities \( v_{AB} = v_A - v_B \) that lead to a collision within a time horizon \( \tau \) is the truncated velocity obstacle

Geometrically this is a cone, the set of directions along which the discs eventually touch, truncated by an arc of radius \( (r_A + r_B)/\tau \) centered at \( p_{AB}/\tau \), the arc being the collisions that happen only at or before the horizon. If the desired relative velocity lies inside \( VO^{\tau}_{A|B} \), the robots are on a collision course and must change velocity. The minimal change is the vector \( u \) from the relative velocity to the nearest point on the boundary of the velocity obstacle:

when the nearest boundary is the truncating arc, with \( n = w/\|w\| \) the outward normal of the half-plane at that point. The reciprocal insight of ORCA (optimal reciprocal collision avoidance) is that both robots share responsibility: rather than \( A \) taking the whole change \( u \), each robot takes half, \( A \) constraining its velocity to the half-plane \( v_A \cdot n \ge (v_A^{\text{pref}} + \tfrac{1}{2}u)\cdot n \) and \( B \) the mirror image. Because each robot independently guarantees the pair is collision-free by respecting its own half-plane, and the halves compose to remove the whole relative-velocity violation, the team avoids collisions with no communication at all: each robot solves a small linear program to find the velocity closest to its preference inside the intersection of the ORCA half-planes from all neighbors. This is what runs on dense crowds of simulated agents and on real multi-robot fleets, and Problem 7 computes the ORCA velocity for a head-on encounter.

Where the other agent is a human rather than a robot, reciprocity can no longer be assumed, and the safety argument shifts to conservative separation: speed-and-separation monitoring keeps a protective distance that accounts for the human's possible motion and the robot's stopping distance, slowing or halting the robot as the gap closes. That human-facing regime, and the assumption structure that separates it from the robot-robot reciprocal case, is the subject of the interactive-robotics page; the coordination point here is that ORCA's guarantee rests entirely on both parties running the same protocol, which is exactly what fails when one party is a person.

Worked problems

Implementation

The consensus, assignment, and coverage primitives are short enough to write in full and run. The first block builds the five-robot Laplacian of Problem 1, computes the Fiedler value, iterates the discrete protocol, and prints the disagreement decay so the quoted convergence rate is reproduced rather than asserted. It also runs offset consensus for the Problem 2 formation.

import numpy as np

def laplacian(n, edges):
    A = np.zeros((n, n))
    for i, j in edges:
        A[i, j] = 1.0
        A[j, i] = 1.0
    return np.diag(A.sum(1)) - A                 # L = D - A, shape (n, n)

edges = [(0, 1), (1, 2), (2, 3), (3, 4), (1, 3)]
L = laplacian(5, edges)
w, U = np.linalg.eigh(L)                          # ascending eigenvalues, orthonormal eigvecs
assert np.abs(U @ np.diag(w) @ U.T - L).max() < 1e-9   # guard against a bad LAPACK
fiedler, lam_max = w[1], w[-1]
print("eigenvalues:", np.round(w, 4))            # [0. 0.6972 1.382 3.618 4.3028]
print("fiedler lambda_2 =", round(fiedler, 4))   # 0.6972

# discrete consensus x_{k+1} = (I - eps L) x_k, need eps < 2 / lam_max
x = np.array([10.0, 2.0, -4.0, 8.0, 1.0])
avg = x.mean()                                    # 3.4, the conserved average
eps = 1.0 / lam_max                               # safe step 0.2324
W = np.eye(5) - eps * L
for k in range(1, 101):
    x = W @ x
    if k in (1, 10, 100):
        print(k, np.round(x, 5), "err", f"{np.linalg.norm(x - avg):.2e}")
# 100 [3.4 3.4 3.4 3.4 3.4] err 1.02e-07   -> converges to the average

# formation control = consensus on offset-corrected coordinates z = x - d
d = np.array([0.0, 1.0, 2.0, 3.0])                # evenly spaced line, 4 robots
Lp = laplacian(4, [(0, 1), (1, 2), (2, 3)])
xf = np.array([0.0, 5.0, -2.0, 10.0])
for _ in range(4000):
    xf = xf - 0.3 * (Lp @ (xf - d))               # descend disagreement of z
print("formation:", np.round(xf, 4))             # [1.75 2.75 3.75 4.75], spacing 1.0

The second block solves the Problem 3 assignment two ways: the exact Hungarian through SciPy's solver, and Bertsekas's auction implemented directly, both returning cost 12. Running the auction in code makes the price dynamics of Problem 4 concrete.

import numpy as np
from scipy.optimize import linear_sum_assignment

C = np.array([[4, 2, 8],
              [4, 3, 7],
              [3, 1, 6]], dtype=float)

# exact, centralized: Hungarian / Jonker-Volgenant, O(n^3)
r, c = linear_sum_assignment(C)
print("hungarian:", list(zip(r.tolist(), c.tolist())), "cost", C[r, c].sum())  # cost 12.0

def auction(C, eps=0.5):
    n = C.shape[0]
    A = C.max() - C                               # benefits: maximize sum a_ij
    price = np.zeros(n)                           # price per task
    owner = [-1] * n                              # task -> robot, -1 if free
    assign = {}                                   # robot -> task
    free = list(range(n))
    while free:
        i = free.pop(0)
        val = A[i] - price                        # net value of each task to robot i
        j = int(np.argmax(val))
        best = val[j]
        val[j] = -np.inf
        second = val.max()                        # best alternative
        price[j] += (best - second) + eps         # raise price by the bid increment
        if owner[j] != -1:                        # displace the previous holder
            free.append(owner[j]); del assign[owner[j]]
        owner[j] = i; assign[i] = j
    return assign

a = auction(C)
cost = sum(C[i, a[i]] for i in a)
print("auction:", a, "cost", cost)               # matches optimum 12.0

The third block iterates Lloyd's coverage on the interval and reproduces the Problem 6 fixed point, and prints the coverage cost decreasing monotonically, which is the descent the gradient derivation guarantees.

import numpy as np

def lloyd_1d(p, iters=8):
    p = np.sort(np.asarray(p, float))
    for _ in range(iters):
        bnds = np.concatenate(([0.0], (p[:-1] + p[1:]) / 2, [1.0]))  # Voronoi boundaries
        p = (bnds[:-1] + bnds[1:]) / 2            # centroid = cell midpoint (uniform density)
    return p

def coverage_cost(p, grid=20001):
    q = np.linspace(0, 1, grid)
    d2 = (q[:, None] - p[None, :]) ** 2           # squared distance to each robot
    return d2.min(1).mean()                       # H under uniform density, up to a constant

p = np.array([0.2, 0.3, 0.9])
print("start cost", round(coverage_cost(p), 6))
p = lloyd_1d(p)
print("final", np.round(p, 5), "target", np.round([1/6, 1/2, 5/6], 5))
print("final cost", round(coverage_cost(p), 6))  # lower: descent to the centroidal tessellation

Where a vectorized rollout adds value is the swarm case, in which the same alignment consensus runs over a batch of agents and one wants it on the GPU. The next block puts a boids alignment-plus-cohesion update in PyTorch and JAX, batched over agents, sharing the shape annotations. Alignment is the velocity Laplacian flow derived above; cohesion is a pull toward the neighbor-average position. The stability bound \( \varepsilon k < 2/\lambda_{\max} \) from the consensus analysis is what keeps the batched update from oscillating.

import torch

def boids_step(pos, vel, radius=1.0, k_align=0.1, k_cohere=0.02, dt=0.1):
    # pos, vel: (N, 2). Metric neighborhood within `radius`.
    N = pos.shape[0]
    diff = pos[:, None, :] - pos[None, :, :]      # (N, N, 2) pairwise offsets
    dist = diff.norm(dim=-1)                       # (N, N)
    adj = (dist < radius).float()                # (N, N) neighbor mask
    adj = adj - torch.eye(N)                       # drop self-edges
    deg = adj.sum(1, keepdim=True).clamp(min=1)    # (N, 1) degree, avoid /0

    # alignment: velocity consensus  v += k * sum_j (v_j - v_i)  == -k L v
    v_nb = adj @ vel / deg                         # (N, 2) mean neighbor velocity
    align = v_nb - vel
    # cohesion: pull toward mean neighbor position
    p_nb = adj @ pos / deg                         # (N, 2) mean neighbor position
    cohere = p_nb - pos

    vel = vel + k_align * align + k_cohere * cohere
    pos = pos + dt * vel
    return pos, vel

torch.manual_seed(0)
pos = torch.randn(64, 2) * 5.0
vel = torch.randn(64, 2)
for _ in range(200):
    pos, vel = boids_step(pos, vel)
heading_spread = vel.std(0).norm().item()          # shrinks as headings align
print("heading spread after flocking:", round(heading_spread, 4))

import jax, jax.numpy as jnp

def boids_step(pos, vel, radius=1.0, k_align=0.1, k_cohere=0.02, dt=0.1):
    # pos, vel: (N, 2)
    N = pos.shape[0]
    diff = pos[:, None, :] - pos[None, :, :]        # (N, N, 2)
    dist = jnp.linalg.norm(diff, axis=-1)           # (N, N)
    adj = (dist < radius).astype(pos.dtype) - jnp.eye(N)
    deg = jnp.clip(adj.sum(1, keepdims=True), 1.0)  # (N, 1)

    v_nb = adj @ vel / deg                          # (N, 2) mean neighbor velocity
    align = v_nb - vel                              # velocity consensus term
    p_nb = adj @ pos / deg                          # (N, 2) mean neighbor position
    cohere = p_nb - pos

    vel = vel + k_align * align + k_cohere * cohere
    pos = pos + dt * vel
    return pos, vel

@jax.jit
def rollout(pos, vel, steps=200):
    def body(carry, _):
        p, v = boids_step(*carry)
        return (p, v), None
    (p, v), _ = jax.lax.scan(body, (pos, vel), None, length=steps)
    return p, v

key = jax.random.PRNGKey(0)
kp, kv = jax.random.split(key)
pos = jax.random.normal(kp, (64, 2)) * 5.0
vel = jax.random.normal(kv, (64, 2))
pos, vel = rollout(pos, vel)
print("heading spread:", round(float(jnp.linalg.norm(vel.std(0))), 4))

How it is done in practice

The gap between these derivations and a deployed multi-robot system is mostly about the assumptions the clean theory makes and reality breaks. Consensus assumes a fixed connected graph, synchronous updates, and noiseless communication; a real radio network drops packets, delivers them late, and partitions as robots move. Production consensus implementations are therefore asynchronous and gossip-based, updating pairwise when two robots happen to communicate, and the convergence guarantee shifts from the fixed-graph Fiedler value to the joint-connectivity condition, that the union of communication events over a window is connected. The practical design lever is that the achievable coordination rate is bounded by the algebraic connectivity of the effective graph, so systems that need fast agreement invest in connectivity, either physically through relay placement or algorithmically through controllers that keep \( \lambda_2 \) above a floor.

Warehouse fleets are the largest deployed instance of multi-robot path planning, running hundreds to thousands of robots on a shared floor. They do not run optimal CBS at that scale, because optimal MAPF is NP-hard and the instances are too large; instead they run prioritized or windowed planners that replan a short horizon frequently, accepting suboptimality for the throughput that fast replanning buys, and they engineer the environment, one-way lanes and reserved intersections, so that conflicts are rare and cheap to resolve. Bounded-suboptimal variants of CBS (ECBS and its successors) are the middle ground: they keep the two-level structure but relax the low-level and high-level optimality to a factor \( 1 + w \), which empirically solves an order of magnitude more agents than optimal CBS at a small, bounded cost premium. The open Robotics Middleware Framework (open-rmf) is the production-facing embodiment of these ideas, coordinating heterogeneous fleets across shared resources such as doors, lifts, and corridors, with the traffic scheduler doing exactly the space-time reservation that CBS formalizes.

Reciprocal collision avoidance is the most widely shipped result on this page. ORCA and its velocity-obstacle predecessors run in crowd simulation, in games, and on real multi-robot navigation stacks precisely because each robot's step is a small linear program with no communication, which is cheap enough to run at control rate for hundreds of agents. The engineering caveat that matters is that ORCA's guarantee is exactly reciprocal: it holds only when every agent runs the same protocol with compatible parameters, so a single non-compliant agent, a human, a robot from a different vendor, breaks the composition and forces the fallback to conservative worst-case avoidance. This is the concrete reason human-shared workspaces need the separate speed-and-separation discipline rather than reusing the robot-robot reciprocal argument.

The current research frontier

Three threads are active. The first is scaling optimal and bounded-suboptimal MAPF. The conflict-based-search line out of Ben-Gurion University, together with work at USC on large-scale MAPF and lifelong (continuously-replanned) variants, has pushed certified planners from tens to hundreds of agents through better conflict prioritization, symmetry-breaking, and learned heuristics that guide which conflict to branch on. The competing line replaces search with learning: decentralized neural policies that map local observations to actions and are trained to imitate a centralized planner, trading the completeness guarantee for constant-time per-step inference that scales to thousands of agents, at the cost of occasional deadlock that must be detected and repaired.

The second is learned coordination. Value factorization beyond QMIX, from the monotonic constraint toward richer but still tractable mixing (QPLEX, weighted QMIX), and the broader question of when centralized-training-decentralized-execution is necessary versus when independent learners with good representations suffice, is contested across DeepMind, Oxford, and university labs; the reinforcement-learning specifics are developed on the advanced RL page. The coordination-relevant frontier is the fusion of learned allocation with classical guarantees: a learned high-level policy that proposes assignments and a certified low-level planner or controller that executes them safely, which keeps the guarantee where safety needs it and puts the learning where the modeling is hard. Heterogeneity itself has begun to soften at the single-robot layer, since cross-embodiment training in the Open X-Embodiment collaboration (2023) and zero-shot cross-embodiment deployment efforts such as Tsinghua's RDT-2 (2025) aim at one policy family spanning hardware from different vendors, and a fleet whose members share a policy interface is an easier target for the certified coordination layer above it.

The third is connectivity-aware and communication-limited coordination. Maintaining \( \lambda_2 \) above a threshold as a control objective, planning under explicit bandwidth budgets, and learning when to communicate rather than always communicating are active across robotics groups; the last of these, learned communication policies that decide what and when to transmit, closes the loop between the decentralized-estimation results here and the multi-agent-learning results next door. The unifying question behind all three threads is the one this page opened with: how much of the centralized optimum survives when the joint problem can never be assembled in one place, and the recurring answer is that a well-chosen structural restriction, integrality, admissibility, monotonicity, reciprocity, recovers most of it.

Open source to read

• AtsushiSakai/PythonRobotics is the best starting point: readable, dependency-light implementations of consensus-style rendezvous, Voronoi coverage, reciprocal velocity obstacles, and grid path planning. Open the PathPlanning and Mapping directories and read the RVO and coverage examples against the derivations here.
• snape/RVO2 is the reference C++ implementation of ORCA by the authors of the method. Read src/Agent.cpp to see the per-agent linear program that intersects the ORCA half-planes, which is the computation Problem 7 does by hand for one neighbor.
• open-rmf/rmf is the production Robotics Middleware Framework for coordinating heterogeneous fleets over shared resources. Start with the traffic scheduler to see space-time reservation, the engineering form of the CBS constraint model, deployed at facility scale.
• Farama-Foundation/PettingZoo is the standard multi-agent environment API, the multi-agent analogue of Gym. Read pettingzoo/mpe for the particle environments in which cooperative and mixed coordination policies are benchmarked.
• oxwhirl/pymarl is the canonical QMIX and cooperative-MARL codebase. Read src/modules/mixers/qmix.py to see how the monotone mixing network enforces \( \partial Q_{\text{tot}}/\partial Q_i \ge 0 \) through nonnegative weights, the constraint derived above.
• cyberbotics/webots is a mature multi-robot simulator with physics and sensors, useful for validating a coordination controller before hardware. Its sample worlds include swarm and formation demos that exercise the consensus and flocking laws here.

Common misconceptions

“Consensus converges faster with more robots.” The rate is the algebraic connectivity \( \lambda_2 \), not the count. Adding robots that extend a chain lowers \( \lambda_2 \) and slows convergence; adding well-placed shortcut edges raises it. A large team on a sparse graph agrees more slowly than a small team on a dense one.

“The assignment problem is hard because it is integer.” Its LP relaxation is integral by Birkhoff–von Neumann, so the integrality constraint is free and the problem is polynomial. What is NP-hard is the combinatorial version where robots bid on bundles with non-additive value, or MAPF where the assignments must be realized by non-colliding paths.

“Decentralized allocation must sacrifice optimality.” Bertsekas's auction is fully decentralized and exactly optimal for the linear assignment problem, because prices are the assignment LP's dual variables. The factor-of-two loss appears only when tasks couple, as in sequential single-item auctions for routing, where the coupling, not the decentralization, is what costs.

“Conflict-based search explores the joint configuration space.” It explicitly does not; that is the whole point. CBS searches a tree of conflict constraints and plans each agent in its own space-time, expanding only the conflicts that arise, which is why it beats joint-space search on the sparse-conflict instances that dominate practice while remaining optimal.

“ORCA needs the robots to communicate.” It needs no communication at all. Each robot observes neighbors' positions and velocities and solves a local linear program; the collision-free guarantee comes from both robots independently respecting reciprocal half-planes, which is exactly why it fails against a non-compliant agent that does not run the protocol.

“Flocking is a special emergent phenomenon separate from consensus.” Reynolds's alignment rule is velocity consensus, \( \dot{v} = -kLv \), and it converges to a common heading at rate \( k\lambda_2 \) with the same stability bound as any consensus protocol. The emergence is real but the mathematics is the Laplacian flow already derived.

“QMIX can represent any cooperative team value.” No. The monotone mixing constraint, chosen so that decentralized greedy execution recovers the centralized greedy action, cannot express joint values that are non-monotone in the per-agent utilities, which is precisely the class of coordination tasks that motivated later factorizations.

Self-check

References

1. Mesbahi, M., and Egerstedt, M. Graph Theoretic Methods in Multiagent Networks. Princeton University Press, 2010.
2. Ren, W., and Beard, R. W. Distributed Consensus in Multi-vehicle Cooperative Control. Springer, 2008.
3. Bullo, F., Cortés, J., and Martínez, S. Distributed Control of Robotic Networks. Princeton University Press, 2009. coordinationbook.info
4. Bertsekas, D. P. Network Optimization: Continuous and Discrete Models. Athena Scientific, 1998.
5. Olfati-Saber, R., Fax, J. A., and Murray, R. M. “Consensus and cooperation in networked multi-agent systems.” Proceedings of the IEEE 95(1), 2007. doi:10.1109/JPROC.2006.887293
6. Olfati-Saber, R., and Murray, R. M. “Consensus problems in networks of agents with switching topology and time-delays.” IEEE Transactions on Automatic Control 49(9), 2004. doi:10.1109/TAC.2004.834113
7. Fax, J. A., and Murray, R. M. “Information flow and cooperative control of vehicle formations.” IEEE Transactions on Automatic Control 49(9), 2004. doi:10.1109/TAC.2004.834433
8. Jadbabaie, A., Lin, J., and Morse, A. S. “Coordination of groups of mobile autonomous agents using nearest neighbor rules.” IEEE Transactions on Automatic Control 48(6), 2003. doi:10.1109/TAC.2003.812781
9. Kuhn, H. W. “The Hungarian method for the assignment problem.” Naval Research Logistics Quarterly 2(1–2), 1955. doi:10.1002/nav.3800020109
10. Bertsekas, D. P. “The auction algorithm: a distributed relaxation method for the assignment problem.” Annals of Operations Research 14, 1988. doi:10.1007/BF02186476
11. Gerkey, B. P., and Matarić, M. J. “A formal analysis and taxonomy of task allocation in multi-robot systems.” International Journal of Robotics Research 23(9), 2004. doi:10.1177/0278364904045564
12. Dias, M. B., Zlot, R., Kalra, N., and Stentz, A. “Market-based multirobot coordination: a survey and analysis.” Proceedings of the IEEE 94(7), 2006. doi:10.1109/JPROC.2006.876939
13. Lagoudakis, M. G., Markakis, E., Kempe, D., Keskinocak, P., Kleywegt, A., Koenig, S., et al. “Auction-based multi-robot routing.” Robotics: Science and Systems, 2005. doi:10.15607/RSS.2005.I.045
14. Sharon, G., Stern, R., Felner, A., and Sturtevant, N. R. “Conflict-based search for optimal multi-agent pathfinding.” Artificial Intelligence 219, 2015. doi:10.1016/j.artint.2014.11.006
15. Yu, J., and LaValle, S. M. “Structure and intractability of optimal multi-robot path planning on graphs.” AAAI Conference on Artificial Intelligence, 2013. doi:10.1609/aaai.v27i1.8541
16. Cortés, J., Martínez, S., Karatas, T., and Bullo, F. “Coverage control for mobile sensing networks.” IEEE Transactions on Robotics and Automation 20(2), 2004. doi:10.1109/TRA.2004.824698
17. Yamauchi, B. “A frontier-based approach for autonomous exploration.” IEEE International Symposium on Computational Intelligence in Robotics and Automation, 1997. doi:10.1109/CIRA.1997.613851
18. Reynolds, C. W. “Flocks, herds and schools: a distributed behavioral model.” ACM SIGGRAPH Computer Graphics 21(4), 1987. doi:10.1145/37402.37406
19. van den Berg, J., Guy, S. J., Lin, M., and Manocha, D. “Reciprocal n-body collision avoidance.” Robotics Research (ISRR 2009), Springer Tracts in Advanced Robotics 70, 2011. doi:10.1007/978-3-642-19457-3_1
20. van den Berg, J., Lin, M., and Manocha, D. “Reciprocal velocity obstacles for real-time multi-agent navigation.” IEEE International Conference on Robotics and Automation, 2008. doi:10.1109/ROBOT.2008.4543489
21. Olfati-Saber, R. “Distributed Kalman filtering for sensor networks.” IEEE Conference on Decision and Control, 2007. doi:10.1109/CDC.2007.4434303
22. Rashid, T., Samvelyan, M., de Witt, C. S., Farquhar, G., Foerster, J., and Whiteson, S. “QMIX: monotonic value function factorisation for deep multi-agent reinforcement learning.” ICML, 2018. arXiv:1803.11485
23. Stone, P., and Veloso, M. “Multiagent systems: a survey from a machine learning perspective.” Autonomous Robots 8(3), 2000. doi:10.1023/A:1008942012299
24. Turpin, M., Michael, N., and Kumar, V. “CAPT: concurrent assignment and planning of trajectories for multiple robots.” International Journal of Robotics Research 33(1), 2014. doi:10.1177/0278364913515307
25. Open X-Embodiment Collaboration. “Open X-Embodiment: robotic learning datasets and RT-X models.” IEEE ICRA, 2024. arXiv:2310.08864
26. RDT Team, Tsinghua University. RDT-2, an autoregressive vision-language-action model aimed at zero-shot deployment on unseen embodiments, 2025. github.com/thu-ml/RDT2