DECENTRALIZED NEURAL BARRIER CERTIFICATES
Year: 2021

Abstract:
We study the multi-agent safe control problem where agents should avoid collisions to static obstacles and collisions with each other while reaching their goals. Our core idea is to learn the multi-agent control policy jointly with learning the control barrier functions as safety certificates. We propose a new joint-learning framework that can be implemented in a decentralized fashion, which can adapt to an arbitrarily large number of agents. Building upon this framework, we further improve the scalability by incorporating neural network architectures that are invariant to the quantity and permutation of neighboring agents. In addition, we propose a new spontaneous policy refinement method to further enforce the certificate condition during testing. We provide extensive experiments to demonstrate that our method significantly outperforms other leading multi-agent control approaches in terms of maintaining safety and completing original tasks. Our approach also shows substantial generalization capability in that the control policy can be trained with 8 agents in one scenario, while being used on other scenarios with up to 1024 agents in complex multi-agent environments and dynamics. Videos and source code can be found on the website1.

heading: 1 INTRODUCTION
text: Machine learning (ML) has created unprecedented opportunities for achieving full autonomy. However, learning-based methods in autonomous systems (AS) can and do fail due to the lack of formal guarantees and limited generalization capability, which poses significant challenges for developing safety-critical AS, especially large-scale multi-agent AS, that are provably dependable.
On the other side, safety certificates (Chang et al. (2019); Jin et al. (2020); Choi et al. (2020)), which widely exist in control theory and formal methods, serve as proofs for the satisfaction of the desired properties of a system, under certain control policies. For example, once found, a Control Barrier Function (CBF) ensures that the closed-loop system always stays inside some safe set (Wieland & Allgöwer, 2007; Ames et al., 2014) with a CBF Quadratic Programming (QP) supervisory controller. However, it is extremely difficult to synthesize CBF by hand for complex dynamic systems, which stems a growing interest in learning-based CBF (Saveriano & Lee, 2020; Srinivasan et al., 2020; Jin et al., 2020; Boffi et al., 2020; Taylor et al., 2020; Robey et al., 2020). However, all of these studies only concern single-agent systems. How to develop learning-based approaches for safe multi-agent control that are both provably dependable and scalable remains open.
In multi-agent control, there is a constant dilemma: centralized control strategies can hardly scale to a large number of agents, while decentralized control without coordination often misses safety and performance guarantees. In this work, we propose a novel learning framework that jointly designs multi-agent control policies and safety certificate from data, which can be implemented in a decentralized fashion and scalable to an arbitrary number of agents. Specifically, we first introduce the notion of decentralized CBF as safety certificates, then propose the framework of learning decentralized CBF, with generalization error guarantees. The decentralized CBF can be seen as a
1https://realm.mit.edu/blog/learning-safe-multi-agent-control-decentralized-neural-barrier-certificates
contract among agents, which allows agents to learn a mutual agreement with each other on how to avoid collisions. Once such a controller is achieved through the joint-learning framework, it can be applied on an arbitrarily number of agents and in scenarios that are different from the training scenarios, which resolves the fundamental scalability issue in multi-agent control. We also propose several effective techniques in Section 4 to make such a learning process even more scalable and practical, which are then validated extensively in Section 5.
Experimental results are indeed promising. We study both 2D and 3D safe multi-agent control problems, each with several distinct environments and complex nonholonomic dynamics. Our jointlearning framework performs exceptionally well: our control policies trained on scenarios with 8 agents can be used on up to 1024 agents while maintaining low collision rates, which has notably pushed the boundary of learning-based safe multi-agent control. Speaking of which, 1024 is not the limit of our approach but rather due to the limited computational capability of our laptop used for the experiments. We also compare our approach with both leading learning-based methods (Lowe et al., 2017; Zhang & Bastani, 2019; Liu et al., 2020) and traditional planning methods (Ma et al., 2019; Fan et al., 2020). Our approach outperforms all the other approaches in terms of both completing the tasks and maintaining safety.
Contributions. Our main contributions are three-fold: 1) We propose the first framework to jointly learning safe multi-agent control policies and CBF certificates, in a decentralized fashion. 2) We present several techniques that make the learning framework more effective and scalable for practical multi-agent systems, including the use of quantity-permutation invariant neural network architectures in learning to handle the permutation of neighbouring agents. 3) We demonstrate via extensive experiments that our method significantly outperforms other leading methods, and has exceptional generalization capability to unseen scenarios and an arbitrary number of agents, even in quite complex multi-agent environments such as ground robots and drones. The video that demonstrates the outstanding performance of our method can be found in the supplementary material.
Related Work. Learning-Based Safe Control via CBF. Barrier certificates (Prajna et al., 2007) and CBF (Wieland & Allgöwer, 2007) is a well-known effective tool for guaranteeing the safety of nonlinear dynamic systems. However, the existing methods for constructing CBFs either rely on specific problem structures (Chen et al., 2017b) or do not scale well (Mitchell et al., 2005). Recently, there has been an increasing interest in learning-based and data-driven safe control via CBFs, which primarily consist of two categories: learning CBFs from data (Saveriano & Lee, 2020; Srinivasan et al., 2020; Jin et al., 2020; Boffi et al., 2020), and CBF-based approach for controlling unknown systems (Wang et al., 2017; 2018; Cheng et al., 2019; Taylor et al., 2020). Our work is more pertinent to the former and is complementary to the latter, which usually assumes that the CBF is provided. None of these learning-enabled approaches, however, has addressed the multi-agent setting.
Multi-Agent Safety Certificates and Collision Avoidance. Restricted to holonomic systems, guaranteeing safety in multi-agent systems has been approached by limiting the velocities of the agents (Van den Berg et al., 2008; Alonso-Mora et al., 2013). Later, Borrmann et al. (2015) Wang et al. (2017) have proposed the framework of multi-agent CBF to generate collision-free controllers, with either perfectly known system dynamics (Borrmann et al., 2015), or with worst-case uncertainty bounds (Wang et al., 2017). Recently, Chen et al. (2020) has proposed a decentralized controller synthesized approach under this CBF framework, which is scalable to an arbitrary number of agents. However, in Chen et al. (2020) the CBF controller relies on online integration of the dynamics under the backup strategy, which can be computationally challenging for complex systems. Due to space limit, we omit other non-learning multi-agent control methods but acknowledge their importance.
Safe Multi-Agent (Reinforcement) Learning (MARL). Safety concerns have drawn increasing attention in MARL, especially with the applications to safety-critical multi-agent systems (Zhang & Bastani, 2019; Qie et al., 2019; Shalev-Shwartz et al., 2016). Under the CBF framework, Cheng et al. (2020) considered the setting with unknown system dynamics, and proposed to design robust multiagent CBFs based on the learned dynamics. This mirrors the second category mentioned above in single-agent learning-based safe control, which is perpendicular to our focus. RL approaches have also been applied for multi-agent collision avoidance (Chen et al., 2017a; Lowe et al., 2017; Everett et al., 2018; Zhang et al., 2018). Nonetheless, no formal guarantees of safety were established in these works. One exception is Zhang & Bastani (2019), which proposed a multi-agent model predictive shielding algorithm that provably guarantees safety for any policy learned from MARL, which differs from our multi-agent CBF-based approach. More importantly, none of these MARL-
based approaches scale to a massive number of, e.g., thousands of agents, as our approach does. The most scalable MARL platform, to the best of our knowledge, is Zheng et al. (2017), which may handle a comparable scale of agents as ours, but with discrete state-action spaces. This is in contrast to our continuous-space models that can model practical control systems such as robots and drones.

