# Multi-Agent Reinforcement Learning with Control-Theoretic Safety Guarantees
for Dynamic Network Bridging

Raffaele Galliera, Konstantinos Mitsopoulos, Niranjan Suri and Raffaele
Romagnoli R. Romagnoli is with the Department of Electrical and Computer
Engineering, Carnegie Mellon University, 5000 Forbes Ave, Pittsburgh, PA
15213, USA<EMAIL_ADDRESS>Galliera, N. Suri, and Konstantinos
Mitsopoulos are with the Institute for Human and Machine Cognition, 40 South
Alcaniz St, Pensacola, FL 32502, USA<EMAIL_ADDRESS><EMAIL_ADDRESS><EMAIL_ADDRESS>
###### Abstract

Addressing complex cooperative tasks in safety-critical environments poses
significant challenges for Multi-Agent Systems, especially under conditions of
partial observability. This work introduces a hybrid approach that integrates
Multi-Agent Reinforcement Learning with control-theoretic methods to ensure
safe and efficient distributed strategies. Our contributions include a novel
setpoint update algorithm that dynamically adjusts agents’ positions to
preserve safety conditions without compromising the mission’s objectives.
Through experimental validation, we demonstrate significant advantages over
conventional MARL strategies, achieving comparable task performance with zero
safety violations. Our findings indicate that integrating safe control with
learning approaches not only enhances safety compliance but also achieves good
performance in mission objectives.

##  I Introduction

Despite the promising performance of Multi-Agent Reinforcement Learning (MARL)
in simulations, its application in real-world, safety-critical scenarios
raises significant concerns. A key challenge is collision avoidance,
especially in applications like autonomous driving, where failure to prevent
collisions could result in severe consequences. Moreover, the inherent nature
of Multi-agent Systems (MAS) often involves partial observability, further
increasing the complexity of these problems by limiting the information
available to each agent about the environment and the states of other agents.

This challenge highlights a fundamental limitation of all Reinfocement
Learning (RL)-based approaches: while agents learn to optimize predefined
reward functions, their behavior lacks guarantees and remains inherently
unpredictable. The sole reliance on MARL’s reward functions to ensure safety
is insufficient [1]. Even with extensive training and monitoring of an agent’s
performance based on expected rewards, or other performance measures, it is
impossible to exhaustively examine all potential scenarios in which the agent
might fail to act safely or predictably.

In ensuring safety among agents, various control-theoretic approaches and
hybrid learning approaches have been developed, ranging from Model Predictive
Control (MPC) [2] to Reference Governor (RG) techniques [3], and from Control
Barrier Functions (CBFs) [4] to Reachability Analysis (RA) methods [5]. In
this work, we focus on developing a hybrid learning approach built upon the
method used in [6], that can learn to achieve complex objectives while
ensuring safety guarantees in distributed MAS.

To demonstrate and evaluate the effectiveness of our hybrid approach we
consider the cooperative task of Dynamic Network Bridging [7] (Fig. 1). In
this task the goal is to establish and maintain a connection between two
moving targets A and B in a 2D plane, relying on a swarm of $N$ agents with
limited observation of the environment. The agents must form an ad-hoc mobile
network that establishes a communication path between the two targets as they
move, dynamically adjusting their positions to ensure an uninterrupted multi-
hop communication link.

Figure 1: Decentralized swarm coordination for dynamic network bridging

In this paper we introduce a hybrid approach combining MARL and control-
theoretic methods, accomplishing task objectives while providing safety
guarantees. Our key contributions are: 1) A decentralized control framework
that is MARL compatible and restricts the effect of each agent’s movement
updates to only its one-hop neighbors, enabling efficient local coordination;
2) An algorithm that updates setpoints while preserving safety conditions
through communication with affected neighbors; 3) An analytical
computationally tractable condition verifying potential safety violations
during updates. Overall our approach provides effective coordination among
agents while ensuring safety constraints.

##  II Preliminaries

In this section, we present the foundational theoretical elements, drawing
from both control theory and MARL, that form the basis of our proposed hybrid
approach.

Consider a linear time invariant (LTI) system expressed in the state space
form

$\dot{x}=Ax+Bu$ (1)

where $x\in\mathbb{R}^{n}$ is the state vector with $n$ components, and
$u\in\mathbb{R}^{p}$ is the input vector with $p$ components. Thus, the
dynamical matrices are $A\in\mathbb{R}^{n\times n}$ and
$B\in\mathbb{R}^{n\times p}$. If the pair $(A,B)$ is controllable, there
exists a state feedback controller:

$u=-Kx$ (2)

such that, the origin ($x=0$) of the resulting closed-loop (C-L) system:

$\dot{x}=(A-BK)x=A_{f}x$ (3)

is an asymptotically stable equilibrium point (EP): $x(t)\rightarrow
0\quad\text{as}\quad t\rightarrow+\infty$. Hence, the matrix $A_{f}$ is
Hurwitz, i.e. all the eigenvalues have a negative real part [8]. The problem
to design (2) that makes (1) asymptotically stable is called stabilization
problem.

###  II-A Tracking Control Problem

