{'fraction_non_alphanumeric': 0.03893327575037789, 'fraction_numerical': 0.012394731159576766, 'mean_word_length': 4.307242722897089, 'pattern_counts': {'":': 0, '<': 7, '<?xml version=': 0, '>': 9, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 3, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
Multi-agent systems with CBF-based controllers -- collision avoidance and liveness from instability

Assuring system stability is typically a major control design objective. In this paper, we present a system where instability provides a crucial benefit. We consider multi-agent collision avoidance using Control Barrier Functions (CBF) and study trade-offs between safety and liveness -- the ability to reach a destination without large detours or gridlock. We compare two standard decentralized policies, with only the local (host) control available, to co-optimization policies (PCCA and CCS) where everyone's (virtual) control action is available. The co-optimization policies compute control for everyone even though they lack information about others' intentions. For comparison, we use a Centralized, full information policy as the benchmark. One contribution of this paper is proving feasibility for the Centralized, PCCA, and CCS policies. Monte Carlo simulations show that decentralized, host-only control policies and CCS lack liveness while the PCCA policy performs as well as the Centralized. Next, we explain the observed results by considering two agents negotiating the passing order through an intersection. We show that the structure and stability of the resulting equilibria correlates with the observed propensity to gridlock -- the policies with unstable equilibria avoid gridlocks while those with stable ones do not.


I. INTRODUCTION
With the recent advances in automated driver assist systems, autonomous vehicles, and multi-robotic systems, management of agent-to-agent interactions has received a lot of attention. Each agent must be capable of planning and executing paths in real time while assuring collision-free operation. A challenging situation could arise from mixed operating scenarios such as with multi-brand, multi-robot factories or heterogeneous driving scenarios with fully autonomous, semi autonomous, and human-driven agents/vehicles that both compete and cooperate. This can lead to complex feedback loops that are only partially controllable from each agent's perspective, presenting an opportunity for the rigors of feedback control.
In recent years, Control Barrier Functions (CBF) [1], [2], [18] have shown great promise in providing a computationally efficient method that is both provably safe and able to handle complex scenarios. Similar to Model-Predictive Control (MPC), CBF is a model-based control design method that can be formulated as a quadratic program (QP) and solved online using real-time capable solvers, e.g. [8]. A few noteworthy differences between CBF and MPC include (i) MPC generally relies on a set of linearized dynamic systems to cover the nonlinear model range, whereas CBF deals with the nonlinear (but control affine) model directly, (ii) for nonconvex constraints, MPC requires convexification, sequential convex programming, or mixed integer programming, while CBFs do not see them as such, and (iii) MPC takes advantage of future state prediction whereas CBF does not.
In a controlled environment with all agents having the ability to communicate, a centralized controller -an offboard computer that takes in all agents' inputs (such as their desired acceleration), calculates and relays the optimal action for each agent -may be employed [19]. One contribution of this paper is a proof that the centralized, distance-CBF based QP problem is always feasible.
In less controlled scenarios such as vehicles operating on roadways, or multi-brand robots operating without common communication protocols, a decentralized controller may be necessary. In this case, each agent computes and executes the best control for itself given the information available similar to how we drive vehicles. Several variations of the decentralized CBF policy exist. In particular, the Decentralized Follower (DF) method [4] assumes each agent takes full responsibility for collision avoidance while the Decentralized Reciprocal (DR) method [17] assigns each agent a fraction of responsibility. Robust CBF (RCBF) [11] was used as the basis for the development of the Predictor-Corrector for Collision Avoidance (PCCA) algorithm [16]. We herein present a novel decentralized controller, called Complete Control Set (CCS), that assigns appropriate agent responsibility and guarantees constraint adherence in the two-agent case. The PCCA and CCS are performing "co-optimization" -they compute the best course of action for every agent with local, incomplete information. The advantage is that the corresponding QPs are always feasible. The difference between them is that CCS simply discards local copies of other agent actions, while PCCA compares them to the observed actions -hence the "predictor-corrector" nomenclature -and feeds the difference back as a disturbance.
After introducing each algorithm, we assess feasibility and its effect on online algorithm implementation. We then proceed to compare algorithm metrics on liveness, collisions, and feasibility through a randomized five-agent Monte-Carlo simulation trials for each method (each set up identically). It turns out that the two decentralized algorithms and the CCS exhibit a certain percent of gridlocks as well as generally slower arrival to the destination compared to the Centralized and PCCA policies which showed consistently fast conver-gence with no gridlocks.
As mentioned above, agents operating independently in a shared space create complex feedback loops. We conjectured that the equilibrium structures and their stability play a decisive role in determining propensity to gridlock. Gridlocks for multi-agent systems have been studied before in robotics literature. The results typically deal with decentralized policies (DF, DR) and propose methods to deconflict the agents once a gridlock is detected -see, for example [6], [9], [10], [17] and references therein. Here, we are interested in trying to explain the observed differences between the control policies. We analyze the equilibrium structure in the joint space for a simple problem of two agents negotiating passing order through an intersection or a merge point. The decentralized policies as well as CCS have a stable set of equilibria which explains their propensity to gridlock. In contrast, the Centralized and PCCA policies have unstable equilibria and thus only a set of measure zero that ends up in a gridlock. Moreover, the instability is exponential, resulting in fast movement away from the gridlock point even for trajectories that start close to the stable manifold of the equilibrium set.
The paper is a significant extension of the conference paper [12]. Besides many improvements and clarifications throughout the text and added figures better explaining Monte Carlo results in Section V, the main addition is the equilibrium analysis in Section VI. This section contains an explanation of the observed gridlock propensity linking it with policy dependent stability of multi-agent systems.
The rest of this paper is organized as follows. Section II reviews CBF and RCBF based control. Section III introduces the dynamic model for the agents. Section IV reviews or introduces CBF-based controllers for collision avoidance. The simulations in Section V consider randomized trials of five interacting agents with a stationary obstacle. The equilibrium analysis is provided in Section VI.
Notation: For a differentiable function h(x) and a vector f (x), L f h(x) denotes ∂h ∂x f (x). A continuous function α(·) is of class K if it is strictly increasing and satisfies α(0) = 0. We additionally assume α ∈ K is Lipschitz continuous. A function γ(t, ε) is said to be O(ε) if |γ(t, ε)| ≤ κ|ε| for some κ > 0 and for all sufficiently small ε.

II. ROBUST CONTROL BARRIER FUNCTIONS REVIEWED
In this section, we briefly review the concepts of CBFs -introduced in [18] and later combined with quadratic programs (see, e.g. [1], [2]) -and of RCBFs introduced in [11]. CBFs apply to nonlinear systems affine in the control inputẋ with x ∈ IR n , u ∈ IR m , f (x) and g(x) Lipschitz continuous. RCBFs extend CBFs to systems with a bounded external disturbance w(t) ∈ IR ν , w(t) ≤w > 0, of the forṁ where p(x) is also Lipschitz continuous.
One control objective is to regulate the system to the origin or suppress the disturbance (i.e. achieve input-to-state stability (ISS)) and we assume that there is a known baseline controller u 0 that achieves the objective. The other control objective is to keep the state of the system in an admissible (i.e. safe) set defined by C = {x ∈ IR n : h(x) ≥ 0} where h(x) is a twice continuously differentiable function. Here we combine definitions of CBF and RCBF into one.
Definition 1: (CBF and Robust-CBF) A twice continuously differentiable function h(x) is a CBF for the system (1) if there exists a function α h ∈ K such that The function h(x) is an RCBF for the system (2) if In the CBF case, the definition asks that, when the control over the evolution ofḣ = L f h + L g hu is lost (L g h = 0), the rate of decrease of h to 0 is not faster than α(h). Similarly, for the system with disturbance, the bound on the rate of decrease applies for the worst case disturbancew.
One advantage of CBFs for control affine systems is that they naturally lead to linear constraints on the control input u that could be enforced online. A quadratic program (QP) is set up to enforce the constraint, while staying as close as possible to the baseline (performance) control input u 0 : (R)CBF QP Problem: Find the control u that satisfies if h is a CBF for the system (1); if h is an RCBF for the system (2) with an unknown disturbance; or ) when an estimate/measurement of the disturbance is available.
The available results (e.g. [1], [2], [11]) guarantee that the resulting control is Lipschitz continuous, the barrier constraint F i is satisfied, which implies that h(x(t)) ≥ 0, ∀t and the safe set C is forward invariant. Note that strict ">" is needed in the (R)CBF definition (3) and (4) to guarantee Lipschitz continuity of the control law [11], or, alternatively, L g h(x) = 0, ∀x ∈ C needs to be assumed as in [1].
In the distance-based barrier functions considered in the rest of the paper, the control input does not appear in their first derivative as assumed in the definition of (R)CBF. The inputs appear in the second derivative of h, so we follow the ideas of [15], [20] for dealing with higher relative degree: instead of enforcingḣ + α h (h) ≥ 0, we switch to linear barrier dynamics and enforcë as the QP constraint. The parameters l 0 , l 1 should be selected so that the two roots {−λ 1 , −λ 2 } of the polynomial s 2 +l 1 s+ ). It is a matter of straight-forward calculation to show that, if the barrier constraint (6) holds, the set where −λ l is either of the two eigenvalues, is forward invariant. With C * ⊂ C the original constraint h(x) ≥ 0 will be satisfied and C * → C as λ l → ∞.
For the second-order barrier, the QP constraints that need to be enforced for C * to be forward invariant are in the case of the CBF for the system without disturbance; for an RCBF with unknown disturbance bounded byw; or for an RCBF with known disturbance estimateŵ.

