untitled - tro-chung-2853610

IEEE TRANSACTIONS ON ROBOTICS

Robotic Herding of a Flock of Birds Using

an Unmanned Aerial Vehicle

Aditya A. Paranjape

, Soon-Jo Chung

, Senior Member, IEEE

, Kyunam Kim

and David Hyunchul Shim

, Senior Member, IEEE

Abstract

—In this paper, we derive an algorithm for enabling

a single robotic unmanned aerial vehicle to herd a flock of birds

away from a designated volume of space, such as the air space

around an airport. The herding algorithm, referred to as the

waypoint algorithm, is designed using a dynamic model of bird

flocking based on Reynolds’ rules. We derive bounds on its per-

formance using a combination of reduced-order modeling of the

flock’s motion, heuristics, and rigorous analysis. A unique contri-

bution of the paper is the experimental demonstration of several

facets of the herding algorithm on flocks of live birds reacting to

a robotic pursuer. The experiments allow us to estimate several

parameters of the flocking model, and especially the interaction

between the pursuer and the flock. The herding algorithm is also

demonstrated using numerical simulations.

Index Terms

—Aerial robotics, biologically inspired robots, field

robots, motion control.

I. I

NTRODUCTION

IRD AND OTHER wildlife collisions with aircraft cause

well over $1.2 billion in damages to the aviation industry

worldwide [1], [2]. The Federal Aviation Administration (FAA)

documented 142 000 wild-life strikes at U.S. airports between

1990 and 2013, with birds being involved in 97% of the re-

ported cases [3]. A large number of passive and active methods

are currently used for deterring birds from entering the airspace

around airports [1], [4], [5], which depend on the type of birds

encountered at the airport. Passive techniques typically work

by curtailing the food and water resources around the airfield

or laying bird-repellent grass swards. On the other hand, active

techniques include the use of live ammunition and flares at air-

ports. Usually, a combination of the aforementioned techniques

Manuscript received October 12, 2017; revised April 4, 2018; accepted April

7, 2018. This paper was recommended for publication by Guest Editor P. Dames

and Editor F. Park upon evaluation of the reviewers’ comments. This work was

supported in part by the National Science Foundation CAREER Award NSF

IIS 1253758 & 1664186 and in part by the California Institute of Technology.

(Corresponding author: Soon-Jo Chung.)

A. A. Paranjape is with the Department of Aeronautics, Imperial College

London, London SW7 2AZ, U.K. (e-mail:

a.paranjape@imperial.ac.uk).

S.-J. Chung and K. Kim are with the Graduate Aerospace Laborato-

ries, California Institute of Technology, Pasadena, CA 91125 USA (e-mail:

sjchung@caltech.edu; knkim@caltech.edu).

D. H. Shim is with the Department of Electrical Engineering, Korea Advanced

Institute of Science and Technology, Daejeon 305-701, South Korea (e-mail:

hcshim@kaist.ac.kr).

This paper has supplementary downloadable material available at

http://ieeexplore.ieee.org.

Color versions of one or more of the figures in this paper are available online

at http://ieeexplore.ieee.org.

Digital Object Identifier 10.1109/TRO.2018.2853610

Fig. 1. Setting for the problem addressed in the paper.

is required for effective bird control, and even that effectiveness

is known to be limited [4]. The only proven lasting way is to

use birds of prey [5], but it is considerably difficult to train and

control real birds. Further, the most effective performers (e.g.,

peregrine falcons) are endangered species. As an alternative,

remote-controlled airplanes resembling birds of prey have been

tested using skilled human pilots [6].

In this paper, we develop a novel robotic herding algorithm

for birds flying near airports using unmanned aerial vehicles

(UAVs). The present paper is based on the preliminary work

reported in [7], [8], and differs in its analysis of the stability of

flocks, the analysis of the performance of herding algorithms,

and the experimental demonstration of the principles underly-

ing the herding algorithm. A graphical prelude to this paper is

depicted in Fig. 1.

A. Overview of the Literature

Modeling the behavior of flocks is the starting point for the

development of herding algorithms. Reynolds [9] formulated

simple motion behaviors (collision avoidance, velocity match-

ing, and flock centering) for creating computer animations of

bird flocks and simulating the stable collective motion seen

therein. Reynolds’ model has formed the basis for other flocking

models such as the self-propelled particle model [10], [11] and

a leader-based modification of Reynolds’ model [12]. Along-

side theoretical modeling, attempts have been made to extract

flocking rules, aggregate patterns, and ordering from empirical

studies on large flocks of birds and fish [13], [14]. The reader

is referred to [15] for a detailed review of collective animal

behavior.

See http://www.ieee.org/publications

standards/publications/rights/index.html for more information.

IEEE TRANSACTIONS ON ROBOTICS

Over the years, several distributed, scalable coordination

algorithms have been developed while trying to obtain

mathematical guarantees on the stability of the formation

[16]–[22]. This has been accompanied by parallel work on un-

