TECHNICAL RESEARCH REPORT

A Simple Control Law for UAV Formation Flying

by E.W. Justh, P.S. Krishnaprasad

TR 2002-38

I R
INSTITUTE FOR SYSTEMS RESEARCH

ISR develops, applies and teaches advanced methodologies of design and analysis to solve complex, hierarchical,
heterogeneous and dynamic problems of engineering technology and systems for industry and government.
ISR is a permanent institute of the University of Maryland, within the Glenn L. Martin Institute of Technol-
ogy/A. James Clark School of Engineering. It is a National Science Foundation Engineering Research Center.
Web site http://www.isr.umd.edu
 Form Approved
Report Documentation Page OMB No. 0704-0188

Public reporting burden for the collection of information is estimated to average 1 hour per response, including the time for reviewing instructions, searching existing data sources, gathering and
maintaining the data needed, and completing and reviewing the collection of information. Send comments regarding this burden estimate or any other aspect of this collection of information,
including suggestions for reducing this burden, to Washington Headquarters Services, Directorate for Information Operations and Reports, 1215 Jefferson Davis Highway, Suite 1204, Arlington
VA 22202-4302. Respondents should be aware that notwithstanding any other provision of law, no person shall be subject to a penalty for failing to comply with a collection of information if it
does not display a currently valid OMB control number.

1. REPORT DATE 3. DATES COVERED

2. REPORT TYPE
2002 -
4. TITLE AND SUBTITLE 5a. CONTRACT NUMBER
A Simple Control Law for UAV Formation Flying 5b. GRANT NUMBER

5c. PROGRAM ELEMENT NUMBER

6. AUTHOR(S) 5d. PROJECT NUMBER

5e. TASK NUMBER

5f. WORK UNIT NUMBER

7. PERFORMING ORGANIZATION NAME(S) AND ADDRESS(ES) 8. PERFORMING ORGANIZATION

REPORT NUMBER
Army Research Office,PO Box 12211,Research Triangle Park,NC,27709
9. SPONSORING/MONITORING AGENCY NAME(S) AND ADDRESS(ES) 10. SPONSOR/MONITOR’S ACRONYM(S)

11. SPONSOR/MONITOR’S REPORT

NUMBER(S)

12. DISTRIBUTION/AVAILABILITY STATEMENT

Approved for public release; distribution unlimited
13. SUPPLEMENTARY NOTES

14. ABSTRACT
see report
15. SUBJECT TERMS

16. SECURITY CLASSIFICATION OF: 17. LIMITATION OF 18. NUMBER 19a. NAME OF
ABSTRACT OF PAGES RESPONSIBLE PERSON
a. REPORT b. ABSTRACT c. THIS PAGE
36
unclassified unclassified unclassified

Standard Form 298 (Rev. 8-98)

Prescribed by ANSI Std Z39-18
 A Simple Control Law for UAV Formation
Flying

E. W. Justh a P. S. Krishnaprasad b
a Institute
for Systems Research
University of Maryland
College Park, MD 20742, USA
b Institutefor Systems Research and
Dept. of Electrical and Computer Engineering
University of Maryland
College Park, MD 20742, USA

Abstract

This paper presents a Lie group setting for the problem of control of formations,
as a natural outcome of the analysis of a planar two-vehicle formation control law.
The vehicle trajectories are described using planar Frenet-Serret equations of mo-
tion, which capture the evolution of both the vehicle position and orientation for
unit-speed motion subject to curvature (steering) control. The set of all possible
(relative) equilibria for arbitrary G-invariant curvature controls is described (where
G = SE(2) is a symmetry group for the control law). A generalization of the con-
trol law for n vehicles is presented, and the corresponding (relative) equilibria are
characterized. Work is on-going to discover stability and convergence results for the
n-vehicle problem. The practical motivation for this work is the problem of forma-
tion control for meter-scale UAVs; therefore, an implementation approach consistent
with UAV payload constraints is also discussed.

Key words: Frenet-Serret equations, nonlinear stability, Lyapunov function,

formation control, shape space

This research was supported in part by the Army Research Office under ODDR&E
MURI01 Program Grant No. DAAD19-01-1-0465 to the Center for Communicating
Networked Control Systems (through Boston University), by the Air Force Office
of Scientific Research under AFOSR Grant No. F49620-01-0415, and by the Naval
Research Laboratory under Grant No. N00173-02-1G002.
Email addresses: [email protected] (E. W. Justh), [email protected] (P.
S. Krishnaprasad).
1 Introduction

As the technological development of meter-scale UAVs (unmanned aerial ve-

hices) progresses, and the cost of such vehicles decreases, there is growing
interest in applications for formations (or swarms) of these UAVs. These ap-
plications include surveillance, creating decoys, delivery of payloads (e.g., dis-
tributing ground-based sensor networks), and radar or communications jam-
ming. Having human operators remotely control each UAV in a formation
is impractical; therefore, coordinating the flight of multiple UAVs becomes a
problem of automatic control. In ongoing work, we are examining a particular
approach to this control problem, with the ultimate objective of producing a
prototype system capable of meeting the size, weight, and power constraints
associated with small UAV platforms.

An essential feature of the formation control problem for meter-scale UAVs

is that “autonomy” (e.g., sensors and processing power for target recognition,
obstacle avoidance, GPS and inertial navigation, and performance of sophis-
ticated mission objectives) is severly limited by cost and payload constraints.
Consequently, we identify a few specific objectives, and attempt to formulate
and implement a control law to meet these basic objectives. These objectives
are to avoid collisions between UAVs, maintain the cohesiveness of the forma-
tion, be robust to loss of individuals, and scale favorably for large swarms. The
challenge is that the physics of sensing, actuation, and communication can-
not be neatly separated from the problem of coordination and control. Rather
than simply extra payload, the automatic control system for formation control
becomes an integral part of vehicle design.

In section 2, we describe how an automatic control system for formation flying

could be practically implemented. The basic idea involves providing a mecha-
nism (based on radio-frequency pulses) by which each UAV can sense its range
and relative orientation with respect to its neighbors. We consider simple rules
for how each UAV changes its motion in response to these “sensor” measure-
ments. In terms of implementation, the hardware required for the controller
on-board each UAV can, by incorporating analog VLSI circuitry, fit on a single
small printed-circuit board. The objective is to supply the collection of UAVs
with a “default” formation-maintaining behavior in such a way that the for-
mation (as an entity) can be easily controlled, e.g., by modifying parameters,
adding exogenous inputs, or switching among various “default” behaviors.

Models of the individual vehicles are based on the planar Frenet-Serret equa-
tions of motion (discussed in section 3), which describe how vehicle trajectories
evolve under curvature (steering) control, subject to a unit-speed assumption
[1]. While our interest is primarily in formation control for small UAVs, this
approach to modeling and control could also be applicable to formations or

2
swarms of ground vehicles or underwater vehicles, and may also be a useful
starting point for understanding certain features of biological swarming or
schooling behavior.

This paper presents a Lie group setting for the problem of control of for-
mations. The setting emerges naturally from the analysis of basic cases and
concomitant physical contraints on the controls. (A modern reference for con-
trol systems on Lie groups is Jurdjevic [2].)

The primary analytical result we present (in section 4) is a global convergence

result for a planar two-vehicle formation control law, proved using LaSalle’s
Invariance Principle [3]. A corresponding convergence result for a single vehicle
responding to an omnidirectional beacon is also presented, and is used (in
section 5) to help physically motivate the form of the two-vehicle control law,
and to explain the relationship between the various sensor measurements and
the quantities appearing in the control law. A generalization of the control law
to n vehicles is presented in section 6, but a stability analysis is the subject
of on-going work, and will be presented in a future paper.