heading: 2 PRELIMINARIES

heading: 2.1 CONTROL BARRIER FUNCTIONS AS SAFETY CERTIFICATES
text: One common approach for (single-agent) safety certificate is via control barrier functions (Ames et al., 2014), which can enforce the states of dynamic systems to stay in the safe set. Specifically, let S ⊂ Rn be the state space, Sd ⊂ S is the dangerous set, Ss = S\Sd is the safe set, which contains the set of initial conditions S0 ⊂ Ss. Also define the space of control actions as U ⊂ Rm. For a dynamic system ṡ(t) = f(s(t), u(t)), a control barrier function h : Rn 7→ R satisfies:
(∀s ∈ S0, h(s) ≥ 0) ∧ (∀s ∈ Sd, h(s) < 0) ∧ (∀ s ∈ {s | h(s) ≥ 0} ,∇sh · f(s, u) + α (h) ≥ 0) , (1)
where α(·) is a class-K function, i.e., α(·) is strictly increasing and satisfies α(0) = 0. For a control policy π : S → U and CBF h, it is proved in Ames et al. (2014) that if s(0) ∈ {s | h(s) ≥ 0} and the three conditions in (1) are satisfied with u = π(x), then s(t) ∈ {s | h(s) ≥ 0} for ∀t ∈ [0,∞), which means the state would never enter the dangerous set Sd under π.

heading: 2.2 SAFETY OF MULTI-AGENT DYNAMIC SYSTEMS
text: Consider a multi-agent system with N agents, the joint state of which at time t is denoted by s(t) = {s1(t), s2(t), · · · , sN (t)} where si(t) ∈ Si ⊂ Rn denotes the state of agent i at time t. The dynamics of agent i is ṡi(t) = fi(si(t), ui(t)) where ui(t) ∈ Ui ⊂ Rm is the control action of agent i. The overall state space and input space are denoted as S .= N⊗
i=1 Si, U .= N ⊗ i=1 Ui. For each agent i,
we define Ni(t) as the set of its neighborhood agents at time t. Let oi(t) ∈ Rn×|Ni(t)| be the local observation of agent i, which is the states of |Ni(t)| neighborhood agents. Notice that the dimension of oi(t) is not fixed and depends on the quantity of neighboring agents. We assume that the safety of agent i is jointly determined by si and oi. Let Oi be the set of all possible observations and Xi := Si ×Oi be the state-observation space that contains the safe set Xi,s, dangerous set Xi,d and initial conditions Xi,0 ⊂ Xi,s. Let d : Xi → R describe the minimum distance from agent i to other agents that it observes, d(si, oi) < κs implies collision. Then Xi,s = {(si, oi)|d(si, oi) ≥ κs} and Xi,d = {(si, oi)|d(si, oi) < κs}. Let d̄i : S → R be the lifting of d from Xi to S, which is welldefined since there is a surjection from S to Xi. Then define Ss . = {s ∈ S|∀i = 1, ..., N, d̄i(s) ≥ κs}. The safety of a multi-agent system can be formally defined as follows: Definition 1 (Safety of Multi-Agent Systems). If the state-observation satisfies d(si, oi) ≥ κs for agent i and time t, then agent i is safe at time t. If for ∀i, agent i is safe at time t, then the multi-agent system is safe at time t, and s ∈ Ss.
A main objective of this paper is to learn the control policy πi(si(t), oi(t)) for ∀i such that the multi-agent system is safe. The control policy is decentralized (i.e., each agent has its own control policy and there does not exist a central controller to coordinate all the agents). In this way, our decentralized approach has the hope to scale to very a large number of agents.