derstanding the presence of order and phase transitions in flocks

[23], building upon analogies between flocks on the one hand,

and fluid and magnetic systems on the other. Flocking dynamics

described by Reynolds’ rule are known to be asymptotically

stable under fairly weak conditions on the topology of the

underlying graph [17], [18], [24], [25]. Stronger results, such as

exponential stability, have been found for linear time-varying

consensus protocol for single integrator systems [26], in the

context of synchronization for second-order Euler–Lagrange

systems [20]–[22], and using tools from dynamical systems

theory for time-invariant, undirected graph topologies in

second-order, two-dimensional (2-D) flocking dynamics [27].

Preliminary results on exponential stability of flocks under tree

and star topology constraints are presented in [8].

Modeling the response of a flock to external pursuers is es-

sential for developing herding models and strategies. Evasive

strategies used by flocks against one or more predators are pre-

sented in [28], [29]. Escape waves, as a means for formulating

the evasive response, have been examined for starling flocks [30]

and fish schools [31]. A simulation study of agitation waves in

starling flocks is presented in [32]. The dynamics between a

school of fish and a pursuer are shown to depend on local, fast-

time scale predator–prey interactions [33]. The expected size

of flocks is correlated with the likelihood of predation: Com-

pact and large flocks occur in areas with higher predation, and

vice-versa [34].

Early work on herding algorithms used geometric principles

to identify the relative position and posture of the shepherd with

respect to the flock [35]–[37], in order to first confine the flock

within a well-defined spatial zone and then impose trajectory

tracking on the confined flock [38], [39]. It is generally well

known that these algorithms may perform poorly when a single

shepherd is employed [37]. Heuristic herding strategies used by

solitary sheep dogs were modeled in [40] and used to design a

strategy that enforces confinement to achieve herding. However,

the design was not analyzed rigorously, which leaves open the

question of its limitations and performance guarantees.

B. Objectives and Contributions

The primary objective of this paper is to design a strategy

for diverting and herding a flock of birds away from a specified

region. This region is modeled conservatively as a cylindrical

volume around an airport located on the ground. Our algorithm

can be extended readily to the case where the specified region

is spherical, as depicted in Fig. 1, rather than cylindrical.

We present a novel herding technique, called the

-waypoint

herding algorithm. The robotic UAV interacts with the flock

by positioning itself sequentially at a periodically refreshed set

points. It relies on the inherent stability of the flocking

dynamics to prevent fragmentation of the flock, and the

points

are chosen to maximise the deflection of the flock’s flight path.

We demonstrate that the algorithm also leads to a reduction in

the physical space occupied by the flock, measured in terms of

its radius. Importantly, the technique works effectively with a

single robotic UAV, and can be generalized readily for multiple

UAVs.

An important contribution of the paper is the series of ex-

periments performed on live birds in order to identify some

of the parameters of the flocking dynamic model and identify

the nature of the evasive action taken by birds in response to

a robotic pursuer. These are important steps in validating the

design premise of the

-waypoint herding algorithm. The herd-

ing algorithm is demonstrated through simulations on a flocking

model similar to that estimated from the experiments.

The problem addressed in the paper is similar to [36]. A ma-

jor difference, though, is a combination of the rigorous analysis

accompanying the algorithm and the experimental demonstra-

tion on live birds. Another difference is the non-zero minimum

speed of the flock, which is a consequence of the birds needing

a certain minimum speed to stay aloft.

We use a standard flocking model, similar to Reynolds [9],

[17], augmented with evasion laws similar to [28], [29]. It is

assumed that the pursuer has access to real-time data about the

flock, such as that provided by avian radars [41].

C. Organization

The paper is organized as follows. In Section II, we present

the problem formulation. Conditions for exponential stability of

flocks are derived in Section III. The pursuer–flock interaction is

studied analytically in Section IV, and the

-waypoint herding

algorithm is presented in Section V. The performance of the

algorithm is analyzed rigorously in Section VI. Experiments

conducted on live flocks are reported in Section VII, while

numerical simulations are described in Section VIII.

II. P

ROBLEM

ORMULATION

A. Preliminaries

Consider a flock of

(usually

) birds. We denote the

position and the velocity of the

th bird by

∈

and

∈

respectively. The vector between the

th and

th birds is denoted

−

. We use the subscript “p” for the pursuer, so

that

denotes its position vector, and

−

is the

vector from the pursuer to the

th bird. Given a vector

,we

denote unit vector along

Let

com

denote the communication range for the interaction

between two birds. The neighborhood of the

th bird is defined

using the standard Euclidean distance as

{

≤

−

≤

com

}

(1)

and it is assumed that two birds interact only if their distance is

less than or equal to

com

.Thesetofbirds(

), thus, forms a

graph

)

where

{

,..., n

}

{

(

i, j

)

∈V×V|

∈J

⊆N

}

card

