{'fraction_non_alphanumeric': 0.039382299305474724, 'fraction_numerical': 0.00985527490008924, 'mean_word_length': 4.300020563438207, 'pattern_counts': {'":': 0, '<': 2, '<?xml version=': 0, '>': 3, 'https://': 1, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 13, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
Deadlock Analysis and Resolution in Multi-Robot Systems: The Two Robot Case

Collision avoidance for multirobot systems is a well studied problem. Recently, control barrier functions (CBFs) have been proposed for synthesizing decentralized controllers that guarantee collision avoidance (safety) and goal stabilization (performance) for multiple robots. However, it has been noted in several works that reactive control synthesis methods (such as CBFs) are prone to deadlock, an equilibrium of system dynamics that causes the robots to come to a standstill before they reach their goals. In this paper, we analyze the incidence of deadlocks in a multirobot system that uses CBFs for goal stabilization and collision avoidance. Our analysis is formal, in that we demonstrate that system deadlock is indeed the result of a force-equilibrium on robots. We show how to interpret deadlock as a subset of the state space and prove that this set is non-empty, bounded, of measure zero and located on the boundary of the safe set. Based on this analysis, we develop a decentralized three-phase algorithm that uses feedback linearization to ensure that the robots provably exit the deadlock set and converge to their goals while avoiding collisions. We show simulation results and experimentally validate the deadlock resolution algorithm on Khepera-IV robots.


I. INTRODUCTION
Multirobot systems have been studied thoroughly for solving a variety of complex tasks such as search and rescue [1], sensor coverage [2] and environmental exploration [3]. Global coordinated behaviors result from executing local control laws on individual robots interacting with their neighbors [4], [5]. Typically, the local controllers running on these robots are a combination of a task-based controller responsible for completion of a primary objective and a reactive collision avoidance controller. However, including a hand-engineered safety control no longer guarantees that the original task will be satisfied [6]. This problem becomes all the more pronounced when the number of robots increases. Motivated by this bottleneck, this paper focuses on algorithmic analysis of the performance-safety trade-offs that result from augmenting a task-based controller with a collision avoidance constraints as done using CBF based quadratic programs (QPs) [7]. Although CBF based QPs are not hand-engineered, rather they mediate between safety and performance in a rigorous way, yet ultimately they are reactive controllers. They locally (in a decentralized way) explore the acceleration/velocity space from which one admissible control is selected at every time instant. These local approaches exhibit a lack of look-ahead, which causes  the robots to be trapped in deadlocks as noted in [8], [9], [10].
Deadlock occurs because robots reach a state where conflict becomes inevitable, i.e. a control favoring goal stabilization will violate safety (see solid red dot in fig. 1). Hence, the only feasible strategy is to remain static. Although once in deadlock, small perturbations can steer the system away from deadlock, there is no theoretical guarantee that the robots will not fall back in deadlock. To circumvent these issues, this work addresses the following technical questions: 1) What are the characteristics of a system in deadlock? 2) How can we leverage these characteristics to synthesize a controller that provably makes the system exit deadlock and reach its goal?
As a first step towards addressing these questions, in Section III, we review technical definitions for CBF based QPs [10] to synthesize controllers for collision avoidance and goal stabilization. In Section IV, we recall the definition of deadlock and analyze the KKT conditions for the QP when a robot is in deadlock. The mechanics interpretation of KKT conditions indeed reveals the intrinsic force-balance on a robot in deadlock (section V-A). We motivate a set theoretic interpretation of deadlock for the case of N robots, treating it as a subset of the state space, with an eye towards designing a strategy that evades/exits this set. In Section V, we focus on the easier to analyze case for two robots and analyze the mathematical properties of the deadlock set. We prove that this set is on the boundary of the safe set and that it is non-empty, bounded and of measure zero. We believe that these properties offer insight for the characteristics of deadlock in the general N robot case. Finally, in Section VI, we use these properties to derive a provably-correct threephase control strategy to make the robots exit deadlock and make them reach their goals. We demonstrate this strategy on different robot models in simulation, and experimentally on Khepera-IV robots. Finally, we conclude with directions for future work.
II. PRIOR WORK Several existing approaches provide inspiration for the results presented here. Of these, two are especially relevant to our work. In the first category, we describe existing methods for collision avoidance and in the second we focus on prior work on deadlock resolution.