III. HOLONOMIC AGENT MODEL
In the literature, agents are typically modeled either with holonomic double integrators in the X-Y plane or as a nonholonomic "unicycle" or "bicycle" model. For simplicity, here we consider the first option. An agent i is modeled as a disk of radius r 0 with the center motion given by the double integrator in each dimension: The relative motion between any two agents i and j is given byξ where ξ ij = [x i −x j , y i −y j ] T is the center-to-center (vector) displacement between the two agents, v ij = [v xi − v xj , v yi − v yj ] T is their relative velocity, and u i = [u xi , u yi ] T is agent i's control. Our goal is to keep the ξ ij larger than r ≥ 2r 0 (with the distance r strictly greater than 2r 0 we are providing a "radius margin" relying on robustness of barrier functions (see [21]) to push the states out of the inadmissible set). To this end, we define a barrier function with the goal to keep it greater than 0. The advantages of this barrier function over alternative ones used for multi-agent collision avoidance is that (i) we can prove the feasibility of the centralized and a few decentralized QPs and (ii) it allows a radius (barrier) margin because the calculation does not collapse when h(ξ ij ) < 0. A disadvantage is that h has relative degree two from all 4 inputs. Because of this, we apply the approach described in Section II and form a CBF barrier constraint: where a ij = 2v T ij v ij + 2l 1 ξ T ij v ij + l 0 (ξ T ij ξ ij − r 2 ), b ij = 2ξ T ij , and u i and u j are the control actions of the two agents. The function h is a CBF for the system (11) because L g h = 2b ij = 0 unless the two agents completely overlap (that is, are well past the point of collision). As a result, we can always enforce positive invariance of the admissible set C with λ l one of the two eigenvalules, as discussed above. Without loss of generality, we will use l = 1.
As we shall see below, with the centralized controller we can guarantee that the agents do not collide even if there is no barrier margin: r = 2r 0 . In the non-ideal case -for example, discrete-time implementation, the only way a QP could be implemented -some very small barrier function violations appear. Non-centralized controllers might have larger violations because two agents i and j compute u i and u j independently, based on different information available to them. To the extent they don't agree, a difference between the left hand sides of the centralized barrier constraint F c ij ≥ 0, which guarantees collision avoidance, and the actual F a ij ≥ 0 resulting from independent control calculations could appear. On the other hand, the radius margin creates a repelling term equal to 2l 0 (r 2 − r 2 0 ) on the boundary of the actual barrier function we want to enforce, h 0 = ξ ij 2 − 2r 0 , providing a degree of robustness (see [21] for a more general consideration).

