Provably Safe Online Multi-Agent Navigation in Unknown Environments

Authors: zhan  gao
guang  yang
jasmine  bayrooti
amanda  prorok
Venue: robot-learning_org_CoRL_2024_Conference
Published: 2024-06-06 16:18:36

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.

Main paper: 
 introduction: 
 Multi-agent systems have garnered significant attention for applications such as distributed aerial surveillance [1, 2] , search and rescue [3, 4] , and warehouse transportation [5, 6] , where safe and efficient navigation is a key enabling technique. In this work, we focus on the problem of decentralized multi-agent 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, traditional CBF-based approaches require full knowledge of the environment, e.g., positions and shapes of obstacles, to formulate a closed-form expression for the safety function [13, 14] . Such information 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 to 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 a potential solution, which, however, remains an open question as traditional control-based methods lack the expressiveness to deal with rich sensing models. For example, it is unclear how to handcraft differentiable CBFs with a discrete number of observations (e.g., visual images or LiDAR readings).Learning-based methods have been shown successful for sensing-feedback control tasks [15, 16] , and recent works have used neural networks to approximate CBFs and CLFs to design observationfeedback controllers to navigate in unknown environments [17, 18, 19] . However, these approaches often sacrifice safety guarantees of the controller. Moreover, they follow an offline supervised learning 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-feedback controller for decentralized multi-agent navigation in unknown environments, by utilizing an online learning-based 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 received from neighboring agents, and incorporate the SVM-based CBF into a quadratic programming (QP) controller for safe navigation in unknown environments. Moreover, we train SVM in an online manner with instantaneous LiDAR readings, which adapts to any new (unseen) environments.(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-based method by leveraging the accuracy 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-critical controls [10, 11, 12] .Traditional approaches often assume a centralized setting with global information of the environment or agents to formulate safety functions [13, 14] . Distributed CBFs consider the partial observability of agents to provide decentralized safe navigation [20, 21] , 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 to handcraft 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 is synthesized and then independently verified. The work in [23] uses adversarial testing to assess safety and searches for the most likely input that causes the vision-based controller to fail, while [24] trains a 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 assume that the environment (including all obstacle locations) is known prior to deployment, limiting its generalization to unknown environments. The authors in [28, 29] leverage SVM and Gaussian process (GP), respectively, to approximate the CBF of the unknown environment with LiDAR readings. However, all these works consider a 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 observation-feedback controllers. These neural network based methods enjoy scalability benefits and are versatile w.r.t. the input space. However, they follow an offline supervised learning framework, which leads to significant performance degradation if deploying environments are vastly different from training ones. Moreover, the learned barrier certificate is an approximation of the true one and it is difficult to provide theoretical safety guarantees. 
preliminaries: 
 System dynamics. Consider a multi-agent system of n agentsEQUATION) with x i the state, u i the control input, ẋi the time derivative of x i , and f (x i ), g(x i ) the flow vectors.The CLF is designed to encode the goal reaching constraint, i.e., the saistification of CLF constraints guarantees agents converging to their designated goals. In this work, we define an exponentially-stabilizing control Lypaunov function [31] as a positive definite function V i (x i ) : R n → R [31] such that there exists a constant ϵ ≥ 0 withEQUATIONwhere£ f V i (x i ) := ∂Vi(xi) ∂xi f (x i )is the Lie derivative of the continuously differentiable function V i (x i ) along dynamics f (x i ), U i the control space of agent A i and ϵ controls the convergence rate.The safety requirement of agent A i is equivalent to that a continuously differentiable function h i (x i ) : R n → R and its derivative w.r.t. time satisfyEQUATIONwhere £ f h i (x i ), £ g h i (x i ) are the Lie derivatives of h i (x i ), and α(•) is a 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] . 