In the case the problem requires to move the system (1) following a specific
trajectory, the problem is called tracking control. This problem can be solved
by generating a sequence of EPs [9] that we call setpoints, denoted by
$x_{sp}$. The C-L system (3) can be represented as:

$\dot{x}=A_{f}(x-x_{sp})$ (4)

where the control input (2) becomes $u=-K(x-x_{sp}).$

###  II-B Lyapunov’s Theory

Since $A_{f}$ is Hurwitz, there exists a symmetric positive definite matrix
$P>0$ such that:

$A_{f}^{T}P+PA_{f}=-Q$ (5)

for a given symmetric positive definite matrix $Q>0$. Equation (5) is called
Lyapunov’s equation. Defining the $P$-norm as:

$\lVert x-x_{sp}\rVert_{P}\triangleq\sqrt{(x-x_{sp})^{T}P(x-x_{sp})}$ (6)

the $P$-norm squared is a Lyapunov function $V(x)=\lVert
x-x_{sp}\rVert_{P}^{2}$, which is always positive except at $x_{sp}$ where it
is zero. For all trajectories $x(t)$ starting within the ellipsoid:

$\mathcal{E}_{c}(x_{sp})=\\{x\in\mathbb{R}^{n}\,|\,\lVert
x-x_{sp}\rVert_{P}^{2}\leq c\\},$ (7)

where $c>0$, $V(x(t))$ is monotonically decreasing. Therefore, the trajectory
$x(t)$ never leaves $\mathcal{E}_{c}$, which is called a positively invariant
set [8].

###### Remark 1

In the case of a nonlinear dynamical system described by $\dot{x}=f(x,u)$
where $u=0$, $x=0$ is an equilibrium point for the system $f(0,0)=0$. The
control input (2) can be designed by considering the linearized system (1)
around the equilibrium point. Therefore, the closed-loop (CL) system (3) can
be used to solve Lyapunov’s equation (5), which is used to compute the
positively invariant set $\mathcal{E}_{c}(x_{sp})$ (7). While for LTI systems,
$\mathcal{E}_{c}(x_{sp})$ is positively invariant for any positive
$c\in\mathbb{R}$, for nonlinear systems, we need to verify that condition in a
neighborhood of the equilibrium point $x_{sp}$ [8]. Furthermore, for nonlinear
systems, $x_{sp}$ has to satisfy $f(x_{sp},0)=0$.

###  II-C 6-DOF UAV

In this work, we consider a 6-DOF UAV as the agent, described by a state
vector of 12 components:

$x=\begin{bmatrix}\dot{p}_{x},&p_{x},&\dot{p}_{y},&p_{y},&\dot{p}_{z},&p_{z},&\dot{\phi},&\phi,&\dot{\theta},\\\
\theta,&\dot{\psi},&\psi\end{bmatrix}^{T}$ (8)

where $p_{x}$, $p_{y}$, $p_{z}$, and their derivatives represent linear
position and velocity, respectively. Similarly, $\phi$, $\theta$, $\psi$, and
their derivatives represent the Euler angles (roll, pitch, and yaw) and their
angular velocities, respectively. This model is consistent with the one used
in [9] and references therein. The controller used is given by (2), obtained
by linearizing the quadrotor model around an equilibrium point. For this case,
the equilibrium point is indicated with $x_{sp}$ which has the same structure
of (8) with all components equal to zero except for $p_{x}$, $p_{y}$, $p_{z}$.

###  II-D Multi-Agent Reinforcement Learning

In a typical multi-agent cooperative scenario, $N$ agents interact within an
environment to complete a task. Noisy and limited sensors may prevent each
agent from observing the full state of the environment, allowing access only
to partial observations. With partial observability, an agent no longer knows
the true state of the environment, but instead needs to maintain a belief
state - a probability distribution over states estimated from its observation
history - which it uses to select actions. Decision-making processes in such
contexts can be formulated as a Decentralized Partially Observable Markov
Decision Process (Dec-POMDP) [10, 11].

A Dec-POMDP is defined by a tuple
$(S,\mathbf{A},\mathcal{O},T,R,\Omega,\gamma,N)$ where $S$ is a finite set of
states of the environment, $\mathbf{A}$ is a set of joint action spaces, and
$N$ is the number of agents, $T$ is the state transition probability function
which gives the probability of transitioning from state $s$ to state
$s^{\prime}$ when joint action $\mathbf{a}=(a_{1},\cdots,a_{N})$ is taken; $R$
is the joint reward function that maps states and joint actions to real
numbers and is used to specify the goal of the agents; $\Omega$ is a set of
joint observations $O_{i}$, where $O_{i}$ is the observation set for agent
$i$; $\mathcal{O}$ is the joint observation probability function, which gives
the probability of receiving joint observation
$\mathbf{o}=(o_{1},\cdots,o_{N})$ after taking joint action $\mathbf{a}$ and
ending up in state $s^{\prime}$; and $\gamma$ is the reward discount factor,
$0\leq\gamma\leq 1$.