The two-vehicle control law has an evident Lie-group structure, and this struc-
ture is exploited (in section 7) to determine the set of all possible (relative)
equilibria for arbitrary G-invariant curvature controls, where G = SE(2) is
the symmetry group for the control law. Ideas of “shape control” on Lie groups
arise in a natural way for this problem [4–6]. The equilibrium analysis is also
generalized to the n-vehicle problem. Finally, in section 8, we discuss directions
for future research.

The use of curvature controls can be given the mechanical interpretation of

steering unit-mass, unit-charge particles by magnetic fields (and hence by
forces derived from vector potentials). For a discussion of the general theory
of such controls, see [7]. This is in contrast with other current approaches to
formation control that are based on scalar potentials [8]. Furthermore, our
emphasis on the Lie group structure of the control laws distinguishes our
work from an established physics literature in the area of large collections
of interacting particles subject to local interaction laws, and giving rise to
pattern-forming systems, spatially localized coherent structures (e.g., flocks),
and phase transitions (e.g., from disorder to order); see, for instance, [9–11].

3
Fig. 1. A pair of receive antennas separated by a quarter-wavelength, and the sinu-
soidal function of angle-of-arrival which it can measure.

2 Formation control system implementation

2.1 Angle-of-arrival and range sensing

Consider the planar formation control problem: i.e., assume that there as a
common plane of motion for the UAVs (and that this plane of motion does not
change with time). Suppose that an RF (radio-frequency) transmit antenna,
as well as a pair of receive antennas, are located in (and oriented perpendicular
to) the plane of motion. (Neglect the mutual impedance of the receive anten-
nas). If the receive antennas are spaced a quarter-wavelength apart, then by
appropriate quadrature phase shifting, correlation (i.e., multiplication), and
low-pass filtering, a sinusoidal function of the angle of arrival can be measured
(see figure 1). The range, or distance between the transmitter and receiver, can
also be measured (since it is inversely related to the received signal power).

If two pairs of receive antennas are used, oriented perpendicular to each other
as shown in figure 2, then the direction of arrival of the received RF signal
can be unambiguously determined. (Although dipole antennas are shown in
figure 2, the actual antenna design would need to take into account aircraft
aerodynamics and possible parasitic antenna elements. Noise, interference, and
multipath are also important electromagnetics issues, but are also beyond the
scope of this paper.) As figure 2 suggests, the antenna separation and hence
the transmission frequency are related to the UAV dimensions.

It turns out that more information besides simply range and direction-of-
arrival is useful for formation control. Specifically, we would also like to sense
the relative orientation between the transmitting and receiving UAV. This
extra information can be sensed if all four antennas shown in figure 2 partic-
ipate in transmitting as well as receiving. Each pair of antennas, considered

4
 Fig. 2. Two pairs of receive antennas oriented perpendicularly on a UAV.
as a transmitting antenna array, has a cardioid antenna pattern if driven with
single-tone pulses which are in phase-quadrature (figure 3(a)). Reversing the
signals to the two antennas spatially reorients the cardioid antenna pattern
by 180 degrees (figure 3(b)). If two quadrature signals at nearby but different
frequencies are fed to the antennas simultaneously, but with the proper phase
relationship so that the cardioid antenna patterns have their peaks in oppo-
site directions, then by differencing the (normalized) amplitudes (i.e., power
measurements) of the received pulses, a remote UAV can extract information
about the orientation of the transmitting UAV relative to the baseline be-
tween the two UAVs (figure 3(c)). If both pairs of half-wave dipole antennas
are driven (with four nearby but different frequencies) in this way (figure 3(d)),
then the remote UAV will have enough sensor information to unambiguously
measure the mutual orientation of the two UAVs.

After presenting and analyzing a specific control law in sections 3 and 4, we

will explicitly show (in section 5) how the various quantities in the control law
correspond to relative orientation and range measurements of the type just
described.

2.2 Pulsed communication scheme

In the previous subsection, we discussed how RF signals and appropriate an-

tenna configurations can permit each UAV to sense range and orientation
relative to the other UAVs. One approach for reducing power consumption
while keeping the system complexity low is to transmit RF pulses, as shown
in figure 4, rather than continuous-wave signals. The UAVs take turns trans-
mitting pulses (or bursts), and except when transmitting, each UAV listens to
the others. (Of course, some scheme is required to organize the pulsed commu-
nication and prevent simultaneous transmissions, but these details are beyond
the scope of this paper.) The PRI (pulse repetition interval), pulse width, and
power consumption depend on the frequency, the number of UAVs, and the
required UAV control signal update rate. Thus, the communication system
depends intimately upon vehicle characteristics, such as its dimensions and
dynamical constraints.

5
 90 90
1 1
120 60 120 60
0.8 0.8

0.6 0.6
150 30 150 30
0.4 0.4

0.2 0.2

180 0 180 0

210 330 210 330

240 300 240 300

270 270

(a) (b)
90
1
120 60
0.8

1
0.6
150 30
0.8
0.4

0.6
0.2
0.4

180 0
0.2

−0.2

210 330
−0.4

−0.6

−0.8
240 300

270
−1
−3 −2 −1 0 1 2 3

(c) (d)
Fig. 3. Using two pairs of antennas for extracting relative orientation information:
(a) cardioid antenna pattern for a single pair of antennas and a single tone; (b)
cardioid antenna patterns for a single pair of antennas and two tones at different
frequencies; (c) difference in received signal power as a function of angle between
the transmitting UAV and the baseline; and (d) cardioid antenna patterns for two
pairs of antennas and tones at four different frequencies.

Using this type of pulsed communication system avoids the need for a data
communication network for formation control. (Of course, if a data communi-
cation network were available, the UAVs could determine their own positions
and orientations using GPS, and then exchange the information with each
other over the data communication network.) The main drawback with using
a data communication network is the interplay between the communications
and the control aspects of the resulting communicating networked control sys-
tem. (Note, for example, that as the UAVs move, the network topology may

6
Fig. 4. Pulsed communication system: the UAVs take turns transmitting pulses, and
except when transmitting, each UAV listens to the others.

change.) Using a data communication network for control requires careful at-
tention to communication protocols, can introduce problems of scalability for
large formations, and can be extremely difficult to analyze. An additional
benefit of the pulsed communication scheme is reduced reliance on GPS.

The pulsed communication scheme uses time-division-multiplexing to share

the communications bandwidth among multiple transmitters. One reason for
chosing this scheme is to facilitate prototyping. Of course, other channel-
sharing techniques like CDMA (code division multiple access) might ulti-
mately be useful for improving stealth capability and reducing succeptibility
to jamming.

2.3 Transceiver/controller block diagram

Figure 5 shows the block diagram for a transceiver/controller capable of imple-

menting the control systems we consider based on the pulsed communication
scheme described in the previous subsection. The four antennas represent the
two pairs of antennas in figure 2. When the UAV is listening, the antenna
signals pass through the transmit/receive switches to the low-noise-amplifiers
and bandpass filters. Next, the signals arrive at an analog processor, which
produces the various range and orientation measurements described above,
and combines them into a single steering control increment each time an RF
pulse is received. This steering control increment is then digitized and sent to
a digital processor. The analog processor also has an output signal (an activity
indicator) to tell the digital processor whether its steering control increment
represents valid data. The digital processor accumulates the steering control
increments over a full period during which each other UAV is transmitting,
and then updates a steering control signal that it sends to the UAV autopi-
lot. The digital processor is also responsible for controlling when the UAV
transmits, and when it listens. During the transmitting phase, the required
quadrature oscillator signals (which can be generated by the analog processor)
are amplified, and sent to the antennas through the transmit/receive switches.
The digital processor can also have a control line to the analog processor, so

7
Fig. 5. Transceiver/controller block diagram for UAV control based on pulsed com-
munication.
that, e.g., control law parameters can be varied on the fly.