problem formulation: 
 Consider a multi-agent system A in an unknown environment E, i.e., the agents have no information about neither the obstacle positions nor the obstacle shapes. The agents are initialized at positions S = [s 1 , ..., s n ] and tasked towards G = [g 1 , ..., g m ]. Each agent is equipped with a LiDAR scanner that senses its surrounding environment with a number of L lasers and returns distances to the endpoints of these lasers. The goal is to navigate the agents from S to G while avoiding collision with obstacles and other agents. Specifically, let x i be the local state of agent A i that includes its position p i , velocity v i , destination g i and LiDAR readings, and let x (0) i and x d i 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. 1a . Thus, the destination convergence is equivalent to the state convergence lim t→T x (t) i = x d i with T the maximal time step. Let also C safe ⊆ E be the obstacle-free space that can be occupied by the agents. Collision avoidance is equivalent to the safety constraint x (t) i ∈ C safe for t = 1, ..., T . This allows to formulate the problem of safe decentralized multi-agent navigation.Problem 1 (Safe decentralized multi-agent navigation). Given the multi-agent system A with dynamics (1), the initial and target states {x (0) i } nEQUATIONwith δ i ∈ R a slack variable that determines how strictly we enforce the CLF constraint, ξ ∈ R + a regularization parameter often set as one, and U i 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 d l ∈ [0, d max ], with d max the maximum scanning distance. When d l = d max , there is no collision detected w.r.t. the lth laser and no obstacle along that direction within the sensing range -see Fig. 1a . We transform d l to the endpoint location of the laser z l based on the agent position p, and label z l with a binary variable y l ∈ {+1, -1} where +1 indicates a detected obstacle and -1 otherwise.At each time step t, agent A i obtains local LiDAR readingsZ (t) i = {(z (t) i,l , y (t) i,l )} Ll=1 and communicates with its neighbors to collect nearby LiDAR readings {Z (t) j } j∈Ni , where N i is the neighbor set of A i within communication range. By considering the aggregated Z (t) i and {Z (t) j } j∈Ni as the training data, we can learn the safety function h of the environment CBF in (5) . Since LiDAR readings change across time steps as the agent moves, it requires online learning to capture a real-time up-to-date representation of the surrounding environment. As the label y (t) i,l is binary, we propose to leverage SVM because of its fast training for online implementation and high accuracy for performance guarantees. Specifically, we consider the SVM classifier as f SVM (z l ) = sign(⟨ω, ϕ(z l )⟩ F ) with parameters ω [33] , where ϕ(•) is a lifting function that maps the input data to some feature space F and ⟨•⟩ F is some inner product defined in F, and solve the optimization problem as [34] minEQUATIONBy solving (6) in the dual domain to obtain the support vector set N S.V. and its corresponding Lagrangian multipliers β, we can estimate the safety function with the decision function of SVM asEQUATIONwhich measures how safe the position x is w.r.t. the obstacles. By substituting h SVM into (5), we formulate an SVM-based CBF-CLF-QP controller that generates safe actions for each agent A i with online SVM-based CBFs learned from its local LiDAR readings Z (t)i and {Z (t) j } j∈Ni . By selecting a differentiable lifting function ϕ(•) for SVM, the safety function h SVM (•) and the resulting SVM-based CBF constraint are differentiable for the QP controller (5) . Furthermore, an exploration mechanism is incorporated to resolve the potential infeasibility of the QP controller in challenging scenarios during navigation (e.g., non-convex safety regions) -see details in Appendix B. 
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 t. However, it may be computationally expensive if the number of LiDAR readings, i.e., the number of neighboring agents, is large, since the time complexity of SVM training is quadratic w.r.t. the number of training samples. To reduce the online computation, we quantify the importance of neighboring agents by learning edge weights with a GAT and train the SVM only with LiDAR readings received from important neighbors. Specifically, consider the multi-agent system A as a graph G, where the nodes are the agents {A i } n i=1 and the edges are communication links. The graph structure is captured by an adjacent matrix W, where [W] ij ̸ = 0 if there is a link between A i and A j , and [W] ij = 0 otherwise. The value of [W] ij represents how important the neighboring agent A j is w.r.t. the local agent A i . The agent states are modeled by X, which is a matrix whose ith row is the state of A i . We define decentralized attention generators g i (x i , {x j } j∈Ni ) for i = 1, ..., n, which computes edge weights {[W] ij } j∈Ni 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 } n i=1 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 we propose to follow an imitation learning framework to solve this problem. In particular, let x i = {p i , v i , g i , Z i } be the states of A i . For the scenario without any concern of computation, each agent A i aggregates all available states x i and {x j } j∈Ni , trains the SVM to synthesize the environment CBF with Z i and {Z j } j∈Ni , and generates the action u * i with the CBF-CLF-QP controller. We can then consider {u * i } n i=1 as the expert actions of the agents given the states {x i } n i=1 and available communication links. We thus consider the agent states X as 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 a GAT Φ GAT (X, W) to process features and formulate Problem 2 mathematically as an empirical risk minimization problemEQUATION)where M is the number of training samples, ℓ(•, •) 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. I.e., a larger value of [W] ij indicates that more information of the states x j is used to generate the action u i and thus, A j is more important to A i .Thresholding. While the trained GAT mimics an expert action, we need only the computed edge weights W * to identify the neighbors' importance and leverage the latter to reduce the computation of SVM training. Consequently, we define a threshold γ that determines if the LiDAR readings of a neighboring agent A j are used by the local agent A i . When [W] ij ≥ γ, the LiDAR readings of A j are important and will be used to train the SVM; when [W] ij < γ, the LiDAR readings of A j may be redundant, and will hence not be used in the computation. 
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-based 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 l , y l )} L l=1 be the dataset of L LiDAR readings, with z l ∈ Z ⊆ R 2 and y l ∈ Y = {+1, -1}. For the space Y Z , assume there exists an SVM classifier f * SVM that classifies all samples in Z correctly. Define the error margin of f * SVM asEQUATIONwhich measures the minimum distance of data samples to the classification hyperplane and identifies how well f * SVM is w.r.t. Z. For our safety analysis, we need the following assumptions. Assumption 1. The function ϕ of the SVM classifier is infinitely differentiable. Assumption 2. There exists a constant C s.t. for any z ∈ Z, it holds that Pr(∥ϕ(z)∥ ≤ 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-QP controller with the function ϕ satisfying Assumptions 1-2 w.r.t. C. Let C safe be the safety set and ∆t be the time interval between two successive LiDAR scanning, i.e., agents re-scan LiDAR readings every ∆t. For any agent state x randomly distributed in C safe with probability at least 1-α, if the trained SVM f * SVM classifies L LiDAR readings, the agent state within the next time interval ∆t stays in C safe at a large probability 1 -δ, whereEQUATIONTheorem 1 states that the unsafety risk is bounded by factors that are inversely proportional to the number of LiDAR readings L and the square of error margin ϵ(f * SVM ) 2 . In particular, L depends on the LiDAR scanner of the agent and ϵ(f * SVM ) is determined by the performance of the SVM classifier. When L and ϵ(f * SVM ) 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-based CBF method with provable safety guarantees in a multi-agent setting. 1 
experiments: 
 First, we provide a proof-of-concept for the proposed OE-CLBF, to show the effectiveness of SVMbased CBF-CLF-QP controller and attention-based computation reduction, in an 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 not 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 8m×6m. 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 0.1m 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 is 50. The maximal time step is 1000 and the time interval is 0.1s. For convenience of corroborating the relationship between the edge weights computed by GAT and the importance of neighboring agents, we assume a 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 threshold γ = 0.5. Our method completes all navigation tasks, and the removed LiDAR readings by attention-based 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 is close to destination such that its navigation task is 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 are complementary and useful for the local agent. Fig. 2d shows the computation time of SVM training with different thresholds γ. For γ = 0, it trains the SVM with LiDAR readings of all neighbors and requires the most computation, while for γ = 1, it trains the SVM with only local LiDAR readings and requires the least computation. An appropriate selection of γ (e.g., 0.5) saves almost half of the computation and maintains a good performance. Performance evaluation. We evaluate our method for a large system with 8 agents in an environment 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-QP controller and works in unknown environments [17, 19] ; (ii) CBF-CLF-QP 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 requires environment 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 approximate 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 to total agents, where success represents goal reaching without collision, the second is a stringent 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.Table 1 shows the results. The proposed OE-CLBF consistently outperforms the baselines in all metrics, without requiring any knowledge of the environment. Neural CLBF performs worst although it also does not need the environment knowledge. This can be explained by the fact that offline supervised 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 practical and presented as benchmark values only for reference. CBF-CLF-QP with RRT achieves a comparable success rate to ours, but a 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 a larger SPL and smaller time steps compared to the one with RRT. We attribute this to the fact that it approximates rectangular obstacles with large circles and generates conservative agent behaviors, resulting in infeasible navigation scenarios for the CBF-CLF-QP controller [22] . 
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 neighboring 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 accuracy analysis of the SVM and state invariance of CBFs. We experimentally show that our approach achieves superior performance over baselines and adapts to a 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 encourages agents out of local minima but still does not guarantee global success. Finally, we aim to extend our work with more complex non-linear dynamics such as unicycle models and drone modes.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 our work, "environment" refers to 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 as 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. The majority of prior approaches focus on the setting with known environments (maps) and predefined dynamics to design safety-critical controllers for navigation. Learning-based approaches offer a way to leverage sensing inputs, including LiDAR readings and images, for safe navigation in unknown environments, while existing works mainly focus on offline supervised learning to synthesize 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 hyperparameters 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 a 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-feedback controller for multi-agent navigation in unknown environments. Our method learns the CBF of the surrounding environment with a support vector machine (SVM) in an online manner, enabling deployment in any new environment without prior knowledge. Moreover, we leverage graph attention learning to select important neighbors' states to reduce online computation and provide provable safety guarantees.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 if 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 opposite side of an obstacle [53, 19, 22] . To overcome this challenge, we propose an exploration mechanism inspired by the Expansive Search Tree (EST) [54] and integrate it into our 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., no feasible control satisfies both convergence and safety constraints in (6) . The exploration mode samples a state x sample ∼ P state,dmax from its nearby space with the sampling radius determined by the maximum scanning Apply u i to system (1) 14:Scan the environment to collect LiDAR readings 15: Train SVM with the latest LiDAR readings to update the environment CBF 16: Switch to the convergence mode distance d max of the LiDAR scanner, and generates an action by the QP controller to steer the agent towards the sampled state x sample .As we collect LiDAR readings at each time step and perform online SVM training, each agent estimates the surrounding environment in a real-time manner. For any generated action that violates safety constraints, the previously sampled state will be discarded and a new state will be sampled. After repeating this sampling process for a fixed number of times N explore , we switch back to the convergence mode and navigates the agents towards their destinations. Algorithm 1 summarizes the exploration mechanism integrated in our method.We provide additional details about the proposed method in this section.Graph attention networks (GATs) [32] are a variant of graph neural networks (GNNs) [55, 56, 57] that leverage the attention mechanism to extract task-relevant features from graph data. Different from conventional GNNs, which aggregate neighborhood information with (pre-defined) fixed weights, GATs allow to differentiate neighbors w.r.t. their contributions when aggregating neighborhood information to generate task-relevant features.Specifically, consider a graph G = {V, E} with the node set V = {1, . . . , n} and the edge set E. The graph structure can be captured by a support matrix W with (i, j)th entry w ij = [W] ij ̸ = 0 if node i is connected to node j, i.e., (i, j) ∈ E, or i = j, and [W] ij = 0 otherwise. The graph data can be captured by a graph signal X, which is a matrix whose ith row x i = [X] i contains the feature of node i. GATs are capable of assigning different attention coefficients {[W] ij } j∈Ni to the neighboring nodes {j} j∈Ni 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 a shared self-attention mechanism, enabling to quantify the relevance among graph nodes. Therefore, GATs are suitable candidates to 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 coefficients between neighboring nodes. For the local node i and its neighboring node j, the unnormalized attention coefficient is calculated asEQUATIONwhere H is a learnable weight matrix (i.e., linear transformation) that maps the node features x i and x j to some higher-order features, and a(•) is a shared attention function such as a feedforward neural network. The unnormalized e ij is then passed through a softmax function to get the normalized attention coefficients asEQUATIONwhich makes the sum of neighbors' attention coefficients equal to one for ease of probabilistic interpretation. With the normalized attention coefficients W, each node i generates its task-relevant feature as a weighted sum of neighbors' higher-order featuresEQUATIONwhere σ(•) 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 ′ i = u i that mimics the expert action u * i 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 importance 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. [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 ′ 1 .The proposed method contains two main components: SVM-based CBF-CLF-QP navigation and attention-based computation reduction. The former generates safe actions for the agents to 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.We start the proof by defining the generalization error of the learned SVM classifier f * SVM as the probability risk in classifying any unseen data (z, y), i.e., 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 Z = {(z l , y l )} L l=1 , we can follow Theorem 1 of [33] to bound the probability risk asEQUATIONEQUATIONFor the learned safety function h * SVM from f * SVM , ( 15) is equivalent to that for any position z / ∈ Z, if h * SVM (z) > 0, it holds thatEQUATIONwithEQUATIONwhere C safe is the safety set of the environment. Define the safety set C SVM,safe w.r.t. the learned safety function h * SVM as C SVM,safe = {z|h * SVM (z) > 0 for all z ∈ E}.By substituting this safety function h * SVM into the CBF constraint (3) and the latter into the CBF-CLF-QP controller (6) , we can follow Theorem 3 of [12] to prove that there exists a class K function α(h * SVM ) such that the h * SVM -based safety set C SVM,safe [cf. (18) ] is forward invariant, i.e., the agent will stay in C SVM,safe with generated actions.Since the h * SVM -based safety set C SVM,safe depends on the learned safety function h * SVM , which, in turn, depends on the training data of L LiDAR readings Z, and each agent only re-scans these LiDAR readings every ∆t, we assume C SVM,safe keeps the same in the time interval ∆t. Therefore, we haveEQUATIONfor any time t until the next time interval ∆t.By combining ( 16) and ( 19), we complete the proof that withEQUATIONEQUATIONfor any time t in the next interval ∆t.We conduct additional experiments to further validate methodology and corroborate theory.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 on 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-based safety function approaches zero with the number of training samples, which corroborates our theoretical result in Theorem 1. Moreover, the SVM-based safety function achieves good performance even with a small number of training samples (e.g., 250), which highlights the strong classification capacity of the SVM. The goal of the following experiments is to further validate the effectiveness of the attention mechanism 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 D of the agents are initialized randomly in the environment and the obstacles are distributed between S and D. We generate 200 multi-agent trajectories of 200 time steps with 4 × 10 4 samples to construct the dataset, and leverage the ADAM optimizer with a learning rate 10 -4 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. Fig. 5 plots the training procedure of the GAT over 10 4 epochs. We see that the training loss decreases with the number of epochs and the decreasing rate reduces; ultimately, reaching a stationary solution. The convergent loss is small, which indicates a good performance of the trained GAT for action generation and a 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 in [58] 2 , in addition to the distance-based baseline considered in Section 6. Specifically, we follow the idea of spatial confidence-aware communication in [58] to develop a heuristic method to act as a 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 performs 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 of 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-based baseline obtains the worst performance as it computes attention only based on the distance between two agents without considering their LiDAR reading relevance. Lastly, we remark that any attention computing mechanism can be applied to our SVMbased CBF-CLF-QP framework, to develop extended variants for further performance improvement.The goal of this experiment is to 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 a non-convex safety space and the agent easily 2 The attention learning mechanism in [58] cannot be applied directly to our SVM-based CBF-CLF-QP controller. Specifically, it computes attentions among agents via end-to-end learning for a specific downstream task, where attentions are neural network outputs trained using a well-defined task-specific loss function (e.g. the detection loss based on given ground-truth labels in a supervised manner). However, in our case, it is challenging to define the loss function for training because it is non-trivial to measure how well the generated attention values quantify the neighbors' importance w.r.t. the proposed SVM-based CBF-CLF-QP controller. Therefore, there is no end-to-end loss function we can use and [58] can not be applied directly in our setting. gets stuck in a 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 A 1 out of the local dilemma by searching over its nearby space. The method without exploration mechanism fails the navigation task of agent A 1 in Fig. 6b , because it can only generate actions that stay in the local safety set.The goal of the following experiments is to 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 a lower threshold allows for more communication among agents, thereby providing each agent with more LiDAR readings from its neighbors, which in turn leads to more accurate CBF estimates with the SVM and improves the navigation performance. Second, we evaluate our method without the exploration mechanism and present the results in Table 6 . The SVM-based QP controller performs worse without the exploration mechanism in all three metrics. 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. The goal of the following experiments is to study the robustness of the proposed method to realworld deployment effects, i.e., 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 a reasonable update frequency for practical systems with LiDAR scanners [59, 60] . Table 7 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) as expected. This is because a low frequency leads to a delay in LiDAR reading updates and the CBF constraint learned by the 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. Second, we evaluate the proposed method with different levels of random noise on LiDAR readings of the agents, where the imposed noise on each axis (i.e., x-axis and y-axis) is sampled randomly from the interval [0, β] and β 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 of 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 to alleviate the noise on LiDAR readings [63, 64] . show more examples of agents' trajectories generated by our method, for different navigation 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 in 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. The probability bound can be further reduced by leveraging improved accuracy analysis of SVM[36,37]. 
 
 Appendix:  