IV. CBF-BASED COLLISION AVOIDANCE ALGORITHMS
In the absence of other agents, we assume that each agent has its own preferred control action u 0i (for agent i), computed independently of the collision avoidance algorithm. In this paper, each agent knows its own final destination and uses the Linear Quadratic Regulator (LQR) controller to compute u 0i that is supposed to bring it there. On the other hand, we set up the Centralized controller that controls all the agents, knows everyone's u 0i 's, and uses the barrier constraints between each two agents defined in the previous section. Thus, the Centralized controller could be set up as the solution to the following quadratic program: where a ij and b ij are defined in the previous section (after equation (13)) and N a is the number of agents. The QP solution could be computed by a central node and communicated to the agents, or each agent could solve the QP independently, which still requires communication between them because they need to know each-others' baseline controls u 0j . If this QP problem is feasible, and this is proven below, the control action would satisfy all the barrier constraints (13) and guarantee collision-free operation (see [17]).
Without communication, the base control action u 0j for the target (i.e. other) agents are not available to the host i (the agent doing the computation). In this case, each agent could implement an on-board decentralized controller. One version, included here because it resembles many defensive driving policies considered in literature, is for each agent to accept full responsibility for avoiding all the other agents. Borrowing nomenclature from Game Theory, we refer to this policy as "Decentralized Follower" (DF): Decentralized Follower QP (for agent i): Find the control u i for the agent i that satisfies This formulation is essentially the same as in [4] but a different barrier function is used, as described above. The agent i has only its own actions (x and y accelerations) to avoid all other agents and there are no guarantees that the DF QP is feasible. Even when it is feasible and the agents apply the same defensive algorithm, there are no collision avoidance guarantees. The reason is that each agent knows only its own acceleration u 0i , and may assess it safe to apply. That is, if a ij + b ij u 0i ≥ 0, ∀j, agent i would consider u 0i safe to apply. Similarly, agent j might find that u 0j is safe to apply. However, would actually guarantee collision avoidance. Indeed, our simulations show that, even with only two agents, there could be a collision as seen by overlapping circles in Figure 1.
In the simulation run shown, each agent implemented the (identically tuned) navigation policy described by (15) with their u 0i 's coming from an LQR controller. We note that (i) the collision did not happen during braking (i.e. when the agents are approaching one another), but when they both optimistically assume it is safe to accelerate; (ii) even though the algorithm updates controls every 50ms with new position and velocity information, the collision is not avoided when the actual constraint To improve the DF performance, the "Decentralized Reciprocal" (DR) policy was introduced in [17]: Decentralized Reciprocal QP (for agent i): Find the control u i for the agent i that satisfies The only difference from the DF version is the 1 2 factor multiplying a ij , meaning that each agent assumes half the responsibility for avoiding the collision (we assumed all the agents are the same). The method was shown in [17] to guarantee constraint adherence and, hence, collision avoidance as long as it is feasible and, when it is not, proposed a braking action. Braking, however, works only if all agents, even those with feasible QP, apply it at the same time. To illustrate the issue, we consider two moving agents passing the stationary one in the middle as shown in Figure 2. The DR QP turns out infeasible for the agent in the middle, but, because it was already stationary, the braking applied has no effect. The other two have feasible QPs and keep applying the solutions. This leads to collisions as shown in Figure  2 because the expected half contribution towards avoiding collisions by the agent in the middle has not been met. One possible approach to avoid the problem is for each agent to run a separate DR-QP's for itself and all the other agents and brake when any one of the QPs turns infeasible (no need to know u 0j 's to assess feasibility). This would increase computational footprint, but also raise the issue of when to stop braking: as soon as all QP's become feasible, or only after all agents have stopped. The former might lead to a jerky motion, while the latter would suffer from reduced liveness. In the simulation section, we have allowed the QP solver to resolve the feasibility issue by selecting control with the smallest constraint violation counting on eventual application of the radius margin.
Instead of N a DR-QPs being solved by the host to assess feasibility for all the other agents, one could consider setting up a single QP that includes all the constraints. The problem, of course, is that the host does not know other agents' preferred accelerations, so zeros are used instead of unknown u 0j 's. We refer to this policy as the "Complete Control Set" (CCS): where ρ i is a design parameter used to assure that when the constraint is active for multiple agents, the actual barrier constraint (13) is satisfied. The agent i uses the CCS policy to find the control action for all the agents and implements its own: u i = u * ii + u 0i where u * ii denotes the solution to the QP problem. The CCS QP is guaranteed to be feasible (see Proposition 1 below).
To better understand the ρ i term in front of b ij u 0i , first note that ρ i = 1 would be equivalent to the centralized QP (14) with all u 0j , except j = i, (i.e. all the unknown ones) set to 0 and with a variable change for u ii . While the complete set of constraints guarantees that agents will correctly split the responsibility for a ij , other agents do not know about u 0i so the responsibility could not be split. The multiplier ρ i = 2 works in the case of two agents implementing the CCS policy, when constraint adherence could be established using the closed-form solution from [16]. In the multi-agent case, this is not the case -one could find situations when the constraints will not be satisfied. Still, because it is always feasible and, as it turned out, somewhat more lively than the two decentralized policies, we have included it in the comparison.
An idea to use RCBFs to robustify the CCS policy against the missing information led to the development of the "Predictor-Corrector for Collision Avoidance" (PCCA) method (see [16]): and implement its own: ii . This setup resembles the CCS (17) with all the agent-toagent constraints accounted for, but with no ρ i multiplier applied as in CCS. Instead, the (fictitious) disturbance termŝ w ij have been added to the u ij (i = j). They represent the uncertainty of agent i's computation of agent's j acceleration.
One could put an upper limit on this uncertainty and proceed with RCBF using the worst case disturbance. Instead, the PCCA uses the estimated disturbance as a difference between the control action for agent j (u * ij ) computed by the host (agent i) with the action agent j actually implemented (u j ): Because u * ij requires knowingŵ j and vice versa, an algebraic feedback loop is created. To break this algebraic loop, one could use either the value from the previous sample (the controller solving the QP could only be implemented in discrete time) or a low pass filter.
The paper [16] considered the case of two agents and, with discrete single sample delay, proved that the error in enforcing the constraint is of the order of the sample time ∆T -the smaller the sampling time, the smaller the error. Moreover, [16] showed that, even if one agent is not cooperating, the other agent takes over full responsibility for collision avoidance also producing possible constraint violation of the order of the sample time. In contrast to CCS, we could not find a multi-agent case when the real constraints would not be satisfied (within ∆T accuracy) but the general proof is not available. We also note that PCCA assumes information (measurement) of other agents' acceleration that can generally be obtained by lead filtering velocity measurements/estimates or with the use of an estimator such as the one proposed in [3].
We now show that the Centralized, CCS, and PCCA QP's are feasible. To the best of our knowledge, this is a new result, but specific to the distance-based barrier function. The problem is nontrivial because there is a scenario where we have more active QP constraints than the linearly independent (row) vectors multiplying control inputs. This situation also prevents the standard approach to establishing Lipschitz continuity of optimal programs from being used [14] (note: we are not implying the controller is not Lipschitz continuous).
Proposition 1: The Centralized QP (14), CCS QP (17), and PCCA QP (18) are always feasible in the admissible set . . , N a }, i = j} and the solution in each case is unique.
Proof: Consider the Centralized policy constraint where the last term is obtained by using h ij ≥ −1 λ1ḣ ij (from the definition of C * ) and l 1 − l 0 /λ 1 = λ 1 . From here, we construct a feasible u by selecting one that satisfies which results in F ij ≥ 2 v ij 2 ≥ 0. We proceed by using mathematical induction. For the first two agents, we pick any u 1 and u 2 that satisfy (20) where, in this case, i = 1 and j = 2. For example, we could select u 1 = 0, u 2 = λ 1 v 12 . Proceeding with the induction argument, assume that for the first l − 1 agents we have selected control inputs u 1 , . . . , u l−1 such that the condition (20) holds for all i, j = 1, . . . , l − 1, i = j. Adding the l-th agent we first consider F 1l ≥ 2 v 1l 2 +2ξ T 1l (u 1 −u l +λ 1 v 1l ). Selecting u l = u 1 + λ 1 v 1l makes F 1l ≥ 0 and we need to show that all the other constraints are satisfied. Because v il = v ij + v jl , v ij = −v ji , and (20) holds for i, j = 1, . . . , l − 1, i = j by the induction assumption, for all i = 2, . . . , l − 1 we have Thus, for all i = 1, . . . , l − 1, F il ≥ 2 v il 2 ≥ 0 and the induction argument completes the feasibility part for the centralized QP. Because the optimal program has (strictly convex) quadratic cost and linear (convex) constraints, there is a unique solution.
Feasibility of CCS follows because, by changing the variables, the constraint set takes the same form as that of the centralized controller with only the cost function being different. The same applies for PCCA.
Remark 1: From the proof of Proposition 1 it is clear that we have one extra degree of freedom assuring feasibility even if one agent, say agent 1, is non-responsive, but with its acceleration known to the entity computing the QP. Second, if we introduce a fictitious, stationary agent 1, each agent braking proportional to its velocity u i = −λ 1 v i becomes a feasible action. 1 Note that the proportional braking policy is a sub-optimal option (it leaves F ij ≥ 2 v ij 2 ) proving feasibility, rather than an external action to be applied when the respective QP is not feasible. The above consideration also shows that the deceleration for each agent need not be larger than λ 1 v i , Thus, the QP problem remains feasible even if agent deceleration is limited provided their speed is appropriately limited too.

