{'fraction_non_alphanumeric': 0.041719062060803315, 'fraction_numerical': 0.010429765515200829, 'mean_word_length': 4.48013781921362, 'pattern_counts': {'":': 0, '<': 1, '<?xml version=': 0, '>': 9, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 2, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 10, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
Multi-Robot Collision Avoidance under Uncertainty with Probabilistic Safety Barrier Certificates

Collision avoidance for multi-robot systems is a difficult challenge under uncertainty, non-determinism, and lack of complete information. This paper aims to propose a collision avoidance framework that accounts for both measurement uncertainty and bounded motion uncertainty. In particular, we propose Probabilistic Safety Barrier Certificates (PrSBC) using Control Barrier Functions to define the space of possible control actions that are probabilistically safe. The framework entails minimally modifying an existing unconstrained controller to determine a safe controller via a quadratic program constrained to the chance-constrained safety set. The key advantage of the approach is that no assumptions about the form of uncertainty are required other than finite support, also enabling worst-case guarantees. We demonstrate effectiveness of the approach through experiments on a realistic simulation environment.


I. INTRODUCTION
Safe control and planning is one of the most important task that needs to be addressed in the realm of multi-robot systems. For example, consider the problem of building an automatic collision avoidance system (ACAS) for aerial robots that would scale up as the autonomous aerial traffic increases. Such a system needs to be robust to various realworld factors that include uncertainty, non-determinism and approximations made in the formulation of the system. In many scenarios, uncertainty in the system arises from various estimation or prediction procedures in real-world that rely on sensory information being collected in real-time. For example, information from sensors such as radars, LIDARS, cameras might be used to detect other robots and obstacles in the vicinity. Similarly, sensors such as an on-board GPS, Inertial Measurement Unit (IMU) etc. could be used to estimate the robots state with respect to the environment. Such estimations naturally introduce uncertainty that needs to be factored into the safety considerations.
Non-determinism often arises from our in-ability to model various exogenous variables that are part of our operating environment. For example, it is fairly difficult to model phenomena such as wind gusts and effects of turbulence near complex topologies that an aerial robot might need to fly. Ability to pro-actively deal with such surprises is a fundamental requirement in guaranteeing safety.
Another important consideration is robustness against approximations that might have been made in the problem formulation. For instance, any equation characterizing the dynamics of the system is an approximation. Similarly, our 1 The Robotics Institute, School of Computer Science, Carnegie Mellon University, Pittsburgh, PA 15213, USA. Email: wenhao@cs.cmu.edu. 2 Microsoft Corporation, Redmond, WA 98033, USA. Email: akapoor@microsoft.com. * Work done while interning at Microsoft Corporation, Redmond implementation on a digital device introduces discretization, both in the mathematical entities being computed as well as for time. Thus, our safety fabric needs to be able to factor deviations from such modeling assumptions.
While many prior approaches have attempted to address these different aspects of the problem, a complete solution addressing all the above aspects has been elusive. Many methods that attempt to address the measurement uncertainty often make restrictive assumptions, such as Gaussianity [1]- [5] and/or simple dynamics model of the robots [1], [3], [4], [6]. Approaches that consider bounded localization or control disturbance using conservative bounding volumes [7]- [10] often overestimate the probability of collisions. Also popular among methods that do distributed collision avoidance is the simplistic assumption of constant velocity [2]. This paper proposes a novel framework that provides collision-free guarantees for crowded multi-robot team operating in a realistic environment. Akin to real-world we consider scenarios with both the measurement uncertainty as well as incomplete information about the dynamics. At the heart of the method is the idea of probabilistic safety barrier certificates (PrSBC) that minimally modifies the existing controllers in real-time to formally satisfy collisionavoidance chance-constraints. Our work is most closely related to the work on safety barrier certificates [11] using permissive control barrier functions (CBF) [12], [13]. While the prior work focused on deterministic settings, our goal here is to provide a safety envelope around an existing controller that accounts for uncertainties and non-determinism.
There are several advantages of the proposed framework. First, in contrast of other probabilistic collision avoidance approaches that directly constrain the inter-robot distance [2], [3], [6], the proposed method produces a more permissive set for the controllers with a tighter bound. Second, the framework naturally inherits the forward invariance from CBF, e.g. robots staying in the collision-free set at all time, and thus enabling us to prove guarantees throughout the continuous time scale. Finally, it is natural to apply the framework for both centralized and decentralized settings.
The key underlying assumption in our framework is that the uncertainties arising due to sensor measurements, incomplete dynamics and other exogenous variables have finite support. This is a reasonable assumption for many of the multi-robot scenarios. For example, we can safely assume that true positions of robots, or the amount of wind gusts etc. are bounded within certain sensor specifications or physical parameters respectively. Similarly, sophisticated dynamic models can also be simplified as a single integrator dynamics with bounded, uniformly distributed noise [14]. We use the task similar to automatic collision avoidance system for aerial robots as a motivating application. Our experiments explore the proposed computation framework in both centralized and decentralized settings, which can handle both the uncertainties as well as environmental disturbances while continuously guaranteeing safety. In summary, the core contributions of this paper are as follows: • A novel safety framework with Probabilistic Safety Barrier Certificates ensuring provable forward invariance under uncertainties with bounded support. • Formal proof of existence of PrSBC in a closed form.
• Experimental results on the task similar to automatic collision avoidance for aerial robots that demonstrate efficiency, scalability and distributed computation.

A. Robot and obstacle model
Consider a team of N robots moving in a shared workspace. Each robot i ∈ I = {1, . . . , N } is centered at the position x i ∈ X i ⊂ R d and enclosed with a uniform safety radius R i ∈ R. The stochastic control affine dynamicṡ x i ∈ R d and the noisy observationx i ∈ R d of each robot i at each time-point are described as followṡ where u i ∈ U i denotes the control input. w i , v i ∈ R d are the process noise and the measurement noise respectively and considered as continuous independent random variables with finite support. A uniform distribution is a natural choice for these noise processes, however, most of our analysis does not require the exact form except that the support is finite. In order to account for any motion uncertainty and possible non-linearity of the dynamic model, similar to [14] we assume the robot dynamics model f i : X i × U i → R d is uniformly continuous, bounded, and Lipschitz continuous for any control input u i ∈ U i ⊂ R d . Thus, we can rewrite the robot dynamics to beẋ i = u i + w i , where w i accounts for both the disturbance and model non-linearity. In this paper, we assume that w i , v i only have a finite support. This finite support can vary at each time-point and come from a state estimator and other physical parameters of the system. Obstacle Model: Similar to the robots, other static or moving obstacles k ∈ O = {1, . . . , K} are also modeled as a rigid sphere located at x k ∈ R d with the safety radius R k ∈ R. Again, the measurement via sensor is modeled asx k = x k + v k ∈ R d with bounded noise v k ∼ U (−∆v k , ∆v k ). We assume the obstacle' velocity can also be detected asû k within a bounded noise aṡ The finite supports of v k , w k are assumed to be known by the robots. Extension to complex shapes is straightforward using a point cloud model.

B. Safety sets
Denote the joint robot states as x = {x 1 , . . . , x N } ∈ X ⊂ R d×N and the joint obstacle states as For any pair-wise inter-robot or robot-obstacle collision avoidance between robots i, j ∈ I and obstacles k ∈ O, the following condition define the safety of x.
The condition of ∀i > j ensures each pairwise collision will be considered only once for the robot team. The sets of H s i,j and H s i,k indicate the safety set from which robots i and j, robot i and obstacle k will never collide. For the entire robotic team, the safety set can be composed as follows: C. Chance-constrained collision avoidance for safety As the robots only have access to the noisy measurements on the states of the robots and obstacles, the positions of the robots and obstacles are modeled as random variables with a finite support. The collision avoidance constraints can then be considered in a chance-constrained setting for each robot i. Formally, given the minimum admissible probability of safety σ, σ o ∈ [0, 1] predefined by the user we require that: Note that when σ, σ o are set to 1, the conditions naturally lead to the worst-case collision avoidance with enlarged bounded volume as discussed in section IV. Such worst-case guarantees can lead to a conservative behavior, thus often there are advantages in maintaining a probabilistic safety.

D. Problem Formulation
Assume that each robot has a task-related controller u * i ∈ R d . We consider the chance-constrained collision avoidance as an one-step optimization problem that minimally modifies u * i for each robot i, while satisfying the desired probabilistic safety in (5). Formally we solve the following Quadratic Program (QP) under the safety constraints: Pr where u ∈ U ⊂ R d×N is the space of joint control inputs for all the robots with bounded magnitude (α i , ∀i) Next, we first describe Safety Barrier Certificates (SBC) [11]. Section IV then presents our method of Probabilistic Safety Barrier Certificates (PrSBC) that utilizes control barrier functions [13] to remap the probabilistic safety set constraints (5) from the state space X ⊂ R d×N to the control space U ⊂ R d×N .

III. BACKGROUND: SAFETY BARRIER CERTIFICATES
Recent advances in permissive control barrier functions [11]- [13] enable mechanisms that guarantee forward invariance of desired safety sets for robots, e.g. robots staying collision-free at all times by constraining the controllers. Here we first describe the formulation of the deterministic safety constraints utilizing the safety barrier certificates [11]. Without loss of generality, we can represent the desired safety set H s in (4) by the function h s (x) from (2) as: First, we summarize the conditions on controllers u ∈ U based on Zeroing Control Barrier Functions (ZCBF) [12] and the Safety Barrier Certificates (SBC) [11] to guarantee forward invariance of safety. Formally, a safety condition as Readers are referred to [11], [12] for details.
Lemma 1. Given the control affine dynamical system in equ, (1) without uncertainties, i.e. w i = 0, ∀i ∈ I and the set H s defined by equ. (10) for the continuously differentiable function h s : R d×N → R. The function h s is a ZCBF and the admissible control space S(x) can be defined as then any Lipschitz continuous controller u ∈ S(x) for the system (1) renders the set H s forward invariant, i.e. robots stay collision-free at all time.
We consider the extended class-K function as κ(h s (x)) = γh s (x), which has been previously proved to preserve the forward invariance of set H s [11] with γ >> 0. Thus the admissible control space induces the following pairwise constraints over the controllers, referred as Safety Barrier Certificates (SBC):.
Here B s (x), B o (x, x o ) define the SBC for the inter-robot and robot-obstacle collision avoidance respectively. Hence, the robots will always stay safe, i.e. satisfying (2) at all time if they are initially collision free and the joint control input One of the useful properties of the constrained control space in (12) is that they induce linear constraints over both the pair-wise control inputs u i and u j (inter-robot) or control input u i (robot-obstacle).

IV. PROBABILISTIC SAFETY BARRIER CERTIFICATES A. Probabilistic Safety Barrier Certificates
Lets consider the stochastic settings, where the states and/or the dynamics of each robot i ∈ I in (1) are latent random variables with a finite support. For example, they can be uniformly distributed around the given measurement x i and the control input u i respectively as We assume initially the robots are collision-free, i.e. E.q. (2) holds true for pairwise random variables x i , x j at t = 0.
We seek a probabilistic version of Lemma 1 that implies the SBC in (12) as a sufficient condition for the forward invariance of H s in (10). Since Lemma 1 is a sufficiency condition, it is straightforward to show that Pr(u i ∈ B s i,j (x)) ≤ Pr(x i ∈ H s i,j ) and Pr(u i ∈ B o i,k (x, x o )) ≤ Pr(x i ∈ H s i,k ). Consequently, we can derive the following probabilistic collision free sufficiency conditions corresponding to equ. (5): Intuitively, these conditions allow us to translate the probabilistic safety constraints from the state-space directly to the the controls, thereby enabling consideration of safety when reasoning about the next control action. Note that the above condition is over the joint control space of multiple robots, hence far less restrictive than other methods that only constrain ego robots motion. Given these reformulated collision-free chance constraints over controllers, we now formally define the Probabilistic Safety Barrier Certificates (PrSBC): Definition 2. Probabilistic Safety Barrier Certificates (PrSBC): Given a confidence level σ ∈ [0, 1], PrSBC determines the admissible control space S σ u guaranteeing the chance-constrained safety condition in equ. (5) and are defined as the intersection of n different half-spaces where n is the total number of pairwise deterministic inter-robot constraints.

B. Theoretical Analysis of PrSBC
Next, we provide theoretical analysis that discusses existence of PrSBC, justifies representation of PrSBC as intersection of half-spaces and show how they can be computed and enable us to compute probabilistic safe controllers. Proof. We start by proving the existence of PrSBC between each pairwise robots i and j. Denote ∆x i,j =x i −x j and , ∆x i,j + (∆v i + ∆v j )). As the random variables w i , w j , x i , x j are all independent with finite support, the distributions T i,j and Q i,j of ∆x i,j and ∆w i,j also have a finite-support.
Given a confidence level σ for Pr(u i ∈ B s i,j (x)) in (13), substituting R ij = R i + R j , ∆x i,j ∈ R d and ∆w i,j ∈ R d enables us to write the safety condition as: Lets define B ij = −2/γ · max ∆w i,j ∆x i,j . Its easy to see that B ij ≤ 2∆w T i,j ∆x i,j /γ due to the finite support of ∆w i,j , ∆x i,j . Thus, we can further reduce equ. (15) using the fact that γ >> 0.
For clarity lets focus on the 2D case (d = 2) when ∆x i,j = [∆x x i,j , ∆x y i,j ] T ∈ R 2 and u i = [u x i , u y i ] T ∈ R 2 . Also lets denote Ω i,j = supp(T i,j ) ⊂ R 2 as the 2D bounded support of the distribution T i,j where ∆x i,j has positive probability. Now consider the following projected 2D space: where It is easy to show that the condition in (16) is equivalent to: To prove the guaranteed existence of PrSBC, we need to show there always exists a solution of pairwise u i − u j such that (18) holds for any given σ ∈ [0, 1]. Recall ∀u ∈ U, As all pairwise robots are assumed to be initially collisionfree with the probabilistic forward invariance as defined in (13), and −B ij 0, we have the probability of bounded 2D support Pr(Ω i,j ⊂ Ω U i,j ) ≥ σ for any given σ. Hence the solution corresponding to a particular pair of u i , u j always exist for equ. (18) to be true under a given σ ∈ [0, 1]. It is straightforward to extend to all pairwise inter-robot collision avoidance constraints under higher dimensional space. This thus concludes the proof.
Computation of PrSBC: Next we describe how to efficiently compute the PrSBC. Given any confidence level σ ∈ [0, 1], the chance constraint (16) can be transformed into a deterministic linear constraint over pairwise controllers u i , u j in the form of (14). While it is computationally intractable to get a closed form solution from (16), we obtain an approximate solution by considering the condition on each individual dimension ∆x l i,j ∈ {∆x 1 i,j , . . . , ∆x d i,j } ∈ R d of ∆x i,j . Formally, the sufficient condition for (16) becomes: where ∆x l i,j ∼ T l i,j (∆x l i,j − (∆v l i + ∆v l j ), ∆x l i,j + (∆v l i + ∆v l j )). To simplify the discussion, we assume σ > 0.5 and denote e l,1 i,j = Φ −1 (σ) and e l,2 i,j = Φ −1 (1 − σ) with Φ −1 (·) as the inverse cumulative distribution function (CDF) of the random variable ∆x l i,j . Assuming a uniform distribution on random variables with the finite support leads to a trapezoid distribution T l i,j . We have σ > 0.5 =⇒ e l,1 i,j > e l,2 i,j . Thus we can re-write the chance constraint from (20) to the following deterministic constraint.
  e l,2 i,j , e l,2 i,j > 0 e l,1 i,j , e l,1 i,j < 0 0, e l,2 i,j ≤ 0 and e l,1 i,j ≥ 0 Note that e l i,j = 0 implies the two robots i and j overlap along the lth dimension, e.g. two drones flying to the same 2D locations but with different altitudes. As it is assumed any pairwise robots are initially collision free and from the forward invariance property discussed above, e l i,j = 0 only happens along at most d − 1 dimensions. To that end, we can formally construct the PrSBC in (14) with the following linear deterministic constraints in closed form.
where e i,j = [e 1 i,j , . . . , e d i,j ] T ∈ R d as defined in (22). This invokes a set of pairwise linear constraints over the robot controllers such that the inter-robot probabilistic collision avoidance in (5) holds true at all time.

Remark 1.
For ∆x i,j with other forms of distribution than uniform but with finite support for the noise models, the only change is the computation of inverse CDF to specify different e l,1 i,j , e l,2 i,j and the rest of the derivations of PrSBC still holds and ensure chance-constrained safety.
PrSBC for Robot-Obstacle Collision Avoidance: Consider the dynamic obstacle model described in Section. II-A and PrSBC for pairwise robots in (23), the PrSBC for robotobstacle collision avoidance with a given confidence level σ o ∈ [0, 1] can be defined as follows.
where the intermediate variables of e i,k , B ik are computed the same way as for inter-robot case. However, here the obstacles are assumed to be non-cooperative with constant velocityû k with bounded random noise. Hence each obstacle introduces one linear constraint over each robot's controller as in (24). (23) can be considered as a generalized SBC when the dynamics model in (1) is deterministic and without any uncertainty. In this case we have e i,j = x i − x j and B ij = 0 in (23), which is the same constraints as SBC in (12).

Remark 2. PrSBC in
Remark 3. (Worst-case Collision Avoidance) When confidence level is σ = 1, the PrSBC in (23) leads to the worst-case driven collision avoidance with e i,j specified by the relative distance between robots fully expanded with the bounded finite support of ∆x i,j .

C. Optimization-based Controllers with Probabilistic Safety
The constrained control space specified by PrSBC in (23) and (24) ensures the forward invariance of probabilistic safety in (13). Hence, we can reformulate the original QP problem in (6) with the PrSBC constraints. The probabilistic safety controller can thus obtained by minimally modifying the original controller u * that the system wished to execute. Formally, we can write this as: As mentioned the PrSBC constraints (26) invoke a set of linear constraints over robot controllers and hence the probabilistic safety controller (25) can be solved efficiently in real-time with guaranteed specified probability of safety.

D. Decentralized Probabilistic Safety Controller
While the controller in (25) is in a centralized setting, we can also derive a decentralized version of the PrSBC and the controllers. The mechanism is similar to Wang et al. [11] which was originally applied to deterministic SBC.
Consider the PrSBC in equ. (23) and denote b ij = e i,j 2 −R 2 ij +B ij . We can then separate the linear pairwise PrSBC constraint between robot i and j in the following: Here p ij , p ji represents the responsibility that each of the two robot takes regarding satisfying this pairwise probabilistic safety constraint. The knowledge of p ij , p ji can be either predefined and assumed known by all robots, in which case each robot does not need to communicate and simply avoid collision in a reciprocal manner, or can be communicated locally between pairwise robots in a more cooperative manner. Note that equ. (27) is a sufficient condition of equ. (23) and hence still guarantees the required probabilistic safety.
With such decentralized constraints, we have the decentralized probabilistic safety controller for each robot i as follows.
This decentralized PrSBC controller does not require centralized optimization process as for (25), but may thus lead to more conservative motion of robots or infeasible solution in extreme cases. In this case the robots will simply decelerate to zero velocities to ensure safety, which may cause the deadlock preventing the robots from achieving the goals. Some deconfliction policies for deterministic SBC can thereby be employed, such as the one suggested in [15]. Readers are referred to [15] for detailed solutions.

V. EXPERIMENTAL EVALUATION AND RESULTS
Simulation Example: Fig. 1 demonstrates the first set of simulations performed on a team of N = 6 mobile robots constrained by the unicycle dynamics using our PrSBC from (25) and the comparing deterministic SBC from [11], with both in centralized setting. All of the robots employ the gradient based controller u * i = −K p (x i − x i,goal ) to swap their positions with the robot on the opposite side, e.g. robot 1 with 2, 3 with 4, and 5 with 6 shown in Fig. 1a. Locations indexed in red are the goal positions for the corresponding robots. The robot safety radius is set to be R i = 0.2m and has bounded uniformly distributed localization error denoted by the red error box accounting for the safety radius. At each time step, each robot only has access to the noisy measurement marked by dashed black circle covering each robot. Maximum velocity limit is 0.1m/sec for the robots and robots motion is disturbed by randomly generated bounded noise with magnitude up to 0.07m/sec. The interrobot collision-free confidence level σ set to be 0.9. As the SBC [11] is designed for a deterministic system, here it takes the noisy measurement of the robots directly as the robot states to compose the SBC for collision avoidance controller. We observe from Fig. 1f that collisions occur (robot 1 and 5) due to uncertainty in measured robot states as well as the motion disturbances. While with our PrSBC controller in (25), robots safely navigate through the work space ( Fig. 1d) (but not too conservatively as it still allows interaction between bounding error box shown in Fig. 1b for probabilistic safety). In particular, results in Fig. 1h indicates our PrSBC method successfully ensures the satisfying probabilistic safety (σ = 0.9). This is computed by the minimum ratio between non-overlapping area and the whole area within each robot's bounding error box shown in red. Scenario with Dynamic Obstacles: To account for dynamic obstacles, we add robot 7 to the previous scenario and make robot 6 and 7 serve as the non-cooperating passive moving obstacles. Fig. 2 highlights our observations from this experiment. We assume robots can identify them as obstacles instead of cooperating robots. With the same set-up except for the two obstacles, we demonstrate the performance of our controller based on decentralized PrSBC in (28) and set the inter-robot, robot-obstacle collision-free confidence σ = σ o = 0.8 to encourage more flexible motion. In the decentralized settings, robots are set to assume equal responsibility in collision avoidance, i.e. p ij = p ji = 0.5 in (27) for each robot, and thus no communication is needed between robots. Results in Fig. 3a and 3b indicate the inter-robots and robot-obstacle are collision free and with a satisfying probabilistic safety close to σ = 0.8 (thus not overly conservative). From Fig. 2b it is noted that robot 5 with light blue trajectory took a large detour before reaching the goal position. This is caused by the non-cooperating obstacle robot 6 and 7 in the way, where the PrSBC for obstacles (24) forces the robot 5 to obey the more restrictive constraints to adapt to the momentum in order to guarantee the satisfying probabilistic collision avoidance performance. Quantitative Results: We performed 50 random trials with different number of robots under a required confidence σ = 0.9 to validate the effectiveness of our decentralized PrSBC controller in presence of random measurement and motion noise. Fig. 3a and 3b shows that the robots are always safe and satisfy the probabilistic safety guarantee using PrSBC. Finally, we also carried out experiments in AirSim [16], a near-realistic simulation environment for drones. In particular, we couple our PrSBC controller to the drone controller and perform a complex formation control with 11 drones under probabilistic safety guarantee. During the task, no collisions are observed as (Fig. 4b). Readers are encouraged to look to details of the experiments in the Video attachments.

VI. CONCLUSIONS AND FUTURE WORK
We presented a framework to address collision avoidance for a system of multiple robots in real-world settings. We address the complexities that arise due to uncertainty in perception and incompleteness in modeling the underlying dynamics of the system. The key idea is to induce probabilistic constraints via safety barriers, which are then used to minimally modify an existing controller via a constrained quadratic program. We formally define Probabilisitc Safety Barrier Certificates, that guarantee forward-invariance in time continuously and also can be decomposed so as to enable de-centralized computation of the safe controllers. Future work entails extensions to model-free controllers trained via Reinforcement Learning and implementation to solve realworld tasks, such as Automatic Collision Avoidance System for manned and unmanned aircraft.