The digital processor is thus involved with organizing the pulsed communi-
cation, interfacing with the autopilot, and could also potentially filter (or re-
ject corrupted data from) the analog processor signal. Although not indicated
in figure 5, the digital processor can also interface with a higher-level con-
trol system on board the UAV, which may communicate with the ground or
other UAVs using a data communication network. Such data communication
could be used to control the formation as a whole, with the basic formation-
maintaining function being performed by the pulsed communication system
and block diagram of figure 5.

The key feature of figure 5 is that (apart from the antennas and autopilot)
the entire system could potentially fit on a single printed circuit board small
enough to fit into a meter-scale UAV, provided the analog processor is im-
plemented using analog VLSI technology. There are some similarities between
the analog processor in figure 5 and the analog CMOS continuous wavelet
transform circuits developed at the Naval Research Laboratory [12]. There is
thus a feasibility demonstration of some of the required subcomponents of an
analog VLSI processor for the UAV formation control application.

The possibility of producing a practical prototype formation controller for

meter-scale UAVs is precisely what motivates the modeling and analysis pre-
sented in the following sections (although building such a prototype controller
would still be a project in its own right). However, the modeling and anal-
ysis might be useful for other formation control problems as well (e.g., for
ground or underwater vehicles). As long as the required range and orientation
quantities can be measured and communicated to the appropriate vehicles,

8
 Fig. 6. UAV trajectory illustrating definitions of x, y, z, and r.

the control laws we present may be useful.

3 Modeling UAV formations

Each UAV trajectory is given a kinematic description using (a variant of) the
well-known Frenet-Serret equations of motion, where at each point along the
trajectory one attaches a moving frame (of unit tangent, normal, and binormal
vectors) [1]. For a single UAV, the evolution equation we consider is

ṙ = x
ẋ = yu − zv (1)
ẏ = −xu + zw
ż = xv − yw,

where r is the position of the UAV; x, y, and z are orthonormal vectors

specifying the orientation of the UAV; and u, v, and w are scalar control
inputs (any two of which are sufficient to specify the motion). As shown in
figure 6, x specifies the unit tangent vector to the UAV trajectory, y is normal
to the trajectory, and z (the binormal) completes the orthonormal frame.

Using a kinematic description of the motion allows us to consider the forma-

tion control laws independently of the dynamics of individual vehicles. The
formation control laws we consider would be implemented as simple commands
supplied to each UAV’s on-board autopilot, which has already been designed
to account for the vehicle dynamics. Although optimal energy use is an im-

9
portant criterion for UAVs, our philosophy is to try to provide near-optimal
energy use in the UAVs by studying optimality criteria within the frame-
work of our kinematic models. At this stage in our investigations, however,
we are simply trying to demonstrate models with basic formation-maintaining
behaviour.

Note that the Frenet-Serret frame for the UAV corresponds to the trajectory
followed by the UAV, not to the orientation of the UAV itself. For example, an
aircraft would normally change direction by banking (rather than by yawing,
as would be required if the Frenet-Serret frame described its orientation). For
purposes of the idealized control laws we present, the Frenet-Serret frame is
the one that applies. (The UAV-fixed frame could play an important role,
however, in the control system implementation based on pairs of antennas
and pulsed communication, an issue which merits further investigation.)

To reduce from a three-dimensional Frenet-Serret model to a planar model,

we simply set the controls v and w to zero in equation (1), which eliminates
the dynamical equation for z. In this case, it is assumed that each UAV has
some alternative method of determing the appropriate altitude. We allow for
the possibility that the UAVs are flying at the same altitude, so that collision
avoidance is a consideration.

4 Planar control law analysis

4.1 Control law for a pair of vehicles

Consider two vehicles modeled as point particles moving in the plane. Figure
7(a) illustrates the trajectories of the two vehicles, and their respective planar
Frenet-Serret frames. The control law specifies the steering commands u1 and
u2 for each vehicle. We present a convergence result for the system of two
vehicles. In section 5 we discuss the physical interpretation and motivation for
the control law.

Our model for the pair of vehicles and associated feedback control law is the
following:

10
 ṙ1 = x1 , ṙ2 = x2 ,
ẋ1 = y1 u1 , ẋ2 = y2 u2 ,
ẏ1 = −x1 u1 , ẏ = −x2 u2 ,

2 


r r r
u1 = −η(|r|) − · x1 − · y1 − f (|r|) − · y1 + µ(|r|)x2 · y1 ,
|r| |r| |r|




r r r
u2 = −η(|r|) · x2 · y2 − f (|r|) · y2 + µ(|r|)x1 · y2 , (2)
|r| |r| |r|

where r = r2 − r1 , the functions η(·), µ(·), and f (·) are Lipschitz continuous,
and f (·) satisfies

lim f (ρ) = −∞,

ρ→0
 ρ
lim f (ρ̂)dρ̂ = ∞, for some ρ̃ > 0. (3)
ρ→∞ ρ̃

We further assume that η(|r|) > 0 and µ(|r|) > 0 for all |r| ≥ 0.

Identifying (punctured) R2 with the (punctured) complex plane, we define

r = r2 − r1 = |r|ieiψ ,
x1 = eiθ1 ,
x2 = eiθ2 ,
φ1 = θ1 − ψ,
φ2 = θ2 − ψ, (4)
π
where we note that ψ + 2
is the argument (i.e., angle) of r. We introduce the
variable
ρ = |r|, (5)
and we observe that

r   ∗ 
· x1 = Re ieiψ eiθ1 = sin(θ1 − ψ) = sin φ1 ,
|r|
r
· x2 = sin φ2 ,
|r|
r   ∗ 
· y1 = Re ieiψ ieiθ1 = cos(θ1 − ψ) = cos φ1
|r|
r
· y2 = cos φ2 . (6)
|r|
Figure 7(b) illustrates the definitions of ρ, φ1 , and φ2 .

Using
d
ṙ = ieiψ |r| − |r|eiψ ψ̇ = x2 − x1 = eiθ2 − eiθ1 , (7)
dt

11
 (a) (b)
Fig. 7. Planar trajectories for two vehicles and their respective planar Frenet-Serret
frames: (a) in (r1 , x1 , y1 ), (r2 , x2 , y2 ) coordinates, and (b) in (ρ, φ1 , φ2 ) coordinates.
we find that

ρ̇ = sin φ2 − sin φ1 ,
1
ψ̇ = − (cos φ2 − cos φ1 ) . (8)
ρ
We also have

θ̇1 = u1 = −η(ρ) sin φ1 cos φ1 + f (ρ) cos φ1 + µ(ρ) sin(θ2 − θ1 ),

θ̇2 = u2 = −η(ρ) sin φ2 cos φ2 − f (ρ) cos φ2 + µ(ρ) sin(θ1 − θ2 ). (9)

We thus obtain the system

ρ̇ = sin φ2 − sin φ1 ,
1
φ̇1 = −η(ρ) sin φ1 cos φ1 + f (ρ) cos φ1 + µ(ρ) sin(φ2 − φ1 ) + (cos φ2 − cos φ1 ) ,
ρ
1
φ̇2 = −η(ρ) sin φ2 cos φ2 − f (ρ) cos φ2 + µ(ρ) sin(φ1 − φ2 ) + (cos φ2 − cos φ1 ) .
ρ
(10)

System (10) represents a reduction of the dynamics (2) by the symmetry group

12
SE(2), which is made possible by the fact that the control law of equation (2)
depends only on suitably defined shape variables, i.e., it is invariant under an
action of the symmetry group SE(2). This point of view is made precise and
further explored in section 7.

Consider the Lyapunov function candidate

Vpair = − ln (cos(φ2 − φ1 ) + 1) + h(ρ), (11)

where f (ρ) = dh/dρ. Differentiating Vpair with respect to time along (10) gives

sin(φ2 − φ1 )  
V̇pair = φ̇2 − φ̇1 + f (ρ)ρ̇
cos(φ2 − φ1 ) + 1

