Systems and methods for avian flock flight path modification using UAVs

Abstract

Systems and methods for autonomously herding birds in accordance with embodiments of the invention are illustrated. One embodiment includes an autonomous flock herding system, including a bird location sensor, a drone; and a control system, including a processor, and a memory, the memory containing a flock herding application, where the application directs the processor to obtain bird position data from the at least one bird location sensor, where the bird position data describes the location of birds in a flock of birds, determine if the flock of birds will enter a protected zone, generate a set of waypoints using a flock dynamics model, instruct the unmanned aerial vehicle to navigate to at least one waypoint in the set of waypoints such that the flock of birds will, in response to the presence of the unmanned aerial vehicle at the at least one waypoint, change trajectory away from the protected zone.

Claims

1. An autonomous bird flock herding system, comprising: at least one bird location sensor; an unmanned aerial vehicle; and a flock herding control system, comprising: a processor; and a memory, the memory containing a flock herding application, where the flock herding application directs the processor to: obtain bird position data from the at least one bird location sensor, where the bird position data describes the location of birds in a flock of birds, where the flock of birds forms a non-convex hull; determine if the flock of birds will enter a protected zone; generate a set of waypoints for positioning the unmanned aerial vehicle using a predictive flock dynamics model, where for each waypoint in the set of waypoints, the unmanned aerial vehicle is predicted to not split the flock when at the waypoint; uniformly sample the set of waypoints to produce a subsample of waypoints; score each given waypoint in the subsample of waypoints based on whether or not placing the unmanned aerial vehicle at the given waypoint will move the flock of birds in a desired direction and the distance to other waypoints in the subsample of waypoints; sort the subsample of waypoints based on score; select a waypoint from the sorted subsample of waypoints having the highest score; instruct the unmanned aerial vehicle to navigate to the selected waypoint such that the flock of birds will, in response to the presence of the unmanned aerial vehicle at the at least one waypoint, change trajectory away from the protected zone.

2. The autonomous bird flock herding system of claim 1, wherein the flock of birds will, in response to the presence of the unmanned aerial vehicle at the selected waypoint maintain integrity such that a centroid of the flock and a shape of the flock are maintained and communication links between any two neighboring birds of the flock are not broken.

3. The autonomous bird flock herding system of claim 1, wherein the protected zone is a cylinder.

4. The autonomous bird flock herding system of claim 1, wherein the protected zone is over an airport.

5. The autonomous bird flock herding system of claim 1, wherein the at least one bird location sensor is an avian radar.

6. The autonomous bird flock herding system of claim 1, further comprising at least one environmental sensor; and the flock herding application further directs the processor to: obtain environment data describing environmental conditions proximal to the protected zone from the at least one environmental sensor; and generate the set of waypoints using the environment data.

7. The autonomous bird flock herding system of claim 6, wherein the environment data describes the position of airplanes.

8. The autonomous bird flock herding system of claim 6, wherein the environment data describes wind speed.

9. The autonomous bird flock herding system of claim 1, wherein the flock herding application further directs the processor to: obtain updated bird position data; update the set of waypoints based on the updated bird position data; uniformly sample the updated set of waypoints to produce an updated subsample of waypoints; score each specific waypoint in the updated subsample of waypoints based on whether or not placing the unmanned aerial vehicle at the specific waypoint will move the flock of birds in a desired direction and the distance to other waypoints in the updated subsample of waypoints; sort the updated subsample of waypoints based on score; and select a new waypoint from the sorted, updated subsample of waypoints having the highest score.

10. The autonomous bird flock herding system of claim 1, further comprising: a second unmanned aerial vehicle; and wherein the flock herding application further directs the processor to: generate a second set of waypoints using the predictive flock dynamics model; uniformly sample the second set of waypoints to produce a second subsample of waypoints; score each specific waypoint in the second subsample of waypoints based on whether or not placing the unmanned aerial vehicle at the specific waypoint will move the flock of birds in a desired direction and the distance to other waypoints in the second subsample of waypoints; sort the second subsample of waypoints based on score; select a second waypoint from the sorted second subsample of waypoints having the highest score; and instruct the second unmanned aerial vehicle to navigate to the selected second waypoint such that the flock of birds will, in response to the presence of the second unmanned aerial vehicle at the given at least one waypoint, change trajectory away from the protected zone.

11. A method for the autonomous herding of flocks of birds comprising: obtaining, using a flock herding control system, bird position data from at least one bird location sensor, where the bird position data describes the location of birds in a flock of birds, where the flock of birds forms a non-convex hull; determining, using the flock herding control system, if the flock of birds will enter a protected zone; generating, using the flock herding control system, a set of waypoints using a predictive flock dynamics model for an unmanned aerial vehicle, where for each waypoint in the set of waypoints, the unmanned aerial vehicle is predicted to not scars split the flock when at the waypoint; uniformly sampling the set of waypoints to produce a subsample of waypoints; scoring each given waypoint in the subsample of waypoints based on whether or not placing the unmanned aerial vehicle at the given waypoint will move the flock of birds in a desired direction and the distance to other waypoints in the subsample of waypoints; sorting the subsample of waypoints based on score; selecting a waypoint from the sorted subsample of waypoints having the highest score; and instructing, using the flock herding control system, the unmanned aerial vehicle to navigate to the selected waypoint such that the flock of birds will, in response to the presence of the unmanned aerial vehicle at the at least one waypoint, change trajectory away from the protected zone.

12. The method for the autonomous herding of flocks of birds of claim 11, wherein the flock of birds will, in response to the presence of the unmanned aerial vehicle at the selected waypoint maintain integrity such that a centroid of the flock and a shape of the flock are maintained and communication links between any two neighboring birds of the flock are not broken.

13. The method for the autonomous herding of flocks of birds of claim 11, wherein the protected zone is a cylinder.

14. The method for the autonomous herding of flocks of birds of claim 11, wherein the protected zone is over an airport.

15. The method for the autonomous herding of flocks of birds of claim 11, wherein the at least one bird location sensor is an avian radar.

16. The method for the autonomous herding of flocks of birds of claim 11, further comprising obtaining, using the flock herding control system, environment data from at least one environmental sensor describing environmental conditions proximal to the protected zone from the at least one environmental sensor; and generating the set of waypoints using the environment data.

17. The method for the autonomous herding of flocks of birds of claim 16, wherein the environment data describes the position of airplanes.

18. The method for the autonomous herding of flocks of birds of claim 16, wherein the environment data describes wind speed.

19. The method for the autonomous herding of flocks of birds of claim 16, further comprising: obtaining, using the flock herding control system, updated bird position data; updating, using the flock herding control system, the set of waypoints based on the updated bird position data; uniformly sampling the updated set of waypoints to produce an updated subsample of waypoints; scoring each specific waypoint in the updated subsample of waypoints based on whether or not placing the unmanned aerial vehicle at the specific waypoint will move the flock of birds in a desired direction and the distance to other waypoints in the updated subsample of waypoints; sorting the updated subsample of waypoints based on score; and selecting a new waypoint from the sorted, updated subsample of waypoints having the highest score.