In a Dec-POMDP, agents need to collaborate and coordinate their actions based
on their individual observations to maximize the joint reward function.
Solving a Dec-POMDP optimally is computationally intractable, as the policy
space grows exponentially with the number of agents and the planning horizon.
Therefore, various approximate solution methods [12, 13] have been used, such
as heuristic search, dynamic programming, value or policy-based approximators
with neural networks etc. The problem facing the team is to find the optimal
joint policy, i.e. a combination of individual agent policies that produces
behavior that maximizes the team’s expected reward.

##  III Problem Formulation

We address the challenge of dynamically forming and sustaining a connection
between two moving targets, A and B, in a 2D space using a swarm of $N$ agents
[7]. These agents must collaboratively adjust their positions to maintain a
continuous multi-hop link between the targets, operating under decentralized
control and limited local perception, while ensuring they avoid collisions and
respect physical boundaries. We consider all the agents as nonlinear systems
that can be reduced into the form (1) controlled by (2) around the equilibrium
point $x_{sp,i}$ [9]:

$\dot{x}_{i}=A_{f}(x_{i}-x_{sp,i})=(A-BK)(x_{i}-x_{sp,i})$ (9)

for $i=1,\ldots,N$. In this case, we consider $N$ agents described with the
same model, but in general, our approach can be generalized to the case of
different dynamics and multidimensional scenarios.

###  III-A One-hop Communication

We assume that for each agent, there is a ball of radius $r$ in the 2- or
3-dimensional Euclidean space centered at the agent’s current linear position
$p_{i}(t)=[p_{x,i}(t),p_{y,i}(t),p_{z,i}(t)]^{T}$:

$\mathcal{B}_{r}(p_{i}(t))=\left\\{p\in\mathbb{R}^{3}:\|p-p_{i}(t)\|^{2}\leq
r^{2}\right\\}$

Given two agents $i$ and $j$ with $i\neq j$, they can communicate if and only
if

$\mathcal{B}_{r}(p_{i}(t))\cap\mathcal{B}_{r}(p_{j}(t))\neq\emptyset$ (10)

In our setup, since $p_{z,i}$ is fixed, the one-hop communication region is
described by a 2-D ball. Note that, we use a different notation when we refer
to the 2-D communication space to avoid any confusion between the quadrotor
$x$-axis and the state space $x$.

###  III-B Safety

###### Definition 1

Given two agents $i$ and $j$, where $x_{sp,i}\neq x_{sp,j}$,
$x_{i}(t_{0})\in\mathcal{E}_{c}(x_{sp,i})$, and
$x_{j}(t_{0})\in\mathcal{E}_{c}(x_{sp,j})$. Agents $i$ and $j$ are safe with
respect to each other if

$\mathcal{E}_{c}(x_{sp,i})\cap\mathcal{E}_{c}(x_{sp,j})=\emptyset.$ (11)

The above definition is derived by the positively invariant property of (7),
since the initial conditions of each agent are inside their respective
ellipsoids, then $x_{i}(t)\in\mathcal{E}_{c}(x_{sp,i})$ and
$x_{j}(t)\in\mathcal{E}_{c}(x_{sp,j})$ for $t\rightarrow+\infty$. This means
that the trajectory of each agent cannot intersect generating the risk of
possible collisions.

In order to guarantee safety in our setup, we need the following assumption:

###### Assumption 1

The projection of $\mathcal{E}_{c}(x_{sp,i})$ into the 2-D space formed by the
components $p_{x}$ and $p_{y}$ must be contained within the 2-dimensional ball
$\mathcal{B}_{r}(p_{i}(t))$, where $p_{i}(t)=[p_{x,i}(t),p_{y,i}(t)]$
represents the actual position coordinates ($p_{x,i}(t),p_{y,i}(t)$) of agent
$i$ for any state $x_{i}\in\mathcal{E}_{c}(x_{sp,i})$.

###  III-C Cooperative MARL for Dynamic Network Bridging

Each agent $i$ has a local observation $o_{i}$ comprising the structure of its
neighborhood and features representing its neighbors at certain time-step $t$.
Such features include the node ID, current coordinates, action taken, and
coordinates of the targets A and B to be connected. At the beginning of every
time-step, agents make decentralized decisions, generating target points $w$,
utilizing their local observation to choose the direction of their next
movement. This is encoded in a two-dimensional action space, with each
dimension having three options: move forward, move backward, or hold along the
corresponding $p_{x}$ or $p_{y}$ axis. Given the direction chosen by the
agents, a new target point is calculated for each agent using a fixed offset
equal for both the $p_{x}$ and $p_{y}$ axes. Finally, agents are rewarded
using a reward function that motivates agents to form a connected network
bridging the targets. Such reward signal combines three components:

Base Connectivity Reward: The base reward, $R_{\text{base}}$, encourages
larger connected components:

$R_{\text{base}}(s)=\frac{|C_{\text{max}}(s)|}{|\mathcal{V}|},$ (12)

where $|C_{\text{max}}(s)|$ represents the size of the largest connected
component in state $s$, and $|\mathcal{V}|$ is the total number of entities.

Centroid Distance Penalty: The centroid distance penalty, $P_{\text{cent}}$,
is based on agents’ positions relative to the targets, penalizing them based
on the Euclidean distance between the centroid of the agents’ positions and
the central point between the targets.