A. Prior Work on Avoidance Control
Avoidance control is a well-studied problem with immediate applications for planning collision-free motions for multirobot systems. Classical avoidance control assumes a worst case scenario with no cooperation between robots [11], [12]. Cooperative collision avoidance is explored in [13] where avoidance control laws are computed using value functions. A robust control formulation of this work is presented in [14] for robot models described by Lagrangian dynamics and bounded noise in actuator torques. Velocity obstacles have been proposed in [15] for motion planning in dynamic environments. They select avoidance maneuvers outside of robot's velocity obstacles to avoid static and moving obstacles by means of a tree-search. While this method is prone to undesirable oscillations, the authors in [16], [17], [18] propose reciprocal velocity obstacles that are immune to such oscillations. More recently, control barrier function based controllers have been used in [6], [10] to mediate between safety and performance using QPs. The QP computes a controller closest to a task-based control that guarantees collision avoidance.

B. Prior Work on Deadlock Resolution
The importance of coordinating motions of multiple robots while simultaneously ensuring safety, performance and deadlock prevention has been acknowledged in works as early as in [9]. Here, authors proposed scheduling algorithms to asynchronously coordinate motions of two manipulators to ensure that their trajectories remain collision and deadlock free in addition to reaching their goals. However, their approach relies on prior knowledge of the explicit geometric path in the workspace each robot should take (without assuming knowledge of the other robot's path). In the context of mobile robots, [19] identified the presence of deadlocks in a cooperative scenario using mobile robot troops. To the best of our knowledge, [20] were the first to propose algorithms for deadlock resolution specifically for multiple mobile robots. Their strategy for collision avoidance modifies planned paths by inserting idle times and resolves deadlocks by asking the trajectory planners of each robot to plan an alternative trajectory until deadlock is resolved. Authors in [21] proposed coordination graphs to resolve deadlocks in robots navigating through narrow corridors. Authors in [22] added perturbation terms to their optimal controllers for avoiding deadlock. Similarly, authors in [10] use consistent perturbations and modify the QP to synthesize controllers which evade deadlock.
Differently from these works, we characterize the analytical properties of states in deadlock. We explicitly analyze controls from CBF based QPs and demonstrate that intuitive explanations for system in deadlock are indeed obtained from analysis using duality. We do not consider additive perturbations for resolving deadlocks since there are no formal guarantees for such methods. Instead, we use feedback linearization to synthesize a provably correct controller that ensures safety, performance and deadlock resolution.

III. AVOIDANCE CONTROL WITH CBFS: REVIEW
In this section, we review CBF based QPs used for synthesizing controllers that mediate between safety (collision avoidance) and performance (goal-stabilization) for multirobot systems. We refer the reader to [10] for a comprehensive treatment on this subject, since our work builds on top of their approach. Assume that we have N mobile robots, each of which follows double-integrator dynamics: , where p i = (x i , y i ) ∈ R 2 represents the position of robot i, v i ∈ R 2 represents its velocity and u i ∈ R 2 represents the acceleration (i.e. control). The collective state of robot i is denoted by z i = (p i , v i ) and the collective state of the multirobot system is denoted as Z = (z 1 , z 2 , . . . , z N ).
Assume that each robot has maximum allowable acceleration limits |u i |≤ α i that represent actuator constraints. The problem of goal stabilization with avoidance control requires that each robot i must reach a goal p di while avoiding collisions with every other robot j = i. For reaching a goal, assume that there is a prescribed PD Although this controller by itself ensures exponential stabilization of each robot to its goal, there is no guarantee that the resulting trajectories will be collision free.
Based on [10], a pairwise safety constraint is formulated for every pair of robots to ensure mutual collision free motions. This constraint is mathematically posed by defining a safety function that maps the joint state space of a pair of robots i and j to a real-valued safety index i.e. h : This index is defined as [10], Robots i and j are considered to be collision-free if their states (z i , z j ) are such that h ij (z i , z j ) ≥ 0. We define the "safe set" as the zero level super set of h ij i.e. C ij := The boundary of the safe set is defined as: Assuming that the initial positions of robots are in the safe set C ij , we would like to synthesize controls u i and u j that ensure that future states of the robots i and j also stay in C ij . This can be achieved by ensuring that where we choose, κ(h) := h 3 . For the given choice of h, constraint eq. (4) can be rewritten as compactly This constraint is distributed on robots i and j as: (7) Therefore, any u i and u j that satisfy eq. (7) are guaranteed to ensure collision free trajectories for robots i and j in the multirobot system. Note that these constraints are linear in u i and u j for a given state (z i , z j ). Therefore, the feasible set of controls is convex. Assuming robot i wants to avoid collisions with its M neighbors, there will be M collision avoidance constraints. To mediate between safety and goal stabilization objective, a quadratic program is posed that computes a controller closest to the PD controlû i (z i ) (in 2-norm) and satisfies the M collision avoidance constraints.
This QP has (M + 4) linear constraints (M from collision avoidance with M neighbors and four from acceleration limits). Each robot i executes a local version of this QP and computes its optimal u * i . The control generated by this QP represents a reactive collision avoidance mechanism. At every time step, u * i depends on the state of the ego robot z i and its M neighbors. As long as the QP remains feasible, the generated control u * i ensures collision avoidance of robot i with its neighbors. In the next section, we use this method to analyze the incidence of deadlocks due to this technique.

IV. ANALYSIS FOR N ROBOT DEADLOCK
We reviewed the problem formulation of multirobot collision avoidance and goal stablization using the framework of CBF based QPs. In this section, we will show that this approach can result in deadlocks (depending on the initial conditions and goals of robots). Additionally, we want to analyze qualitative properties of a robot in deadlock. Towards that end, we will investigate the KKT conditions of the problem in eq. (8). Our goal is to use these properties to devise a strategy to make the system exit deadlock.
From our numerical simulations, we observed that one scenario when deadlock occurs is when the initial states of a pair of robots and their goals are symmetric with respect to one another. That is to say that one scenario prone to deadlock in robots i and j is when the initial position of robot i is the desired goal for robot j and vice versa. To illustrate this point, Fig. 2 shows the states of two robots executing controllers based on eq. (8) . Notice from fig. 2(a) that the positions of robots have converged, but not to their respective goals. Therefore, the outputs from the prescribed PD controller will still be non-zero after convergence. Additionally, the corresponding velocities have converged to zero ( fig. 2(b)), and the control inputs from eq. (8) have converged to zero as well ( fig. 2(c)). Following these observations, deadlock is defined as follows This definition states that for a robot to be in deadlock, the robot should be static i.e. its velocity should be zero, and the output from the QP based controller should also be zero, even though the prescribed PD controller reports non-zero acceleration since the robot is not at its intended goal. We now review the KKT conditions for the optimization problem in eq. (8) and then specifically analyze them in deadlock.

A. KKT Conditions
As explained in Section III, we seek control inputs that guarantee collision avoidance and goal stabilization. Recall that each robot i computes a control by solving a local QP as in eq. (8). For the following discussion, define a j := −∆p ij andb j = αi αi+αj b ij . To simplify notation, we will drop subscript i and implicitly assume that the QP is being solved for the ego robot. Therefore, we rewrite eq. (8) as: Letã k denote the rows ofÃ andb k denote the elements of b. The KKT conditions are necessary and sufficient (in this case) for a global optimum of the problem in eq. (9). The Lagrange dual function is Let (u * , µ * ) be the optimal primal-dual solution to problem eq. (9). The KKT conditions [23] for this problem are 2) Primal Feasibilitỹ 3) Dual Feasibility

