Swarm Abstractions for Distributed Estimation and Control

(1)

Summary

Swarm of vehicles, instead of single or small groups of vehicles, are becoming of large interest in a variety of applications for their in-trinsic robustness and exibility. Probably, the most dicult issue is coordination and control of a large number of small vehicles with limited processing, communication and power capabilities. A large number of solutions for practical problems have been studied and proposed by researchers worldwide; they are often specic solutions to specic problems that are dicult to generalize. Most of them cannot manage the natural heterogeneity of a large group of vehicles: it is often desired that a swarm performs a complex mission in dif-ferent phases that may require dierent specialized vehicles instead of a multi role one.

The aim of this thesis is to develop a framework for swarm model-ing, decentralized estimation and control capable of managing many of the the application elds proposed and studied in the literature. The environment and mission(s) under consideration are as general as possible, as well as the characteristics of the agents which may be all identical or heterogeneous.

The Descriptor Functions Framework, the main topic and contri-bution of this thesis, associates a specic function to each agent, and one or more functions to the mission and uses an analytical framework for generation of the agents control law. Decentralized control and estimation of the relevant variables needed as feedback are cast into an optimization problem; analysis of equilibria and formal proof of convergence of the estimation and control law proposed are derived. Then, a bio-inspired method for task self-assignment is applied to the Framework; swarm vehicles are given the capability to select the best task to perform, swap task with other agents during the mission, and assess the degree of completeness of the various tasks in order to balance the swarm capabilities among them. Finally an hardware test bed, together with experimental results, is be presented.

(2)

(3)

I Descriptor Functions Framework

25

2 Motivations 27 2.1 Related Work . . . 29

(4)

3 Modeling 33

3.1 Nomenclature and Denitions . . . 35

3.2 Agent Descriptor Functions . . . 36

3.3 Current Task Descriptor Functions . . . 37

3.4 Desired Task Descriptor Functions . . . 38

3.4.1 Uniform Deployment . . . 38

3.4.2 Static Coverage . . . 39

3.4.3 Eective Coverage . . . 40

3.4.4 Dynamic Coverage . . . 41

3.4.5 Target Assignment . . . 42

3.5 Task Error Function . . . 43

3.5.1 The absolute Task Error Function . . . 43

3.5.2 The relative Task Error Function . . . 44

4 Control 45 4.1 Swarm Deployment as an Optimization Problem . . . 46

4.1.1 Gradient Control . . . 47

4.1.2 Choice of the Cost Function . . . 49

4.1.3 Numerical Approximation of the Control Law 62 4.2 Simulation Results . . . 69 4.2.1 Uniform Deployment . . . 69 4.2.2 Eective Coverage . . . 77 4.2.3 Dynamic Coverage . . . 84 4.2.4 Target Assignment . . . 90 5 Estimation 107 5.1 Decentralized estimation of the current TDF . . . 109

5.1.1 Stability and Convergence Analysis . . . 111

5.2 Estimation of the Agents DFs Parameters . . . 122

5.3 Simulation Results . . . 125

5.3.1 Estimation of the TDF . . . 125

5.3.2 Estimation of the agents DFs parameters . . . 132

(5)

6 Multi-resolution Modeling 141

6.1 Function Approximation using RBFs . . . 143

6.2 Supervised Learning . . . 144

6.2.1 Decentralized Supervised Learning . . . 146

6.3.1 Centralized Supervised Learning . . . 148

6.3.2 Decentralized Supervised Learning . . . 149

6.4 Conclusions . . . 153

7 Management of multiple tasks 155 7.1 Task Selection using Response Thresholds . . . 157

7.1.1 Response Thresholds . . . 158

7.1.2 Stimuli Signals Update . . . 160

II Hardware Testbed

169

8 Hardware Testbed 171 8.1 Swarm Control Test-bed . . . 172

8.1.1 Selection of the RC Car and Modications . . 173

8.1.2 Test-bed Agent Kinematics and Control . . . 176

8.1.3 Synchronization and Communications . . . 179

8.1.4 Simulation Results . . . 180

8.1.5 The Virtual Ideal Agent Concept . . . 184

8.1.6 Experimental Results . . . 189

8.2 Human Swarm Interface . . . 189

8.2.1 Generation of Formation Statistics . . . 193

8.2.2 Pilot Input and Graphical Display . . . 195

8.2.3 Simulations and Experimental Results . . . . 200

A Consensus Protocols 203 A.1 Dynamic Average Consensus Protocols . . . 207

(6)

(7)

Chapter

1

Introduction

Control of swarms of vehicles has received a lot of attention from the scientic community for their theoretical challenges and poten-tial use. The concept of swarm has a number of advantages in many applications due to the decentralized nature, and the capability of performing missions not possible for single large vehicles. One of the most dicult problem in swarm control is the design of a manage-ment structure general enough to accommodate vehicles with dier-ent properties, with limited information exchange, which move in an adverse environment to achieve the same objective. The problem under consideration here consists of a number of agents, which are heterogeneous in terms of size, payload capability, and able to per-form dierent tasks. A high level controller should (loosely speaking) optimize the dynamics of the swarm (i.e. position and velocity), its shape, dimension(s), and motion with respect to the objectives of the mission, within a scenario characterized by the absence-presence of a mission operator. The dynamics of a single agent must be a combination of mathematical tractability and essential physical re-ality. There are several methods, and strategies that can be used in order to address the above problem; one of the most promising is the set of knowledge tools derived from biology (especially bird

(8)

Chapter 1. Introduction

ocking, sh schooling, insect foraging techniques, predator hunting, boids, etc.) [39], [4]. Often the leader/follower structure is used, and in many instances, [23], the dierent characteristics among agents of a swarm may congure them as leaders or followers.

This structure can be used for establishing formation geometries op-timized for performance and objectives of the mission. In addition, a leader/follower structure appears to be appropriate for separating agents according to their task and/or capabilities.

Flocking and schooling motions can also provide insights and algo-rithms for implementation of the relative motion with respect to ob-stacles, [56].

Topological geometry, algebraic graph theory, consensus estimation, decentralized control and optimization of sensor networks are some of the methods used primarily for management of swarm communi-cations networking issues [44], [21], [61], [57].

Still, one of the limitations, and open area of research found from literature, is the absence of a structured relationship between the general swarm control problem, and its connection to actual mission and tasks objectives.

Path planning and task assignment problems, have been traditionally studied, in reference to standard UAVs (single, multiple), but not so much with respect to miniature vehicles and swarms [7]. Early re-search in autonomous cooperative multi vehicle control addressed the problem from a global optimization point of view, which is certainly the most attractive avenue, and for which there is a large amount of literature [35], [67].

However, the generality of the problem, the variety of scenarios, the number of tasks and vehicle's constraints make global optimality un-feasible except for very simple applications. The type of vehicle (size, shape, performance), the payload (processing unit, sensors, commu-nications suites), the number of agents (swarm, many, single) are in fact very dependent on the type of mission, so that a unied theory is not available yet.

(9)

1.1 Literature Review

The problem of control and management of a swarm of vehicles, or a distributed allocation of resources over an unknown environment has been addressed in the past using dierent tools, depending on the driving application, and the mathematical background. The fol-lowing paragraphs give a brief summary of the current state of the art.

