Probabilistic and Distributed Control of a Large-Scale Swarm of Autonomous Agents

I. INTRODUCTION

• Large swarms can tackle complex formation and exploration tasks, motivating control that is distributed, versatile, robust to agent changes and uncertainty, and scalable.The paper adopts the Eulerian framework because Lagrangian trajectory generation scales poorly with agent count and does not efficiently handle agent changes or arbitrary shapes.Source: §I · p. 1

A. Literature Review

• HMC-based approaches are probabilistic and robust to agent additions or removals, but their constant Markov matrices lack feedback; PSG–IMC refines them using current swarm density.The paper also says PSG–IMC suppresses undesirable transitions and reduces control effort relative to HMC-based algorithms.Source: A. Literature Review · p. 2

B. Main Contributions

• The PSG–IMC method constructs feedback-based Markov matrices that minimize expected transition cost, obey motion constraints, and support convergence to formation or exploration distributions.The paper also presents convergence analysis and an area-exploration extension.Source: B. Main Contributions · p. 2

C. Notations; II. PRELIMINARIES AND PROBLEM STATEMENT

• The space is partitioned into bins, and the desired formation Θ is a probability vector specifying target density per bin; nonzero entries identify recurrent bins.The setup assumes many more agents than recurrent bins, anonymous and identical agents, and the ability to sense each agent’s bin.Source: §II · p. 3

II. PRELIMINARIES AND PROBLEM STATEMENT

• Motion constraints specify allowed bin transitions, while the transition-cost matrix represents control effort, fuel use, or another quantity agents seek to minimize.The setup assumes agents know the space, bins, and target formation in advance, and have cost and motion-constraint matrices available.Source: §II · p. 4

A. Distributed Estimation of the Current Swarm Distribution

• The distributed estimate assumes a strongly connected, time-varying communication network, and the algorithm is reported to work remarkably well despite residual estimation error.Distributed estimation algorithms can estimate the current swarm distribution under that assumption.Source: A. Distributed Estimation of the… · p. 4

B. Problem Statement for Shape Formation

• Each agent independently selects a motion-constrained bin trajectory toward the desired formation; the objectives also include repairing formation damage and minimizing transition cost at every time instant.The motion constraints are represented by Aj k, and transition costs by Ck.Source: B. Problem Statement for Shape Formation · p. 4

C. Outline of the PSG–IMC Algorithm

• At each iteration, an agent identifies its bin and estimates swarm distribution, escapes a transient bin if needed, then computes and modifies a Markov matrix to select its next bin.A lower-level controller moves the agent to that bin in a collision-free manner.Source: C. Outline of the PSG–IMC Algorithm · pp. 4–5, Figure 4 · p. 5

III. CONSTRUCTION OF FEEDBACK-BASED MARKOV MATRIX

• The paper presents novel techniques for constructing feedback-based Markov matrices.Source: §III · p. 5

Choice of Hellinger distance

• Equal L1 distances can correspond to different Hellinger distances, which penalize agents in bins with zero desired occupancy and distinguish errors across bins with different target weights.The Hellinger distance is symmetric and bounded by 1.Source: A. Construction of Minimum Cost Markov… · p. 5, Figure 5 · p. 5

Feedback-based construction

• Unlike Metropolis-Hastings construction for a given stationary distribution, this method directly incorporates feedback from the current swarm distribution through a feedback gain.The passage states there is no direct method for incorporating feedback into Metropolis-Hastings.Source: A. Construction of Minimum Cost Markov… · pp. 5–6

Method 1

• When the Hellinger-distance feedback gain falls below the convergence threshold, the matrix becomes the identity; otherwise, motion constraints and zero-weight target bins restrict transitions.The identity matrix prevents further transitions after convergence.Source: A. Construction of Minimum Cost Markov… · pp. 5–6

Method 1 and Theorem 1

• The optimal Markov matrix minimizes expected transition cost at each time instant, and its feasible set is nonempty with row-stochastic matrices, stationary distribution Θ, and transitions only into recurrent bins.The construction applies motion-constraint and target-bin restrictions.Source: A. Construction of Minimum Cost Markov… · p. 6