4) Complementary Slackness
Define the set of active and inactive constraints as follows: Using complementary slackness from eq. (15), we deduce Therefore, we can restrict the summation in eq. (12) to the set of active constraints only i.e.

B. KKT Conditions for the deadlock case
Since in deadlock, the acceleration input to the robot i.e. u * ≡ 0 is also obtained from QP, KKT conditions can still be used to analyze the characteristics of the system in deadlock. From Def.1, we know that in deadlock, u * = 0,û = 0 and v = 0. We conclude that: 1) u * =û i.e. the solution to the QP is not equal to the prescribed PD controller (which means thatû is infeasible in deadlock i.e. a Tû b ). 2) u * = 0 =⇒ u * = ±α. This implies that at least the last four constraints inÃu ≤b are inactive i.e. {M + 1, M + 2, M + 3, M + 4} ∈ IA(u * ).
Using these observations, we can rewrite the KKT conditions for the deadlock case as follows: 2) Primal Feasibilitỹ 3) Dual Feasibility

4) Complementary Slackness
Based on these conditions, we will now motivate a settheoretic interpretation of deadlock. Assume that the state of ego robot is z = (p, v) and it has M neighboring robots denoted as Z neighbors . Define P ∈ R 2×4 and V ∈ R 2×4 appropriately to extract the position and velocity components from z i.e. p = P z and v = V z. Finally, define D as: The set D is defined as the set of all states of the ego robot which satisfy the criteria of being in deadlock. We have combined the conditions of deadlock into a set theoretic definition. Additionally note that for each robot, its set of deadlock states depends on the states of its neighboring robots. This is because the Lagrange multipliers depend on the states of all robots. To highlight this dependence, we use the notation D(z | Z neighbors ).
The motivation behind stating this definition is to interpret deadlock as a bonafide set in the state space of the ego robot and derive a control strategy that makes the robot evade/exit this set. We now rewrite this definition in more easily interpretable conditions. From eq. (19) and eq. (20), note that u * (z) = 0 ⇐⇒û(z) = 1 2 Sinceã k = −∆p ik = −P (z − z k ), we rewrite eq. (25) as: We will use this condition to replace the u * (z) = 0 criterion in the def. of D in (24). Secondly, we know that prescribed controllerû(z) is a PD controller. Define the goal state as z d = (p d , 0). Noting thatû(z) = 0 and v = 0 in deadlock: This criterion is merely restating that in deadlock the ego robot is not at its goal. Finally, we note that the third condition is that the velocity of the ego robot is zero i.e. v = 0 ⇐⇒ V z = 0 Combining these conditions, we rewrite the definition of the deadlock from eq. (24) as follows: The Lagrange multipliers µ * k , in general, are a nonlinear function of the state. The exact values of µ * k can only be determined on the basis of the set of active constraints. If there are M neighboring robots i.e. M collision avoidance constraints per ego robot, there will be 2 M possible cases of active/inactive constraints. Therefore, for further analysis, we will restrict the discussion to the special case of two robots.