1.1.1 Behavioral Approaches

One of the most attractive areas of research in the eld of swarms, agents, and their general interrelated behavior is the understanding and development of tools inspired by biology (especially bird ock-ing, sh schoolock-ing, foraging techniques, predator huntock-ing, boids, etc.). Reynolds's work [12] is perhaps the most widely known attempt to devise a simulation environment that describes ocking and school-ing. It is based on particle motion dynamics and a set of rules to be followed by each particle (in particular collision avoidance with neigh-bors and obstacles, same velocity of close by particles, and attraction to the center of the swarm). References [12] and [44] are among the rst results in relating the motion of animal swarms with formal optimization techniques. In [46] the authors provide some formal def-initions and relationships to describe animal and bacterial foraging, and their potential use in engineering applications such as unmanned aerial and ground vehicles search missions, and more generally task assignment problems. Dierent foraging strategies are catalogued, and associated with gradient and non gradient based optimization algorithms. Reference [45] establishes a bridge between behavioral swarms, and more traditional system theory properties, such as sta-bility, and global convergence to computable equilibrium points. A theoretical framework for design and analysis of distributed ock-ing algorithms is presented in [56], while Tanner and coworkers, [65] and [66], associate ocking behavior to xed and dynamic

(10)

topolo-Chapter 1. Introduction

gies, in order to take advantage of the tools of graph theory for the modeling of splitting and recomposing of swarms. One of the rst applications of ocking in migratory birds is found in [23]. Social and greedy behaviors shown by geese and storks are used to develop formation control algorithms, and to extend the principle of virtual leader, to the new concept of formation geometry leader. Biomimicry techniques are presented in [63], where the problems of obstacle avoid-ance, and swarm consensus are solved using articial potential based controllers. An interesting example is found in [25], where the au-thors present simple, yet useful, modeling of moth swarming behavior during mating. Another analysis of swarm intelligence can be found in the work described in [4]. Although wider in scope, the book by Bonabeau and coworkers concentrates on the understanding, and algorithmic implementation of "social behaviors" shown by several species of insects. In particular, the concept of stigmergy is described in detail. Stigmergy is dened as a set of indirect interactions, which modies the behavior of a colony member, due to changes (to the environment) caused by other members.

1.1.2 Consensus Protocols

The consensus protocol is an algorithm that formalizes what we call the "agreement" on a set of shared variables, and has been widely used to estimate some properties or data that has to be common to the entire swarm. The asymptotic convergence of typical consensus protocol is reached using local communications only; thus the algo-rithm is decentralized in nature.

Consensus problems have a long history in computer science and sta-tistical analysis forming the core of the so-called distributed comput-ing, [43], [17]. A consensus theoretical framework was introduced by Olfati-Saber and coworkers in [51], with a correlation to graph the-ory and graph topology. In this context, asymptotic convergence to a single equilibrium condition is achieved for static as well as dynamic topologies, provided that some connectivity conditions on the

(11)

under-Chapter 1. Introduction

lying graphs are satised. These conditions in fact have a motivation in Laplacian matrix theory and their spectral properties. One of the most appealing aspects of consensus is that the variable or variables that should reach a common steady state value can be motion related (position, velocity), or representative of any other physical or system property (temperature, voltage, density, sociological behavior, etc.). This makes the methodology applicable not only to the control of mo-tion of vehicles, but also to many "non vehicle oriented" problems. Information and sensor networks and communications networks are typical application elds of the examples found in the literature. A comprehensive treatment of consensus can be found in the text by Ren and Beard [61].

1.1.3 Coverage and Connectivity

Coverage control deals, in a general sense, with the optimal distribu-tion of a large amount of resources over the environment of interest. These resources can be robots, sensor networks, diversied assets, all characterized by a decentralized and distributed evolution. In cov-erage approaches, the focus is on the use of tools such as proximity graphs (Voronoi diagrams, Delaunay tessellations, etc) to determine the best distribution of resources for a given task. Given a coordi-nation task to be performed by the network as well as a proximity graph representing communication constraints, gradient ows can be used. Other approaches use the notion of neighboring agents, and an interaction law between them is found in [36]. Another method is based on optimizing local objective functions to achieve the desired global task [16]. Graphs can model local interactions among agents, when individual agents are constrained by limited knowledge of oth-ers. The whole purpose of a coordinated coverage by a multi-agent system is to evolve towards the fulllment of a global objective. This typically requires the minimization (or maximization) of a cost asso-ciated with each global conguration. References [49] and [37] show some optimal coverage applications when the global objective is a

(12)

function of the graphical abstraction of the formation, instead of the full conguration space of the system.

1.1.4 Abstractions and Models

The use of mathematical and physical abstractions is an appealing concept in swarm control management. One useful application of mathematical abstractions is the identication of a limited number of variables as a way of reducing the swarm shape to a "small" manage-able set from the computation standpoint, as well as from the point of maintaining sucient capability of management. The literature presents several approaches that use this idea. In [3], the concepts of center of mass and moments of inertia are used as consensus variables for shaping the geometry of a swarm of homogeneous agents. Refer-ence [52] describes the problem of pattern generation in obstacle-lled environments by a swarm of mobile robots. Decentralized controllers are devised by using the Smoothed Particle Hydrodynamics (SPH) method, where the swarm is modeled as an incompressible uid sub-jected to external forces. In reference [38], starting from deployment and target tracking applications, the authors develop a controller that tries to minimize the dierence between an optimal location (or tar-get location) density and the density of the agents in the scenario. The density function described in [38] is the actual number of agents per unit of volume (or area). The main concept is based on the as-sumptions that for two comparably sized regions, more agents should deploy in the one with the higher number of targets.

(13)

1.2 A Case Study: Formation Statistics

This section presents an example of application of swarm abstractions to the control of large swarms of vehicles as case study. Formation statistics, originally introduced in [57], are dened in analogy with physical bodies: center of mass position and inertia moments. The formation statistics represent a set of abstract swarm variables that encode the shape and the position of the swarm. This approach dis-regards agents positions as long as the swarm has the desired shape and employs rst and second order moments computed on the posi-tion of all the vehicles. The main advantage of this technique is the capability to represent shape and position of an entire swarm using a very limited number of variables regardless of the number of agents. A set of desired formation statistics are used to drive the swarm to the desired pose and orientation. Dening formation statistics is a non trivial task, thus a technique for easy computation of formation statistics is given. Each agent elaborates its own estimate of these variables using a dynamic consensus algorithm and uses a gradient descent algorithm to move so that the formation statistics equal the desired ones.

Dierently from its original formulation, a consensus algorithm ca-pable of tracking a ramp reference is used here, in order to reduce tracking errors. Collisions between agents and with obstacles were not considered so far. Thus, gyroscopic and damping terms are added to the control law in order to avoid collisions between vehicles and with obstacles. The proposed decentralized control law curves the ve-hicle trajectory when the veve-hicle gets near to an obstacle or another vehicle; an additional braking term is employed to reduce vehicle ve-locity inversely proportional to the obstacle distance. The obstacle avoidance terms appear in the control law only in the presence of obstacles or nearby vehicles. This behavior was modeled as a hybrid system and proof of stability is given, under mild conditions, using the Common-Lyapunov functions approach.