V. 5-AGENT SIMULATION RESULTS
We now compare the CBF collision-avoidance algorithms reviewed above by Monte-Carlo simulation of five agents maneuvering in an enclosed area. The agents are modeled as disks of radius r 0 = 2 with the center motion given by a double integrator in two dimensions as in (10). A static outer circle of radius R 0 = 11 acts as an additional (soft) barrier constraint to enclose the space containing all five agents. The controller sample time is chosen to be ∆T =50 ms, and the baseline controller u 0i for each agent is computed by LQR with Q = 0.2I 4 and R = I 2 . For computation of the QP constraints (13), we choose l 0 = 6 and l 1 = 5 to satisfy l 2 1 ≥ 4l 0 (i.e. negative real eigenvalues). All the algorithms use this same set of parameters and CCS is implemented with ρ i = 2.
For each simulation trial, each agent is assigned random beginning and end locations somewhere within the outer 1 We note that the fixed (maximal) deceleration policy does not work for the barrier functions and constraints considered in this paper. For example, with ξ ij 2 = r 2 /(1 − ε) (with ε < 1), v i and v j collinear in the same direction, and v ij = −λ 1 (1 − r 2 / ξ ij 2 )ξ ij , F ij constraint would be violated if both agents decelerate with the same constant deceleration.  Figure 3 shows a time snapshot of one of these rans -the agents, their beginning and end locations, as well as their past and future paths are all displayed. To assess the algorithms, a set of metrics was devised to compare liveness, collisions, and feasibility. Liveness is a measure of convergence time; we assess how long it takes for all the agents to reach within 0.1 units from their destinations with the velocity magnitude less than 0.1 units/sec. Each simulation was run for 100 seconds and assessed for convergence. It was found that all non-convergent runs at 100 seconds had gridlocked and were not expected to converge. We did not use the deconfliction algorithms for gridlocks because they need a preferred passing direction to be agreed up front [17] or determined on line, which assumed agentto-agent communication in [6].
The results shown in Table I depict the aggregated results from 100 Monte-Carlo simulations for the Centralized (14), DF (15), DR (16), CCS (17), and PCCA (18) policies without any additional radius margin added. PCCA was implemented with either a sample delay (∆T = 50ms) or a low-pass filter with a time constant of 0.2 sec to break the algebraic loop between (18) and (19). Table I shows the minimum convergence time to be similar for each algorithm, while the maximum is quite varied. Additionally, the min, max, and mean values do not include the gridlocked simulation results for DF, DR, and CCS. Both the DF and DR algorithms exhibit less liveness and generally take longer for all agents to converge as previously reported in the literature (e.g. [17]). We see this better in Figure 4, where the simulations trials   are sorted by the average convergence time for each trial over all algorithms from maximum to minimum. Generally, the convergence times and liveness of the Centralized and PCCA algorithms are similar, while DF, DR, and CCS exhibit longer times to converge, if at all. It has been established above that the centralized, CCS, and PCCA controllers are always feasible and the simulations confirmed this. However, nearly a third of the DF and DR simulations exhibited infeasible QPs at some point. In this case, the QP solver [8] was configured to return the "least infeasible" solution before implementing the control. Except for slacked constraints on the outer static circle, the algorithms were implemented in pure form without alternative actions to handle infeasibility.
For collision avoidance in the multi-agent case, the centralized controller exhibits the best results, but also requires  Figure 5 that displays the minimum agent-toagent barrier value sorted by average of h min over all the algorithms. DF and CCS generally have larger violations than the other methods while DR has only a few visible violations. Both the Centralized and PCCA controllers exhibit minimal barrier violation and are almost indistinguishable in the plot. We now rerun the Monte-Carlo simulation trials using the worst-case agent-to-agent barrier violations h min recorded in Table I to add a radius margin (r > 2r 0 ) for each algorithm's computation of the barrier constraint h. The results, shown in Figures 6 and 7 and tabulated in Table II, depict the barrier violations with the agents' actual size r 0 ; all methods but one CCS trial effectively avoid collision with radius margin added. The CCS trial with a collision is due to an interaction between agent-to-agent hard constraints and agent-to-staticouter-circle soft constraints. Note also that the radius margins added for DF and DR grow the agent sizes enough to induce additional gridlocks and infeasibility. One could iterate on the barrier margin required for both DF and DR to achieve h min closer to zero, similar to the other methods.  While CCS did deliver infeasibility-free runs, as expected, the collisions and the number of gridlocks was similar to the pure decentralized policies DF and DR. Another surprising finding was the very close, practically indistinguishable results for the Central and the PCCA policies despite the fact that the former runs with full information, while the latter does not know where the other agents are heading, i.e. does not know their u 0j . Next, we will explain these results on a related problem simplified enough to make it analytically tractable.