20. The method for the autonomous herding of flocks of birds of claim 16, further comprising: generating, using the flock herding control system, a second set of waypoints using the predictive flock dynamics model; uniformly sampling the second set of waypoints to produce a second subsample of waypoints; scoring each specific waypoint in the second subsample of waypoints based on whether or not placing the unmanned aerial vehicle at the specific waypoint will move the flock of birds in a desired direction and the distance to other waypoints in the second subsample of waypoints; sorting the second subsample of waypoints based on score; selecting a second waypoint from the sorted second subsample of waypoints having the highest score; and instructing, using the flock herding control system, a second unmanned aerial vehicle to navigate to the selected second waypoint such that the flock of birds will, in response to the presence of the second unmanned aerial vehicle at the given at least one waypoint, change trajectory away from the protected zone.

Description

BRIEF DESCRIPTION OF THE DRAWINGS

(1) The description and claims will be more fully understood with reference to the following figures and data graphs, which are presented as exemplary embodiments of the invention and should not be construed as a complete recitation of the scope of the invention.

(2) FIG. 1 is a conceptual system diagram for a flock herding system in accordance with an embodiment of the invention.

(3) FIG. 2 is a conceptual block diagram for a flock herding control system in accordance with an embodiment of the invention.

(4) FIG. 3 is a high-level illustration of a flock herding system in action in accordance with an embodiment of the invention.

(5) FIG. 4 is a flowchart illustrating a flock herding process in accordance with an embodiment of the invention.

(6) FIG. 5 illustrates several important distance variables in the flocking model in accordance with an embodiment of the invention.

(7) FIG. 6 illustrates a top view of two loci of candidate target points in accordance with an embodiment of the invention.

(8) FIG. 7 illustrates a typical subgraph in a dense flock and a subgraph with two birds collinear with a pursuer in accordance with an embodiment of the invention.

(9) FIG. 8 illustrates a model with a single edge and the pursuer in accordance with an embodiment of the invention.

(10) FIG. 9 illustrates two canonical scenarios with different signs of q.sub.k in accordance with an embodiment of the invention.

(11) FIG. 10 is psuedocode for the m-waypoint herding algorithm in accordance with an embodiment of the invention.

(12) FIG. 11 is psuedocode for the selection of m-waypoints in accordance with an embodiment of the invention.

(13) FIG. 12 illustrates one half of the cone outside which the herding should start in accordance with an embodiment of the invention.

(14) FIG. 13 is a vector diagram illustrating push from the aft and from the front, respectively.

(15) FIG. 14 is an example of flock motion in the presence of a pursuer and without a pursuer in accordance with an embodiment of the invention.

DETAILED DESCRIPTION

(16) Turning now to the drawings, systems and methods for avian flight path modification using UAVs are illustrated. Flocks of birds are a common sight, and their dynamic movements are highly choreographed. The nature of these movements both in formation and flight path are complex and take place at high speeds. Unfortunately, there are many situations where the presence of birds are highly problematic to human activities and infrastructure. For example, in the case of US Airways Flight 1549, colloquially referred to as the “Miracle on the Hudson,” the airplane on ascent after takeoff struck a flock of geese and was forced to ditch into the Hudson river. While keeping the skies clear over a small area has been traditionally handled by trained birds of prey, for example the famous Harris's Hawks of Wimbledon, this solution is not easily scaleable nor feasible in many situations.

(17) Drones, however, as opposed to biological solutions, are mass-producible, highly controllable, and can be stored long-term in many different conditions with considerably less maintenance. While there have been some attempts to utilize drones to scare away birds from airports (for example RoBird of the Netherlands), these systems are often remote controlled and designed to scare birds away. Both of these factors can cause significant issues, as both the ineffectiveness of human piloting and unrefined scare tactics can lead to flocks of birds to split up, which simply causes more problems in the form of multiple sub-flocks which must now be controlled. In turn, this requires additional UAVs or other interdiction methods (e.g. air cannons, lasers, biological solutions, etc.) which escalate cost and increase the likelihood of strikes.

(18) In contrast to the conventional “scare-tactics” which can split flocks, systems and methods described herein can mitigate these issues by utilizing autonomous drones to manipulate the movements of flocks of birds to guide them outside of a predefined geographic region without disrupting the flock unit. This process is referred to as “herding,” because the flock is left intact. In many embodiments, multiple drones acting in accordance with methods described herein can work in tandem to herd a single flock, or to herd multiple flocks at once. Autonomous drones with appropriate sensing platforms can be pre-loaded with control software and deployed to safely remove birds in any number of scenarios not limited to airports. However, for ease of description, airports will be discussed in greater detail, and one of ordinary skill in the art would understand that the systems and methods described herein could easily be deployed in alternative scenarios and locations.

(19) In order to maintain flock integrity, in many embodiments, herding processes include real-time modeling of a flock and the expected response of the flock to external pursuers. In many embodiments, a number of waypoints are calculated for the drone to maneuver to in relation to the flock. The model of the flock dynamics can be used to generate waypoints that avoid flock fragmentation and/or reduce the amount of physical space that the flock occupies (e.g. promote tighter flying formations). In numerous embodiments, multiple drones can be utilized, each with their own set of waypoints collectively calculated to herd the flock. Flock herding systems are discussed in more detail below.

(20) Flock Herding Systems

(21) Flock herding systems are systems which prevent flocks of birds from entering a pre-defined geographical region, or a “protected zone.” In many embodiments, a protected zone includes the airspace above a particular region. As mentioned above, protected zones can be any number of different regions, and are not defined by any particular geographic feature. Drones can be utilized either alone or in tandem to keep birds out of the protected zone. In many embodiments, drones have sensors to enable them to at least detect birds and/or other drones. However, in numerous embodiments, external sensors and/or sensor arrays are utilized to track bird movements.

(22) Turning now to FIG. 1, a flock herding system in accordance with an embodiment of the invention is illustrated. Flock herding system 100 includes a drone 110 and a flock herding control system 120. In many embodiments, drones are quadcopters, however, any number of different drone platforms can be utilized, including, but not limited to, those that mimic birds of prey, fixed wing unmanned craft, single or other multi-rotor craft, and or any other UAV as appropriate to the requirements of specific applications of embodiments of the invention. Flock herding control systems are computing platforms capable of ingesting bird position data and producing waypoints for drones to navigate to in order to remove flocks from a protected zone. In many embodiments, flock herding control systems are implemented on local computing platforms such as a server or personal computer. However, flock herding control systems can be implemented using cloud computing architecture and/or any number of different computing platforms as appropriate to the requirements of specific applications of embodiments of the invention.

