Learning Safe Multi-agent Control with Decentralized Neural Barrier Certificates
Authors: Zengyi Qin
Kaiqing Zhang
Yuxiao Chen
Jingkai Chen
Chuchu Fan
Venue: ICLR 2021 Poster (2021)
Keywords: Multi-agent
safe
control barrier function
reinforcement learning

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 at https://realm.mit.edu/blog/learning-safe-multi-agent-control-decentralized-neural-barrier-certificates.

Published as a conference paper at ICLR 2021
LEARNING SAFE MULTI-AGENT CONTROL WITH DECENTRALIZED NEURAL BARRIER CERTIFICATES
Zengyi Qin', Kaiqing Zhang', Yuxiao Chen², Jingkai Chen' and Chuchu Fan'
"Massahussett Institute of Technology
2 University of Illinois Trrbana-Champen California Institute of Technology {qinzy, chuchuJ@mi t. edu
ABSTRACT
We study the multi-agent safe control problem where agents should avoid colli- sions 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 decentralized fashion, which can adapt to an arbitrarily large number of agents. Building upon this framework, we fur- ther 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 demon- strate that our method significantly outperforms other leading multi-agent control approaches in terms of maintaining safety and completing original tasks. Our ap- proach also shows substantial generalization capability in that the control policy can be trained with 8 agents in one scenario, while being used on other scenar- ios with up to 1024 agents in complex multi-agent environments and dynamies. Videos and source code can be found on the website]]
INTRODUCTION
Machine learning (ML) has created unprecedented opportunities for achieving full autonomy. How- ever, learning-bast 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 al. (2019); Jin 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 & Allgöwer 2007 Ames al. 2014) with a CBF Quadratic Programming (QP) supervisory controller. However, is extremely difficult to synthesize CBF by hand for complex dynamic systems, which stems growing interest in learning-basse based CBF (Saveriano & Lee 2020 Srinivasan et al. [2020) Jin et al. 2020 Botf 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- 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 de- signs 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 intro- duce 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

---

Published as a conference paper at ICLR 2021
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 to make such learning process even more scalable and practical, which are then validated extensively in Section
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 joint- leaming framework performs exceptionally well: our control policies trained on scenarios with agents can be used on up to 1024 agents while maintaining low collision rates, which has notably pushed the boundary of learning-basee 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 1 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 decentralized fashion. 2) We present several techniques that make the learning framework more effective and scalable for practi- cal multi-agent systems, including the use of quantity-permutann tures 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 com- plex 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.
invariant neural network architec-
Safe Control via CBE. Barrier certificates (Prajna et al. 2007) and CBF (Wieland & Allgöwer, 2007) is 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
Related Work. Learning-Bast
primarily consist of two categories: learning CBFs from data (Saveriano & Leel 2020 Srinivasan ct al. 2020; Jin et al.) 2020; Boffi et al. 2020). and CBF-based approach for controlling unknown systems (Wang al. 2017 2018 Cheng et al. 2019: TTylor 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 bearning-enables approaches, however, has addressed the multi-agent setting.
Multi-Agent Safety Certificates and Collision Avoidance. Restricted to holonomic systems, guar- anteeing 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, [orrmann et al. (2015) Wang et al. (207)) have proposed the framework of multi agent CBF to generate collision- free controllers, with either perfectly known system dynamics (Borrman et al. 2015), or with worst-case uncertainty bounds (Wang 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-Shwartze et al. 2016). Under the CBF framework, [Cheng al.
2020) considered the setting with unknown system dynamics, and proposed to design robust multi- agent CBFs based the learned dynamics. This mirrors the second category mentioned above in safe control, which is perpendicular to our focus. RL approaches have
single-agent learning-bacc also been applied for multi-agent collision avoidance (Chen et al., 2011aa] Lowe al. 2017 Everett let al. 2018 Zhang et al.] 2018). Nonetheless, no formal guarantees of safety were established in these works. One exception Zhang & Bastani (2019), which proposed aulti-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 MARI
2

---

Published as a conference paper at ICLR 2021
based approaches scale to massive number of, e.g., thousands of agents, as approach does. The most scalable MARL platform, to the best of our knowledge, is Zheng et al. (2017). which may handle comparable scale of agents ours, but with discrete state-action spaces. This is in contrast to our continuous-space models that can model practical control systems such as rohots and drones.
2
PRELIMINARIES
2.1 CONTROL BARRIER FUNCTIONS AS SAFETY CERTIFICATES
One common approach for (single-agent) safety certificate is via control barrier functions (Ames) et 2014), which can enforce the states of dynamic systems stay in the safe set. Specifically, let
SC K" be the state space, Sa C SSin is the dangerous set. S, S Sd is the safe set, which contains the set of initial conditions So C Sg. Also define the space of control actions as 2 C R". For a
dynamic system 8(t) f(s(t), u()),, ). control barrier function h : K + R satisfies:
(V' E So, h(a) 2 0) A (Vs E Sa, h(s) <0) A (V {& A(4) 2 0). V.h f(s,u) + a (h) 2 0), (1)
where a<-) is a class-K function, i.e., ac.) is strictly increasing and satisfies a00) 0. For a control
policy x S + Ul and CBF h, it is proved in Ames et al. (2014) that if s(0) E {s h(ss) 2 0] and the three conditions in (1) are satisfied with オ (z), then s(t) {s h(s)) 2 0} for Vt E [0, oo), which means the state would never enter the dangerous set Sy under π.
2.2 SAFETY OF MULTI-AGENT DYNAMIC SYSTEMS
Consider a mulli-agennt system with N agents, the joint state of which at time is denoted by stt) = (s1(t), (t). SN (t())) where (t()) E S. C R" denotes the state of agent time t. The dynamics of agent is (t) = f((s: (t), us (t)) where (t) E U4 C I is the control action of agent i. The overall state space and input space denoted as @ S., u
us For each agent we detine (t) as the of its neighborhood agents at time t. Let (t) E [X be the local observation of agent i, which is the states of [N.(t) neighborhood agents, Notice that the dimension of (t) is not fixed and depends on the quantity of neighboring agents. We assume that the safety of agent i is jointly determined by 8; and X. := S, x O, be the observbbervation space that contains the safe set X. dangerous set Na,a and initial conditions X.o0 C Ki... Let d X; - R describe the minimum distance from agent i to other agents that it observes, d(s;, 01) < Kg implies collision. Then X = {(s,; o))ld(ss 0,) 2 k2) and X.a = {(s (d))d(s; 0,) < k,). Let d, S - IR be the lifting of from X, to S, which is well- defined since there is surjection from S X, Then define S, = {s E S I,..,,,, ds(s) Z
Let O be the set of all possible observations and
). The safety of multi-agent system can be formally defined as follows:
Definition 1 (Safety of Multi-Agent Systems). If the state-obe observation satisfies d(s;, 0,) 2 Rgg for agent i and time then agent is safe at time t. ffr Vi, agent i is safe at time t, then the multi-agent system is safe at time I, and 8 E S..
A main objective of this paper to learn the control policy (t), for Vi 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.
3 LEARNING FRAMEWORK FOR MULTI-AGENT DECENTRALIZED CBF
3.1 DECENTRALIZER CONTROL BARRIER FUNCTIONS
For multi-agent dynamic system, the most naive CBF would be 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 h2 X2 + R:
(V (st, oz) E &, (8i, ot) 2 0) A (V (si, o.) E &, ha(si, oz) <0) <
(2)
(V (s) E 0.), o.) 2 0}, V., fils, us) + Vo o:(t) + aa (h.) 2 0)
3