VI. EQUILIBRIUM INSTABILITY AND LIVENESS
In this section we consider a simpler problem with only two agents, but to make the problem non-trivial for our objective, we give them only one degree of freedom -they can only accelerate or decelerate. The problem is equivalent to robots or vehicles moving through narrow straight corridors where turning is not a useful option. Essentially, the agents will have to decide (negotiate) which one goes first through the intersection. It turns out that the policies that exhibited gridlocks (DF, DR, CCS) create a set of stable equilibrium (gridlock) points, while for those that did not (Centralized, PCCA) there is a single unstable equilibrium point in the physical space. In other words, the liveness in these multiagent systems comes from instability.
The problem considered here is depicted in Figure 8. Each agent can only move longitudinally, accelerate or decelerate. The control action is the velocity, i.e. the model of each agent is the single integrator. For agent i, i = 1, 2, the model iṡ Here, we have used x 1 and x 2 (instead of y 2 ) to denote the distance of the two agents from the origin -the intersection point. The goal of each agent is to move at their desired velocity v 0i , assumed constant, while avoiding collision with the other agent. We assume that the initial displacements from the origin are negative while the desired velocities are positive as depicted in Figure 8. For collision avoidance, we use the same distance-based control barrier function with r ≥ 2r 0 , x = [x 1 , x 2 ] T , and the admissible set C = {x ∈ IR 2 : h(x) ≥ 0}. The barrier constraint is therefore given by where λ > 0 is a design parameter -the barrier bandwidth. Because x 1 and x 2 cannot be simultaneously 0 in the admissible set C, if both control actions v 1 and v 2 are available for collision avoidance, the problem is feasible and h is a CBF. Fig. 8. The configuration for the two agents inside their corridors -the corridor lines just serve for illustration, the agents cannot turn.

