Self Improvement

27 pages
10 views

Flocks and formations

of 27
All materials on our website are shared by users. If you have any questions about copyright issues, please report us to resolve them. We are always happy to assist you.
Share
Description
Flocks and formations
Transcript
  FLOCKS AND FORMATIONS J. J. P. Veerman ∗ , G. Lafferriere, J. S. Caughman, A. Williams.Department of Mathematics and Statistics,Portland State University, Portland, OR 97207. In Honor of Mitchell Jay Feigenbaum’s 60’th Birthday. August 19, 2005 Abstract Given a large number (the “flock”) of moving physical objects, we investigate physically reasonablemechanisms of influencing their orbits in such a way that they move along a prescribed course and in aprescribed and fixed configuration (or “in formation”).Each agent is programmed to see the position and velocity of a certain number of others. This flowof information from one agent to another defines a fixed directed (loopless) graph in which the agents arerepresented by the vertices. This graph is called the communication graph. To be able to fly in formation,an agent tries to match the mean position and velocity of his neighbors (his direct antecedents on thecommunication graph) to his own. This operation defines a (directed) Laplacian on the communicationgraph. A linear feedback is used to ensure stability of the coherent flight patterns.We analyze in detail how the connectedness of the communication graph affects the coherence of thestable flight patterns and give a characterization of these stable flight patterns. We do the same if inaddition the flight of the flock is guided by one or more leaders.Finally we use this theory to develop some applications. Examples of these are: flight guided byexternal controls, flocks of flocks, and some results about flocks whose formation is always oriented alongthe line of flight (such as geese).KEYWORDS: Communication Graphs. Directed Graph Laplacians. Stability of Formations. LinearFeedback and Control. Systems of Ordinary Differential Equations. 1 INTRODUCTION In observing large schools of fish or flocks of birds, what strikes us most is their capability of maneuveringwhile maintaining the pattern formed by their bodily positions (up to translation and/or rotation). If theflock is large enough, it dawns on us that the animals cannot possibly keep track of the positions andvelocities of all the others; on contrary, they must execute a local algorithm that enables them to stay “information” while the flock as a whole executes its motion or maneuver. In fact, biologically based models ∗ e-mail: veerman@pdx.edu 1  studied in [20] indicate that animals do not keep track of more than something on the order of ten others.This algorithm must be such that the configuration is stable against perturbation (such as sudden wind,etcetera).While still little appears to be known about the algorithm that animals actually employ to fly (or run,or swim) in stable configurations (but see [16], [20]), neighbor-based algorithms are now employed to controlthe movement of groups of artificial agents (robots, drones, see [10, 13, 15, 23, 25]). In order to see how theneed for such an algorithm may arise, we mention the following taken from the literature (see [6]). Supposethat many autonomous (not steered by an external source) vehicles find themselves in an enclosed spacewith only one relatively narrow exit. The object is to get all the vehicles to leave the space through the exitas quickly as possible, with a minimum of computation on the part of the vehicles, and without collisions.One way to achieve this is to have the vehicles move a circular formation first, then have the vehicles exitthe through the opening one after the other. We end Section 8 with a simulation of a movement reminiscentof this problem.The part of the problem we address is how can one achieve that autonomous agents move towards aformation and, once formation is attained, how can we ensure it is stable against perturbations. There arevarious approaches to achieve this. One of the first ones led to “boids” [24]. In many of these applicationsone is not necessarily preoccupied with actual physical objects, but rather a numerical simulation. In [26]previous approaches were greatly simplified, but again the equations are not plausible for physical agents(they are more interested in phase transitions). Fax and Murray ([4, 5]) were among the first to write downequations that were meant to govern actual physical entities. Our exposition follows along these lines.An area of research which is closely related to the theme of this paper is that of consensus seekingautonomous agents. In this case agents achieve consensus if their associated variables converge to a commonvalue. In [17, 18, 21, 23] the convergence to consensus is proved under a variety of circumstances. However,in our case the agents, being physical objects, do not want to coalesce to the same position but to a positiona fixed distance away from its neighbors, and they must satisfy Newton’s Law.The algorithm we investigate (following [11], [12], [3]) in this paper has the following ingredients. Theindividual agents are identical (all do the same computation). Each individual agent complies with Newton’sLaw in that it changes position and velocity by applying a force or thrust, which causes it to accelerate inthe desired direction. Furthermore, in order to compute the thrust each agent may use as its input onlythe following data: its own position and velocity relative to an absolute coordinate system and those of asmall (and fixed) collection of neighbors. It will turn out that in fact only the position and velocity of theothers relative to it will be used except when we wish the flock to accelerate (see the equations at the end of Section 2). In addition the computation requires the desired position of each agent in the formation. (Again,the aforementioned equations show that we only require the relative positions.) Finally, the algorithm thatcomputes the thrust is only to use affine combinations of the above quantities, and must, at least for a largecollection of initial conditions, cause the whole system to converge to an in formation orbit, that is: an orbitof the flock in which all the relative positions have the desired value.In the next section we will consider such a model. We will address two main issues. The first is todecide exactly what kind of coherent motions the flight of the flock converges to if we choose an appropriatelinear feedback. It turns out that this depends on the topology of the graph whose vertices represent theagents and whose directed edges ( i,j ) represent the relation: agent i sends information to agent j in theflock. Thus in Section 3 we discuss some notions of graph theory. The first main result, (Theorem 4.4),which specifies the set of asymptotic orbits of the flock, is a generalization of results obtained by [5] and[12].The second main issue is essentially new and addresses the question how to arrange the algorithm2  that computes the force or thrust applied by each agent in such a way that the “center of mass” of theflock follows a specified orbit and the configuration is stable against perturbations throughout the orbit (seeTheorem 5.2). In [12] this issue was addressed only in the case linear acceleration is desired.In the remaining sections we simplify the stability calculation for hierarchies of graphs, extendingearlier results of [27] (see Section 7), and modify the notion of in formation to a biologically more reasonableone that involves orientable configurations (Section 8). The equation that governs the evolution of thissystem is nonlinear. The last section summarizes the main lines of thought in this paper, now with thebenefit of being able to use the language developed in the course of this work.This exposition depends on a theorem stated here (as Theorem 3.6) but proved in a companion paper([3]) since its proof requires quite a few lemmas unrelated to the main argument here. With this exception,the theory developed here is self-contained. Acknowledgements : The authors fondly recall a recent and memorably festive visit of Mitchell to PortlandState. There was no end to oysters, good wine, and interaction between faculty of about half a dozendepartments.One of the authors (JJPV) has many dear memories, first as a student at Cornell, and later as apostdoc with Mitchell at Rockefeller, of many inspiring evenings, always marked by Mitchell’s unfailinglyinquisitive and analytic nature and superb taste in wine.AW and GL were supported in part by a grant from Honeywell, Inc. GL was also supported in partby NSF grant DMS-0408334 and by a career support grant from Portland State University. JJPV is gratefulfor the hospitality of the Physics Department of the UFPE, in Recife, Brazil, where part of this researchwas carried out, and support from the CNPQ for his stay there. 2 THE LINEAR MODEL The individual agents are assumed to move in IR d , so that the dynamical coordinates (position and velocity)of each agent constitute a point in the tangent bundle T  IR d ∼ =IR 2 d . In physical applications (such as buffaloor drones) d will usually be 2 or 3. The agents are numbered, say, from 1 through N  . It is convenient tothink of the coordinates of the entire flock as the graph of a function C  : { 1 , ··· ,N  }→ IR 2 d in the product X  ≡{ 1 , ··· N  }× IR 2 d . Indeed we will end up writing a general position in X  as a (tensorial)sum of the positions of each agent (see Equations 2.1 and 2.2).We now choose coordinates in X  . A point in z ∈ X  is specified by a column vector of 2 dN  real numbersas follows. The position and velocity of agent j are given by the entries numbered 2 d (  j − 1) + 1 through2 dj . The first of these real numbers specifies the first of its position coordinates (the x -coordinate) and thesecond specifies the first of the velocity coordinates. The third entry is the second position coordinate, andso on alternatingly.It turns out that the Kronecker product ( ⊗ ) provides us with the adequate description of the space X  . Using this product, we can write an arbitrary point z ∈ X  as z = N   i =1 e i ⊗ ρ i , (2.1)3  where e i is an N  -vector with a single 1 in the k -th entry as its only non-zero entry and ρ i is the position-velocity vector of the i -th agent. Alternatively, if we wish to specify the position x i and velocity v i of theindividual agent separately, we can write z = N   i =1 e i ⊗  x i ⊗  10  + v i ⊗  01  . (2.2)Each agent is assigned a desired position h i ∈ IR d in the flock. (We can also assign a desired velocity,but the only choice for a stabilizable in formation state turns out to be a velocity that is the same for allagents, see Section 5.) We thus obtain a vector h as follows: h = N   i =1 e i ⊗ h i ⊗  10  . This vector is the desired configuration vector. Definition 2.1 The orbit  φ : IR → X  of the flock is said to be in formation if it is given by  φ ( t ) = h + N   i =1 e i ⊗ α = h + 1 N  ⊗ α ,  for some function  α : IR → IR 2 d of the form  α = q ⊗  10  +  p ⊗  01  and p = dqdt, where 1 denotes the N  -dimensional vector of all ones. Each agent is allowed to see only some of its colleagues (its neighborhood) and applies the same linearfeedback as the others. This neighborhood does not vary. The agent continually averages its neighbors’positions and velocities, then subtracts that from its own. It then compares this with the desired outcomeof that calculation (namely, the same operation performed on the h k ). Thus if agent k has agents i and j asits neighbors, it calculates the d -dimensional vector ( x k − h k ) − 1 / 2( x i − h i ) − 1 / 2( x  j − h  j ) and another one, v k − 1 / 2 v i − 1 / 2 v  j . The operation that does this for each agent will be called the (directed) Laplacian. Theagent is then allowed to compute linear combinations of the components of this 2 d -dimensional vector anduse these to determine its thrust. Finally, we allow the agent to correct its orbit using linear combinationsof its own position-velocity vector.As an example, consider a flock in IR 3 so that agent i has position ( x i ,y i ,z i ), velocity ( u i ,v i ,w i ), anddesired position ( h x,i ,h y,i ,h z,i ). Assume that agent 1 sees only agents 2 and 3. The equations of motion foragent 1 become (with some further assumptions, see below).˙ x 1 = u 1 ˙ u 1 = au 1 + f   ( x 1 − h x, 1 ) − 12( x 2 − h x, 2 + x 3 − h x, 3 )  + g  u 1 − 12( u 2 + u 3 )  ˙ y 1 = v 1 ˙ v 1 = av 1 + f   ( y 1 − h y, 1 ) − 12( y 2 − h y, 2 + y 3 − h y, 3 )  + g  v 1 − 12( v 2 + v 3 )  4  ˙ z 1 = w 1 ˙ w 1 = aw 1 + f   ( z 1 − h z, 1 ) − 12( z 2 − h z, 2 + z 3 − h z, 3 )  + g  w 1 − 12( w 2 + w 3 )  These equations are invariant under Galilean transformations only if  a = 0. The parameter a and othersimilar parameters in this model (the matrix A 4 in the remark after Theorem 4.2) are parameters thatcan used by a central authority to ‘steer’ the orbit of the flock as a whole. A few examples of this will bediscussed in Section 5.In a more compact notation using the Kronecker product for matrices as well, we can write the aboveequations of motions for the whole system very succinctly in the following way. Definition 2.2 With the above conventions, the equations of motion of the flock are: ˙ z = I  N  ⊗ Az + L N  ⊗ K  ( z − h ) . (2.3) Here I  N  is the N  × N  identity matrix and  L N  is the N  × N  (directed) Laplacian matrix (see Section 3).The matrices A and  K  are assumed to be constant. The matrix  K  may be chosen to stabilize in formation orbits (see below). The matrix K  is essentially a linear filter. To obtain the equations of the above example (these arethe equations studied by [12]), we chose A and K  to have a particularly simple form, namely: A =  0 1 0 0 0 00 a 0 0 0 00 0 0 1 0 00 0 0 a 0 00 0 0 0 0 10 0 0 0 0 a  and K  =  0 0 0 0 0 0 f g 0 0 0 00 0 0 0 0 00 0 f g 0 00 0 0 0 0 00 0 0 0 f g  . The srcin of the matrix K  in equation 2.3 is in a control theoretic formulation of this problem, of which an extensive discussion can be found in [5]. The thought underlying the last term of equation 2.3 isthat each agent performs two computations. Agent k filters its data by applying the 2 d × 2 d matrix K  toits own 2 d components of the vector z − h (the vector z k − h k ), and it applies the k -th row of the Laplacian L N  to the flock (this computation involves only data from the agents it sees directly). That said, we shouldremark that the order in which these operations are executed is irrelevant, since:( L N  ⊗ I  2 d )( I  N  ⊗ K  ) = ( I  N  ⊗ K  )( L N  ⊗ I  2 d ) . Thus we may think of the agents as computing the Laplacian before filtering their output. Since the outputof the computation gives the acceleration, we can think of  K  as a feedback. This is also the approach takenby [5].In Section 8, a model will discussed in which each h i is rotated by the angle in which agent i is flying.This has the advantage that the formation as a whole can orient itself. However, the resulting equation isnonlinear.As a final remark in this section, we should point out that the main conclusions are valid if we replacethe above Laplacian by a weighted version of it: the diagonal entries equal 1, all other entries are non-positive, and row-sums are zero. We do not pursue this here in the interest of readability (but see ref.3).5
Related Documents
View more...
We Need Your Support
Thank you for visiting our website and your interest in our free products and services. We are nonprofit website to share and download documents. To the running of this website, we need your help to support us.

Thanks to everyone for your continued support.

No, Thanks