Computation time

• For ν150 and ν300, the general linear program is impractical for real-time computation, with about 5×10^8 and 8×10^9 variables, respectively.The number of variables grows approximately as n_bin^2.Source: A. Construction of Minimum Cost Markov… · p. 7

Corollary 1

• With a symmetric cost matrix, the closed-form optimal matrix lets each agent compute its row directly, and computation times for all four Figure 6 cases are under 2 minutes on a standard desktop.This construction is given in Corollary 1.Source: A. Construction of Minimum Cost Markov… · p. 7

Convergence rate

• For an inhomogeneous Markov chain, convergence rate is determined by the coefficient of ergodicity, whereas a homogeneous chain uses the second-largest eigenvalue modulus.Source: B. Construction of Fastest Mixing IMC · p. 8

Fastest-mixing construction

• To avoid a trivial coefficient value when recurrent-bin graph diameter exceeds two, the method minimizes the coefficient of ergodicity of a matrix power based on that diameter.Source: B. Construction of Fastest Mixing IMC · p. 8

Corollary 2

• The fastest-mixing matrix is constructed through a convex optimization problem subject to the linear-program constraints LP1–4.Source: B. Construction of Fastest Mixing IMC · p. 8

Trapping bins

• A trapping bin is transient and permits transitions only to other transient bins under the agent’s motion constraints.Source: C. Condition for Escaping Transient Bins · p. 8, Figure 7 · p. 8

Escaping trapping bins

• For each trapping bin, an onboard path chosen from the motion constraints deterministically exits the trapping set in finite time.The best exit from bin 5 is bin 3 in one illustrated case and bin 7 in the other.Source: C. Condition for Escaping Transient Bins · p. 8

Escaping other transient bins

• From a transient bin that is not trapping, the agent transitions with equal probability to any reachable recurrent bin, reaching one in a single time instant.Source: C. Condition for Escaping Transient Bins · pp. 8–9

• Each agent estimates the current swarm distribution and identifies its bin before computing transition probabilities for the next move.Source: §IV · p. 9
• For transient bins, agents sample their next bin from a separate transition matrix; otherwise, they compute a feedback gain and derive a Markov matrix.Source: §IV · p. 9
• A time-decaying suppression term reduces transitions out of bins deficient in agents, with its amplitude and time constant set by positive constants.The passage reports that this suppression reduces total transitions and improves convergence error.Source: §IV · p. 9
• Each agent executes the guidance steps independently and needs to communicate only with neighboring agents to move while avoiding collisions.Source: §IV · p. 9

• Each agent enters a recurrent bin within at most nbin − nrec + 1 time instants and thereafter remains among recurrent bins.Source: A. Main Result: Convergence Analysis · p. 10
• Each agent’s predicted bin-position distribution converges pointwise to the desired formation, irrespective of its initial condition.Source: A. Main Result: Convergence Analysis · p. 10
• For a finite swarm, the analysis gives a probabilistic bound on final formation error when the number of agents meets a stated lower-bound condition.Source: A. Main Result: Convergence Analysis · pp. 11–12
• As the number of agents tends to infinity, the final swarm distribution converges in probability to the desired formation.Source: A. Main Result: Convergence Analysis · p. 12
• The algorithm continues to converge after agents are added or removed and can tolerate errors in estimating the current swarm distribution.The robustness discussion states that the resulting Markov matrix retains the desired formation as its stationary distribution under estimation errors.Source: A. Main Result: Convergence Analysis · p. 12
• Multiresolution guidance selects formation resolution using feedback-gain thresholds for computational efficiency, and the framework also applies when the swarm’s local reference frame follows a predefined trajectory.Source: A. Main Result: Convergence Analysis · pp. 12–13

