control//multi-agent control//communication graph
A communication graph is the graph whose nodes are the agents of a fleet and whose edges are the links over which they currently hear each other, and it is the structure every multi-agent algorithm actually runs on: consensus, auctions and distributed estimation only ever combine information along its edges. Unlike the graph of a pipe network it does not stay put; it changes as agents move, as obstacles come between them and as packets are lost.
A communication graph is the graph whose nodes are the agents of a fleet and whose edges are the links over which they currently hear each other, and it is the structure every multi-agent algorithm actually runs on: consensus, auctions and distributed estimation only ever combine information along its edges. Unlike the graph of a pipe network it does not stay put; it changes as agents move, as obstacles come between them and as packets are lost.
The convenient model is the disk model: agents iii and jjj are linked when their distance is below a radio range rrr, so the adjacency entry is aij=1a_{ij}=1aij=1 if ∥pi−pj∥<r|p_i-p_j|<r∥pi−pj∥<r and zero otherwise (adjacency and degree). Real links are probabilistic (a packet gets through with a probability that falls with distance, multipath and interference) and can be asymmetric (a drone with a stronger transmitter is heard by one it cannot hear back), which turns an undirected graph into a directed one (radio link).
Whether the group can agree at all, and how fast, is a property of this graph.
Its graph Laplacian has λ2>0\lambda_2>0λ2>0 exactly when it is connected, and λ2\lambda_2λ2 sets the convergence rate of the consensus protocol: ten drones that each hear only their neighbours in a chain agree a hundred times slower than ten that all hear each other.
Moving changes the graph, so the speed of agreement changes during the manoeuvre itself: whatever the agents do with their positions feeds back into how well they can talk.
Losses make edges flicker. Consensus still converges if the union of the links over every bounded window of time is connected, so an intermittent graph is slower but survivable; a graph that stays split is not (network partition).
Direction changes the answer. With one-way links, consensus converges when some agent reaches every other along the arrows, and the agreed value is a weighted average that favours the agents most listened to (diffusion and consensus gives its left-eigenvector form).
Every edge is also a message per period on a shared channel, which is where communication constraints begin: more links buy speed and robustness and pay for them in bandwidth.