(23) Flock herding system 100 further includes a bird location sensor 130. In many embodiments, bird location sensors 130 are avian radars. However, bird location sensors can be any sensor platform capable of reporting the location of birds in a protected zone in at least near real-time. In numerous embodiments, flock herding systems include additional sensors for tracking other environmental objects or conditions (collectively “environmental sensors”). For example, if an airport is in a protected zone, additional environmental data can be produced regarding the position of nearby aircraft. Further, environmental conditions such as wind speed, humidity, temperature, cloud cover, time, date, and any other environmental information can be captured by sensors and provided to flock herding control systems for use in waypoint generation and/or other control functions.

(24) Flock herding system 100 additionally includes an interface device 140. Interface devices are any device capable of enabling a user to communicate with a flock herding control system or a drone. In many embodiments, interface devices are personal computers, but can be any number of digital communication devices such as, but not limited to, smart phones, smart TVs, tablet computers, and/or any other digital communication device as appropriate to the requirements of specific applications of embodiments of the invention. Components of the flock herding system 100 communicate via a network 150. In many embodiments, the network is a composite network made of multiple different interconnected networks which can be implemented using the same or different communications protocols. For example, networks can be wired, wireless, or a combination thereof. For example, in some embodiments, flock herding control systems communicate with bird location sensors on a particular network, and the flock herding control system provides data to the drones via a separate network. One of ordinary skill in the art would appreciate that any different number of system architectures and/or communications architectures can be utilized as appropriate to the requirements of specific applications of embodiments of the invention, including, but not limited to, those that utilize different environmental sensors and/or different numbers of drones.

(25) Turning now to FIG. 2, a conceptual block diagram of a flock herding control system in accordance with an embodiment of the invention is illustrated. Flock herding control system 200 includes a processor 210. Processors can be any number of logic processing circuitries including, but not limited to central processing units (CPUs), graphics processing units (GPUs), field programmable gate arrays (FPGAs), application specific integrated circuits (ASICs), and/or any other logic processing circuitry capable of computation. In many embodiments, more than one processor is utilized. Flock herding control system 200 further includes an input/output interface 220. Input/output interfaces enable communication to other parts of flock herding systems.

(26) Flock herding control system 200 further includes a memory 230. Memories can be implemented using volatile memory, non-volatile memory, or a combination of both. Memory 230 contains a flock herding application 232. Flock herding applications instruct the processor to generate waypoints for drones to navigate to in order to herd flocks away from protected zones. In many embodiments, memory 230 further contains bird position data 234 and/or environment data 236. As noted above, bird position data describes the 3D coordinate location of birds in range of the protected zone, and environment data describes various environmental conditions.

(27) In many embodiments, flock herding control systems are implemented on standard computing platforms. However, flock herding control systems can be integrated into drones so long as the drone platform has sufficient computing capabilities. As one can appreciate, any number of different implementations of system architectures and flock herding control systems can be utilized to generate waypoints that enable drones to successfully herd flocks away from a protected zone as appropriate to the requirements of specific applications of embodiments of the invention. Processes for generating waypoints are discussed below.

(28) Generating Waypoints for Flock Herding

(29) As noted above, a key problem with conventional bird dispersal techniques is the fracturing of flocks into individual birds and/or subflocks. This creates significant inefficiencies as the fractured units are dispersed over a wider area and then must each individually be dealt with. In contrast, processes described herein can generate waypoints that, which when navigated to by a drone, will herd a flock away from a protected zone without fracturing the flock. This leads can lead to an increase in efficiency at least by requiring fewer drones, quicker dispersal times, and more efficient use of resources generally.

(30) By way of example, a high-level conceptual illustration of the effect of a flock herding process in accordance with an embodiment is illustrated in FIG. 3. In this case an airport is within a cylindrical protected zone with radius R.sub.PZ. However, protected zones are not required to be cylindrical, and be any number of shapes, for example, a sphere, a cube, a polyhedron, or a composite shape. When an flock on an intruding path is detected, a drone is dispatched to herd the flock away from the protected zone.

(31) Turning now to FIG. 4, a high-level flowchart for a flock herding process in accordance with an embodiment of the invention is illustrated. Process 400 includes detecting (410) an intrusion. In many embodiments, the intrusion is determined when a flock enters a protected zone. However, intrusion can be determined when a flock is determined to be on a trajectory that will lead to the protected zone. In numerous embodiments, this is accomplished by having a zone outside the protected zone where flocks are tracked to determine if herding is necessary.

(32) To accomplish successful herding, the “m-waypoint herding algorithm” has been developed. At a high level, a drone interacts with the intruding flock by positioning itself sequentially at a periodically refreshed set of m points. The inherent stability of the flocking dynamics are leveraged to prevent fragmentation, and the m points can be selected to maximize the deflection of the flock's flight path.

(33) Turning now to FIG. 4, a particular implementation of a flock herding process utilizing the m-waypoint herding algorithm in accordance with an embodiment of the invention is illustrated. Process 400 further includes obtaining (420) flock position data. In numerous embodiments, the flock position data is obtained from the bird location sensor. Flock position data can described the location of individual birds, or the location of a flock as a whole. In many embodiments, individual bird locations can be aggregated into a single unit representing a flock. For example, by measuring proximity, speed, direction, and/or any other positioning measurement, birds flying in a coherent pattern and/or in proximity can be grouped. A waypoint is generated (430) and a drone is navigated (440) to the waypoint. If the flock is not yet out of the protected zone (450), then updated flock position data can be obtained and a new waypoint can be generated for the drone to navigate to until the flock has been successfully removed. In numerous embodiments, waypoints are generated as a sequential set instead of one at a time, and the drone navigates to each point in order. In a variety of embodiments, the set of waypoints is continuously updated. In many embodiments, multiple sets of waypoints can be generated for multiple drones to work in tandem to herd the same flock, and/or different flocks.

(34) In order to generate the waypoints, an understanding of flock dynamics can be modeled from which the basis of the m-waypoint herding algorithm can be formulated. Consider a flock of n (usually >>1) birds. The position and the velocity of the i.sup.th bird are denoted by x.sub.i∈.sup.3 and v.sub.i ∈.sup.3, respectively. The vector between the i.sup.th and j.sup.th birds is denoted by r.sub.ij=x.sub.j−x.sub.i. The subscript ‘p’ is used for the pursuer, so that x.sub.p denotes its position vector, and r.sub.pi=x.sub.i−x.sub.p is the vector from the pursuer to the i.sup.th bird. Given a vector r, the unit vector along r is denoted by {circumflex over (r)}.