(14)

1.2.1 Problem Statement

In the following sections a decentralized control scheme for a swarm of vehicles capable of achieving desired formation statistics and of avoiding obstacles and collisions within the swarm itself is proposed. The swarm is composed of n agents with positions p1, ..., pn. Each

agent's position vector has the dimensionality of the motion space under consideration; in this work planar motion is assumed, thus the i-th vehicle position is: pi = [pix piy]T ∈ <m.

The swarm statistics are dened via the formation statistics abstrac-tion based approach, see [57], which employs the inertia moments of the swarm as shape variables to be tracked by the control system. The statistics are represented by the swarm moment vector f(p) ∈ <l

, which uses a C2 vector moment generating function φ : <m → <l:

f (p) = 1 n n X i=1 φ(pi) (1.1)

Each agent is modeled by a double integrator. It knows the desired swarm moment vector, represented by the vector f∗ _{∈ Im(f), and}

measures its position and velocity. The agent's control input is vehi-cle acceleration. The communication network, over which the vehivehi-cles may exchange information, is assumed to be distance dependent, i.e. each agent can communicate with its neighbors only if the relative distance is less than some specied communication radius. This is one of the most commonly used model for describing time-varying topologies in mobile sensor networks, and accomplishes quite well with the mode of operation of commercial wireless radio modems. In order to achieve the goal, each vehicle must estimate the current swarm statistics. This is achieved using a dynamic consensus algo-rithm, see Appendix A, capable of tracking the mean values of the vector moments of all the agents, under the assumption that the net-works is connected and undirected. Collisions between obstacles and other agents will be taken into account using a gyroscopic correction term and appropriate braking forces [62] and [19].

(15)

1.2.2 Moment Statistics

The moments of a set of unit mass points in a plane are dened as:

Mab = 1 n n X i=1 pa_ixpb_iy, a, b≥ 0

where a + b is the order of the moment. Even if a large number of moments can provide an exact formation description, we are inter-ested in lower order moments through which we specify a family of formations. We will focus on rst and second order moments, since they give the minimum number of statistics sucient for specifying pose, orientation and shape of the swarm. Under this assumption, the vector moment generating function is:

φ(pi) = [pix piy p2ix pixpiy p2iy]T (1.2)

and the formation statistics are:

µx = 1_n Pn i=1pix µy = 1_n Pn i=1piy M2x = _n1 Pn i=1p 2 ix M2y = _n1 Pn i=1p 2 iy Mxy = _n1 Pn i=1pixpiy (1.3)

The rst-order moments µx and µy specify the pose of the swarm,

i.e. the center of mass. Through Mxy it is possible to dene the

orientation as the rotation of the reference frame centered in the center of mass for which the formation satises:

n

X

i=1

xrel_i y_irel = 0 (1.4) where the relative variables are computed as:

[xrel_i yrel_i ]T = RT(pi− µ). (1.5) θ = 1 2atan 2Pn_i=1(pix− µx)(piy− µy) Pn i=1(pix− µx)2− (piy− µy)2 (1.6)

(16)

where θ is restricted to be between [−π

2,

π

2], and µ = [µx, µy]

T.

Thus, using this set of 5 swarm statistics, it is possible, to some ex-tent, to dene the desired position and shape of the swarm. The choice of a suitable value for the rst order moments, given the de-sired position of the center of the swarm on a map, is straightforward; selection of second order moments in order to obtain a swarm of the desired size and elliptical shape is much more dicult: in partic-ular it must be noted that, given a certain distribution of agents

pi, i ∈ [1 · · · n], second order moments change when the swarm is

subject to a rigid translation ˜pi = pi + δ, i.e. a change in the rst

order moments from µx and µy to µx+ δx and µy + δy. This means

that, when the swarm moves in the plane, it changes its second order moments, even without changing its actual shape.

The shape of the swarm is assumed to be independent from its pose; geometric considerations can be made using relative second-order mo-ments: a1 = _n1 Pn i=1(xreli )2 a2 = 1_n Pn i=1(y rel i )2 (1.7) These relative abstract variables provide a bound for the region oc-cupied by the agents, as derived in [3]:

|xrel

i | ≤ √na1

|yrel

i | ≤ √na2 (1.8)

It is then possible to determine a spanning rectangle, centered in µ, and with sides given by 2√na1 and 2√na2.

These measures are expressed in the relative frame. Therefore, using the equivalence in eq.(1.5) a convenient expression for calculating inertia moments has been derived:

M2x = 1₂(2µ2x+ a1+ a2+ (a1− a2) cos 2θ)

M2y = 1₂(2µ2y + a1+ a2− (a1− a2) cos 2θ)

Mxy = (µxµy+ (a1− a2) sin θ cos θ)

(17)

From eq.(1.9) we can come back to the relative shape variables using the following: θ = 1 2atan2 (M2x− µ2x− M2y+ µ2y) 2(Mxy − µxµy) (1.10) a1 = (M2x− µ2x) cos2θ + (M2y− µ2y) sin2θ +2(Mxy − µxµy) sin θ cos θ a2 = (M2x− µ2x) sin 2_{θ + (M} 2y− µ2y) cos 2_θ −2(Mxy − µxµy) sin θ cos θ

Using (1.9) is possible to obtain rigid translations by selecting (a1, a2, θ)

and deriving the corresponding second-order moments.

1.2.3 Consensus Estimation

Dynamic consensus algorithms are used to estimate the swarm cur-rent moment vector. A consensus algorithm allows the internal vari-ables of all agents to converge to a common value in a decentralized way (see Appendix A for an overview of consensus algorithms). Following [18] we distinguish between static and dynamic consensus; in the static case the consensus is achieved at the average of the initial values of all agents variables. On the other hand, a dynamic consen-sus algorithm requires an additional input variable for each agent; the problem is then to track the average of the input values with the consensus variables.

Consensus algorithms are based on the topology of the underlying communication/sensing graph. A graph is dened as a set of nodes and arcs. The adjacency matrix (A) is a n × n matrix whose ij − th entry is 1 if the edge (i, j) is included in the graph, and 0 otherwise. The diagonal degree matrix is dened as follows:

Dii=

X

j

(18)

The Laplacian matrix is dened in terms of the adjacency matrix and the diagonal degree matrix:

L = D− A.

In the following we will assume a connected and undirected graph. A static average consensus algorithm is the following:

˙xi =

X

j∈Ni

(xj− xi)

where Ni is the set of neighbors of agent i. The whole system

dy-namics can be stated using the Laplacian matrix: ˙x =−Lx

where x = [x1, ..., xn]T. The convergence of this algorithm can be

stated as follows: lim t→∞xi(t) = 1 n n X i=1 x(0)

and its proof uses properties of the Laplacian matrix of an undirected and connected graph, [18].

Tracking performance of dynamic algorithms depends on time vari-ation of the input signal z(t) = [z1(t) ... zn(t)]T. The dynamic

