{'fraction_non_alphanumeric': 0.0444295249002804, 'fraction_numerical': 0.010663085976067296, 'mean_word_length': 4.162487257900102, 'pattern_counts': {'":': 0, '<': 5, '<?xml version=': 0, '>': 5, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 10, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
Robust Semi-Cooperative Multi-Agent Coordination in the Presence of Stochastic Disturbances

This paper presents a robust distributed coordination protocol that achieves generation of collision-free trajectories for multiple unicycle agents in the presence of stochastic uncertainties. We build upon our earlier work on semi-cooperative coordination and we redesign the coordination controllers so that the agents counteract a class of state (wind) disturbances and measurement noise. Safety and convergence is proved analytically, while simulation results demonstrate the efficacy of the proposed solution.


I. INTRODUCTION
Coordination in multi-agent systems has attracted much attention over the last decade with a plethora of theoretical and practical problems that this paper can not cite in their entirety; for recent overviews the reader is referred to [1]- [4].
A fundamental problem of interest in the area of distributed coordination and control is the decentralized multiagent motion planning, which mainly focuses on generating collision-free trajectories for multiple agents (e.g., unmanned vehicles, robots) so that they reach preassigned goal locations under limited sensing, communication, and interaction capabilities. Numerous elegant methodologies on planning the motion for a single agent (robot) have appeared in recent years, with the most popular being (i) samplingbased methods, including probabilistic roadmaps [5], and rapidly-exploring random trees [6], [7], (ii) Lyapunov-based methods, including either the definition of closed-form feedback motion plans via potential functions or vector fields, or computation of Lyapunov-based feedback motion plans via sum-of-squares programming [8], [9], and (iii) graph search and decision-theoretic methods, see also [10], [11] for a detailed presentation. Although each method has its own merits and caveats, arguably Lyapunov-based methods (often termed reactive) are particularly popular for multiagent motion planning problems, as they offer scalability with the number of agents, and the merits of Lyapunov-based control design and analysis.
In addition, robustness against modeling and/or measurement uncertainties is of primary importance for real-world systems and applications. Hence the problems of modeling, quantifying, and treating uncertainty are of particular interest when it comes to multi-agent coordination. A straightforward way to model uncertainty in multi-agent systems is by considering them as bounded disturbances. In [12], a stable uncertainty is assumed to be bounded in H ∞ -norm by some prior given desired tolerance, and a state space observer along with a robust controller are designed by using the algebraic Riccati equations. In [13], an additive l 2 -norm bounded disturbance is considered, and a robust controller is proposed for the distributed cooperative tracking problem in a leader-follower network by using Lyapunov stability theorems. In [14], both bounded disturbances and unmodeled dynamics are assumed in the dynamics of agents; an identifier for each agent is designed to estimate the unknown disturbances and unmodeled dynamics. Related work considering bounded deterministic disturbances can be found in the design of finite-time consensus algorithms with mismatched disturbances [15], and the rotating consensus control with mixed model uncertainties and external disturbances [16].
Another way of modeling uncertainty is by Gaussian random processes. In [17], communication noises are described by a standard Brownian motion, and the mean square consensus in the multi-agent system is achieved by proposing a stochastic approximation-type gain vector, which attenuates the effect of noises. This work is extended to networks with Markovian switching topologies [18], and leader-follower networks [19] with a similar noise-attenuation controller. In [20], it is assumed that the measurements for each agent are disturbed by white noises. Robust consensus can be achieved by applying stochastic Lyapunov analysis. Based on this idea, in [21], the average-consensus problem of firstorder multi-agent systems is considered, and a necessary and sufficient condition is proposed for robust consensus by using probability limit theory. The aforementioned methods are efficient in solving the coordination problems with stochastic uncertainties in measurement or system dynamics; however, safety (i.e., the generation of collision-free trajectories) is not considered.
In contrast to the aforementioned results, in this paper we consider the problem of generating collision-free trajectories for multiple agents in the presence of uncertainty. We propose a robust, Lyapunov-based coordination protocol that achieves collision-free motion for multiple agents in a distributed fashion, in the presence of state and measurement uncertainties. The method builds upon our earlier work in [22], in which the nominal (uncertainty-free) case was considered. More specifically, we redesign the semi-cooperative coordination protocol in [22] so that it accommodates the case of state and measurement uncertainties. Our approach yields a method on the safe and robust motion planning of multiple agents that is based on analytic vector fields, hence offers scalability with the number of agents along with provable guarantees. In summary, the contributions of this paper are: (i) a robust, semi-cooperative coordination protocol that accommodates for a class of stochastic disturbances in the agents' dynamics and measurements, and (ii) the derivation of analytical bounds on the navigation (estimation) and final state errors of the agents in terms of the considered uncertainties.
The paper is organized as follows: Section II includes an overview of the modeling of the system under the effect of disturbances. Section III presents the robust coordination protocol along with the safety and convergence analysis. Section IV evaluates the performance of the proposed method via two simulation scenarios. Our conclusions and thoughts on future work are summarized in Section V.

II. MODELING AND PROBLEM STATEMENT
Let us consider N identical agents i ∈ {1, . . . , N }, which are assigned to move to goal locations of position coordinates r gi = x gi y gi T relative to some global frame G, while avoiding collisions. The motion of each agent i is modeled under unicycle kinematics with additive disturbances that stand for state and output uncertainty, for instance due to wind effects and sensor imperfections, respectively, as: where q i = r T i θ i T is the state vector of agent i, comprising the position vector r i = x i y i T and the orientation θ i of the agent with respect to (w.r.t.) the global frame G, u i = u i ω i T is the control input vector comprising the linear velocity u i and the angular velocity ω i of agent i, f (·, ·) : R 3 × R 2 → R 3 is the vector valued function of the agent dynamics, and c(·) cos(·), s(·) sin(·) and The random process w = w x w y T is assumed to be Gaussian, white, of known meanw = w xwy T and known covariance P w ∈ R 2×2 . To maintain the Lipschitz continuity of the proposed control law, we assume that the mean value of state disturbance is continuous in time and is bounded. Furthermore, y i ∈ R m is the output vector comprising the available measurements, h i (·) : R 3 → R m is the output function, and v i ∈ R m is the measurement noise modeled as a Gaussian, white process of zero meanv i = 0 and known covariance P vi ∈ R m×m . For simplicity in the sequel we assume that the output function is the identity map so that the measurement model reduces to y i = q i + v i , and that the measurements are uncorrelated, so that the covariance matrix of v i reads P vi = diag(σ vi,1 , σ vi,2 , σ vi,3 ).
Each agent i is modeled as a closed circular disk of radius i , and has a circular communication/sensing region C i of radius R c centered at r i = x i y i T , denoted as C i : {r ∈ R 2 | r i − r ≤ R c }. We denote N i the set of neighboring agents k ∈ C i of agent i. We assume that each agent i can measure the position r k , orientation θ k and receive the linear velocity u k of any agent k lying in C i . In our earlier work [22] we considered the nominal case of (1), i.e., the case for w = 0, v = 0, and designed the following semi-cooperative distributed coordination protocol: Coordination of linear velocities: The linear velocity u i of each agent i is governed by the control law: where: d ij is the Euclidean distance between agents i and j, agent k ∈ N i , given as: with the terms in (10) defined as: Coordination of angular velocities: The angular velocity ω i of each agent i is governed by the control law: where k ωi > 0, and ϕ i arctan Fiy Fix is the orientation of a reference vector field F i for agent i, defined as: where details about the attractive and repulsive vector fields can be found in [22]. Under this protocol we were able to establish collisionfree and almost globally convergent motion of the agents towards to their goal locations: Theorem 1: Consider N agents i ∈ {1, . . . , N } assigned to move to goal locations r gi . Then, under the coordination protocol (2), (4), each agent safely converges to its goal configuration almost globally, except for a set of initial conditions of measure zero.
Proof: The design and analysis of the coordination controller is given in [22].
In this paper we seek to design a robust coordination protocol so that each agent i can safely accommodate the effects of state and measurement uncertainties w(t), v i (t), t ∈ [0, ∞), respectively. Since we are only concerned about radial convergence of the agents to their respective goal locations, we re-define the radially attractive vector field F r gi for r i = r gi as: With this globally attractive field, the new reference field is given by

III. ROBUST COORDINATION: DESIGN AND ANALYSIS
The problem of safe trajectory generation in the presence of disturbances is tackled in two steps. The first step is to modify the nominal controller in order to accommodate for known state disturbances, that in our case can be thought of as wind effects. This task is achieved by feed-forwarding the mean wind speed to each agent's control law as per (9) and (13). Once we have a controller that handles this class of known disturbances, the next step is to make it robust w.r.t. unknown, zero-mean state disturbances and sensor noises. To accomplish this, an Extended Kalman Filter (EKF) based observer is used to estimate the state vector for the feedback coordination law of each agent. In order to incorporate the estimation error, the crucial safety parameters involved in the nominal control law (i.e., the minimum allowed separation d m and the set J k of critical neighbors k to agent i) in (2) are modified. Then, with a controller in hand for nominal (or disturbance-free case), feed-forwarded with the known mean wind speed, and by using estimated states as feedback with properly modified safety parameters, we get a robust coordination protocol that steers the agents within a neighborhood of their goal locations, while maintaining safety at all times. Recall that the system is safe if the interagent distance d ij between any pair of agents i, j is always greater than a minimum allowed separation d m .

A. Control design under bounded disturbances
We first consider the case where each agent i is subject to known state disturbances, without any measurement uncertainty, i.e., we consider the agent dynamics: wherew is the known mean of the state disturbance and T is the control input. We propose the following coordination protocol yielding the feedback control law u p i (q,w, d m ) for the perturbed dynamics (8) of agent i: Coordination of linear velocities: The linear velocity of each agent i is governed by the control law: where: • the linear velocity of agent i when free of conflicts is: where k ui > 0 and F i is given by the nominal vector field (7), • for a = a 1 , . . . , a n T , the function g(a) = e −µai is a smooth approximation of the minimum function min{a 1 , . . . , a n } as µ → ∞, • u i|k is the safe velocity of agent i w.r.t. a neighbor agent k ∈ N i , given as: with the terms in (10) defined as: , if agent i moves towards agent j, then agent i adjusts its linear velocity according to the velocity profile shown here, given analytically by (12).
Coordination of angular velocities: The angular velocity of each agent i is governed by the control law: where k ωi > 0, ϕ p i arctan  a point (x, y), with the vector field F p i for the perturbed system (8) given out of: where F i is the nominal vector field given out of (7), and u i is given out of (11). The time derivative of ϕ p i readṡ It can be readily seen that steady-state solution ofθ i = The following theorem proves that safety for the multiagent can be guaranteed under the control law given by (9) and (13): Theorem 2: If each agent i ∈ {1, . . . , N } subject to the system dynamics (8) follows the control law given by (9) and (13), then ∀i, j ∈ {1, . . . , N }, i = j, it holds that: and each agent converges to its goal location almost globally, i.e., except for a set of initial conditions of measure zero. Proof: To prove (15), we have that under the control law (9), agent i adjusts its linear velocity u i according to the velocity profile shown in Fig. 1, given analytically out of (12), so that the distance d ij w.r.t. the worst case neighbor j remains greater than d m . Mathematically, it is required that so that the inter-agent distance does not decrease further once the agents i, j are at the minimum allowed separation d m .
The derivative of inter-agent distance is given in (17). Hence, we have: The worst case neighbor for agent i is defined as the agent j ∈ {N i | J j r ji T η i < 0} towards whom the rate of change of inter-agent distance d ij given by (18), due to the motion of agent i, is maximum. More specifically, the decision making process works as follows: The term J j < 0 describes the set of neighbor agents j of agent i towards whom agent i is moving [23]. Thus agent i computes safe velocities u i|j w.r.t. each neighbor j ∈ {N i | J j < 0}, and picks the minimum u i|j of the safe velocities so that the first term in (18) is as less negative as possible. Now, the value of the safe velocity u i|j (12) when d ij = d m is by construction equal to ε i u is|k = ε i u j rji T ηj rji T ηi . Plugging this value into (18) reads: To see why this condition is true, recall that ε i − 1 < 0, u j ≥ 0, and r ji T η j ≤ 0: this is because agent j is either following a vector field F j that points away from agent i, or happens to move away from agent i in the first place. This implies that the inter-agent distance d ij can not become less than d m [22]. To verify this argument, it is sufficient to show that in the presence of known disturbancesw, the motion of any agent i, j ∈ {1, 2, . . . , N } under the control law (9) and (13) is along their nominal vector fields given by (7), as follows: Let θ d i be the nominal direction that agent i is supposed to follow under the nominal vector field F i , i.e., θ d i arctan Fix Fiy . From the steady-state solution ofθ i = ω i under the control law (13), we have θ i = ϕ p i , where θ i is the orientation of the agent i.
Let ∠(·) be signed angle, defined to be positive in the clockwise direction and negative in the counter-clockwise direction. Now, from (8) we have: ∠(ṙ i −w) = θ i . Also, by construction of the new vector field (14), = θ i out of the steady-state solution of (13), see also Figure 2. Thus we have that Hence, the motion of agent i is along the desired nominal vector field F i . Analysis of convergence of the agents to their goal locations is given in [22]. Note that the analysis given in [22] is carried out for dipole type attractive vector field, which will still hold for the radially attractive vector field. Since, except for a set of initial conditions of measure zero, the nominal vector field drives the agents to their goal location (Theorem 1), it follows that the modified coordination protocol also drives the agents to their goal locations almost globally.
It is to be noted that while the direction of motion of agent i is along the nominal vector field F i , its orientation (heading angle) θ i remains along the modified vector field F p i .

B. Extension of the controller for stochastic disturbances
In order to estimate the states of the system in the presence of stochastic disturbances, we design a system observer based on the Extended Kalman Filter: is the linearized output matrix evaluated atq i , P i is the covariance matrix of the estimation errorq i = q i −q i , and K i is the Kalman gain. Note that the control law (20e) has the same form as (9) but it uses the estimated statesq for feedback, the mean wind speedw for feed-forward command, and involves d m as the new safety parameter. The last parameter J is introduced to re-define the worst-case neighbor, as per (21). Stability of EKF-based estimator: In [24], authors have shown that the EKF is stable if there exist positive constants c, p, q, δ, k such that: whereq i = q i −q i and H.O.T stands for higher-order terms of the linearization . Furthermore, if these conditions hold, then the estimation error is exponentially mean-square bounded. Using this result, we now show that EKF based estimator will remain bounded for system (1) whose control law is given by (20e). In our system, H is just an identity mapping, which allows us to choosec = 1. Since H is identity, we have that the system is always observable. By the assumption on the type of disturbance we consider in (1), the covariance matrices P vi and P w are non-zero constant matrices and hence are bounded. We assume that the initial estimation error is bounded. Now, we show that our closedloop system also satisfies the condition on boundedness of H.O.T . The function f of the system dynamics given by (1) is continuously differentiable in q i and u i . From (9) and (13) we have that the control law (20e) is a bounded, continuously differentiable function of q, since the vector field F p i , its partial derivatives w.r.t.  (20) is stable, which implies that the estimation errorq will remain bounded for sufficiently small disturbances, i.e., for small covariance matrices P w and P vi . We can therefore bound the norms of the estimation errors in individual states and position of agent i by small, positive numbers. Define the maximum of the errors in the estimation of the states for any agent i as where P ill , l ∈ {1, . . . , n}, are the diagonal terms of error covariance matrix P i . Also, we define the maximum error in the estimation of the position as d 2 x + 2 y . Using the 3σ bound for the Gaussian noise, we have that Referring to Definition 4.1 of [24], we can choose a function Λ(q) = −1, so that Λ = 1. Then, using Theorem 7 in [26], we have that P i (t) ≤ P i (0) + 1. We choose P i (0) = P vi , so that max P (t) = max i P vi + 1. With this bound on the covariance matrix, we can express x = y = θ = max i P vi + 1 and d = 2 max i P vi + 1 .

C. Safety Analysis
The linear velocity coordination law (9) depends upon the safety parameter d m . As only estimates of the interagent distances are available to each agent, one can set the minimum allowed estimated distanced ijmin equal to d m (given by (23)), in order to ensure that actual interagent distance d ij remains greater than the minimum allowed distance d m .
We re-define the worst case neighbor (defined earlier) in terms of the estimated states as: To proceed with the analysis, we first prove the following Lemma: , then with probability 0.997 Proof: Since we are concerned about safety of the system, let's assume that inter-agent distance d ij = d m . We use the fact that which further reads as in (22).
. Since θ and d are small positive numbers, we have Since the bounds on the estimation error are probabilistic, we only guarantee that this result holds with probability 0.997 1 .
Now we use this result to show the safety of the system. In order to maintain the safety of the agents in the presence of disturbances, the safety parameter d m in the control law (20e) is given by: Theorem 3: If each agent i under the system dynamics (1) follows the control law given by (20e), and if d m is given by (23), then with probability 0.997, ∀t ≥ 0, ∀ i, j ∈ {1, . . . , N }, j = i: Proof: Using triangle inequality, Choosing d m as per (23), we get r i − r j ≥ d m . To complete the proof, it is sufficient to show that whend ij = d m , the time derivative of inter-agent distance is positive, i.e.ḋ ij > 0. In the presence of uncertainties, to guarantee that the system is safe, we modify the definition of the worst case neighbor as j ∈ {N i |Ĵ j r T jiη j < − J } so that, from Lemma 1 we have that r T ji η j ≤ 0, which impliesḋ ij ≥ 0 atd ij r i −r j = d m . Therefore, we have that: (i) the inter-agent distance does not decrease beyond this point. Hence the multi-agent system always remains safe.
D. Analysis of convergence to goal location Theorem 4: If agent i under the system dynamics (1) follows the control law given by (20e), then with probability 0.997: where f = d + , where is an arbitrary small positive constant. 1 Note that this can be increased to a value arbitrarily close to 1 by using k-σ rule to bound the estimation error, where k is arbitrarily large.
Proof: Using triangle inequality, System (20a) can be seen as a perturbed form of (8) with y i −ŷ i being the constantly acting, bounded perturbation. From Theorem 2, we have that r gi is an (almost globally) asymptotically stable equilibrium of (8). Furthermore, (assuming no interactions among agents in the vicinity of the goal locations) one has that r gi is a stable equilibrium of (20a). To verify this argument, use the candidate Lyapunov function V = r i − r gi 2 . Define r e r i − r gi . Now, taking the time derivative of candidate Lyapunov function along the system (20a), we geṫ Note that u p i cϕ p i +w x u p i sϕ p i +w y is theṙ p i of agent i in the absence of unknown disturbance with magnitude |ṙ p i | = u i and is along the attractive vector field F r gi which points in the direction −(r i −r gi ). Hence, we have that u p i cϕ p i +w x u p i sϕ p i +w y = −u i re re . Finally, since the EKF based estimator is stable, the perturbation term K i (y i −ŷ i ) can be bounded by K i d ≤ δ. Hence, the time derivativeV readṡ Hence, we haveV ≤ 0 for r e = r i − r gi ≥ tanh −1 δ kui where k ui is chosen to be greater than δ. Using the stability of perturbed systems under the effect of constantly acting (non-vanishing) perturbations [27], we have that r gi is a stable equilibrium of (20a), which ensures that r i∞ −r gi ≤ for some small positive number > 0. Therefore, Choosing f = d + completes the proof. It is important to note that in the presence of stochastic state-disturbance it cannot guaranteed that an agent can achieve any given goal orientation. In fact, the steady-state orientation of any agent would be opposite to the wind direction with small deviations because of uncertain state disturbance. This is true because at goal location, F i = 0 and hence, F p i is along the opposite direction of wind.

IV. SIMULATIONS
We consider two scenarios involving N = 20 agents which are assigned to move towards goal locations while avoiding collisions. The goal locations are selected sufficiently far apart so that the agents' communication regions do not overlap when agents lie on their goal locations. The covariance matrix of the state disturbance is taken as P w = diag(0.01, 0.01) and measurement noise as P vi = diag(0.01, 0.01, 0.01). In the first case, we assume the mean wind speed to be constant with time, withw = −0.2 0.7 T (m/sec). With these uncertainties, we have  Figures 3 and 4 respectively show the minimum distance between any pair of agents and the final distances of agents from their respective goal locations. It can be seen that the agents reach the f ball around their respective goals, while maintaining the d m distance between each other. Figure 5 shows that agents align themselves opposite to the wind direction in the equilibrium. Figure 6 shows the initial,   In the second case, we assume the mean wind speed to be time varying withw x (t),w y (t) ∈ [−1, 1] (m/sec). Similar to the first case, plots are given to show the performance of the coordination protocol in presence of time-varying wind disturbance. Figure 7 and 8 depict the minimum pairwise distances between the agents and their final distance from their goal locations, respectively.

V. CONCLUSIONS AND FUTURE WORK
We presented a safe semi-cooperative multi-agent coordination protocol under state and measurement uncertainty.  The nominal case of our earlier work is redesigned by feedforward control, vector-field-based feedback control, and nonlinear estimation techniques, so that safety and convergence of the agents up to some bound around the desired destination is guaranteed. In the future, we would like to study the case when the mean state disturbance has a spatial distribution. Ongoing work focuses on treating the case of input-and state-constrained agents under uncertainties, with application to fixed-wing aircraft operating in obstacle environments.