(

(2)

Note that if

for all

, the graph is undirected. Otherwise,

it is directed. The incidence matrix of the graph is denoted as

PARANJAPE

et al.

: ROBOTIC HERDING OF A FLOCK OF BIRDS USING AN UNMANNED AERIAL VEHICLE

Fig. 2. Important distance variables in the flocking model. Green dashed lines

are distances related to neighboring birds and red dash-dot lines are distances

related to the pursuer. Note that

com

and

fear

are unrelated.

agg

is smaller

than

fear

∈

. Recall that the

(

i, j

)

th entry of

is 1 if the

edge is incoming at

−

if outgoing at

, and 0 otherwise.

An undirected edge is treated as two separate directed edges in

this formulation of

. We denote by

Δ(

)

the diagonal matrix

formed by the elements of the tuple

. Finally, we define the

centroid and the radius of the flock as follows:

max

−

(3)

B. Flock Dynamics

The dynamics of an individual (

th) bird are described

by a nonlinear, second-order differential equation based on

Reynolds’ rules [9] and augmented with an evasive response

∈J

−

safe

∈J

(

−

)

(

−

(

)

(4)

where

safe

denotes the steady-state distance between two adja-

cent members of the flock;

denotes the preselected, steady ve-

locity of each member of the flock; and

(

−

)

denotes the evasive response to the pursuer. We assume that

lies in the horizontal plane.

Fig. 2 summarizes the important distance variables that ap-

pear in the model. The terms

safe

and

com

have been defined

already. The terms

fear

and

agg

(

fear

) refer to critical dis-

tances in the bird–pursuer interaction, and we assume that both

of these quantities are known for a given flock. The flock re-

sponds to a pursuer only when the pursuer is within a radius

fear

of a member of the flock. Within

fear

, the evasive behav-

ior takes two different forms.

1) If the pursuer is within

[

agg

fear

]

, the bird tries to ac-

celerate radially away from the pursuer.

2) If the pursuer is within

agg

, the bird tries to out-maneuver

the pursuer by turning and/or climbing rapidly.

Fig. 3. Example showing the two loci of candidate target points, and the

chosen target point

div

. Being vertical lines, the loci appear as points in this

top view.

The behavior detailed above was observed in experiments

with live birds, which are described in Section VII. Since the

out-turning or 3-D behavior can have adverse implications for

the stability of the flock, we treat

agg

as a lower bound for

the permissible distance between the pursuer and the flock. We

model

(

)

as follows:

(

fear

and

otherwise

(5)

and we impose the restriction that

≥

agg

for all

where

is an arbitrarily chosen constant.

C. Herding Objectives

The spatial volume that needs to be kept free of birds is

referred to, hereafter, as the protected zone (PZ). We assume that

PZ is cylindrical with radius

. We assume that the birds fly

along a constant, preselected heading,

, when not disturbed by

a pursuer. This is true, for instance, for flocks flying to migration

grounds considerably far from PZ. It is clear that the pursuer

only needs to move the flock to a point from which its flight

path (along

) would no longer cross PZ. We denote this target

point as

div

(

)

, noting that its exact position may change with

time as described presently.

We define the global coordinate frame with its origin placed

at the centre of PZ, and its axes pointing north, east, and up,

respectively. Let

(

)

denote the instantaneous altitude of the

flock. We start by constructing two vertical lines (in the global

frame), which serve as loci for all possible target points. Recall

that

in (4) is the predetermined nominal flock velocity, which

satisfies

where

is the unit vector pointing upwards

in the global frame. We define the unit vector

⊥

, which satisfies

⊥

. The two candidate loci are then given by

cand

(

)

⊥

where

∈

, and

s>R

is a suitably chosen constant. We denote

div

.Of

these candidate loci, we select the one closest to

(the moment at which the herding commences), as illustrated in

Fig. 3. Finally, at each

, we set the instantaneous target waypoint

on the chosen locus as

div

=(+

−

)

div

⊥

(

)

.Ifthetwo

loci are equidistant from

, then any of the two loci can be

chosen. However, this choice persists for the remainder of the

herding operation. This selection of herding target points is a

IEEE TRANSACTIONS ON ROBOTICS

logical extension from 2-D to 3-D when the herding algorithm

does not seek to control the altitude of the flock.

The objective of the herding algorithm is to prescribe a trajec-

tory

(

)

for the pursuer, which enables it to do the following

functions.

1) Move the center of gravity (CG) of the flock to

div

finite time.

2) Avoid fragmentation of the flock.

3) Keep the flock outside the PZ during the course of herding.

III. S

TABILITY

NALYSIS OF THE

LOCK

In this section, we determine the conditions for exponential

stability of the flocking dynamics. These conditions can be used

to select the gains and the underlying graph in (4) for analyti-

cal investigation when sufficient empirical data is not available

to determine these parameters. The resulting robustness of the

flock implies that the pursuer is free to approach the flock

from

any direction

. As long as it maintains a certain minimum dis-

tance between itself and the flock (see Section IV), the flock

will not undergo fragmentation.