con-sensus algorithm proposed in [18] is capable of reaching concon-sensus equilibrium on any signal that has a steady-state value (i.e. Z(s) has all its poles in the left-half plane and at most one pole in zero). The resulting system dynamics are given by:

˙x =−Lx + ˙z (1.11) and consensus is achieved when:

lim t→∞(xi(t)− 1 n X j zj(t)) = 0.

(19)

The LTI system can be described by the MIMO transfer function matrix:

Hxz = s(sI + L)−1.

Using step references as commands to the swarm may often result in saturation of vehicle maneuvering capabilities; providing commands in terms of ramps instead of steps has several advantages; the most notable is that it reduces the actual tracking error, thus reducing the amount of control required by the decentralized autopilots, yielding better overall performance. Using a transfer function matrix of the form: Hxz = s2 (s + α)2 s2 (s + α)2I + L −1 , α > 0

it is possible to reach consensus state on ramp inputs. The Lapla-cian matrix of an undirected graph is symmetric and admits spectral decomposition: L = n X i=1 λiPi

where λi are the eigenvalues of L and Pi orthogonal projections onto

mutually orthogonal eigenspaces. For a connected graph the following conditions are satised:

1. λ1 = 0

2. P1 = 1_n11T

3. λi > 0, ∀i > 1

The input to error transfer function can be derived as:

E(s) = X(s)− 1 n11 T_Z(s)_{→ H} ez = Hxz− 1 n11 T

using the above conditions, it is possible to write Hez as:

Hez = X i>1 s2 (1 + λi)s2+ 2αλis + α2λi Pi

(20)

where all terms in the summation are stable. From the nal value theorem e(t) → 0 as t → ∞ if Z(s) is an arbitrary signal with at the most two poles in s = 0.

We can then derive the algorithm to run by each vehicle: (1 +|Ni|)¨xi = X j∈Ni ¨ xj+ 2α X j∈Ni ( ˙xj− ˙xi) + α2 X j∈Ni (xj− xi) + ¨z (1.12)

where the input signal is the vehicle's acceleration. From an imple-mentation point of view the agents now need to transmit not only the consensus variable x but also ˙x and ¨x.

The improvement in estimation is shown in Figure 1.1 and Figure 1.2 with the comparison of the maximum and minimum estimation errors of the two rst order moments (µx, µy) using the consensus

al-gorithm described in eq.(1.11) (dotted line) and eq.(1.12) (solid line). Simulations were performed using 25 vehicles with a xed communi-cation topology, where agent i is connected to agents i − 1 and i + 1 if i 6= 1, n; agents 1 and n had only one neighbor, agent 2 and n − 1 respectively. The control law used is given in eq.(1.14) and described in more detail in the next section.

The reference signal is a ramp on the center of mass position; second order moments were computed keeping a1 and a2constant, and using

eq.(1.9).

1.2.4 Control

The global control objective is dened by the minimization of a suit-able potential function, Ξ : <mn _{→ <, of the form:}

Ξ = [f (p)− f∗]TΓ[f (p)− f∗] (1.13) where Γ ∈ <l×l _{is chosen such that Ξ(p) has the unique global}

mini-mum in f(p) = f∗_.

Each agent follows the gradient of Ξ(p), and estimates the global moment vector f(p) using consensus algorithms. The applied control

(21)

Chapter 1. Introduction 5 10 15 −2 −1.5 −1 −0.5 0 0.5 1 1.5 2 2.5 time µ x estimation error Ramp inputs µ x estimation error

Figure 1.1: Ramp inputs, µx minimum and maximum estimation

error 0 5 10 15 20 −2 −1.5 −1 −0.5 0 0.5 1 1.5 2 time µ y estimation error Ramp inputs µ y estimation error

Figure 1.2: Ramp inputs, µy minimum and maximum estimation

(22)

Chapter 1. Introduction law is the following:

¨

pi =−Bip˙i− [Dφ(pi)]T∆i[Dφ(pi)] ˙pi − [Dφ(pi)]TΓ[xi− f∗] (1.14)

where the rst and second terms are damping terms and xi is the

estimate of the global moment vector f(p) done by agent i and Dφ(·) denes the l × m Jacobian matrix of φ. The second damping term is needed to prove the boundness of the involved signals and will be discarded during simulations.

The consensus algorithm proposed in [57] is: ˙

wi =−γwi+

P

j∈Ni(xj− xi)

xi = wi+ φ(pi) (1.15)

where φ(pi) is the vector moment generating function. Looking at

the derivative of x the algorithm is the same as in eq.(1.11), except for the forgetting factor γ that takes into account the events of an agent leaving the formation or joining of a new agent:

˙x = ˙w + ˙φ(p) =−γw − Lx + ˙φ(p)

where z(t) = φ(p(t)).

The closed-loop system can be described in terms of (p, ˙p, E), where

E = [e1, ... en]T is the column vector whose elements are the

esti-mate errors of each agent. In [57] a proof of the boundness of each trajectory of system described in eq.(1.14) and eq.(1.15) is provided using two Lyapunov functions, V and U, and then summing them in a convenient way:

V (p, ˙p) = ˙pT_{p + nΞ(p)}_˙

U (E) = T r(EET)

Ψ(p, ˙p, E) = V + (1 + ν)U, ν > 0

(1.16)

The derivative of Ψ is non-increasing along trajectories in time, in fact: ˙ Ψ≤ − n X i=1 [ ˙pT_i [Bi+ BTi ] ˙pi+ ν|ei|2], > 0 (1.17)

(23)

where the Bi terms had been chosen to verify [Bi+ BiT] > 0 ∀i.

1.2.5 Obstacle Avoidance

In order to avoid obstacles and collisions with other agents, gyroscopic and braking forces were added ( [62], [19]). Gyroscopic forces are used as steering forces that curve the trajectories when an obstacle is in the detection shell of the agent. Steering forces alone are generally not sucient for collision avoidance, thus braking forces terms are added when obstacles or other vehicles are in close proximity.

Each agent has its own detection shell, within which it can sense obstacles and neighboring agents. The detection shell will be part of the ball of radius rscentered at the agent position; more precisely the

area within the angles (∠ ˙pi− αs,∠ ˙pi+ αs). Reaction behaviors will

depend on rsand αs. Agents only react to the nearest obstacle within

their detection shell so, if there are no obstacle the gyroscopic and braking forces are set to zero. Gyroscopic forces are orthogonal to the velocity vector, while braking forces are damping terms acting in the opposite direction of the velocity vector. The resulting obstacle avoidance force is given by:

FOA = FG+ FB

The turning direction is chosen depending on the approach angle, i.e. the angle between the velocity vector of the agent and the vector from the agent to the nearest point of the obstacle (denoted as nva);

in order to have an escape behavior the gyroscopic force must produce an innitesimal rotation around the vector nva× ˙pi. This yields:

FG = S(nva, ˙p) ˙p

FB =−D(nva) ˙p

(24)

where the matrix D is symmetric and positive-denite, and the ma-trix S is skew-symmetric. The latter implies:

< S(nva, ˙p), ˙p >= 0 ⇒ FG p = 0˙

that is the force is orthogonal to the velocity vector. The magnitude of the braking force is selected so as to generate innite force as distance tends to zero. The structure can be therefore described by an hybrid system with three states:

• Normal (N)

• Turn Left and Brake (TLB) • Turn Right and Brake (TRB)

as shown in Figure 1.3. The control inputs for the three states are: ¨ pi =−Bip˙i+ g(pi, ˙pi, xi) (N ) ¨ pi =−Bip˙i− D ˙pi+ SLp˙i+ g(pi, ˙pi, xi) (T LB) ¨ pi =−Bip˙i− D ˙pi+ SRp˙i+ g(pi, ˙pi, xi) (T RB) (1.19)

where g(pi, ˙pi, xi) is the sum of the gradient and second damping

term of eq.(1.14). Boundness of all signals can be proved for each subsystem, as done in [57] for the Normal subsystem (eq.(1.16) and eq.(1.17) show this result). This is a necessary, but not sucient, condition for the boundness of all signals of the resulting system that is subject to arbitrary switching. The problem can be solved using the Common Lyapunov functions approach.

Recall the denition: A positive denite continuously derivable (C1₎

function V : <n_{→ < is a Common Lyapunov Function for the family}

of systems described by

˙x = fp(x), x∈ <n, p∈ P

(where P is the index set of all subsystems) if there exists a continuous positive denite function W (x) : <n_{→ < for witch is veried:}

∂V

(25)

Chapter 1. Introduction TURN LEFT + BREAK (TLB ) OBJECT TO THE RIGHT OBJECT TO THE RIGHT OBJECT TO THE LEFT NO OBJECT NO OBJECT TURN RIGHT + BREAK (TRB ) NORMAL (N)

Figure 1.3: Control system hybrid dynamics

A sucient condition for the boundness of all signals of the switched system is the existence of a Common Lyapunov Function. Finding one function for all subsystems gives us a measure of the loss of energy in a monotonic way; i.e. we can assure that, during switching, the Lyapunov function is still decreasing. From eq.(1.19) and using the properties of matrices in eq.(1.18):

D > 0 SL+ SLT = SR+ SRT = 0 (1.20)

we can see the Lyapunov function in eq.(1.16) as Common Lyapunov Function for the family of systems in eq.(1.19). The derivatives of the Lyapunov function for the three subsystems are:

˙ ΨN ≤ − n X i=1 [ ˙pT_i [Bi+ BiT] ˙pi+ ν|ei|2] =−W (p, ˙p, E) (1.21) ˙ ΨT LB = ˙ΨT RB ≤ − n X i=1 [ ˙pT_i [Bi+BiT+D+D T_{] ˙}_p i+ν|ei|2]≤ −W (p, ˙p, E) (1.22)

(26)

Chapter 1. Introduction −10 −5 0 5 10 15 20 25 −10 −5 0 5 10 15 20 25 x y

Obstacle Avoidance, 20 agents

Figure 1.4: Sample obstacle avoidance maneuver

1.2.6 Numerical Results

A simulation was performed using 20 agents with a fully connected communication topology. The objective of the simulation is to test the abstraction based approach with the added obstacle avoidance terms, rather than weighting the estimation performance. The sce-nario considered is shown in Figure 1.4. The control law and the consensus algorithm are dened in eq.(1.14) and eq.(1.15).

From the analysis of the time evolution of the global function Ξ(p) (Figure 1.5) it is possible to evaluate the behavior of the swarm. A larger value of this function corresponds to larger errors of the cur-rent moment vector. Figure 1.6 shows the tracking error history of the ve absolute abstract variables (µx, µy, M2x, Mxy, M2y), and the

evolution of the relative abstract variables (a1, a2).

From the numerical simulation, we can extract the following infor-mation:

• t ≤ 3s the system evolves in order to reach the desired statistics

(27)

• 3 < t ≤ 6s the system is subjected to a ramp command on the

center of mass and tracks it with a nite error; the errors on second order moments are still decreasing;

• 6 < t ≤ 17s the agents are subjected to the obstacle avoidance

forces; near the obstacle the second order moments are greater than desired (error is negative) to avoid the obstacle, while the motion of the center of mass slows down (error is positive). When leaving the obstacle region, the errors decrease;

• 17 < t ≤ 21s the agents are subjected to a ramp command on

the center of mass and the errors decrease;

• t > 21s the system evolves in order to reach the desired

statis-tics (µ = [17 17], a1 = a2 = 3, θ = 0). 0 3 6 9 12 15 18 21 24 27 30 0 200 400 600 800 1000 1200 time Ξ (p)

Global Objective Function, Ξ(p)

step

obstacle

step ramp

Figure 1.5: Global Objective Function

Figure 1.7 shows the evolution of the minimum distance between any two agents: while approaching the obstacle it decreases, and increases when the swarm is leaving the obstacle.

(28)

Chapter 1. Introduction 1 3 5 7 a1 , a 2

Relative Abstract Variables

0 10 20 30 −1 0 1 2 3 time µ x , µ y Tracking error −4 −3 −2 −1 0 1 M 2x , M 2y Tracking error 0 10 20 30 −1 0 1 2 3 4 5 time M xy Tracking error a 1 a 2 M xy M 2x M 2y µ_y µ_x

Figure 1.6: Swarm abstract variables

0 5 10 15 20 25 30 35 0.2 0.4 0.6 0.8 1 1.2 1.4 1.6 time

Min distance between vehicles

Min distance between vehicles

(29)

1.3 Outline of the Thesis

The case study just described represents a viable solution to multi-agent coordination but suers of several issues:

• it is dicult to infer the real shape of the swarm from the

knowledge of the formation statistics because the computable bounding box is, generally, too conservative;

• it is not possible to manage agent heterogeneity;

• it is dicult to deal with multiple tasks and with agents that

can execute more than one task simultaneously;

• control of the "agents density" inside the desired shape is not

possible with a reduced set of controlled/estimated inertia mo-ments.

For all these motivations a dierent and possibly unifying ap-proach was sought. This research lead to the Descriptor Functions (DF) Framework that is the subject of Part I of the thesis, and aims at modeling and solving a large class of coordination problems.

The environment and mission(s) under considerations are as gen-eral as possible, as well as the characteristics of the agents which may be all identical or heterogeneous. This condition is seldom found in the literature regarding high level control, and it comes into consid-eration usually only at the task assignment level. The number of agents is assumed to be "large", and therefore the size of a single vehicle is considered neglectable. Secondly, due to that, each agent may be limited in its own capability as an individual, but could help optimizing the overall behavior in terms of performance, robustness and probability of success. Thirdly, we will assume that the swarm may be subjected to losses (or planned expendabilities), therefore the performance are better evaluated as a whole, rather that at the individual level.

With the above assumptions, the main idea, which is at the basis of Descriptor Functions Framework, is to associate a specic function

(30)

to each agent, and one or more functions to the mission and the use of an analytical framework for generation of the control laws.

These functions, that we called Descriptor Functions, will have a dierent analytical formulation depending on the scenario and the agent capability they are modeling, but their relationships are other-wise general and scenario independent, so that they can be applied to dierent vehicles and dierent tasks with little or no modication. Thus, rst the DF Framework is introduced and the necessary modeling mathematical tools presented, then several application sce-narios are modeled inside the proposed unifying framework (Chapter 3).

Then the problem of how to control the swarm in order to achieve the assigned task is modeled as an optimization problem and solved using a gradient approach. Solution and extensive simulations for the proposed scenarios are shown, together with equilibria analysis and formal proof of convergence (Chapter 4).

The problem of decentralization of the control law is introduced next. Two dierent approaches for decentralized estimation of the necessary swarm variables are presented, and formal proof of conver-gence is given. Simulations to support the conclusions are shown as well (Chapter 5).

Two methods, derived from the functional approximation domain, capable of reducing the cardinality of information needed to compute the control laws are presented next. Simulations for typical coordi-nation applications are shown (Chapter 6).

Finally a bio-inspired method for task self-assignment is applied to the DF Framework; simulations will show that the method allows the agents of the swarm to select the best task to perform, and possibly switch task during the mission, in order to balance the degree of completeness among the various tasks (Chapter 7).

The last part of the Thesis (Part II) presents an hardware test bed that was designed in order to eld test coordination algorithms. This part of the thesis details the test bed design and presents ex-perimental results limited to a case study only (Chapter 8).

(31)

Part I

Descriptor Functions

Framework

(32)

(33)

Chapter

2

Motivations

Multi agent systems have received much attention from the scientic community due to their theoretical challenges and potential appli-cations. Despite the growing research literature in the eld, less at-tention has been paid to systems composed of heterogeneous agents. Agents' heterogeneity occurs primarily at two dierent levels: dier-ent agdier-ents may be associated to dierdier-ent tasks (mission level het-erogeneity) and/or agents may have dierent capabilities in execut-ing the same task (task level heterogeneity). Obviously the above mentioned dierences could constitute a big advantage in performing more complex missions, and/or in performing the same task at dif-ferent levels of quality. The other advantage is that the coordination among the subtasks of a mission can be improved if the ensemble of heterogeneous agents is treated as a single system (swarm). Further-more, in such a situation, all the agents could be managed at a macro level (high level coordination).

In order to achieve adaptation and robustness of the system to chang-ing environment conditions or evolution of the mission execution, agents capable of performing more than one task are preferable. In-deed, some kind of swarm self-organization can be obtained by let-ting each agent switching between dierent tasks. Due to this

(34)

self-Chapter 2. Motivations

organization process and, since some agents may execute more than one task at the same time, mission level heterogeneity may arise. The scenario considered in the following chapters describes the swarm mission as a set of tasks, with each agent capable of performing one or more tasks, possibly at the same time, and with the agents execut-ing the same task with dierent skills. Under these assumptions, the challenge we are facing is to design a general framework such that many tasks can be described using the same mathematical tools and accomplished using the same or a minimally modied control law. The chapters present a new approach to the deployment of a swarm of heterogeneous agents. The vehicles, or agents, may have dierent skills, and be employed for dierent missions. The methodology is based on the denition of Descriptor Functions that model the capa-bilities of the single agent and the capacapa-bilities needed by each task or mission.

The agents are considered resources, and have associated a function (descriptor) that uniquely denes their dynamic properties in the en-vironment. The descriptor function is representative of the agent's capabilities such as size, type of sensing properties, the task being ex-ecuted, etc. as they evolve dynamically. The overall swarm objective is dened by a global desired descriptor function, and the control of the swarm is related to the minimization of a suitable measure of the dierence between swarm and environment descriptors. One of the objectives of the proposed method is the construction of an unied framework capable of handling swarm area coverage, task allocation and swarm redistribution, depending on the agents' awareness and learning of the scenario.

(35)

Chapter 2. Motivations

2.1 Related Work

An approach similar to the one proposed in this thesis can be found in [31]. The authors introduced the concept of eective coverage: "Given a sensor network and mission domain D, how should the mo-tion of each sensor agent be controlled such that the entire network surveys D by sensing each point in D by an amount of eective cov-erage equal to C∗_{?" where the quantity C}∗ _{is statistically correlated}