Target Path Bonus: A bonus, $B_{\text{path}}=100$, is awarded if a path exists
between the two targets.

The overall reward combines these three elements:

$R(s,a)=\begin{cases}B_{\text{path}}(s)&\mbox{if
}\exists\mathrm{path}(T_{1},T_{2});\par\\\
R_{\text{base}}(s)-P_{\text{cent}}(s),&\mbox{otherwise}.\end{cases}$ (13)

We also include a physics simulator, modeling the continuous non-linear
dynamics of the agents (2), and a safe tracking control system proposed in the
next section (Algorithm 1).

##  IV Safe Tracking Control

The safety tracking control algorithm that we propose here consists of two
steps, the first one is the setpoint update of the agent $i$ that guarantees
that its current position belongs to $\mathcal{E}_{c}$ of the new setpoint.
This condition is fundamental for the second step where the safety condition
(11) is checked for all agents within the one-hop communication ball.

Let us start with the first step which has been borrowed from [6]. For each
agent, we select two scalars $c$ and $s$ such that $0<s<c$ therefore
$\mathcal{E}_{s}(x_{sp,i})\subset\mathcal{E}_{c}(x_{sp,i})$.

###### Definition 2

We can say that the agent has reached the setpoint $x_{sp,i}$ if and only if
$x_{i}(t)\in\mathcal{E}_{s}(x_{sp,i})$.

Assuming that the agent $i$ is moving from the target point $w_{i}$ to the
target point $w_{i+1}$, generated by the MARL, the idea is to generate a
sequence of setpoints on the line that connects the two target points. Once
the state of agent $i$, $x_{i}$ reached the setpoint $x_{sp,i}$, a new
setpoint $x^{\prime}_{sp,i}$ is generated following the rule

$x^{\prime}_{sp,i}=x_{sp,i}+(\sqrt{c}-\sqrt{s})v$ (14)

where $v\in\mathbb{R}^{n}$ with $\|v\|_{2}=1$, indicating the direction of the
line connecting the two target points. As showed in [6]

$x_{i}(t)\in\mathcal{E}_{s}(x_{sp,i})\Rightarrow
x_{i}(t)\in\mathcal{E}_{c}(x^{\prime}_{sp,i}).$ (15)

Fig. 2 illustrates the process of updating the setpoint, presented in 2-D
space for clearer visualization, though it actually corresponds to a state
space with n=12 components, as applicable to quadrotors.

Figure 2: Setpoint update for agent $i$ in the state space. Note that the
target points $w_{i}$ and $w_{i+1}$ have the same structure of the setpoints
$x_{sp,i}$.

Thanks to (14) and Assumption 1, the projection of
$\mathcal{E}_{c}(x^{\prime}_{sp,i})$ is contained in $\mathcal{B}(p_{i}(t))$.

###### Proposition 1

Considering agent $i$ moving from target point $w_{i}$ to $w_{i+1}$, and
updating the setpoint $x_{sp,i}$ every time
$x_{i}(t)\in\mathcal{E}_{s}(x_{sp,i})$ by using (14). Considering also
Assumption 1 true, then the safety condition (11) can be violated only with
all the agents $j\neq i$ that satisfy (10) (i.e. within the one-hop
communication range).

###### Proof:

From Assumption 1, the ball $\mathcal{B}_{r}(p_{i}(t))$ encompasses the
projection onto the 2-D space of $\mathcal{E}_{c}(x{sp,i})$ for any current
state $x_{i}(t)\in\mathcal{E}_{c}(x_{sp,i})$. Utilizing (14) to adjust the
setpoint ensures that $x_{i}(t)$ remains within
$\mathcal{E}_{c}(x^{\prime}_{sp,i})$, signifying that its 2-D space projection
still falls within $\mathcal{B}_{r}(p_{i}(t))$. Thus, should the updated
setpoint $x^{\prime}_{sp,i}$ contravene (11), such a violation would only
occur concerning agents situated within the one-hop communication range. ∎

Proposition 1 highlights a critical aspect of setpoint updates: setpoint
updates only impact safety for agents within one-hop range. This ensures agent
$i$ can communicate with affected neighbors before executing updates. This
allows coordinating to preemptively address any potential safety concerns from
the new setpoint through direct communication with impacted agents.

Building upon Proposition 1, let’s define $\mathcal{D}_{i}(t)$ as the set
comprising all agents $j\neq i$ that are within the one-hop communication
range of agent $i$ at time $t$. The safe setpoint update algorithm for each
agent $i$ is given in Algorithm 1. Once agent $i$’s state $x_{i}(t)$ reaches
its current setpoint $x_{sp,i}$ (as per Definition 2), it computes a new
target setpoint $x^{\prime}_{sp,i}$. Before updating, agent $i$ checks for any
possible safety violations by evaluating the safety condition (11) for all
agents in $\mathcal{D}_{i}(t)$. If no violation is detected, $x_{sp,i}$ is
updated to the new $x^{\prime}_{sp,i}$; otherwise, the previous setpoint is
retained.

Input: Agent $i$ with setpoint $x_{sp,i}$, $\mathcal{D}_{i}(t)$