A. Snapshot Dynamics, Steady States, and Linearization

We define two column vectors

∈

, formed by per-

muting the components of

and

, respectively,

∀

,...,

]

and

is constructed in a similar manner. There exists a permu-

tation matrix, denoted by

∈

, such that

⎡

⎢

⎣

⎤

⎥

⎦

⎡

⎢

⎣

⎤

⎥

⎦

−

Ignoring the pursuer-dependent terms, the flocking dynamics

(4) can be written as

−

⊗

(

⊗

−

)

−

⊗

(

)

(6)

where

(

i, j

−

if the

th edge is incoming at

, and

(

i, j

)=0

otherwise. Here,

the

identity matrix, while

⊗

denotes the Kronecker product. We can replace

with

if the graph is undirected. The matrix

(

)

∈

is a diagonal

matrix satisfying

(

j, j

)=1

−

safe

In order to analyze the stability of the flock, we will make a

change of coordinates:

(

)

−

(

)

−

. Since

(

)

, we write the flocking dynamics as

follows:

−

⊗

(

)

−

⊗

−

(7)

This is a nonlinear, autonomous system whose equilibrium so-

lutions are given by

[

⊗

]

, where

satisfies

(

⊗

(

)

. Given an equilibrium configuration

we define the family of equilibrium solutions obtained by rigid-

body translation and rotation of the flock by

⊗

αP

(

⊗

)

−

(8)

where

∈

(3)

, and

∈

Let

denotes a small perturbation in the corresponding vari-

able, and

is the steady-state

th edge vector. Then, the lin-

earization of (7) about an equilibrium point is given by

−

⊗

, ...,

−

⊗

These equations can be written compactly as

[

]

where the Jacobian

is given by

−

(9)

and

⊗

Aδ

⊗

, ...,

(10)

B. Spectral Properties of

and

Lemma 1:

The null space of

defined in (10) is a superset

of eigenvectors, which correspond to a rigid body translation

and rotation of the flock; i.e.,

(

)

⊇N

span

⊗

(

⊗

)

−

(

⊗

)

−

(

⊗

)

−

where

form a basis for

(3).

Proof:

It is evident from (10) that

(

)

is a su-

perset of the vectors

, which satisfy

(

⊗

)

∀

{

,...,p

}

. The former condition

implies that

⊗

, where

, and

are arbitrary constants.

The latter condition is satisfied by

for all

constants

Assumption 1:

The matrix

has exactly six eigenvalues,

which are equal to 0. Therefore,

(

)

Assumption 1 is satisfied by connected undirected graphs [27]

and by strongly connected and balanced digraphs [16].

Assumption 2:

The Jacobian

has the following properties.

1) All eigenvalues of

have nonpositive real parts.

2) The algebraic and geometric multipicities of the zero

eigenvalue are equal to each other.

3) The null space

(

)=[

]

, where

∈

(

)

The reader should note that Assumption 2 always holds for

an undirected graph satisfying Assumption 1 [27].

PARANJAPE

et al.

: ROBOTIC HERDING OF A FLOCK OF BIRDS USING AN UNMANNED AERIAL VEHICLE

C. Stability Analysis

In this section, we use the center manifold theorem [42, Th. 1]

to show that trajectories which start away from

(

)

,atleast

locally, converge to

(

)

at an exponential rate. The proof

proceeds in two steps. First, we show that there exists a center

manifold when Assumption 2 is satisfied. We note that the set

(

)

is also a center manifold. In the second step, we use the

property that center manifolds are arbitrarily close to each other

to complete the proof.

Lemma 2:

Suppose that the flocking dynamics satisfy

Assumption 2. Then, for every steady state

, there exists an in-

variant manifold

(

)

, such that any trajectory starting

around

converges at an exponential rate to

Proof:

From Assumption 2, we know that the Jacobian

evaluated at

, has six zero eigenvalues and the other eigen-

values are negative. Thus, it follows from the center manifold

theorem [42, Th. 1] that there exists a 6-D center manifold

such that trajectories starting outside

converge at an expo-

nential rate to

Theorem 1:

The set

(

)

is exponentially stable.

Proof:

We note that

(

)

is itself a center manifold of the

dynamics. From Lemma 2, we know that trajectories starting

in a neighborhood of

converge at an exponential rate to the

center manifold

(

)

. We recall that

any

two center manifolds

about an equilibrium point

differ by transcendentally small

terms, and every equilibrium point in the vicinity of

lies on

every

center manifold

(

)

[42, Sec. 4.6]. Thus, a trajectory

starting in a neighborhood of

converges exponentially fast

(

)

The discussion above shows that

(

)

is exponentially sta-

ble, and therefore, robust to small perturbations. In the context

of herding, this implies that, for every direction in relation to

the flock (or its center), there exists a nontrivial set of pursuer

positions for which the underlying graph of the flock is pre-

served. In the next section, we present analytical formulae for

estimating a set of permissible pursuer positions based purely

on local topological considerations.