---

Published as a conference paper at ICLR 2021
where (t) is the time derivative of the observation, which depends 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 h, 0z) is local in the sense that it only depends on the local state & and observation ON- 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 AMulti-Agen Safety Certificates with Decentralized CBF). ffr Vi, the initial state- observation (s)(0), 0, (x)) E {(s1,0.) (8, 0;) 2 0} and the decentralized CBF conditions in (2) are satisfied, then vi and Vt, (t; (x)) E {(st, ha(s;, 0;) 2 0}, which implies the state would never enter R. any agent i. Thus, by Definition 7 the multi-agent system is safe.
The proof of Proposition T is provided in the supplementary material. The key insight of Propo- sition D is that for the whole multi-agent system, the CBFs can be applied in a decentralized fash- ion for each agent. Since (s,,,, 0z) 2 0 is invariant, by definition of h4, h,(s;, d.(s) 2 Ka, which means agent i never gets closer than Ka to all its neighborhood agents. There- fore, Vi, hs,,, 0z) 2 0 implies that vi, ds 2 Kg, which by definition also means 8 E S., and the multi-agent system is safe as defined in Definition
0 =
Notice that an agent only needs to care about its local information, and if all agents respect the same form of contract (i.c., the decentralized CBF conditions), the whole multi-agent system will be safe. The fact that global safety can be guaranteed by decentralized CBF of great importance since 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.
3.2 LEARNING FRAMEWORK
From Proposition] we know that if we can jointly learn the control policy n. (s; 0:) and control bar- rier function h.(s; 0z) such that the decentralized CBF conditions in 2 are satisfied, then the multi- agent system is guaranteed to be safe. Next we formulate the optimization objective for the joint learning of (.( 0;) and (s( o.). Let T C RR be the time interval and 7; {sx(1), (ee) be a trajectory of state and observation of agent i. Let Tr be the set of all possible trajectories of agent Let H. and V. be the function classes of h; and wy. Define the function ys: T, H4 x V, + I as:
(e his nT) == min { inf h4(ss: inf -hi(st, ot), Ni,or,
inn (h, + a (b:)) N.aMn.
The set Xt,, = {(s,, o;) (s 2 0}. Notice that the third item on the right side of Equation (3)
depends on both the control policy and CBF, since h = Vg,,; S((s;, us) + Vo,h; ác((), uq (1)8)00). It is clear that if we can find h; and 0z) such that (1 hi, m.) > 0 for VT, T and Vi, then the conditions in (2) are satisfied. For each agent i, assume that we are given 2, i.i.d trajectories (T ... , . drawn from distribution D; during training. We solve the objective:
For all i, find h4 E H4 and n, E V,, s.t. BT h,, n.) 2 y, Vj = 1,2, 24
(4)
where 7 > 0 is a margin for the satisfaction of the CBF condition in ( 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 D;. See a detailed statement of the results in Appendix B. The bound depends
the richness of the function classes, the margin 7, 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 from D,, 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., 202T). We leave 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- -oop 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 See more details of this implementation in Section 4.1 and more discussion on this point in the Remark in Appendix B
4

---

Published as a conference paper at ICLR 2021
State and obscrvation (9,, 92)
Neural Net Controller
Ncural Net CBF
hi(s 0z)
Vehi(Su o:)
I
Control input uG
5 fi x))
Vyhi
Loss C
Figure I: The computational graph the control-certificte jointly learning framework in multi-agent systems. Only the graph for agent shown because agents have the same graph and the computation is decentralized.
Besides the generalization guarantee, there also exists several other gaps between the formulation in A and the practical implementation. First, 4 does not provide concrete way of designing loss functions to realize the optimization objectives. Second, there are still N pairs of functions (h, T:) be learned. Unfortunately. the dimension of the input o, of the functions h4s मद are different for each agent i, and will even change over time in practice, as the proximity of other agents is time- varying. leading to time-varying local observations. To scale an arbitrary number of agents, h; and 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.
4 SCALABLE LEARNING OF DECENTRALIZED CBF IN PRACTICE
Following the theory in Section 3 consider the practical learning of safe multi-agent control with neural barrier certificates, i.c., using neural networks for and V. We will present the formulation of loss functions in Section 4.1 which corresponds to the objective in ( Section 4.2 presents the neural network architecture of h; and Ty, which are invariant to the quantity and permutation of neighboring agents. Section 4.3 demonstrates spontaneous policy refinement method that enables the control policy to satisfy the decentralized CBF conditions as possible as could during testing.
4.1 LOss FUNCTIONS OF JOINTLY LEARNING CONTROLLERS AND BARRIER CERTIFICATES
the main idea is jointly learn the control policies and control barrier func- tions in aeeet- 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 single environment to generate experiences, which are combined to minimize the empirical loss function L E,C5 where L is the loss function for agent formulated as:
Based on Section 3.2
Σ max (0,7-h. (s,
Σ max (0,7+ + (st, 4,E22
Σ A.E.A
max (0,7 - vi,li (s x, (s., Vo - a(h
We choose 7 10-2 in implementation. O; and wy 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 òj, which is the time derivative of the observation. Instead, we approximate h(s; o,) = h, ffi (8s, TT (ss, +,))+ Vo hf--o, numerically by h(s;,o;) = [t(s o, (t+ At) ((s;(t), o, (t)))/Att For the class-K function a(-), we simply choose a linear function a(h) = Ah. Note that Le mainly considers safety instead of goal reaching. To train safe control policy n; (#s, o:) that can drive the agent to the goal state, we also minimize the distance between u; and u. where uf is the reference control input computed by classical approaches (e.g.. LQR and PID controllers) to reach the goal. The goal reaching loss _ = Σ, where C. formulated as C (w:) Σ.,ex || (si, oz) uf (s, l2). The final loss function L L C, where 1) is balance weight that is set to 0.1 in our experiments. We present the computational graph in Figure to help understand the information flow.
where y is the margin defined in Section 3.2
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 (st, under their current policies with
5

---

Published as a conference paper at ICLR 2021
s;(t) [N(())
128
Concatenution
(( E R
(()
Notation
Vector
11
RowMax
128
Fully connected layers
Figure 2: Neural network architecture of the control policy. The blue part indicates quantity-permutaat permutation invariant observation encoder, which maps (t( E [X*(() with time-varying dimension fixed length vector. The network takes the state s; and local observation o as input to compute control action u.. The neural network of the decentralized CBF bu has a similar architecture except that the output is a scalar.
probability 1 and random policies with probability where is set be 0.05 in experiment. The collected (s;, are stored as a temporary dataset and every step of policy update, 128 (si, 0;) are randomly sampled from the temporary dataset to calculate the total loss L. We minimize C by applying stochastic gradient descent with learning rate 10-3 and weight decay 10-6 to 02 and wi, which are the parameters of the CBF and control policies. Note that the gradients are computed by back-proe propagation rather than policy gradients because L is differentiable w.r.t. 6 and wi.
Iterative Data Collection and Training. It is important note that we did not use 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 training process is crucial for generalizing to testing scenarios. More discussion on this point can be found in the Remark in Appendix
4.2 SHANTITY-PERMUTAT
INVARIANT OBSERVATION ENCODER
Recall that in Section 3.1 we define o; the local observation of agent i. o contains the states of neighboring agents and its dimension can change dynamically. In order to scale to an arbitrary number of agents, there are h4(s;, o:) and (3; o;). First, the architecture should be able to dynamically adapt to the changing quantity of observed agents that affects the dimension of ot. Second, the architecture should be invariant to the permutation of observed agents, which should not affect the output of h; or w,, All these challenges arise from encoding the local observation o, Inspired by PointNet (Qi al. (017). we leverage the max pooling layer to build the cernnity-pemmtattionn invariant observation encoder.
pivotal principles of designing the neural network architectures of
Let us start with a simple example with input observation (t) R (M(0), where is the di- mension of state and (t) is the set of the neighboring agents at time change from time to time. The permutation of the columns of o; is also dynamic. Denote the weight matrix as W E Roxx and the element-wise ReLU activation function as a()). Define the row-wise max pooling operation as RowMax(-), which takes a matrix input and outputs the maximum value of each row. Consider the following mapping p (O) + RP formulated as p(o,)= = Row:ax((((Woo))
fixed while (t can
(8)
where p maps a matrix o whose column has dynamic dimension and permutation fixed length feature vector p(ox) E Rº, The dimension of p(o:) remains the same even if the number of columns of (1), which is [M], change over time. The network architecture of the control policy shown in Figure 2 which uses the RowMax(-) operation. The network of the control barrier function is similar except that the output is scalar instead vector.
4.3 SPONTANEOUS ONLINE POLICY REFINEMENT
We propose spontaneous online policy refinement approach that produces even safer control poli- cies in testing than the neural network has actually learned during training. When the model dy- namics environment settings complex and exceed the capability of the control policy, the

---

Published as a conference paper at ICLR 2021
Agent Target
Food
Reference Traj.
Prey Predator
Obstacle
(a) Navigation
(b) Predator-Prey
(c) Nested Rings
Figure 3: Illustrations of the 2D environments used in the experiments. The Navigation and Predator- Prey
environments are adopted from the multi-agent particle environment (Lowe et al. 2017). The Nested-Rings environment is adopted from Rodriguez-Sedas et al. (2014).
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 u, online by minimizing the violation of the decentralized CBF conditions. That is, the learned CBF can serve as guidance on generating updated uy 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 using h by solving quadratic programming problems (Xu et al. 2017 Ames et al. 2017). In the experiments, also study the effects of such an online policy refinement step.
computed online
Given the state 8;, local observation Og, and action us computed by the control policy, consider the scenario where the third CBF condition is violated, which means V vi f((8), u.) + Vo, hy à + ahh.) < 0 when h; 2 0. Let e; E Rn be an increment of the action u₁ Define Φ(e:) RR" + IR as
((e,) = max(0, - 2., f((st, + +e) - Vo, h4 6; - a(h)) + m//es/12-
(9)
If the first term on the right side Equation ( is O, then the third CBF condition satisfied. We enforce the satisfaction in every timestep of testing (after u; is computed by the neural network controller) by finding an 6; that minimizes ((c:). ll is regularization factor that punishes large 6;- We set μ = 1 in implementation and observed that in our experiment, a fixed μ sufficient make sure the I|u, + eall do not exceed the constraint on control input bound. When evaluating on new scenarios and the constraints violated. one can dynamically increase ju to strengthen the penalty. For every timestep during testing, we initialize to zero and check the value of ((e:). o(e,) > 0 indicates that the control policy not good enough to satisfy the decentralized CBF conditions. Then we iteratively refine e; by allowed iteration is exceeded. The final control input is u, = u4 + e,. Such refinement can flexibly refine the control input to satisfy the decentralized CBF conditions much possible.
Ve((e;) until Φ(ex) mlless13 = 0 or the maximum
5 EXPERIMENTAL RESULTS
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 descrip- tion of each method is as follows. MAMPS leverages the model dynamics iteratively switch to safe control policies when the learned policies are unsafe. PIC proposes the permutation-invarian critic to enhance the performance of multi- auett--gent RL. We incorporate the safety reward 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 pioneering work on multi-agent RI., and MADDPG-SSfe is obtained by adding the safety reward the reward function that is similar to PIC-Safe. S2M2 is a sfate-of-the-arr 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-fri 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 visible to model-based methods including MAMPS, S2M2 and our methods, and invisible the
7

---

Published as a conference paper at ICLR 2021
Navigation
IrlditoorPPey
Nestod Rings
0.00
0.20
0.95
0..5
MEDCC couns)
HANTS
0.80
0.25
agents
eagents
Novigation
kings
Avcroge rowOrd
NAMRS
Number agents
Mumber of spents
Figure 4: Safety and reward in the 2D tasks. Results taken after each method converged and averaged over 10 independent trials.
Maze
Maze
TA
6.96
Safety
6.94
NDBC [OLES
SPM2
MAMPS
Number of agents
Number of
Avereçe
Kumber of agents
Number of ofengss
Figure 5: Environments and results of 3D tasks. In Maze and Tunnel, the initial and target locations of each drone randomly chosen. The drones from the initial locations and aim to reach the targets without collision. The results are taken after method converged and are averaged over independent trials.
model-free MADDPG and PIC. Since the model-free methods do not have access to model dynamics but instead the simulators, they are more Bata-demanding. The number of cate-observation pairs to train MADDPG and PIC is 10 times more than that of model-based based learning methods to make sure they converge to their best performance. When training the RL-bbased methods, the control action computed by LQR for goal-reaching is also fed to the agent as one of the inputs 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 safery rate as a criteria when evaluating the methods. The safety rate calculated as 1 BieT [I((s(tt), ot)) X,)] where I(() is the indicator function that is 1 when its argument is true or O otherwise. The observation o, contains the states of other agents within the observation radius, which is 10 times the safe distance. The safe distance set to be the diagonal length of the bounding box 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 +10 reward if it reaches the goal and a -I reward 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 +10, which is attained when the agent successfully reaches the goal and always stays in the safe set.
N
Ground Robots. We consider three tasks illustrated in Figure 3 In the Navigation task, each agent starts from random location and aims to reach 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
8

---

Published as a conference paper at ICLR 2021
1.000
10.0
9.5
0.995
Averag reward
Safety rate
0.990
8.5
0.985
Testing Training Env.
Testing Training Env.
Maze Maze
Maze Maze
7.5
0.980
Num. of agents in training
Maze Tunnel
Tunnel Tunnel
Num. or agents in training
Maze Tunnel
Tunnel Tunnel
Tunnel Maze
Tunnel Maze
0.975
6.5
4
8
16
32
64
128
256
512
1024
16 32 64
256 Number of agents testing
128
512 1024
Number agents testing
Figure 6: Generalization capability of MDBC the 3D tasks. MDBC can be trained with 8 agent in one environment and generalize to 1024 agents in another environment in testing.
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 environment to ensure the overall density of agents remains similar.
environment, we will also enlarge the area of the
Figure 4 demonstrates that when the number of agents grows (c.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 otate-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. Fig- ureBsdemonstrates the environments and the re- sults of each approach. Similar to the results of ground robots, when there are a large number of agents (c.g., 32 agents), maintain high reward and safety rate, while other methods have worse performance. Fig- ure shows the generalization capability of our method across different environments and num- ber of agents. For each experiment, we train 8 agents during training, but test with up 1024 agents. The extra agents are added by copy- ing the neural network parameters of the trained 8 agents. Results show that our method has remarkable generalization capability to diverse
H
method can still
Figure 7: Illustration of the Maze environment with 1024 drones. Videos can be found the supplementary material.
scenarios. Another related work Chen 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 u, 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 single run of evaluation with 32 agents, showing significant advantage in computational efficiency. For both the ground robot and drone experiments, we provide video demonstrations in the supplementary material.
CONCLUSION
This paper presents a novel approach of learning safe multi-agent control via jointly learning the de- centralized control barrier functions as safety certificates. We provide the theoretical generalization bound, as well as the effective techniques to realize the learning framework practice. Experi- ments 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.

---

Published as a conference paper at ICLR 2021
7 ACKNOWLEDGEMENT
The authors would like to thank Nikolai Matni for the valuable discussions. The authors acknowl- edge support from the DARPA Assured Autonomy under contract 118750-19-C-00990 The views, opinions and/or findings expressed are those of the authors and should not be interpreted repre- senting the official views or policies of the Department of Defense or the U.S. Government.
REFERENCES
Javier Alonso-Mora, Andreas Breitenmoser, Martin Rufli, Paul Beardsley, and Roland Siegwart. Optimal reciprocal collision avoidance for multiple non-holonomic robots. In Distributed Au- tonomous Robotic Systems, pp. 203-216. Springer, 2013.
Aaron D Ames, Jessy W Grizzle, and Paulo Tabuada. Control barrier function based quadratic programs with application to adaptive cruise control. Decision and Control (CDC), 2014 IEEE 53rd Annual Conference on, pp. 6271-6275 IEEE, 2014.
Aaron D Ames, Xiangru Xu, Jessy W Grizzle, and Paulo Tabuada. Control barrier function based quadratic programs for safety critical systems. IEEE Transactions on Automatic Control, 62(8): 3861-3876, 2017.
Nicholas M Boffi, Stephen Tu, Nikolai Matni, Jean-Jacques Slotine, and Vikas Sindhwani. Learn- ing stability certificates from data. arXiv preprint 2rXi::2008.05955: 2020.
Urs Borrmann, Li Wang, Aaron D Ames, and Magnus Egerstedt. Control barrier certificates for safe swarm behavior. IFAC-Papers-Onl 48(27):68 2015.
Ya-Chien Chang, Nima Roohi, and Sicun Gao. Neural lyapunov control. In Advances in Neural Information Processing Systems, pp. 1245-3254 2019.
Jingkai Chen, Jiaoyang Li, Chuchu Fan, and Brian C. Williams. Scalable and safe multi-agent motion planning with nonlinear dynamics and bounded disturbances. In Proceedings the Thirty- Fifth AAAI Conference on Artificial Intelligence (AAAI 2021), 2021.
Yu Fan Chen, Michael Everett, Miao Liu, and Jonathan P How. Socially aware motion planning with deep reinforcement learning. In IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS), pp. 1343-1350. IEEE, 2017a.
Yuxiao Chen, Huei Peng, and Jessy Grizzle. Obstacle avoidance for low-speed autonomous vehicles with barrier function. IEEE Transactions on Control Systems Technology, 26(1):194-206 2017b.
Yuxiao Chen, Andrew Singletary, and Aaron D Ames. Guaranteed obstacle avoidance for multi- robot operations with limited actuation: a control barrier function approach. IFEE Control Sys- tems Letters, 5(1):127-132, 2020.
Richard Cheng, Gábor Orosz, Richard M Murray, and Joel W Burdick. End-to-end safe reinforce- ment learning through barrier functions for safety-critical continuous control tasks. In AAAI Conference on Artificial Intelligence, volume 33, pp. 3387-3395, 2019.
Richard Cheng, Mohammad Javad Khojasteh, Aaron Ames, and Joel W Burdick. Safe multi-agent interaction through robust control barrier functions with learned uncertainties. arXiv preprint arXiv:2004.05273. 2020.
Jason Choi, Fernando Castañeda, Claire Tomlin, and Koushil Sreenath. Reinforcement learning for safety-critical control under model uncertainty, using control Yyарunov functions and control barrier functions. arXiv preprint arXiv:2004. 07584, 2020.
Michael Everett, Yu Fan Chen, and Jonathan P How. Motion planning among dynamic, decision- making agents with deep reinforcement learning. In IEEE/RSJ International Conference on In- telligent Robots and Systems (IROS), pp. 3052-3059. IEEE, 2018.
10

---

Published as a conference paper at ICLR 2021
Chuchu Fan, Kristina Miller, and Sayan Mitra. Fast and guaranteed safe controller synthesis for nonlinear vehicle models. Shuvendu K. Lahiri and Chao Wang (eds.), Computer Aided Verifi- cation. pp. 629-652, Cham, 2020. Springer International Publishing.
Paul Glotfelter, Jorge Cortés, and Magnus Egerstedt. Nonsmooth barrier functions with applications to multi-robot systems. IEEE control systems letters, 1(2):100-315, 2017.
Wanxin Jin, Zhaoran Wang, Zhuoran Yang, and Shaoshuai Mou. Neural certificates for safe control policies, arXiv preprint arXiv:2006.08466 2020.
lou-Jen Liu, Raymond A Yeh, and Alexander G Schwing. Pic: permutation invariant critic for multi-agent deep reinforcement learning. In Conference on Robot Learning, pp. 590-602, 2020.
Ryan Lowe, Yi I Wu, Aviv Tamar, Jean Harb, OpenAl Pieter Abbeel, and Igor Mordatch. Multi- agent actor-critic for mixed cooperative-competiite environments. Advances in Neural Infor- mation Processing Systems, pp. 6379-6390, 2017.
Hang Ma, Daniel Harabor, Peter. Stuckey, Jiaoyang Li, and Sven Koenig. Searching with consis- tent prioritization for multi-agent path finding. AAAI 2019 Thirty-Third AAAI Conference on Artificial Intelligence, 33(1):7643-76) 7650, 2019.
lan M Mitchell, Alexandre M Bayen, and Claire Tomlin. A time-dependent familton-jacobi formu- lation of reachable sets for continuous dynamic games. IEEE Transactions on automatic control, 50(7):947-557, 2005.
Stephen Prajna, Ali Jadbabaie, and George Pappas. A framework for worst-case and stochastic safety verification using barrier certificates. IEEE Transactions on Automatic Control, 52(8):
1415-1428, 2007.
Charles R. Qi, Hao Su, Kaichun Mo, and Leonidas Guibas. Pointnet: Deep learning on point sets for 3d classification and segmentation. In P Proceedings of the IEEE Conference on Computer Vision and Puttern Recognition (CVPR), July 2017.
Han Qie, Dianxi Shi, Tianlong Shen, Xinhai Xu, Yuan Li, and Liujing Wang. Joint optimization of multi-UAV target assignment and path planning based on multi-agent reinforcement learning. IEEE Access, 7:146264 0462664146272.2 2019.
Alexander Robey, Haimin Hu, Lars Lindemann, Hanwen Zhang, Dimos V Dimarogonas, Stephen Tu, and Nikolai Matni. Learning control barrier functions from expert demonstrations. arXiv preprint arXiv:2004.03311 03311,, 2020.
Erick Rodríguez-Seda, Chinpei Tang, Mark W. Spong, and Dušan M. Stipanović. Trajectory tracking with collision avoidance for nonholonomic vehicles with acceleration constraints and limited sensing. The International Journal of Robotics Research, 3312)) 2014.
Matteo Saveriano and Dongheui Lee. Learning barrier functions for constrained motion planning with dynamical systems. arXiv preprint arXiv:2003.1 11100003.110000 11500, 2020.
Shai Shalev-Shward Shaked Shammah, and Amnon Shashua. Safe, multi-agent, reinforcement learning for autonomous driving. arXiv preprint arXiv:1610.03295. 2016.
Nathan Srebro, Karthik Sridharan, and Ambuj Tewari. Smoothness, low noise and fast rates. In Advances in Neural Information Processing Systems 23, pp. 2199-2207, 2010.
Mohit Srinivasan, Amogh Dabholkar, Samuel Coogan, and Patricio Vela. Synthesis of control barrier functions using supervised machine learning approach. arXiv preprint
2020.
Andrew Taylor, Andrew Singletary, Yisong Yue, and Aaron Ames. Learning for safety-critical control with control barrier functions. In Learning for Dynamics and Control, pp. 708-717, 2020.
Stephen Tu, Alexander Robey, and Nikolai Matni. Closing the closed-loop distribution shift in safe imitation learning. arXiv preprint 11Xiv:2102.09161, 2021.

---

Published as a conference paper at ICLR 2021
Jur Van den Berg, Ming Lin, and Dinesh Manocha. Reciprocal velocity obstacles for real-time multi-agent navigation. In IEEE International Conference on Robotics and Automation (ICRA), pp. 1928-1935. IEEE, 2008.
Li Wang, Aaron D Ames, and Magnus Egerstedt. Safety barrier certificates for collisions-free mul- tirobot systems. IEEE Transactions on Robolics, 33(3):661-674, 2017.
Li Wang, Evangelos A Theodorou, and Magnus Egerstedt. Safe learning of quadrotor dynamics using barrier certificates. In JEEE International Conference Robotics and Automation (ICRA), pp. 2460-2465. IEEE, 2018.
Peter Wieland and Frank Allgöwer. Constructive safety using control barrier functions. IPAC Pro- ceedings Volumes, 40(14):224)))) (27, 2007.
Xiangru Xu, Jessy W Grizzle, Paulo Tabuada, and Aaron D Ames. Correctness guarantees for the composition of lane keeping and adaptive cruise control. IEEE Transactions on Automation Science and Engineering, ((13):211-122)) 2017.
Kaiqing Zhang, Zhuoran Yang, Han Liu, Tong Zhang, and Tamer Basar. Fully decentralized multi- agent reinforcement learning with networked agents. International Conference on Machine Learning. pp. 5872-5881, 2018.
Wenbo Zhang and Osbert Bastani. Mamps: Safe aulti-agent reinforcement learning via model predictive shielding. arXiv preprint arXiv: 1910. 12639, 2019.
Lianmin Zheng, Jiacheng Yang. Han Cai, Weinan Zhang, Jun Wang, and Yong Yu. Magent: A
many-agent reinforcement learning platform for artificial collective intelligence. arXiv preprint arXiv:1712.00600, 2017.
12

---

Published as a conference paper at ICLR 2021
A PROOF OF PROPOSITION 1
Since h4 = V ha fi(si, u4) + Val (t),, the satisfaction of implies: A (s;, E Xs,0
h h 0r) 2
V 0z) E Xi.d,
h, 0:) <
(10)
A 0s) E ((s),,)) h; o,) 2 0}. h, + a (h,) 2
The initial condition (s:(0), (0)) E ((s),o)) hu(s;, o;) 2 0} means that h; > 0 at time 0. Since h, a (h:) 2 0. h, will stay non-negative. which is proved in Section 2 of Ames et al. 2014 4). This means that (t), (t)) & Xx for Vi O. Thus for Vi and Vt > 0, agent would not enter the dangerous set, and the whole multi-agent system is safe by Definition
Remark. Since the input dimension and permutation of h2 change with time, the time derivative of h; does not exist everywhere but almost everywhere. In fact, in the safety guarantee provided by Proposition [ we do not require the time derivative of hy exist everywhere. The h; can also be non-smooth. Based (2) of Glotfelter et al. (0177), and the time derivative exists almost everywhere. Then
define hę the generalized gradient
that always exists when h4 is based on Theorem of Glotfelter al. (2017). long as the CBF conditions are satisfied under the generalized gradient, then h; is a valid CBF and the safety can be guaranteed.
Global CBF from decentralized CBFs. addition to Proposition D another way to prove the global safety of the multi-agen agent system under the decentralized CBFs is to construct the global CBF hg : + R from individual CBFs by taking the minimum, as is in:
(s) == min 4 $1, 01), (2 $2, 02), ... ,,n(s sN, s (NN}}
(11)
where 8; is the projection of the global state onto the state of agent and o; is the projection of the global state to the observation of agent Then the following proposition guarantees the global safety of the multi-agent system.
Proposition 2. If 10 is satisfied for every agent then the global CBF hy (s) satisfies:
v Su.
hy(s)
v E Sa.
hg(s) <
(12)
A E {s hg(s)) 2}, hy + (hg) 2 0,
where S. = fs E Slvi, (s 8, o;) X.,) and S. {s S|3i, (s s; 4 o;) E Xi,). Then Vt 0, (s(()) 2 0 and s Sz, which means the multi-agent system globally safe.
Proof. Let first prove that the satisfaction of (T)) implies the satisfaction of (12. By definition of So. when s E So. we have Vi, (s L 8 & o.) N.o. which means Vi, h; 1 Si,8 o,) 2 0.
Thus (s) mine (hi(s (s 4 si,8 0,]] 2 O. When s E Sa, we have 3i, (s s $ o;) E X,
which means 3i, h,(s 1 Si. s + .;) < 0. Thus hy(s)
min,(h,(s 4 s;,8 o,)} < 0. When
{s (s) 2 0}. we have Vi, (s 1 s, o,) {(s s,, s 0.) h, s; 4,) 0}. So
Vi, h, + (h,) 2 O. Let i" = arg min; (h, 1 s;, 4 o,)). Then (s) = h, 8;,, o+-)
and hy + a (hg) = hy- + a (h.-) ) 2 O. Hence the satisfaction of (10) implies the satisfaction of I2 Then based on Section of Ames al. (2014), we have (s(t)) 2 0, Vt > 0. This means
E Sa, VI > 0, and the multi-agent system globally safe.
B GENERALIZATION ERROR BOUND OF THE DECENTRALIZED CBF
To answer how well the learned (s; 0;) and h (si, oz) can generalize to unseen scenarios, we will provide a generalization bound with probabilistic guarantees. We denote the solution to { as h2 and दद. Denote the Rademacher complexity of the function class of y: as R2, ())), whose definition could be found in Appendix B Also we define e; as the probability that the decentralized CBF conditions are violated for agent over randomly sampled trajectories (not necessarily the samples encountered in training). Under such definition, é, measures the generalization error and
13

---

Published as a conference paper at ICLR 2021
be expressed Pr,-D, [u((T,, hi, ús) < 0). Then we have Proposition 3 that provides generalization guarantees for all the learned hú and nt..
Proposition 3 (Generalization Error Bound of Learning Decentralized CBF), Assume that lul S b
and (4 is feasible. Let ha and in be the solutions (4) and be universal positive constant vector, Recall that N is the number of agents. Then, for any (0,1) the following statement holds:
N n
6 14 log
log(N log(4b/>)/0)
R²
(D:) + p4
21-6.
(6)
Proof. Note that e; Pr. PrWD: [T h4 ūz)) s ENDD [ (M(TT, he ūz) s =)] Under zero
empirical loss, using the Theorem 5 in Srebro et al. (2010) for any & > 0, the following statement holds with probability at least 1
5. N'
log 2 R² (v)) + 72
log( log(4b/7))
G G 14
(13)
2
where μr > is some universal constant. By taking the union bound over all agents, the following statement holds with probability at least (1
8 N )):
N n
log 21 R² (1)) + p4
log( (N log (og(44/))/8)
E
S 4i
(14)
722
1=1
Since (1 N. IN N > 1
ā for d (0,1), we have:
PP
N
e S u
log
2:
R2 (D%) + u
log( N log( 1og(4b/>)/0)
)
2 21 1
(15)
72
which completes the proof.
The Rademacher complexity R2, (Vi) is defined as:
1 Σ ESUL hi, Ti)
R2, =
sup s Dw
Ee Unif ((11)))
sup N.E.. Zi
where & E IR is random vector and E, denotes its jth element. R., (3%) characterizes the richness of function class V/
The left side of Equation 66 is the probability that the generalization error is upper bounded for all the N agents. Equation (6) claims that the generalization error is bounded for all agents with high probability 1 8. Similar to the discussions in Section 4 in Boffi et al. (2020). for specific function classes of H4 and V., 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 2, increases. Such derivations 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 tra- jectories are drawn from the same distribution. Since testing the trajectories come from the closed-loop -nntelll----thh--oloo) 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 up- dated controller sample new data formulate (4, and solve for 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 used. We leave a systematic analysis on the generalization and convergence of this iterative process in future work.
14

---

Published as a conference paper at ICLR 2021
C MODEL DYNAMICS
In the experiment section of our main paper, we use the 2D ground robots and 3D drones. For ground robots, we use double integrator model with state s; [i Was Up,ás Uy.i] for the navigation and predator-prey tasks, and the model from Sedríguez-Seda et al. (0144) for the nested rings task. For drones, we use the following dynamics:
Uz,á Uy. UzZd (n,)) 9 tan()0,)))
ds:
Wa,i
u, =
Wy.i
(16)
Uy
dt
Uz,i
bz.i
Way
0y.iJ
Wy.
D SUPPLEMENTARY EXPERIMENT
For 3D drones we have shown the generalization capability to 1024 agents even when our method is trained with 8 agents (Figure For 2D ground robots we have similar results that were omitted the main paper due to space limitations. We present the results Figure as below. Our method demonstrates the exceptional generalization capability to testing scenarios where the number of agents significantly greater than that training. The safety rate and average reward remain high even when the number of agents grow exponentially.
1.00
Average reward
Safety rate
0.95
0.93
Navigation
Navigation
0.88
egents traiiiing
Predetor-Prey
Num. agents traininn
Predator-Prey Nested Rings
Nested Rings
8
16
64 128 256
512
1024
2566 Number of in testing
32
128
512 1024
Number agents testing
Figure 8: Generalization capability of our method in the 2D tasks. Our method is trained with
agents and tested with to 1024 agents.
Ablation Study on Online Policy Refinement. In Section 4.3 refinement method. Here we study the effect this method on our performance and present the results in Table 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.
we introduced test-time policy
Table 1: Efffec of online policy refinement (OPR). Proportion of OPR stands for the proportion of steps that OPR performed testing.
Safety Rate
Proportion OPR
Environment
Config
4 Agents
8 Agents
32 Agents
1024 Agents 4 Agents 8 Agents 32 Agents
1024 Agents
w/ OPR
0.9999
0.9999
0.9987
0.9956
0.0149
0.0958
0.1423
0.1655
Maze
w/o OPR
0.9999
0.9999
0.9869
0.9741
0
0
0
0
w/ OPR
0.9999
0.9998
0.9988
0.9946
0.01
0.0729 0
0.1271
0.1493
Tunnel
w/o OPR
0.9999
0.9992
0.9866
0.9727
0
0
0
15

---

Published as a conference paper at ICLR 2021
Landscapes of the Learned CBF
0.10
500'0-
Relative Velocity
0.05
20O
0.00
0.000
0.003
-0.05
0.005
0.10
0.050 0.075 0.100 0.125 0.150 0.175 0.200 Relative Distance
Figure 9: Visualization of the learned CBF in the Maze environment with 2 agents. The red area is where the distance between agents is less that the safc threshold.
Visualization of the Learned CBE To have a better understanding of the learned decentralized CBF, we provide a visualization 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 the negative time derivative the relative distance. When the relative velocity is positive, the two agents getting close to each other. From Figure 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 positive only when the states are sufficiently safe (the bottom-right area).
16


Reviews:
[{"review_id": "zJZuugQ4Nf", "reviewer": "AnonReviewer4", "summary": "", "questions": "", "limitations": "", "rating": 8, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "##########################################################################\nPost rebuttal:\n\nI have read authors' rebuttal as well as the newly added contents.\nI appreciate the time and the details that the author goes in when addressing my comments. \nI am convinced that this method can be used even without the OPR module based on the ablation study. \n\nOverall, I think this is a high quality paper that deals with decentralised Multi-agent safety-awared learning. And learning the safe certificate is the shining point of this contribution. I recommend for acceptance and give my final score at 8.  \n\n\n##########################################################################\nSummary:\n \nThe work studies how, in a multi-agent environment, agents should avoid collisions and develop safety guarantee during learning. It presents a novel approach of learning safe multi-agent control via jointly learning the control barrier functions (CBF) as safety certificates. The benefit of this learning-based CBF framework is that during testing, it is decentralised, thus it can scale up to large number of agents, and is agnostic to the changing agent number, which nicely fits with the need of multi-agent problems. An extensive list of experiments against strong multi-agent learning baselines has been conducted, and results are significant. \n\n##########################################################################\nReasons for score: \n\nExtending the learning-based CBF approach to multi-agent problems is an important work in the area of multi-agent learning. The result of multi-agent safe control of robots and drones on 1024 agents using the policies trained on only 8 agents to me is impressive.  I am tending towards an acceptance. However,  I have some uncertainties over the the current version, see the below.\n\n \n##########################################################################ProPros: \n \n1. This paper studies an interesting and an emerging topic in multi-agent learning: multi-agent safety control. They used a CBF approach, a classical idea in control domain, and empower it with the learning capability and extend it in the multi-agent domain. \n\n2. It gives out a clear definition of multi-agent safety control, and show that why a decentralised CBF can meet such multi-agent safety control definition. \n\n3. The author provides a classical high probability generalisation bound based on the Rademacher complexity. \n\n2. The author is considerate in that they account for the changing number of neighbours in a time-variant multi-agent setting. I believe it is an important topic but usually would be neglected by MARL people from the moment of problem definition. \n\n\n \n3. This paper provides comprehensive experiments, including 2D grid world, ground robots, and 3D drones. The results seems competitive against baselines, and outperforming when the agent number is large.\n \n##########################################################################\nCons: \n \n1. I don't quite get the idea of section 4.3, the spontaneous online policy refinement. It seems to me that the learning agent can somehow “cheat” during the test time should they entered into a dangerous zone during the test time. I believe an ablation study on the performance with and without this module is critical. \n\n2. Can the author provide more insights why the proposed algorithm outperform the baselines when the agent number is large, based on figure 4 and 6, it is consistent that N=32 is the break-even point.  \n\n3. The related work of <Guaranteed Obstacle Avoidance for Multi-Robot Operations With Limited Actuation: A Control Barrier Function Approach> seems to be doing a similar topic. Could the author include this baseline into the experiment?\n\n\n4. the union bound in equation6, should it be a \\cup rather than \\cap?\n\n\n5. am I right that your method is in fact a supervised learning approach to learn the policy and the certificate, rather than a RL approach, where the policy update will not influence the new data that you are going to collect. I would love to see a pseduco-code if it is not the case.\n\n6. Can the author comment on how in general the dynamical system information of f_i can be known? \n\n##########################################################################\nQuestions during rebuttal period: \n \nPlease address and clarify the cons above \n \n#########################################################################\n", "extra_scores": {}, "extra_text": {}}, {"review_id": "oGuqwfMh2xv", "reviewer": "AnonReviewer5", "summary": "", "questions": "", "limitations": "", "rating": 7, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "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.\n\nOverall, it's a very interesting extension of the CBF idea for the decentralized setting and permutation+#agents invariant setup seems quite scalable. It's good to have proven generalization guarantees as well.\n\nAlthough the paper shows impressive performance on a variety of tasks, the learning setup is unclear. Sure you have the loss function in Sec 4.1 with the computational graph in Fig 1. But it's unclear how exacly learning happens? Like how is the data collected; how are the enviornments explored. Do you have to estimate policy gradients or you have exact gradients. How exactly do you compare against both MADDPG style model-free method as well as planning based MAFACTEST. Do they even have the exact same environment models? The details are unclear, so it's not possible for me to really judge what's going on in Fig 4. Sure the average rewards and safety rates are higher but are the quantities even commensurable for these very different methods? It's probably yes gven the quantified metrics are scalar quantities which can possibly be measured in a similar manner for the approaches. But still more information is necessary for it be meaningful.", "extra_scores": {}, "extra_text": {}}, {"review_id": "CZTxDzJe3lc", "reviewer": "AnonReviewer1", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "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.\n\n\nConcern 1: The contribution of this paper is incremental. Particularly, the author extends the control barrier function from (1) to (2). It is quite straightforward to prove proposition 1 and 2. In addition, I am not sure whether the definition of equation (2) is reasonable or not.  To simplify the problem, it directly assumes h_i are independent. Is it true that the whole barrier function isthe product of the individual one?\n\nConcern 2: As the author mentioned, the loss function in equation (7) just considers the safety instead of goal reaching. Thus how do you train the agent in the experiment?  It is initialized by a well-trained policy (but not safe ), and then rectified by the loss function. Or you train the goal-seeking policy and safe-policy simultaneously. \n\n\nConcern3: the definition of  safety of the Multi-agent system. It suggests that safety is defined on the Euclidean distance between agents (the agent does not collide with each other). Is it possible to extend this definition to a more general setting?\n\n", "extra_scores": {}, "extra_text": {}}, {"review_id": "Bna7X9HVchB", "reviewer": "AnonReviewer2", "summary": "", "questions": "", "limitations": "", "rating": 8, "confidence": 2, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "## Post-rebuttal\nThe rebuttal was convincing (see my comment below) and addressed my concerns. I therefore increase my score to 8.\n\n## Overview\n\nThis paper introduces MDBC, a method relying on a Control Barrier Function (CBF) learnt jointly with a policy, to obtain a safe and generalizable behavior.\nIt proceeds to show experiments on 2D and 3D navigation tasks, where the safety is defined as the avoidance of any collision.\n\nThe paper is globally well written, and the underlying theoretical foundations seem sound, and experiments show strong results.\nHowever, the experiments leave out a lot of critical implementation details, raising concerns for the reproducibility of the work. Moreover, the baselines used seem inadequate.\n\n\n## Method\n\nThe theory underpinning the proposed method is well exposed and sound.\nThe only question that I have is with respect to the choice of the neural network architecture. A PointNet is being used, what motivates this choice? Have you considered other alternatives such as Pointer network, Graph neural net, transformers?\n\n## Experiments\n\nSome information is missing to fully reproduce the experiments, including:\n* The optimization parameters (optimizer, lr, and possible additions like weight decay and so on)\n* The exact loss used for the policy training (the text mentions a \"distance\", but doesn't specify which\n* How the policy loss and the safety loss $\\mathcal{L}^c$ are combined (I would expect a weighted sum, but this is not specified as far as I can tell)\n* Values of some other hyper-parameters, such as $\\gamma$, $\\mu$, $\\lambda$. Even the non-linear activation $\\sigma$ used in the network is unspecified\n* The theory section assumes that each agents observe the states of other agents within a neighborhood. In the context of the experiments, this neighborhood is unspecified.\n\n\nAs for the comparison, I find the choice of some of the baselines inadequate. With the exception of MAFACTEST (which is, unexpectedly, not reported on all environments), all 3 others (PIC, MAMPS, and MADDPG) are reward based, while the proposed method uses policy imitation to a target policy (LQR or PID controller), which is a much simpler learning problem, as it sidestep many hard problems in RL such as exploration and credit assignment (both temporal and agent-wise). As such, it is not surprising that RL based approaches struggle more when trying to generalize/scale, especially if the training scenario always contain the same number of agents (better results could possibly obtained with some limited curriculum learning)\n\nIt is not even clear from the text how the rewards for these baseline are engineered in some environments like \"Nested Rings\" where the agents must additionally follow a predefined trajectory.\n\nIn addition, the safety loss used in the proposed approach to avoid collisions is enforced with some margin $\\gamma$, which naturally encourages more conservative policies. By contrast, the reward provided to the RL baseline agents is negative only in the event of a collision (positive when the goal is reach, 0 otherwise). To make a fair comparison, the negative reward should be given whenever two agents are getting too close to each other, similar in spirit to the margin $\\gamma$, so as to encourage more conservative policies in this case as well.\n\nAll in all, better baselines could probably devised, perhaps even as simple as well-tuned potential fields.\n\nAside from the baselines, the results shown are mostly convincing, and demonstrate good generalization capabilities. Some limitations:\n* Even though results are averaged over 10 independent runs, now error bar are represented in any of the graphs, so we don't know to what extent the methods are brittle or not\n* Section 4.3 introduces the \"spontaneous online policy improvement\" which is a test-time refinement of the policy to increase safety. However, no discussion of this component is made in the experimental section. In particular, what would be the performance without such refinement? The refinement requires doing some gradient descent over some cost function. How many step does that usually take? What is the impact on the run-time? What is the percentage of states/actions that need to be refined in practice (I expect this percentage to increase with the number of agents, perhaps the generalization capabilities can be credited solely to this component of the method? )\n* It would be valuable to provide some sort of visualization of the $h$ function that has been learnt. How well does it correlate to the distance to the closest object?\n", "extra_scores": {}, "extra_text": {}}, {"review_id": "7WHJYidEMXE", "reviewer": "AnonReviewer3", "summary": "", "questions": "", "limitations": "", "rating": 4, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "Summary:\nThis paper presents a learning framework for decentralized control barrier functions in multi-agent systems, applied to collision-avoidance problems. The paper reviews some key ideas from the CBF literature and extends them to the multi-agent, partially-observed case, then presents a learning framework for estimating CBFs and policies jointly, and concludes with experimental results.\n\nStrengths:\n* Good coverage of recent literature in this area and placement of the present work within it\n* Adequate, though concise presentation of key ideas from CBF literature. I was able to follow this fine but (a small suggestion) it might be a good idea to spend a little more time on this for readers who have not heard of CBFs before.\n* Clear extension to the decentralized, multi-agent case\n* Strong experimental evidence that this approach can scale\n\nWeaknesses:\n* (main one) the time derivative of each agent's observation may not always exist - indeed the paper points out that observations can arbitrarily permute and change dimension at any time. This would seem to be a pretty big theoretical problem...\n* the paper should comment explicitly upon how this formulation differs from existing work in (non-learned) multi-agent CBFs\n* the interpretation of (3) is unclear. One component (though it would still be unclear even without this issue), is the parsing of \\mathcal{X}_{i, 0}. Is this _all state, observation pairs for agent i_? If so, it would certainly help to just say that.\n* The presentation and preparation for Prop 2 is very sparse and hard to follow/understand. For example, what does (5) really buy us except for a term in (6) which is not really explained clearly? To me, this looks a little bit \"decorative\" (to use a term I've seen several conferences use in instructions to reviewers).\n* the mu term in (9) doesn't really make sense\n* in the results, it would be good to comment on failure modes since the proposed method does not achieve perfect safety rates and in the video it is clear that some of the agents violate safety\n* Is MAFACTEST published? If not, this would seem to merit further discussion. If so, it should be clearly cited as different from FACTEST.\n\nOverall:\nI like the main ideas here, but I have identified a number of directions of weakness and potential improvement. For now, I cannot recommend publication.", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Meta-review: Initially there were some shared concerns about the work being too incremental, lack of technical clarity on the algorithmic side and experiments, and lack of clear mathematical formulations. The authors did a good effort and cleared up many questions and remarks satisfactorily, and several reviewers have increased their scores as a consequence. In its current state I recommend to accept the paper.
Decision: Accept (Poster)