(35) Let R.sub.com denote the communication range for interaction between two birds. The neighborhood set of the i.sup.th bird is defined using the standard Euclidean distance as,
.sub.i={j≤n:|∥x.sub.i−x.sub.j∥≤R.sub.com}.  (1)
and it is assumed that two birds interact only if their distance is less than or equal to R.sub.com. The set of birds (ν) thus forms a graph G=(ν, ε) where
ν={1,2, . . . ,n},
ε={(i,j)∈ν×ν|j∈.Math..sub.i}, card(ε)=p  (2)

(36) Note that if =.sub.i for all i, the graph is undirected. Otherwise, it is directed. The incidence matrix of the graph is denoted as B.sub.c∈.sup.n×p. Recall that the (i,j).sup.thb entry of B.sub.c is 1 if the j.sup.th edge is incoming at i, −1 if outgoing at i, and 0 otherwise. An undirected edge is treated as two separate directed edges in this formulation of B.sub.c. Δ(ν) denotes the diagonal matrix formed by the elements of the tuple ν. Finally, the centroid and the radius of the flock are defined as

(37) $\begin{array}{cc}{x}_{\mathrm{cg}}=\frac{1}{n}\underset{i=1}{\overset{n}{.Math.}}{x}_i,R_F\stackrel{\Delta }{=}{\max }_i.Math.x_i-x_{\mathrm{cg}}.Math.& \left(3\right)\end{array}$
A. Flock Dynamics

(38) The dynamics of an individual (i.sup.th) bird are described by a nonlinear, second-order differential equation based on Reynolds' rules and augmented with an evasive response:

(39) $\begin{array}{cc}{\stackrel{.}{x}}_i=v_i& \left(4\right)\\ {\stackrel{.}{v}}_i=k_s\underset{j\in {𝒥}_i}{\overset{}{.Math.}}\left(1-\frac{R_{\mathrm{safe}}^3}{{.Math.r_{\mathrm{ij}}.Math.}^3}\right)r_{\mathrm{ij}}+k_a\underset{j\in {𝒥}_i}{\overset{}{.Math.}}\left(v_j-v_i\right)+k_g\left(v_d-v_i\right)+k_{p}H\left(r_{\mathrm{pi}}\right)& \end{array}$
where R.sub.safe denotes the steady-state distance between two adjacent members of the flock; v.sub.d denotes the pre-selected, steady velocity of each member of the flock; and H(r.sub.pi)=H(x.sub.i−x.sub.p) denotes the evasive response to the pursuer. It is assumed that v.sub.d lies in the horizontal plane.

(40) FIG. 5 summarizes important distance variables that appear in the model in accordance with an embodiment of the invention. The terms R.sub.safe and R.sub.com have been defined already. The terms R.sub.fear and R.sub.agg (<R.sub.fear) refer to critical distances in the bird-pursuer interaction, and it is assumed that both of these quantities are known for a given flock. The flock responds to a pursuer only when the pursuer is within a radius R.sub.fear of a member of the flock. Within R.sub.fear, the evasive behaviour generally takes two different forms: If the pursuer is within [R.sub.agg, R.sub.fear], the bird tries to accelerate radially away from the pursuer. If the pursuer is within R.sub.agg, the bird tries to out-maneuver the pursuer by turning and/or climbing rapidly.

(41) Since the out-turning or 3-D behavior can have adverse implications for the stability of the flock, R.sub.agg can be treated as a lower bound for the permissible distance between the pursuer and the flock. H(⋅) can be modeled as follows:

(42) $\begin{array}{cc}H\left(r_{\mathrm{pi}}\right)=\{\begin{array}{cc}\frac{r_{\mathrm{pi}}}{{.Math.r_{\mathrm{ij}}.Math.}^3},& \mathrm{if}.Math.r_{\mathrm{pi}}.Math.<R_{\mathrm{fear}}\mathrm{and}{r}_{\mathrm{pi}}^T{\stackrel{.}{r}}_{\mathrm{pi}}<0\\ 0& \mathrm{otherwise}\end{array}& \left(5\right)\end{array}$
and a restriction that ∥r.sub.pi∥ R.sub.agg+ϵ for all i, where ϵ>0 is an arbitrarily-chosen constant can be imposed.
B. Herding Objectives

(43) As noted above, the protected zone (PZ) is the spatial volume that needs to be kept free of birds. For illustrative purposes, in this example, PZ is assumed to be cylindrical with radius R.sub.PZ. However, in many embodiments, the PZ can be other shapes. For modeling purposes, it can be assumed that birds fly along a constant, pre-selected heading, {circumflex over (v)}.sub.d, when not disturbed by a pursuer. This is in fact 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 {circumflex over (v)}.sub.d) would no longer cross PZ. This target point is denoted as x.sub.div(t), noting that its exact position may change with time as described presently.

(44) The global coordinate frame is defined with its origin placed at the centre of PZ, and its axes pointing north, east and up, respectively. Let h(t) denote the instantaneous altitude of the flock. First, two vertical lines (in the global frame) can be constructed which serve as loci for all possible target points. Recall that v.sub.d in (4) is the predetermined nominal flock velocity which satisfies {circumflex over (k)}.sup.Tv.sub.d=0 where {circumflex over (k)} is the unit vector pointing upwards in the global frame. Unit vector {circumflex over (v)}.sub.d.sup.⊥ is defined which satisfies v.sub.dt{circumflex over (v)}.sub.d.sup.⊥={circumflex over (k)}.sup.T{circumflex over (v)}.sub.d.sup.⊥=0. The two candidate loci are then given by l.sub.cand,±(a)=±(R.sub.PZ+s){circumflex over (v)}.sub.d.sup.⊥+a{circumflex over (k)} where a∈, and s>R.sub.F is a suitably chosen constant. R.sub.divR.sub.PZ+s is denoted. Of these candidate loci, the one closest to x.sub.cg, at t=0 (the moment at which the herding commences) is selected, as illustrated in FIG. 6 in accordance with an embodiment of the invention. Finally, at each t, set the instantaneous target waypoint on the chosen locus as x.sub.div=(+/−)R.sub.div{circumflex over (v)}.sub.d.sup.⊥+h(t){circumflex over (k)}. If the two loci are equidistant from x.sub.cg, then any of the two loci can be chosen: however, this choice may persist for the remainder of the herding operation. This selection of herding target points is a logical extension from 2D to 3D when the herding algorithm does not seek to control the altitude of the flock. The objective of the herding algorithm is to prescribe a trajectory x.sub.p(t) for the pursuer which enables it to: (1) move the CG of the flock to x.sub.d, in finite time; (2) avoid fragmentation of the flock; and (3) keep the flock outside the protected zone PZ during the course of herding.

(45) C. Stability Analysis

(46) In order to avoid fracturing the flock, conditions for flock stability can be modeled. These conditions can be used to select the gains and the underlying graph in (4) for analytical 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 distance between itself and the flock, the flock will not undergo fragmentation.