Decision: 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.

Reviews: review: title: title: Review of CoRL submission 306
paper_summary: paper_summary: 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.
main_review: main_review: The motivation for multi-agent collision avoidance in an unknown environment is sound and clear. The paper is well-written and easy to follow. I like the idea of incorporating SVM into CBF-CLF-QP, which is insightful and SVM-based CBF can be updated in an online manner. The theoretical guarantee is sound. Here are some weaknesses.

- I wonder if the SVM-based CBF is differential when solving QP problem (6) as the gradient of Eq (8) wrt $x$ is needed for the Lie derivative. How to connect LiDAR readings $z$ with state $x$?

- The infeasibility of QP is resolved by exploration, which is an empirical solution. Is there any theoretical perspective regarding the infeasibility of SVM-based QP?

- Although Thm 1 is sound, it is unknown how tight the bounds are. It seems that the convergence rate wrt $L$ is $\mathcal{O}(\frac{\log L}{L})$ and the convergence rate wrt $\epsilon$ is $\mathcal{O}(\frac{\log \epsilon}{\epsilon^2})$, which are only asymptotic and not very tight. Is there any tighter bound to achieve exponential convergence? Also, since the probabilistic guarantee is not sound, can the tightness be verified through Monte Carlo sampling in the experiment?

- For the experiment, the distance-based attention is too naive and may not be convincing. It is expected to compare the proposed method with other baselines from the literature. Also, a quantitative comparison is expected besides qualitative comparison in Figure 2. In Figure 2, it seems that the proposed is unnormalized but the distance-based attention baseline is somehow normalized, so it needs more clarification to justify the results. Time comparison with the baseline should be reported in Figure 2d as well.

