{'fraction_non_alphanumeric': 0.04531584460536503, 'fraction_numerical': 0.011021542105023456, 'mean_word_length': 4.12080223880597, 'pattern_counts': {'":': 0, '<': 1, '<?xml version=': 0, '>': 0, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 14, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
Optimization-based control for Multi-Agent deployment via dynamic Voronoi partition

This paper presents a novel decentralized control law for the Voronoi-based deployment of a Multi-Agent dynamical system. At each time instant, a bounded convex polyhedral working region is partitioned using a Voronoi algorithm providing the agents with non-overlapping functioning zones. The agents’ deployment objective is to drive the entire system into a stable static configuration which corresponds to a stationary maximal coverage. This goal is achieved by using local stabilizing feedback control ensuring the convergence of each agent towards a centroid of its associated functioning zone. The proposed approach considers the Chebyshev center as centroidal point of each Voronoi cell.


INTRODUCTION
Set-theoretic methods are widely employed in many research fields of modern automation, exploring the regulation problem in a geometry-based optimization context and, thus, providing efficient tools Blanchini and Miani (2007), Kontouras et al. (2015), Prodan (2012). Recent results have been reported on the application of set-theoretic methods for Multi-Agent system (MAS) control, related to consensus Barthélemy and Janowitz (1991), collision avoidance Khatib (1986), Nguyen et al. (2016a) formation safety due to the exclusion of the faulty agent or the admission of new/recovered agents Nguyen et al. (2015), Rosich et al. (2014) etc. The MAS formation can have a polyhedral description Prodan (2012) or an implicit setbased form where the inter-distance between the agents is constant Nersesov et al. (2010), Rucco et al. (2015).
In a wide range of MAS applications, such as environmental/meteorological monitoring, surveillance/rescue operations Murray (2007), Tanner et al. (2007), Bullo et al. (2009), Cortés et al., the common principle is to let a group of cooperative mobile agents (UAV, AUV, vehicles...) deploy in a predetermined target region. The main objective of such cooperative task is to approach a maximal coverage subject to constraints like minimum energy consumption Song et al. (2014), Schwager et al. (2009), environmental disturbance Bakolas and Tsiotras (2010), Bakolas and Tsiotras (2013) or collision avoidance Tanner (2004), Nguyen and Stoica Maniu (2016). Such optimal coverage is considered as a stable static configuration for MAS, however it cannot be determined beforehand in the context of MAS deployment. There are various works mentioned in the control literature employing dynamic Voronoi partition (Voronoï (1908)) based deployment as a conventional mathematical tool to approach a stationary configuration over a deployed bounded region. Notice that the partition is built on the agents current position thus is time-varying due to the agents evolution. In this context, the primer objective of the global system is to obtain a static configuration where each agent's state coincides with an inner (central) target point. Many recent research works focus on driving the MAS into a Centroidal Voronoi Configuration (CVC) in which the position of each agent coincides with the center of mass of its associated Voronoi cell 1 Cortes et al. (2002), Kwok and Martinez (2010), Yan and Mostofi (2012), Song et al. (2014). Moarref and Rodrigues (2014) proposes an optimal decentralized control to deal with energy-efficient constraints. The main results are developed for continuous-time systems, while a discrete-time version is developed by Nguyen et al. (2016b). The main difficulty is related to the computation of the center of mass. To overcome this problem, other types of target center are then studied. Nguyen and Stoica Maniu (2016) considered a so-called vertex interpolated center as the local equilibrium target for each agent.
In this paper, we propose a new approach for the dynamic deployment problem that leads to a configuration which is not fixed a priori and which verifies the coverage constraints imposed by the time-varying Voronoi partition. The proposed procedure considers the Chebyshev center as the target point. Its advantage is that the Chebyshev center can be expressed in geometric terms with respect to its associated Voronoi cell, leading to decrease the complexity compared to the conventional methods based on the center of mass.
The outline of the paper is as follows. Section 2 formulates the problem and recalls the necessary theoretical background. A new approach for the MAS deployment stability based on the Chebyshev center computation is proposed in Section 3. Numerical simulation results are illustrated in Section 4, followed by concluding remarks in Section 5.
Notation. In the sequel, R + denotes the set of the positive real numbers. The set R [a,b) ⊂ R is defined as R [a,b) = {q ∈ R|a ≤ q < b}. We use B(x, r) to denote a ball centered at x ∈ R n , with the radius r ∈ R + . Let ||x||= √ x x denote the Euclidean norm of the vector x and additionally ||x|| 2 Q = x Qx. The notation Q 0 means that Q is a semi-positive definite matrix. Denote by V the Voronoi partition of a considered Euclidean working space into n cells V i , with i = 1, . . . , n and V = n i=1 V i , with V i the corresponding Voronoi cell of the i th agent. The notation N is used for the set {1, 2, . . . , N }. The set N i contains the neighbors' indices of the i th agent. The Minkowski sum of two sets A and B is defined by A⊕B = {a+b|a ∈ A, b ∈ B}. The identity matrix of size n × n is denoted by I n .

PROBLEM FORMULATION
In the sequel, firstly some necessary assumptions will be given. Secondly, we describe the general steps of the proposed decentralized control strategy based on the real time partition of the functioning space.

System description
Consider the Multi-Agent System (denoted by Σ) composed of N subsystems fully characterized by state vectors x i ∈ R n , with i ∈ N = {1, . . . , N }. Each agent has its own discrete-time linear time-invariant dynamics with the control signal u i ∈ R m , the observed output y i ∈ R p , with p ≤ n. The matrices A i , B i and C i have the appropriate dimensions, with (A i , B i ) controllable and (C i , A i ) observable. Next, X (k) = (x 1 (k), . . . , x N (k)) denotes the tuple containing the agents states. We give below the assumptions of control feasibility associated with the MAS deployed region. Assumption 1. The agents are sharing a common working space which corresponds to the output of each individual agent output. It is assumed that for any output vector y e i ∈ R p there exists a corresponding pair (x e i , u e i ) such that (x e i , u e i ) is an equilibrium point of (1) with y e i = C i x e i . Remark 1. Notice that Assumption 1 can be satisfied whenever the mapping y e i = C i (I n − A i ) −1 B i u e i is wellposed and surjective, which implies m ≥ p and the matrix A i without poles at 1. However, the last condition is not necessary and the Assumption 1 should be considered in the general sense of the statement. For example, the common working framework for MAS which builds on the dynamics (1) with the configuration A i = C i = I n falls within the framework of Assumption 1. Assumption 2. Any convex set V i ⊂ R p is controlled λcontractive Blanchini and Miani (2007) Assumption 2 ensures that the trajectories can be steered towards the interior of any given convex set in the output space. This can be relaxed but will be employed as working assumption in order to simplify the presentation.

Primary objective
The agents evolve in a common convex and bounded working space W which is a proper subset of the output space R p . This set will be considered to be polytopic and represented as the intersection of a set of half-spaces W = {y ∈ R p |Hy ≤ θ}.
The global objective is to control each agent independently such that the global position of the Multi-agent system in W converges towards a static configuration described by the tuple Y e = (y e 1 , y e 2 , . . . , y e N ). This configuration relates the agents' output y e i at the equilibrium with an associated neighborhood described by a nondegenerated set V e i ⊂ W. This collection of sets has to cover the working Additionally, the output of each agent's dynamics y e i represents a relative center with respect to its neighborhood V i . Finally, the control law will be local and efficient. The local characteristic of the control action u i (k) is understood as a feedback law with respect to the i th agent's state and the geometry of the neighborhood at the time instant k. This implies that the design cannot rely on the knowledge of the global states of the Multi-Agent system Σ nor on the communication in between the agents with respect to their respective control decisions. The efficiency of the control policy will be compared in terms of a performance cost function. It remains to provide rigorous notions for neighborhood and center in order to cast the problem into a clear mathematical framework.

Mathematical tools for dynamical MAS
We introduce next the neighborhood corresponding to an agent output y i when this agent is part of the tuple (y 1 , y 2 , . . . , y N ) ∈ W × W . . . × W. A partition of the working space V(y 1 , . . . , y N ) needs to be computed, by decomposing W into a union of sets whose interior do not overlap A mathematical definition of such a decomposition is provided by the Voronoi partition, which characterizes the neighborhood V i (y i ) such as (3) From this definition, it follows that y i − y ≤ y j − y and subsequently 2(y j − y i ) y ≤ y j 2 − y i 2 . Thus, we can rewrite It is worth to notice that the agents Voronoi cells of such partition V(y 1 , . . . , y N ) have to be constructed in a centralized manner. But according to Assumption 3, an agent can derive its immediate own Voronoi cell by locating its closest neighbors. Assumption 3. The agents are assumed to be equipped with sensors that allow them to determine their immediate neighbors and are thus able to build their own Voronoi cell.
Additionally, each set V i is a polytope as a consequence of the boundedness of W and the structure of the constraints in (3). Using the available output measurement of the Multi-Agent system Σ (which satisfies the assumption that y i (k) ∈ W) at the time instant k, the geometric formulation (2) leads to a time-varying partition The cardinality (i.e. the number of the agents) remains constant in (2), as well as the structure of constraints in (4), and thus each point is associated to a set called neighborhood within the partition y i (k) ↔ V i (k). According to the agents evolution, the sets of neighborhood are clearly time-varying.
With these elements, the first objective of the problem formulation becomes obvious: drive the global Multi-Agent system Σ towards a static configuration by ensuring the convergence of each agent iteratively towards the central point inside its Voronoi cell. The basic idea of the present work builds on the well-established notions of Chebyshev center and radius which are presented in Definition 1. m] . The Chebyshev centerx of V is defined as the center of the largest ball/sphere The values of (x, r) are obtained by solving (5) ( There is also a computational reason related to the description of the Chebyshev centerȳ i (k) in terms of the constraints defining V i (k) available via a fixed-structure convex optimization problem. Using the description of the Voronoi cell V i in equation (4), we can derive the following local optimization problem to find its Chebysev center y i (k) and radiusr i (ȳ i (k),r i (k)) = arg max yi(k),ri(k)r i s.t.: 2(y j (k) − y i (k)) ȳ i (k) + 2||y j (k) − y i (k)||r i (k) ≤ ||y j (k)|| 2 −||y i (k)|| 2 , ∀j = i (6) This optimization can ultimately be reduced to the constraints related to the neighboring agents and thus allowing a local (decentralized) decision making for the control synthesis problem solved locally (as described in the next sections). When the Voronoi partition is a timevarying configuration, the corresponding Chebyshev center exhibits an implicit dynamical behavior.

MAIN RESULT
In this section, we propose a basic control solution for the Multi-Agent system deployment, based on the Chebyshev radius tracking and further give the proof of convergence towards a static Chebysehv configuration.
To simplify the presentation of the basic solution, in this section we consider A i = C i = I n , with i ∈ N which satisfy Assumption 1 and meaning that the working environment is the agents' state-space (e.g. position-velocity space).

Chebyshev radius tracking
For each agent x i , we define a set R i ⊂ R + which collects the distance from the agent's state x i to the hyperplanes forming its Voronoi cell Obviously, R i is also time-varying whenever x i (k) or V i (k) is time-varying.
In the general case, the distance from the agent state x i to a hyperplane is half of the distance between the positions of this agent and of the agent in its neighbor sharing this hyperplane. We can define the finite set of distance R i Let us define the distance from the agent state x i to the closest and the farthest hyperplanes The following expressions depending explicitly on time are derived r m i (k) ≤r i (k) ≤ r M i (k) (10) withr i (k) the radius of the Chebyshev ball.
The distance notations are illustrated in the Example 1.
Example 1. Consider four agents deployed within a bounded working space W, as illustrated in Fig. 1. The blue points are the agents states x i and the red points are their Chebyshev centersx i . The dash lines denote the distance r i from the agent state x i to the facets of its Voronoi cell V i . The Chebyshev radiusr i , the minimal distance to a frontier r m i and the maximal distance to a frontier r M i are also indicated. Furthermore, each agent's control law will be defined as u i (k) = K i (x i (k), x i (k)) and, in particular, privilege the linear form u i (k) = K i (x i (k) −x i (k)). It can be noticed that the control signal is time-varying by the dependence on the Chebyshev center.
The definitions of a Static Configuration and also a Chebyshev Configuration of Multi-Agent systems is further introduced in order to describe the limit behavior. Definition 2. A Static Configuration (SC) of the MAS Σ is achieved whenever u i (k) = 0 and x i (k) = x i (k 0 ), ∀k ≥ k 0 .

Definition 3. A Chebyshev Configuration (CC) of the Multi-Agent system is achieved when the agents positions coincide with their corresponding Chebyshev centers
x i =x i . Remark 2. Not any SC is CC as it can be observed by choosing the null input u i = 0 for a configuration where x i =x i . Conversely, a CC is not necessary a SC for the homogeneous agents with u 1 = u 2 = . . . = u N = 0. Proposition 1. The Multi-Agent system Σ in closed-loop with a set of decentralized control laws u i = K i (x i (k)−x i ) achieves a Satic Configuration if and only if this is a Chebyshev Configuration.
Proof. First we observe that for x i (k) =x i (k) the control action is u i (k) = 0 and thus it characterizes an equilibrium for the specific case A i = C i = I n . Conversely, if x i (k) = x i (k) based on the controllability assumption, the control action u i (k) = 0 and x i (k + 1) = x i (k), thus invalidating the assumption of static configuration.
We analyze next the time-varying configuration and the convergence towards a so-called Chebyshev Static Configuration (CSC) which mixes the CS and CC notions. Remark 3. Note that a CSC is not unique and depends on the initial agent state and implicitly on the control policies applied on the agents (feedback gain).
The convergence of MAS deserves a particular attention as long as the ultimate SC is not known a priori.

Convergence proof
Consider the following semi-positive function From the first part of the inequality in (10), it follows that each term of the sum in (11) is positive and globally V (X (k)) ≥ 0. Another structural property inherited from the definition of the Chebyshev radius is resumed by Proposition 2. Proposition 2. If the Multi-Agent system Σ achieves a static configuration over the working space W and additionally if V (X (k)) = 0, then the achieved configuration is a static Chebyshev configuration.
Proof. The configuration at equilibrium is characterized by x i (k) =x i (k) and u i (k) =ū i (k) which is equivalent tō r i (k) = r m i (k), and by the positivity of r m i (k) and (11), this leads to V (X (k)) = 0.
The convergence of Σ towards a stationary configuration is analyzed on the basis of the value function (11). The approach is based on the monotonic decrease (or at least non-increase) of V (X (k)) along the trajectories of Σ.
The monotonicity of V (X (t)) is not straightforward by analyzing equation (12) but it is possible to study its behaviour over a longer horizon. Extending the differences over N p time steps forward yields . . .
Summing up these equations, we obtain Lemma 1. The sum i∈N (r i (k + N p ) −r i (k)) is upper bounded by N · γ(W), with γ(W) denoting the radius of the largest ball enclosed in W.
Proof. One has 0 ≤r i ≤ γ(W). The upper bound γ(W) is obvious from the boundedness assumptions on W. The lower bound is derived by considering the worst case where all agents' positions are superposed, leading to r m i = 0. Hence summing up the N agents Chebyshev radius yields 0 ≤ i∈Nr i ≤ N · γ(W) and finally i∈N (r i (k + N p ) − r i (k)) ≤ N · γ(W). Proposition 3. For each agent i ∈ N , lim j→∞ θ i (k + j) = 0.
Proof. Lemma 1 ensures the boundedness of the first term in (14). Consider the remaining term which depends uniquely on the distance between the agents. The limit lim j→∞ V (X (k + j)) − V (X (k)) is bounded if and only if the limit lim j→∞ k+j t=k i∈N θ i (t) exists and it is bounded. Recall that θ i (k) ≤ 0 and thus the existence of the bounded limit is related to the convergence of i∈N θ i → 0. Equivalently the sum i∈N r m i becomes stationary, according to the theory of series (see Brabenec (2004)), otherwise the convergence is not guaranteed. Corollary 1. If the Chebyshev center associated to each Voronoi cell is unique, the MAS converges to a CSC.
Proof. Proposition 3 proves the convergence of r m i (k) towardsr i which ultimately leads to u i (k) = 0 if the Chebyshev center is uniquely associated to the Chebyshev radiusr i . Thus in the limit case, r m i =r i corresponds to a CSC.
The following example is used to illustrate this analysis.
In conclusion, this section proves that local control laws can be designed to decrease the distance between the minimal distance r m i and the Chebyshev radius and globally to drive the Multi-Agent system Σ towards a static configuration whenever the Chebyshev center is unique. The convergence proof enforces the decrease of the difference between these distances.

NUMERICAL ILLUSTRATIONS
A numerical simulation is given in this section to illustrate the deployment performance of a Multi-Agent system over a bounded region W by using the Chebyshev Static Configuration solution proposed in Section 3.
Consider a Multi-Agent system composed by N = 4 agents, with the discretized dynamics equation where x i ∈ R 2 and u i ∈ R 2 refer respectively to the agent position and velocity. The sampling period is T s = 0.1. This choice of agents dynamics (15) satisfies both Assumptions 1 and 2, the steady-state ensures that every point in R 2 can be an equilibrium point of (15) if the agent's velocity at this point is null.
The main objective is to drive the agents towards a Chebyshev Static Configuration.
The agents decentralized control has the affine/linear feedback form as u i (k) = K i (x i (k) −x i (k)), withx i (k) denoting here the Chebyshev center. The control gain K i is derived via a pole placement technique (the stable poles are 0.2 and 0.5). The Chebyshev centerx i (k) associated to the Voronoi cell V i (k) is determined by solving (6). The deployment result is shown in Fig. 3. We use the green and blue points to denote respectively the agents initial positions x i (0) and their evolution. The Chebyshev centers x i have their trajectories described by the red points. The deployment result and the tracking error x i (k) −x i (k) will be illustrated. We show the value of x i (0) directly in the figures and also the static Voronoi configuration. The center tracking errors x i (k) −x i (k) and the radius tracking errorsr i (k) − r m i (k) are plotted in Figs. 4-5. As result, the tracking errors go asymptotically to zero and thus the Multi-Agent system approaches a stable CSC. It is worth to be mentioned that the tracking error of each agent is not monotonically decreasing. Although the feedback gains are tuned to track the Chebyshev center with monotonic behavior, the time-varying characteristic of the center leads to a global non-monotonic tracking convergence.

CONCLUSION
This paper provides a novel control strategy in the Multi-Agent deployment. The ultimate goal is to drive the agents into a static configuration over a bounded region. This goal is obtained in a decentralized manner by ensuring the convergence of each agent towards a target point inside its functioning zone. The zones are described based on the Voronoi tessellation of the working region. Then the Chebyshev center is used as time-varying target point.
However, it should be noticed that Corollary 1 assumes the uniqueness of the Chebyshev center. Whenever the Chebyshev center computation is not unique, the convergence is not anymore guaranteed. Oscillations may appear, for exemple. In order to keep driving the agents into a stable static configuration, future work will investigate the computation of a general center which leads to a unique center by recursive deflation in the degenerate cases.
In this work, the control design is based on the assumption that the entire working region is controlled invariant with respect to the agent dynamics. For some dynamics, this requirement might be overrestrictive. This point will be discussed in the future work.