V. ANALYSIS FOR TWO ROBOTS
In section IV, we proposed a set-theoretic definition of deadlock for a specific robot in an N robot system. In this section, we will refine the KKT conditions derived in Sec. IV-B for the case of two robots in the system. We restrict to two robots not only because this case is easier to analyze, but also because it reveals several important underlying characteristics of the system in deadlock that will extend to the N robot case. Specifically, we believe that deadlock analysis for N robots can be decomposed into subproblems involving deadlock analysis involving pairs of robots. We will explore this future work. One key feature of a two-robot system is that a single robot by itself cannot be in deadlock i.e. either both robots are in deadlock simultaneously or neither. This is because the sole collision avoidance constraint is symmetric in a system with just two robots. Keeping this in mind, we define system deadlock set to be the set of states for which both robots are in deadlock. To define this set, we modify eq. (25); specifically for this case there is no summation since the ego robot avoids collision only with the other robot i.e.
Assuming (z 1 , z 2 ) are the states of the two robots, we modify eq. (28) and define D system as: where a 1 = −a 2 = −(p 1 − p 2 ). To gain more insight into this system deadlock, we derive analytical expressions for the Lagrange multipliers µ * 1 , µ * 2 . Depending on whether the collision avoidance constraint is active/inactive at the optimum, there are two cases: Case 1: The constraint a T u ≤b is active at u = u * . (31) The constraint a T u ≤b is inactive at u = u * . i.e. a T u * <b. From complementary slackness, it follows that i.e. µ * = 0 and hence u * =û. However, this contradicts the def. of deadlock. Hence, we conclude that case 2 can never arise when the two robots are in deadlock.

A. Mechanics interpretation of KKT conditions
Recall eq. (29) which is one of the conditions for two robots in deadlock. The left hand side of this equation iŝ u(z) = −k P (p ego −p d ). The right hand side of this equation is 1 2 µ * ã = − 1 2 µ * (p ego −p neighbor ). Writing eq. (29) another way, we get −k p (p ego − p d ) + 1 2 µ * (p ego − p neighbor ) = 0. We interpret the first term as an attractive force that pulls the ego robot towards the goal p d . Since µ * > 0, we interpret the second term as a repulsive force pushing the ego robot away from its neighbor. Thus, deadlock occurs when the net force due to attraction to goal and repulsion from the other robot vanishes. We illustrate this equilibrium in Fig. 3.