• The method is presented for goal searching, including matching an unknown distribution associated with a physical or artificial phenomenon.Oil spill is given as an example.Source: §V · p. 13
• Agents measure the target distribution in their current bin and use waiting times proportional to that bin’s target value before moving.Source: §V · p. 13
• The convergence result states that each agent’s predicted bin-position distribution converges pointwise to the target distribution, irrespective of initial condition.Source: §V · p. 13

• Shape-formation results are presented from numerical simulations and experiments.Source: §VI · p. 14
• Area-exploration results are presented from numerical simulations.Source: §VI · p. 14
• The section covers both shape formation and area exploration, with hardware experimentation stated for shape formation only.Source: §VI · p. 14

A. Numerical Simulations for Shape Formation with Fine Spatial Resolution

• With 300×300 bins, agents starting uniformly attain the Eiffel Tower formation in 100 time instants; at instant 251, approximately 3 × 10^4 agents are removed from its top half, and the remainder reconfigure.Figure 10 depicts the swarm attaining the 3-D Eiffel Tower shape and reconfiguring after top-half removal.Source: A. Numerical Simulations for Shape… · p. 14, Figure 10 · p. 15
• PSG–IMC provides approximately 2 times improvement in HD, 16 times reduction in cumulative transitions, and 16 times reduction in total cost versus HMC over 500 time instants.The comparison is based on cumulative results from 10 Monte Carlo simulations.Source: A. Numerical Simulations for Shape… · p. 14
• PSG–IMC avoids many undesirable transitions by making transitions proportional to HD, while HMC reaches an HD equilibrium of 0.115 after about 40 instants.After 250 instants, PSG–IMC's HD is 0.055; both approaches retain nonzero convergence error.Source: A. Numerical Simulations for Shape… · p. 14
• With 150 × 150 × 150 bins, 10^5 agents form the 3-D Eiffel Tower in a few instants and reconfigure in a few more after 1.25 × 10^4 agents are removed.The agents removed are from the top half of the formation.Source: A. Numerical Simulations for Shape… · p. 15
• A 10^6-agent swarm forms a target with multiple disconnected parts in 300 instants, despite each agent being limited to bins within 50 steps.The recurrent bins are noncontiguous but satisfy the stated property in Definition 4.Source: A. Numerical Simulations for Shape… · p. 15
• Both algorithms scale with spatial resolution and swarm size, while PSG–IMC performs better because it requires fewer transitions.Table II presents the computation-time comparison for the algorithms.Source: A. Numerical Simulations for Shape… · p. 15, Table II · p. 15

B. Numerical Simulations for Shape Formation with Coarse Spatial Resolution and Estimation Errors

• The estimation-error study uses 5,000 agents and a coarse 25 × 25-bin Eiffel Tower because PSG–OT’s linear program cannot be solved at finer resolutions.Each agent can transition only to bins at most 9 steps away.Source: B. Numerical Simulations for Shape… · p. 15
• With estimation error, PSG–IMC works reliably across the tested range and performs better than HMC and PSG–OT; PSG–OT performs worse than open-loop HMC when ϵest ≥ 0.25.PSG–OT performs slightly better than PSG–IMC only when ϵest = 0.0, a condition the authors say does not arise in practical scenarios.Source: B. Numerical Simulations for Shape… · pp. 15–16
• At ϵest = 0.25, PSG–IMC achieves smaller convergence error with fewer transitions than HMC and PSG–OT.The results are cumulative and shown in Figure 12(b).Source: Figure 12 · p. 15, B. Numerical Simulations for Shape… · p. 16
• Alternative feedback-gain functions increase the convergence rate but also increase the number of transitions.The comparison uses ϵest = 0.25.Source: B. Numerical Simulations for Shape… · p. 16

C. Experimental Results for Shape Formation to Demonstrate Real-Time Execution