Output: Updated setpoint $x_{sp,i}$

safety_violation $\leftarrow$ 0;

if  _$x_{i}(t)\in\mathcal{E}_{s}(x_{sp,i})$_ then

Compute $x^{\prime}_{sp}\leftarrow$ (14);

for  _$j\in\mathcal{D}_{i}(t)$_ do

if  _$\mathcal{E}_{c}(x_{sp,i})\cap\mathcal{E}_{c}(x_{sp,j})\neq\emptyset$ _
then

safety_violation $\leftarrow 1$;

break;

end if

end for

if  _safety_violation $==$ $0$_ then

$x_{sp,i}\leftarrow x^{\prime}_{sp,i}$;

end if

end if

Algorithm 1 Setpoint Update Algorithm

By applying Algorithm 1 to each agent, we ensure that the safety condition
(11) is satisfied throughout the system. This is guaranteed by the fact that
an agent can only update its setpoint after verifying that the new target does
not violate safety for any agents within its one-hop communication range, as
stated in Proposition 1. The proof of safety relies on the following
assumptions:

###### Assumption 2

The initial setpoints of all agents satisfy the safety condition (11).

###### Assumption 3

During the setpoint update for agent $i$, all agents $j\in\mathcal{D}_{i}(t)$
cannot change their setpoints $x_{sp,j}$.

###### Proposition 2

Considering the multi-agent system described by (9) and Assumptions 1, 2 and
3, then applying Algorithm 1 to each agent guarantees that the safety
condition (11) is satisfied for all agents.

###### Proof:

By Assumption 2, the initial setpoints of all agents satisfy the safety
condition (11). Whenever an agent $i$ updates its setpoint using Algorithm 1,
it checks if the new target setpoint $x_{sp,i}^{\prime}$ violates the safety
condition for any agent $j\in\mathcal{D}_{i}(t)$. If a violation is detected,
the setpoint is not updated, ensuring that the current safe solution is
maintained. Proposition 1 guarantees that safety is only impacted for agents
within the one-hop communication range, which agent $i$ can directly
communicate with before executing the update. Furthermore, Assumption 3
prevents agents in $\mathcal{D}_{i}(t)$ from changing their setpoints during
agent $i$ ’s update, ensuring a consistent safety evaluation. Therefore, by
applying Algorithm 1 to each agent, the safety condition (11) is upheld
throughout the system’s operation. ∎

We now need to verify when the safety condition (11) is violated. Our
objective is to demonstrate that if (11) is violated, then there exists a
point on the line connecting $x_{sp,i}$ and $x_{sp,j}$, inside the overlap
region of two ellipsoids $\mathcal{E}_{c}(x_{sp,i})$ and
$\mathcal{E}_{c}(x_{sp,j})$ (Fig. 3). This overlap region, denoted by
$\mathcal{E}_{c}(x{sp,i})\cap\mathcal{E}_{c}(x_{sp,j})$, satisfies the
following condition:

$\lambda(x-x_{sp,i})^{T}P(x-x_{sp,i})+(\lambda-1)(x-x_{sp,j})^{T}P(x-x_{sp,j})\leq
c$ (16)

for $0\leq\lambda\leq 1$ with $x_{sp,i}\neq x_{sp,j}$.

###### Proposition 3

Let us consider the ellipsoids $\mathcal{E}_{c}(x_{sp,i})$ and
$\mathcal{E}_{c}(x_{sp,j})$ defined as in (7). The set of points $x$
satisfying (16) for all $\lambda\in[0,1]$ is either empty, a single point, or
an ellipsoid:

$\hat{\mathcal{E}}_{K_{\lambda}}(m_{\lambda})=\left\\{x\in\mathbb{R}^{n}:(x-m_{\lambda})^{T}P^{-1}(x-m_{\lambda})\leq
K_{\lambda}\right\\}$ (17)

where

$\displaystyle m_{\lambda}$ $\displaystyle=\lambda
x_{sp,i}+(1-\lambda)x_{sp,j}$ $\displaystyle K_{\lambda}$
$\displaystyle=1-\lambda(1-\lambda)(x_{sp,j}-x_{sp,i})^{T}P(x_{sp,j}-x_{sp,i}).$

###### Proof:

See [14]. ∎

Proposition 3 shows that if there is an ellipsoid violation, then the point
$m_{\lambda}$ belongs to the intersection Fig. 3:

$\mathcal{E}_{c}(x_{sp,i})\cap\mathcal{E}_{c}(x_{sp,j})\neq\emptyset\rightarrow
m_{\lambda}\in\mathcal{E}_{c}(x_{sp,i})\cap\mathcal{E}_{c}(x_{sp,j})$

Figure 3: Explaination of Proposition 3: $m_{\lambda}$ is on the segment that
connects the two setpoints.

Therefore, to test if the two ellipsoids intersect we need to find if there
exists at least one point on the segment joining $x_{sp,i}$ and $x_{sp,j}$
that satisfies (16). To do so we consider both ellipsoids

