Nested Systems: Sheaf Tower Compiler

NestedSystems

Nested system specification and sheaf tower compiler (see docs/issues/007-nested-layered-systems-design.md and docs/issues/009-nested-spec-and-tower-compiler.md).

A nested specification is a tree of teams (raw agents in a rigid formation, see build_escort_topology) and refined subsystems, together with a set of top-level targets and an arbitrary many-to-many observation incidence between systems and targets.

build_sheaf_tower compiles this specification into a tower of cellular sheaves

H₀  (coarsest)
 ↑ f₁
H₁
 ↑ f₂
 ⋮
H_N (finest — raw agents and targets)

connected by graph homomorphisms f_k, each level the pushforward_sheaf of the one below it. Because every homomorphism maps each target vertex to its own vertex at the coarser level (targets are singleton fibres at every level — see the module docstring's parent design doc, §4.2), a target's stalk stays D-dimensional and its fibre-section basis stays the identity all the way to H₀. This is what lets the eventual harmonic-extension solve (Issue 010) pin targets directly, with no pseudo-inverse anywhere in this module.

AbstractSystemNode

Common supertype of the nested-system tree nodes: LeafTeam (raw agents) and RefinedSystem (a subsystem whose members are themselves systems).

AgentBinding(; dynamics=nothing, K_lqr=nothing, initial_position=nothing)

Per-agent dynamics override. Any field left nothing falls back to the enclosing team's binding, then to successively more distant ancestors — see resolve_dynamics. Fields resolve independently: an agent may override only its initial position while inheriting its dynamics model from an ancestor.

Centroid()

Backing type for centroid.

LeafTeam(name, kind, n_agents, radius; observers=[1])

A team of raw agents in a kind formation (see build_escort_topology). Leaves are where actual agents live; every other node in the tree is structural.

kind is one of :ring, :path, :star, :clique. observers names which of the team's own agents (local indices 1:n_agents) are used to fix the team's internal geometry; it is independent of which target(s) the team observes — that incidence is declared separately via Observation.

NestedEscortProblem(tower, bindings, target_trajectories; target_velocities=nothing,
                    target_accelerations=nothing, dt=0.05, steps=200)

A closed-loop tracking problem over a SheafTower: tower supplies the topology and per-timestep solve_hierarchical reference solve, bindings resolves per-agent dynamics/gain/initial state via resolve_dynamics, and target_trajectories[t] is a function time -> Vector{Float64} giving target t's D-dimensional world position. target_velocities/target_accelerations, if supplied, enable feedforward tracking (see run_nested_escort_simulation).

Mirrors Layered.LayeredEscortProblem structurally, built on NestedSystems's tree-shaped primitives instead of LayeredEscortSpec's flat ones.

NestedEscortResult

Output of run_nested_escort_simulation. sim_data[step][agent] is the agent's raw dynamics state (length state_dim(dyn)); qstar_history[step][agent] is the D-dimensional hierarchical reference the agent was tracking that step (tower.agent_vertices order); target_history[step][target] is the target's D-dimensional world position that step.

NestedSystemSpec(root, targets, observations, D, affine)

Full specification for a nested layered-control system: a tree of teams and subsystems (root), a set of top-level TargetSpecs, the Observation incidence between systems and targets, the stalk dimension D, and whether restriction maps are affine (see build_escort_topology).

Observation(system_path, target_index; system_map=project(1))

Declares that the system at system_path (a path of child indices from the root) observes target target_index. Arbitrary many-to-many incidence is allowed: one system may observe several targets and one target may be observed by several systems.

system_map declares what the observing system presents on this edge (see RestrictionSpec); the target end is always the identity, since a target is a single D-dimensional vertex at every level. The default project(1) reproduces the pre-Issue-011 behaviour of wiring the system's first agent to the target.

ProjectMember(member)

Backing type for project. member is a direct-member index, or a Symbol naming a child of a RefinedSystem.

RawRestriction(M::Matrix{Float64})

Escape hatch: present an arbitrary declared matrix. M must be D × (n_members · D), checked when it is materialized against a specific node.

RefinedSystem(name, children, internal_edges=SystemEdge[])

A subsystem whose vertices are themselves systems. internal_edges are consensus edges among children: either SystemEdges, or bare (i, j) index pairs, which are promoted to SystemEdges with the default project(1) maps on both ends.

ResolvedAgent

A fully-bound leaf agent: its global agent index (matching SheafTower's agent_vertices), its dotted path in the tree (for error messages and debugging), and the dynamics, gain, and initial position that won the inheritance cascade.

RestrictionSpec

Declarative description of the restriction map on one end of an edge: what a subsystem presents to whatever it is wired to.

Declaration is symbolic; lowering is numeric. A RestrictionSpec is declared against the subsystem's raw joint state — the plain concatenation of its direct members' values, of dimension n_members × D. That dimension follows from declared arities alone, with no rank or nullspace computation anywhere, which is what lets validation stay numeric-free. Only at tower assembly is the declared map composed with the fibre-section basis discovered by the pushforward:

R_coarse = R · B_v        (D × total) · (total × k)  =  D × k

EuclideanSheaf permits non-square restriction maps, so R_coarse needs no special handling.

A node's direct members are its children if it is a RefinedSystem, or its raw agents if it is a LeafTeam. Refinement is opaque: a refined child counts as exactly one member no matter how many agents it eventually expands to.

Concrete specs: project, centroid, and RawRestriction.

SheafTower

Compiled tower of sheaves. levels[1] is the coarsest sheaf H₀; levels[end] is the finest H_N containing one vertex per raw agent plus one per target. homs[k] : levels[k+1] → levels[k], and bases[k][v] is the fibre-section basis over vertex v of levels[k], used to lift a value at v down into levels[k+1].

Targets occupy vertices 1:length(spec.targets) at every level (including H_N), so target_vertices[t] is target t's vertex index and is valid at every level — this is what makes the singleton-fibre invariant checkable and usable uniformly across the tower. agent_vertices[a] is agent a's vertex index in levels[end].

Fibre bases (bases) are computed once during compilation and cached here; they are never recomputed by downstream consumers (e.g. the Issue 010 solver).

SystemBinding(; dynamics=nothing, K_lqr=nothing, children=Dict(), agents=Dict())

Dynamics bindings for one node of the system tree, mirroring the structure of the NestedSystemSpec it is resolved against.

dynamics/K_lqr apply to every leaf agent in this subtree unless a descendant overrides them. children maps a child system's name to its own SystemBinding. agents maps a local agent index within a LeafTeam to an AgentBinding.

Child names and agent indices are validated against the spec during resolve_dynamics: a name or index present here but absent from the spec is an error, so a typo surfaces immediately rather than as a silently-unbound agent.

SystemEdge(src, dst; src_map=project(1), dst_map=project(1))

A consensus edge between two children of a RefinedSystem, given as index pairs into children. src_map and dst_map declare what each endpoint presents on this edge (see RestrictionSpec); a subsystem may present something different on each of its edges.

The defaults reproduce the plain (i, j) behaviour exactly, which is why an internal_edges list of bare tuples is still accepted.

TargetSpec(name)

An uncontrolled agent supplying a boundary condition at solve time. Targets are top-level vertices and are never owned by a team.

_DeferredEdge

An edge that could not be expressed in H_N because at least one endpoint presents an aggregate of several vertices. It is added at level, the finest level at which both endpoints are single vertices. u_node/v_node are nothing for a target endpoint (targets are single vertices everywhere and always present the identity).

_add_leafteam_edges!(F, leaf, D, affine, vertex_offset)

Build leaf's formation via build_escort_topology and transplant its consensus edges (agent-to-agent) into F at vertex_offset, mirroring Layered.jl's ring transplant. build_escort_topology also generates edges pinning leaf.observers to a synthetic local target vertex (n_agents + 1); those are dropped here rather than transplanted, because a LeafTeam has no target of its own in the nested architecture — teams are pinned to real targets only via Observation edges. The consensus edges alone already give the team an exact D-dimensional global-section space for any connected kind (see build_escort_topology's docstring), so dropping the synthetic pin does not affect rigidity.

_assign_agent_ranges!(node, next_idx, agent_range, agent_owner)

Depth-first walk assigning consecutive H_N vertex indices to every raw agent. next_idx is a running Ref{Int} counter (already offset past the target block). Records each node's (contiguous) vertex range in agent_range, and appends each raw agent's owning LeafTeam to agent_owner in visitation order.

_atomic_level(node, S, depth) -> Int

The finest tower level at which node is a single vertex. Below it, node has been split into its direct members — which is precisely the level whose fibre basis an aggregate restriction map must compose with.

_boundary_dict(tower, target_values) -> Dict{Int,Vector{Float64}}

Map each target's vertex index to its pinned value, checking arity and stalk dimension. Targets share the same vertex index at every level of the tower, so the resulting dictionary is a valid boundary condition for tower.levels[1] and tower.levels[end] alike.

_build_parent_map!(node::RefinedSystem, parent_of)

Populate parent_of[c] = node for every child c of node, recursively. Root's direct children get an entry too (pointing at the root), but it is never dereferenced: every root child is guaranteed collapsed (a singleton slot) by H₀, so climbing (see _owner_slot_index) never needs to pass through it.

_collapse_depth(node) -> Int

Number of pushforward steps needed for node's subtree to collapse into a single vertex, counting from the finest level H_N (where _collapse_depth(::LeafTeam) == 1, since raw agents always collapse into their team's centre in one step). A RefinedSystem must wait for its slowest child before it, too, can collapse: 1 + maximum(_collapse_depth, children). Memoized in S (keyed by node identity, since two structurally-equal LeafTeams are still distinct tree nodes).

_direct_member_names(node) -> Union{Vector{Symbol},Nothing}

Names of node's direct members, or nothing when they are unnamed (a LeafTeam's raw agents are addressed by index only).

_fine_representative(node, r, agent_range) -> Union{Int,Nothing}

The single H_N vertex that r designates on node, or nothing when r designates no single vertex.

Only project has a representative, and finding it is recursive: selecting a member of a refined system leaves another system, whose own representative is its first member, and so on down to a raw agent. Selecting a member of a LeafTeam lands on that agent directly.

An aggregate map such as centroid returns nothing: it is a functional of several vertices at once and cannot be an edge endpoint in H_N, where those vertices are still separate. Such an edge is placed at the coarsest level where its endpoints are single vertices — see build_sheaf_tower.

_fold(inherited::AgentBinding, local_::AgentBinding) -> AgentBinding

Overlay local_ on inherited, field by field: a non-nothing local field replaces the inherited one, a nothing field leaves the inherited value intact. This independence — not replacing the whole binding wholesale — is what lets an agent override just its initial position while still inheriting its dynamics model.

_level_owner_slots(node::RefinedSystem, level, depth, S) -> Vector{AbstractSystemNode}

Ordered list of the nodes that are represented as their own single vertex ("atomic") at tower level level (coarser levels are smaller level), obtained by recursing into any child that has not yet collapsed (S[child] > depth - level). Used to build the vertex set of every pushforward level below H_N.

_member_index(node, member) -> Int

Resolve a direct-member designator to an index, checking it against node's arity. A Symbol resolves against child names and throws a message naming the available children if unmatched.

_n_direct_members(node) -> Int

Number of direct members: children for a RefinedSystem, raw agents for a LeafTeam.

_owner_slot_index(node, pos_dict, parent_of) -> Int

Climb from node up through parent_of until reaching a node present in pos_dict (i.e. one that is atomic at the target level), and return its position. Every node is guaranteed to find such an ancestor-or-self without ever climbing past a root child (see _build_parent_map!).

_per_vertex(F::EuclideanSheaf, x::AbstractVector) -> Vector{Vector{Float64}}

Split a flat cochain x on F into one value per vertex, using each vertex's own stalk dimension (stalks are not uniform above H_N).

_resolve_path(root::RefinedSystem, path::Vector{Int}) -> AbstractSystemNode

Walk path (a sequence of child indices) from root, returning the node it addresses. Throws an ArgumentError if the path is malformed (out-of-range index, or it tries to descend into a LeafTeam, which has no children).

_wire_declared_edges!(F, spec, agent_range, S, depth) -> Vector{_DeferredEdge}

Add every declared consensus and observation edge that can live in H_N, and return the ones that cannot.

An edge lands in H_N exactly when both endpoints resolve to a single vertex there — which is the case for project-wired edges, and so for every spec written before per-edge maps existed. Keeping those edges at the finest level is what preserves the earlier behaviour and, more importantly, what keeps solve_direct's baseline meaningful: a target pinned through an H_N edge still constrains individual agents when the tower's rigidity is relaxed.

agent_index_ranges(team_sizes::Vector{Int}) -> Vector{UnitRange{Int}}

Contiguous index ranges into a SheafTower's agent_vertices for a sequence of leaf teams of the given sizes, in the order those teams were added as children. Agent indices are assigned depth-first over the spec's tree (see _assign_agent_ranges!), so each leaf team occupies a contiguous block in visitation order — this reconstructs those blocks from the team sizes alone, without reaching into the tower's private bookkeeping.

approximation_gap(tower::SheafTower, target_values)
    -> (; hierarchical, direct, gap, relative_gap)

Energy of both solutions measured on the finest sheaf, and their difference.

gap is guaranteed nonnegative up to floating-point tolerance, and this is a theorem rather than an empirical observation. The hierarchical solution satisfies every constraint the direct problem imposes plus the extra requirement that each team lie exactly on its space of global sections; it is therefore a feasible point of the direct problem, and a feasible point can never beat the optimum. Equality holds exactly when the direct optimum was already fibrewise-exact — rigid teams pinned to a single target are the equality case. A positive gap quantifies what insisting on rigid formations costs: it is the energy the direct solve recovers by letting teams deform.

relative_gap is gap / direct, or 0.0 when both energies vanish.

build_sheaf_tower(spec::NestedSystemSpec) -> SheafTower

Compile a nested specification into a tower of sheaves connected by pushforwards.

Algorithm: flatten the tree to the finest level H_N (targets at vertices 1:n_targets, raw agents consecutively after, per team and per subsystem — see _assign_agent_ranges!), then repeatedly pushforward_sheaf up the tower. At each step, every node whose entire subtree has already collapsed becomes a single coarse vertex; targets always map to themselves (singleton fibres, identity basis), which is asserted after every pushforward and fails loudly if violated — this is the invariant the whole hierarchical architecture rests on (see the module docstring). A fibre whose section space collapses to dimension 0 means the corresponding team or subsystem is over-constrained and the tower cannot represent it; this is also rejected.

centroid() -> RestrictionSpec

Present the unweighted average of the subsystem's direct members, (1/N) Σ.

Unlike project, a centroid is a functional of several members at once, so it has no representative vertex in H_N; it exists only at the level of abstraction where the subsystem is a single vertex. See build_sheaf_tower for what that implies.

homogeneous_binding(dyn; K_lqr=zeros(0,0)) -> SystemBinding

Shorthand for a root-level binding applying dyn/K_lqr to every agent in the tree — the common case, and the degenerate case that reproduces the old flat HomogeneousDynamics.

materialize_restriction(r::RestrictionSpec, node::AbstractSystemNode, D::Int) -> Matrix{Float64}

Build the D × (n_members · D) matrix for r against node's raw joint state.

Purely structural: it depends only on node's declared arity, never on a rank, nullspace, or pseudo-inverse computation. Composition with the fibre basis — the only numeric step — happens later, at tower assembly.

n_agents(spec::NestedSystemSpec) -> Int
n_agents(node::AbstractSystemNode) -> Int

Total number of raw agents in spec's tree (or in node's subtree).

project(i::Int) -> RestrictionSpec
project(name::Symbol) -> RestrictionSpec

Present direct member i's own block unchanged (or the child named name). The materialized matrix is the selection matrix [0 … I_D … 0].

This is the default on every edge, and it is the one spec that lowers all the way to a single finest-level vertex — selecting a member, then that member's first member, and so on — so a project-wired tower places its edges on raw agents in H_N exactly as it did before per-edge maps existed.

redundant_pin(n_members::Int, D::Int, k::Int) -> RestrictionSpec

project(1) for the first (k == 1) pin, translation_pin for every pin after that — the system-map to use for member k of a 1:2:n_members-style redundant-pin scheme that lets several agents jointly vote on tracking one target without corrupting the homogeneous coordinate.

resolve_dynamics(spec::NestedSystemSpec, ctx::SystemBinding) -> Vector{ResolvedAgent}

Walk spec's tree carrying the inherited binding, overriding it wherever ctx supplies a more specific value, and return one ResolvedAgent per leaf agent in global agent-index order (matching SheafTower's agent_vertices).

Precedence, most specific first: per-agent, leaf team, nearer ancestor, root default. Each field resolves independently.

Throws if any agent ends with no dynamics bound anywhere up its chain, or if ctx names a child or agent index that does not exist in spec — both errors report the full dotted path.

run_nested_escort_simulation(prob::NestedEscortProblem; use_feedforward::Bool=false) -> NestedEscortResult

Run a closed-loop simulation over prob.tower's spec: at each step, solve the tower hierarchically for the current target positions, lift the result to per-agent references, and step each agent's AgentState toward that reference.

use_feedforward toggles two things, exactly as in Layered.run_layered_escort_simulation: whether AgentState uses a joint (position+velocity) Tikhonov filter, and whether velocity/ acceleration references are additionally solved for (via the same hierarchical machinery, on prob.target_velocities/prob.target_accelerations) and passed to step_agent! for differential-flatness feedforward.

sheaf_energy(F::EuclideanSheaf, x::AbstractVector) -> Float64

Dirichlet energy ‖δx‖² of a flat cochain x on F, where δ is the coboundary_map. This is the quantity both solves minimise, and the common yardstick that makes them comparable.

solve_direct(tower::SheafTower, target_values) -> Vector{Vector{Float64}}

Baseline: harmonic extension on the fully expanded finest sheaf tower.levels[end], pinning the same targets that solve_hierarchical pins. Every agent moves independently, so teams may deform — the internal formation edges are penalised, not enforced.

Returns per-vertex values on the finest level. This is the unconstrained optimum against which the hierarchical solution is measured; see approximation_gap.

solve_hierarchical(tower::SheafTower, target_values) -> Vector{Vector{Vector{Float64}}}

Solve the tower top-down: one harmonic extension on the coarsest sheaf tower.levels[1] with target_values pinned at the target vertices, then successive fibre-basis lifts down to each finer level.

Because every fibre basis B_v spans the fibre's exact global-section space, each lift is energy-preserving: the internal edges of a fibre contribute exactly zero, and the cross-edge energy of the coarse sheaf equals that of the lifted cochain on the finer one. The coarse solve therefore genuinely minimises finest-level energy — but only over configurations in which every team stays rigidly in formation. See approximation_gap for what that restriction costs.

Returns one cochain per level, coarsest first, each as a vector of per-vertex values (per-vertex, because stalk dimensions differ between vertices above the finest level). The last entry holds the per-agent and per-target reference states on tower.levels[end].

translation_pin(n_members::Int, D::Int, k::Int) -> RawRestriction

A restriction map pinning direct member k's translation components (the first D-1 coordinates) to a target, deliberately leaving the homogeneous row (D) unconstrained.

Meant for every redundant pin beyond the first when several agents around a rigid team each observe the same target (see redundant_pin). project materializes as a full D×D identity block, homogeneous row included; a single such pin is fine (it unambiguously forces that row to 1), but several pins to the same target are mutually inconsistent for a rigid body by construction — that inconsistency is the point, it rebalances the team's "vote" against competing edges elsewhere in a tower. Left unmodified, the least-squares compromise that inconsistency produces doesn't stay confined to translation: it drags the homogeneous row away from 1 too, which — because these affine restriction maps only represent pure translation correctly when that row is exactly 1 — rescales the entire rigid body's geometry. translation_pin avoids this by never contesting anything but translation, leaving only the first, unmodified project(1) pin responsible for anchoring the homogeneous row.

This is the mechanism translation_pin exists to suppress; leaving pins full and untruncated on purpose is a legitimate, different construction — see the "emergent rescaling" literate example (docs/literate/nested/rescaling_formation.jl), where several agents are each pinned to a different target and the resulting homogeneous-coordinate drift is used deliberately to let a rigid team absorb divergent targets by uniform rescaling rather than shearing.