Coordination Benchmarks

CoordinationBenchmarks

Head-to-head benchmarking of the two ways to drive a fleet onto the harmonic extension of a pinned cellular sheaf.

Both laws share a fixed point, the harmonic extension $q^\star$, but they are different dynamical systems, and this module measures what that costs.

Diffusion, the decentralized law of Heterogeneous Multi-Agent Multi-Target Tracking using Cellular Sheaves (arXiv:2512.24886, eq. 4–5), feeds the sheaf disagreement back directly:

\[u = -k\, g^{+} \eta, \qquad \eta = \mathcal{H} q - B p .\]

Direct solves the harmonic extension first and then tracks the delivered reference locally:

\[u = -k\, g^{+} (q - q^\star), \qquad q^\star = \mathcal{H}^{-1} B p .\]

Substituting each into the tracking error gives $\dot e_{\mathrm{Diffusion}} = -k\mathcal{H}e$ against $\dot e_{\mathrm{Direct}} = -k e$: Diffusion inherits the sheaf spectrum, Direct does not.

Every numerical kernel here is an existing CellularSheaves entry point , restricted_laplacian_blocks for the blocks, harmonic_extension as the correctness oracle, and the DistributedSolve cached tree solve as the hot path.

See benchmark_coordination for the top-level entry point.

Named stages of the Diffusion law, in execution order.

One-time setup stages of the Direct law.

Repeated stages of the Direct law.

CoordinationBenchmark

Result of benchmark_coordination: one row per scenario, each holding the scenario, its spectrum, and both laws' SettlingResult.

Plot it with plot(result, :settling), see plot_coordination for the available metrics.

A recorded closed-loop rollout against moving targets, for visualisation.

CoordinationScenario

A pinned tracking problem: an agent graph, a set of sensed targets, and the sheaf Laplacian blocks both control laws are built from.

H and Bmat follow the tracking paper's convention, so that η = H*q - Bmat*p and q* = H \ (Bmat*p).

Construct with coordination_scenario.

Fields

• name, label: identifier and display name.
• dim: stalk dimension (agents live in R^dim).
• nagents, ntargets: fleet and target counts.
• agent_graph: inter-agent communication graph.
• sensing: for each target, the agents that sense it.
• sheaf: the underlying EuclideanSheaf.
• H, Bmat: the free–free and free–pinned Laplacian blocks.

DirectPlan

Everything Direct computes once per sheaf: the symbolic analysis, the numeric factorization of $\mathcal{H}$, and a preallocated solve workspace.

Target motion changes only the right-hand side, so this is built once and reused for every subsequent solve. Construct with direct_plan.

SettlingResult

What one control law spent to bring the fleet onto the harmonic formation.

Fields

• method: :diffusion or :direct.
• gain: the gain actually deployed.
• ticks: control steps taken to reach the tolerance.
• converged: whether the tolerance was met.
• seconds: total compute, including any one-time setup.
• slots: total half-duplex communication slots.
• peak_command: largest speed commanded to any agent at any tick.
• path_length: integral of that commanded speed.
• error_history: formation RMS error per tick.

Ticks and seconds measure computation, not whether a vehicle could fly the result. Each law runs at its own discrete stability ceiling, and Direct's ceiling is kappa times higher, so it is free to command a more aggressive transient. peak_command is what a saturating actuator would clip and is the honest counterweight to the tick counts.

Per-stage cost of one control law over a fixed number of ticks.

A path spine with one pendant leaf per spine vertex: treewidth 1, but a very different degree profile from a chain or a star.

Formation RMS error, computed without allocating a temporary.

Critical path of a combining reduce on a rooted forest, sibling-serialized.

Static target positions, spread so the formation has somewhere to go.

agent_groups(scenario) -> Vector{Int}

Assign each agent to the target group it escorts, for colouring figures.

animate_coordination(result; kwargs...)

Reserved for animated coordination rollouts; implemented in the CellularSheavesPlots package extension.

benchmark_coordination(; family, tolerance, dt, safety, verify) -> CoordinationBenchmark

Run both control laws to the harmonic formation across a family of topologies and collect the cost of each.

family defaults to scenario_family. When verify is true (the default) each scenario's cached solve is checked against the library's canonical harmonic_extension before timing.

Example

result = benchmark_coordination()
plot(result, :settling)

coordination_scenario(name; size_parameter = 0, dim = 2, coverage = :sparse)

Build a CoordinationScenario from a named topology family.

name is one of :tworing, :chain, :ring, :grid, :rgg, :star, :twoclique, or :expander. size_parameter sets the family's size (side length for :grid, clique size for :twoclique, vertex count otherwise).

coverage controls how many agents sense a target, which is what sets $\lambda_{\min}$ and therefore how hard the problem is for Diffusion:

• :sparse (default) pins two agents at the extremes of the formation.
• :full gives every agent its own target edge, the best case for Diffusion.

Examples

prob = coordination_scenario(:chain; size_parameter = 32)
prob = coordination_scenario(:expander; size_parameter = 128, coverage = :full)

diffusion_control!(u, eta, k) -> u

Diffusion's input $u = -k g^{+}\eta$ (identity $g^{+}$ for the single-integrator plants used here).

diffusion_residual!(eta, scenario, q, p) -> eta