sin(φ2 − φ1 )
= − η(ρ) (sin φ2 cos φ2 − sin φ1 cos φ1 ) + 2µ(ρ) sin(φ1 − φ2 )
cos(φ2 − φ1 ) + 1

−f (ρ) (cos φ2 + cos φ1 )

+f (ρ) (sin φ2 − sin φ1 )



−1  sin(φ2 − φ1 ) 2µ(ρ) sin(φ2 − φ1 ) +
η(ρ)
= (sin 2φ2 − sin 2φ1 )
cos(φ2 − φ1 ) + 1 2
+f (ρ) sin(φ2 − φ1 )(cos φ2 + cos φ1 )


−f (ρ)(cos(φ2 − φ1 ) + 1)(sin φ2 − sin φ1 )



−1  sin(φ2 − φ1 ) 2µ(ρ) sin(φ2 − φ1 ) +
η(ρ)
= (sin 2φ2 − sin 2φ1 ) ,
cos(φ2 − φ1 ) + 1 2
(12)

where we have used the identity (see Appendix A)

sin(φ2 − φ1 )(cos φ2 + cos φ1 ) − (cos(φ2 − φ1 ) + 1)(sin φ2 − sin φ1 ) = 0. (13)

We also have the identity (see Appendix A)

 
1
sin(φ2 − φ1 ) sin(φ2 − φ1 ) + (sin 2φ2 − sin 2φ1 )

2
1  2
2 2 2 2
= (cos φ1 + cos φ2 ) (sin φ1 − sin φ2 ) + sin φ1 − sin φ2 . (14)
2

Therefore, provided 2µ(ρ) > η(ρ), ∀ρ ≥ 0, it follows that V̇pair ≤ 0, and

V̇pair = 0 if and only if sin(φ2 − φ1 ) = 0. We can use this calculation to prove
a convergence result.

13
Proposition 1: Consider the system given by equation (10), evolving on
R × T2 , where T2 is the two-torus (i.e., φi + 2π is identified with φi , i = 1, 2).
In addition, assume the following:

(1) η(ρ), µ(ρ), and f (ρ) are Lipschitz continuous on (0, ∞);
(2) f (ρ) = dh/dρ, so that h(ρ) is continuously differentiable on (0, ∞);
(3) limρ→0 h(ρ) = ∞, limρ→∞ h(ρ) = ∞, and ∃ρ̃ such that h(ρ̃) = 0;
(4) η(ρ) > 0, µ(ρ) > 0, and 2µ(ρ) > η(ρ), ∀ρ ≥ 0.

  


Define the set Λ = (ρ, φ1 , φ2)|φ1 − φ2 | = π and 0 < ρ < ∞ . Then any tra-

jectory starting in Λ converges to the set of equilibrium points for system
(10).

Proof: Observe that Vpair given by equation (11) is continuously differentiable

on Λ. By assumption (2) and the form of Vpair , we conclude that Vpair is
radially unbounded (i.e., Vpair → ∞ as |φ1 − φ2 | → π, as ρ → 0, or as
ρ → ∞). Therefore, for each trajectory starting in Λ there exists a compact
sublevel set Ω of Vpair such that the trajectory remains in Ω for all future time.
Then by LaSalle’s Invariance Principle, the trajectory converges to the largest
invariant set M of the set E of all points in Ω where V̇pair = 0 [3]. The set E
in this case is the set of all points (ρ, φ1 , φ2 ) ∈ Ω such that sin(φ1 − φ2 ) = 0,
i.e., such that φ1 = φ2 (since Ω ⊂ Λ). At points in E, the dynamics may be
expressed as

ρ̇ = 0,
φ̇1 = −[η(ρ) sin φ1 + f (ρ)] cos φ1 ,
φ̇2 = −[η(ρ) sin φ1 − f (ρ)] cos φ1 . (15)

If φ1 = ±π/2 and f (ρ) = 0, then the trajectory leaves E. The largest invariant
set contained in E may thus be expressed as

      
π π π π 

M= (ρ, , ), ∀ρ ∪ (ρ, − , − ), ∀ρ ∪ (ρe , 0, 0)f (ρe ) = 0 ∩ Ω,
2 2 2 2 
(16)
which is simply the set of equilibria of the system (10) contained in Ω. 2

A physical interpretation of this convergence result (and the set M) is provided

in subsection 5.4.

14
4.2 Control law for a single vehicle (and fixed beacon)

We now present a control law for a single vehicle based on its position and
orientation relative to a “beacon” fixed at the origin, as illustrated in figure
8(a):

ṙ = x,
ẋ = yu,
ẏ = −xu,




r r r
u = −η(|r|) ·x · y − f (|r|) ·y . (17)
|r| |r| |r|

Define

r = |r|ieiψ ,
x = eiθ ,
ρ = |r|,
φ = θ − ψ. (18)

(The variables ρ and φ are illustrated in figure 8(b).) Then we obtain, analo-
gously to system (10),

ρ̇ = sin φ,


1
φ̇ = −η(ρ) sin φ cos φ − f (ρ) − cos φ. (19)
ρ

Consider the Lyapunov function candidate

Vsingle = − ln(cos φ) + h(ρ), (20)

defined on the set

  
 π π

Λsingle = (ρ, φ)ρ > 0, − < φ < , (21)
 2 2

and where f (ρ) − 1/ρ = dh/dρ. We then compute



sin φ 1
V̇single = φ̇ + f (ρ) − ρ̇
cos φ ρ



sin φ 1 1
= −η(ρ) sin φ cos φ − f (ρ) − cos φ + f (ρ) − sin φ
cos φ ρ ρ
= −η(ρ) sin2 φ. (22)

15
 (a) (b)
Fig. 8. Planar trajectory and Frenet-Serret frame for a single vehicle responding to
a fixed beacon: (a) in (r, x, y) coordinates, and (b) in (ρ, φ) coordinates.

Based on this calculation, we can prove a convergence result.

Proposition 2: Consider the system given by equation (19), evolving on

R×T1 , where T1 is the one-torus (i.e., φ+2π is identified with φ). In addition,
assume the following:

(1) η(ρ) and f (ρ) are Lipschitz continuous on (0, ∞);

(2) f (ρ) = dh/dρ, so that h(ρ) is continuously differentiable on (0, ∞);
(3) limρ→0 h(ρ) = ∞, limρ→∞ h(ρ) = ∞ and ∃ρ̃ such that h(ρ̃) = 0;
(4) η(ρ) > 0, ∀ρ ≥ 0.

Let Λsingle be defined by equation (21). Then any trajectory starting in Λsingle
converges to the set of equilibrium points for system (10), i.e., the set
 
 
 1

Γe = (ρ, φ) f (ρ) − = 0, φ = 0 . (23)
 ρ

Proof: Observe that Vsingle given by equation (20) is continuously differen-

tiable on Λsingle . By assumption (2) and the form of Vsingle , we conclude that
Vsingle is radially unbounded (i.e., Vsingle → ∞ as |φ| → π2 , as ρ → 0, or as
ρ → ∞). Therefore, for each trajectory starting in Λsingle there exists a com-
pact sublevel set Ω of Vsingle such that the trajectory remains in Ω for all future
time. Then by LaSalle’s Invariance Principle, the trajectory converges to the
largest invariant set M of the set E of all points in Ω where V̇single = 0 [3].
The set E in this case is the set of all points (ρ, φ) ∈ Ω such that sin(φ) = 0,
i.e., such that φ = 0 (since Ω ⊂ Λsingle ). At points in E, the dynamics may be
expressed as

ρ̇ = 0,


1
φ̇ = − f (ρ) − . (24)
ρ

16
  
If f (ρ) − ρ1 = 0, then the trajectory leaves E. The largest invariant set
contained in E may thus be expressed as

M = Γe ∩ Ω, (25)

which is simply the set of equilibria of the system (19) contained in Ω. 2