A. DF and DR equilibria and their stability
For the DR policy, each agent assumes half of the responsibility for satisfying the barrier constraint while having only its own control at its disposal. For agent 1, the QP is Note that the only difference between the DR and DF policies would amount to removing 1 2 , or equivalently selecting λ larger by a factor of 2. Hence, all the conclusions here apply to DF as well. The solution to (24) for agent 1 is given by The case for agent 2 is symmetric: the subscript "1" → "2". Now, we consider the critical case, in terms of gridlocks, where the barrier constraints for both agents are active: First, because x i < 0, both agents' constraints will activate while h(x) > 0. After they activate,ḣ = − λ 2 h, which results in h(x(t)) > 0 ∀t and guarantees collision avoidance. Second, the only way for the two agents satisfying (26) to move backward is if h(x) < 0, but this has just been ruled out. Therefore, once they both get closer to the origin than r (the shaded region in Figure 9) they are stuck because neither moves backward and one of them has to be farther away than r for the other to pass. Thus, any trajectory that hits the shaded "triangle" will result in a gridlock.
More formally, we look at the equilibrium structure of (26) in the quarter-plane the equilibrium set is an arc or radius r as shown in Figure 9. Moreover, becauseḣ = − λ 2 h, the arc itself is attractive from the points outside of it. Linearizing around an equilibrium point x e ∈ {x ∈ IR 2 : h(x) = 0, x 1 < 0, x 2 < 0}, we obtain the linear systemζ = A dr ζ in the ζ = x − x e coordinates, where The eigenvalues of the matrix A dr are 0 and −λ. This does not necessarily prove that the equilibrium x e is stable because the system (26) is nonlinear. Instead, we consider g(x) = x 2 1 − x 2 2 which satisfiesġ = 0. Hence, the function g(x) is constant along the trajectories of (26) and intersects the arc h(x) = 0 if |g(x(t c ))| < r 2 in the third quadrant. Here, t c is the first time instant when both agents have their constraints activated. This shows that the points on the equilibrium arc are indeed stable and that a small perturbation or noise would not result in them clearing the intersection.