heading: 3 LEARNING FRAMEWORK FOR MULTI-AGENT DECENTRALIZED CBF

heading: 3.1 DECENTRALIZED CONTROL BARRIER FUNCTIONS
text: For a multi-agent dynamic system, the most naı̈ve CBF would be a centralized function taking into account the cross production of all agents’ states, which leads to an exponential blow-up in the state space and difficulties in modeling systems with an arbitrary number of agents. Instead, we consider a decentralized control barrier function hi : Xi 7→ R:
(∀ (si, oi) ∈ Xi,0, hi(si, oi) ≥ 0) ∧ (∀ (si, oi) ∈ Xi,d, hi(si, oi) < 0) ∧ (∀ (si, oi) ∈ {(si, oi) | hi(si, oi) ≥ 0} ,∇sihi · fi(si, ui) +∇oihi · ȯi(t) + α (hi) ≥ 0) (2)
where ȯi(t) is the time derivative of the observation, which depends on the behavior of other agents. Although there is no explicit expression of this term, it can be evaluated and incorporated in the learning process. Note that the CBF hi(si, oi) is local in the sense that it only depends on the local state si and observation oi. We refer to the three conditions in (2) as decentralized CBF conditions. The following proposition shows that satisfying (2) guarantees the safety of the multi-agent system. Proposition 1 (Multi-Agent Safety Certificates with Decentralized CBF). If for ∀i, the initial stateobservation (si(0), oi(0)) ∈ {(si, oi) | hi(si, oi) ≥ 0} and the decentralized CBF conditions in (2) are satisfied, then ∀i and ∀t, (si(t), oi(t)) ∈ {(si, oi) | hi(si, oi) ≥ 0}, which implies the state would never enter Xi,d for any agent i. Thus, by Definition 1, the multi-agent system is safe.
The proof of Proposition 1 is provided in the supplementary material. The key insight of Proposition 1 is that for the whole multi-agent system, the CBFs can be applied in a decentralized fashion for each agent. Since hi(si, oi) ≥ 0 is invariant, by definition of hi, hi(si, oi) > 0 =⇒ d̄i(s) ≥ κs, which means agent i never gets closer than κs to all its neighborhood agents. Therefore, ∀i, hi(si, oi) ≥ 0 implies that ∀i, d̄i(s) ≥ κs, which by definition also means s ∈ Ss, and the multi-agent system is safe as defined in Definition 1.
Notice that an agent only needs to care about its local information, and if all agents respect the same form of contract (i.e., the decentralized CBF conditions), the whole multi-agent system will be safe. The fact that global safety can be guaranteed by decentralized CBF is of great importance since it reveals that a centralized controller that coordinates all agents is not necessary to achieve safety. A centralized control policy has to deal with the dimension explosion when the number of agents grow, while a decentralized design can significantly improve the scalability to a large number of agents.

heading: 3.2 LEARNING FRAMEWORK
text: From Proposition 1, we know that if we can jointly learn the control policy πi(si, oi) and control barrier function hi(si, oi) such that the decentralized CBF conditions in (2) are satisfied, then the multiagent system is guaranteed to be safe. Next we formulate the optimization objective for the joint learning of πi(si, oi) and hi(si, oi). Let T ⊂ R+ be the time interval and τi = {si(t), oi(t)}t∈T be a trajectory of state and observation of agent i. Let Ti be the set of all possible trajectories of agent i. LetHi and Vi be the function classes of hi and πi. Define the function yi : Ti×Hi×Vi 7→ R as:
yi(τi, hi, πi) := min {
inf Xi,0∩τi hi(si, oi), inf Xi,d∩τi −hi(si, oi), inf Xi,h∩τi
(ḣi + α (hi)) } . (3)
The setXi,h := {(si, oi) | hi(si, oi) ≥ 0}. Notice that the third item on the right side of Equation (3) depends on both the control policy and CBF, since ḣi = ∇sihi · fi(si, ui) + ∇oihi · ȯi(t), ui = πi(si, oi). It is clear that if we can find hi and πi(si, oi) such that yi(τi, hi, πi) > 0 for ∀τi ∈ Ti and ∀i, then the conditions in (2) are satisfied. For each agent i, assume that we are given zi i.i.d trajectories {τ1i , τ2i , · · · , τ zi i } drawn from distribution Di during training. We solve the objective:
For all i, find hi ∈ Hi and πi ∈ Vi, s.t. yi(τ ji , hi, πi) ≥ γ, ∀j = 1, 2, · · · zi, (4) where γ > 0 is a margin for the satisfaction of the CBF condition in (2). Following standard results from statistical learning theory, it is possible to establish the generalization guarantees of the solution to (4) to unseen data drawn from Di. See a detailed statement of the results in Appendix B. The bound depends on the richness of the function classes, the margin γ, as well as the number of samples used in (4). However, we note that such a generalization bound is only with respect to the open-loop data drawn fromDi, the training data distribution, not to the closed-loop data in the testing when the learned controller is deployed. It is known to be challenging to handle the distribution shift between the training and testing due to the closed-loop effect. See, e.g., a recent result along this line in the context of imitation learning (Tu et al., 2021). We leave a systematic treatment of this closed-loop generalization guarantee for learning CBF in our future work. Finally, we note that in our experiments, we solve (4) and update the controller in an iterative fashion: run the closed-loop system with a certain controller to sample training data online and formulate (4), then update the controller by the solution of (4). We run the system using the updated controller and re-generate new samples to solve for a new controller. At the steady stage of this iterative process, the training and testing distribution shift becomes negligible, which validates the use of the generalization bounds given in Proposition 3. See more details of this implementation in Section 4.1, and more discussion on this point in the Remark in Appendix B.
Besides the generalization guarantee, there also exists several other gaps between the formulation in (4) and the practical implementation. First, (4) does not provide a concrete way of designing loss functions to realize the optimization objectives. Second, there are still N pairs of functions (hi, πi) to be learned. Unfortunately, the dimension of the input oi of the functions hi, πi are different for each agent i, and will even change over time in practice, as the proximity of other agents is timevarying, leading to time-varying local observations. To scale to an arbitrary number of agents, hi and πi should be invariant to the quantity and permutation of neighbourhood agents. Third, (4) does not provide ways to deal with scenarios where the decentralized CBF conditions are not (strictly) satisfied, i.e., where problem (4) is not even feasible, which may very likely occur when the system becomes too complex or the function classes are not rich enough. To this end, we propose effective approaches to solving these issues, facilitating the scalable learning of safe multi-agent control in practice, as to be introduced next.