Remark: If the set Γe consists of isolated points, then Proposition 2 implies

that each trajectory starting in Λsingle converges to an equilibrium point. 2

Remark: A result analogous to Proposition 2 holds for trajectories starting

in
  
 π
alt 
Λsingle = (ρ, φ)ρ > 0, |φ| > . (26)
 2
Instead of Vsingle defined by equation (20), the Lyapunov function

alt
Vsingle = − ln(− cos φ) + h(ρ) (27)

is used. 2

5 Physical motivation for the planar control law

In this section we provide some physical motivation for the control law ana-
lyzed in the previous section, as well as a physical interpretation of the conver-
gence result. The objective is primarily to suggest why this control law is the
simplest that could reasonably be expected to perform well. (While the pur-
pose of the previous section was to provide careful mathematical statements,
here we adopt a more pragmatic approach for purposes of conveying physical
intuition.)

5.1 Achieving a common orientation

In system (2), the term µ(|r|)x2 · y1 in the equation for u1 , and the term
µ(|r|)x1 · y2 in the equation for u2 , can be easily interpreted as serving to drive
the two vehicles to a common orientation. In fact, this approach generalizes
for driving n vehicles to a common orientation. For µ > 0 constant, consider
the control law

17
 ṙk = xk ,
ẋk = yk uk ,
ẏk = −xk uk ,
n

uk = µ xj · yk , (28)
j=k

for k = 1, ..., n. Observe that ṙk = xk decouples from the rest of equation (28).

Introducing complex notation, we define

xj = eiθj , (29)

so that the dynamics can be written in θj coordinates as

   ∗  
θ̇j = uj = µ Re eiθk ieiθj =µ sin(θk − θj ). (30)
k=j k=j

It is well known that system (30) is a gradient system with respect to the
energy function
µ
Vorient = − cos(θk − θj ), (31)
2 j,k
i.e.,
∂Vorient
θ̇j = − . (32)
∂θj

The control law (28) thus acts to reorient the vehicles so that they all head
in the same direction. Furthermore, the heading direction for the formation
is determined by an averaging-like process based on the initial orientations.
While these are both laudable properties, there is a weakness to this control
scheme, as it stands, for formation initiation: there is no control of the relative
positions of the vehicles in the formation. We would like to augment this
reorientation scheme with some approach for maintaining swarm cohesiveness,
while avoiding collisions.

5.2 Achieving appropriate separation

To understand how an appropriate vehicle separation is maintained by system

(2), it is helpful to first consider the single-vehicle system given by equation
(17). Suppose for simplicity that there exists a single value ρo > 0 such that
(f (ρo ) − 1/ρo ) = 0. Then under the assumptions of Proposition 2, for almost
all initial conditions (i.e., provided |φ| = π2 initially), system (19) converges
to one of two equilibrium points: either (ρo , 0) or (ρo , π). The corresponding
solutions for system (17) are circular orbits centered at the origin and with

18
radius ρo , and the two (relative) equilibria correspond to clockwise and coun-
terclockwise orbits. The initial condition determines whether the orbit will be
clockwise or counterclockwise, and the initial condition |φ| = π2 represents the
vehicle heading directly toward (or directly away from) the origin.

Now consider the control law given by equation (2), but with µ ≡ 0. Physically,
this control law can be thought of as each vehicle using the control law given
by equation (17), but with the other vehicle treated as the “beacon,” rather
than having a beacon fixed at the origin. (Due to space limitations, we do not
provide any analytic statements for this system, so this discussion is informal.)
This control law tends to appropriately separate the two vehicles; however,
depending on initial conditions, they may either head off in the same direction,
or else circle each other. Either of these behaviors is consistent with the beacon-
circling behavior of a single vehicle governed by the control law of system (17).

We can thus understand physically the various control law terms in system
(2) for a pair of vehicles as serving to achieve a common orientation and an
appropriate separation. This physical interpretation is compatible with many
biological swarming and schooling models, which tend to be characterized by
(1) some mechanism for heading alignment, (2) switching between attraction
or repulsion based on separation distance, and (3) greater responsiveness for
small separations [13].

5.3 Angle quantities appearing in the control law

In the control law for a pair of vehicles, system (2), various dot products
 (rep- 
r
resenting sines and cosines of various angles) appear. The quantities |r| · xi
 
r
and |r| · yi in the expression for ui , i = 1, 2, indicate the orientation of the
ith vehicle relative to the baseline between the two vehicles. These are the
angle-of-arrival quantities that can be sensed from a single transmitted tone
using the two pairs of antennas shown in figure 2. (Note that these are the
only angle quantities required for the single vehicle control law, system (17).)

The quantities x2 · y1 and x1 · y2 can be expressed as





r r r r
x2 · y1 = · x2 · y1 − · y2 · x1 ,
|r| |r| |r| |r|





r r r r
x1 · y2 = · x1 · y2 − · y1 · x2 . (33)
|r| |r| |r| |r|

Thus, the relative orientation between the two vehicles can be determined
from the relative orientations of each vehicle relative to the baseline between

19
them. For our implementation approach based on radio-frequency pulses, the
orientation of a transmitting UAV relative to the baseline between the UAVs
is sensed with the aid of the four cardioid transmit antenna patterns of figure
3(d).

5.4 Interpretation of the convergence result

Consider the control law for a pair of vehicles given by system (2). Suppose
for simplicity that there exists a single value ρo > 0 such that f (ρo ) = 0. Then
the set of equilibria which system (10) can converge to consists of the isolated
point (ρo , 0, 0), the connected set (ρ, π2 , π2 ), and the connected set (ρ, − π2 , − π2 ).
The isolated point (ρo , 0, 0) is easily interpreted: both vehicles are heading in
the same direction, perpendicular to the baseline between them, and separated
by a distance ρo . This stable equilibrium minimizes Vpair . The other sets of
equilibria correspond to the two vehicles heading in the same direction, one
leading the other by a distance ρ (with the two sets distinguished by which
vehicle is in the lead). These equilibria appear to be unstable.

The requirements on f (·) for Proposition 1 to hold, namely

f (ρ) is (Lipschitz) continuous on (0, ∞),

dh
f (ρ) = , with h(ρ̃) = 0,
dρ
 ρ
lim h(ρ) = ρ→∞
ρ→∞
lim f (ρ̂)dρ̂ = ∞, (34)
ρ̃
 ρ
lim h(ρ) = lim f (ρ̂)dρ̂ = ∞, (35)
ρ→0 ρ→0 ρ̃

have some practical implications. For example, if f (ρ) ≈ ρ1 as ρ → ∞, then

equation (34) holds; however, if f (ρ) ≈ ρ12 as ρ → ∞, then it does not. If
f (ρ) is derived from a physical measurement of received signal power from
another UAV, then it would be natural for f (ρ) ≈ ρ12 as ρ → ∞. This means
our model of the physical system, for which Proposition 1 holds, can only
be valid provided the distance between the UAVs is not too large.

Equation (35) implies f (ρ) → −∞ as ρ → 0. Physically, this suggests that the

steering control for the vehicles can become infinite if the separation between
the vehicles is small. Thus, our model of the system is only valid provided the
vehicles remain sufficiently far apart. Although our model can only be valid
for a certain range of distances between the vehicles, from Proposition 1 we
know that for our model, trajectories never leave sublevel sets of Vpair . Thus,
as long as the two vehicles satisfy initial conditions within a sublevel set of

20
Vpair , throughout which the model agrees with the physical system, then the
conclusion of Proposition 1 remains valid.

6 A generalization of the planar control law to n vehicles

The control system given by equation (2) can be generalized to n vehicles as

follows:

ṙk = xk ,
ẋk = yk uk ,
ẏk = −xk uk , (36)

with



 
 rjk rjk rjk
uk =  −η · xk · yk −f (|rjk |) · yk +µxj ·yk , (37)
j=k |rjk | |rjk | |rjk |