B. Centralized controller equilibrium analysis
With the Centralized controller, the agents have full information about each others intentions and solve the same QP: This QP is executed by both agents and they would activate the constraint at the same time, namely when λh + 2x 1 v 01 + 2x 2 v 02 becomes negative. Before this point, each agent uses its desired constant velocity v 0i and they move in the straight line in the (x 1 , x 2 ) space. After this point, the coupled dynamics becomeṡ By adding and subtracting the right hand sides of (29) and setting them to 0 we obtain the equilibrium set, defined by the intersection of the arc h(x) = 0 and the line x 2 v 01 −x 1 v 02 = 0 as shown in Figure 10 -that is, the equilibrium is a single point. Linearizing around the equilibrium, we obtain the dynamicsζ = A c ζ, with the state ζ = x − x e as above, and the matrix A c given by

C. CCS equilibrium analysis
As before, we give CCS the control over both agents while realizing that only the host action computed by the QP is the actual one (for agent 1, v 1 = v * 11 ) while the other one (v * 12 ) is virtual. We assume no information about the other agent's intention, so the agent 1 QP uses v 02 = 0, and vice-versa. Upon changing variables,v 11 = v 11 − v 01 , the QP problem for the agent 1 is In this case, the factors ρ i 's are used to assure that, when the constraint is active for both agents, the actual barrier constraint (13), the one that guarantees collision avoidance, is satisfied. The control computed by agent 1 for itself (the other one it computes gets discarded) is given by To decide what ρ i to use, we look at the CBF constraintḣ + λh ≥ 0 when each agent implements its own control: λh Because the two terms in the sum are independently computed, each has to be non-negative. A good choice then is ρ i = 1 + , i being the host, j the other agent. This choice of ρ i 's produces the joint dynamics under active constraints as follows: Thus, a part of the equilibrium analysis is the same as in the DR/DF case: • The equilibrium set, given by h(x) = 0, is attractive, i.e.ḣ = −λh, guaranteeing there are no collisions. • The linearization shows the eigenvalues at any equilibrium point x e to be eig(A ccs ) = {0, −λ}. • The function invariant along the trajectories of (32) is g ccs = ln(−x 1 ) − ln(−x 2 ) + c. Thus, the arc h(x) = 0 represent a set of stable (gridlock) equilibrium points. However, the presence the x 2 i in the denominator in ρ i creates an additional (spurious) equilibrium of (32) at x i = 0 not related to the position of the other agent. This singularity in ρ i can be removed by multiplying both side of (31) by x 2 i , but the equilibrium remains.
makes the constraint in (31) active when x i is negative and sufficiently close to 0.
• Making ρ i smaller than 1 + leads to a violation of the actual constraint, while making it larger makes the agents stop before they arrive at the original equilibria h = 0 or x i = 0. Hence, the CCS policy always produces a gridlock either at h = 0 or x i = 0. The first one will not be impacted by a small amount of noise. A small amount of noise would eventually free the agents from the second one -once x i > 0 due to noise, the constraint becomes inactive andẋ i = v i0 .

D. PCCA equilibrium analysis
As was the case with the CCS policy, the PCCA policy performs co-optimization and uses 0 instead of the unknown desired velocity for the other agent. The "error," i.e. the difference between the observed and host computed velocity for the other agent, is filtered and fed back as the disturbance term into the constraint: The closed form solution to the PCCA QP is given by with µ 1 = λh + 2x 1 v 01 + 2x 2 w 2 . The control v 1 = v * 11 is then implemented as the velocity for agent 1. The equations for agent 2 are symmetric.
If both agents have active constraints, which is the only way to have a gridlock because inactive constraints lead to v i = v 0i > 0, the dynamics for the combined system is given byẋ x 2 x 2 Note that we should use a fast filter (i.e. the time constant τ small) because the constraint adherence is within O(τ ) margin of error. This could be established by using the singular perturbation argument (see Chapter 11 in [13]). To briefly illustrate the mechanism behind this property, we note that, regardless of the combination of active constraints between the two agents, the variable z = x 2 w 1 +x 1 w 2 always satisfies As τ → 0, the solution of (36) satisfies , with t 0 the initial time, δ arbitrarily small, and T arbitrarily large. When both agents have active constraints, from (35) we computė In turn, proving that the barrier violation could be made arbitrarily small by selection of the time constant τ . The same equation (37) can be derived for the other cases when either one or both agents have the constraint inactive by subtracting the inactive constraint(s) from the right hand side ofḣ and using z(t) = x 1 (t)v 02 + x 2 (t)v 01 + O(τ ) (details omitted). Hence, the barrier constraint is satisfied with O(τ ) error margin over any arbitrary long time interval (t 0 , T ).
Returning to the equilibrium analysis of (35), we obtain that the one-dimensional equilibrium set in IR 4 is defined by To analyze stability of an equilibrium point (x e , w e ) that belongs to the set defined by (38), we use the ratio µ e = x1e x2e and change the variables: The linearized system around (x e , w e ) in the η-coordinates isη = A p η with A p given by (40) where we have used x 1e = −µ e r/ √ 1 + µ e and x 2e = −r/ √ 1 + µ e . The systemη = A p η is exponentially unstable because with the first eigenvalue being positive. Note that the 0 eigenvalue has moved from the physical states x to the controller states w, while the exponentially unstable state plane. The projection of trajectories onto the physical space (x 1 , x 2 ) should resemble behavior shown in Figure 10 and helps explain the lack of gridlock for the PCCA policy in the simulations in Section V.