heading: 4 SCALABLE LEARNING OF DECENTRALIZED CBF IN PRACTICE
text: Following the theory in Section 3, we consider the practical learning of safe multi-agent control with neural barrier certificates, i.e., using neural networks for H and V . We will present the formulation of loss functions in Section 4.1, which corresponds to the objective in (4). Section 4.2 presents the neural network architecture of hi and πi, which are invariant to the quantity and permutation of neighboring agents. Section 4.3 demonstrates a spontaneous policy refinement method that enables the control policy to satisfy the decentralized CBF conditions as possible as it could during testing.

heading: 4.1 LOSS FUNCTIONS OF JOINTLY LEARNING CONTROLLERS AND BARRIER CERTIFICATES
text: Based on Section 3.2. the main idea is to jointly learn the control policies and control barrier functions in multi-agent systems. During training, the CBFs regulate the control policies to satisfy the decentralized CBF conditions (2) so that the learned policies are safe. All agents are put into a single environment to generate experiences, which are combined to minimize the empirical loss function Lc = ΣiLci , where Lci is the loss function for agent i formulated as:
Lci (θi, ωi) = ∑
si∈Xi,0
max ( 0, γ − hθii (si, oi) ) + ∑ si∈Xi,d max ( 0, γ + hθii (si, oi) ) +
∑ si∈Xi,h max ( 0, γ −∇sih θi i · fi (si, π ωi i (si, oi))−∇oih θi i · ȯi − α(h θi i ) ) ,
(7)
where γ is the margin defined in Section 3.2. We choose γ = 10−2 in implementation. θi and ωi are neural network parameters. On the right side of Equation (7), the three items enforce the three CBF conditions respectively. Directly computing the third term could be challenging since we need to evaluate ȯi, which is the time derivative of the observation. Instead, we approximate ḣ(si, oi) = ∇sih θi i ·fi (si, π ωi i (si, oi))+∇oih θi i ·ȯi numerically by ḣ(si, oi) = [h(si(t+∆t), oi(t+ ∆t)) − h(si(t), oi(t))]/∆t. For the class-K function α(·), we simply choose a linear function α(h) = λh. Note that Lc mainly considers safety instead of goal reaching. To train a safe control policy πi(si, oi) that can drive the agent to the goal state, we also minimize the distance between ui and ugi , where u g i is the reference control input computed by classical approaches (e.g., LQR and PID controllers) to reach the goal. The goal reaching loss Lg = ΣiLgi , where L g i is formulated as
Lgi (ωi) = ∑ si∈X ||π ωi i (si, oi) − u g i (si)||2. The final loss function L = Lc + ηLg , where η is a balance weight that is set to 0.1 in our experiments. We present the computational graph in Figure 1 to help understand the information flow.
In training, all agents are put into the specific environment, which is not necessarily the same as the testing environment, to collect state-observation pairs (si, oi) under their current policies with
probability 1− ι and random policies with probability ι, where ι is set to be 0.05 in our experiment. The collected (si, oi) are stored as a temporary dataset and in every step of policy update, 128 (si, oi) are randomly sampled from the temporary dataset to calculate the total loss L. We minimize L by applying stochastic gradient descent with learning rate 10−3 and weight decay 10−6 to θi and ωi, which are the parameters of the CBF and control policies. Note that the gradients are computed by back-propagation rather than policy gradients because L is differentiable w.r.t. θi and ωi.
Iterative Data Collection and Training. It is important to note that we did not use a fixed set of state-observation pairs to train the decentralized CBF and controllers. Instead, we adopted an on-policy training strategy, where the training data are collected by running the current system. The collected state-observation pairs are stored in temporary dataset that is used to calculate the loss terms and update the decentralized CBF and controllers via gradient descent. Then the updated controllers are used to run the system and re-generate new state-observation pairs as training data. The iterative data collection and training is performed until the loss converges. Such a training process is crucial for generalizing to testing scenarios. More discussion on this point can be found in the Remark in Appendix B.

