Multi-agent Coordination with AlgebraicJulia using Cellular Sheaves

Cellular Sheaves for Multi-agent Control Systems

For our purposes, a multi-agent control system consists of a collection of N agents with discrete LTI dynamics x_i(t+1) = A_i x_i(t) + B_i u_i(t) for each i\in[N], where A_i and B_i are matrices, x_i is the state variable of agent i, and u_i is the control input of agent i. We suppose that agents can have bidirectional communication with other agents. The communication topology of the agents thus forms an undirected simple graph G. A general multi-agent coordination problem involves each agent choosing control inputs for themselves to drive the total system towards some desired goal. The agents should make these choices using only local computation and communication with neighboring agents. Examples of coordination goals include

• Consensus, where each agent reaches the same position,
• Formation, where each agent reaches a desired displacement from neighboring agents,
• Flocking, where all agents move with the same velocity while staying a fixed distance apart from each other.

The main idea of our paper was to use cellular sheaves to model the communication structure of the multi-agent system and edge potential functions to encode the coordination goals between each pair of agents. For the rest of this section, we introduce concepts from cellular sheaves as they relate to this multi-agent setup.

A cellular sheaf \mathcal{F} on an undirected simple graph G=(V,E) consists of

• a collection of vector spaces \mathcal{F}(v) for each v\in V known as vertex stalks,
• a collection of vector spaces \mathcal{F}(e) for each e\in E known as edge stalks,
• For each edges e=v\sim w, a pair of linear maps \mathcal{F}_{v\to e}\colon \mathcal{F}(v)\to \mathcal{F}(e) and \mathcal{F}_{w\to e}\colon \mathcal{F}(w)\to\mathcal{F}(e) known as restriction maps.

The graph G corresponds to the communication topology of the agents, while the vertex stalks are the state spaces of each agent. The edge stalks are then the spaces of valid communications between agents and the restriction maps encodes the view of each agents state which is passed to other agents. A simple example is an agent with a complex state space who only wants to communicate its position with other agents. In this case, it would choose projection onto the position components of its state as its restriction map to its neighbors.

There are two important vector spaces associated to any cellular sheaf:

1. The space of 0-cochains: C^0(G;\mathcal{F})\coloneqq\bigoplus_{v\in V}\mathcal{F}(v)
2. The space of 1-cochains: C^1(G;\mathcal{F})\coloneqq\bigoplus_{e\in E}\mathcal{F}(e)

A global section of \mathcal{F} is a globally consistent choice of vectors for each vertex stalk, meaning that when we pass these vectors through the incident restriction maps, they are equal. In the context of our multi-agent system, a global section is a state for each agent which agrees when communicated with neighboring agents.

To compute whether a given state is a global section, we can use the coboundary map. Given an arbitrary orientation of the edges of G, the coboundary map of \mathcal{F}, denoted \delta_\mathcal{F} is the linear map C^0(G;\mathcal{F})\to C^1(G;\mathcal{F}) defined by (\delta_{\mathcal{F}} \mathbf{x})_{e} = \mathcal{F}_{i \to e}(x_i) - \mathcal{F}_{j \to e}(x_j) for all edges e=i\sim j. It is easy to see that the zeros of the coboundary map correspond to global sections, because (\delta_\mathcal{F}\mathbf{x})_e=0 precisely when \mathcal{F}_{i\to e}(x_i)=\mathcal{F}_{j\to e}(x_j).

To introduce different coordination goals, we can define potential functions on each edge. For an edge e\in E, a potential on e is a function U_e\colon\mathcal{F}(e)\to\mathbb{R} which we can think of as defining a cost for each element of the edge stalk. The function U(\mathbf{y}) = \sum_{e\in E}U_e(y_e) defines the total cost for all edges of the cellular sheaf. Given such a U, the coordination goal of our multi-agent system is \underset{\mathbf{x}\in C^0(G;\mathcal{F})}{\textnormal{minimize }} U(\delta_\mathcal{F}\mathbf{x}). In other words, we want our system to reach a state which minimizes the edge potential functions after being passed through the coboundary map. To get some intuition, the following table summarizes the edge potential functions associated with various coordination goals.

Solving Coordination Problems

We implemented cellular sheaves with nonlinear potential functions and a solver for coordination problems in our package AlgebraicOptimization.jl. In our framework, a multi-agent optimal control problem consists of

• A cellular sheaf \mathcal{F} on a graph G
• Potential functions for each edge
• Single-agent optimal control objectives (specified as JuMP.jl models in our implementation) for each vertex.

The overall problem is to then compute control inputs over a fixed time horizon which minimize each agents optimal control objective as much as possible while satisfying the coordination goal by the end of the time horizon.

Here as some examples of different coordination goals being reached by a 3 agent system, where each agents’ dynamics are given by 2-dimensional double integrators. Details on each example as well as the code to generate the plots can be found in the docs