where rjk = rk − rj . One possible choice for f (·) is


2 
ro
f (|rjk |) = α 1 − , (38)
|rjk |

and µ, η, and α could also be functions of inter-vehicle distance. Observe that

each vehicle trajectory evolves with its own planar Frenet-Serret equation, and
that the control is simply a sum of terms analogous to those present in system
(2).

A generalization of the energy function Vpair that might play a role in analyzing
the convergence of this system is
n 

Vn = wjk [− ln (cos(θk − θj ) + 1) + h(ρjk )] , (39)
k=1 j<k

where the wjk are positive weights (or weighting functions). We have not yet
proved a convergence result for the n-vehicle system. However, simulation
results, combined with Proposition 1, suggests that it may be possible to
prove some sort of convergence result for the n-vehicle system.

Figure 9 shows the formation-initializing behavior for three different sets of

random initial conditions. Observe that the ultimate heading direction for
the formation is initial-condition dependent. Also, observe that the relative
positions of the vehicles within the formation is somewhat irregular, although
the spacings between neighbors are roughly consistent. It appears from the

21
Fig. 9. Formation initialization for ten vehicles with three different sets of random
initial conditions (in equations (36) and (37), η = µ = α = constant = 0.02).

Normalized Separation Parameter vs. Time

ro

time

(a) (b)
Fig. 10. Formation flying for ten vehicles as the separation parameter is varied:
(a) the vehicle trajectories, and (b) a semilog plot of the normalized separation
parameter vs. time (where the time axis is linear).

simulation results that the control scheme given by equations (36) and (37)
does indeed avoid collisions and maintain swarm cohesiveness.

Figure 10(a) illustrates how a single parameter, common to all the vehicles, can
be varied to produce a global change in the formation. For this simulation,
the length scale parameter (or separation parameter) α in equation (38) is
varied with time as shown in figure 10(b). As α is decreased, the formation
becomes more tight, and as α is increased, the separation between the vehicles
increases.

Figure 11 illustrates “leader-following” behavior. The leader, i.e., the vehicle

represented by the dashed path, follows a prescribed steering program, and
is unaffected by the other vehicles. However, the other vehicles are influenced
both by the leader and by each other. (Results are shown for two different

22
Fig. 11. Formation initialization for ten vehicles, one of which (dashed) follows a
prescribed steering program unaffected by the other vehicles (for two different sets
of random initial conditions).

sets of random initial conditions.) The influence of the leader on the formation
behavior is evident; however, the leader need not be physically in front of the
other vehicles. Indeed, this is by no means the only approach for generating
leader-following behavior; nor is it necessarily the best approach. However, it
clearly illustrates the possibility of allowing the control law of equations (36)
and (37) to maintain the basic formation, while some additional control action
guides the formation as a whole.

7 Lie group formulation and relative equilibria

7.1 Two-vehicle problem

There is a natural Lie group structure evident in system (2). In this subsec-
tion, we discuss how the formation control problem for two vehicles can be
formulated as a “shape-control” problem in the Lie group setting [4–6]. We
can consider the dynamics of system (2) as evolving on a (collision-free) con-
figuration submanifold Mconf ig ⊂ G × G, where G = SE(2) is the special
Euclidean group in the plane. Specifically, if g1 , g2 ∈ G are represented as
   
 x1 y1 r1   x2 y2 r2 
   
   
g1 =  , g2 =  , (40)
   
   
0 0 1 0 0 1

23
then   


Mconf ig = (g1 , g2) ∈ G × G  r1 = r2 . (41)


(From Proposition 1, we can conclude that for initial conditions in Mconf ig ,

the dynamics evolve in Mconf ig for all future time, provided the controls given
by equation (2) are used. However, for purposes of this section, we are primar-
ily interested in identifying relative equilibria without restriction to a partic-
ular control law.) We can express the dynamics given by equation (2) as

ġ1 = g1 ξ1 = g1 (A0 + A1 u1 ),
ġ2 = g2 ξ2 = g2 (A0 + A1 u2 ), (42)

where ξ1 , ξ2 ∈ g = the Lie algebra of G, and the matrices A0 and A1 (which

generate g under Lie bracketing) are given by
   
 0 0 1   0 −1 0 
   
   
A0 =  0 0 0  , A1 =  1 0 0  . (43)
   
   
0 0 0 0 0 0

We define
g = g1−1g2 , (44)
and observe that
    
 xT1 −r1 · x1   x2 y2 r2   x1 · x2 x1 · y2 (r2 − r1 ) · x1 
    
    
g= 
 y1T −r1 · y1 

 

= 
 y1 · x2 y1 · y2 (r2 − r1 ) · y1 

.
    
0 0 1 0 0 1 0 0 1
(45)
Similarly,
 
 x1 · x2 x2 · y1 −(r2 − r1 ) · x2 
 
 
g −1 = g2−1g1 =  y2 · x1 y1 · y2 −(r2 − r1 ) · y2  . (46)
 
 
0 0 1

Let gij denote the elements of the matrix g, let g ij denote the elements of the
matrix g −1 , and let
 
2 2
r= g13 + g23 = (g 13 )2 + (g 23 )2 . (47)

We have the following relationships among the gij and g ij :

24
 g11 = g22 = g 11 = g 22 ,
g12 = −g21 = g 21 = −g 12 , (48)

and
2 2
g11 + g12 = 1. (49)

Remark: We can express u1 and u2 as defined by equation (2) as

   
g13 g23 g23
u1 (g) = −η(r) 2
+ f (r) + µ(r)g21 ,


r 

r 
g 13 g 23 g 23
u2 (g) = −η(r) 2
+ f (r) + µ(r)g 21. (50)
r r

Equations (42), (44), and (50) are sufficient to conclude that the closed-loop
dynamics are G-invariant. Although we do not require the specific control law
given by equation (50) for the (relative) equilibrium analysis presented in this
subsection, we do assume that the control law is G-invariant, in addition to
ensuring that the dynamics evolve in the collision-free submanifold. 2

Now,

ġ = −g1−1 ġ1 g1−1g2 + g1−1ġ2

= −g1−1 g1 ξ1 g + g1−1 g2 ξ2
= −ξ1 g + gξ2
= g(ξ2 − g −1ξ1 g)
= g(ξ2 − Adg−1 ξ1 )
= gξ, (51)

where ξ = ξ2 − Adg−1 ξ1 ∈ g. If the feedback controls depend only on the shape

variable g, then ξ = ξ(g) and (51) evolves on the shape space Mconf ig /G.

We refer to (51) as the reduced dynamics. Equilibria of the reduced dynamics

correspond to relative equilibria of the full dynamics in Mconf ig . The equilibria
ge of the reduced dynamics are given by setting

ξ(ge ) = ξ2 (ge ) − ge−1 ξ1 (ge )ge = 0. (52)

Equation (52) is equivalent to

ge ξ2 (ge ) = ξ1 (ge )ge , (53)

which (dropping the “e” subscript) becomes

25
      
 g11 g12 g13   0 −u2 1   0 −u1 1   g11 g12 g13 
     
     

 −g12 g11 g23 

 u2 0 0 =
  u1 0 0 
 −g12 g11 g23 

     
0 0 1 0 0 0 0 0 0 0 0 1
   
 g12 u2 −g11 u2 g11 
 g12 u1 −g11 u1 1 − g23 u1 
 
 
   

 g11 u2 g12 u2 −g12  =
  g11 u1 g12 u1 g13 u1 .

(54)
   
0 0 0 0 0 0

2 2
Since g11 + g12 = 1, at equilibrium we must have

u2 = u1 ,
g11 = 1 − g23 u1 ,
g12 = −g13 u1 . (55)

But equation (52) is also equivalent to

ξ2 (ge )ge−1 = ge−1 ξ1 (ge ), (56)