heading: 4.2 QUANTITY-PERMUTATION INVARIANT OBSERVATION ENCODER
text: Recall that in Section 3.1, we define oi as the local observation of agent i. oi contains the states of neighboring agents and its dimension can change dynamically. In order to scale to an arbitrary number of agents, there are two pivotal principles of designing the neural network architectures of hi(si, oi) and πi(si, oi). First, the architecture should be able to dynamically adapt to the changing quantity of observed agents that affects the dimension of oi. Second, the architecture should be invariant to the permutation of observed agents, which should not affect the output of hi or πi. All these challenges arise from encoding the local observation oi. Inspired by PointNet (Qi et al., 2017), we leverage the max pooling layer to build the quantity-permutation invariant observation encoder.
Let us start with a simple example with input observation oi(t) ∈ Rn×|Ni(t)|, where n is the dimension of state and Ni(t) is the set of the neighboring agents at time t. n is fixed while Ni(t) can change from time to time. The permutation of the columns of oi is also dynamic. Denote the weight matrix as W ∈ Rp×n and the element-wise ReLU activation function as σ(·). Define the row-wise max pooling operation as RowMax(·), which takes a matrix as input and outputs the maximum value of each row. Consider the following mapping ρ : Rn×|Ni(t)| 7→ Rp formulated as
ρ(oi) = RowMax(σ(Woi)), (8) where ρ maps a matrix oi whose column has dynamic dimension and permutation to a fixed length feature vector ρ(oi) ∈ Rp. The dimension of ρ(oi) remains the same even if the number of columns of oi(t), which is |Ni(t)|, change over time. The network architecture of the control policy is shown in Figure 2, which uses the RowMax(·) operation. The network of the control barrier function is similar except that the output is a scalar instead of a vector.

heading: 4.3 SPONTANEOUS ONLINE POLICY REFINEMENT
text: We propose a spontaneous online policy refinement approach that produces even safer control policies in testing than the neural network has actually learned during training. When the model dynamics or environment settings are too complex and exceed the capability of the control policy, the
decentralized CBF conditions can be violated at some points along the trajectories. Thanks to the control barrier function jointly learned with the control policy, we are able to refine the control input ui online by minimizing the violation of the decentralized CBF conditions. That is, the learned CBF can serve as a guidance on generating updated ui in unseen scenarios to guarantee safety. This is also a standard technique used in (non-learning) CBF control where the CBF h is usually computed first using optimization methods like Sum-of-Squares, then the control inputs u are computed online using h by solving quadratic programming problems (Xu et al., 2017; Ames et al., 2017). In the experiments, we also study the effects of such an online policy refinement step.
Given the state si, local observation oi, and action ui computed by the control policy, consider the scenario where the third CBF condition is violated, which means ∇sihi · fi(si, ui) +∇oihi · ȯi + α(hi) < 0 when hi ≥ 0. Let ei ∈ Rm be an increment of the action ui. Define φ(ei) : Rm 7→ R as
φ(ei) = max(0,−∇sihi · fi(si, ui + ei)−∇oihi · ȯi − α(hi)) + µ||ei||22. (9) If the first term on the right side of Equation (9) is 0, then the third CBF condition is satisfied. We can enforce the satisfaction in every timestep of testing (after ui is computed by the neural network controller) by finding an ei that minimizes φ(ei). µ is a regularization factor that punishes large ei. We set µ = 1 in implementation and observed that in our experiment, a fixed µ is sufficient to make sure the ||ui + ei|| do not exceed the constraint on control input bound. When evaluating on new scenarios and the constraints is violated, one can dynamically increase µ to strengthen the penalty. For every timestep during testing, we initialize ei to zero and check the value of φ(ei). φ(ei) > 0 indicates that the control policy is not good enough to satisfy the decentralized CBF conditions. Then we iteratively refine ei by ei = ei − ∇eφ(ei) until φ(ei) − µ||ei||22 = 0 or the maximum allowed iteration is exceeded. The final control input is ui = ui+ ei. Such a refinement can flexibly refine the control input to satisfy the decentralized CBF conditions as much as possible.