In addition to stability, for the purpose of herding, it is use-

ful to have the property of time-scale separation between the

synchronization of the flocking dynamics to

(

)

on the one

hand, and the translational dynamics of the center of gravity of

the flock (whose time constant, as shown in Section V, is

)

on the other [21], [22]. This can be achieved by a suitable choice

and

for a given graph topology.

IV. A

NALYTICAL

STIMATION OF THE

ERMISSIBLE

ET OF

URSUER

OSITIONS

The objective of this section is to derive approximations for

the approach distance between a pursuer and the flock, based

purely on the local interaction between the pursuer and the birds

in a flock. This estimate supersedes the distance

agg

in Fig. 2

from the point of view of preserving the local topology of the

flock, and is used in Section V to determine the feasible positions

for the pursuer in relation to the flock.

The influence exerted by the pursuer can cause one of the

two effects in extreme circumstances. In one case, the pursuer

Fig. 4. Typical subgraph in a dense flock, and a subgraph with two birds

collinear with the pursuer. Note

safe

. (a) Dense flock. (b) Local

neighborhood.

Fig. 5. Model with a single edge and the pursuer. The pursuer approaches

along the perpendicular bisector of the edge and

. (a) Sparse flock.

(b) Local neighborhood.

can push a bird to within an unacceptable distance of its neigh-

bor. This scenario is likely in dense flocks, as shown in Fig. 4.

In the second case, the pursuer can cause the link between two

neighbors to be broken by pushing them beyond their communi-

cation distance

com

. This scenario, illustrated in Fig. 5, is more

plausible in sparse flocks. We write the minimum permissible

distance between two birds as

safe

, where

is a constant

that depends on the species of birds and the pursuing UAV.

A. Maintaining Minimum Allowable Distance Between

Neighbors

Consider the situation wherein a bird on the boundary of the

flock (labeled “1”) is engaged by the pursuer. The bird tries to

move away radially from the pursuer, and into the flock. In the

worst case, the bird’s evasive path points in the direction of a

neighboring bird (“2”) and there is force from other neighboring

birds pulling 1 away from 2. This is depicted in Fig. 4.

A conservative estimate for the minimum approach distance

between the pursuer and the bird 1 is found from Fig. 4(b). This is

a repelling, “outward-pointing” (with respect to the flock) force

on 1 due to 2 is countered by the inward-pointing force on 1

IEEE TRANSACTIONS ON ROBOTICS

arising as a consequence of repulsion by the pursuer. Balancing

these two forces when the distance between 1 and 2 is

safe

(thereby, ensuring that the minimum approach distance is no

less than

safe

) gives the minimum approach distance

min

safe

−

safe

(

safe

)

⇒

min

−

)

safe

(11)

B. Preserving Communication Between Neighboring Birds

In sparse flocks, it is a commonplace to find a linear topology,

involving two or three agents forming an angle or a straight

line with no other common neighbors. Consider a single edge,

as shown in Fig. 5, involving just two birds, and assume that

the pursuer approaches along the perpendicular bisector of the

edge. If

com

is the maximum permissible distance between two

boundary agents for the underlying graph to be preserved, we

get the following condition for the minimum permissible

com

−

safe

com

⇒

min

⎛

⎝

−

safe

com

⎞

⎠

(12)

We will provide a numerical example for

min

Section VIII. In Section V, the estimates for

min

are used

as part of the motion planning strategy for the pursuer.

Definition 1:

We define a set

of permissible pursuer po-

sitions in relation to the flock

min

≤

min

∈V

−

≤

fear

(13)

where

min

is the maximum of

agg

and either (11) or (12)

depending on the topology of the flock.

-W

AYPOINT

ERDING

LGORITHM

In Sections III and IV, we established conditions for stability

and robustness of the flock, and derived approximations for the

approach distance between the flock and the pursuer. In this sec-

tion, we solve the problem of herding, described in Section II-C,

by modeling the ensemble behavior of the flock. We first de-

rive a set of objectives that the pursuer’s trajectory,

(

)

,must

satisfy in order to herd the flock successfully. The

-waypoint

algorithm is obtained as an approximate, but efficient, solution

to the problem of ensuring that

(

)

meets these objectives.

A. Formulation of the Herding Problem

The coordinates of the flock’s centroid and its velocity are

given by

. Using (4) and

(5), we get

(

−

(

)

(

)

∈N

(

)

(14)

where

denotes the subset of the flock that lies within

fear

the pursuer; the pursuer’s velocity,

, is a control variable for

the herding algorithm. The term

(

)

is zero when the graph

is undirected (since

) or if it has synchronized to a

steady state configuration from Section III. This would occur

naturally when the flock synchronizes on a faster time scale than

the dynamics of its CG [21], [22]. Since we need the flock to

point in the direction of the herding target point, it suffices to

ensure that its velocity normal to an axis pointing towards

div

is driven to zero. We define

(

)

div

(

)

−

(

)

(15)

Recall, from Section II-C, that

div

(

)

(the altitude of the flock). Since

div

(

)

lies on a fixed ver-

tical line for all

,wealsohavethat

div

(

)=0

. Since

(

div

(

)

−

(

)

, we get the following expression for

the dynamics of

div

−

(

)

div

Next, we define

. Note that

(

div

(

div

)=0

. Thus, the dynamics of

are given by

(

)) +

(

))

(16)

We denote the amount of deviation that can be produced by

placing the pursuer at

using the right hand-side of (16):

(

)

(

)) +