- More ablation study over the proposed method is needed, e.g. to show the effectiveness of attention, exploration mechanism in Alg 1.

- Type on line 164: there is no reference to Fig. 3a.
questions: questions: See weakness.
limitations: limitations: 3
review_summary: review_summary: I would be happy to increase my rating if the theory details are clarified and more experiments are conducted as I mentioned in weakness.
title: title: More clarity needed
paper_summary: paper_summary: This paper proposes an Online Exploration-based Control Lyapunov Barrier Function (OE-CLBF) controller for safe decentralized multi-agent navigation in unknown environments.
main_review: main_review: While the work presents some interesting ideas, there are several issues with clarity, technical details, and practical applicability that need to be addressed.

Major concerns:

1. The related work discussion lacks sufficient depth and organization. A comparison table categorizing prior approaches (e.g. known vs unknown map, known vs unknown dynamics, online vs offline) would help contextualize this work.

2. The definition of "unknown environment" needs clarification. Only the map layout seems unknown, while agent dynamics are known and communication is allowed. This is a much weaker "unknown environment" setting than typically referred to.

3. The complexity of agent dynamics is not adequately addressed. More complex dynamics can significantly complicate CBF learning.

4. Many mathematical symbols are introduced without proper explanation (e.g. inf in Eq. 2, $\delta$ in Eq. 6). The notation needs to be more carefully organized.