heading: 5 EXPERIMENTAL RESULTS
text: Baseline Approaches. The baseline approaches we compare with include: MAMPS (Zhang & Bastani, 2019), PIC (Liu et al., 2020) and MADDPG (Lowe et al., 2017). For the drone tasks, we also compare with model-based planning method S2M2 (Chen et al., 2021). A brief description of each method is as follows. MAMPS leverages the model dynamics to iteratively switch to safe control policies when the learned policies are unsafe. PIC proposes the permutation-invariant critic to enhance the performance of multi-agent RL. We incorporate the safety reward to its reward function and denote this safe version of PIC as PIC-Safe. The safety reward is -1 when the agent enters the dangerous set. MADDPG is a pioneering work on multi-agent RL, and MADDPG-Safe is obtained by adding the safety reward to the reward function that is similar to PIC-Safe. S2M2 is a state-of-the-art model-based multi-agent safe motion planner. When directly planning all agents fails, S2M2 evenly divides the agent group to smaller partitions for replanning until paths that are collision-free for each partition are found. The agents then follow the generated paths using PID or LQR controllers.
For each task, the environment model is the same for all the methods. The exact model dynamics are visible to model-based methods including MAMPS, S2M2 and our methods, and invisible to the
model-free MADDPG and PIC. Since the model-free methods do not have access to model dynamics but instead the simulators, they are more data-demanding. The number of state-observation pairs to train MADDPG and PIC is 103 times more than that of model-based learning methods to make sure they converge to their best performance. When training the RL-based methods, the control action computed by LQR for goal-reaching is also fed to the agent as one of the inputs to the actor network. So the RL agents can learn to use LQR as a reference for goal-reaching.
Evaluation Criteria. Since the primal focus of this paper is the safety of multi-agent systems, we use the safety rate as a criteria when evaluating the methods. The safety rate is calculated as 1 NΣ N i=1Et∈T [I((si(t), oi(t)) ∈ Xs)] where I(·) is the indicator function that is 1 when its argument is true or 0 otherwise. The observation oi contains the states of other agents within the observation radius, which is 10 times the safe distance. The safe distance is set to be the diagonal length of the bounding box of the agent. In addition to the safety rate, we also calculate the average reward that considers how good the task is accomplished. The agent is given a +10 reward if it reaches the goal and a -1 reward if it enters the dangerous set. Note that the agent might enter the dangerous set for many times before reaching the goal. The upper-bound of the total reward for an agent is +10, which is attained when the agent successfully reaches the goal and always stays in the safe set. Ground Robots. We consider three tasks illustrated in Figure 3. In the Navigation task, each agent starts from a random location and aims to reach a random goal. In the Predator-Prey task, the preys aim to gather the food while avoid being caught by the predators chasing the preys. We only consider the safety of preys but not predators. In the Nested-Rings task, the agents aim to follow
the reference trajectories while avoid collision. In order for the RL-based agents to follow the rings trajectory, we also give the agents a negative reward proportional to the distance to the nearest point on the rings. When adding more agents to an environment, we will also enlarge the area of the environment to ensure the overall density of agents remains similar.
Figure 4 demonstrates that when the number of agents grows (e.g., 32 agents), our approach (MDBC) can still maintain a high safety rate and average reward, while other methods have much worse performance. However, our method still cannot guarantee that the agents are 100% safe. The failure is mainly because we cannot make sure the decentralized CBF conditions are satisfied for every state-observation pair in testing even if they are satisfied on all training samples due to the generalization error. We also show the generalization capability of MDBC with up to 1024 in the appendix and also visualization results in the supplementary materials.
Drones. We experiment with 3D drones whose dynamics are even more complex. Figure 5 demonstrates the environments and the results of each approach. Similar to the results of ground robots, when there are a large number of agents (e.g., 32 agents), our method can still maintain a high reward and safety rate, while other methods have worse performance. Figure 6 shows the generalization capability of our method across different environments and number of agents. For each experiment, we train 8 agents during training, but test with up to 1024 agents. The extra agents are added by copying the neural network parameters of the trained 8 agents. Results show that our method has remarkable generalization capability to diverse
scenarios. Another related work Chen et al. (2020) can also handle the safe multi-drone control problem via CBF, but their CBF is handcrafted and based on quadratic programming to solve the ui. Their paper only reported the results on two agents, and for 32 agents it would take more than 70 hours for a single run of evaluation (7000 steps and 36 seconds per step). By contrast, our method only takes ∼ 200s for a single run of evaluation with 32 agents, showing a significant advantage in computational efficiency. For both the ground robot and drone experiments, we provide video demonstrations in the supplementary material.

heading: 6 CONCLUSION
text: This paper presents a novel approach of learning safe multi-agent control via jointly learning the decentralized control barrier functions as safety certificates. We provide the theoretical generalization bound, as well as the effective techniques to realize the learning framework in practice. Experiments show that our method significantly outperforms previous methods by being able to scale to an arbitrary number of agents, and demonstrates remarkable generalization capabilities to unseen and complex multi-agent environments.

heading: 7 ACKNOWLEDGEMENT
text: The authors would like to thank Nikolai Matni for the valuable discussions. The authors acknowledge support from the DARPA Assured Autonomy under contract FA8750-19-C-0089. The views, opinions and/or findings expressed are those of the authors and should not be interpreted as representing the official views or policies of the Department of Defense or the U.S. Government.

