iDocSlide.Com

Free Online Documents. Like!

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

Tags

Transcript

FLOCKS AND FORMATIONS
J. J. P. Veerman
∗
, G. Laﬀerriere, 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 “ﬂock”) of moving physical objects, we investigate physically reasonablemechanisms of inﬂuencing their orbits in such a way that they move along a prescribed course and in aprescribed and ﬁxed conﬁguration (or “in formation”).Each agent is programmed to see the position and velocity of a certain number of others. This ﬂowof information from one agent to another deﬁnes a ﬁxed directed (loopless) graph in which the agents arerepresented by the vertices. This graph is called the communication graph. To be able to ﬂy 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 deﬁnes a (directed) Laplacian on the communicationgraph. A linear feedback is used to ensure stability of the coherent ﬂight patterns.We analyze in detail how the connectedness of the communication graph aﬀects the coherence of thestable ﬂight patterns and give a characterization of these stable ﬂight patterns. We do the same if inaddition the ﬂight of the ﬂock is guided by one or more leaders.Finally we use this theory to develop some applications. Examples of these are: ﬂight guided byexternal controls, ﬂocks of ﬂocks, and some results about ﬂocks whose formation is always oriented alongthe line of ﬂight (such as geese).KEYWORDS: Communication Graphs. Directed Graph Laplacians. Stability of Formations. LinearFeedback and Control. Systems of Ordinary Diﬀerential Equations.
1 INTRODUCTION
In observing large schools of ﬁsh or ﬂocks 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 theﬂock 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 ﬂock 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 conﬁguration is stable against perturbation (such as sudden wind,etcetera).While still little appears to be known about the algorithm that animals actually employ to ﬂy (or run,or swim) in stable conﬁgurations (but see [16], [20]), neighbor-based algorithms are now employed to controlthe movement of groups of artiﬁcial 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 ﬁnd 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 ﬁrst, 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 ﬁrst 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 simpliﬁed, 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 ﬁrst 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 ﬁxed 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 ﬁxed) 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 ﬂock 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 aﬃne 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 ﬂock 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 ﬁrst is todecide exactly what kind of coherent motions the ﬂight of the ﬂock 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 theﬂock. Thus in Section 3 we discuss some notions of graph theory. The ﬁrst main result, (Theorem 4.4),which speciﬁes the set of asymptotic orbits of the ﬂock, 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 theﬂock follows a speciﬁed orbit and the conﬁguration 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 conﬁgurations (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 thebeneﬁt 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, ﬁrst 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 buﬀaloor 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 ﬂock 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 speciﬁed 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 ﬁrst of these real numbers speciﬁes the ﬁrst of its position coordinates (the
x
-coordinate) and thesecond speciﬁes the ﬁrst 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 ﬂock. (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 conﬁguration vector.
Deﬁnition 2.1
The orbit
φ
:
IR
→
X
of the ﬂock 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 ﬂock 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 ﬂock 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.
Deﬁnition 2.2
With the above conventions, the equations of motion of the ﬂock 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 ﬁlter. 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
ﬁlters 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 ﬂock (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 ﬁltering 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 ﬂying.This has the advantage that the formation as a whole can orient itself. However, the resulting equation isnonlinear.As a ﬁnal 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

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