5. The key insights and advantages of the approach over existing methods should be more clearly articulated, beyond just stating "provable guarantees". For example, Theorem 1 lacks clarity, with undefined terms ($\kappa$) and insufficient discussion of parameters like $C$, neither theoretically nor empirically. In practice, $C$ can be extremely large which makes the conclusion meaningless. 


Practical concerns:

1. Compressing LiDAR data to binary values (-1, 1) discards valuable depth information. The impact of this simplification is not justified.

2. The real-time feasibility and update frequency of the algorithm are not discussed in experiment, which is crucial for collision avoidance. Low frequency may cause still cause collision because the agent cannot respond in real-time. 

3. The graph attention component requires expert demonstrations, it is unclear how to get this data in advance.

4. How robust is your approach to sensor noise, particularly for LiDAR inputs? Given that real LiDAR sensors typically have some level of noise, and this is a major challenge when deploying to real robots, can you provide evidence or analysis demonstrating that your method can handle noisy input data? Additionally, since no real robot experiments were presented, what assurances can you offer that this approach is viable for real-world deployment?

It is recommended to provide a demo video to better illustrate the approach.
questions: questions: - 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.

- 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.

- 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?
limitations: limitations: 2
review_summary: review_summary: 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.
title: title: Review of Provably safe online multi-agent navigation in unknown environments
paper_summary: paper_summary: 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.
main_review: main_review: **Quality and Clarity**

The quality of the paper is very high and its ideas are clearly well written. I can not verify all theoretical contributions but the 
math was sound as far as I followed it.

**Originality**

The work contributes theoretical and framework advances by incorporating SVMs and GATs.
The work seems to be original and thorough work of the authors.

**Significance**

The work has medium significance as it shows how to use GATs to reduce computational time, can be used as a safe component in larger framework or could be improved upon on the theoretical side. However, none of these seem to be large advances.

**Strengths**
Good Robotic Experiments are done with a multitude of provided scenarios. Testing against Baselines was done and fair comparisons to state of the art methods are established. 
The theoretical advances seem to be well done and contribute to the scientific literature.
The quality of the writing is throughout the paper high and its main ideas are clearly stated and experiments covered all laid out claims in the introduction.

**Weaknesses**
None came to mind reading the paper
questions: questions: I have no questions to the authors regarding submission.
limitations: limitations: 3
review_summary: review_summary: The paper seems to be done with the necessary due dilligence done and was a joy to read.