(47) C.I. Snapshot Dynamics, Steady States, and Linearization

(48) To model snapshot dynamics, steady states, and linearization, two column vectors x, v∈.sup.3n, formed by permuting the components of x.sub.i and v.sub.i, respectively, ∀i:
x=[x.sub.11, . . . ,x.sub.n1,x.sub.12, . . . ,x.sub.n2,x.sub.13, . . . ,x.sub.n3].sup.T
are defined, and v is constructed in a similar manner. There exists a permutation matrix, denoted by P.sub.3n∈.sup.3n×3n, such that

(49) $x=P_{3n}\left[\begin{array}{c}{x}_1\\ x_2\\ \mathrm{.Math.}\\ x_n\end{array}\right],\left[\begin{array}{c}{x}_1\\ x_2\\ \mathrm{.Math.}\\ x_n\end{array}\right]=P_{3n}^{-1}x$

(50) Ignoring the pursuer-dependent terms, the flocking dynamics (4) can be written as
{dot over (x)}=v
{dot over (v)}=−k.sub.a(I.sub.3.Math.D.sub.cB.sub.c.sup.T)v+k.sub.g(v.sub.d.Math.1.sub.n−v)−k.sub.s(I.sub.3.Math.D.sub.cQ(x)B.sub.c.sup.T)x  (6)
where D.sub.c(i,j)=−1 if the j.sup.th edge is incoming at i, and D.sub.c(i,j)=0 otherwise. Here, I.sub.3 the 3×3 identity matrix, while .Math. denotes the Kronecker product. D.sub.c can be replaced with B.sub.c/2 if the graph is undirected. The matrix Q(x)∈.sup.p×p is a diagonal matrix satisfying Q(j,j)=1−R.sub.safe.sup.3/∥e.sub.j∥.sub.3.

(51) In order to analyze the stability of the flock, a change of coordinates can be made: {tilde over (x)}.sub.i(t)=x.sub.i(t)−v.sub.dt, {tilde over (v)}.sub.i(t)=v.sub.i(t)−v.sub.d. Since Q(x)=Q({tilde over (x)}), flocking dynamics can be written as
{tilde over ({dot over (x)})}={tilde over (v)}
{tilde over ({dot over (v)})}=−k.sub.s(I.sub.3.Math.D.sub.cQ({tilde over (x)})B.sub.c.sup.T){tilde over (x)}−k.sub.a(I.sub.3ÐD.sub.cB.sub.c.sup.T){tilde over (v)}−k.sub.g{tilde over (v)}  (7)

(52) This is a nonlinear, autonomous system whose equilibrium solutions are given by [{tilde over (x)}.sup.0, 1.sub.n.Math.0.sub.3], where {tilde over (x)}.sup.0 satisfies (I.sub.3.Math.D.sub.cQ({tilde over (x)}.sup.0)B.sub.c.sup.T){tilde over (x)}.sup.0=0.

(53) Given an equilibrium configuration {tilde over (x)}.sup.0, the family of equilibrium solutions obtained by rigid-body translation and rotation the flock are defined by
S({tilde over (x)}.sup.0)={{tilde over (x)}|{tilde over (x)}=b.Math.1.sub.n+αP.sub.3n(I.sub.n.Math.J)P.sub.3n.sup.−1{tilde over (x)}.sup.0}  (8)
where b∈.sup.3, J∈ so (3), and α∈.

(54) Let δ.Math. denotes a small perturbation in the corresponding variable, and e.sub.i.sup.0 is the steady-state i.sup.th edge vector. Then, the linearization of (7) about an equilibrium point is given by

(55) $\delta \stackrel{.}{x}=\mathrm{\delta \upsilon }\delta \stackrel{.}{\upsilon }=-\frac{3}{R^2}\left(I_3.Math.D_c\Delta \left(e_1^{0^{\top }}\delta e_1,.Math.,e_p^{0^{\top }}\delta e_p\right)B_c^{\top }\right){\tilde{x}}^0-\left(k_a\left(I_3.Math.D_c{B}_c^{\top }\right)+k_g{I}_{3n}\right)\mathrm{\delta \upsilon }$

(56) These equations can be written compactly as

(57) $\left[\begin{array}{c}\delta \stackrel{.}{x}\\ \delta \stackrel{.}{\upsilon }\end{array}\right]=G\left[\begin{array}{c}\delta x\\ \mathrm{\delta \upsilon }\end{array}\right],$
where the Jacobian G is given by

(58) $\begin{array}{cc}G=\left[\begin{array}{cc}{0}_{3n}& I_{3n}\\ -k_{s}A& -B\end{array}\right],& \left(9\right)\end{array}$
and

(59) $\begin{array}{cc}B=k_a\left(I_3.Math.D_c{B}_c^{\top }\right)+k_g{I}_{3n}A\delta x=\frac{3}{R^2}\left(I_3.Math.D_c\Delta \left(e_1^{0^{\top }}\delta e_1,.Math.,e_p^{0^{\top }}\delta e_p\right)B_c^{\top }\right){\tilde{x}}^0& \left(10\right)\end{array}$
C.II. Spectral Properties of A and G

(60) In order to determine the spectral properties of A and G:

(61) Lemma 1. The null space of A defined in (10) is a superset of eigenvectors which correspond to a rigid body translation and rotation of the flock; i.e.,
(A)⊇≙span([1,0,0].sup.T.Math.1.sub.n[0,1,0].sup.T.Math.1.sub.n,
[0,0,1].sup.T.Math.1.sub.n,P.sub.3n(I.sub.n.Math.J.sub.1)P.sub.3n.sup.−1{tilde over (x)}.sup.0,P.sub.3n(I.sub.n.Math.J.sub.2)P.sub.3n.sup.−1{tilde over (x)}.sup.0,
P.sub.3n(I.sub.n.Math.J.sub.3)P.sub.3n.sup.−1{tilde over (x)}.sup.0)
where J.sub.1, J.sub.2, J.sub.3 form a basis for so (3).
Proof: It is evident from (10) that (A) is a superset of the vectors δx which satisfy (I.sub.n.Math.B.sub.c.sup.T)δx=0 or e.sup.0.sub.i.sup.Tδe.sub.i=0 ∀i={1, . . . , p}. The former condition implies that δx=k.sub.1[1, 0, 0].sup.T.Math.1.sub.n+k.sub.2[0, 1, 0].sup.T.Math.1.sub.n+k.sub.3[0, 0, 1].sup.T.Math.1.sub.n, where k.sub.1, k.sub.2, and k.sub.3 are arbitrary constants. The latter condition is satisfied by δx.sub.i=Σ.sub.j=1.sup.3k′.sub.jJ.sub.jx.sub.i, for all constants k′.sub.j.
Assumption 1. The matrix A has exactly six eigenvalues which are equal to 0. Therefore, .sub.u(A)=(A).
Assumption 1 is satisfied by connected undirected graphs and by strongly connected and balanced digraphs.
Assumption 2. The Jacobian G has the following properties: 1. All eigenvalues of G have non-positive real parts. 2. The algebraic and geometric multiplicities of the zero eigenvalue are equal to each other. 3. The null space (G)=[n.sup.T, 0.sub.1×3n].sup.T, where n∈(A)=.sub.u(A).
Assumption 2 always holds for an undirected graph satisfying Assumption 1.
C.III. Stability Analysis