which (by an analogous computation) leads to

u2 = u1 ,
g11 = 1 − g 23 u2 ,
g12 = g 13 u2 . (57)
2 2
Using g11 + g12 = 1, from equation (55) we obtain

1 = (1 − g23 u1 )2 + g13
2 2
u1
2 2 2 2
= 1 − 2g23 u1 + g23 u1 + g13 u1
  
2 2
0 = u1 g13 + g23 u1 − 2g23
2g23
u1 = 2 2
, or u1 = 0. (58)
g13 + g23

There are thus two distinct equilibrium cases to analyze: u1 = 0 and u1 =

2g23 /r 2 . First, consider the case u1 = 0. Then from equations (55) and (57),
we conclude

u2 = u1 = 0,
g11 = 1,
g12 = 0. (59)

26
For such an equilibrium, x1 = x2 , so we also have

g13 = −g 13 ,
g23 = −g 23 . (60)

However, the relationship between x1 and r = r2 − r1 is arbitrary.

Next, consider the case u1 = 2g23 /r 2 = 0. We must assume that r > 0 so that
u1 is well-defined. Then from equations (55) and (57), we conclude

u2 = u1 = 2g23 /r 2 ,
g23 = g 23 ,
g13 = −g 13 ,
2
g11 = 1 − 2g23 /r 2 ,
g12 = −2g13 g23 /r 2 . (61)

With some further calculation (see Appendix B), one can show that the corre-
sponding relative equilibrium consists of the two vehicles moving on the same
circular orbit, separated by a chord of fixed length.

The notion of shape space associated to a symmetry group is useful for de-
scribing the evolution of system (42) [4–6]. To summarize, equation (42) de-
scribes motion in the configuration space. The variable g = g1−1g2 plays the
role of a shape variable, and evolves on the (collision-free) shape submani-
fold Mshape = Mconf ig /G. The reduced dynamics on shape space are given
by equation (51). Equilibria ge of the reduced dynamics correspond to equi-
librium shapes. The configuration variables can be expressed in terms of the
shape variable as
(g1 , g2 ) = (g1 , g1 g), (62)
and if g = ge (i.e., the shape is an equilibrium shape), then the trajectory in
the configuration space is a relative equilibrium.

Remark: The collision-free submanifold Mshape is isomorphic to R × T2 , the

set which appears in the statement of Proposition 1. Indeed, Proposition
1 can be understood as a convergence result for the shape dynamics. 2

Remark: The Lyapunov function Vpair given by equation (11) is, as expected,
also G-invariant, and can be expressed as
 
Vpair = − ln 1 − (g13 g 13 + g23 g 23 )/r 2 + h(r). 2 (63)

27
7.2 The n-vehicle problem

The notions of configuration space and shape space described above for the
2-vehicle problem generalize naturally to n vehicles. The configuration space
consists of n copies of G = SE(2), and an appropriate non-collision manifold
analogous to Mconf ig can be defined. The dynamics in configuration variables
can be expressed as

ġ1 = g1 ξ1 , ġ2 = g2 ξ2 , ... ġn = gn ξn , (64)

where ξ1 , ξ2 , ... ξn ∈ g have the form

ξj = A0 + A1 uj , ∀j = 1, ..., n. (65)

We define the shape variables

g̃j = g1−1gj , j = 2, ..., n, (66)

which evolve on the reduced (shape) space consisting of a product of n − 1

copies of G. (It is also possible to define shape variables in other combina-
−1
tions; e.g., g̃j = g̃j−1 gj , j = 2, ..., n [5].) Here we have assumed that ξ1 , ξ2 ,
... ξn depend only on the reduced variables g̃2 , g̃3 , ...g̃n (and we note that this
assumption can indeed be verified for the control law given by equation (36)).

By calculations analogous to those in the previous subsection, we are led to

the conclusion that at equilibrium (in shape space),

u1 = u2 = ... = un . (67)

Proposition 3: Consider the dynamics given by equations (64) and (65),

evolving on the collision-free submanifold
 n copies  
  

Mconf ig = (g1 , g2 , ..., gn ) ∈ G × G × ... × G rjk = rk −rj = 0, 1 ≤ j = k ≤ n ,

(68)
where G = SE(2) (and rj is defined as in equation (40) for j = 1, ..., n).
Assume that the controls u1 , u2, ...un depend only on the shape variables given
by equation (66) (i.e., the controls are G-invariant). Then for equilibrium
shapes (i.e., for relative equilibria of the dynamics (64) on configuration space)
u1 = u2 = ... = un , and there are only two possibilities:

(a) u1 = u2 = ... = un = 0 at equilibrium, in which case a relative equilib-

rium consists of all vehicles heading in the same direction (with arbitrary
relative positions within the formation), or

28
 (a) (b)
Fig. 12. Relative equilibria for the n-vehicle problem, illustrated for n = 5 (arrows
indicate tangent vectors to the vehicle trajectories): (a) for u1 = u2 = ... = un = 0,
and (b) for u1 = u2 = ... = un = 0.

(b) u1 = u2 = ... = un = 0, in which case a relative equilibrium consists of all

vehicles moving on the same circular orbit, with arbitrary cordal distances
between them.

Proof: Omitted due to space constraints, but essentially follows the same
steps indicated in the previous subsection for the two-vehicle problem. 2

Figure 12 illustrates the two types of relative equilibria for the n-vehicle prob-
lem described in Proposition 3.

Thus, the control system (2), or system (36), can be naturally understood in
the Lie group setting. This suggests that shape space notions for Lie groups
may play an important role in formation control problems. We have shown
how to characterize the set of all possible relative equilibria for any choice
of G-invariant control law. We are now in the process of investigating the
next obvious issue: how to choose controls that stabilize particular relative
equilibria.

8 Conclusions and future research directions

Our work on formation control using models based on the Frenet-Serret equa-
tions of motion is still in its early stages. Areas of current and future work
include developing control laws and proving stability results for formations of
n vehicles, investigating continuum limits in which the number of “vehicles”
becomes infinite, and investigating formation-control problems in the setting
of the three-dimensional Frenet-Serret equations. On the practical side, there
is also an effort underway to develop the hardware required for implementation
of these types of control laws for meter-scale UAVs, and here the development

29
of the analog VLSI processor is one of the main challenges. An essential theme
of this work is that jointly considering control law design and implementation
issues has the best chance of ultimately leading to a prototype formation con-
trol system implementation for meter-scale UAVs.

9 Acknowledgements

The authors would like to thank Jeff Heyer, Ted Roberts, and Hal Levitt of
the Naval Research Laboratory, Washington, DC for valuable discussions.

References

[1] W.M. Boothby, An introduction to differentiable manifolds and Riemannian

geometry, 2nd ed. Orlando: Academic Press, 1986.

[2] V. Jurdjevic, Geometric Control Theory, Cambridge: Cambridge University

Press, 1997.

[3] H. Khalil. Nonlinear Systems. New York: Macmillan Publishing Co., 1992.

[4] R.G. Littlejohn and M. Reinsch, “Gauge fields in the separation of rotations
and internal motions in the n-body problem,” Review of Modern Physics, Vol.
69, No. 1, pp. 213-275, 1997.

[5] P.S. Krishnaprasad and D.P. Tsakiris, “G-Snakes: Nonholonomic Kinematic

Chains on Lie Groups,” Proc. 33rd IEEE Conf. Decision and Control, pp. 2955-
2960, IEEE, New York, 1994. (see also Institute for Systems Research technical
report ISR TR 94-27, 1994).

[6] F. Zhang and P.S. Krishnaprasad, “Center of Mass of a System of Particles in

G” Preprint, 2002.

[7] L.-S. Wang and P.S. Krishnaprasad, “Gyroscopic control and stabilization,”
Journal of Nonlinear Science, Vol. 2, pp. 367-415, 1992.