• Nine experiments with three or five quadrotors achieved the desired formation within a few instants using a 9-second PSG–IMC step and a 3-second lower-level guidance step.The setup tracks quadrotor positions through Vicon cameras and executes each agent's computation in an independent desktop thread.Source: C. Experimental Results for Shape… · p. 16, Figure 14 · p. 16
• The experiments show real-time formation control that robustly adapts to measurement and actuator errors, downwash, intermittent visibility loss, and communication loss.The quadrotors track computed trajectories using an onboard nonlinear control law.Source: C. Experimental Results for Shape… · pp. 16–17
• Repeated runs from the same initial condition reach the same desired formation with significantly different trajectories, reflecting probabilistic bin selection.The repetitions include two sets of experiments with five runs each.Source: C. Experimental Results for Shape… · p. 17, Figure 15 · p. 17

D. Numerical Simulations for Area Exploration

• A swarm of 10^5 agents converges from a uniform distribution to an unknown target, then reconfigures when that target changes after 100 seconds.The simulation partitions the physical space into 100 × 100 bins with a 0.1-second time step; Figure 16 shows the sample run and cumulative results.Source: D. Numerical Simulations for Area… · p. 17, Figure 16 · p. 17
• Compared with HMC, PSG–IMC provides approximately 1.5 times improvement in HD and 6 times reduction in cumulative transitions and total cost over 200 seconds.The comparison uses cumulative results from 10 Monte Carlo simulations.Source: D. Numerical Simulations for Area… · p. 17

VII. CONCLUSION

• The algorithm constructs time-inhomogeneous Markov matrices using a Hellinger-distance-based feedback gain, minimizes expected transition cost per instant, and avoids transitions from deficient bins.The conclusion also reports a rigorous convergence analysis and describes the real-time feedback construction as, to the authors’ knowledge, the first such path-planning strategy.Source: §VII · p. 18
• The conclusion reports 6–16 times lower transition cost and 1.5–2 times lower HD than HMC for formation and area exploration; under estimation error, PSG–IMC also outperforms PSG–OT.The hardware experiments use a Voronoi-based lower-level guidance and control algorithm with multiple quadrotors.Source: §VII · p. 18
• The authors state that the algorithm can also address surveillance, task allocation, and coverage when cast as shape formation or area exploration.They frame this as a potential application of the proposed path-planning strategy.Source: §VII · p. 18

Appendix

• A nonnegative square matrix is primitive when some positive integer power of it has all positive entries.This definition is introduced among the preliminaries for the appendix proofs.Source: APPENDIX · p. 18
• Strong ergodicity means rows of the forward matrix product converge to the same limit; under the stated conditions, asymptotic homogeneity is necessary and sufficient for it.The conditions include primitivity and a uniform bound involving the minimum positive matrix entries.Source: APPENDIX · p. 18
• With irreducible matrices and condition (34), asymptotic homogeneity is equivalent to convergence of the stationary distributions, and strong ergodicity gives the same limit vector.The limiting stationary vector equals the vector d defining asymptotic homogeneity.Source: APPENDIX · p. 18
• The appendix establishes that U^j_{k,k+nrec−1} is positive, proving it by contradiction using irreducibility of the submatrix.The proof rules out a zero entry by tracing the implied zero transitions back to a contradiction with irreducibility.Source: APPENDIX · p. 18
• The PSG–OT formulation modifies transition costs to penalize motion-constraint violations, then finds an optimal transference plan with a linear program.The resulting Γ^j_k depends directly on current-distribution feedback and is sensitive to estimation errors.Source: APPENDIX · pp. 18–19
• Agents recursively combine local swarm-distribution estimates with neighbors; when A_k is balanced, estimates converge globally exponentially to μ⋆_k.The stated convergence rate is at least as fast as the second-largest singular value of A_k.Source: APPENDIX · p. 19
• Inverse transform sampling selects a bin by drawing a uniform random number and locating it in the cumulative distribution of the bin probabilities.The selected bin is where the cumulative probability first reaches or exceeds the draw.Source: APPENDIX · p. 19
• For collision-free motion, agents moving bins target the nearest point in their Voronoi partition while agents staying put target the centroid of its overlap with their bin.The partitions account for neighboring agents and nearby stationary obstacles; Figure 17 illustrates a six-agent, two-bin case.Source: APPENDIX · p. 19, Figure 17 · p. 19