heading: A PROOF OF PROPOSITION 1
text: Since ḣi = ∇sihi · fi(si, ui) +∇oihi · ȯi(t), the satisfaction of (2) implies:
∀ (si, oi) ∈ Xi,0, hi(si, oi) ≥ 0 ∀ (si, oi) ∈ Xi,d, hi(si, oi) < 0 ∀ (si, oi) ∈ {(si, oi) | hi(si, oi) ≥ 0} , ḣi + α (hi) ≥ 0.
(10)
The initial condition (si(0), oi(0)) ∈ {(si, oi) | hi(si, oi) ≥ 0} means that hi ≥ 0 at time t = 0. Since ḣi+α (hi) ≥ 0, hi will stay non-negative, which is proved in Section 2 of Ames et al. (2014). This means that (si(t), oi(t)) /∈ Xi,d for ∀t > 0. Thus for ∀i and ∀t > 0, agent i would not enter the dangerous set, and the whole multi-agent system is safe by Definition 1.
Remark. Since the input dimension and permutation of hi can change with time, the time derivative of hi does not exist everywhere but almost everywhere. In fact, in the safety guarantee provided by Proposition 1, we do not require the time derivative of hi to exist everywhere. The hi can also be non-smooth. Based on (2) of Glotfelter et al. (2017), we can define ḣi as the generalized gradient that always exists when hi is non-smooth and the time derivative exists almost everywhere. Then based on Theorem 2 of Glotfelter et al. (2017), as long as the CBF conditions are satisfied under the generalized gradient, then hi is a valid CBF and the safety can be guaranteed.
Global CBF from decentralized CBFs. In addition to Proposition 1, another way to prove the global safety of the multi-agent system under the decentralized CBFs is to construct the global CBF hg : S 7→ R from individual CBFs by taking the minimum, as is in:
hg(s) := min{h1(s ↓ s1, s ↓ o1), h2(s ↓ s2, s ↓ o2), · · · , hN (s ↓ sN , s ↓ oN )}, (11)
where s ↓ si is the projection of the global state onto the state of agent i and s ↓ oi is the projection of the global state to the observation of agent i. Then the following proposition guarantees the global safety of the multi-agent system. Proposition 2. If (10) is satisfied for every agent i, then the global CBF hg(s) satisfies:
∀ s ∈ S0, hg(s) ≥ 0 ∀ s ∈ Sd, hg(s) < 0 ∀ s ∈ {s | hg(s) ≥ 0} , ḣg + α (hg) ≥ 0,
(12)
where S0 = {s ∈ S|∀i, (s ↓ si, s ↓ oi) ∈ Xi,0} and Sd = {s ∈ S|∃i, (s ↓ si, s ↓ oi) ∈ Xi,d}. Then ∀t > 0, hg(s(t)) ≥ 0 and s 6∈ Sd, which means the multi-agent system is globally safe.
Proof. Let us first prove that the satisfaction of (10) implies the satisfaction of (12). By definition of S0, when s ∈ S0, we have ∀i, (s ↓ si, s ↓ oi) ∈ Xi,0, which means ∀i, hi(s ↓ si, s ↓ oi) ≥ 0. Thus hg(s) = mini{hi(s ↓ si, s ↓ oi)} ≥ 0. When s ∈ Sd, we have ∃i, (s ↓ si, s ↓ oi) ∈ Xi,d, which means ∃i, hi(s ↓ si, s ↓ oi) < 0. Thus hg(s) = mini{hi(s ↓ si, s ↓ oi)} < 0. When s ∈ {s | hg(s) ≥ 0}, we have ∀i, (s ↓ si, s ↓ oi) ∈ {(s ↓ si, s ↓ oi) | hi(s ↓ si, s ↓ oi) ≥ 0}. So ∀i, ḣi + α (hi) ≥ 0. Let i∗ = arg mini{hi(s ↓ si, s ↓ oi)}. Then hg(s) = hi∗(s ↓ si∗ , s ↓ oi∗) and ḣg + α (hg) = ḣi∗ + α (hi∗) ≥ 0. Hence the satisfaction of (10) implies the satisfaction of (12). Then based on Section 2 of Ames et al. (2014), we have hg(s(t)) ≥ 0,∀t > 0. This means s(t) 6∈ Sd,∀t > 0, and the multi-agent system is globally safe.