to the probability of event detection at each point in D. Roughly speaking, the problem is: how can the exhaustive search be per-formed in the domain D such that each point is monitored for given amount of time? Agents were modeled with an instantaneous cover-age function that describes how eective the cover-agent senses each point of the environment. An error function was used to describe the dier-ence between the desired and the attained eective coverage. A cost function was then dened that maps the error function of the whole environment into a positive real number, which encodes how far the actual coverage is from the desired one. The global minimum of the cost function is reached if and only if the attained coverage equals the desired one. In order minimize the cost function, the control law of each agent was derived as the gradient of the cost function with re-spect to its position. Since the cost function may have local minima, a perturbation term is used to enforce the system towards a global optimization. In order to compute the control, each agent needs to know the information about the time trajectories of all the agents. In this rst implementation, the decentralization was achieved for a xed communication network by simply executing the same algo-rithm for each fully connected subgroup of the network, each seeking to cover the entire domain. Improvements to this approach where presented in [32] and [33], where collision avoidance terms and pe-nalization terms on the maximum acceptable inter-agent distance were added. This constraint was relaxed in [34] where a network of heterogeneous vehicles is used: one class of vehicles is responsible for the sole covering of the domain, while a second class of vehicles

(36)

provided the capability of eectively communicate coverage informa-tion across the network and to maintain strong communicainforma-tion links. In [30] the non-stationary problem for the eective coverage was for-mulated. The attained coverage was updated with an information decay term, so that the agents would continuously keep gathering information. The problem of coverage over large scale domains, i.e domains too large to be covered by a static sensor network, using instantaneous coverage function was improved in [68]. Instead of using a ocking strategy to achieve strong communication channels among sensors, another dierential equation, which represented the individual state of awareness, was fed back in the control law. The information sharing process would then reduce the amount of redun-dant coverage. The environment is discretized into n cells and, for each cell, the state of awareness describes how vehicles are aware of events occurring at that location. The individual state of awareness evolves continuously and is discretely updated whenever the agent establishes a new connection with other agents.

In [42] a new optimization algorithm for the coverage problem was formulated. A sensor is modeled with a function that describes the probability of event detection by the agent in the environment. The objective is encoded in a cost function that represents the joint detection probability of all the agents, weighted with a probability density function. The gradient of the cost function is used to derive a decentralized control law that drives the agents toward locations that maximize the cost function. The communication cost to deliver information to a base station was incorporated into the problem.

In [24] this algorithm was extended to teams of anisotropic sen-sors, i.e. sensors models in which the performance of the sensors depend not only on the distance but also on the orientation of the sensor with respect to the point of the environment. The algorithm optimizes the position and the orientation of the sensors.

(37)

The approach we propose is somewhat similar in the sense that agents are modeled in the environment with a function, and the tasks are described with objective functions. The proposed approach is however more general and it includes new considerations on the swarm's stability.

(38)

(39)

Chapter

3

Modeling

