{'fraction_non_alphanumeric': 0.039486317810849735, 'fraction_numerical': 0.014222275564090255, 'mean_word_length': 4.200343267280387, 'pattern_counts': {'":': 0, '<': 2, '<?xml version=': 0, '>': 6, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 7, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
Composition of Safety Constraints For Fixed-Wing Collision Avoidance Amidst Limited Communications

This paper considers how to ensure that a system of fixed wing Unmanned Aerial Vehicles (UAVs) can avoid collisions. To do so we develop a novel method for creating a barrier function, which is similar to a Lyapunov function and can be used to ensure that a system can stay safe for all future times. After introducing the general approach, it is shown how to ensure that collision avoidance for two vehicles can be guaranteed for all future times. The construction is then extended to the case of arbitrarily many vehicles by addressing how to satisfy multiple safety objectives simultaneously. We do this while ensuring output actuator commands are within specified limits. Because this formulation requires communication of control values and may therefore reduce throughput of other important messages, we then show how to reformulate the solution without this significant communication overhead while still ensuring safety is maintained and actuator limits are respected. We validate the theoretical developments of this paper in the simulator SCRIMMAGE with a simulation of 20 UAVs that maintain safe distances from each other even though their nominal paths would otherwise cause a collision.

conservative behaviors, they demonstrate in simulation that the decentralized algorithm continues to allow vehicles to reach their target configuration while avoiding collisions for as many as 70 vehicles. Reactive methods are useful because they can often be calculated online while evasive maneuvers benefit from a lookahead into the future. In this paper we leverage the merits of both approaches within the framework of control barrier functions.
Motivated by the importance of formal guarantees of collision avoidance that are computationally feasible and minimally invasive we discuss in this paper how to apply barrier functions (e.g., [22], [23]) to the UAV collision avoidance problem, where the system is subject to actuator constraints, nonlinear dynamics, and nonlinear safety constraints. Barrier functions are similar to Lyapunov functions and allow for guarantees that a system will stay safe (i.e., vehicles will maintain safe distances from each other) for all future times. Further, under some assumptions detailed in Section II, a Quadratic Program (QP) can be used to calculate a safe control input implied by a barrier function so that the calculation can be done online [23]. Given such safety guarantees, barrier functions have been applied to a set of problems including collision avoidance for autonomous agents ( [24,25]), bipedal robots ( [26,27]), adaptive cruise control and lane following ( [23,[28][29][30]), and in mobile communication networks [31].
However, barrier functions rely on being able to find a function for safety set invariance to be guaranteed. For systems like a fixed wing UAV with actuator constraints, nonlinear dynamics, and nonlinear safety constraints, generating such a function can be difficult. In this respect they are similar to Lyapunov functions. They provide guarantees when a system designer can find appropriate functions but they may be difficult to construct.
Nevertheless, there are a variety of approaches to finding a barrier function given a system and safety constraints.
One approach discussed for instance in ( [22,28,32,33]), uses a sum of squares decomposition [34]. In this approach an initially conservative estimate for a barrier function is found and the associated safe set is iteratively enlarged.
Iterative approaches have also been developed when the system has relative degree greater than one. The conditions for calculating a safe control input for higher order systems are given in [35]. In [27], a backstepping approach is developed that ensures a control barrier function can be constructed and a similar approach is discussed in [36]. The approach discussed in this paper is most similar to [37] where a barrier function is formulated by calculating the distance to a backup set after applying a backup controller. In this paper we develop an alternative approach that does not require the specification of a backup set.
System-specific arguments have also been applied to the development of a barrier function. For instance, geometric insights are exploited in [26], where the authors develop a barrier function for precise foot placement by ensuring that the foot is within the intersection of two circles. Similarly, in [24,25], the authors develop a barrier function that ensures a circle and ellipsoid, respectively, around each robot will not overlap in order to ensure there will be no collisions for double integrator and quadrotor robots, respectively. Barrier functions have also been developed for unicycle dynamics in [30], where the dynamics are simplified by considering a point slightly in front of the vehicle.
Previous work on barrier functions has shown how, given the current state, a safe control input can be selected to ensure the system is safe for all times. In this paper, we also ensure system safety but do so by integrating the dynamics into the future using a known evasive maneuver that is always available to keep the system safe. In this respect the system is more predictable since it is known that a particular control input will be safe. Further, we ensure that actuator limits are respected which is a significant constraint in the case of UAVs where the system has non-zero minimum velocity.
Aside from ensuring a barrier function constraint can be satisfied given actuator limitations, UAV collision avoidance also motivates the consideration of multiple safety constraints that must be satisfied at all times. In particular, because collision avoidance can be viewed as a constraint for each pairwise combination of vehicles [31,38], we briefly review how barrier functions have been applied to systems with multiple constraints. A contract-based approach is presented in [28]. A sum of squares decomposition is presented in [33] where additional safety constraints map to additional constraints in the optimization problem. In [36], necessary and sufficient conditions are given for the existence of a control input that satisfies multiple barrier function constraints. The approach generalizes to high order and time-varying systems but requires that actuator constraints be unbounded. Barrier function composition has also been addressed in [28,31,38]. In [28], the authors partition the state space into regions for which a single barrier function is active in each component of the partition. In [31] and [38] non-smooth barrier functions are discussed, where the result allows for combining barrier functions using boolean primitives. One drawback of the boolean composition approaches is that it is not guaranteed that the composition of barrier functions will result in a barrier function.
The high level contribution of the paper is a method for constructing a barrier function given a safety constraint and system dynamics. In particular, after a safety engineer specifies an evasive maneuver we then show how to construct a barrier function. This paper makes the following technical contributions. First, it generalizes a method discussed in [24,25] for constructing a barrier function that can be used to make safety guarantees for a system. Second, it examines how to ensure that multiple safety constraints can be satisfied simultaneously when using this constructive method. Third, it presents an algorithm for ensuring safety in the context of multi-agent systems that does not require communication of low level actuator commands. Fourth, it shows how to apply the above theory to a scenario involving fixed wing UAVs where vehicles must ensure minimum separation distances are maintained at all times. This paper expands on the conference version [39] which did not consider multiple constraints and did not consider limited communications.
Finally, this paper expands on the simulation study presented in [39] by considering a scenario with 20 vehicles to demonstrate that all pairwise distances between vehicles can be kept above a minimum safety distance throughout a scenario.
This paper is organized as follows. Section II discusses background information for barrier functions. Section III discusses a general method for constructing a barrier function and shows how to apply it to fixed wing collision avoidance.
Section IV generalizes the results of Section III by showing how to satisfy multiple constraints simultaneously. Section V relaxes the amount of information required to share between vehicles while still guaranteeing safety. Section VI presents a simulation verification of the approach. Section VII concludes.

II. BARRIER FUNCTIONS BACKGROUND
We summarize the necessary background for barrier functions here. See [23] for further discussion. Consider a control affine system where and are locally Lipschitz functions, ∈ R , ∈ ⊂ R , and solutions are forward complete, meaning the system has a unique solution for all time ≥ 0 given a starting condition (0).
We expand this formulation to a set of vehicles by considering each vehicle's state and dynamics = ( ) + ( ) where ∈ R , ∈ ⊆ R and ∈ {1, . . . , }. The overall state for the system is described by where = 1 + · · · + . In this case, (1) can be represented as We model the state and control input to the single vehicle by = , , , and = , respectively. Further, we assume in this paper that the vehicles experience small bank and pitch angles so that single vehicle dynamics can be approximated by where the sets of bounded control inputs are ∈ [ , ] with > 0, | | ≤ , | | ≤ . Similar approaches to modeling fixed wing aircraft can be found in [6, 8-10, 20, 21]. We also assume that each vehicle can sense the state of every other vehicle.
Suppose the set of desired configurations is described by the superlevel set of an output function ℎ : R → R defined on an open set D ⊆ R . The superlevel set of ℎ is then called the safe set and is defined as The objective is now to establish the condition under which the state system belongs to C for all times.
In the above definition ℎ( ) = ℎ ( ) ( ) and ℎ( ) = ℎ ( ) ( ) denote the Lie derivatives. From Definition 1, it follows that the admissible control space is defined as Theorem 1. [23] Given a set C ⊂ R defined in (3) for a continuously differentiable function ℎ, if ℎ is a ZCBF on D, then any Lipschitz continuous controller : D → such that ( ) ∈ ( ) will render the set C forward invariant.
In [23] it is also shown how to calculate ( ) ∈ ( ) using a Quadratic Program (QP) to support fast, online calculations. In particular, assume there is some nominal control inputˆ∈ R available that is designed to achieve some performance goal (e.g., path-following) that has not necessarily been designed to satisfy safety constraints. Additionally, we assume can be expressed as the set of all satisfying the linear inequality ≥ . A safe control input can then be calculated using the following Quadratic Program (QP) * = min Note that by property (4), when ℎ is a ZCBF, (6) is guaranteed to be feasible when ∈ D.

III. BARRIER FUNCTION CONSTRUCTION
In general, in order to apply the barrier function framework discussed in the previous section, one needs to define an appropriate barrier function ℎ( ) representative of the collision avoidance constraints the UAVs must satisfy. To this end, as shown in the following example, the design of a suitable barrier function for fixed wing vehicles is not trivial.

A. Motivating Example
In this section we discuss some difficulties with applying barrier functions to the fixed-wing collision avoidance problem via a concrete example. Consider a candidate ZCBF, ℎ, that encodes a collision avoidance safety constraint in a system of two vehicles with state = is the squared distance between vehicles 1 and 2 and is a positive minimum safety distance. To show why ℎ defined in (7) is not a ZCBF, we present an example where, even though the configuration of the aircraft is safe since ∈ C, ℎ( ) does not satisfy constraint (4). Let 1 = − /2 0 0 and 2 = /2 0 − for some ≥ 0.
First, we note that for = Since > 0 and > 0, if the two vehicles' initial positions satisfy 0 ≤ < 2 / we observe that the quantity above does not satisfy constraint (4), i.e., sup ∈ [ ℎ( ) + ℎ( ) + (ℎ( ))] < 0. Therefore, we conclude that ℎ( ) defined in (7) is not a ZCBF. The problem with this candidate ZCBF is that it does not account for the fact that by the time the vehicles are close to colliding, it may be too late to avoid each other due to the limited turning radius and positive minimum velocity.

B. Constructing a Barrier Function via Evading Maneuvers
In order to overcome the difficulties demonstrated in the example of Section III.A, we introduce a method to systematically construct a ZCBF from a safety constraint. Let : D → R be a safety function that represents the safety objective we want to satisfy at all times so that ( ) ≥ 0 indicates that the system is safe. In the example from Section III.A for vehicles and , Second, let : D → be a nominal evading maneuver. Section III.C discusses specific examples of for the UAV collision avoidance problem. For now, assuming has been selected, let be a candidate ZCBF whereˆand ˆare given bŷ For ease of notation, we will omit the time dependencies whenever the time is clear from the context. We assume in this paper that the solution (10) is well defined and contained in D for all ≥ 0 so that (ˆ( )) is well defined. This choice of a candidate ZCBF ℎ is motivated by the fact that in (9), ℎ measures how close the state will get to the boundary of the safe set assuming is used as the control input for all future time.
In Section III.A we saw that we could not use the Euclidean distance for a ZCBF because when a candidate ZCBF ℎ is defined as in (7), ( ) could be empty for some ∈ D. In other words, although ∈ D there was no control input available to keep the system safe. With ℎ defined in (9), this problem is alleviated.

Theorem 2. Given a dynamical system (1) and a set C ⊂ D defined in (3) for a continuously differentiable ℎ defined in (9) with a safety function and locally Lipschitz evading maneuver , ℎ satisfies (4) for all ∈ C. If in addition, ℎ( ) is non-zero for all ∈ C and maps to values in the interior of , then ℎ is a ZCBF on an open set
Proof. We start by assuming ∈ C and show that ℎ satisfies (4). Because ∈ C, ℎ( ) ≥ 0 so (ℎ( )) ≥ 0. Further, note that ℎ( ) + ℎ( ) ( ) is the derivative along the trajectory ofˆ. In other words, Consider the term inside the parenthesis in (12), namely and notice that it is the subtraction of an infimum of the same function evaluated on two different intervals. Further, note that the first interval is a subset of the second interval since approaches 0 from above. Thus, the term inside the parenthesis on the right hand side of (12) is non-negative so ℎ( ) + ℎ( ) ( ) ≥ 0. We can then conclude that Now assume that ℎ( ) is non-zero for some ∈ C and maps to values in the interior of . We will show that there is an open set D that is a strict superset of C for which (4) holds. Let ∈ C be such that ℎ( ) is non-zero and ( , ) be a ball of radius > 0 such that for all ∈ ( , ) \ C, ℎ( ) is non-zero. Such a ball exists such that ( ) is a non-zero vector in the direction of ℎ( ). Note that such a vector exists because maps to the interior of .
Also note that ℎ( ) ( ) > 0. Further restrict so that ℎ( ) ( ) + (ℎ( )) ≥ 0 for all ∈ ( ; ) \ C. Note that for similar reasons discussed earlier in the proof, Remark 1. The intuitive reason why ℎ is a ZCBF is that whenever ℎ( ) is non-negative, we have by definition a control input available to keep the system safe. A geometric view is presented in Figure 1. Note that is not the output of the Quadratic Program (6). Instead, the role of is to allow ℎ to be evaluated via (9).
Remark 3. We have found an error in Lemma 1 of the conference version of this paper [39] and Theorem 2 of that paper was based on that Lemma. Therefore Theorem 2 of this paper is reformulated so as not to require that Lemma.

C. Deriving a Barrier Function for UAV Collision Avoidance
We now consider how to calculate ℎ defined in (9) for the UAV collision avoidance problem. From Theorem 2 the only restriction on and is that is locally Lipschitz and that ℎ is continuously differentiable so there is some flexibility in choosing and . In this section we discuss two cases where we can choose and so that ℎ can be calculated in closed form. Let the initial state for vehicle ( = 1, 2) be given by For these examples we can calculate ℎ in (9) for arbitrary initial states in closed form. Section IV generalizes the results We emphasize that the specification of an evasive maneuver is necessary to evaluate ℎ in (9). In other words, without a safety engineer specifying there cannot be a barrier function ℎ. However, is never actually directly applied to the actuators. Instead, its role is to specify ℎ so that the final actuator command calculated in (6) can actually be applied to the aircraft. In this section we give two examples where for a given , ℎ can be calculated in closed form even though it is an integration over an infinite horizon. While we provide two examples of an evasive maneuver to calculate a continuously differentiable ℎ from (9) in closed form, we note that it is a system specific derivation and have not identified a general method for finding a for an arbitrary system that allows ℎ to be calculated in closed form.
However, we emphasize that any Lipschitz continuous resulting in an ℎ such that (9) can be calculated in closed form and where ℎ is continuously differentiable can be used to ensure safety via Theorem 2. While for any such the safety characteristics of the system are guaranteed via Theorem 2, the performance characteristics (e.g., deviation from the nominal path) may be different for different evasive maneuvers.

Example 1.
In the first case, let In other words, is defined by the same turn rate for both vehicles but possibly different translational velocities. See Fig. 4a for an example. Define = to be the turn radius of the evasive maneuver when traveling at speed , where the terms are introduced to affect the smoothness of ℎ. See the Appendix for details. Then By expanding the square terms and applying two trigonometric identities, * we get Grouping constant terms and applying phasor addition yields where 1 results from grouping constant terms, while 2 and Θ are the amplitude and phase resulting from the phasor addition so that 1 and 2 are functions of . By convention 1 and 2 are nonnegative with appropriate calculation of Θ. The minimum in (16) then occurs at = ( − Θ + 2 )/ for integers resulting in nonnegative so that Note that for the case where the same reasoning yields ℎ( ) = √ 1 − 2 − for defined in (17). To ensure that the square root is well defined, we must then require that 1 − 2 ≥ 0 which occurs when the vehicles do not get more than 2 from each other along the trajectory defined by (10) using in (13). Since can be chosen to be arbitrarily small, it can be chosen so that so the vehicles are very far outside the safe set before this condition occurs.

Example 2.
For a second case, let be given in (8) and which is quadratic in so the minimum can be calculated in closed form. See the Appendix for an analysis of the differentiability of ℎ in this case.
The evasive maneuvers in (13) and (18) (when 1 = 2 = 0 in (18)) both encode trajectories where the vehicles maintain the same altitude for all times and therefore appear to not be exploiting an important evasive capability of the aircraft, namely the ability to change altitudes. However, this is not actually the case. Although and ℎ (for 1 = 2 = 0) are purely planar maneuvers, they nevertheless can induce behaviors that exploit altitude changes. To see this, note that for ℎ in (16) and (19), which is not equal to zero for 1, 0 ≠ 2, 0 . A similar calculation also holds for ℎ ( ) 2,0 . In other words, ℎ changes as a function of initial altitude. Specifically, this means that the QP can exploit 1 and 2 because the fourth and eighth elements of ℎ( ( )) are non-zero when 1, 0 ≠ 2, 0 , i.e., the QP in (6) can exploit the altitude control input even though and ℎ do not necessarily include an altitude changing term in the evasive maneuver.

D. Simulation of Two Vehicles
We demonstrate the theoretical development of this section in simulation using SCRIMMAGE [40]. SCRIMMAGE is a multi-agent simulator designed to scale to high numbers of vehicles and includes a plugin-interface that makes it easy to experiment with different motion models and controllers without having to change code. This makes it simple to swap out nominal controllers and vary the fidelity of fixed-wing UAVs from the unicycle dynamics in (2)  This setup is selected so that the vehicles are on a collision course. The nominal controller is that described in [41] [42] with a 30 degree bank with a speed of . We note that while the experiments do not consider dynamics or sensor noise, the robustness of barrier functions to noise was previously discussed in [29]. Each vehicle evaluates (6) at each timestep where we use OSQP [43] to evaluate the QP. We investigate the performance of the vehicles when ℎ defined in (9) is constructed from in (13) Figure 2. Note that the resulting trajectory can be different depending on which is used as shown in Figure 2d. Nevertheless, in both cases the vehicles are able to maintain safe distances from each other and satisfy actuator constraints throughout the simulation regardless of which is used to construct a ℎ.
In the second experiment, we examine the effect of altitude control on the evasive behavior of the aircraft. Because (20) predicts that ℎ ( ) , 0 ≠ 0 (for = 1, 2) only when the vehicles are not at the same altitude, we start the vehicles at an altitude of −1 and 1, respectively. This offset is small enough to ensure that the nominal path of the vehicles still involves a collision. As was done in the previous experiment, we set = 0 • and = 2 • degrees when using and ℎ , respectively. In Figure 2 we show the output of 1 , where overriding behavior peaks around 8.2 seconds.
Notice that the actuator output is within the limits of ± . Further, the vehicles maintain safe distances at all times.
This occurs even though the evading maneuver does not explicitly encode altitude changes.

IV. COMPOSITION OF MULTIPLE SAFETY CONSTRAINTS A. Motivating Example
Although the constructive method introduced in (9) can produce a barrier function in the presence of actuator constraints that ensures two vehicles do not collide, the formulation does not extend immediately to collision avoidance for systems with more than two vehicles. To see this, we present a specific example where three UAVs with a collision avoidance safety objective cannot use the results from Section III.B to ensure safety. A plot of this scenario is shown in   We now apply the results of Section III to these constraints and for simplicity, let be approximately 0. For each constraint, define an arbitrarily chosen nominal evading maneuver In other words, 1 encodes an evasive maneuver where all the vehicles turn right while 2 and 3 encode a maneuver where all the vehicles turn left. We note that ℎ ( = 1, . . . , 3) defined in (9) and constructed from and are ZCBFs.
In this example we let = 1, = 2, = 1, and = 0.5 so that the vehicles follow a circular trajectory with radius = 1 when applying and . Assume now that the vehicles have the following initial states . Then ℎ 1 ( ) = ℎ 2 ( ) = ℎ 3 ( ) = 0 and the barrier constraints in (4) for ℎ 1 ( ) and ℎ 2 ( ) Although ℎ 1 and ℎ 2 are ZCBFs, these two constraints cannot be simultaneously satisfied for ∈ [ , ] and | | ≤ . In particular, after substituting the minimum velocity 1 = 2 = 1, the first equation dictates that 1 + 2 ≤ −2 (i.e., vehicles 1 and 2 must turn right). Similarly, the second equation dictates that vehicle 1 and 3 must turn left. The problem with this scenario is that vehicle 1 cannot simultaneously execute both nominal evading maneuvers (i.e., turn both left and right at the same time). To solve this problem, we will make sure that the evasive maneuver applied by a vehicle is the same for every barrier function. A geometric view of the general problem and its solution are shown in Figure 5.

B. Sufficient Conditions for Satisfying Multiple Safety Constraints
In order to solve the issues arising when vehicles have to simultaneously respect multiple constraints, we now extend the use of the constructive technique introduced in (9). In this section we extend the reasoning of [23] to the case of constraints. Consider a nonlinear autonomous system where is locally Lipschitz. Then we have a similar definition to Definition 1 for autonomous systems. the assumption that (0) ∈ C we want to show that ( ) ∈ C for all ≥ 0. Hence, we are interested in the forward invariance of the intersection of all the safe sets, which motivates the following definitions where D ∩ is an open superset of C ∩ and ∈ D ∩ . We can now present a multiple constraint analogue of Theorem 1 by following the same reasoning as [23].

Proposition 1. Given a dynamical system (23) and a set C ∩ defined by (25) for continuously differentiable functions
Proof. The proof is the same as that for Proposition 1 of [23], namely ℎ ( ) = − ( ) ≥ 0 for any such that ℎ ( ) = 0 so the result follows by Nagumo's Theorem [44]. We add the assumption that ℎ ( ) is non-zero for all ∈ C ∩ such that ℎ ( ) = 0 to ensure that the tangent cone in Nagumo's Theorem is non-empty.
Then for autonomous systems with dynamics (1), we have the following corollary of Theorem 1.

C. The Shared Nominal Evading Maneuver Assumption
Suppose there are constraints : D → R ( = 1, . . . , ) that must be greater than or equal to 0 at all times.
Section IV.A showed an example where ∩ could be empty for some ∈ C ∩ . As a result, the assumptions of Corollary 1 could not be satisfied. In order to address the issue discussed in Section IV.A, we introduce an additional constraint on ( = 1, . . . , ) that all ℎ are constructed from the same nominal evading maneuver.
Note, however, that this does not imply that each ℎ must be constructed from the same safety function.
The example in Section IV.A does not satisfy Assumption 1 because 1 ( ) and 2 ( ) defined in (21) are not the same. To enforce that the shared evasive maneuver assumption holds, one option is to change 1 so that for each constraint. Another example where the shared nominal evading maneuver assumption holds is as follows: In this case, ( ) encodes an evasive maneuver where vehicle 1 turns left with a linear velocity of 1, vehicle 2 stays straight with a linear velocity of 1.5, and vehicle 3 turns right with a linear velocity of 2. These three nominal evading maneuvers satisfy the shared evasive maneuver assumption because for all ∈ D ∩ , 1 ( ) To see the purpose of Assumption 1, we first examine the case of a single constraint. In particular, let ℎ be defined in (9) and consider the role of in establishing that ℎ is a ZCBF. From Definition 1, for ℎ to be used for a barrier function, ( ) must be nonempty for all ∈ D. With ℎ defined as in (9), this property is satisfied by ( ) or a perturbation of ( ) for all ∈ D (see Theorem 2). The analogue condition for multiple constraints is that ∩ ( ) is non-empty for all ∈ D ∩ . If each ℎ defined in (9) is a ZCBF and is constructed from then by similar reasoning to Theorem 2, ( ) or a perturbation of ( ) is in ( ) for all ∈ D ∩ . This allows us to state a multiple constraint analogue to Theorem 2.

Theorem 3. Given a dynamical system (1) and a set C ∩ ⊂ D ∩ defined in (25) for continuously differentiable functions
ℎ defined in (27)  Proof. To prove the first statement, note that it was shown in the proof of Theorem 2 that is in ( ) for = 1, . . . , and ∈ C ∩ . To prove the second statement, note that we can use the same method as was used in the proof of Theorem 2 to find a vector ( ) such that ℎ ( ) satisfies (4) for all ∈ ( , ) given ∈ C ∩ . In particular, because We choose ( ) with sufficiently small norm. Using the notation of the proof of Theorem 2, for sufficiently small , the projection of ( ) onto ℎ( ) will be in the direction of ℎ( ) for ∈ ( , ) because ℎ( ) is continuous.
Remark 5. A geometric view of the problem introduced in Section IV.A and its resolution via the shared evading maneuver assumption is shown in Figure 5.

V. CONTROL CALCULATION WITH LIMITED COMMUNICATION
The QP in (32)  be the shared evading maneuver where 1 is the part of that is applied to vehicle 1 and therefore has the same size as 1 . Define 2 similarly for vehicle 2. Similarly decompose in (6c) as = 1 2 and ℎ , ( ) as Further, let in (6c) be block diagonal with block entries 1 and 2 so that ≥ represents the actuator constraint for vehicle for = 1, 2.
Notice that 1 is not a function of 2 and 2 is not a function of 1 . In other words, if we can select 1 and 2 such that 1 ( , 1 ) ≥ 0 and 2 ( , 2 ) ≥ 0 then = 1 2 ∈ ∩ ( ) ∀ ∈ C. For ∈ C ∩ , this can be done by letting 1 = 1 ( ) and 2 = 2 ( ) and noting that this implies For ∉ C ∩ , a pertubation of 1 ( ) and 2 ( ) using a similar method as shown in the proof of Theorem 3 suffices.
In other words, we can find without vehicle 1 needing to knowˆ2 or 2 and similarly for vehicle 2. Each vehicle ( = 1, 2) could then calculate the following QP: * = min Note that ( , ) is linear in .
Finally, the last statement where K ( ) is nonempty for all in an open set that is a superset of C ∩ follows similarly to the proof of Theorem 3.
We now write a QP similar to (32) but without requiring knowledge of other agents' low level control values as follows: * = min . We note that the solution from the centralized QP (32) may be different than the solution from the limited communication QPs (37)  be that the total cost of each vehicle calculating (37) is higher than the centralized calculation (32). In other words, the calculated safe control may not be as close to the nominal control signal in a least squares sense when using (37) as opposed to (32). Nevertheless, in either case of (32) or (37), a solution exists to the corresponding QP such that ∈ ∩ .
Another difference between the limited communication (37)

VI. SIMULATION
In this section we repeat the scenario discussed in Section III.D but consider = 20 vehicles. For the scenario where ℎ is constructed from , we use 0 0 where = 0.9 + 0.1 and = 0.9 .
For the scenario where ℎ is constructed from ℎ , we let = (1 + 0.01 ) 0 0 so that each vehicle uses a different translational velocity as is required to ensure differentiability of ℎ (see Section III.C). Note that this does not violate the shared evading maneuver assumption because = ( 1 ) · · · ( ) . Additionally, we let = 0 and = 25 • in the scenario where ℎ is constructed from and ℎ , respectively. Offsetting the initial orientation 25 • from pointing at the origin is required so that the vehicles can start in the safe set when using ℎ . A video of the resulting behavior is available in [45]. Quantitative results for both scenarios are shown in Figure 6 which shows similar outputs to the results for the two vehicle simulation shown in Figure 2. Small random perturbations, e.g. adding a uniformly sampled angle within ±5 • to the initial heading, does not appear to change qualitative results. We also compare the approach of this paper to a navigation function from [9] in Figure 6. Note that when using a navigation function the vehicles begin the evasive maneuver earlier than when the collision avoidance algorithm is based on a barrier function constructed from . Using a less aggressive function, such as a linear function with a small coefficient instead of a cubic function, may have caused the behavior from the barrier function override to similarly override earlier. A comparison of potential and barrier functions can also be found in [46]. Also note that the pairwise distance between all vehicles are kept above the minimum safety distance while satisfying actuator constraints.

VII. CONCLUSION
In this paper we have examined method for ensuring a system with constrained inputs can be safe for all future times. The main result is a general method for constructing a barrier function given a safety constraint, system dynamics with actuator limits, and an evasive function specified by a safety engineer. We then apply this method to show how collision avoidance for two UAVs can be ensured for all future times. The result is then extended to the case of collision avoidance for arbitrarily many UAVs by considering how to ensure that arbitrarily many safety objectives can be satisfied simultaneously. In the case of arbitrarily many UAVs, network constraints may limit the message throughput so we provide a reformulation of the algorithm that requires less message passing while still ensuring that vehicles will stay = 0, 5 and 6 are both zero on the set 1 ⊆ D where 1,0 = 2,0 or 1,0 = 2,0 + . Although 1 is a zero measure set, we note that for > 0 that 2 is zero on a set 2 ⊂ 1 where 2 is the restriction of 1 to a specific set of positions which we now specify.