Provably Safe Online Multi-Agent Navigation in Unknown Environments
Authors: Zhan Gao
Guang Yang
Jasmine Bayrooti
Amanda Prorok
Venue: CoRL 2024 (2024)
Keywords: Decentralized Multi-Agent Navigation
Unknown Environment
Support Vector Machine
Graph Attention Learning
Control Barrier Function
TL;DR: This paper proposes an online learning-based approach that allows for decentralized multi-agent navigation in unknown environments with provable safety guarantees.

Abstract: Control Barrier Functions (CBFs) provide safety guarantees for multi-agent navigation. However, traditional approaches require full knowledge of the environment (e.g., obstacle positions and shapes) to formulate CBFs and hence, are not applicable in unknown environments. This paper overcomes this issue by proposing an Online Exploration-based Control Lyapunov Barrier Function (OE-CLBF) controller. It estimates the unknown environment by learning its corresponding CBF with a Support Vector Machine (SVM) in an online manner, using local neighborhood information, and leverages the latter to generate actions for safe navigation. To reduce the computation incurred by the online SVM training, we use an Imitation Learning (IL) framework to predict the importance of neighboring agents with Graph Attention Networks (GATs), and train the SVM only with information received from neighbors of high `value'. The OE-CLBF allows for decentralized deployment, and importantly, provides provable safety guarantees that we derive in this paper. Experiments corroborate theoretical findings and demonstrate superior performance w.r.t. state-of-the-art baselines in a variety of unknown environments.

Provably Safe Online Multi-Agent Navigation in Unknown Environments
Zhan Gao Guang Yang* University of Cambridge
Jasmine Bayrooti Amanda Prorok
Abstract: Control Barrier Functions (CBFs) provide safety guarantees for multi- agent navigation. However, traditional approaches require full knowledge of the environment (e.g.. obstacle positions and shapes) to formulate CBFs and hence, are not applicable in unknown environments. This paper overcomes this issue by proposing an Online Exploration-based Control Lyapunov Barrier Function (OE- CLBF) controller. estimates the unknown environment by learning its corre- sponding CBF with a Support Vector Machine (SVM) in an online manner, using local neighborhood information, and leverages the latter generate actions for safe navigation. To reduce the computation incurred by the online SVM training, we use Imitation Learning (IL) framework to predict the importance of neigh- boring agents with Graph Attention Networks (GATs), and train the SVM only with information received from neighbors of high 'value'. The OE-CLBF allows for decentralized deployment, and importantly, provides provable safety guaran- tees that we derive in this paper. Experiments corroborate theoretical findings and demonstrate superior performance w.r.t. state-of-the-art baselines variety of unknown environments.
Decentralized Multi-Agent Navigation, Unknown Environment, Sup- port Vector Machine, Graph Attention Learning, Control Barrier Function
Keywords:
Introduction
Multi-agent systems have garnered significant attention for applications such as distributed aerial surveillance [1. 2], search and rescue [3, 4], and warchouse transportation [5, 6], where safe and efficient navigation is key enabling technique. In this work, focus the problem of decentral- ized multi-agen navigation with dynamical constraints. Different from classic path finding problems [7, 8, 9], we consider both state and control spaces in the continuous domain, and aim to develop controllers that generate feedback control inputs based on local neighborhood information. This problem can be formulated as a sequence of real-time quadratic programming with control barrier functions (CBFs) and control Lyapunov functions (CLFs), where CBFs encode safety for collision avoidance and CLFs encode convergence for goal reaching. The combination of CBFs and CLFs has been widely used for safety-critical controls [10, 11, 12]. While providing safety guarantees, tradi- tional CBF-based approaches require full knowledge of the environment, e.g., positions and shapes of obstacles, to formulate a closed-fone expression for the safety function [13, 14]. Such informa- tion is not available when navigating agents in unknown environments, which happens commonly for decentralized multi-agent systems that have limited observability of the real world.
Our goal is synthesize decentralized controllers that navigate agents in unknown environments with provable safety guarantees. This problem is challenging because it is difficult to formulate the CBF of an unknown environment. Using sensing input, such as vision and LiDAR, is potential solution, which, however, remains an open question as traditional control-based methods lack the
Equal contribution.
8th Conference Robot Learning (CoRL. 2024), Munich, Germany.

---

200
1.5
Tine S0Up
Lowe
10
Concuntisioo
(b)
Figure 1. (a) Local agent A; senses surrounding environment using LiDAR scans (blue circle) with lasers (blue arryss), and communicates with neighbors within communication range (green circle). (b) An example of our method applied in an unknown environment with different obstacle positions, sizes and shapes. Blue circles are initial positions and green squares destinations. Obstacles black, and blue-to slue-to-green lines agent trajectories. The color bar represents time scale, showing no collision occurs.
expressiveness to deal with rich sensing models. For example, it is unclear how to handeraft dif- ferentiable CBFs with a discrete number of observations (e-g.. visual images or LiDAR readings). Learning-bai -asedd methods have been shown successful for sensing-feedbace control tasks [15, 16], and recent works have used neural networks approximate CBFs and CLFs to design observation- feedback controllers to navigate in unknown environments [17, 18, 19J. However, these approaches often sacrifice safety guarantees of the controller. Moreover, they follow an offline supervised learn- ing framework, which suffers from distribution shifts when the deployment environments are vastly different from the training environments; hence, resulting in significant performance degradation.
In pursuit of the aforementioned goal, we propose a sensing- controller for decentralized multi-agent navigation in unknown environments, by utilizing online learning-basel approach without requiring any prior knowledge about the environment. Our contributions are as follows:
(i) We learn the environment CBF with a support vector machine (SVM), using LiDAR readings re- CBF into a quadratic programming (QP) controller for safe navigation unknown environments. Moreover, we train SVM an online manner with instantaneous LiDAR readings, which adapts any new (unseen) environments.
ceived from neighboring agents, and incorporate the
(ii) We leverage graph attention learning to quantify neighbors' importance and perform training only with observations received from important neighbors, to reduce online computation.
(iii) We provide safety guarantees for the proposed learning-base based method by leveraging the accu- racy bound of SVM and the state invariance of CBFs.
(iv) We evaluate our method in a variety of navigation scenarios and show a significant improvement over other leading approaches. We also incorporate an exploration mechanism into the practical implementation of our method, so that agents are encouraged out of local minima.
Related Work. CBF-based methods have been widely used for safety-critic controls [10, 11, 12]. Traditional approaches often assume centralized setting with global information of the environ- ment or agents to formulate safety functions [13, 14]. Distributed CBFs consider the partial observ- ability of agents to provide decentralized safe navigation [20, 21J. while these works address only inter-agent collision avoidance but not obstacles. The work in [22] leverages reinforcement learning to prevent deadlocks when deploying distributed CBFs. However, it still requires prior knowledge of obstacle configurations in the environment handeraft CBFs and is not applicable in unknown environments. Moreover, the hand-designed analytical CBF form may not capture the environment accurately even with global information, leading to inevitable performance degradation.
Learning-based approaches provide a handle to use sensing input for controller synthesis, which is a potential solution for safe navigation in unknown environments. Most existing works conduct the safety check of the learned sensing- based controller post hoc, where the controller synthesized and then independently verified. The work in [23] uses adversarial testing assess safety and searches for the most likely input that causes the vision- based controller to fail, while [24] trains generative adversarial network to map states to image observations and uses the latter to check the safety of the

---

concatenated controller network. Several works attempt to incorporate the safety consideration into the controller synthesis. The works in [25, 26, 27] learn a perception map from observations and use it to design controllers, but these approaches make strong assumptions. For example, they as- sume that the environment (including all obstacle locations) known prior to deployment, limiting its generalization to unknown environments. The authors [28, 29] leverage SVM and Gaussian process (GP), respectively, to approximate the CBF of the unknown environment with LiDAR read- ings. However, all these works consider single-agent system, and [28] requires discretizing the state space to verify the safety. The work in [30] attempts to extend the GP-based CBF to multiple agents, while it ignores inter-agent communication with a lack of system-level consideration and its experiment only involves three agents. More closely related works [17, 18, 19] use neural networks to approximate CBFs and CLFs to design inservation-fedhaee controllers. These neural network based methods enjoy scalability benefits and are versatile w.r.t. the imput space. However, they fol- low an offline supervised learning framework, which leads significant performance degradation if deploying environments vastly different from training ones. Moreover, the learned barrier cer- tificate is an approximation of the true one and it is difficult to provide theoretical safety guarantees.
2 Preliminaries
System dynamics. Consider multi-agent system of n agents A = {A,)=-- The dynamics of agent A, of the form
f ) + (xx));
with x; the state, u, the control input, R; the time derivative of x,, and fxx,), g(x;) ) the flow vectors.
Control Lyapunov function (CLF). The CLF designed to encode the goal reaching constraint, i.., the saistification of CLF constraints guarantees agents converging to their designated goals. In this work, we define an exponentially-stabiiee
control Lypaunov function [31] positive definite function Vx(x,) R" + R [31] such that there exists constant c 2 0 with
infu,eu,
(2)
where VvV := (V,(x.) fxx.) is the Lie derivative of the continuously differentiable function dx. (x,x,) along dynamics fx:)), U, the control space of agent A, and controls the convergence rate.
Control barrier function (CBF). The safety requirement of agent A, is equivalent that contin- uously differentiable function ha (x;) IR" + R and its derivative w.r.t. time satisfy
h4 2 0, (x,) + a (h, (x.)) 2 O, with hx(x)) = L (x,,), + (x,)(x,
(3)
where (x), h, are the Lie derivatives of h₂(x,) and ar-)) ) is class K. function that determines how strictly we enforce safety. We define the higher-order CBF [12] with relative degree one in this paper, and the satisfaction of (3) ensures forward invariance of the state trajectory [12].
3 Problem Formulation
Consider multi-agent system A in unknown environment &, i.e., the agents have no information about neither the obstacle positions nor the obstacle shapes. The agents are initialized at positions S= [s. sn] and tasked towards G ==[ga [g....., B. Each agent is equipped with LiDAR scanner that senses its surrounding environment with a number of lasers and returns distances to the end- points of these lasers. The goal is to navigate the agents from S to while avoiding collision with obstacles and other agents. Specifically, let x; be the local state of agent A; that includes its position p:. velocity v., destination g; and LiDAR readings, and let (0) and x be the initial and target states. We consider a decentralized setting, where each agent senses its local state, communicates with its neighboring agents, and generates its own action with only neighborhood information see Fig. la. Thus, the destination convergence is equivalent to the state convergence lim, x(") x with T the maximal time step. Let also Caate C È be the obstacle-free space that can be occupied by the agents. Collision avoidance is equivalent the safety constraint xx" Csato for t = I,,, T. This allows to formulate the problem of safe decentralized multi-agent navigation.
3

---

Problem 1 (Safe decentralized multi- navigation). Given the multi-agent system A with dy- namics (1), the initial and target states {x; fi=1 and {x {x find decentralized navigation poli-
cies h= that generate agent actions U = [u] ... un [ such that
(t)
lim HT
x = and X E Ceafe: for all t I,..., T and ,,...,I.
(4)
The first condition in (4) encodes the state convergence, i.e., navigation to the goals, and the second condition in (4) encodes state safety, i.e., collision avoidance. Problem is challenging because (i) the safety set Safe is not available as the environment unknown; and (it) the decentralized policies [m:))=) require generating agent actions only with local neighborhood information.
Methodology
To overcome these challenges, we propose to estimate the safety set Crate by synthesizing the CBF of the unknown environment with LiDAR readings sensed by the local agent and received from its neighboring agents, and combine the latter with CLFs into quadratic programming (QP) controller solve Problem 1. Since it difficult formulate continuously differentiable CBFs with a discrete number of LiDAR readings, we leverage learning-based approach to synthesize the environment CBF and perform training online to provide real-time representation for the surrounding environ- ment. To reduce the computation of online learning, we learn the importance of neighboring agents with graph attention networks (GATs), which have achieved success in a wide array of applica- tions and allow for decentralized implementation [32], and train with only LiDAR readings from important neighbors. More specifically, our method contains two main components.
SVM-based CBF-CLF-QP navigation. This component estimates the unknown environment by learning its corresponding CBF with online support vector machine (SVM) using instantaneous Li- DAR readings at each time step. It then employs CBF-CLF-ON controller to generate control inputs for the agents based on local neighborhood information, and integrates an exploration mech- anism into the controller to avoid infeasibility the QP controller during navigation.
Attention-based computation reduction. This component leverages the GAT to predict the impor- tance of the neighboring agents' states in estimating the surrounding environment of the local agent, by following an imitation learning framework. With a cut-off threshold it trains the SVM only with LiDAR readings of the neighboring agents whose attentions are larger than y, to reduce the computation of online SVM training.
With these components, propose an Online Exploration-based Control Lyapunov Barrier Func- tion (OE-CLBF) controller that allows to conduct safe multi-agent navigation in unknown environ- ments in decentralized manner. It can be applied directly to any environment (i.e., any obstacle layout) without fine-tuning or pre-training, due to the nature of online learning see Fig. lb for an example. Moreover, it capable of providing provable safety guarantees due to accuracy guarantees of the SVM and the state invariance of CBFs.
4.1 SVM-based CBF-CLF-QP Navigation
We leverage a CBF-CLF-QP controller to solve Problem (1) iteratively across time. Specifically, at QP problem with CBF and CLF constraints
each time step we re-formulate Problem
[|u[() (u( [|2 + )2
min E'E
s.t. LT (x),(xx (t) + L Lggh 1p (x
ju (0) + tain 20,
(5)
V (1) + Vx )u, " + S. for all i 1,...,n
with 6 R slack variable that determines how strictly enforce the CLF constraint, & R+ regularization parameter often set one, and U, the action space given physical constraints.

---

However, (5) cannot be formulated directly because the environment is unknown and thus, CBF constraints are not available. To overcome this issue, we learn the CBF of the unknown environment with LiDAR readings sensed by the agents. Specifically, the raw LiDAR reading is a distance di E [0, dmax]. with dmax the maximum scanning distance. When di = dmax. there is no collision detected w.r.t. the (th laser and no obstacle along that direction within the sensing range- see Fig. la. We transform di to the endpoint location of the laser 2₁ based on the agent position p. and label 2 with a binary variable y/ {+1, where +1 indicates detected obstacle and -1 otherwise.
At each time step t, agent A, obtains local LiDAR readings 2,") {(21.) Mil D and commu- nicates with its neighbors to collect nearby LiDAR readings (2 JEEN, where NG is the neighbor set of A; within communication range. By considering the aggregated 2 and {2) { HeE, as the training data, we can learn the safety function h of the environment CBF in (5). Since LiDAR read- ings change across time steps as the agent moves, it requires online learning to capture real-time up-to-date representation of the surrounding environment. As the label yi. is binary, we propose to leverage SVM because of its fast training for online implementation and high accuracy for perfor- mance guarantees. Specifically, we consider the SVM classifier as fsvM(zi) sign( (w,, ((z1)) .) with parameters [33], where (6.) is lifting function that maps the input data to some feature space F and (+)x f is some inner product defined in F, and solve the optimization problem as [34]
min
subject to (w o(z)) 2 1 for all L.
(6)
2
By solving (6) in the dual domain to obtain the support vector set Ns.v. and its corresponding Lagrangian multipliers B, we can estimate the safety function with the decision function of SVM as
(z)
Σ (((((()),(Z)))))))
LENs.v.
which measures how safe the position is w.r.t. the obstacles. By substituting hSvm into (5), formulate SVM-based CBF-CLF-QP controller that generates safe actions for each agent A; with online SVM-based CBFs learned from its local LiDAR readings z and [ By selecting a differentiable lifting function (b)) for SVM, the safety function l.vv(()) and the resulting SVM-based CBF constraint are differentiable for the QP controller (5). Furthermore, an exploration mechanism is incorporated resolve the potential infeasibility of the QP controller in challenging scenarios during navigation (e.g., non-convex safety regions) see details in Appendix B.
4.2 Attention-based Computation Reduction
The SVM-based CBF-CLF-QP controller requires training an SVM online with instantaneous Li- DAR readings at each time step l. However, it may be computationally expensive the number of LiDAR readings, i.c., the number of neighboring agents, large, since the time complexity of SVM training is quadratic w.r.t. the number of training samples. To reduce the online computation, quantify the importance of neighboring agents by learning edge weights with GAT and train the SVM only with LiDAR readings received from important neighbors. Specifically, consider the multi-agent system A as graph G, where the nodes are the agents {A₂ [A,) and the edges are com- munication links. The graph structure is captured by an adjacent matrix W, where [W]s] * 0 there is a link between A, and Ay. and [W]s = 0 otherwise. The value of [W]s represents how important the neighboring agent A, w.r.t. the local agent A,. The agent states are modeled by X, which is a matrix whose ith row is the state of A.. We define decentralized attention genera- tors 9, (x,, {x, )eAA, for i = 1,... n. which computes edge weights {[] HEN, based on local neighborhood information. We then formulate the problem of graph attention learning as follows.
Problem 2 (Graph attention learning). Given the agent states X, find decentralized generators {g:): \i that compute edge weights with local neighborhood information, to identify the importance of the neighboring agents to the local agent in synthesizing the CBFs of an unknown environment.
Problem 2 is challenging because it is difficult to define the objective function for training, i.e., it is non-trivial to measure how well the generated attentions quantify the neighbors' importance, and
5

---

we propose to follow an imitation learning framework to solve this problem. In particular, let x; (P., Vi,gi, ] be the states of A,. For the scenario without any concern of computation, each agent A; aggregates all available states x; and (xy JeN. trains the SVM to synthesize the environment CBF with 2, and {2,,, and generates the action i with the CBF-CLF-QP controller. We can then consider {u; N as the expert actions of the agents given the states {x and available communication links. We thus consider the agent states X features and the expert actions U as labels to build a training dataset in the framework of imitation learning. As we are interested in learning attentions W of graph edges, we consider GAT &GAT (X, W) to process features and formulate Problem 2 mathematically as an empirical risk minimization problem
M
min W
M G(PGAT W), U
1
Σ 1==11
(8)
where M is the number of training samples, E(..-) is the loss function that measures the difference between the predicted action and the expert action, and the edge weight matrix W is learned based on the attention mechanism. The learned W identifies the importance of the neighbors' states for the action generation of the local agent. Le., larger value of [W]; indicates that more information of the states x, is used to generate the action u, and thus, A, is more important to A₁.
Thresholding. While the trained GAT mimics an expert action, we need only the computed edge weights W identify the neighbors' importance and leverage the latter to reduce the computation of SVM training. Consequently, neighboring agent A, are used by the local agent A, When [Wiy 2 % the LiDAR readings of A are important and will be used to train the SVM; when [W]s < the LiDAR readings of A, may be redundant, and will hence not be used in the computation.
define threshold y that determines if the LiDAR readings of
5 Safety Guarantees for SVM-based CBFs
The proposed OE-CLBF estimates the unknown environment by training an SVM to formulate the corresponding CBF for collision avoidance. Different from conventional learning- approaches, it is capable of providing safety guarantees with the accuracy bound inherited from SVM and the state invariance inherited from CBF. Specifically, let Z {(z), w)) be the dataset of L LiDAR readings, with z; E E C I²2 and Y1 E Y {+1,-11 For the space Y², assume there exists an SVM classifier fšVM that classifies all samples in Z correctly. Define the error margin of fsvM
y/ w. Φ(zi) >F
<(fšvx)
min (22
which measures the minimum distance of data samples the classification hyperplane and identifies how well S'vM is w.r.t. 2. For our safety analysis, we need the following assumptions.
Assumption 1. The function & of the SVM classifier is infinitely differentiable.
Assumption 2. There exists constant C s.l. for any 2 E Z. it holds that Pr([((())] S C. = 1.
Assumptions 1-2 are not restrictive as they are common for SVM classifiers [35, 33]. We now provide safety guarantees for the proposed method, and summarize the proof in Appendix D.
Theorem 1. Consider the SVM-based CBF-CLF-ORR controller with the function & satisfying As- sumptions 1-2 w.rl. C. Let Caste be the safety set and At be the time interval between two successive LiDAR scanning, i.e., agents re-scan LiDAR readings every At. For any agent state x randomly dis- tributed Caato with probability least 1-a, the trained SVM fåvM classifies L LiDAR readings, the agent state within the next time interval At stays in Crate at a large probability 1 8, where
85 (R(Svva)) logz
SeL
1o2,(
L2 2 with k(fāVM)
K ' (10)
SC
(
Theorem 1 states that the unsafety risk is bounded by factors that inversely proportional the number of LiDAR readings L and the square of error margin e e(fāvaa) In particular, L depends

---

Pellona bucied
0L.5 0115
Thrpaeed
(a)
(b)
(c)
(d)
Figure 2. GAT-based attention and distance-basse attention when: (a) Agents close or far away: (b) Local agent needs information from its neighboring agents; (c) Agents are close destinations. (d) Computation time single SVM training with different thresholds ry for attention-based computation reduction.
on the LiDAR scanner of the agent and ((āvx) is determined by the performance of the SVM classifier. When L and e e(fávM) becomes large, i.e., LiDAR scanner captures more readings from the environment and SVM classifier identifies two classes more clearly, the probability bound reduces towards zero and the unsafety risk decreases for multi-agent navigation. It is noteworthy that this is the first learning-base based CBF method with provable safety guarantees in multi-agent setting."
6 Experiments
First, we provide proof-of-concept for the proposed OE-CLBE, show the effectiveness of SVM- based CBF-CLF-QP controller and attention- based computation reduction, in environment with three agents and three obstacles. Then, we provide performance comparisons between our method and state-of-the-art baselines in environments with more agents and different obstacle layouts (i.e., more obstacles with different positions, sizes and shapes). For all experiments, we consider single integrator dynamics, and a Radial Basis Function (RBF) kernel for the SVM [38]. The method can be extended to general systems with complex dynamics, by substituting the SVM-based safety function (7) into corresponding CBF constraints [39, 40, 41], which will increase the computation or required samples of the online SVM training. Additional experiments are provided in Appendix E.
Proof of concept. We consider an environment of size 8mx6m. The initial and goal positions S and G of the agents are distributed randomly in the environment. The agent has a circular shape of radius Im with a maximum velocity 0.5m/s, and the obstacles are rectangles with different sizes. The sensing range of LiDAR scanner is 1.5m and the number of scanning lasers 50. The maximal time step is 1000 and the time interval 0.1s. For convenience of corroborating the relationship between the edge weights computed by GAT and the importance of neighboring agents, assume sufficiently large communication radius here with a fully connected graph among agents. We consider a distance-based attention mechanism as a baseline for comparison, which computes the edge weight that is inversely proportional to the distance between two neighboring agents.
Figs. 2a-2c plot agents' trajectories computed by our method with GAT-based attention at a thresh- old 7 0.5. Our method completes all navigation tasks, and the removed LiDAR readings by attention- thresholding do not affect CBF synthesis and navigation performance. There are three scenarios where GaT-based attention is small and computation can be saved: (i) Two agents are far away such that their LiDAR readings are irrelevant with useless information - see Fig. 2a; (ii) Two agents are close such that their LiDAR readings are similar and redundant - see Fig. 2a; (iii) The local agent close to destination such that its navigation task trivial and dose not need information from neighbors see Fig. 2c. The distance-based attention is only small in scenario (i) and thus, does not capture all relevant cases. Moreover, Fig. 2b shows that GAT-based attention is large when LiDAR readings of neighbors shows the computation time of SVM training with different thresholds 7. For ς 0, it trains the SVM with LiDAR readings of all neighbors and requires the most computation, while for y = 1, it trains the SVM with only local LiDAR readings and requires the least computation. An appropriate selection of y ge.g., 0.5) saves almost half of the computation and maintains good performance.
complementary and useful for the local agent. Fig. 2d
'The probability bound can be further reduced by leveraging improved accuracy analysis of SVM [36, 37].
7

---

Table 1: Performance comparison between our method and baselines in three metries. A higher success rate, a higher SPL and a smaller number of time steps represent a better performance.
Method
Metric
Success
SPT.
Time steps
OE-CLBF (ours) unknown environments
0.99 0.02
0.83
0.07
207.51
Neural CLBF unknown environments
0.19 + 0.06
0.16 0.08
760.94 + 269.36
CBF-CLF-QP with RKT in known environments 0.98 0.04
0.67 0.07
458.50 + 65.89
Global CBF-CLF-QP in known environments
0.85 = 0.13 0.77 #0.11
266.31 + 111.39
Performance evaluation. We evaluate our method for a large system with 8 agents in an environ- ment with 6 obstacles of different positions, sizes and shapes - see Fig. 1b for an example. The initial and goal positions are random, and the communication radius is 2.5m. We consider three state-of-the-art baselines: (i) Neural CLBF that leverages offline supervised learning to synthesize the CBF-CLF-OL controller and works in unknown environments [17, 19]: (ii) CBF-CLF-QU with RRT that requires environment knowledge, leverages it to generate collision-free trajectories with RRT, and follows these trajectories with CBF-CLF-QP [42, 43]; (iii) Global CBF-CLF-QP that re- quires enviromment knowledge to formulate CBFs for safe navigation [10, 44]. As it is non-trivial to formulate analytical CBFs for irregular obstacles even with environment knowledge, we approx- imate with circular obstacles of diameter as diagonal length. We use three metrics: success rate, Success weighted by Path Length (SPL), and time steps. The first is the ratio of successful agents total agents, where success represents goal reaching without collision, the second measure combining success rate and path length, and the third characterizes how fast agents reach destinations. We average results over 10 navigation tasks and 5 environments with 3 trials per case.
stringent
Table I shows the results. The proposed OE-CLBF consistently outperforms the baselines in all met- rics, without requiring any knowledge of the environment. Neural CLBF performs worst although also does not need the environment knowledge. This can be explained by the fact that offline su- pervised learning suffers from performance degradation when testing environments are significantly different from training ones, highlighting the importance of online SVM training. CBF-CLF-QP with RRT and global CBF-CLF-QP require full environment knowledge, which may not be prac- tical and presented as benchmark values only for reference. CBF-CLF-QP with RRT achieves comparable success rate to ours, but lower SPL and larger time steps. This is because it randomly explores the entire space and may generate inefficient trajectories. Global CBF-CLF-QP has a lower success rate, but larger SPL and smaller time steps compared to the one with RRT. We attribute this to the fact that approximates rectangular obstacles with large circles and generates conservative agent behaviors, resulting infeasible navigation scenarios for the CBF-CLF-QP controller [22].
7 Discussion
Conclusion. This paper focused on decentralized multi-agent navigation in unknown environments, and proposed the OE-CLBF controller consisting of two main components: (i) an SVM-based CBF- CLF-QP controller that estimates the environment by learning its corresponding CBF with an online SVM, based on instantaneous LiDAR readings, and generates safe actions by solving the resulting CBF-CLF QP; (ii) an attention- based computation reduction that predicts the importance of neigh- boring agents by learning edge weights with GATs, which allows the SVM to be trained with only relevant LiDAR readings. Our method provides provable safety guarantees, by leveraging an accu- racy analysis of the SVM and state invariance of CBFs. We experimentally show that our approach achieves superior performance over basclines and adapts to variety of unknown environments.
Limitations. While the attention-based computation reduction follows the intuition behind the inner-working mechanism of GATs, it is established upon the assumption that larger edge weights learned by the GAT represent higher importance of the corresponding neighbors, which has not been formally proved in theory. Additionally, the exploration mechanism incorporated in our method en- courages agents out of local minima but still does not guarantee global success. Finally, aim to extend our work with more complex non-linear dynamics such unicycle models and drone modes.
8

---

Acknowledgments
This work was supported by European Research Council (ERC) Project 949940 (gAla).
References
[1] E. Lyshevski. Multi-agent distributed coordination and control for aerial systems, In IEEE International Conference Unmanned Aircraft Systems (ICUAS), 2018.
[2] J. Hu, H. Zhang, L. Song, R. Schober, and H. Poor. Cooperative internet of uavs: Dis- tributed trajectory design by multi-agent deep reinforcement learning. IEEE Transactions on Communications, 68(1 10x600--6221, 2020.
[3] D. S. Drew. Multi-agent systems for search and rescue applications. Current Robotics Reports, 2:189-200 200, 2021.
[4] A. Kleiner, A. Farinelli, S. Ramchurn, B. Shi, F. Maffioletti, and R. Reffato. Rmasbench: benchmarking dynamic multi-agent coordination in urban search and rescue. In International Conference on Autonomous Agents and Multiagent Systems (AAMAS), 2013.
[5] Z. Gao and A. Prorok. Constrained environment optimization for prioritized multi-agent navi- gation. IEEE Open Journal of Control Systems, 2023.
[6] Z. Gao, G. Yang, and Prorok. Co-optimization of environment and policies for decentralized multi-agent navigation. arXiv preprint arXiv:2403. /4583, 2024.
[7] G. Wagner and H. Choset. M complete multirobot path planning algorithm with per- formance bounds. In IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS), 2011.
[8] R. Stern, N. Sturtevant, A. Felner, S. Koenig, H. Ma, T. Walker, J. Li, D. Atzmon, L. Cohen, Kumar, et al. Multi-agent pathfinding: Definitions, variants, and benchmarks. Interna- tional Symposium on Combinatorial Search (SoCS), 2019.
[9] D. Focad, A. Ghifari, M. B. Kusuma, N. Hanafiah, and E. Gunawan. A systematic literature review of a* pathfinding. Procedia Computer Science, 179:507-514, 2021.
[10] A. D. Ames, J. W. Grizzle, and P. Tabuada. Control barrier function based quadratic programs with application to adaptive cruise control. In IEEE Conference on Decision and Control (CDC),2014,
[11] Q. Nguyen and K. Sreenath. Exponential control barrier functions for enforcing high relative- degree safety-critical constraints. In IEEE American Control Conference (ACC), 2016.
[12] W. Xiao and C. Belta. High-order control barrier functions. IEEE Transactions on Automatic Control, 6767):3655-366, 2022.
[13] U. Borrmann, L. Wang, A. D. Ames, and M. Egerstedt, Control barrier certificates for safe swarm behavior. IFAC- MEACCPPaprsOOLLine 48(27):68-77 (3)))6688,,777 2015.
[14] S.-C. Hsu, X. Xu, and A. D. Ames. Control barrier function based quadratic programs with application to bipedal robotic walking. In IEEE American Control Conference (ACC), 2015.
[15] Y. Pan, C.A. Cheng, K. Saigol, K. Lee, X. Yan, E. Theodorou, and B. Boots. Agile tonomous driving using end-to-end deep imitation learning, In Robotics: Science and Systems (RSS), 2018
[16] D. Cofer, Amundson, R. Sattigeri, A. Passi, C. Boggs, E. Smith, L. Gilham, Byun, and S. Rayadurgam. Run-time assurance for learning- based aireraft taxiing. In AIAA/EEE Digital Avionics Systems Conference (DASC), 2020.

---

[17] C. Dawson, Z. Qin, S. Gao, and C. Fan. Safe nonlinear control using robust neural Iyapunov. barrier functions. In Conference on Robot Learning (CoRL., 2022.
[18] S. Zhang, O. So, K. Garg, and C. Fan. Gcbf+: A neural graph control barrier function frame- work for distributed safe multi-agent control. arXiv preprint arXiv:2401. 14554, 2024.
[19] C. Dawson, B. Lowenkamp. Goff, and C. Fan. Learning safe, generalizable perception- based hybrid control with certificates. IEEE Robotics and Automation Letters, ((2):1904-1911 2022.
[20] X. Tan and V. Dimarogonas. Distributed implementation of control barrier functions for multi-agent systems. IEEE Control Systems Letters, 6:1879-1884, 2022.
[21] M. Jankovic, M. Santillo, and Y. Wang. Multiagent systems with cbf-based controllers: Colli- sion avoidance and liveness from instability. IEEE Transactions on Control Systems Technol- ogy, 2023.
[22] Z. Gao, G. Yang, and A. Prorok. Online control barrier functions for decentralized multi-agent navigation. In IEEE International Symposium on Multi-Robes and Multi-Agent Systems (MRS), 2023.
[23] K. D. Julian, R. Lee, and M. J. Kochenderfer. Validation of image-based neural network controllers through adaptive stress testing. In IEEE International Conference on Intelligent Transportation Systems (ITSC), 2020.
[24] S. M. Katz, A. L. Corso, C. A. Strong, and M. J. Kochenderfer. Verification of image-based neural network controllers using generative models. Journal of Aerospace Information Sys- tems, 19(9):574-584 2022.
[25] S. Dean, N. Matni, B. Recht, and V. Ye. Robust guarantees for perception-based control. In Learning for Dynamics and Control (L4DC), 2020.
[26] S. Dean, A. Taylor, R. Cosner, B. Recht, and A. Ames. Guaranteeing safety learned per- ception modules via measurement-robust control barrier functions. In Conference on Robot Learning (CoRI.), 2021.
[27] A. Murillo-González and Poveda. Data-assisted vision-based hybrid control for robust stabilization with obstacle avoidance via learning of perception maps. In IEEE American Control Conference (ACC), 2022.
[28] M. Srinivasan, Dabholkar, S. Coogan, and Vela. Synthesis of control barrier functions using supervised machine learning approach. In JEEE/RSJ International Conference on Intelligent Robots and Systems (IROS), 2020.
[29] M. A. Khan, T. Ibuki, and A. Chatterjee. Gaussian control barrier functions: Non-parametric paradigm safety, IEEE Access, 10:99823-99836. 2022.
[30] S. Keyumarsi, M. W. S. Atman, and A. Gusrialdi. Lidar-based online control barrier func- tion synthesis for safe navigation unknown environments. IEEE Robotics and Automation Letters, 2023.
[31] A. D. Ames, K. Galloway, K. Sreenath, and J. W. Grizzle. Rapidly exponentially stabiliz- ing control Yyаpunov functions and hybrid zero dynamics. JEEE Transactions on Automatic Control, 59(4):876-89) 2014.
[32] P. Veličković, G. Cucurull, A. Casanova, A. Romero, P. Liò, and Y. Bengio. Graph attention networks. In International Conference on Learning Representations (ICLR), 2018.
[33] R. Herbrich and T. Graepel. A pac-bayesian margin bound for linear classifiers: Why svms work. In Advances in Neural Information Processing Systems (NeurIPS), 2000.
10

---

[34] Т. Wen and A. Edelman. Support vector machine lagrange multipliers and simplex volume decompositions. SIAM J. Matrix Anal. Appl, 21(1):1-32 2000.
[35] Shawe-Taylor, Bartlett, R. C. Williamson, and M. Anthony. Structural risk minimization over data-dependent hierarchies. IEEE Transactions Information Theory, 44(5): 1998.
[36] N.-E. Ayat, M. Cheriet, and C. Y. Suen. Automatic model selection for the optimization of svm kernels. Pattern Recognition,
2005.
[37] J. Zeng, Z.-H. Tan, T. Matsunaga, and T. Shirai. Generalization of parameter selection of svm and Is-svm for regression. Machine Learning and Knowledge Extraction, 2019
[38] B. Scholkopf, K.-K. Sung, C. J. Burges, F. Girosi, P. Niyogi, T. Poggio, and Vapnik. Com- paring support vector machines with gaussian kernels to radial basis function classifiers. JEEE Transactions on Signal Processing. 45(11):2758-2777 2765, 1997.
[39] G. Notomista, M. Wang, M. Schwager, and M. Egerstedt. Enhancing game-theoretic au- tonomous car racing using control barrier functions. In IEEE International Conference on Robotics and Automation (ICRA), 2020.
[40] S. He, J. Zeng, B. Zhang, and K. Sreenath. Rule-based safety-critical control design using control barrier functions with application to autonomous lane change. In IEEE American Control Conference (ACC), 2021.
[41] M. Tayal, B. G. Goswami, Rajgopal, R. Singh, T. Rao, Keshavan, P. Jagtap, and S. Kolathaya, A collision cone approach for control barrier functions. arXiv preprint 2xXiv:2403.0704. 2024.
[42] G. Yang, B. Vang, Z. Serlin, C. Belta, and R. Tron. Sampling-based motion planning via control barrier functions. In International Conference on Automation, Control and Robots (ICACR), 2019.
[43] A. Ahmad, C. Belta, and Tron. Adaptive sampling-baid motion planning with control barrier functions. In IEEE Conference Decision and Control (CDC), 2022.
[44] D. Zhang, G. Yang, and R. P. Khurshid. Haptic telcoperation of uavs through control barrier functions. IEEE Transactions on Haptics, 13(1):109-115, 2020.
[45] M. Tayal, R. Singh, Keshavan, and S. Kolathaya. Control barrier functions in dynamic uavs for kinematic obstacle avoidance: A collision cone approach. In IEEE American Control Conference (ACC), 2024.
[46] A. Manjunath and Q Nguyen. Safe and robust motion planning for dynamic robotics via control barrier functions. In IEEE Conference on Decision and Control (CDC), 2021.
[47] Y. Lyu, J. M. Dolan, and W. Luo. Decentralized safe navigation for multi-agent systems via risk-aware weighted buffered voronoi cells. In International Conference on Autonomous Agents and Multiagent Systems (AAMAS). 2023.
[48] I. Jang and H. Kim. Safe control for navigation in cluttered space using multiple 1yapunov- based control barrier functions. IEEE Robotics and Automation Letters, 2024.
[49] M. Cavorsi, L. Sabattini, and S. Gil. Multi-robot adversarial resilience using control barrier functions. JEEE Transactions on Robotics, 2023.
[50] L. Lindemann and D. V. Dimarogonas. Control barrier functions for multi-agent systems under conflicting local signal temporal logic tasks. IEEE Control Systems Letters, 3(3):757-762, 2019.

---

[51] C. Yu, H. Yu, and S. Gao. Learning control admissibility models with graph neural networks for multi-agent navigation. In Conference on Robot Learning (CoRI.), 2023.
[52] G. Raja, T. Mökkönen, and R. Ghabcheloo. Safe control using occupancy grid map-based control barrier function (ogm-cbf), arXiv preprint 2005.02405. 2024.
[53] Zeng, Zhang, and K. Sreenath. Safety-critical model predictive control with discrete-time control barrier function. In IEEE American Control Conference (ACC), 2021.
[54] J. M. Phillips, N. Bedrossian, and L. E. Kavraki. Guided expansive spaces trees: A search strategy for motion-and cost-constrainee state spaces. In IEEE International Conference on Robotics and Automation (ICRA), pages 3968-3973, 2004.
[55] F. Scarselli, M. Gori, A. C. Tsoi, M. Hagenbuchner, and G. Monfardini. The graph neural network model. IEEE Transactions on Neural Networks, 20(1):61-80, 2008.
[56] Bruna, W. Zaremba, A. Szlam, and Y. LeCun. Spectral networks and locally connected networks graphs. arXiv preprint arXiv:1312.6203. 2013.
[57] Z. Gao, E. Isufi, and A. Ribeiro. Stochastic graph neural networks. JEEE Transactions on Signal Processing, 69:4428 4443, 2021.
[58] Y. Hu, S. Fang, Z. Lei, Y. Zhong, and S. Chen. Where2comm: Communication--ffiiccnn collab- orative perception via spatial confidence maps. In Advances in Neural Information Processing Systems (NeurIPS), 2022.
[59] A. Aijazi, P. Checchin, and L. Trassoudaine. Detecting and updating changes in lidar point clouds for automatic 3d urban cartography. ISPRS Annals of the Photogranmetry, Remote Sensing and Spatial Information Sciences, 2:7-12, 2013.
[60] T. Raj, F. Hanim Hashim, A. Baseri Huddin, M. F. Ibrahim, and A. Hussain. A survey on lidar scanning mechanisms. Electronics, 955)744, 2020.
[61] D. Iordan and G. Popescu. The accuracy of lidar measurements for the different land cover categories. Scientific Papers. Series E. Land Reclamation, Earth Observation Surveying, Environmental Engineering, 4:158-164, 2015.
[62] A. Elaksher, T. Ali, and A. Alharthy. quantitative assessment of lidar data accuracy. Remote Sensing, 15(2))442, 2023.
[63] N. Csanyi and C. K. Toth. Improvement of lidar data accuracy using lidar-specific ground targets. Photogrammetric Engineering & Remote Sensing, 73(4))385-366, 2007.
[64] T.-T. Nguyen, C.-H. Cheng, D.-G. Liu, and M.-H. Le. Improvement of accuracy and precision of the lidar system working in high background light conditions. Electronics, 11(1):45, 2021.
12

---

A Related Works
We provide more details about related works in the following comparison table, which categorizes prior approaches with respect to known v.s. unknown environments, known v.s. unknown dynamics and online v.s. offline learning. In work, "environment" refers the external configuration of the map that is independent of the agents, in particular it refers to the obstacle layout in the space (e.g., the obstacle position, shape and size). We consider agent dynamics and the communication capacity internal properties of the agents, which are assumed known for our controller. This is a standard setting in the study of multi-agent navigation, particularly when dealing with unknown environments.
Table 2: Comparison table of related works
Related Works
Known or Unknown Environment
Known or Unknown Dynamics
Online or Offine Learning
[10, 11, 13, 14,
Known
Known
20, 21, 45, 46, 43,
47, 491
[25, 27, 51]
Known
Offline
[18, 17, 19, 23, 24)
Unknown
Known
Offline
1221
Known
Known
Online
[52]
Unknown
Known
Online
The majority of prior approaches focus on the setting with known environments (maps) and pre- defined dynamics to design safety-critical controllers for navigation. Learning-based approaches offer way leverage sensing inputs, including LiDAR readings and images, for safe navigation in unknown environments, while existing works mainly focus on offline supervised learning to syn- thesize controllers or estimate agent states. This suffers from performance degradation when testing scenarios are significantly different from training ones, and cannot provide safety guarantees due to the nature of end-to-end learning. The work in [22] leverages online learning to tune hyperpa- rameters of the control barrier functions (CBF) in real-time but requires the knowledge of the map for deployment, while [52] studies a single-agent scenario in discrete grid maps and assumes the existence of controller capable of following the discrete trajectory.
Note that all these works require the knowledge of system dynamics to either formulate analytic safety constraints or generate ground-truth labels for training. With this contextualization in mind, our work develops a sensing-feedbace controller for multi-agent navigation in unknown environ- ments. Our method learns the CBF the surrounding environment with a support vector machine (SVM) an online manner, enabling deployment in any new environment without prior knowledge. Moreover, leverage graph attention learning select important neighbors' states reduce online computation and provide provable safety guarantees.
B Exploration Mechanism
While control inputs satisfying the CBF constraint always remain safe and control inputs satisfying the CLF constraint lead the agent to its goal, the QP in (5) becomes infeasible these sets have an empty intersection. The latter causes agents to get stuck in complex navigation scenarios, such as environments with non-convex obstacle regions or where the destination is located directly on the propose exploration
opposite side of an obstacle [53, 19, 22]. To overcome this challenge, mechanism inspired by the Expansive Search Tree (EST) [54] and integrate it into method to encourage agents out of local minima. and integrate it into our method to ensure successful agent navigation.
Specifically, we consider the standard QP controller (5) as the convergence mode, and switch to the exploration mode when the QP controller becomes infeasible, i.e., feasible control satisfies both convergence and safety constraints in (6). The exploration mode samples a state Xsample P Pstate.dmee from its nearby space with the sampling radius determined by the maximum scanning
13

---

Algorithm Exploration Mechanism (for agent A,)
Input: State x,, target x safety constraints S
2: Output: Control action u,
3: if' QP controller infeasible then
4: Switch to the exploration mode
5: for fexplore l.... Nexplore do
6:
while exploration mode do
7:
Sample state Xsample ~ deta
8:
Attempt to generate control action u, steer towards Xsample
9:
u, violates safety constraints then
10:
Discard
11:
else
12:
break
13:
Apply u, to system (1)
14:
Scan the environment collect LiDAR readings
15:
Train SVM with the latest LiDAR readings to update the environment CBF
16:
Switch to the convergence mode
distance dmax of the LiDAR scanner, and generates action by the QP controller to steer the agent towards the sampled state Xsample.
As we collect LiDAR readings at each time step and perform online SVM training, each agent estimates the surrounding environment a real-time manner. For any generated action that violates safety constraints, the previously sampled state will be discarded and new state will be sampled. After repeating this sampling process for fixed number of times Nexplore- switch back to the convergence mode and navigates the agents towards their destinations. Algorithm summarizes the exploration mechanism integrated in our method.
C Methodology Details
We provide additional details about the proposed method in this section.
C.1 Graph Attention Networks
Graph attention networks (GATs) [32] variant of graph neural networks (GNNs) [55, 56, 57] that leverage the attention mechanism to extract task-relevant features from graph data. Differ- ent from conventional GNNs, which aggregate neighborhood information with (pre-defined) fixed weights. GATs allow to differentiate neighbors w.r.t. their contributions when aggregating neigh- borhood information to generate task-relevant features.
Specifically, consider a graph G (V,E) with the node set V =1,,.... f1,...., ......,,]].. and the edge set E. The graph structure can be captured by support matrix W with (i, entry waj [W]; * if node is connected to node j. i.e., (i,j) E E, o i j. and [W]y 0 otherwise. The graph data can be captured by graph signal X, which is matrix whose ith row x; = [X], contains the feature of node GATs are capable of assigning different attention coefficients {[W to the neighboring nodes {j)jEN; of each node i, which represent the importance of the neighbors' features for the feature update of the local node. These attention coefficients W are learned with shared self-attention mechanism, enabling to quantify the relevance among graph nodes. Therefore, GATs are suitable candidates characterize the importance of the neighbors' LiDAR readings in synthesizing the CBF of the unknown environment at the local agent.
The key component of the GAT lies in the attention mechanism, which computes attention coeffi- cients between neighboring nodes. For the local node and its neighboring node j, the unnormalized attention coefficient is calculated as
Gj = a Hx, Hx
(11)
14

---

where H is learnable weight matrix (i.e., linear transformation) that maps the node features and x, to some higher-order features, and a(-) is a shared attention function such as feedforward neural network. The unnormalized Eij then passed through a softmax function to get the normalized attention coefficients as
exp(ei))
Wij ΣKEN, exp(e:=)*
(12)
which makes the sum of neighbors' attention coefficients equal to one for ease of probabilisstc interpretation. With the normalized attention coefficients W, each node i generates its task-relevant feature as a weighted sum of neighbors' higher-order features
x =
Σ JEN.
Wiy Hx,),
(13)
where a-) is the non-linearity function such as ReLU and absolute value. Fig. 3 illustrates the attention mechanism, where the task-relevant feature, in our case, is the predicted action x u that mimics the expert action uy given in the training data.
Discussion. The attention coefficients learned by the GAT weigh the neighboring features when generating the task-relevant feature, i.e., the predicted action. That is, they represent how much the neighboring features are accounted for in the generation of the task-relevant feature. Therefore, it provides justifications for considering the attention coefficients as indicators to quantify the impor- tance of the neighboring agents to the local agent, and for leveraging the latter to remove LiDAR readings of less important neighbors to reduce computation of online SVM training see Section 4.2 of the main paper.
1012
Update
Xg
wmmm
x
Whi0
difa
X4
X6
Figure 3. An illustration of the attention mechanism within the GAT [32]. The local node 1 aggregates the neighbors' features weighted by their corresponding attention coefficients, and leverages the latter to update its task-relevant feature x(-
C.2 Methodology Framework
The proposed method contains two main components: SVM-hased CBF-CLF-QP navigation and attention-based computation reduction. The former generates safe actions for the agents approach their destinations (Section 4.1 of the main paper), while the latter identifies important neighbors with the attention mechanism of the GAT and uses only LiDAR readings of these neighbors for online SVM training to reduce real-time computation (Section 4.2 of the main paper). Fig. 4 provides an overview for the general framework of the proposed OE-CLBF controller to ease understanding.
D Proof of Theorem 1
We start the proof by defining the generalization error of the learned SVM classifier fåvm as the probability risk in classifying any unseen data (z, y), i.e..
R(fšvm) Pr(ffvm + v).
(14)
15

---

Agent X
LiDAR readings 2
Graph nilention network (GAT)
Communications
scanning
Aggregatid readings 2/" and heog""
Agent actions U
Attention coefficients W!!!
Support vecior machine (SVM)
Thresholding
SVM-buoed CBF
CBF-CLF-QE controller
Neighbors high "value"
Attention-based Computation Reduction
SVM-based CBF-CLF-QP Navigation
Figure 4. General framework of the proposed OE CLBF controller, which contains SVM-base CBF-CLF.QP navigation and attention-based computation reduction. The former senses the surrounding unknown environ- ment with LiDAR scanner, synthesizes the corresponding CBF with online SVM, and incorporates it into the CBF-CL.--Q C- controller generate agent actions. The latter quantifies the importance of the neighboring agents the local agent with GAT, thresholds useless LiDAR readings from less important neighbors, and uses only useful and relevant LiDAR readings for online SVM trianing to reduce computation.
where Pr(.) is the probability measure and (z, y) is drawn randomly from the space of interest. With the conditions provided in the theorem and the LiDAR readings 2 {(Z), vI) we can follow Theorem of [33] to bound the probability risk as
R(fsvad S ) ( loge
SeL (n(fīvM)
log, (32L) +In ( with x(fvvx))
8C
(
(15)
For the learned safety function hSvm from fšVM (15) is equivalent to that for any position z & Z, if (zvxa(z) > O, it holds that
Pr(z E Crafe) 2 8
(16)
with
is ( loga (<(F5vM) log, (32T) +In
SeL
L2
with k((SvM)) = C
8C
) (17)
where Caate the safety set of the environment. Define the safety set CSVM w.r.t. the learned safety function hyvM as
CsVM,sate = {z) > 0 for all z E E).
(18)
By substituting this safety function hşvM into the CBF constraint (3) and the latter into the CBF- CLF-QP controller (6), we can follow Theorem [12) to prove that there exists a class K. function a (hšvv)) such that the haverbbaed safety set CsvM,safe [cf. (18)) is forward invariant, ie.. the agent will stay in safe with generated actions.
Since the based safety set CsvM.safe depends on the learned safety function hšvm- which, in turn, depends on the training data L LiDAR readings 2, and each agent only re-scans these LiDAR readings every At, we assume CsVM,sae keeps the same time interval At. Therefore, we have
(0) CsVM.safe
(19)
for any time until the next time interval At. By combining (16) and (19), we complete the proof that
(t(z(() E Csate) 2 1 - 8
(20)
16

---

Truining procedure of GAT
10
Training loss
10
M
2000
4000
6000
8000
Number of epochs
Figure S. The training procedure of graph attention network (GAT) in the framework of imitation learning.
with
5 loga ( for any time in the next interval At.
8eL log, +22)+Inn
with K =((Evv)))=((( ((( ( a
8C )9
(21)
(((fsvm))
E Additional Experiments
We conduct additional experiments to further validate methodology and corroborate theory.
E.1
SVM-based Safety Function
The goal of this experiment is to verify the accuracy of the SVM classifier for learning the safety region of the unknown environment. Specifically, we train the SVM classifier with different numbers of random LiDAR readings from the environment in Fig. 1b, and evaluate the decision function of the trained SVM 100 randomly sampled (unseen) LiDAR readings over the entire environment.
Table 3 shows the results. We see that the evaluation accuracy increases and approaches one as the number of training samples increases. This indicates that the generalization error of the SVM-bbsed safety function approaches zero with the number of training samples, which corroborates our theo- retical result in Theorem 1. Moreover, the SVM-based safety function achieves good performance even with small number of training samples (e.g.. 250), which highlights the strong classification capacity of the SVM.
Table Accuracy of the SVM-based safety function
Number of Training Samples
250
500
1000
2500
5000
Testing Accuracy
0.87+10.4
0.8910.02
0.90=10.04
0.93
0.97:10.02
E.2 Graph Attention Learning.
The goal of the following experiments is to further validate the effectiveness of the attention mech- anism in Section 4.2. First, we show the training procedure of the graph attention network (GAT), which mimics the expert action, i.e., the one generated with all neighborhood information, following an imitation learning framework. The initial and goal positions S and of the agents are initialized randomly in the environment and the obstacles are distributed between S and We generate 200 multi-agent trajectories of 200 time steps with 4 10 samples construct the dataset, and leverage the ADAM optimizer with learning rate 10 for training. The mean square error (MSE) is used as the loss function to measure the difference between the predicted action and the expert action.
17

---

250
1000
200
800
150
Time step
600
Time stop
A
100
400
200
200
(a)
(b)
Figure 6. (a) Navigation procedure of our method with exploration mechanism, where all agents complete their tasks successfully, (b) Navigation procedure of our method without exploration mechanism, where agent A1 gets stuck in local minima because of limited sensing and communication ranges. Blue circles are initial positions and green squares are destinations. Black rectangles obstacles and blue-to-green lines agent trajectories. Color bar represents time scale, showing that agent-agent agent-obstacle collision occurs.
Fig. 5 plots the training procedure of the GAT 10 epochs. We that the training loss de- creases with the number of epochs and the decreasing rate reduces; ultimately, reaching stationary solution. The convergent loss is small, which indicates a good performance of the trained GAT for action generation and good prediction of attention coefficients for neighbors' importance.
Second, we emphasize the performance of the GAT by comparing with a heuristic method inspired by the attention learning mechanism [58]2, in addition to the distance-based bascline considered in Section 6. Specifically, we follow the idea of spatial confidence-awand communication in [58] to develop a heuristic method to act strong baseline, i.e., we assuming that agents have less confidence in areas where there is no LiDAR detection and prompt communication in such regions.
Table 4 provides the comparison results. The proposed method achieves the best performance with the least computation time of the online SVM training. The spatial confidence- based baseline per- forms worse than the proposed method in all three metrics because our GNN-based attention better captures the importance of neighbors' states. Moreover, the online SVM training time of the spatial confidence-based baseline is higher than our method because: (i) some less-confident areas may be irrelevant to agents' navigation and it is not necessary to provide estimation for these areas; (ii) some agents in the direction less-confident areas are too far from the local agent and their LiDAR readings are irrelevant to the local navigation. Both facts result in unnecessary LiDAR readings and more online computation. The distance-bar based baseline obtains the worst performance attention only based on the distance between two agents without considering their LiDAR reading relevance. Lastly, we remark that any attention computing mechanism be applied to SVM- based CBF-CLF-QP framework, to develop extended variants for further performance improvement.
computes
E.3 Exploration Mechanism.
The goal of this experiment is show the necessity of incorporating the exploration mechanism [Appendix B] into our method for resolving challenging navigation scenarios. Fig. 6 shows one example of these scenarios, where the obstacles form non-convex safety space and the agent easily
"The attention learning mechanism in [58] cannot be applied directly to our SVM-based CBF-CLF-QP controller. Specifically, it computes atlentions among agents via end-to-end learning for specific downstream task, where attentions the detection loss based on given ground truth labels in a supervised manner). However, our case, challenging to define the loss function for training because is non-trivial to measure how well the generated attention values quantify the neighbors' importance w.r.t. the proposed SVM-based CBF-CLF-OR CLF-QP controller. and [58] can not be applied directly in setting.
neural network outputs trained using well-defined task-specific loss function (e.g.
Therefore, there is no end-to and-oo-end loss function
18

---

Table Performance our attention mechanism and baselines
Method
Success Rate
SPI.
Time Step
SVM Training Time (ms)
DE CLBF (Our Method)
0.90
0.03:00007
207.51 36.76
4.01:::353
Spatial Contidence-bseed Baseline
0.81=0.17
0.71
396.71=1800 180.87
4.48::3.24
Distance-based Baseline
0.78=0.20
0.70=0.199
180.51=188.27
4.54::3.04
gets stuck in local region due to its limited sensing and communication ranges. We see that our method navigates all agents towards destinations successfully in Fig. 6a, where the exploration mechanism pulls agent A1 out the local dilemma by searching over its nearby space. The method without exploration mechanism fails the navigation task of agent A in Fig. 6b, because can only generate actions that stay in the local safety set.
E,4 Ablation Study
The goal of the following experiments is perform an ablation study for the proposed method. First, we evaluate our method with different cut-off thresholds for the attention mechanism and show the results in Table 5. The performance of the proposed method increases as the value of threshold decreases. This is because lower threshold allows for more communication among agents, thereby providing each agent with more LiDAR readings from its neighbors, which in turn leads more accurate CBF estimates with the SVM and improves the navigation performance.
Table Performance with different cut-off thresholds for the attention mechanism
Threshold
Metric
Success Rate
SPL
Time Step
0.3
0.99+0.02
0.85=+0.11
199.341:3.18
0.4
0.99+0.02
0.83=0.12
20..03-84.31
0.5
0.99:10.02
0.83
207.51136.76
0.6
0.97:10.05
0.81=0.09
210.95=65.69
0.7
0.94=10.08
0.78=0.13
230.83=10..74
Second, we evaluate our method without the exploration mechanism and present the results in Table The SVM-based QP controller performs worse without the exploration mechanism all three metries. This can be explained by the infeasibility of the SVM-based CBF-CLF-QP controller in certain challenging navigation scenarios, as discussed in Appendix B.
Table Performance with and without the exploration mechanism
Metric
Success Rate
SPL
Time Step
SVM-based CBF-CLF-OO QP with exploration
0.99+0..2
0.83=10.07
207.51
SVM- UBF-CLF-QU QP without exploration
0.68+10.24
0.62:+0.22
426.29=208.36
E.5
Method Robustness
The goal of the following experiments is study the robustness of the proposed method real- world deployment effects, i.c.. the update frequency of online LiDAR readings and the sensor noise on LiDAR readings.
First, we set the update time as 0.1s in our work, which is reasonable update frequency for practical systems with LiDAR scanners [59, 60]. Table shows the performance of the proposed method with different update times of online LiDAR readings. We see that the performance degrades as
the update time increases (i.e., the update frequency decreases) expected. This is because low frequency leads to delay in LiDAR reading updates and the CBF constraint learned by the
19

---

SVM may be outdated, resulting in worse environment estimation and performance degradation. However, the proposed method maintains good performance for relatively low update frequencies, which validates the robustness of the proposed method to update frequencies.
Table 7:
Performance with different update times of online LiDAR readings
Update Time (s)
Metric
Success Rate
Time Step
0.1
0.99
0.83.10.07
207.51-136.76
0.15
0.95#0008
0.79+10110
217.55=
0.2
0.92:10.110
0.77++0.14
263.06:1:07002
0.25
0.89+10.12
0.74
289.06++188.88
0.3
0.8410.10
0.72:10.13
310.85:191.73
Second, we evaluate the proposed method with different levels of random noise on LiDAR readings of the agents, where the imposed noise each axis (i.e., x-axis and y-axis) is sampled randomly from the interval [0, [ and 3 is the parameter that controls the noise level with the unit as meter. Table 8 shows the results. We see that the performance of the proposed method degrades with the increase of noise level. This is expected because larger noise on LiDAR readings results in less accurate estimation the SVM-based CBF constraint. However, the proposed method remains robust to moderate noise and maintains good performance in all cases. Lastly, we clarify that the magnitudes of the noise considered in these experiments are reasonable in practical systems [61, 62], and techniques have been developed alleviate the noise LiDAR readings [63, 64).
Table 8: Performance with different levels of sensor noise on LiDAR readings
Noise Level / (m) Metric
Success Rate
SPI.
Time Step
0.99110.22
0.8310.07
207.51
0.005
0.95110.08
0.78:10.10
223.55.179.33
0.93+10.16
0.76
249.93+ 144.02
0.025
0.94+:0008
0.74
254.95 105.70
0.05
0.91110.13
0.74.10.15
256.25 123.27
0.1
0.86::0.19
301.18:165.99 0.72+00.16
E.6 More Examples.
Figs. 7a-7f show more examples of agents' trajectories generated by our method, for different nav- igation tasks in unknown environments with different obstacle positions, sizes and shapes. We see that in all these scenarios, all agents complete their navigation tasks successfully. where the success represents the agents reaching their destinations without collision within the maximal time step, and do not require any prior knowledge about environments, even some challenging scenarios with cluttered obstacles. This highlights the effectiveness of the proposed OE-CLBF controller, which is applicable in unknown environments with different obstacle layouts.
20

---

0.
160
360
Time step
120
Time step
240
80
120
40
(a)
(b)
250
250
200
200
150
Time step
150
Time step
100
(c)
(d)
160
135
Time step
120
Time step
90
80
45
40
(f)
Figure 7. Navigation procedures of our method for different navigation tasks in different unknown environ- ments with different obstacle layouts (i.e., different obstacle positions, sizes and shapes), and method capable completing navigation tasks successfully without collision either obstacles or among agents.
21


Reviews:
[{"review_id": "4WeMqxkYsZ", "reviewer": "Reviewer_wuRr", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": 3, "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": "This paper studies multi-agent safe navigation in unknown environment, and introduces an onlinear learning of CBF with SVM using LiDAR sensing. GAT is adopted to predict the importance of the neighbor agents. Experiments validate the effectiveness of the proposed method.", "summary_of_recommendation": "I would be happy to increase my rating if the theory details are clarified and more experiments are conducted as I mentioned in weakness.", "technical_quality": 3, "clarity_of_presentation": 2, "potential_impact": 3, "robotics_focus": 3, "quality_of_limitations": 3, "questions_for_rebuttal": "See weakness.", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "SwJZNQnnXc", "reviewer": "Reviewer_nmUB", "summary": "", "questions": "", "limitations": "", "rating": 2, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": 3, "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": "This paper proposes an Online Exploration-based Control Lyapunov Barrier Function (OE-CLBF) controller for safe decentralized multi-agent navigation in unknown environments.", "summary_of_recommendation": "While this work may have potential contributions to safe multi-agent planning and control, the current lack of clarity and addressing of practical concerns make it difficult to recommend for acceptance in its present form. Substantial revisions are needed to improve the presentation and address the raised issues.", "technical_quality": 2, "clarity_of_presentation": 2, "potential_impact": 2, "robotics_focus": 2, "quality_of_limitations": 2, "questions_for_rebuttal": "- How does this work compare to and improve upon existing approaches for multi-agent navigation in unknown environments, particularly in terms of the assumptions made about the environment, agent dynamics, and available information? A clearer comparison and positioning relative to prior work seems needed.\n\n- What is the real-world feasibility and robustness of this approach, especially regarding computational requirements, update frequency, sensor noise handling, and applicability to more complex agent dynamics? More details on practical implementation concerns appear necessary.\n\n- Can you provide more clarity and justification for some of the key technical elements, such as the binary encoding of LiDAR data, the theoretical guarantees in Theorem 1, and the process for obtaining expert demonstrations for the graph attention component?", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "Mtyfvo75Zp", "reviewer": "Reviewer_tTRi", "summary": "", "questions": "", "limitations": "", "rating": 4, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": 4, "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": "The paper addresses the challenge of decentralized multi-agent navigation in unknown environments by proposing an Online Exploration-based Control Lyapunov Barrier Function controller. The OE-CLBF overcomes the limitation of full environment knowledge by learning Control Barrier Functions using online Support Vector Machine training with local LiDAR data. The paper contributes an SVM based method for learning CBFs in real time, an graph attention network to reduce computational load and it provides a safety guarantee.", "summary_of_recommendation": "The paper seems to be done with the necessary due dilligence done and was a joy to read.", "technical_quality": 5, "clarity_of_presentation": 5, "potential_impact": 3, "robotics_focus": 4, "quality_of_limitations": 3, "questions_for_rebuttal": "I have no questions to the authors regarding submission.", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Meta-review: This paper studies multi-agent safe navigation in an unknown environment and introduces an online learning of CBF with SVM using LiDAR data. GAT is adopted to predict the importance of the neighbor agents.

Strengths
- The motivation for safe multi-agent navigation in an unknown environment is sound and clear.
- The idea of incorporating SVM into CBF-CLF-QP is interesting, especially considering its potential in updating the CBF in an online manner.

Limitations
- The method requires further comparison (both qualitative and quantitative) with existing approaches for multi-agent navigation in unknown environments, particularly in terms of the assumptions made about the environment, agent dynamics, and available information.
- The authors should properly discuss the feasibility and applicability of the proposed method in terms of more general dynamical systems, computational requirements, and sensor noise. Quantitative analysis in this regard would further strengthen the paper.
- More ablation studies and justification is required for some of the key technical elements, such as to highlight the utility of binary encoding of LiDAR data, to show the effectiveness of attention, exploration mechanism in Alg 1, etc.

**Comments post rebuttal**

The additional experiment results make the contribution of this work more clear and convincing. It would be good to include these results as well as a discussion on the online computational complexity of the proposed algorithm in the final version of the paper. There are some additional small suggestions by reviewers that could be incorporated to further improve the paper clarity and exposition.
Decision: Accept