[8] P. Ogren, E. Fiorelli, and N.E. Leonard, “Formations with a Mission: Stable
Coordination of Vehicle Group Maneuvers,” Proc. MTNS, to appear, 2002.

[9] J. Toner and Y. Tu, “Flocks, herds, and schools: A quantitative theory of
flocking,” Phys. Rev. E, Vol. 58, No. 4, pp. 4828-4858, 1998.

[10] H. Levine and W.-J. Rappel, “Self-organization in systems of self-propelled

particles,” Phys. Rev. E, Vol. 63, No. 1, pp. 017101-1 to 017101-4, 2000.

30
[11] A. Czirók, M. Matsushita, and T. Vicsek, “Theory of periodic swarming of
bacteria: Application to Proteus mirabilis,” Phys. Rev. E, Vol. 63, No. 3, pp.
031915-1 to 031915-11, 2001.

[12] E.W. Justh and F.J. Kub, “Analog CMOS High-Frequency Continuous Wavelet
Transform Circuit,” Proc. IEEE Int. Symp. Circuits and Systems, Vol. 2, pp.
188-191, 1999.

[13] D. Grünbaum, “Schooling as a strategy for taxis in a noisy environment,” in

Animal Groups in Three Dimensions, J.K. Parrish and W.M. Hamner, eds.,
Cambridge University Press, 1997.

Appendix A

Derivation of equation (13):

sin(φ2 − φ1 )(cos φ2 + cos φ1 ) − (cos(φ2 − φ1 ) + 1)(sin φ2 − sin φ1 )

= (sin φ2 cos φ1 − cos φ2 sin φ1 )(cos φ1 + cos φ2 )
−(cos φ2 cos φ1 + sin φ2 sin φ1 )(sin φ2 − sin φ1 )
−(sin φ2 − sin φ1 )
= sin φ2 cos2 φ1 + sin φ2 cos φ1 cos φ2 − sin φ1 cos φ1 cos φ2 − sin φ1 cos2 φ2
− sin φ2 cos φ1 cos φ2 − sin2 φ2 sin φ1 + sin φ1 cos φ1 cos φ2 + sin2 φ1 sin φ2
−(sin φ2 − sin φ1 )
= sin φ2 − sin φ1 − (sin φ2 − sin φ1 )
= 0. (69)

Derivation of equation (14):

31
  
1
sin(φ2 − φ1 ) sin(φ2 − φ1 ) + (sin 2φ2 − sin 2φ1 )
2 
= (sin φ2 cos φ1 − cos φ2 sin φ1 ) (sin φ2 cos φ1 − cos φ2 sin φ1 )

+(sin φ2 cos φ2 − cos φ1 sin φ1 )

= sin2 φ2 cos2 φ1 − sin φ1 sin φ2 cos φ1 cos φ2

− sin φ1 sin φ2 cos φ1 cos φ2 + sin2 φ1 cos2 φ2
+ sin2 φ2 cos φ1 cos φ2 − sin φ1 sin φ2 cos2 φ2
− sin φ1 sin φ2 cos2 φ1 + sin2 φ1 cos φ1 cos φ2
 
= cos φ1 cos φ2 sin2 φ1 − 2 sin φ1 sin φ2 + sin2 φ2
 
1 2 1
+ cos2 φ1 sin φ2 − sin φ1 sin φ2 + sin2 φ1
2 2
 
2 1 2 1 2
+ cos φ2 sin φ1 − sin φ1 sin φ2 + sin φ2
2 2
1 1
+ cos2 φ1 sin2 φ2 − cos2 φ1 sin2 φ1
2 2
1 1
+ cos2 φ2 sin2 φ1 − cos2 φ2 sin2 φ2
2 2
1
= (cos φ1 + cos φ2 )2 (sin φ1 − sin φ2 )2
2

   
+ cos2 φ2 − cos2 φ1 sin2 φ1 + cos2 φ1 − cos2 φ2 sin2 φ2

1
= (cos φ1 + cos φ2 )2 (sin φ1 − sin φ2 )2
2

  
+ cos2 φ2 − cos2 φ1 sin2 φ1 − sin2 φ2

1  2
= (cos φ1 + cos φ2 )2 (sin φ1 − sin φ2 )2 + sin2 φ1 − sin2 φ2 . (70)
2

Appendix B

Here we show that the equilibrium equation (61), for g23 = 0, implies that
the corresponding relative equilibrium consists of the two vehicles moving on
the circular orbit, separated by a chord of fixed length. The first observation
is that because u1 = u2 = constant, both vehicles traverse circular orbits of

32
radius 1/|u1|. For the first vehicle, we define

Q1 = x1 y1 ∈ SO(2), (71)

so that  
 0 −u1 
Q̇1 = Q1  , (72)
u1 0
which can be integrated with respect to time to give
 
 cos(u1t) − sin(u1 t) 
Q1 (t) = Q1 (0)  . (73)
sin(u1 t) cos(u1 t)

The equation for r1 , the position of the first vehicle as a function of time,
becomes  
 cos(u1 t) 
ṙ1 = Q1 (0)  , (74)
sin(u1 t)
which can be integrated with respect to time to give
  
1  sin(u1 t)  
r1 (t) = Q1 (0)   + c1  , (75)
u1 − cos(u1 t)

where c1 is a constant vector. We thus obtain

   
 2  2

 1 
  1 sin(u1 t)   1
r1 (t) − Q1 (0)c1  =  Q1 (0) 
 
   = , (76)
 
u1  u1 − cos(u t) 
1
u21

which shows that the trajectory of the first vehicle lies on a circle of radius
1/|u1| centered at (1/u1 )Q1 (0)c1 . Futhermore,
  
1  0  
r1 (0) = Q1 (0)   + c1  . (77)
u1 −1

The corresponding calculation for the second vehicle gives

  
1  0 
r2 (0) = Q2 (0) 


 + c2  . (78)
u1 −1

33
A relationship between c1 and c2 arises from the formula g2 (t) = g1 (t)g, where
 
 1 − g23 u1 −g13 u1 g13 
 
 
g= 
 g13 u1 1 − g23 u1 g23 

(79)
 
0 0 1

is the equilibrium shape. For convenience, we denote


Q b
g= , (80)
0 0 1

and from g2 (t) = g1 (t)g, it follows that

Q2 (t) = Q1 (t)Q,
r2 (t) = Q1 (t)b + r1 (t). (81)

Then

r2 (0) = Q1 (0)b + r1 (0)

  
1  0  
= Q1 (0)b + Q1 (0)   + c1 
u1 −1
   
 1  0  
= Q1 (0) b +   + c1   , (82)
u1 −1

and so
      
1  0    1  0  
Q2 (0)   + c2  = Q1 (0) b +   + c1   . (83)
u1 −1 u 1 −1

This leads us to conclude

     
1  0   1  0  
b+   + c1  = Q   + c2  . (84)
u1 −1 u1 −1

Next, we make use of the specific form of g, namely

34
  
 g13 
b= ,
g23
 
 1 − g23 u1 −g13 u1 
Q= , (85)
g13 u1 1 − g23 u1

to observe that    
1  0  1  0 
b+  = Q . (86)
u1 −1 u1 −1
Combining equations (84) and (86) then gives

c1 = Qc2 . (87)

The center of the circular orbit for the first vehicle was shown above to be
(1/u1)Q1 (0)c1 , and likewise, the center of the circular orbit for the second
vehicle is
1 1 1
Q2 (0)c2 = Q1 (0)Qc2 = Q1 (0)c1 . (88)
u1 u1 u1
Thus, the two vehicle trajectories traverse the same circle.

Note that the chordal distance between the vehicles is given by


2 2
r= g13 + g23 , (89)

but the diameter of the circular trajectory is

2 g 2 + g23 2
d= = 13 . (90)
|u1 | |g23 |

Thus, d = r if and only if g13 = 0.

35