The Descriptor Functions Framework, as for almost all other ap-proaches seen in the literature, models each vehicle of the swarm as an agent of a network. Agents cooperate in order to perform a given task in a specied area according to their own capabilities. A general framework is introduced here, which aims at providing tools for solving a large class of coordination problems. The capability of an agent of executing a task relative to a given point of the envi-ronment, can be quantied, in general, using some function of the relative distance from the specic point. From a qualitative point of view, agents can be dened as carriers of resources of one or more kind, and they are described by a set of functions, which we call Agent Descriptor Functions (ADFs). The Agent Descriptor Function can be seen as a function of agent position and the environment that describes its capability of action/sensing at each point of the envi-ronment. Agents may be capable of performing dierent tasks (e.g. observation, search, etc.) with dierent performance (eg. payload-s/sensors). Thus a dierent ADF is needed for each dierent task. The number of ADFs used to describe the capabilities of a single agent equals the number of tasks contributing to the mission. If an agent is not capable of executing some of the tasks, the DFs relative

(40)

Chapter 3. Modeling

to those tasks are set to zero. Using this approach, mission level het-erogeneity arises naturally. Task level hethet-erogeneity can be included by assigning dierent DFs to the various agents. Since the tasks are dened in the operation space of the agents (i.e. where they move), a task can be specied as the request of resources of a given type for each point of the environment: the desired Task Descriptor Function (TDF).

For each task, the sum of all the agents' DFs is a measure of the spatial distribution of the resources that are pursuing the same objective, and can be used to describe the current state of execution of the task: the current TDF. The dierence between the desired TDF and the current TDF represents, for any point in space, the amount of resources needed, if positive, or in excess if negative, for the accomplishment of each task: the Task Error Function (TEF). The control objective can then be stated as the minimization, with respect to the position of the agents, of some cost function of the TEF. By this way, many dierent tasks can be formulated under the same framework using dierent desired TDF, while the architecture of the control law is maintained for all the tasks.

In order to achieve self-organization and adaptation, the aware-ness about the current state of execution of the tasks is necessary. In the DFs framework, a relevant level of awareness is represented by the knowledge of the current TDF associated to each task. This knowledge can be used by the agents to accomplish the task they are executing (task level self-organization) and to switch between tasks (mission level self-organization). Furthermore, decentralized estima-tion (interpolaestima-tion) techniques can be used to estimate (interpolate) the current TDFs (one for each task) obtaining a fully decentralized approach.

This chapter presents the mathematical tools that were developed for the DFs framework, and application examples using typical agents coordination problems taken from the literature.

(41)

Chapter 3. Modeling

3.1 Nomenclature and Denitions

This section presents the mathematical formulation of the proposed methodology.

The swarm is made up of N heterogeneous agents Vi, i = 1, ...N

and the mission is composed of a set of NT tasks. The set of agents

executing the same task at the same time forms a team. The number of teams may be up to NT, and each agent may be part of one or

more teams simultaneously. As example of this latter assumption, consider a swarm of sensing agents in a large environment. A subset of the agents may be engaged in the task of helping the network to maintain communication connectivity while still acquiring data from their sensors payload.

The set of tasks that agent i is executing at time t are denoted by

Ti(t) and the teams are dened as

Tk(t) =Vi : k ∈ Ti(t)

, k = 1, ..., NT (3.1)

The space where agents operate is Q ⊂ <n_{and the position of agent i}

at time t is pi(t)∈ Q. Without loss of generality, Q is assumed to be

closed and bounded. As usual in the literature, the agent dynamics is modeled as a single integrator with unity gain, i.e.

˙

pi(t) = ui(t), ui(t)∈ <n (3.2)

where pi(t) is the position of agent i. This simple model hides the

real vehicle nonlinear dynamical models and assumes the presence of low level controllers that use ui(t) as reference input.

(42)

Chapter 3. Modeling

3.2 Agent Descriptor Functions

Each agent is described in the framework using NT continuous

func-tions:

dk_i(pi, q) : Q→ <+, k = 1, ...NT, i = 1, ..., N (3.3)

where each dk

i(pi, q) describes the capability of agent i of executing

the task k at location q ∈ Q. For a sensing agent, the descriptor function can be directly related to its sensing performance, i.e. to how much information the agent is capable of gathering at position

q ∈ Q as a function of its position pi(t). Examples can be found in

the eld of sensor networks, where it is common to model the sensors with functions that are decreasing with the distance from the sensor location, [47]. For tasks that are not sensing tasks, the DF can be used to account for agents' presence. If an agent is not capable of executing a task then the DF relative to that task is set to 0 for each

q∈ Q.

The activity region of the agent Vi is dened as:

AVi _:=_q ∈ Q | dk

i(pi, q)≥ d, d ∈ Re+

(3.4) i.e. it is the region where the agent can exploit its capabilities with some level of condence.

To give an idea of analytical expressions usable to describe di(pi, q),

let us consider a Gaussian function as the descriptor function of an agent of the swarm in a two dimensional case:

di(pi, q) = γ exp − (pix − q1)2 σ2 ix − (piy− q2)2 σ2 iy ! (3.5)

where q = [q1 q2]T = [x y]T is the 2-dimensional coordinate of the

(43)

Chapter 3. Modeling

3.3 Current Task Descriptor Functions

The Current Task Descriptor Function (cTDF) describes the aggre-gated state of all the agents performing the task. The cTDF is dened as the sum of the descriptor functions of the agents that are executing that task, i.e. dk_{(p, q) : Q}_{→ <}+_:

dk(p, q) = X

Vi∈Tk(t)

dk_i(pi, q), k = 1, ...NT, i = 1, ..., N (3.6)

By using the terminology of [47], for teams of sensing agents this is a measure of the Sensor Intensity Field. For agents that have no sensing capabilities it describes how they are deployed in the envi-ronment, i.e. it can be used as a measure of the physical density of the agents. Figure (3.1) shows an example of how ADFs mix into the cTDF within the Descriptor Functions framework. The bottom layer shows the trajectories of 5 agents moving in a 2D environment. The corresponding Agents DFs and the Current TDF are shown, super-imposed, in the top layer, both at the beginning and at the end of the simulation.

(44)

Chapter 3. Modeling

3.4 Desired Task Descriptor Functions

The Desired Task Descriptor Function of a task species how the agents that are executing that task should be distributed. Speci-cally, it encodes the need of resources of a given type at each point q of the environment and it is formalized as:

dk_∗(q, t) : Q−→ <+, k = 1, ...NT (3.7)

The desired TDF is a function of the environment (and eventually of time) that encodes how resources should be distributed to execute the task. The following sections describe some of the tasks that can be described within the Descriptor Functions Framework by the denition of the corresponding desired TDFs.

3.4.1 Uniform Deployment

The problem of uniform deployment is often encountered in sensor networks. Typically, a limited number of sensors must be deployed in a known environment trying to keep sensor density (number of sensors in standard area) constant over the area of interest. Often, this type o problem is solved o-line since sensors do not have motion capabilities. The problem of on-line motion planning/control is faced by the so called sensor/actuator networks.

The agents, starting from some compact initial conguration, must spread out such that the area covered by the network is maximized. A similar approach to solve this problem is found in [27] using a potential-eld method: the network spreads itself throughout the environment using repulsion forces between the agents and the envi-ronment boundary. The network is considered homogeneous and the repulsion forces are computed as a function of the distance between the agents.