(62) To perform the stability analysis, the center manifold theorem can be used to show that trajectories which start away from S({tilde over (x)}.sup.0), at least locally, converge to S({tilde over (x)}.sup.0) at an exponential rate. The proof proceeds in two steps. First, it is shown that there exists a center manifold when Assumption 2 is satisfied. It is noted that the set S({tilde over (x)}.sup.0) is also a center manifold. In the second step, the property that center manifolds are arbitrarily close to each other can be used to complete the proof.

(63) Lemma 2. Suppose that the flocking dynamics satisfy Assumption 2. Then, for every steady state {tilde over (x)}.sup.0, there exists an invariant manifold ε.sup.c ≙ε.sup.c({tilde over (x)}.sup.0) such that any trajectory starting around ε.sup.c converges at an exponential rate to ε.sup.c.

(64) Proof: From Assumption 2, it is known that the Jacobian G, evaluated at {tilde over (x)}.sup.0, has six zero eigenvalues and the other eigenvalues are negative. Thus, it follows that from the center manifold theorem that there exists a six-dimensional center manifold ε.sup.c such that trajectories starting outside ε.sup.c converge at an exponential rate to ε.sup.c.
Theorem 1. The set S({tilde over (x)}.sup.0) is exponentially stable.
Proof: It is noted that S({tilde over (x)}.sup.0) is itself a center manifold of the dynamics. From Lemma 2, it is known that trajectories starting in a neighborhood of x.sup.0 converge at an exponential rate to the center manifold ε.sup.c({tilde over (x)}.sup.0). Recall that any two center manifolds about an equilibrium point {tilde over (x)}.sup.0 differ by transcendentally small terms, and every equilibrium point in the vicinity of {tilde over (x)}.sup.0 lies on every center manifold ε.sup.c({tilde over (x)}.sup.0). Thus, a trajectory starting in a neighborhood of {tilde over (x)}.sup.0 converges exponentially fast to S({tilde over (x)}.sup.0).

(65) The discussion above shows that S({tilde over (x)}.sup.0) is exponentially stable, 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 preserved. Below are analytical formulae for estimating a set of permissible pursuer positions based purely on local topological considerations.

(66) In addition to stability, for the purpose of herding, it is useful to have the property of time-scale separation between the synchronization of the flocking dynamics to S({tilde over (x)}.sup.0) on the one hand, and the translational dynamics of the center of gravity of the flock (whose time constant, as shown in above, is 1/k.sub.g) on the other. This can be achieved by a suitable choice of k.sub.s and k.sub.a for a given graph topology.

(67) D. Estimation of the Permissible Set of Pursuer Positions

(68) 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 R.sub.agg in FIG. 2 from the point of view of preserving the local topology of the flock, and is used in below to determine the feasible positions for the pursuer in relation to the flock.

(69) The influence exerted by the pursuer can cause one of two effects in extreme circumstances. In one case, the pursuer can push a bird to within an unacceptable distance of its neighbor. This scenario is likely in dense flocks, as shown in FIG. 7. In the second case, the pursuer can cause the link between two neighbors to be broken by pushing them beyond their communication distance R.sub.com. This scenario, illustrated in FIG. 8, is generally more plausible in sparse flocks. The minimum permissible distance between two birds is written as c R.sub.safe, where c<1 is a constant that depends on the species of birds and the pursuer represented by the drone.

(70) D.I. Maintaining Minimum Allowable Distance Between Neighbors

(71) 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 accordance with an embodiment of the invention in the dense flock of FIG. 7.

(72) A conservative estimate for the minimum approach distance between the pursuer and the bird ‘1’ can be found from the local neighborhood of FIG. 7. 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’ arising as a consequence of repulsion by the pursuer. Balancing these two forces when the distance between ‘1’ and ‘2’ is c R.sub.safe (thereby ensuring that the minimum approach distance is no less than R.sub.safe) gives the minimum approach distance ∥r.sub.p1∥.sub.min:

(73) $\begin{array}{cc}\frac{k_p}{{.Math.r_{p1}.Math.}_{\min }^2}=k_s.Math.{\mathrm{cR}}_{\mathrm{safe}}\left(1-\frac{R_{\mathrm{safe}}^3}{{\left(c{R}_{\mathrm{safe}}\right)}^3}\right).Math.⟹{.Math.r_{p1}.Math.}_{\min }=\sqrt{\frac{c^2{k}_p}{\left(1-c^3\right)k_s{R}_{\mathrm{safe}}}}& \left(11\right)\end{array}$
D.III. Preserving Communication Between Neighboring Birds

(74) In sparse flocks, it is 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. 9 in accordance with an embodiment of the invention, involving just two birds, and assume that the pursuer approaches along the perpendicular bisector of the edge. If R.sub.com is the maximum permissible distance between two boundary agents for the underlying graph to be preserved, the following condition for the minimum permissible ∥r.sub.p1∥ is obtained

(75) 0$\begin{array}{cc}\frac{k_p}{{.Math.r_{p1}.Math.}^2}\times \frac{R_{\mathrm{com}}}{2.Math.r_{p1}.Math.}=k_s\left(1-\frac{R_{\mathrm{safe}}^3}{R_{\mathrm{com}}^3}\right)R_{\mathrm{com}}⟹{.Math.r_{p1}.Math.}_{\min }={\left(\frac{k_p}{2k_s\left(1-\frac{R_{\mathrm{safe}}^3}{R_{\mathrm{com}}^3}\right)}\right)}^{1/3}& \left(12\right)\end{array}$
Below, example estimates for ∥r.sub.p1∥.sub.min are used as part of the motion planning strategy for the pursuer.
Definition 1. Define a set X.sub.p of permissible pursuer positions in relation to the flock as:

(76) $\begin{array}{cc}{\chi }_p=\left\{x_p|R_{\min }\le \underset{i\in V}{\min }.Math.x_p-x_i.Math.\le R_{\mathrm{fear}}\right\},& \left(13\right)\end{array}$
where R.sub.min is the maximum of R.sub.agg and either (11) or (12) depending on the topology of the flock.
E. The M-Waypoint Herding Algorithm
The above established conditions for stability and robustness of the flock, and derived approximations for the approach distance between the flock and the pursuer. In this section, the problem of herding flocks without fracturing them is solved using waypoints generated by modeling the ensemble behavior of the flock. A version of the m-waypoint herding algorithm in accordance with an embodiment of the invention is illustrated in FIG. 10. A set of objectives that the pursuer's trajectory, x.sub.p(t), must satisfy in order herd the flock successfully are provided below. The m-waypoint algorithm is then obtained as an approximate, but efficient, solution to the problem of ensuring that x.sub.p(t) meets these objectives.
E.I. Formulation of the Herding Problem

(77) The coordinates of the flock's centroid and its velocity are given by

(78) $x_{\mathrm{cg}}=\frac{1}{n}{.Math.}_{i=1}^n{x}_i,{\upsilon }_{\mathrm{cg}}=\frac{1}{n}{.Math.}_{i=1}^n{\upsilon }_i.$
Using (4) and (5), obtain

(79) $\begin{array}{cc}{\stackrel{.}{x}}_{\mathrm{cg}}={\upsilon }_{\mathrm{cg}}{\stackrel{.}{\upsilon }}_{\mathrm{cg}}=k_g\left({\upsilon }_d-{\upsilon }_{\mathrm{cg}}\right)+F_p\left(x_p\right)+f\left(x,\upsilon \right)F_p\left(x_p\right)\stackrel{\Delta }{=}\frac{k_p}{n}\underset{i\in {𝒩}_p}{.Math.}H\left(r_{\mathrm{pi}}\right){\stackrel{.}{x}}_p=u_p& \left(14\right)\end{array}$
where denotes the subset of the flock that lies within R.sub.fear of the pursuer; the pursuer's velocity, u.sub.p, is a control variable for the herding algorithm. The term f(x,v) in zero when the graph is undirected (since 1.sub.n.sup.TB.sub.c=0) or if it has synchronized to a steady state configuration. This would occur naturally when the flock synchronizes on a faster time scale than the dynamics of its CG. Since the goal is for 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 x.sub.div is driven to zero. Define
r.sub.dc(t)≙x.sub.div(t)−x.sub.cg(t),q≙r.sub.dc×v.sub.cg  (15)

(80) Recall that {circumflex over (k)}.sup.Tx.sub.div(t)={circumflex over (k)}.sup.Tx.sub.cg(t)=h(t) (the altitude of the flock). Since x.sub.div(t) lies on a fixed vertical line for all t, then {circumflex over (k)}×{dot over (x)}.sub.div(t)=0. Since {dot over (r)}.sub.dc(t)={dot over (x)}.sub.div(t)−v.sub.cg(t), the following expression is obtained for the dynamics of q:
{dot over (q)}=r.sub.dc×{dot over (v)}.sub.cg+{dot over (x)}.sub.div×v.sub.cg
=−k.sub.gq+k.sub.g(r.sub.dc×v.sub.d)+r.sub.dc×F.sub.p(x.sub.p)+r.sub.dc×f(x,v)+{dot over (x)}.sub.div×v.sub.cg
Next, define q.sub.k ≙{circumflex over (k)}.sup.Tq. Note that {circumflex over (k)}.sup.T({dot over (x)}.sub.div×v.sub.cg)=v.sub.cg.sup.T({circumflex over (k)}×{dot over (x)}.sub.div)=0. Thus, the dynamics of q.sub.k are given by
{dot over (q)}.sub.k+k.sub.gq.sub.k={circumflex over (k)}.sup.T(r.sub.dc×(k.sub.gv.sub.d+f(x,v))+r.sub.dc×F.sub.p(x.sub.p))  (16)

(81) Denote the amount of deviation that can be produced by placing the pursuer at x.sub.p using the right hand-side of (16):
ρ(x.sub.p)≙{circumflex over (k)}.sup.T(r.sub.dc×(k.sub.gv.sub.d+f(x,v))+r.sub.dc×F.sub.p(x.sub.p))  (17)
If ρ(x.sub.p)=0 for all t, then it is possible to deduce from (16) that q.sub.k.fwdarw.0 and the CG of the flock moves in a straight line (represented as a solid line in FIG. 9 in accordance with an embodiment of the invention) towards x.sub.div (from the definition of q.sub.k). Further, 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 x.sub.div in FIG. 9. The dashed line is parallel to v.sub.d, and once the flock's CG reaches it, the herding algorithm can safely terminate. This requires that q.sub.k≥0 uniformly (or q.sub.k≤0 uniformly, depending on the choice of x.sub.div) during the course of herding. Without loss of generality, it can be assumed that x.sub.div is chosen such that sign({circumflex over (k)}.sup.T(v.sub.d×r.sub.dc))>0 while commencing herding and set the control objective to maximizing ρ(x.sub.p)≥0 while sign({circumflex over (k)}.sup.T(v.sub.d×r.sub.dc))>0 (see FIG. 9).
E.II. Calculating m Waypoints

(82) A solution to the aforementioned control problem is to compute the trajectory of x.sub.p(t) which maximizes ρ(x.sub.p), and get the pursuer to track it. It is 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. 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, a sub-optimal approach can be employed wherein the flock is engaged through different waypoints in a given timefranme.

(83) The waypoints are chosen by sampling the set X.sub.p from Definition 1. Sampling is preferred to statically defined waypoints 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. The set of m waypoints can be formally identified as follows.

(84) Definition 2. The set X.sub.p.sup.m is defined by construction. The waypoint selection algorithm, illustrated in accordance with an embodiment of the invention in FIG. 11, samples X.sub.p uniformly. Next, up to m waypoints with the highest deviation are identified such that no two waypoints are within a prescribed distance, denoted δ.sub.w, of each other. These waypoints constitute the set X.sub.p.sup.m.
Even for a convex shaped flock, the set X.sub.p.sup.m need not be connected. This enables the use of random sampling for construction.
F. Motion Planning for the Pursuer

(85) The motion planner solves for the pursuer's velocity u.sub.p(t) by commanding one of two motions, as follows. 1. FLY: the pursuer takes the fastest path to the commanded node. Collision avoidance is achieved using artificial potential fields, an alternative to which is a real-time, online motion planner. 2. ENGAGE: using a virtual leader-based approach, the pursuer commands u.sub.p(t) to maintain its position at the chosen waypoint in relation to the flock's centroid for a pre-determined duration τ.sub.e. The engagement is terminated if the distance between two neighboring birds in .sub.p approaches the communication radius, R.sub.com.
G. Tuning the Herding Algorithm

(86) In order to promote successful herding, a condition is derived in the form of the minimum allowable distance from the protected zone at which the herding must begin. If the herding commences beyond this distance, it will succeed with an elevated likelihood. Assume that f(x, v)=0; i.e., the underlying graph is undirected or the flock has synchronized to a steady state.