Diffusion's disagreement $\eta_i$ (the paper's eq. 3), accumulated the way an agent actually would: a sum over its own graph neighbours and sensed targets, touching no global state.

diffusion_round_slots(scenario) -> Int

Diffusion's communication cost for one control tick: a single edge-coloured neighbourhood exchange, $\Delta$ slots. Target sensing is onboard and charged to neither method.

direct_control!(u, q, qstar, k) -> u

Direct's input $u = -k g^{+}(q - q^\star)$, tracking the delivered reference.

direct_plan(scenario) -> DirectPlan

Run Direct's one-time setup and record what it cost.

harmonic_reference!(qstar, plan, p) -> qstar

Solve $\mathcal{H} q^\star = B p$ for the current target positions, reusing the cached factorization: form the right-hand side, permute, forward- and backward-substitute over the clique tree, un-permute.

harmonic_reference(plan, p) -> Vector

Allocating form of harmonic_reference!.

harmonic_reference_oracle(scenario, p) -> Vector

The same reference computed through the library's canonical harmonic_extension, used to verify the cached path.

plot_coordination(result; metrics = (:settling, :communication), kwargs...)

Multi-panel summary of a CoordinationBenchmark.

Requires Plots to be loaded (the recipe lives in the CellularSheavesPlots package extension). Individual panels are also available directly:

plot(result, :settling)       # ticks to reach the formation, against kappa
plot(result, :compute)        # total compute for both laws
plot(result, :communication)  # total half-duplex slots for both laws
plot(result, :speedup)        # Direct advantage in both currencies
plot(result, :spectrum)       # lambda_min / lambda_max decomposition

A SettlingResult plots directly as its own error transient.

rollout_coordination(method, scenario; dt, period, horizon, mode, epsilon, ...)

Fly the fleet against moving targets under one control law, recording the trajectory.

epsilon applies a first-order command lag eps*vdot = -v + u identically to both laws; with epsilon = 0 neither is filtered. It must never be applied to one law and not the other, which is why it is a rollout parameter rather than a property of either controller.

scenario_family()

The topology families and sizes swept by benchmark_coordination. Returns a vector of (name, sizes) pairs.

A short family list for quick runs, one representative size each.

settle_to_formation(method, scenario; tolerance, dt, safety) -> SettlingResult

Cost for one law to actually reach the harmonic formation, from a displaced initial state with the targets held fixed.

This is the metric the two laws should be compared on. Per-tick cost alone misleads: Diffusion's tick is cheap precisely because it does not solve anything, so it needs $O(\kappa)$ of them, while Direct is at $q^\star$ after one solve. Only the total answers "what did coordination cost".

Each law runs at safety times its own stable_gain_ceiling, which is the fastest a deployment could actually drive it.

spectral_summary(scenario) -> (; minimum, maximum, condition)

Extreme eigenvalues and condition number of $\mathcal{H}$.

$\lambda_{\min}$ is set by how much of the fleet senses a target (the Dirichlet boundary), $\lambda_{\max}$ by graph degree. Their ratio is what governs Diffusion's settling time.

stable_gain_ceiling(method, scenario, dt) -> Float64

Largest gain a zero-order-hold implementation can deploy before the discrete closed loop diverges.

Diffusion's fastest mode decays at $k\lambda_{\max}(\mathcal H)$, limiting it to $2/(\Delta t\,\lambda_{\max})$; Direct's every mode decays at $k$, giving $2/\Delta t$. This gap is a real cost of Diffusion's H-weighted feedback, and it bounds every gain used in this module.

step_profile(method, scenario; ticks, dt, safety, reps, solves) -> StepProfile

Time each named stage of one control law in isolation, minimum-of-reps, then scale by how often the mission calls it. This attributes cost to stages; for the end-to-end number that decides the comparison use settle_to_formation.

target_trajectory(scenario, t; period, mode, horizon)

Target positions under one of three task modes: :static (formation assembly), :orbit (steady tracking), :maneuver (targets jump to new stations half-way through, a step in the reference). Deterministic in t, so both laws see identical boundary data at identical times.

tracking_bandwidth(method, scenario; dt, safety) -> Float64

Closed-loop bandwidth against a moving reference. Diffusion's slowest mode responds at k*lambda_min; Direct's at k. Targets slower than this are the quasi-static regime, where both laws track tightly.

tree_makespan(plan) -> Int

Direct's communication cost for one solve, in half-duplex slots: one gather up the elimination tree and one scatter back down.

Charged under the same slot model as the Distributed Sheaf Solve guide, one packet per node per slot, cost is the makespan of a greedy earliest-ready schedule.

tree_statistics(plan) -> (; bag_width, treewidth, fill, offdiagonal_fill, depth, supernodes)

Combinatorial structure of the elimination tree, which is what sets Direct's cost.

bag_width is the widest frontal matrix in degrees of freedom; treewidth is that converted back to vertices (bag_width ÷ stalk - 1), an upper bound on the graph's true treewidth under this ordering. fill is the total number of stored factor entries, diagonal blocks included; offdiagonal_fill counts only the off-diagonal blocks.

This is a combinatorial quantity, independent of the spectral quantity κ that governs Diffusion, the two are set by different properties of the formation and neither predicts the other.