heading: B GENERALIZATION ERROR BOUND OF THE DECENTRALIZED CBF
text: To answer how well the learned πi(si, oi) and hi(si, oi) can generalize to unseen scenarios, we will provide a generalization bound with probabilistic guarantees. We denote the solution to (4) as ĥi and π̂i. Denote the Rademacher complexity of the function class of yi as Rzi(Yi), whose definition could be found in Appendix B. Also we define i as the probability that the decentralized CBF conditions are violated for agent i over randomly sampled trajectories (not necessarily the samples encountered in training). Under such definition, i measures the generalization error and
can be expressed as i = Pτi∼Di [ yi(τi, ĥi, ûi) ≤ 0 ] . Then we have Proposition 3 that provides
generalization guarantees for all the learned ĥi and π̂i. Proposition 3 (Generalization Error Bound of Learning Decentralized CBF). Assume that |y| ≤ b and (4) is feasible. Let ĥi and ûi be the solutions to (4) and µ be a universal positive constant vector. Recall that N is the number of agents. Then, for any δ ∈ (0, 1) the following statement holds:
P [ N⋂ i=1 ( i ≤ µi log3 zi γ2 R2zi(Yi) + µi log(N log(4b/γ)/δ) zi )] ≥ 1− δ. (6)
Proof. Note that i = Pτi∼Di [ yi(τi, ĥi, ûi) ≤ 0 ] = Eτi∼Di [ I ( yi(τi, ĥi, ûi) ≤ 0 )] . Under zero
empirical loss, using the Theorem 5 in Srebro et al. (2010), for any δN > 0, the following statement holds with probability at least 1− δN :
i ≤ µi log3 zi γ2 R2zi(Yi) + µi log(N log(4b/γ)/δ) zi (13)
where µi > 0 is some universal constant. By taking the union bound over allN agents, the following statement holds with probability at least (1− δN ) N :
N⋂ i=1 ( i ≤ µi log3 zi γ2 R2zi(Yi) + µi log(N log(4b/γ)/δ) zi ) . (14)
Since (1− δN ) N > 1− δ for δ ∈ (0, 1), we have:
P [ N⋂ i=1 ( i ≤ µi log3 zi γ2 R2zi(Yi) + µi log(N log(4b/γ)/δ) zi )] ≥ 1− δ, (15)
which completes the proof.
The Rademacher complexityRzi(Yi) is defined as:
Rzi(Yi) := sup τ1i ,···τ zi i ∼Di Eξ∼ Unif ({±1}zi ) sup hi∈Hi,πi∈Vi
1
zi ∣∣∣∣∣ zi∑ j=1 ξjyi(τ j i , hi, πi) ∣∣∣∣∣, where ξ ∈ Rzi is a random vector and ξj denotes its jth element. Rzi(Yi) characterizes the richness of function class Yi. The left side of Equation (6) is the probability that the generalization error i is upper bounded for all the N agents. Equation (6) claims that the generalization error is bounded for all agents with high probability 1 − δ. Similar to the discussions in Section 4 in Boffi et al. (2020), for specific function classes of Hi and Vi, such as Lipschitz parametric function or Reproducing kernel Hilbert space function classes, the Rademacher complexity of the function classes can be further bounded, leading to vanishing generalization errors as the number of samples zi increases. Such derivations are standard, and are thus omitted as they are not the focus of the present paper.
Remark. The generalization guarantee in Proposition 3 requires that the testing and training trajectories are drawn from the same distribution. Since in testing the trajectories come from the closed-loop (controller-in-the-loop) system, we should ensure that the training trajectories are also from the closed-loop system. Thus, in our implementation, the training data are not uniformly sampled from the state-observation space. Instead, the samples are drawn online under the current control policy, which is a solution to (4) using previously learned controller. We then use the updated controller to sample new data to formulate (4), and solve for an updated controller accordingly. In the experiments, we iterate this process until it converges. This way, at the steady stage of this process, the training and testing distribution shift becomes almost negligible, and the generalization results in Proposition 3 can thus be used. We leave a systematic analysis on the generalization and convergence of this iterative process in our future work.

heading: C MODEL DYNAMICS
text: In the experiment section of our main paper, we use the 2D ground robots and 3D drones. For ground robots, we use a double integrator model with state si = [xi, yi, vx,i, vy,i] for the navigation and predator-prey tasks, and the model from Rodrı́guez-Seda et al. (2014) for the nested rings task. For drones, we use the following dynamics:
si = 
xi yi zi vx,i vy,i vz,i θx,i θy,i
 , dsi dt = 
vx,i vy,i vz,i
g tan(θx,i) g tan(θy,i)
az,i ωx,i ωy,i
 , ui = [ ωx,i ωy,i az,i ] . (16)

heading: D SUPPLEMENTARY EXPERIMENT
text: For 3D drones we have shown the generalization capability to 1024 agents even when our method is trained with 8 agents (Figure 6). For 2D ground robots we have similar results that were omitted in the main paper due to space limitations. We present the results in Figure 8 as below. Our method demonstrates the exceptional generalization capability to testing scenarios where the number of agents is significantly greater than that in training. The safety rate and average reward remain high even when the number of agents grow exponentially.
Ablation Study on Online Policy Refinement. In Section 4.3, we introduced a test-time policy refinement method. Here we study the effect of this method on our performance and present the results in Table 1. It is shown that even without the OPR, the safety rate is still promising. The OPR further improved the safety rate. The steps requiring OPR in testing only accounts for a small proportion (< 17%) of the total steps. The proportion gradually becomes saturated and does not significantly increase as the number of agents grow.
Visualization of the Learned CBF. To have a better understanding of the learned decentralized CBF, we provide a visualization in Figure 9. The CBF is learned in the Maze environment with two agents, in order to simplify the interpretation. The relative distance is defined in the 3D Euclidean space. The relative velocity is the negative time derivative of the relative distance. When the relative velocity is positive, the two agents are getting close to each other. From Figure 9, we know that the learned CBF is negative on the dangerous states (the red area) and the potentially dangerous states (the top-right area), where the agents are moving towards each other. The CBF is positive only when the states are sufficiently safe (the bottom-right area).

Review summaries:
This paper extends the neural barrier certificate method from reinforcement learning to  the decentralized multi-agent reinforcement learning setting. In particular,  it borrows the idea of the control barrier function, which enforces the states of the dynamic system to stay in the safe set. It is known that in the single agent system if the control barrier function h satisfies the equation (1), the agent will never enter the dangerous set under policy pi. A straightforward way to extend the control barrier function in the MARL setting is to replace the state-action pair by  the joint state-action pair  in equation (1). However it may suffer from the exponentially large state and action space. Therefore, the author proposes a decentralized setting, where each agent just maintains its own control barrier function. To learn the policy and function h simultaneously, the author penalizes the violation of equation (2). At last, they test the proposed method in Navigation, Predator-Prey, ground robots and Drones compare it with several baselines.

This paper brings the recently introduced idea of control barrier functions (CBF) as safety certificate to the multi-agent land. To this end it introduces the idea of decentralized CBFs. This is followed with a framework for jointy learning the CBFs and policies with a PointNet inspired network architecture. The paper provides some generalization guarantees for the approach as well. Finally the approach is compared against various learning and planning based baselines where it significantly outperforms.