$\left\\{\ \begin{array}[]{l}(x-x_{sp,i})^{T}P(x-x_{sp,i})\leq\rho\\\
(x-x_{sp,j})^{T}P(x-x_{sp,j})\leq\rho\\\ \end{array}\right.$ (18)

We replace $x$ with $m_{\lambda}$ since we are checking only a point in the
segment joining the two setpoints. Defining $d\triangleq x_{sp,j}-x_{sp,i}$,
(18) can be rewritten as

$\left\\{\ \begin{array}[]{r}\lambda^{2}d^{T}Pd\leq\rho\\\
(\lambda-1)^{2}d^{T}Pd\leq\rho\\\ \end{array}\right.\Rightarrow\left\\{\
\begin{array}[]{r}\lambda^{2}\|d\|_{P}^{2}\leq\rho\\\
(\lambda-1)^{2}\|d\|_{P}^{2}\leq\rho\\\ \end{array}\right.$ (19)

Solving for $\lambda$ we obtain

$\left\\{\ \begin{array}[]{l}\lambda^{2}\leq\frac{c}{\|d\|_{P}^{2}}\\\
\lambda^{2}\|d\|_{P}^{2}-2\lambda\|d\|_{P}^{2}+\|d\|_{P}^{2}\leq c\\\
\end{array}\right.\Rightarrow 1-2\sqrt{\frac{c}{\|d\|_{P}^{2}}}\leq 0$ (20)

The two ellipsoids $\mathcal{E}_{c}(x_{sp,i})$ and $\mathcal{E}_{c}(x_{sp,j})$
intersect if

$2\sqrt{\frac{c}{\|d\|_{P}^{2}}}\geq 1\rightarrow\|d\|_{P}^{2}\leq 4c$ (21)

###### Remark 2

Although Algorithm 1 ensures safety according to Proposition 2, it does not
guarantee target achievement. Agents within one-hop communication range may
become immobilized at a certain position because any attempt to reach the
target points could potentially violate the safety condition (11). We
intentionally refrain from employing any enforcer to resolve this deadlock
scenario, as our aim is to assess whether our MARL framework can autonomously
generate target points that circumvent such situations.

In summary, our analysis provides the following key theoretical results:

  * •

Each agent’s setpoint update only impacts the safety of neighboring agents
within its one-hop communication range. This localized effect is an important
property that enables decentralized coordination.

  * •

we establish that Algorithm 1 guarantees the preservation of the safety
condition in (11) for all agents,

  * •

We provide (21) a computationally tractable method for evaluating possible
safety condition (11) violations.

Together, these theoretical results form the basis for our safe and
distributed multi-agent control framework, ensuring that agents can
dynamically update their setpoints while maintaining the prescribed safety
guarantees through local communication and coordination.

Agent Type | Safety Mechanism | Explicit Penalty | Truncation | Avg Coverage | Avg Safety Violations
---|---|---|---|---|---
Baseline A | No | No | No | 41% | 13,880
Baseline B | No | Yes | No | 0.01% | 0
Approach A | Yes | No | No | 39% | 0
Approach B | Yes | Yes | No | 16% | 0
Approach C | Yes | Yes | Yes | 22% | 0
TABLE I: Comparison of agent performance, safety mechanisms, explicit
penalties, and safety violations.

##  V Neural Network Architecture

We employ the neural network architecture for action-value estimation
presented in [7], which is tailored to address the challenges of dynamic
network bridging in a cooperative multi-agent setting, enabling the agents to
extrapolate information about spatial and temporal dependencies while
collaborating effectively. Such architecture combines Graph Neural Networks
(GNNs) for relational modeling and exploits their message-passing mechanisms
compatibly with the task optimized in the environment [Ref Section].
Furthermore, a Long Short-Term Memory (LSTM) is employed to cope with temporal
dependencies and the partial observability of the task. The model is trained
in a Centralized Training Decentralized Execution (CTDE) [15] fashion, where
the agents optimize the same action-value function parameterization during
training. However, during execution, each agent acts based on its local
observations and the shared representations from its neighbors, adhering to
the decentralized nature of the task.

We continue by describing the key components of the architecture below.

####  V-1 Graph Attention Layers

Graph Convolutional Reinforcement Learning (DGN) [16] facilitates cooperation
between the agents by enabling them to share their latent representations with
their immediate neighbors. To this end, we leverage Graph Attention Network
(GAT) [17] to capture the spatial and relational dependencies between agents
in the network. Specifically, we employ two Multi-Headed GAT that enable each
agent to attend to and integrate information from its neighboring agents
adaptively. This encoding allows the agents to condition their actions based
on the dynamic network topology and inter-agent relationships effectively.

Additionally, we integrate target entities into the sharing process by
equipping them with this same encoding module to produce their latent
representation. If an agent’s neighborhood includes target entities, the agent
can gather their representations and condition its actions accordingly.

####  V-2 Long Short-Term Memory

To handle the partial observability and temporal dynamics of the environment,
we integrate a LSTM [18] layer into our architecture. The LSTM layer maintains
a memory of past observations, allowing the agents to make informed decisions
based on past interactions, partial observability, and the evolving
environment.

During training, we employ observation stacking, aggregating observations over
multiple time steps. Such a process gives the LSTM layer the necessary
temporal context for effective learning in the presence of partial
observability.

####  V-3 Dueling Action Decoder

To estimate action values effectively, we incorporate a Dueling Action Decoder
[19] in our architecture. This component comprises separate streams for
estimating state values and advantages, which are then combined to produce the
final action value estimates.

##  VI Experimental Setup

We evaluated our approach in a simulated 2D environment with three agents and
two moving targets. The environment was normalized with axes ranging from 0 to
1. Agents and targets had a communication range of 0.25, and their movement
offset was set to 0.05 for the calculation of the next target point $w$. The
physics simulator allowed us to simulate the non-linear Unmanned Aerial
Vehicle (UAV) dynamics while we updated the positions of the agents in their
paths toward the decided target point.

Our multi-agent strategies were trained across 1M training steps. Training
episodes are truncated and Partial Episode Boostraping [20] was performed
after 100 steps taken by each agent. Agents were initialized at fixed starting
positions that satisfy safety condition (11), and the moving targets were
randomly placed at a certain distance apart to ensure realistic difficulty and
a feasible connection. Target motion and placing follow a seeded random
pattern to control the scenarios during training and testing. The primary
focus of our experiments was to demonstrate the effectiveness of our safe
tracking control system in enabling the MARL approach to learn policies that
satisfy safety constraints. To establish the importance of this contribution,
we designed a set of experiments with varying training configurations:

  * •

Baseline A: We first trained a typical MARL approach without any safety
tracking control, serving as a baseline.

  * •

Baseline B: To investigate the impact of explicit penalization for safety
violations, we trained the same MARL approach as in Baseline A but with a high
penalty (-100) imposed whenever an agent violated the safety constraints.

  * •

Approach A: This configuration represents our key contribution, where we
trained the agents with the safe tracking control system enabled. Agents
employed Algorithm 1 to update their target points while respecting the safety
conditions.

The results from Approach A demonstrated the effectiveness of our safe
tracking control system in enabling the agents to learn policies that
accomplish the task while adhering to safety constraints.

To further solidify our approach and highlight its advantages, we conducted
additional experiments:

  * •

Approach B: Here, we combined the safe tracking control system with explicit
penalization for safety violations, similar to Baseline B. This configuration
aimed to analyze the agents’ behavior when both safety measures and
penalization for safety violations were employed simultaneously.

  * •

Approach C: Building upon Approach B, we additionally introduced episode
termination whenever safety constraints were violated. This experiment
assessed the impact of a more stringent safety enforcement mechanism.

If enabled, the safe tracking control system was used to prevent agents from
continuing their movement if they violated the safety condition (11), such as
going too close to other agents and risking collision. During training, in
case the safety condition was violated, the agents involved were forced to
stop their movement and would remain blocked until a new action toward safe
directions was computed by at least one of the agents involved. To evaluate
our agents, we ran 100 evaluation episodes disabling the safety tracking
control system and counting the number of times that safety conditions were
violated for every position update (14).

##  VII Results

Table I shows the results of our experiments evaluating different learned MARL
strategies. We report the average communication coverage achieved by the
agents as well as the number of safety violations observed when the safe
tracking control system was disabled during evaluation.

Baseline A agents, trained without any safety mechanisms, achieved 41%
coverage but incurred 13,880 safety violations on average. Introducing an
explicit penalty of -100 for violating safety constraints (Baseline B) reduced
the coverage to only 0.01% but did successfully prevent any safety violations.

In our Approach A, agents achieved 39% coverage (2% less than Baseline A)
while completely avoiding any safety violations. This demonstrates that safe
tracking control allows the agents to learn policies that respect safety
constraints without significantly compromising task performance and without
the need for explicit constraint violation penalties. Adding an explicit
penalty for safety violations to the safe tracking control (Approach B)
reduced coverage to 16% while still avoiding violations. Further adding
episode truncation when violating safety (Approach C) increased coverage to
22% while maintaining zero violations.

##  VIII Discussion

Our work presents a novel hybrid approach that combines MARL with control-
theoretic methods to address a complex cooperative task while ensuring safety
guarantees. The theoretical analysis provides three key results. First, we
prove that each agent’s setpoint update only affects the safety of its one-hop
neighboring agents, enabling decentralized coordination. Second, we establish
that Algorithm 1 guarantees the preservation of the safety condition for all
agents under specific assumptions. Third, we derive an analytical condition to
efficiently evaluate potential safety violations during setpoint updates.

The experimental results highlight the importance of our hybrid approach.
Agents trained without any safety mechanisms (Baseline A) achieved high task
coverage but incurred numerous safety violations. Introducing an explicit
penalty for violating safety constraints (Baseline B) successfully prevented
violations but at the cost of significantly compromised task performance. In
contrast, our Approach A, which incorporates the safe tracking control system
based on Algorithm 1, allowed agents to learn policies that respect safety
constraints while maintaining reasonable task coverage, without explicit
constraint violation penalties.

Despite these strengths, there are some limitations to our current work. While
we have demonstrated the approach’s effectiveness on the network bridging
task, we have not extensively evaluated its scalability to significantly
larger swarm sizes or other domains. Moving forward we plan to investigate the
scalability and adaptability of our approach across different domains and with
varying swarm sizes.

## References

  * [1] I. ElSayed-Aly, S. Bharadwaj, C. Amato, R. Ehlers, U. Topcu, and L. Feng, “Safe multi-agent reinforcement learning via shielding,” arXiv preprint arXiv:2101.11196, 2021.
  * [2] L. Dai, Q. Cao, Y. Xia, and Y. Gao, “Distributed mpc for formation of multi-agent systems with collision avoidance and obstacle avoidance,” Journal of the Franklin Institute, vol. 354, no. 4, pp. 2068–2085, 2017.
  * [3] Y. Li, N. Li, H. E. Tseng, A. Girard, D. Filev, and I. Kolmanovsky, “Safe reinforcement learning using robust action governor,” in Learning for Dynamics and Control, pp. 1093–1104, PMLR, 2021.
  * [4] Z. Gao, G. Yang, and A. Prorok, “Online control barrier functions for decentralized multi-agent navigation,” in 2023 International Symposium on Multi-Robot and Multi-Agent Systems (MRS), pp. 107–113, IEEE, 2023.
  * [5] N. Kochdumper, H. Krasowski, X. Wang, S. Bak, and M. Althoff, “Provably safe reinforcement learning via action projection using reachability analysis and polynomial zonotopes,” IEEE Open Journal of Control Systems, vol. 2, pp. 79–92, 2023.
  * [6] R. Romagnoli, B. H. Krogh, D. de Niz, A. D. Hristozov, and B. Sinopoli, “Software rejuvenation for safe operation of cyber–physical systems in the presence of run-time cyberattacks,” IEEE Transactions on Control Systems Technology, 2023.
  * [7] R. Galliera, T. Möhlenhof, A. Amato, D. Duran, K. B. Venable, and N. Suri, “Distributed autonomous swarm formation for dynamic network bridging,” in (To Appear) The 17th International Workshop on Networked Robotics and Communication Systems (IEEE INFOCOM), 2024.
  * [8] H. K. Khalil, Nonlinear systems; 3rd ed. Upper Saddle River, NJ: Prentice-Hall, 2002.
  * [9] A. Chen, K. Mitsopoulos, and R. Romagnoli, “Reinforcement learning-based optimal control and software rejuvenation for safe and efficient uav navigation,” in 2023 62nd IEEE Conference on Decision and Control (CDC), pp. 7527–7532, IEEE, 2023.
  * [10] D. S. Bernstein, R. Givan, N. Immerman, and S. Zilberstein, “The complexity of decentralized control of markov decision processes,” Mathematics of operations research, vol. 27, no. 4, pp. 819–840, 2002.
  * [11] F. A. Oliehoek and C. Amato, A Concise Introduction to Decentralized POMDPs.  SpringerBriefs in Intelligent Systems, Springer International Publishing, 2016.
  * [12] F. A. Oliehoek, S. Whiteson, M. T. Spaan, et al., “Approximate solutions for factored dec-pomdps with many agents.,” in AAMAS, pp. 563–570, 2013.
  * [13] R. Lowe, Y. I. Wu, A. Tamar, J. Harb, O. Pieter Abbeel, and I. Mordatch, “Multi-agent actor-critic for mixed cooperative-competitive environments,” Advances in neural information processing systems, vol. 30, 2017.
  * [14] I. Gilitschenski and U. D. Hanebeck, “A robust computational test for overlap of two arbitrary-dimensional ellipsoids in fault-detection of kalman filters,” in 2012 15th International Conference on Information Fusion, pp. 396–401, IEEE, 2012.
  * [15] S. V. Albrecht, F. Christianos, and L. Schäfer, Multi-Agent Reinforcement Learning: Foundations and Modern Approaches.  MIT Press, 2023.
  * [16] J. Jiang, C. Dun, T. Huang, and Z. Lu, “Graph convolutional reinforcement learning,” in International Conference on Learning Representations, 2020.
  * [17] P. Veličković, G. Cucurull, A. Casanova, A. Romero, P. Liò, and Y. Bengio, “Graph attention networks,” in International Conference on Learning Representations, 2018.
  * [18] M. J. Hausknecht and P. Stone, “Deep recurrent q-learning for partially observable mdps,” in 2015 AAAI Fall Symposia, Arlington, Virginia, USA, November 12-14, 2015, pp. 29–37, AAAI Press, 2015.
  * [19] Z. Wang, T. Schaul, M. Hessel, H. Van Hasselt, M. Lanctot, and N. De Freitas, “Dueling network architectures for deep reinforcement learning,” in Proceedings of the 33rd International Conference on International Conference on Machine Learning - Volume 48, ICML’16, p. 1995–2003, JMLR.org, 2016.
  * [20] F. Pardo, A. Tavakoli, V. Levdik, and P. Kormushev, “Time limits in reinforcement learning,” in Proceedings of the 35th International Conference on Machine Learning (J. Dy and A. Krause, eds.), vol. 80 of Proceedings of Machine Learning Research, pp. 4045–4054, PMLR, 10–15 Jul 2018.