E. Summary of the equilibrium analysis and simulations
The analysis in this section correlates closely with the observed simulation results from Section V. While one distinction between decentralized, host-only-control policies and co-optimization policies is related to feasibility, it is not correlated to liveness and absence of gridlocks. The actual mechanism for gridlock avoidance is the presence of unstable equilibria in the joint agent space. The policies that have unstable equilibria (Centralized and PCCA) produced no gridlocks in the 5-agent Monte Carlo simulations. In contrast, the policies with stable equilibria had gridlocks observed. Existence of equilibria themselves cannot be avoided with the non-convex, compact obstacles as one could deduce from the results of [5], Due to the particular structural difference of the 1-D problem, the CCS policy produces an extra equilibrium at the origin and, as a result, would always gridlock. The analysis of the equilibria structure and their stability is summarized in Table III. 2   TABLE III  Furthermore, we ran simulations to illustrate some additional properties for the 1-D problem. We fixed the initial 2 For CCS, the stable equilibrium may gridlock for some initial conditions. The equilibrium that always theoretically gridlocks is the spurious one at 0 that is not stable. A small amount of noise would eventually free the agent. condition of agent 1 at x 1 (0) = −10, its initial speed at v 01 = 2, and swept the initial condition and speed of agent 2 in 0.01 unit increments over the range x 2 (0) ∈ [−11, −8] and v 20 ∈ [1,3]. Where applicable, the disturbance states w i are initialized at 0. As a measure of performance, we consider the extra time the agents took to clear the intersection. For one agent it is defined as the times it took to clear the intersection in the specific simulation run minus what it would have taken with no interference from the other agent. If the agent did not clear in 20 seconds, that was the time used: The extra time plotted in the figures below is the sum of the two: t ext = t ext 1 + t ext 2 . To avoid the potential singularity at x i = 0 for the DR algorithm, we have added the slack variable to the QP (24) producing the dynamicṡ When the weight M on the slack variable goes to infinity, the original dynamics (26) is recovered. For the DF/DR simulations shown in Figure 11, we have used M = 10 6 . The same initial condition and velocity sweep conducted with the Centralized policy produced the results shown in Figure 12. One can clearly see the combinations that lead to the equilibrium, i.e. those that start on the stable manifold corresponding to the selected v 10 and v 20 .
The PCCA results are shown in Figure 13. It was somewhat of a surprise to observe that there are far fewer PCCA than Centralized runs that gridlock: 0.002% PCCA and 0.1% Centralized (for reference, DR policy gridlocks, i.e. reaches the max time of 20 seconds without either agent clearing the intersection, in 15.4% of runs). One likely explanation is that, with fixed velocities, the stable manifold for the Centralized policy is a 1D line in the 2D plane, while for the PCCA it is a 2D manifold in the 4D space. Obviously, it is less likely to hit the stable manifold for the latter. Indeed, it happened only once in 60,000 points with completely symmetric initial conditions and nominal speeds.
Finally, the CCS simulations have not been run because they would have always gridlocked, i.e. reached the 20s limit.

VII. CONCLUSIONS
This paper compared several CBF-based control policies for their performance in multi-agent scenarios. The results show that algorithms that take all the constraints into account and have or pretend to have control over all the agents, have lower convergence times and, as proven in this paper, are always feasible. The Centralized and PCCA policies showed minimal violations while the Decentralized Follower and Reciprocal methods had a few larger violations due to infeasibility. The CCS algorithm, structurally close to PCCA, showed liveness behavior more similar to Decentralized policies -lower mean convergence time, but about the same number of gridlocks. To explain the observed behavior, we analyzed the policies applied to a simpler 2-agent problem. It turned out that the policies exhibiting good liveness and lack of gridlock in simulation have unstable equilibria in the joint agent space, while policies with observed gridlock have stable equilibria. Beyond the retroactive analysis provided in this paper, it is not known to the authors how to design a control policy that creates unstable equilibria or modify an existing one to have this property.