The control laws proposed in the following chapters are capable of deploying the agents in the environment taking into account their

(45)

Chapter 3. Modeling

sensing heterogeneity as well. The self-deployment objective is spec-ied using the following desired TDF:

d∗(q) = _¯

d if q ∈ P

0 otherwise (3.8)

where P is a generic closed area, non necessarily convex, that repre-sents the area that the agents must cover.

Figure 3.2 shows an example of deployment of 15 heterogeneous agents in a concave environment. Swarm heterogeneity is encoded in the spread parameters of the agent Descriptor Functions that are dierent for the x and y axis (i.e σx 6= σy).

Figure 3.2: Final positions of 15 heterogeneous agents in a concave environment.

3.4.2 Static Coverage

The problem of static coverage is similar to the problem of uniform deployment as a static conguration of the agents is sought. Un-like the uniform deployment, static coverage is preferred when the environment where agents move has regions of highest interest with respect to other areas. For sensor networks, the problem is to deploy agents into geographical areas with the highest information density.

(46)

Chapter 3. Modeling

The most referred algorithm used to solve the coverage problem is the one proposed by Bullo and coworkers in [15] and [14]. The authors develop a decentralized coverage control algorithm which is based on Voronoi partitions and the Lloyd algorithm. A common criticism of the Voronoi based coverage controller is that it is computation-ally intensive. Furthermore, it is designed to deal with homogeneous sensors. Within the Descriptor Function framework, this problem is solved using a lower complexity algorithm that allows the manage-ment of heterogeneous agents.

The desired TDF should encode the relative importance assigned to each point of the environment, thus it takes the more general form:

d∗(q, t) = ¯d∗(q) (3.9) As it will be shown in Section 3.5, the desired TDF may be used to encode the exact need of resources or it can just be a relative measure of importance of each point of the environment. The main concept is based on the assumption that for two comparably sized regions, more agents should be deployed in the one where the value of the desired TDF is higher.

3.4.3 Eective Coverage

The eective coverage problem, which was initially formulated by Hussein in [31], can be seen as the problem of exhaustive search in a given area. Within the DF framework, the agent DF models how eective the agent senses each point of the environment, i.e. it is seen as an instantaneous coverage function. The amount of eective coverage attained at a each point of the environment measures the level of sensing condence reached and it is computed as the integral over time of the current TDF:

de(q, t) = Z t 0 d (p (τ ) , q) dτ = Z t 0 N X i=1 di(pi(τ ) , q) dτ (3.10)

(47)

Chapter 3. Modeling

The goal of this task is to attain a given level of eective coverage for each point of the environment Q such that there is a sucient level of condence in judging whatever an event happened at q ∈ Q or not. The desired TDF depends on the time history of the agents position and is updated as

d∗(q, t) = max 0, ¯C− de(q, t)= = max 0, ¯C− Z t 0 d (p (τ ) , q) dτ

where ¯C quanties the desired level of condence. The task is

com-pleted if the desired TDF is zero for each point of the environment.

3.4.4 Dynamic Coverage

The goal of dynamic coverage is to let the agents to frequently revisit all points of the environment in order to keep the information level high. Dynamic coverage generally encodes the searching task in dy-namic environments or continuous patrolling of a given area. Within the DF framework dynamic coverage can be achieved adding an in-formation decay term to the attained eective coverage in eq.(3.10). The information decay process is analytically described by the partial dierential equation:

∂

∂tI (q, t) = δI (q, t) + d (p, q) (3.11)

with δ ≤ 0. The information decay term is represented by the neg-ative term δI (q, t), while the d (p, q) represents the information gain term. The information decay process can be seen as the loss, dur-ing time, of the awareness that agents have about each point of the environment.

The desired TDF that is used here to encode the task of dynamic coverage is:

(48)

Chapter 3. Modeling

where ¯C is the minimum level of eective coverage that would be

attained for each point of the environment. The desired TDF grows at points ¯q ∈ Q where there are few resources and diminishes where enough capabilities (measured by the current TDF) are present.

3.4.5 Target Assignment

Consider a scenario with Nw static targets and N agents. The goal

of the target assignment task considered here is to move at least one agent to each target if Nw ≤ N, or to cover N targets if Nw > N.

Within the DF framework, assuming identical targets and identically capable agents, targets can be modeled with the same Descriptor Function of the agents, thus the desired TDF is:

d∗(q, t) =

Nw

X

j=1

dj(pt, q) (3.13)

As for the current TDF, the desired TDF in eq.(3.13) can be seen as a measure of the density of the targets at each point of the environment. Figure 3.3 shows an example of target assignment scenario where both agents and targets are modeled with the same Descriptor Functions.

(49)

Chapter 3. Modeling

3.5 Task Error Function

The Task Error Function (TEF) measures the dierence between the desired TDF and the current TDF at each point of the environment. Since the TEF is a function of the current TDF, it is dened at each point of the environment and its domain is the tuple (q ∈ Q, p ∈ P) where q is the point of the environment and p is the vector of agents positions:

e (p, q) : Q× P → < (3.14)

Intuitively, the value of the Task Error Function must be large at those points of the environment where there is great demand of re-sources (large value of the desired TDF) but the current TDF is small. On the other hand, the TEF must be small (possibly nega-tive) at those points of the environment where there is a little demand of resources but a great presence of agents (large value of the current TDF).

Two dierent measures of the error are introduced in the next sections: the absolute TEF and the relative TEF. The absolute TEF is dened as the dierence between the desired TDF and the current TDF, thus it is a direct measure of the lack (if positive) or excess (if negative) of resources at each point of the environment. This measure can be used when agents have exact knowledge of the amount of agents capabilities required at all points of the environment. On the other hand, the relative TEF is dened as the ratio between the desired TDF and the current TDF, therefore the desired TDF may not be directly related to the exact need of resources.

3.5.1 The absolute Task Error Function

The absolute Task Error Function is dened as the dierence between the desired TDF and the current TDF:

(50)

Chapter 3. Modeling

For each task, the error function measures the lack of resources if

ek_A(p, q, t) > 0, and the excess of resources if ek_A(p, q, t) < 0.

This error measure has the advantage of allowing the deployment of the minimum number of capabilities and to give the agents sucient awareness to perform task selection (see chapter 7).

3.5.2 The relative Task Error Function

The relative Task Error Function is dened as the ratio between the desired TDF and the current TDF:

ek_R(p, q, t) = d

∗k_{(q, t)}

dk_{(p, q) + c}, k = 1, ...NT (3.16)

where c ≥ 0 is a parameter used to guarantee the TEF to be well-dened also when the current TDF is 0. At point ¯q the relative TEF is large if d∗k_(¯_{q, t)}_{is large and d}k_{(p, ¯}_q)is small, that means that there

is a need of resources at point ¯q. On the other hand, the relative TEF is small if d∗k_(¯_{q, t)} _{is small and d}k_{(p, ¯}_q) _{is large.}

As anticipated, this error measure has the advantage of not requiring an exact model of the capabilities needed and the desired TDF is not necessarily related to the eective need of the task. Intuitively, the agents must move towards those points of the environment where the need of resources is greater (high TEF) with respect to other points where the TEF is small.