(87) To begin, ignore the dynamics of the pursuer, and recall that the control objective is to maximize ρ(x.sub.p)≥0. Consider the conservative case ρ(x.sub.p)=0 for all t during the course of herding. This case is limiting in that the distance at which the herding needs to be commenced can be lesser when larger values of ρ(x.sub.p) are attainable.

(88) In order to achieve ρ(x.sub.p)=0, set x.sub.p=x.sub.p* where F.sub.p(x.sub.p*)=−k.sub.g({circumflex over (k)}.sup.T({circumflex over (r)}.sub.dc×v.sub.d))({circumflex over (k)}×{circumflex over (r)}.sub.dc). Since {circumflex over (r)}.sub.dc=r.sub.dc/∥r.sub.dc∥, and v.sub.d lie in the horizontal plane, it follows that ∥F.sub.p∥=k.sub.g∥{circumflex over (r)}.sub.dc×v.sub.d∥. Let ρ.sub.F denote the upper bound on ∥F.sub.p∥, which is known. It is clear then that the flock should be made to satisfy ∥{circumflex over (r)}.sub.dc×v.sub.d∥<ρ.sub.F/k.sub.g ∀t, which, in turn, means that the flock must be kept outside the cone shown in FIG. 12. This is an important insight: it shows that the herding is successful only if it begins when the horizontal distance between the centre of the flock and the center of PZ is greater than or equal to

(89) $\begin{array}{cc}{D}_{p,\min }\stackrel{\Delta }{=}\frac{R_{\mathrm{div}}}{\tan {\theta }_{\max }},{\theta }_{\max }={\sin }^{-1}\left(\frac{{\rho }_F}{k_g.Math.{\upsilon }_d.Math.}\right),& \left(18\right)\end{array}$
where R.sub.div was defined above.

(90) While the solution x.sub.p* appears to solve the problem in principle, there is the possibility that the trajectory x.sub.p* 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 place in pulses. Processes described herein can be refactored in light of this pulsed interaction.

(91) Let τ.sub.e denote the duration of any given engagement between the pursuer and the flock, and let τ.sub.f denote the time taken by the bird to fly between two waypoints. During the time τ.sub.f, the flock receives no external stimulus and its velocity tends to align to v.sub.d. Assuming that an engagement begins at time t.sub.0, the dynamics of the flock in the time interval [t.sub.0, t.sub.0+τ.sub.e+τ.sub.f] can be described via the switching dynamics

(92) $\begin{array}{cc}{\stackrel{.}{\upsilon }}_{\mathrm{cg}}+k_g{\upsilon }_{\mathrm{cg}}=\{\begin{array}{cc}{k}_g{\upsilon }_d^{.Math..Math.},& t\in \left[t_0,t_0+{\tau }_e\right)\\ k_g{\upsilon }_d,& t\in \left[t_0+{\tau }_e,t_0+{\tau }_e+{\tau }_f\right)\end{array}& \left(19\right)\end{array}$
where v.sub.d.sup.∥=v.sub.d+F.sub.p/k.sub.g (see FIG. 13 as an example in accordance with an embodiment of the invention). When x.sub.p=x.sub.p*, v.sub.d.sup.∥ is along r.sub.dc at every instant in time, which is why the superscript ∥ is used here. Assume that the flock switches instantaneously between two states. During the engagement phase, the flock moves at an angle θ to the original direction coinciding with v.sub.d. When the pursuer does not engage the flock, it moves along v.sub.d. This is depicted in FIG. 14 in accordance with an embodiment of the invention.

(93) The terms ∥v.sub.d.sup.∥∥ and θ can be be estimated empirically since the precise interaction between the flock and the pursuer is highly case-specific. The magnitude of v.sub.d.sup.∥ depends on whether the flock is driven from the front or from the rear. Since the intent is for the net motion to be perpendicular v.sub.d, it is reasonable to assume that the average force also acts perpendicular to v.sub.d. Thus,

(94) $.Math.v_d^{.Math..Math.}.Math.=\sqrt{{.Math.{\upsilon }_d.Math.}^2+\frac{{.Math.F_p.Math.}^2}{k_g^2}},\theta ={\cos }^{-1}\left(.Math.{\upsilon }_d.Math./.Math.{\upsilon }_d^{.Math..Math.}.Math.\right)$

(95) Consequently,

(96) Theorem 2. Given the approximate values of ∥v.sub.d.sup.∥∥ and θ, the refined value of D.sub.p,min is given by

(97) $D_{p,\min }=R_{\mathrm{div}}\cot \theta \left(1+\frac{{\tau }_f}{{\tau }_e}\right)$
Proof Let n.sub.s denote the number of engagement pulses. From FIG. 14, it is apparent that there can be at most n.sub.s pulses wherein the flock is not engaged with the pursuer. During each engagement pulse, referring to the geometric convention of FIG. 14, the flock shifts through a distance ∥v.sub.d.sup.∥∥ τ.sub.e sin θ. Thus,

(98) $n_s=\frac{R_{\mathrm{div}}}{.Math.{\upsilon }_d^{.Math..Math.}.Math.{\tau }_e\sin \theta }$
Furthermore, during each engagement phase, the flock translates horizontally through a distance ∥v.sub.d.sup.∥∥ τ.sub.e cos θ. During the non-engagement phase, the horizontally translation is at moat ∥v.sub.d∥τ.sub.f. Thus, the minimum horizontal translation is given by

(99) $\begin{array}{c}{D}_{p,\min }=n_s\left(.Math.{\upsilon }_d.Math.{\tau }_f+.Math.{\upsilon }_d^{.Math..Math.}.Math.{\tau }_e\cos \theta \right)\\ =R_{\mathrm{div}}\left(\frac{.Math.{\upsilon }_d.Math.}{.Math.{\upsilon }_d^{.Math..Math.}.Math.}\frac{{\tau }_f}{{\tau }_e}\frac{1}{\sin \theta }+\cot \theta \right)\end{array}$
Setting cos θ=∥v.sub.d∥/∥v.sub.d.sup.∥∥ yields

(100) 0$D_{p,\min }=R_{div}\cot \theta \left(1{+}_{{\tau }_e}^{\underset{¯}{{\tau }_f}}\right).$
Notice that (18) is recovered if when τ.sub.f=0 and θ=θ.sub.max. This completes the proof. Using the above, flock flight dynamics can be modeled and effective waypoints can be generated.

(101) Although the present invention has been described in certain specific aspects, many additional modifications and variations would be apparent to those skilled in the art. It is therefore to be understood that the present invention can be practiced otherwise than specifically described without departing from the scope and spirit of the present invention. Thus, embodiments of the present invention should be considered in all respects as illustrative and not restrictive. Accordingly, the scope of the invention should be determined not by the embodiments illustrated, but by the appended claims and their equivalents.