B. Characteristics of two-robot deadlock
We are now interested in analyzing qualitative properties of the system deadlock set with an eye towards synthesizing controllers that enable the robots to get out of deadlock. We will show that when deadlock occurs, (1) the two robots are separated by the safety distance, (2) deadlock set is nonempty and (3) deadlock set is bounded and of measure zero. Theorem 1. In deadlock,the two robots are separated by the safety distance and on verge of violating safety (Fig. 1, 3) Proof. In eq. (31), we proved that the collision avoidance constraint is active in deadlock. Since both robots are in deadlock, we know that both of their constraints are active i.e. a T 1 u * 1 =b 12 , a T 2 u * 2 =b 21 and u * 1 = 0 and u * 2 = 0. This impliesb 12 =b 21 = 0. Using eqs. (6) and (7) and that in deadlock, (v 1 , v 2 ) = (0, 0) we get Recall h 12 from eq. (2) and using that (v 1 , v 2 ) = (0, 0), we get Therefore, h 12 = 0 ⇐⇒ ∆p 12 = D s . Since robots remain safe (assuming QP is feasible), we disregard ∆p 12 = Fig. 3: Force equilibrium in deadlock in two-robot case 0. Therefore, ∆p 12 = D s . Additionally, recalling the definition from ∂C from eq. (3) we deduce that, in deadlock, This result confirms our intuition, because if the robots are separated by more than the safety distance, then they will have space to move towards each other, albeit with very small non-zero velocity, which however would contradict the definition of deadlock. We now propose a family of states that are always in the deadlock set D system eq. (30).
Theorem 2. ∀ k p , k v , D s > 0, ∃ a family of states z * 1 and z * 2 such that (z * 1 , z * 2 ) ∈ D system . Moreover, these states are such that the robots and their goals are all collinear.
Although in this theorem, we proposed a candidate set of states and verified that they are in deadlock, one can check by explicitly solving the equations in eq. (30) that these are in fact, the only states that satisfy the criteria of deadlock.
Theorem 3. D system is bounded and of measure zero.
Proof. Following the definition of p * 1 and p * 2 from theorem 1 and 2, we can show that when two robots are in deadlock, their positions satisfy the following constraint: This can be verified by straightforward substitution. From this constraint it is evident, that the deadlock set is not "large" and of measure zero. That is why, random perturbations are one feasible way to resolve deadlock. However, whether or not deadlock gets resolved depends on the stability of this set. We explore resolution of deadlock in the next section.
e r Y 9 5 a 8 k q Z g 7 R H 1 i f P y K G l q w = < / l a t e x i t > VI. DEADLOCK RESOLUTION We are now interested in using the properties derived above to synthesize a corrective strategy that (a) gets the robots out of deadlock, (b) ensures safety and (c) makes the robots converge to their respective goals. One approach to accomplish these three objectives is to detect the incidence of deadlock while the QP based controller is running on the robots. Once detected, any small non-zero perturbation to control will instantaneously give a non-zero velocity to the robots. Thereafter, the QP based controller can take charge again and we can hope that using this controller the system state will come out of deadlock at-least for a short time. This approach has two limitations however, firstly, since it was the QP based controller that led the system to deadlock in the first place, there is no guarantee that the system will not fall in deadlock again. Secondly, perturbations can violate safety.
We propose a provably-correct controller which ensures that goal stabilization, avoidance control and deadlock resolution are satisfied. Refer to Fig. 4 for a schematic of our approach. This algorithm is described here: 1) Given initial position of the robots, the algorithm starts by executing controls derived from CBFs based QP in Phase 1. This ensures movement of robots to the goals and safety by construction. To detect the presence of deadlock, we continuously compare u * , v , p − p d against small thresholds. If satisfied, we switch control to phase 2, otherwise, phase 1 continues to operate. 2) In this phase, we use any controller to ensure that the (1) robots rotate around each other to swap positions while (2) maintaining the safe distance. Feedback linearization (FL) is one viable approach that can generate such a controller, and moreover, FL based control can be easily decentralized. By ensuring ∆p 12 = D s and rotation (∆p T 12 ∆v 12 = 0) , we ensure that safety is maintained (i.e h 12 ≥ 0). Once the robots swap their positions (which is guaranteed by design), their new positions will ensure that prescribed PD controllers will be feasible in the future.
3) After convergence of Phase 2 (which happens in finite time), control switches to Phase 3, which simply uses the prescribed PD controllers. This phase guarantees that the distance between robots is non-decreasing and safety is maintained as we prove in theorem 4. Fig. 5 shows simulation and experimental results from running this strategy on a pair of double-integrator ( Fig.  5(a)) and nonholonomic robots ( Fig. 5(b),5(c)). Videos of simulations and experiments are available at https:// tinyurl.com/y4ylzwh8. Note that for nonholnomic robots, we noticed from simulations and experiments that deadlock only occurs if the body frames of both robots are perfectly aligned with one another at t = 0. Since this alignment is difficult to establish in experiments, we simulated a virtual deadlock at t = 0 i.e. assumed that the initial position of robots are ones that are in deadlock. We next prove the correctness of our three-phase strategy: