Zymera — connectivity-aware cooperative exploration

1Overview

A single robot exploring a building is a solved problem in outline: drive toward the nearest unseen boundary, repeat. A team is a different question — the behavior that matters is not in any one machine, but in how their local choices compose into a group outcome.

Two forces pull against each other. Coverage wants the agents to spread out, so the unseen area shrinks fastest. Communication wants them to stay close, because radios reach only so far and a map is worthless if the piece an agent holds never reaches the others. A decentralized team, each agent acting on a keyhole view of the world, has to hold both at once — managing its own connectivity as a resource it spends and recovers while it works.

Zymera studies that tension: how a team covers a world under limited, range-based communication, how the same agents transfer from a small team on a small map to a large team on a large one, and how a fully learned policy can plan far enough ahead to generalize to maps it has never seen.

2Framework

We describe the team on three levels, coupled by the communication network. The mission is a finite-horizon cooperative Dec-POMDP; the network touches it twice — it shapes what each agent sees, and it shapes how local actions compose into the next state.

Macro	The mission — a cooperative objective scored at the team level. Success is more than accumulated reward: a team can gain reward while its capacity to continue — its connectivity, its coverage rate — quietly erodes.
Bridge	The communication graph — a limited-range, time-varying network. Neighbors exchange a shared belief and each agent fuses what it receives. This is the layer that turns a set of individuals into a team.
Micro	The agent — a local observation, a running belief, and a policy. It can only act on what it and its neighbors currently know.

Because return alone is insufficient, the framework also tracks a diagnostic mission health — the algebraic connectivity of the graph, information quality, task progress — and reads outcomes as readiness, degradation, or failure rather than a single score.

connectivity = λ₂( L(G_t) ) > 0 ⟺ the team is one connected graph · coverage = covered free cells / free cells at t = H

The complete model — the formalism, its definitions, and the resilience measures built on it — is written up separately. Read the formalism →

3Environment

Every mission runs on one substrate — deliberately small and honest, so a result is about the team and not a generous setup. The environment is where the framework's bridge becomes concrete.

The world	N agents on an H×W grid with walls and obstacles; discrete moves; a fixed horizon of 100 steps.
The view	Partial observability — each agent sees a small local window, never the whole map. It builds its picture of the world over time and from its neighbors.
The bridge	A range-limited, time-varying comm graph. Neighbors gossip a shared occupancy belief over a size-invariant graph network, so the same policy runs on a team of 4 or 10.

How a mission is modeled into the world

A mission is defined by three choices on this one substrate: what the agents share, what the reward reads, and what connected is required to mean.

Coverage	Reward is the fraction of free cells visited by the horizon, subject to the graph's connectivity staying positive — cover fast, don't fragment.
Relay	Reward is keeping a moving lead agent connected back to a base; connectivity becomes redundant — measured by disjoint paths — so a single link failing is not enough to break it.
Delivery	Coverage counts only once it is communicated home over a graph that cannot be held continuously; the spread-then-regroup rhythm has to emerge from the objective.

The environment is a reusable simulator, kept independent of any particular learning pipeline. See the code →

4Missions

A mission is a team-level objective that emerges from agents acting on local information. Missions group by what the team produces:

Sense

A shared picture

Reduce team-level uncertainty — coverage, mapping, search, monitoring.

Organize

A relational state

Produce the team's own structure — a comm backbone, a formation, a consensus.

Act

An effect on the world

Divided work under shared limits — energy, capacity, safety.

Real deployments are composites. Zymera's target is the Sense × Organize seam — cooperative-mapping-shaped, where a maintained communication graph is exactly what lets local maps fuse into one shared picture (the family of the NASA Starling and CADRE missions). The concrete instances we build:

Connectivity-aware coverage — cover the world while the team stays one connected graph. The built substrate.
Tether-relay — a relay chain keeps a moving lead connected through a communication-denied maze.
Intermittent delivery — relays carry the map between moving endpoints over a graph that cannot be held.
Cornering & patrol — reward shapes that make every agent pivotal, so the labor has to divide.

5Results

Much of the work is honest negative results — each closed door narrows where the real difficulty lives.

reactive one-step policy stalling at walls — **Figure 1 — The navigation bottleneck, and its fix.** A single team of agents on the same rooms map. *Left:* a reactive one-step policy repeatedly stalls and backtracks at walls — it cannot see far enough to commit to a route. *Right:* a fully-learned value-iteration planner, distilled from a shortest-path teacher, routes around the known walls to the nearest unexplored frontier. Replacing the one-step head with this planner is what lets navigation generalize to maps the policy was never trained on.

distilled planner routing around walls — **Figure 1 — The navigation bottleneck, and its fix.** A single team of agents on the same rooms map. *Left:* a reactive one-step policy repeatedly stalls and backtracks at walls — it cannot see far enough to commit to a route. *Right:* a fully-learned value-iteration planner, distilled from a shortest-path teacher, routes around the known walls to the nearest unexplored frontier. Replacing the one-step head with this planner is what lets navigation generalize to maps the policy was never trained on.

Roles help — at small scale: An explorer/relay split reaches ≈ 90.9% coverage on a 16×16 world with 4 agents. But the win does not transfer up the ladder.
Connectivity, settled: At scale the team holds its graph together only by huddling into a dense clump — and the clump already satisfies every per-step connectivity signal, so penalties and constraints cannot push it apart.
The real ceiling: A fixed-specification re-run of the whole idea-space pinned the failure on the one-step reactive move head, not on communication.
The planner works, and is proven: The distilled planner recovers the exact shortest-path wavefront — 98–99.6% passability recovery on unseen maps — so it is optimal by construction, not by luck.
A connectivity tax: The coverage left on the table on walled maps is the price of staying connected, not weak planning. The remaining headroom is team coordination, not navigation.

6Figures

Zero-shot rollouts — frozen policies dropped onto worlds they were never trained on. Each shows one full 100-step episode.

ten agents covering a 32x32 world — **Figure 2 — Coverage at scale.** Ten agents cover a 32×32 world in 100 steps while holding a single connected communication graph throughout. The policy was trained on smaller worlds and dropped onto this one with no further training.

scale transfer from 16 to 32 — **Figure 3 — Size generalization.** The same size-invariant policy, trained at 16×16 with 4 agents, running at 32×32 with 10. Because perception, belief, and message-passing are all local and count-invariant, the parameters transfer without retraining.

explorer and relay roles — **Figure 4 — Explorer and relay behavior.** On the connectivity-aware objective some agents push out to the frontier while others hold position to keep the graph connected — a division of labor that the reward shape encourages rather than hard-codes.

planner on cluttered map — **Figure 5 — Planning through clutter.** The distilled planner on a densely obstructed map: it commits to routes around obstacles it already knows about, rather than rediscovering each wall by bumping into it.