(

))

(17)

(

)=0

for all

, we deduce from (16) that

→

and the

CG of the flock moves in a straight line (solid line in Fig. 6)

towards

div

(from the definition of

). We also note that the

distance and the time required for herding could be reduced, as

compared to moving the flock along the solid line, by pushing

it rapidly towards the dashed line passing through

div

in Fig. 6.

The dashed line is parallel to

, and once the flock’s CG reaches

it, the herding algorithm can safely terminate. This requires that

≥

uniformly (or

≤

uniformly, depending on the choice

div

) during the course of herding. Without loss of generality,

we assume that

div

is chosen, such that sign

(

))

while commencing herding and set the control objective to max-

imizing

(

)

≥

while sign

(

))

(see Fig. 6).

PARANJAPE

et al.

: ROBOTIC HERDING OF A FLOCK OF BIRDS USING AN UNMANNED AERIAL VEHICLE

Fig. 6. Two canonical scenarios, with different signs of

, that correspond to

the flock reaching the dashed line faster than by moving along the solid line to

div

(which corresponds to

). Once on the dashed line, which is parallel

, the flock is guaranteed to stay outside PZ. (a)

,(b)

B. Determination of

Waypoints

An ideal solution to the aforementioned control problem is

to compute the trajectory of

(

)

which maximizes

(

)

, and

get the pursuer to track it. It is well known that a flock tends to

deform into a concave shape locally under persistent pressure

from a pursuer, which is known to dent the effectiveness of

the pursuit [29]. Furthermore, over stressing one or more birds

continuously over an extended period of time carries the risk

of the distressed birds attempting aggressive evasive maneuvers

and fragmenting the flock. To avoid these problems, we use

a sub optimal approach wherein the flock is engaged through

different waypoints in a given time frame.

The waypoints are chosen by sampling the set

from

Definition 1. Sampling is preferred to statically defined way-

points because it allows the algorithm to be agnostic to the

exact geometry of the flock. This is useful when the flock is

not necessarily best represented as a convex shape, for instance,

star-shaped flocks and flocks with a curvilinear geometry. We

formally identify the set of

waypoints as follows.

Definition 2:

The set

is defined by construction. The

waypoint selection algorithm, described in Algorithm 2, sam-

ples

uniformly. Next, up to

waypoints with the highest

deviation are identified such that no two waypoints are within a

prescribed distance, denoted

, of each other. These waypoints

constitute the set

Fig. 7 shows an example of the set

for an arbitrarily

chosen flock and deterministically chosen sample points. It il-

lustrates that even for a convex shaped flock, the set

need

not be connected. This is one of the reasons why we use random

sampling to construct it.

C. Motion Planning for the Pursuer

The motion planner solves for the pursuer’s velocity

(

)

by commanding one of two motions, as follows.

FLY

: the pursuer takes the fastest path to the commanded

node. Collision avoidance is achieved using artificial po-

tential fields, an alternative to which is the real time, online

motion planner based on [43].

ENGAGE

: using a virtual leader-based approach, the pur-

suer commands

(

)

to maintain its position at the chosen

Fig. 7. For an example scenario where the force is to be applied along the

direction, the candidate waypoints in

, defined in (13), are grouped into two

categories. Points marked in green circles satisfy

(

)

and contain the

set

(see Definition 2). Points marked by red

do not satisfy

(

)

Here, blue and black triangles denote birds in the interior of the flock and its

convex hull, respectively.

Algorithm 1:

-Waypoint Herding Algorithm.

1: Input: t;

;small

; locus of

div

2: updateWaypoinstSet

TRUE

while

−

div

OR sign

(

))

−

updateWaypointSet

TRUE

then

CALL(Algorithm 2)

{

Waypoint selection

}

last

; updateWaypointSet

FALSE; node

end if

while

updateWaypointSet

FALSE

(

)

−X

(

node

)

≥

then

10:

(

FLY

(

node

)

11:

else

12:

(

ENGAGE

(

node

);

)

13:

end if

14:

node

card

(

)

−

last

samp, max

then

15:

updateWaypointSet

TRUE

16:

end if

17:

node

node + 1

18:

end while

19:

end while

waypoint in relation to the flock’s centroid for a predeter-

mined duration

. The engagement is terminated if the

distance between two neighboring birds in

approaches

the communication radius,

com

VI. A

NALYSIS OF THE

ERDING

LGORITHM

In this section, we derive a condition for successful herding,

in the form of the minimum allowable distance from the PZ

at which the herding must begin. If the herding commences

beyond this distance, it will almost surely succeed. We assume

that

(

)=0

, i.e., the underlying graph is undirected or the

flock has synchronized to a steady state.

We start by ignoring the dynamics of the pursuer, and recall

that the control objective is to maximize

(

)

≥

. We consider

the conservative case

(

)=0

for all

during the course of

IEEE TRANSACTIONS ON ROBOTICS

Fig. 8. One half of the cone outside which the herding must start; the other

half is the mirror image of the shown half.

Algorithm 2:

Selection of

Waypoints.

Input

; MaxSampleNumber

Output

{

set of waypoints

}

3: INITIALIZE:

{}

, counter

while

counter

MaxSampleNumber

(

)

{

Uniform sample in

}

(

)

AND

−X

>δ

then

←{X

}

←{

,ρ

(

)

}

end if

10:

counter

counter + 1

11:

end while

12: (

)

←

SORT

(

;Γ

)

{

Descending order

(

)

}

13:

card

(

)

then

14:

←X

(1 :

)

15:

end if

herding. This case is limiting in that the distance at which the

herding needs to be commenced can be lesser when larger values

(

)

are attainable (see Section V-A).

In order to achieve

(

)=0

,weset

∗

where

(

∗

−

(

))(

)

. Since

, and

lie in the horizontal plane, it follows that

.Let

denote the upper bound on

which is known from the analysis in Section IV. It is clear

then that the flock should be made to satisfy

∀

, which, in turn, means that the flock must be kept

outside the cone shown in Fig. 8. This is an important insight:

it shows that the herding is successful only if it begins when

the horizontal distance between the center of the flock and the

center of PZ is greater than or equal to

min

div

tan

max

,θ

max

=sin

−

(18)

where

div

was defined in Section II-C.

While the solution

∗

appears to solve the problem in prin-

ciple, there is the possibility that the trajectory

∗

may not be

feasible. Furthermore, the motion planning algorithm adopted

here requires that the pursuer engage with an entire “front” of the

flock rather than specific individual birds. In particular, it means

that the engagement between the pursuer and the flock takes

Fig. 9. Vector diagram showing

and

for push (a) from the aft and (b)

from the front, respectively.

Fig. 10. Refining the estimate of

min

assuming a bimodal herding model.

The solid blue segments denote the motion of the flock when the pursuer engages

it actively; the dashed red segments denote the worst-case motion in the absence

of any pursuer engagement.

place in pulses. We refine the necessary condition to account for

this pulsed interaction.

Let

denote the duration of any given engagement between

the pursuer and the flock, and let

denote the time taken by

the bird to fly between two waypoints. During the time

,the

flock receives no external stimulus and its velocity tends to

align to

. Assuming that an engagement begins at time

,the

dynamics of the flock in the time interval

[

]

can

be described via the switching dynamics

∈

[

)

∈

[

]

(19)

where

(see Fig. 9). When

∗

along

at every instant in time, which is why the superscript

is used here. We will assume that the flock switches instanta-

neously between two states. During the engagement phase, the

flock moves at an angle

to the original direction coinciding

with

. When the pursuer does not engage the flock, it moves

along

. This is depicted in Fig. 10.

The terms

and

should ideally be estimated empirically,

as in Section VII-A, since the precise interaction between the

flock and the pursuer is highly case-specific. The magnitude of

depends on whether the flock is driven from the front or from

the rear. Since we intend for the net motion to be perpendicular

, it is reasonable to assume that the average force also acts

perpendicular to

. Thus, we get

,θ

=cos

−

We now state the main result of this section.

PARANJAPE

et al.

: ROBOTIC HERDING OF A FLOCK OF BIRDS USING AN UNMANNED AERIAL VEHICLE

Theorem 2:

Given the approximate values of

and

,the

refined value of

min

is given by

min

div

cot

(20)

Proof:

Let

denote the number of engagement pulses.

From Fig. 10, it is apparent that we can have at most

pulses wherein the flock is not engaged with the pursuer. During

each engagement pulse, referring to the geometric convention of

Fig. 10, the flock shifts through a distance

sin

. Thus,

div

sin

Furthermore, during each engagement phase, the flock translates

horizontally through a distance

cos

. During the nonen-

gagement phase, the horizontal translation is at most

Thus, the minimum horizontal translation is given by

min

(

cos

)

div

sin

+cot

Setting

cos

yields

min

div

cot

(1 +

)

. Notice that we recover (18) if we set

and

max

This completes the proof.

Remark 1:

We note two extreme cases that give further in-

sight on the variation of

min

with the size of the flock. When

is small, it is reasonable to expect that the pursuer simulta-

neously affects all members of the flock. In such cases,

, and

subsequently,

min

are independent of

(the size of the flock).

When

is large, it is reasonable to assume that the pursuer en-

gages a

fixed

number of boundary agents, and this number is

also independent of

. Furthermore, we expect that

is small,

so that

cot

≈

/θ

, and

≈

(

)

. Since the num-

ber of birds engaged by the pursuer is a constant,

∝

where

is a constant. Assuming that

/τ

is not a function of

, it follows that

min

∝

; i.e., the minimum distance grows

linearly with the flock size for large flocks.

Remark 2:

In [7], we considered several cases wherein the

total number of waypoints was fixed; for each case, a different

fraction of waypoints was used in a manner consistent with

this paper, while the rest were used for pushing the flock from

the rear. This is analogous, in the framework of this paper, to

changing the value of

. Therefore, we do not analyze the

effect of changing

in this sequel. We note, however, that

the choice of the number of waypoints depends on the inherent

cohesiveness of the flock. A larger number of waypoints may

be needed to ensure containment in a loosely bound flock.

In Section VII, we will demonstrate how (19) can be used to

extract a set of flocking model parameters from experimental

data. The model for the minimum distance will be revisited in

Section VIII (numerical simulations), with the objective of de-

riving an empirical relationship between the minimum distance

and the size of the flock.

VII. E

XPERIMENTS ON A

IVE

LOCK OF

IRDS

In this section, we describe the results of experiments carried

out on live birds in Daejeon, South Korea. The objective of

the experiments was to validate the flocking model described

earlier, and estimate the values of the parameters in the flocking

model. The experiments were carried out in two rounds on two

families of birds.

The experiments involved flying a quadrotor drone in the

vicinity of flocks. Two rounds of experiments were conducted

during two different seasons—the first involved egrets, while the

second involved loons. For this study, two drones were deployed:

One drone performed various types of maneuvers around the

flocks as a pursuer (herding drone), while a surveillance drone

hovered at a high altitude with a camera pointing directly down

to the ground for recording the trajectories of the pursuer drone

and the birds. Videos recorded during the experiments are avail-

able as part of the supplementary material, accompanying the

paper.

A. Experiments on Egrets

Egrets are migratory birds, and at the time of conducting

the experiments, they had settled in their nesting grounds in the

vicinity of the KAIST campus. The birds make frequent visits to

a hunting area nearby, and a large number of egrets are found

to return to their nests at sunset. During this time, we attempted

to fly the herding drone in various directions with respect to the

flock.

In Figs. 11 and 12, two cases are closely studied. In Fig. 11, the

drone approaches the flock horizontally at a sufficient distance.

Initially, the birds fly along the

−

direction and the drone

approaches from the left with about 30 m of clearance. As the

birds discover the drone, they divert from their original paths

and fly at a 45

◦

angle to their right. Meanwhile, the drone moves

only a few meters, but drives the birds away from the PZ (left

of the drone). When the birds discover the drone at a sufficient

distance, they adjust their paths horizontally and make smaller

changes in the vertical direction. If the drone were able to fly

along the flock, it would be possible to herd the birds away from

the PZ without breaking the flock.

In Fig. 12, the drone approaches the flock from a shorter

distance at a higher speed. In this case, the birds continue to fly

to their destination without much horizontal deviation but with

large vertical deviation. As the birds discover the approaching

drone, they make sudden vertical adjustments to their paths:

they rapidly descend by making a very large bank angle with

strong flapping motions of their wings. Therefore, if the drone

approaches the flock suddenly, the objective of herding may not

be satisfied and the flock still continues to fly to the PZ.

From the observations made from Figs. 11 and 12, we can

identify the important distance variables shown in Fig. 2. From

Fig. 11,

fear

is more than 20 m, which corresponds to the dis-

tance at which the egrets make horizontal corrections of their

paths. From Fig. 12,

agg

is around 10 m or less. When the

birds discover the drone, they choose to make vertical path

corrections since they do not have sufficient time to make hor-

izontal corrections by banking. It is also evident from the early

IEEE TRANSACTIONS ON ROBOTICS

Fig. 11. Stills and data extracted from a video recording of an experiment on live birds. In this experiment, the drone approaches the flock of egrets at a

sufficient

distance to induce horizontal deviation. The video recording is available as a part of the supplementary material.

Fig. 12. Stills and data from a video recording of an experiment. The drone approaches the flock of egrets close enough to induce vertical deviation.

moments of Fig. 11 that

safe

is approximately equal to 10 m.

The distance between the birds reduces during the engagement

with the pursuer, and this behavior is also observed during the

simulations described in Section VIII.

The time histories of the position and the velocity of the CG

of the flock, corresponding to Fig. 11, are shown in Fig. 13. The

time histories of the velocity are estimated from the position

data using finite differencing, which explains their coarseness.

The velocity profile of the CG is as follows:

1) until approximately 2.5 s (pre-engagement):

(1)

9m/s;

(2)

= ̇

2.5 m/s;

2) after 2.5 s (engagement):

7.5 m/s;

7.5 m/s.

It follows from this data that

−

. We recall the

dynamics of the velocity of the CG during the engagement