Satellites, drone swarms and vehicles increasingly need to split into cooperating teams. Examples are pooling compute for a task, relaying for each other, or jointly covering an area. The best way to divide them into teams changes as they move. Finding a good division of agents into teams is called coalition structure generation. It is hard because the number of possible divisions grows faster than exponentially, from 115,975 for ten agents to about $8 \times 10^{23}$ for thirty. Existing solvers treat it as a one-shot puzzle on a fixed network. On a moving network, however, the team structure is something the system executes over time. Teams split, merge and trade members one step at a time, those steps cost signaling, and every intermediate arrangement must actually be connected by radio links that exist at that moment.
We propose to treat the sequence of intermediate team structures, a "bridge," as the deployed reconfiguration schedule rather than an internal search trick. Using the predictable motion of orbits and flight plans, the method plans bridges from the structure running now to structures that will be valuable a few time steps ahead. It accepts a bridge only if every intermediate step is legal on the network predicted for the moment that step executes, and it scores the bridge by the total team value accumulated along the way, not only at its endpoint. In two sentences: current solvers jump to a good partition as if reorganizing were free and the network frozen. We plan the path of small, always-connected reorganizations that earns the most value while the network moves underneath it.
Core Claim
Our claim is conditional. When changing team membership has a nonzero cost per atomic move and link lifetimes are comparable to the time a reconfiguration takes, planning time-indexed bridges over a predicted time-varying graph should beat two alternatives on welfare accumulated over the horizon. The first is re-solving at each network snapshot and jumping to the new answer. The second is locally repairing the current structure. When moves are free and instantaneous, the advantage should vanish. We treat that vanishing point as a test of the claim, not as an embarrassment.
Formally, let $G_t$ be the predicted communication graph at step $t$ and $P_t$ the deployed partition of agents. Let $v_t(C)$ be the value of coalition $C$ at time $t$, and let $d(P, P')$ be the number of atomic split, merge or swap moves separating two partitions. We maximize
$$J = \sum_{t=1}^{T} \sum_{C \in P_t} v_t(C) \;-\; \lambda \sum_{t=1}^{T} d(P_{t-1}, P_t),$$
subject to every $C \in P_t$ being a connected subgraph of $G_t$ and $d(P_{t-1}, P_t) \le k$. Here $\lambda$ is the cost per move and $k$ is the number of moves executable per step. Following the synergy-minus-coordination-cost structure of Algorithms for Graph-Constrained Coalition Formation in the Real World, we take $v_t(C) = m(C) - a_t(C)$. The synergy $m$ is drawn from standard coalition-value distributions. The coordination cost $a_t$ grows with the multi-hop distances among members in $G_t$, so a coalition becomes expensive before it becomes disconnected.
How This Differs From Closest Work
The bridging idea comes from two papers, and in both it lives entirely inside the optimizer. A Multiagent Path Search Algorithm for Large-Scale Coalition Structure Generation introduces SALDAE, which lays out partitions on a lattice of split and merge moves. Several search agents walk that lattice, and SALDAE builds split-then-merge, merge-then-split and approach-then-swap bridges between an incumbent and a newly found good partition. Grasp and Path-Relinking for Coalition Structure Generation relinks elite partitions with forward, backward and forward-backward paths. In both papers the bridge is a way to find a better endpoint, the lattice is static, every mathematically valid partition is assumed executable, and intermediate states carry no deployment value. We reuse their move vocabulary and their elite-to-elite construction. We change what a bridge means: its intermediate states are deployed, constrained by a time-varying graph, and counted in the objective. We also give SALDAE's acknowledged open problem, where to aim bridges, a concrete answer: aim them at elite partitions of predicted future graphs.
The graph constraint and the value model come from CFSS in Algorithms for Graph-Constrained Coalition Formation in the Real World. CFSS turns connected-coalition search into a tree of edge contractions with tight synergy-minus-cost bounds, reaching 30,000 agents. That tree is conditioned on one fixed graph and fractures when an edge disappears. We use CFSS as a per-snapshot generator of elite targets and as a source of cheap upper bounds for pruning bridge states. We do not try to make the contraction tree itself dynamic.
The dynamic-topology side supplies the premise that motion is predictable. Service Function Chain Dynamic Scheduling in Space-Air-Ground Integrated Networks discretizes satellite and drone motion into a time-extended graph of quasi-static snapshots. Its paths are physical routes for data; ours are paths through the space of partitions, laid on the same kind of time-indexed graph.
Three papers constrain the design. SkyLink: Scalable and Resilient Link Management in LEO Satellite Networks shows that centrally recomputed shortest paths fail badly on moving constellations, and that resilience to unpredicted failures matters. We therefore evaluate under injected link failures, not only clean predictions. BRIDGE: Bi-level Reinforcement Learning for Dynamic Group Structure in Coalition Formation Games handles coalition values that shift as policies learn, but on a stationary interaction topology and with merge-only moves. Cluster-Based Multi-Agent Task Scheduling for Space-Air-Ground Integrated Networks regroups drones by K-Means on position, which responds to motion but optimizes no coalition value function.
Research Program
The first deliverable is a benchmark, because none exists for coalition structure generation on a moving graph. We will build time-indexed graphs $G_t$ in two ways. The first computes line-of-sight links among satellites from the OneWeb orbital-element traces used by SkyLink and the Starlink G6-35 ephemeris setting used by the service-chain paper. The second adds mobile drones in the 5 km by 5 km, 40-drone layout of the clustering paper. On top of these graphs we place synergy values $m(C)$ drawn from the Normal, Exponential, Gamma and Zipf distributions used by SALDAE and SMART, plus distance-based coordination costs $a_t(C)$. The move cost $\lambda$, the per-step move budget $k$ and the snapshot interval are exposed as knobs. For ten or fewer agents, the time-expanded lattice has at most 115,975 partitions per step, with neighbors reachable by one move. Dynamic programming over that lattice therefore gives the exact hindsight optimum of $J$. This exact reference is what lets the small-scale experiments be decisive rather than relative.
The second deliverable is the planner. At each decision step it does three things. It takes elite partitions of the predicted graphs $G_{t+h}$ for a few horizons $h$, produced by a CFSS- or SALDAE-style anytime solver. It then builds candidate bridges from the deployed $P_t$ toward each target using the three SALDAE bridge types, discarding any intermediate state with a coalition disconnected in the graph of its execution step. Finally it scores each surviving bridge by its accumulated $J$ over the horizon and executes only its first step, then replans in receding-horizon fashion.
Evaluation cost along a bridge is a known bottleneck. We control it in two ways. Consecutive bridge states differ in at most two coalitions, so the planner caches coalition values and re-evaluates only the changed ones. It also discards a bridge early when the CFSS upper bound on its remaining states cannot beat the incumbent. The planner can run decentralized, with each current coalition planning its own local bridge, but the first study keeps it centralized so that the effect of the formulation is not confounded with the effect of distribution.
Baselines
The naive reference point is to do nothing beyond forced repair. The initial partition is kept, and a coalition is split along a link only when that link breaks. This shows how much value is lost by ignoring motion altogether. It costs almost nothing, so any method that fails to beat it is paying for reconfiguration without earning it back.
The strongest existing competitor is per-snapshot re-solving with SALDAE (A Multiagent Path Search Algorithm for Large-Scale Coalition Structure Generation). Each snapshot's partition is recomputed on the current graph, and the deployed structure then moves toward the new answer, charged at $\lambda$ per move under the same budget $k$. It is strongest because it is the best reported large-scale approximate method in the file. On the Exponential distribution it reached the optimum in 91% of small cases, against 7% for PICS and 5% for CSG-UCT, and it runs up to 2,000 agents. It also already uses bridges internally, so beating it isolates deployment-aware bridging rather than bridging per se. Where the graph is sparse, we add per-snapshot CFSS, which reports solutions within 88% of optimum in under 100 seconds on 2,732 energy-consuming households (Algorithms for Graph-Constrained Coalition Formation in the Real World). For $n \le 27$ we add exact per-snapshot re-solving with SMART (Faster Optimal Coalition Structure Generation via Offline Coalition Selection and Graph-Based Search), which is optimal per snapshot and myopic across time.
We found no reported result on Lacuna for any coalition structure generation method on a time-varying communication graph. All numbers on the new benchmark will therefore be produced by us, with all methods given the same predicted graphs, the same wall-clock budget per decision step and the same tuning budget over their hyperparameters.
Two further baselines round out the comparison. The first is warm-started repair plus local search, which starts from $P_{t-1}$, applies forced splits, and runs the split, merge and shift neighborhoods of GRASP (Grasp and Path-Relinking for Coalition Structure Generation) under the move budget. The second is K-Means spatial regrouping in the style of Cluster-Based Multi-Agent Task Scheduling for Space-Air-Ground Integrated Networks.
Two ablations isolate the key ingredients. The reactive ablation plans bridges using only the current $G_t$ rather than predicted future graphs. The endpoint ablation scores bridges only by their endpoint value, as SALDAE and path relinking do, instead of by value accumulated along the way.
Beating the strongest baseline means a statistically significant gain in accumulated $J$ over per-snapshot SALDAE at equal compute, across seeds and value distributions, in the regime $\lambda > 0$. At $n \le 10$ we will also report the gap to the hindsight optimum.
Why not just…?
Why not just re-solve at every snapshot with a fast anytime solver and jump? This is the real threat. If reorganizing is free and instantaneous, jumping to each snapshot's best partition is exactly optimal step by step, and our bridges add nothing. The proposal only claims an advantage when $\lambda > 0$ or $k$ is small. It also claims an advantage when links break faster than a jump can be carried out, a regime that Service Function Chain Dynamic Scheduling in Space-Air-Ground Integrated Networks argues is common, since snapshot validity is short. We will sweep $\lambda$ and $k$ and report where the curves cross. If per-snapshot SALDAE matches us at realistic handover costs, the idea is wrong for this domain and we will say so.
Why not just keep the current structure and repair it with local search? Warm-started local search is cheap and naturally respects move budgets. It is myopic, though: it cannot choose a move that loses a little now to avoid a forced split three steps later. GRASP+PR's own comparison showed that local search alone stalls where relinking between elites keeps improving (Grasp and Path-Relinking for Coalition Structure Generation). Whether that carries over to moving graphs is exactly what the repair baseline and the reactive ablation test.
Why not just cluster by position? Proximity captures part of the coordination cost $a_t$ but none of the synergy $m$. Coalitional Structure Generation in Skill Games locates the difficulty of coalition values in overlapping skills, not geometry. On the Zipf and Exponential synergy distributions we expect K-Means regrouping to trail value-aware methods. If it does not, our benchmark's values are too distance-dominated and we will rebalance $m$ against $a_t$.
Proposed Experiments
The first decisive check is at $n \le 10$ on OneWeb-derived graphs. It compares every method's accumulated $J$ to the exact hindsight optimum across the sweep of $\lambda$, $k$ and snapshot interval. We expect bridge planning to close most of the gap that per-snapshot re-solving leaves when $\lambda$ is moderate, and to tie it as $\lambda \to 0$. A win at $\lambda = 0$ would indicate an implementation artifact rather than a real effect.
The second check scales to hundreds and then up to 2,000 agents on combined satellite and drone graphs. There we report $J$ relative to per-snapshot SALDAE at matched decision-time budgets, along with the number of executed moves and the fraction of steps with forced splits.
The third check targets robustness to prediction error. Borrowing SkyLink's failure-injection protocol, we perturb predicted orbits and randomly fail about 3% of links without warning. The measure is how fast the predictive planner's advantage decays relative to the reactive ablation. If the advantage disappears under small prediction errors, anticipation is not worth its cost.
A final diagnostic compares the endpoint ablation with the full planner. It tests whether counting value along the bridge, the one conceptual change from SALDAE and path relinking, carries the improvement on its own.
References
- Algorithms for Graph-Constrained Coalition Formation in the Real World
- A Multiagent Path Search Algorithm for Large-Scale Coalition Structure Generation
- Grasp and Path-Relinking for Coalition Structure Generation
- Service Function Chain Dynamic Scheduling in Space-Air-Ground Integrated Networks
- SkyLink: Scalable and Resilient Link Management in LEO Satellite Networks
- BRIDGE: Bi-level Reinforcement Learning for Dynamic Group Structure in Coalition Formation Games
- Cluster-Based Multi-Agent Task Scheduling for Space-Air-Ground Integrated Networks
- Faster Optimal Coalition Structure Generation via Offline Coalition Selection and Graph-Based Search
- Coalitional Structure Generation in Skill Games