Keywords

These keywords were added by machine and not by the authors. This process is experimental and the keywords may be updated as the learning algorithm improves.

1 Introduction

Military forces face ever increasing challenges to provide timely and accurate information on targets of interest, especially those targets that are mobile and elusive in nature. These tasks expand significantly in complexity when the targets are operating in an urban environment. The use of multiple unmanned vehicles to provide this target information allows our military personnel to stay out of the line of fire. However, many remotely controlled UAVs (i.e., swarms) require as many skilled pilots as there are swarm members, and these pilots must be able to deconflict airspace demands, mission requirements, and situational changes in near real time (Bamburger et al. 2006). On the other hand, autonomous unmanned vehicles allow military personnel to focus on more important issues like interpreting the gathered information, as opposed to determining how to acquire the information (Hirsch et al. 2007). Hence, there is a need to build intelligent unmanned vehicles that can plan and adapt autonomously to the environment they perceive. The clear benefit is shortened mission-critical decision chains.

There has recently been much research done in the area of autonomous vehicle control for surveillance-type missions. Almost all of the research has dealt with centralized cooperative control, with little research concerned with the more realistic decentralized problem (Shima and Rasmussen 2009). Steinberg (2006) provided an overview on research and limitations of autonomous technologies for the control of heterogeneous unmanned naval vehicles. Experiments in this paper examined aspects such as multi-vehicle task allocation, dynamic replanning of vehicle tasks, as well as human-in-the-loop management. Constraints considered in the experiments included pop-up threats, adverse weather conditions, and communication issues between the autonomous vehicles, among others. Liang et al. (2010) present a decision support framework to accurately reconstruct the current picture of the battlespace, by correctly identifying target tracks (i.e., target location, movement, identity) as seen by multiple wide area search munitions. Ahmadzadeh et al. (2006) described their Time Critical Coverage planner as a component of the Office of Naval Research Autonomy program, ICARUS. Each autonomous vehicle was modeled as a Dubin’s vehicle (Dubins 1957), whereby the vehicles were assumed to be point masses with constant speed and a prescribed minimum turning radius. The vehicles also had prescribed starting and ending spatial-temporal locations, as well as polygonal obstacles to be avoided throughout flight. The objective was to determine the flight path of the UAVs to maximize the total sensor footprint over the region of interest. The algorithm utilized to solve this problem was based on sampling a discretized search graph (LaValle 2006).

Ma and Miller (2005) implemented a receding-horizon approach to solve a mixed-integer linear program modeling a trajectory planning problem. They limited their focus to a single vehicle navigating through three-dimensional obstacles and terrain. They considered threat avoidance and made use of the commercial software CPLEX (ILOG CPLEX 2008) to solve their problem. Shetty et al. (2008) considered the strategic routing of multiple unmanned combat vehicles to service multiple potential targets in space. They formulated this as a mixed-integer linear program, and through a decomposition scheme looked at solving the target assignment problem (vehicles to targets) and then determining the tour that each vehicle should take to service their assigned targets (a classical vehicle routing problem). They implemented a tabu-search heuristic to find solutions to their problem. However, they assumed the vehicles were holonomic, which enabled the mixed-integer linear program formulation. Kenefic (2008) utilized techniques from particle swarm optimization (Kennedy and Eberhart 1995) to efficiently define tours for a Dubin’s vehicle, visiting multiple ground targets in two-dimensional space. Schumacher and Shima (2009) considered the problem of wide area search munitions, which are capable of searching for, identifying, and attacking targets. Whenever a new target is found, or a new task needs to be assigned, a capacitated transshipment assignment problem is solved, to determine the optimal assignment of munitions to tasks. Note that from one solution to the next solution, the assignment can change significantly.

Sylvester et al. (2004) presented a path-planning algorithm for two non-holonomic vehicles engaged in a docking maneuver. A bijection search method was used to determine the trajectory of the vehicles, such that the minimum turning radius constraint of each vehicle was satisfied. Santilli et al. (1995) and Bicchi et al. (1995) considered planning a path for a non-holonomic autonomous vehicle in the presence of fixed obstacles. Jiang et al. (1999) also presented a path planning algorithm for a non-holonomic vehicle subject to obstacles. This algorithm employed a global and local strategy to find the shortest path in two dimensions that was free of collisions with the obstacles. Schouwenaars et al. (2001) considered fuel-optimal paths for multiple vehicles. They formulated the problem as a mixed- integer linear program. The vehicles needed to move from an initial to final state, while avoiding vehicular collisions, as well as stationary and moving obstacles. Obstacle positions were assumed known a priori.

Kingston and Beard (2007) presented an algorithm to keep moving UAVs equally spaced (angularly) about a stationary target. The UAVs adapted their spacing based on local communication with other UAVs. Velocity bounds were derived so that the UAVs satisfied their kinematic constraints. They extended this approach to the case when the target was moving, but the path and velocity of the target was assumed known throughout. Gu et al. (2006) discussed the problem of cooperative estimation using a team of UAVs. They considered the goal of organizing the team’s configuration to achieve optimal position and velocity estimates of a moving ground target. Sinclair et al. (2007) and Doucette et al. (2009) considered a problem of cooperative control of aerial munitions during the attack phase of a stationary ground target, in order to refine the estimates of the target location. A dynamic programming solution was implemented to determine the paths for the aerial munitions. McLain et al. (2000) presented a cooperative control problem for UAVs to rendezvous at given locations, at the same time. The UAVs considered threat and fuel constraints, in determining their trajectories. A decomposition approach was employed, whereby at the team level, an arrival time was determined, and at the individual UAV level, an optimal path to reach the specified location at the arrival time was determined.

Rafi et al. (2006) presented an approach to have an autonomous vehicle follow a moving ground target. Their technique specified positional updates for the vehicle, in terms of the next time-step turning rate as well as orientation updates for the gimballed camera mounted on the vehicle. They tested their approach using one vehicle and one moving ground target. Sinha et al. (2005) considered cooperative control for tracking of targets by multiple UAVs. An information theoretic criterion was used to determine the future path of each UAV, so that the total information gain (corresponding to the detected targets) was maximized. The UAVs were assumed to have fixed speed, and each UAV determined its angular turn rate to maximize the expected information gain for the next-time step. Akselrod et al. (2007) presented an approach for multi-target tracking of ground targets using UAVs via an hierarchal Markov decision process framework and dynamic programming. Their objective was to maximize the information gained by the UAVs. Sinha et al. (2004) presented a method to determine the location of sensors for tracking of moving ground targets, so as to maximize the resultant information gain. A genetic algorithm was implemented to determine the sensor positions. Of note here is that it was assumed that the targets were moving in the same direction as the sensors and their relative position remained constant over time.

Close-range maneuvering and following of a moving target continue to pose significant research challenges (Rafi et al. 2006). Close-range maneuvering requires real-time dynamic replanning and decision making as well as optimization of many parameters (taking into account the physical constraints of the vehicle). The problem becomes even more complex when the goal is to track a moving target for which the target dynamics is not known. In Hirsch et al. (2012, 2011) and Hirsch and Ortiz- Pena (2010), Hirsch et al. developed a decentralized approach for the autonomous cooperative control of UAVs, with the goal of persistent and accurate tracking of moving ground targets in an urban domain. The UAVs were able to share limited information with neighboring UAVs (other UAVs in their communication region) and had to dynamically replan their flight paths, incorporating predicted target movements and replanned flight paths of their neighbors into their own decisionmaking process. Line of sight also plays a big role in the flight plan of the UAVs and was incorporated into the problem through the use of Plüker coordinates (Semple and Kneebone 1952; Stolfi 1991). However, it was assumed that the targets were already known.

In this chapter, the approach of Hirsch et al. (2012, 2011) is extended to include, in a decentralized framework, the UAVs actively searching for and detecting the targets, before tracking of the targets can commence. Since the UAVs have no knowledge of how many targets are present in the environment, at each decision-making step, the UAVs need to determine both the task they will perform (either searching for new targets or tracking those targets already detected) as well as determining the flight route to optimally accomplish their task. This results in a coupled task assignment/route planning mathematical formulation, which is highly nonlinear. A GRASP-SA heuristic is developed to efficiently solve the coupled problem. The solution quality is examined to determine its sensitivity to the communication capability of the UAVs. This chapter is organized as follows. Section 64.2 rigorously defines the problem of interest, discusses the dynamic feedback loop, and formulates the coupled task assignment/route planning problem as a nonlinear mathematical program. A hybrid heuristic for continuous global optimization is described in Sect. 64.3. This heuristic is utilized to solve the optimization problem at each time-step, for each UAV. Experimental results as the communication radius of the UAVs is varied are presented in Sect. 64.4. Section 64.5 provides some concluding remarks and future research directions.

2 Programming Formulation

2.1 Problem Definition

The overall problem addressed here is to provide (i) continual surveillance over a region of interest and (ii) accurately track all targets detected in this region. Hence, there are two tasks that a UAV can be performing at any given time: searching for targets or tracking those targets already detected. For this problem, there are N homogeneous autonomous vehicles flying at a fixed altitude. The vehicles are modeled as non-holonomic point masses on a two-dimensional plane with a minimum turning radius (i.e., a Dubin’s vehicle (Dubins 1957)). The vehicles have minimum and maximum speed restrictions, as well as a maximum communication range, beyond which they cannot share information. Each vehicle has an independent internal representation of the surveillance region as a continuous search uncertainty map. For each location \( \mathop Y\limits^ \to \) in the region, the search uncertainty map for a particular UAV stores the uncertainty (from this UAVs perspective) of a target currently at location \( \mathop Y\limits^ \to \). While in search mode, the UAV can update its search uncertainty map using information from its own onboard sensor as well as information from other UAVs currently in search mode (that can communicate with this UAV, i.e., its “neighbor” UAVs). While in tracking mode, the UAV can only update its search uncertainty map using information from neighbor UAVs that are in search mode. Similarly, each UAV has its own internal representation of the targets in the region of interest. When in search mode, the UAV can only update its target map from those neighbor UAVs in track mode. When in track mode, the UAV can update its target map based upon its local sensors as well as information provided from neighbor UAVs in track mode. The one exception to this is if in search mode, it is possible (and hoped) that a UAV will detect a “new” target. When this happens, this target is added to the UAV’s stored target map, and shared with neighbor UAVs.

The vehicles operate in a decentralized manner; at each time-step, every UAV processes an equivalent version of the same dynamic feedback loop, as presented in Fig. 64.1. The feedback loop is discussed from the standpoint of UAV i. At the current time, t c , the first step is for UAV i to move according to its planned route and continue to execute its current task (e.g., searching or tracking). Using onboard sensors, UAV i either searches its current field of view for new targets or attempts to sense the targets (known to UAV i ) that are within its line of sight. The neighbors of UAV i send information relating to their (a) current positions, trajectories, and tasking; (b) sensor characteristics; (c) search uncertainty maps; and (d) sensed target maps. At this point, UAV i creates its assessment of the world, represented as a fused search uncertainty map and a fused target location map. This fused picture is scored in some qualitative manner, based upon the current positions of UAV i and its neighbor UAVs, their current planned trajectories and tasking, as well as the extrapolated search uncertainty map and target tracks, over the planning horizon. If the resultant score is small, or if the elapsed time since the last replan for UAV i is large, then UAV i solves a coupled tasking/route planning optimization problem for itself and its neighbor UAVs, over the planning horizon. The solution to this problem is a tasking for each UAV and route for each UAV to fly in order to accomplish their tasking. The mathematical formulation for this optimization problem is detailed in Sects. 64.2.2–64.2.5. It is worth noting that UAV i updates its own flight path and tasking, but does not share any of this computed information with its neighbor UAVs. The reason for this is that the neighbors are going through this same feedback loop and may be incorporating additional knowledge not available to UAV i. The time is then incremented, and the dynamic loop continues.

Fig. 64.1
figure 1

Feedback control loop for UAV i

Full size image

2.2 Parameters

This section introduces the parameters incorporated into the dynamic tasking and flight plan optimization formulation. For the mathematical formulation to follow, the parameters, decision variables, and constraints are defined for all \(\hat \iota \in {\cal N}_i (t),t \in \left[ {t_c,t_c, + \Delta _t } \right],\ell \in \{ 1,...,{\rm{5}}\},h \in \{ 1,...,{\cal H}{\rm{\} }}j \in \{ 1,...,{\cal J}\},u \in {\rm{\{ 1,}}...{\rm{,4\} }}\), as appropriate:

  • t c = The current time;

  • Δt = The current planning horizon;

  • C d = The maximum distance at which any two UAVs can “communicate”, i.e., share information;

  • \( \mathcal N \) i (t) = The neighbors of UAV i, at time t, i.e., \(\hat \iota \in {\cal N}_i (t) \Rightarrow \left\| {P_i } \right. - \left. {P_{\hat \iota } (t)} \right\|_2 \le C_d \cdot {\rm{N}} \cdot {\rm{B}} \cdot :i \in {\cal N}_i (t);\)

  • The UAV sof interest (from UAV i ’s perspective) are indexed by \(\hat \iota \in {\cal N}_i (t)\);

  • The moving ground targets are indexed by j ∈ {1,..., \( \mathcal J \)};

  • The buildings (3D, rectangular, opaque obstacles) are indexed by h ∈ {1,..., ℋ};

  • \(\Omega _\iota \) = The minimum turning radius of UAV \(\hat \iota \)

  • \(P_{\hat \iota } ^c \) = The current position of UAV \(\hat \iota \) \(({\rm{N}}{\rm{.B}}{\rm{.: }}P_{\hat \iota } ^c = \{ x_{\hat \iota } ^c,y_{\hat \iota } ^c,z_{\hat \iota } ^c \} )\);

  • \(S_{\hat \iota } ^{{\rm{max}}} \) = The minimum speed of UAV \(\hat \iota \);

  • \(S_{\hat \iota } ^{{\rm{max}}} \) = The maximum speed of UAV \(\hat \iota \);

  • \({\rm{\varepsilon }}_{\rm{1}} ^{\min } \) = The minimum distance allowed between any two UAVs (to avoid UAV collisions);

  • \({\rm{\varepsilon }}_{\rm{2}} ^{\min } \) = The minimum distance allowed between any UAV and any known building. Assume this is set to 0, i.e., so that UAVs are constrained to not be within a building, but they can get infinitesimally close to the perimeter of each building. N.B.: this assumption is valid, as one can always artificially increase the size of the buildings, as appropriate;

  • \(Z_{\hat \iota } \) = The fixed altitude of UAV \(\hat \iota \);

  • \({\cal B}_h = \{ {\cal P}_{h\ell 4} \} _{\ell = 1} ^5 \) = The representation of building h, as a set of 5 rectangular regions (i.e., faces) in ℝ3, all oriented in the same counterclockwise fashion;

  • \({\cal P}_{h\ell } = \{ {\rm{\rho }}_{h\ell 1},...,{\rm{\rho }}_{h\ell 4} \} \) = The ℓ-th oriented rectangle (i.e., face) of building h;

  • \({\cal P}_{_{h\ell } } = \{ {\rm{\rho }}_{{\rm{h}}\ell {\rm{1}}},....,\rho _{h\ell 4} \} \) = The u-th point of the ℓ-th oriented rectangle (i.e., face) of building h;

  • ξ hℓ = {v hℓ ; d hℓ } = The plane containing face \( \mathcal P \) hℓ , represented as a normal vector v hℓ and distance to the origin d hℓ (v hℓ = [ρ hℓ3 − ρ hℓ2] × [ρ hℓ1 − ρ hℓ2], d hℓ = v hℓ · ρ hℓ1);

  • γ(x, y) = A function representing the “importance” level of position (x, y). The higher this value, the more important it is to provide accurate track of targets near (x y);

  • \(\Lambda _{\hat \iota } (t)\) = The Pluker coordinate representation (Semple and Kneebone 1952; Stolfi 1991) of the oriented line from the position of UAV \(Z_{\hat \iota } \) at time t, \(P_{\hat \iota } (t)\), to the estimated position of target j, at time t, \(X_j ^i (t)\);

  • Λ îj (\( \mathop Y\limits^ \to \), t) = The Plüker coordinate representation of the oriented line from the position of UAV \(\hat \iota \) at time t, \(P_{\hat \iota } (t)\), to position \( \mathop Y\limits^ \to \);

  • \(\hat \Lambda _{h\ell u,u + 1} \) = The Plüker coordinate representation of the oriented line from ρ hℓu to ρ hℓu+1, with u + 1 = 1 when u = 4;

  • \({\cal G}(\alpha,\hat \alpha ) = \alpha _1 \hat \alpha _6 - \alpha _2 \hat \alpha _5 + \alpha _3 \hat \alpha _4 + \alpha _4 \hat \alpha _3 - \alpha _5 \hat \alpha _2 + \alpha _6 \hat \alpha _1 \) where\(\alpha = \{ \alpha _1,....,\alpha _2 \} \) and \(\hat \alpha = \{ \hat \alpha _1,....,\hat \alpha _6 \} \) are the Plüker coordinate representations of two oriented lines;

  • \(R_{\hat \iota } (t)\) = The measurement noise for the sensor onboard UAV \(\hat \iota \), at time t. N.B.:

  • \(R_{\hat \iota } (t) = \left( {\matrix{ {\sigma _{r\hat \iota } } & 0 \cr 0 & {\sigma _{b\hat \iota } } \cr } } \right)\), where \({\rm{\sigma }}_{r\hat \iota } \) = the range measurement error for the radar platform on UAV \(\hat \iota \) and \({\rm{\sigma }}_{b\hat \iota } \) = the bearing measurement error for the radar platform on UAV \(\hat \iota \);

  • \(\underline {F_{\hat \iota } } (t)\) = The system dynamics matrix for the sensor onboard UAV \(\hat \iota \), at time t;

  • \(Q_{\hat \iota } (t)\) = The process noise for the sensor onboard UAV \(\hat \iota \), at time t ;

  • \(\underline {H_{\hat \iota } } (t)\) = The observation matrix for the sensor onboard UAV \(\hat \iota \), at time t ;

  • \(d_{\hat \iota } \) = The probability of detection for the sensor onboard UAV \(\hat \iota \);

  • χ = The factor by which to increase the search uncertainty map if there is no line of sight to a given position (in Constraint (64.9));

  • ℳ, ℳ = Large enough constants (needed for Constraints (64.7), (64.12), (64.13), (64.15), (64.16), (64.18), (64.19), (64.21), (64.22), (64.28), (64.29), (64.31), (64.32), (64.34), (64.35), (64.37), and (64.38)).

2.3 Decision Variables

This section defines the main decision variables for the mathematical formulation:

  • \(P_{\hat \iota } (t)\) = The position of UAV \(\hat \iota \), at time t \(({\rm{N}}{\rm{.B}}{\rm{.:}}\,P_{\hat \iota } (t) = \{ x_{\hat \iota } \left( t \right),y_{\hat \iota } \left( t \right),Z_{\hat \iota } \} )\);

  • \({\cal S}_{\hat \iota } \left( t \right)\) = The speed of UAV \(\hat \iota \), at time t;

  • \({\rm{\theta }}_{\hat \iota } (t)\) = The heading of UAV \(\hat \iota \), at time t;

  • \(\{ X_{\hat \iota j} (t),\Sigma _{\hat \iota j} (t)\} \) = The estimated position and covariance of target j by UAV \(\hat \iota \), at time t;

  • \(\{ X_j ^i (t),\Sigma _j ^i (t)\} \) = The fused position and covariance of target j, from UAV i ’s perspective, at time t;\(\bar \phi _{\hat \iota j\ell u,u + 1} (t) = \left\{ {\begin{array}{ll} 1 \quad{if\,line\,segment\Lambda _{\hat \iota j} \left( t \right)\,is\,oriented\,counterclokwise\,with\,respect\,to\,line\,segment\,\bar \Lambda _{h\ell u,u + 1},\,at\,time\,t\,;} \\ 0 \quad{o.w.} \end{array} } \right.\)

  • \(\bar \phi _{\hat \iota jh\ell } (t)\) = The number of line segments representing the ℓ-th face of building h that line segment \(\Lambda _{\hat \iota j} (t)\) is oriented counterclockwise with respect to, at time t;\({\rm{\beta }}_{\hat \iota jh\ell } (t) = \left\{ {\matrix{ 1 & {if\,line\,segment\Lambda _{\hat \iota j} \left( {\mathop Y\limits^ \to,t} \right)does\,not\,{\mathop{\rm int}} {\rm{er}}\sec {\rm{t}}\,the{\rm{ }}\ell {\rm{ - }}th\,face{\rm{ }}of{\rm{ }}bubilding\,h\,at\,time\,t\,\bar \Lambda _{h\ell u,u + 1},\,at\,time\,t\,;} \cr 0 & {o.w.} \cr } } \right.\)

  • \({\rm{\bar \beta }}_{\hat \iota jh\ell } (t)\) = The number of faces representing building h that line segment \(\Lambda _{\hat \iota j} (t)\) does not intersect, at time t;\({\rm{\bar \psi }}_{\hat \iota jh} (t) = \left\{ {\matrix{ 1 & {if\,there\,is\,line\,of\,sight\,from\,UAV\hat \iota \,to\,{\rm{t}}\arg {\rm{et}}\,j\,with\,respect\,to\,building\,h,\,at\,time\,t\,} \cr 0 & {o.w.} \cr } } \right.\)

  • \({\rm{\bar \psi }}_{\hat \iota jh} (t)\) = The number of buildings that do not restrict line of sight from UAV \(\hat \iota \) to target j, at time t;\({\rm{\psi }}_{\hat \iota j} \left( t \right) = \left\{ {\matrix{ 1 & {if\,UAV\,\hat \iota \,has\,line\,of\,sight\,to\,t\arg et\,j,\,at\,t} \cr 0 & {o.w.} \cr } } \right.;\) \(b_{\hat \iota } = \left\{ {\matrix{ 1 & {if\,UAV\,\hat \iota \,assigned\,to\,search\,\bmod e\,over\,the\,planning\,horizon\,\left[ {t_c,t_c + \delta _t } \right]} \cr 0 & {if\,UAV\,\hat \iota \,assigned\,to\,search\,\bmod e\,over\,the\,planning\,horizon\,\left[ {t_c,t_c + \delta _t } \right]} \cr } } \right.;\)

  • Γi (\( \left( {\mathop Y\limits^ \to,t} \right) \) = Search uncertainty map for UAV i at time t and position \( \mathop Y\limits^ \to \);\(\bar \phi _{\hat \iota h\ell u,u + 1} \left( {\mathop Y\limits^ \to,t} \right) = \left\{ {\matrix{ 1 & {if\,line\,segment\,\Lambda _{\hat \iota } } \cr 0 & {o.w.} \cr } } \right.\left( {\mathop Y\limits^ \to,t} \right)\,is\,oriented\,counterclockwise\,with\,respect\,to\,line\,segment\,\bar \Lambda _{h\ell u,u + 1},\,at\,time\,t;\)

  • \(\bar \phi _{\hat \iota h\ell } \left( {\mathop Y\limits^ \to,t} \right)\) = The number of line segments representing the ℓ-th face of building h that line segment \(\Lambda _{\hat \iota } \left( {\mathop Y\limits^ \to,t} \right)\) is oriented counterclockwise with respect to, at time t;\({\rm{\bar \beta }}_{\hat \iota h} \left( {\mathop Y\limits^ \to,t} \right) = \left\{ {\matrix{ 1 & {if\,line\,segment\,\Lambda _{\hat \iota } \left( {\mathop Y\limits^ \to,t} \right)\,does\,not\,{\rm{intersect}}\,the\ell - the\,face\,of\,building\,h,\,at\,time\,t} \cr 0 & {o.w.} \cr } } \right.\)

  • \({\rm{\bar \beta }}_{\hat \iota h} \left( {\mathop Y\limits^ \to,t} \right)\) = The number of faces representing building h that line segment \(\Lambda _{\hat \iota } \left( {\mathop Y\limits^ \to,t} \right)\) does not intersect, at time t;\({\rm{\bar \psi }}_{\hat \iota h} \left( {\mathop Y\limits^ \to,t} \right) = \left\{ {\matrix{ 1 & {if\,there\,is\,line\,of\,sight\,from\,UAV\,\hat \iota \,to\,positon\,\mathop Y\limits^ \to\,with\,respect\,to\,building\,h,\,at\,time\,t} \cr 0 & {o.w.} \cr } } \right.\)

  • \({\rm{\hat \psi }}_{\hat \iota } \left( {\mathop Y\limits^ \to,t} \right) \) = The number of buildings that do not restrict line of sight from UAV \(\hat \iota \) to position \( \mathop Y\limits^ \to \), at time t;\({\rm{\psi }}_{\rm{o}} \left( {\mathop Y\limits^ \to,t} \right) = \left\{ {\matrix{ 1 & {if\,UAV\,\hat \iota \,has\,line\,of\,sight\,to\,postition\,\mathop Y\limits^ \to,\,at\,time\,t} \cr 0 & {o.w.} \cr } } \right.;\) \({\rm{\psi }}_o \left( {\mathop Y\limits^ \to,t} \right) = \left\{ {\matrix{ 1 & {if\,neither\,UAV\,i\,nor\,any\,neighbors\,of\,UAV\,i\,has\,line\,of\,sight\,to\,position\, \mathop Y\limits^ \to,\,at\,time\,t} \cr 0 & {o.w.} \cr } } \right.;\)

2.4 Constraints

$$P_{\hat \iota } \left( {t_c } \right) = P_{\hat \iota } ^c \,\forall \hat \iota $$
(64.1)
$${{\partial x_{\hat \iota } \left( t \right)} \over {\partial t}} = {\cal S}_{\hat \iota } \left( t \right)\cos \,\left[ {\theta _{\hat \iota } \left( t \right)\forall \hat \iota,t} \right]$$
(64.2)
$${{\partial y_{\hat \iota \left( t \right)} } \over {\partial t}} = {\cal S}_{\hat \iota } \left( t \right)\sin \left[ {\theta _{\hat \iota } \left( t \right)} \right]\forall \hat \iota,t$$
(64.3)
$$\left| {{{\partial {\rm{\theta }}_{\hat \iota } \left( t \right)} \over {\partial t}}} \right| \le \Omega _{\hat \iota } \forall \hat \iota,t$$
(64.4)
$${\cal S}_{\hat \iota } ^{,\min } \le {\cal S}_{\hat \iota } \left( t \right) \le {\cal S}_{\hat \iota } ^{,\min } \,\forall \hat \iota,t$$
(64.5)
$$\left\| {P_{\hat \iota 1} \left( t \right) - P_{\hat \iota 2} \left( t \right)} \right\|_2 \ge {\rm{\varepsilon }}_{\rm{1}} ^{\min } \forall \hat \iota,t$$
(64.6)
$$P_{\hat \iota } \left( t \right) \cdot v_{h\ell } + d_{h\ell } \ge - \mu _{\hat \iota h\ell } \left( t \right){\cal M}\,\forall \hat \iota,h\,\ell,t$$
(64.7)
$$\sum\limits_{\ell = 1}^5 {\mu _{\hat \iota h\ell } \left( t \right) \le 4\forall \hat \iota,h,\ell,t} $$
(64.8)
$$\begin{array}{ll} {{{\partial \Gamma _i \left( {\mathop Y\limits^ \to,t} \right)} \over {\partial t}} = } & {\left[ {\prod\limits_{\hat \iota \in {\mathcal N}_i \left( t \right)} {\left( {1 - \bar d_{\hat i} } \right)^{b_{\hat i} {\rm{\psi }}_{\hat i} \left( {\mathop Y\limits^ \to,t} \right)} } } \right]} {\Gamma _i \left( {\mathop Y\limits^ \to,t} \right)} { + {\rm{\psi }}_{\rm{o}} \left( {\mathop Y\limits^ \to,t} \right) \cdot \chi \cdot \Gamma _i \left( {\mathop Y\limits^ \to,t} \right)} {\forall t,\mathop Y\limits^ \to} \end{array}$$
(64.9)
$${\rm{\psi }}_{\rm{o}} \left( {\mathop Y\limits^ \to,t} \right) \le 1 - b_{\hat \iota } {\rm{\psi }}_{_{\hat \iota } } \left( {\mathop Y\limits^ \to,t} \right)> \forall \hat \iota, t\,\mathop Y\limits^ \to$$
(64.10)
$${\bf{\psi }}_o \left( {\mathop Y\limits^ \to,t} \right)+ \sum\limits_{_{\hat \iota } \in {\mathcal N}i\left( t \right)} b_{_{\hat \iota } } {\rm{\psi }}_{_{\hat \iota } }\left( {\mathop Y\limits^ \to,t} \right)>0\,\forall\hat \iota,\mathop Y\limits^ \to$$
(64.11)
$${\mathcal G}( \Lambda _{_{\hat \iota } } \left( {\mathop Y\limits^ \to,t} \right),\hat \Lambda _{h\ell u,u + 1}) - (1 - b_{_{\hat \iota } } )\bar {\mathcal M} \le \bar \phi _{\hat \iota h\ell u,u + 1} \left( {\mathop Y\limits^ \to,t} \right){\mathcal M}\forall \hat \iota,\mathop Y\limits^ \to,h,\ell,u,t$$
(64.12)
$$ - {\mathcal G}{\rm{(}}\Lambda _{\hat \iota } \left( {\mathop Y\limits^ \to,t} \right),\hat \Lambda _{h\ell u,u + 1} ) - \left( {1 - b_{\hat \iota } } \right)\bar {\mathcal M}{\rm{ < }}\left( {{\rm{1 - }}\bar \phi _{\hat \iota h\ell u,u + 1} \left( {\mathop Y\limits^ \to,t} \right)} \right){\mathcal M}\forall \hat \iota,\mathop Y\limits^ \to,h,\ell,u,t$$
(64.13)
$$\bar \phi _{\hat \iota h\ell } \left( {\mathop Y\limits^ \to,t} \right) = \sum\limits_{u = 1}^4 {\bar \phi _{\hat \iota h\ell u,u + 1} \left( {\mathop Y\limits^ \to,t} \right)\forall \,\hat \iota,\mathop Y\limits^ \to,h,\ell,t} $$
(64.14)
$$\beta _{\hat \iota h\ell } \left( {\mathop Y\limits^ \to,t} \right) - \left( {1 - b_{\hat \iota } } \right)\bar {\mathcal M} \le 4 - \bar \phi _{\hat \iota h\ell } \left( {\mathop Y\limits^ \to,t} \right)\forall \,\hat \iota,\mathop Y\limits^ \to,h,\ell,t$$
(64.15)
$$\beta _{\hat \iota h\ell } \left( {\mathop Y\limits^ \to,t} \right){\mathcal M} + \left( {1 - b_{\hat \iota } } \right)\bar {\mathcal M} \ge 4 - \bar \phi _{\hat \iota h\ell } \left( {\mathop Y\limits^ \to,t} \right)\forall \, \hat \iota,\mathop Y\limits^ \to,h,\ell,t$$
(64.16)
$$\beta _{\hat \iota h\ell } \left( {\mathop Y\limits^ \to,t} \right) = \sum\limits_{\ell = 1}^5 {\beta _{\hat \iota h\ell } \left( {\mathop Y\limits^ \to,t} \right)\forall \, \hat \iota,\mathop Y\limits^ \to,h,t} $$
(64.17)
$${\rm{\psi }}_{\hat \iota h} \left( {\mathop Y\limits^ \to,t} \right) - \left( {1 - b_{\hat \iota } } \right)\bar {\mathcal M} \le \beta _{\hat \iota h\ell } \left( {\mathop Y\limits^ \to,t} \right)\forall \, \hat \iota \mathop Y\limits^ \to,h,t$$
(64.18)
$$1 - {\rm{\bar \psi }}_{\hat \iota h} \left( {\mathop Y\limits^ \to,t} \right) - \left( {1 - b_{\hat \iota } } \right)\bar {\mathcal M} \le 5 - \bar \beta _{\hat \iota h} \left( {\mathop Y\limits^ \to,t} \right)\forall \, \hat \iota,\mathop Y\limits^ \to,h,t$$
(64.19)
$${\rm{\bar \psi }}_{\hat \iota } \left( {\mathop Y\limits^ \to,t} \right) = \sum\limits_{h = 1}^{\mathcal H} {{\rm{\bar \psi }}_{\hat \iota h} \left( {\mathop Y\limits^ \to,t} \right)\forall \, \hat \iota,\mathop Y\limits^ \to,t} $$
(64.20)
$${\rm{\bar \psi }}_{\hat \iota } \left( {\mathop Y\limits^ \to,t} \right) - \left( {1 - b_{\hat \iota } } \right)\bar {\mathcal M} \le {\rm{\bar \psi }}_{\hat \iota h} \left( {\mathop Y\limits^ \to,t} \right)\forall \, \hat \iota,\mathop Y\limits^ \to,t$$
(64.21)
$$1 - {\rm{\psi }}\left( {\mathop Y\limits^ \to,t} \right) - \left( {1 - b_{\hat i} } \right)\bar {\mathcal M} \le {\mathcal H}{\mathcal E} - {\rm{\hat \psi }}_{\hat \iota } \left( {\mathop Y\limits^ \to,t} \right)\forall \, \hat \iota \mathop Y\limits^ \to,t$$
(64.22)
$$\sum\nolimits_j^i {\left( t \right) = \left[ {\sum\limits_{\hat \iota \in {\cal N}i\left( t \right)} {\left( {1 - b_{\hat \iota } } \right){\rm{\psi }}_{\hat \iota j} \left( t \right)\sum\nolimits_{_{\hat \iota j} }^{ - 1} {\left( t \right)} } } \right]} ^{ - 1} \forall j,t$$
(64.23)
$$X_j ^i \left( t \right) = \sum\nolimits_j^i {\left( t \right) \cdot \left[ {\sum\limits_{\hat \iota \in {\cal N}\left( t \right)} {\left( {1 - b_{\hat \iota } } \right){\rm{\psi }}_{\hat \iota j} \left( t \right)\sum\nolimits_{\hat \iota j}^{ - 1} {\left( t \right)X_{\hat \iota j} \left( t \right)} } } \right]\forall j,t} $$
(64.24)
$${{\partial X_{\hat \iota j} \left( t \right)} \over {\partial t}} = \left( {1 - b_{\hat \iota } } \right)\left[ {F_{\hat \iota } \left( t \right)X_{\hat \iota j} \left( t \right) + K_{\hat \iota } \left( t \right)\left[ {\bar z_{\hat \iota j} \left( t \right) - H_{\hat \iota } \left( t \right)X_{\hat \iota j} \left( t \right)} \right]} \right]\forall \hat \iota,j,t$$
(64.25)
$${{\partial \sum\nolimits_{\hat \iota j} {\left( t \right)} } \over {\partial t}} = \left( {1 - b_{\hat \iota } } \right)[F_{\hat \iota } \left( t \right)\sum\nolimits_{\hat \iota j} {\left( t \right) + \sum\nolimits_{\hat \iota j} {\left( T \right)F_{\hat \iota } ^T \left( t \right) + \bar Q_{\hat \iota } \left( t \right) - K_{\hat \iota } \left( t \right)R_{\hat \iota } \left( t \right)K_{\hat \iota } ^T \left( t \right)\forall \hat \iota,j,t} } $$
(64.26)
$$K_{\hat \iota } \left( t \right) = \sum\nolimits_{\hat \iota j} {\left( t \right)H_{\hat \iota } ^T \left( t \right)R_{\hat \iota } ^{ - 1} \left( t \right)\forall \hat \iota,j,t} $$
(64.27)
$${\mathcal G}\left( \Lambda _{\hat \iota j} \left( t \right),\hat \Lambda _{h\ell u,u + 1} \right) - b_{\hat \iota } \bar {\mathcal M} \le {{\rm{1 - }}\bar \phi _{\hat \iota jh\ell u,u + 1} \left( t \right)} {\mathcal M}\forall \, \hat \iota,j,h,\ell,u,t$$
(64.28)
$$ - {\mathcal G}\left( \Lambda _{\hat \iota j} \left( t \right),\hat \Lambda _{h\ell u,u + 1} \right) - b_{\hat \iota } \bar {\mathcal M} < \left( {{\rm{1 - }}\bar \phi _{\hat \iota jh\ell u,u + 1} \left( t \right)} \right){\mathcal M}\forall \hat \iota,j,h,\ell,u,t$$
(64.29)
$$\bar \phi _{\hat \iota h\ell } \left( t \right) = \sum\limits_{u = 1}^4 {\bar \phi _{\hat \iota jh\ell u,u + 1} \left( t \right)\forall \hat \iota,j,h,\ell,t} $$
(64.30)
$$\beta _{\hat \iota jh\ell } \left( t \right) - b_\iota \bar {\cal M} \le {\rm{4}} - \bar \phi _{\hat \iota jh\ell } \left( t \right)\forall \hat \iota,j,h,\ell,t$$
(64.31)
$$\beta _{\hat \iota jh\ell } \left( t \right){\cal M} + b_{\hat \iota } \bar {\cal M} \ge {\rm{4}} - \bar \phi _{\hat \iota jh\ell } \left( t \right)\forall \hat \iota,j,h,\ell,t$$
(64.32)
$$\bar \beta _{\hat \iota jh} \left( t \right) = \sum\limits_{\ell = 1}^5 {\beta _{\hat \iota jh\ell } \left( t \right)\forall \hat \iota,j,h,t} $$
(64.33)
$${\rm{\bar \psi }}_{\hat \iota jh} \left( t \right) - b_{\hat \iota } \bar {\cal M} \le \beta _{\hat ijh\ell } \left( t \right)\forall \hat \iota,j,h,t$$
(64.34)
$$1 - {\rm{\bar \psi }}_{\hat \iota jh} \left( t \right) - b_{\hat \iota } \bar {\cal M} \le {\rm{5}} - \bar \beta _{\hat \iota jh} \left( t \right)\forall \hat \iota,j,h,t$$
(64.35)
$${\rm{\bar \psi }}_{\hat \iota j} \left( t \right) = \sum\limits_{h = 1}^{\cal H} {{\rm{\bar \psi }}_{\hat \iota jh} \left( t \right)\forall \hat \iota,j,t} $$
(64.36)
$${\rm{\bar \psi }}_{\hat \iota j} \left( t \right) = b_{\hat \iota } \bar {\cal M} \le {\rm{\bar \psi }}_{\hat \iota jh} \left( t \right)\forall \hat \iota,j,t$$
(64.37)
$$1 - {\rm{\psi }}_{\hat \iota j} \left( t \right) - b_{\hat \iota } \bar {\cal M} \le {\cal H} - {\rm{\hat \psi }}_{\hat \iota j} \left( t \right)\forall \hat \iota,j,t$$
(64.38)
$$P_{\hat \iota } \left( t \right) \in \mathbb{R}^3 \forall \,\hat \iota,t$$
(64.39)
$${\mathcal S}_{\hat \iota } \left( t \right) \in {\mathbb{R}_+} \forall \,\hat \iota,t$$
(64.40)
$${\rm{\theta }}_{\hat \iota } \left( t \right) \in \left[ { - \pi,\pi } \right]\forall \hat \iota $$
(64.41)
$${\rm{\bar \phi }}_{\hat \iota jh\ell } \left( t \right),{\rm{\hat \psi }}_{\hat \iota } \left( {\mathop Y\limits^ \to,t} \right)\bar \beta _{\hat \iota h} \left( {\mathop Y\limits^ \to,t} \right) \in {\mathbb{Z}_+} \forall \, \hat \iota, \mathop Y\limits^ \to,h,\ell,t$$
(64.42)
$${\rm{\bar \phi }}_{\hat \iota jh\ell u,u + 1} \left( t \right),\bar \beta _{\hat \iota j} \left( \left( {\mathop Y\limits^ \to ,t} \right) \right) \in {\mathbb{Z}_+} \forall \hat \iota,j,h,\ell,t$$
(64.43)
$${\rm{\bar \phi }}_{\hat \iota h\ell u,u + 1} \left( {\mathop Y\limits^ \to,t} \right),{\rm{\psi }}_{\hat \iota } \left( {\mathop Y\limits^ \to,t} \right),{\rm{\psi }}_{\rm{o}} \left( {\mathop Y\limits^ \to,t} \right),\beta _{\hat \iota h\ell } \left( {\mathop Y\limits^ \to,t} \right) \in \{ 0,1\} \forall \, \hat \iota, \mathop Y\limits^ \to,h,\ell,u,t$$
(64.44)
$${\rm{\bar \phi }}_{\hat \iota h\ell u,u + 1} \left( t \right),{\rm{\psi }}_{\hat \iota j} \left( t \right),\beta _{\hat \iota h\ell } \left( t \right),{\rm{\bar \psi }}_{\hat \iota jh} \left( t \right) \in \{ 0,.1\} \forall \hat \iota,h,\ell,u,t$$
(64.45)
$$\mu _{\hat \iota hl} \left( t \right) \in \{ 0,1\} \forall \hat \iota,j,h,\ell,t$$
(64.46)
$$b_{\hat \iota } \in \{ 0,1\} \forall \hat \iota $$
(64.47)

2.5 Interpretation of Constraints

Constraints (64.1) prescribe initial positions for each of the UAVs in (i) ;

Constraints (64.2) and (64.3) define the motion of UAV î, as a function of the speed and heading of the UAV;

Constraints (64.4) restrict the instantaneous change in heading of UAV \(\hat \iota \) to be less than \(\Omega _{\hat \iota } \) (modeling the UAVs as Dubin’s vehicles);

Constraints (64.5) define minimum and maximum speed restrictions UAV ;

Constraints (64.6) enforce no two UAVs being closer than \({\rm{\varepsilon }}_{\rm{1}} ^{\min } \);

Constraints (64.7) and (64.8) prescribe that no UAV trajectory can intersect with the boundary of any building;

Constraints (64.9)–(64.11) determine the updated search uncertainty map for UAV i at time t;

Constraints (64.12)–(64.22) are only enforced if UAV \(\hat \iota \) is assigned to a search task over the planning horizon [t c , t c + δ t ]:

Constraints (64.12) and (64.13) force \(\bar \phi _{\mathord{\buildrel{\lower3pt\hbox{$\scriptscriptstyle\smile$}}\over \iota } h\ell u,u + 1} \left( {\mathop Y\limits^ \to ,t} \right)\) to be 1 when line segment \(\Lambda _{\hat \iota } \left( {\mathop Y\limits^ \to ,t} \right)\) is oriented counterclockwise with respect to the line segment \(\hat \Lambda _{h\ell u,u + 1} \) at time t, and to be 0 otherwise;

Constraints (64.14) count the number of line segments representing the ℓ-th face of building h that line segment \(\Lambda _{\hat \iota } \left( {\mathop Y\limits^ \to ,t} \right) \) is oriented counterclockwise with respect to, at time t;

Constraints (64.15) and (64.16) force \(\beta _{\hat \iota h\ell } \left( {\mathop Y\limits^ \to ,t} \right) \) to be 1 when line segment \(\Lambda _{\hat \iota } \left( {\mathop Y\limits^ \to ,t} \right) \) does not intersect the ℓ-th face of building h, at time t, and to be 0 otherwise;

Constraints (64.17) count the number of faces of building h that do not inhibit line of sight from UAV to position \( \mathop Y\limits^ \to \), at time t;

Constraints (64.18) and (64.19) force \({\rm{\bar \psi }}_{\hat \iota h} \left( {\mathop Y\limits^ \to ,t} \right)\) to be 1 when there is line of sight from UAV to position \( \mathop Y\limits^ \to \), at time t, with respect to building h, and to be 0 otherwise;

Constraints (64.20) count the number of buildings that do not inhibit line of sight from UAV to position \( \mathop Y\limits^ \to \), at time t;

Constraints (64.21) and (64.22) force \({\rm{\bar \psi }}_{\hat \iota } \left( t \right)\) to be 1 when UAV has line of sight to position \( \mathop Y\limits^ \to \), at time t, and to be 0 otherwise;

Constraints (64.23) and (64.24) determine the fused covariance and state for target j at time t, from UAV i ’s perspective, based on those neighbors of UAV i that have line of sight to target j;

Constraints (64.25)-(64.27) are the continuous time Kalman filter (Kalman-Bucy filter) equations for the state of target j, as seen from UAV î, where \(\bar z_{\hat \iota j} \left( t \right)\) represents the measurement of target j by UAV î, at time t (N.B.: a detailed explanation of the Kalman filter equations can be found in Blackman and Popoli (1999), Gelb (1974), and Maybeck (1994));

Constraints (64.28)–(64.38) are only enforced if UAV is assigned to a track task over the planning horizon [t c , t c + δ t ]:

Constraints (64.28) and (64.29) force \(\bar \phi _{\hat \iota jh\ell u,u + 1} \left( t \right)\) to be 1 when line segment \(\Lambda _{\hat \iota j} \left( t \right)\) is oriented counterclockwise with respect to the line segment \(\hat \Lambda _{h\ell u,u + 1} \), at time t, and to be 0 otherwise;

Constraints (64.30) count the number of line segments representing the ℓ-th face of building h that line segment \(\Lambda _{\hat \iota j} \left( t \right)\) is oriented counterclockwise with respect to, at time t;

Constraints (64.31) and (64.32) force \(\beta _{\hat \iota jh\ell } \left( t \right)\) to be 1 when line segment \(\Lambda _{\hat \iota j} \left( t \right)\) does not intersect the ℓ-th face of building h, at time t, and to be 0 otherwise;

Constraints (64.33) count the number of faces of building h that do not inhibit line of sight from UAV to target j, at time t;

Constraints (64.34) and (64.35) force \({\rm{\bar \psi }}_{\hat \iota jh} \left( t \right)\) to be 1 when there is line of sight from UAV to target j, at time t, with respect to building h, and to be 0 otherwise;

Constraints (64.36) count the number of buildings that do not inhibit line of sight from UAV to target j, at time t ;

Constraints (64.37) and (64.38) force \({\rm{\psi }}_{\hat \iota j} \left( t \right)\) to be 1 when UAV has line of sight to target j, at time t, and to be 0 otherwise;

Constraints (64.23)–(64.27) prescribe domain restrictions on all of the decision variables.

2.6 Objective Function (for UAV i )

The objective function, F, as defined in Eq. (64.48), minimizes the sum of two components. The first component computes the expectant volume of UAV i ’s search uncertainty map over the planning horizon, [t c , t c + δ t ]. The second component computes the weighted sum of the determinants of the fused covariances for the targets that are known to UAV i, over the planning horizon.

$$F = \min \left[ {a_s \int_{t_c }^{t_c + \Delta _t } {\int\limits_{\mathbb{R}{^2 }} {\Gamma _i \left( {{\mathcal Y}{\rm{,}}\tau } \right)d\tau + a_t \int_{t_c }^{t_c + \Delta _t } {\sum\limits_{j = 1}^{\mathcal J} {\left[ {\gamma \left( {X_j ^i \left( \tau \right)} \right)\left| {\sum\nolimits_j^i {\left( \tau \right)} } \right.} \right]} d\tau } } } } \right]$$
(64.48)

2.7 Discussion on Complexity

It is easy to see that our problem of determining the flight plan for a set of autonomous UAVs is a generalization of the standard vehicle routing problem (VRP). While there are many variants to the standard VRP, the general form considers m vehicles, starting at a depot, tasked with delivering goods or services to a set of n customers. Each customer has a certain required demand, and each vehicle has a capacity. In addition, each vehicle must start and end their route at the depot (a tour).

A solution to this problem is a set of tours for which each customer is visited only once while respecting capacity and demand constraints. The objective can be to minimize the total distance traveled by all vehicles, to minimize the maximum distance traveled by any one vehicle, or to minimize the number of vehicles required to service the customers. The VRP is known to be NP-hard (Garey and Johnson 1979), and thus our problem is NP-hard as well.

3 Heuristic Algorithm

There are many papers dealing with UAV routing (Shetty et al. 2008; Ma and Miller 2005; Schouwenaars et al. 2001; Sinha et al. 2005) that formulate the problem statement as a linear or mixed-integer linear program (or a formulation that can be linearized in the standard way). This allows the authors to use various proven heuristics to find good routes for the UAVs. However, for UAV routing, incorporating more realistic constraints on the movement of the UAVs necessitates the introduction of nonlinear constraints that cannot be linearized without approximation of the nonlinear constraints. Hence, the need to utilize more generalized heuristics (or meta-heuristics) in the search for near-optimal solutions.

To efficiently solve the optimization problem presented in Sects. 64.2.2–64.2.5, a hybrid heuristic was developed, combining Greedy Randomized Adaptive Search Procedures (GRASP) and Simulated Annealing (SA). GRASP is a multi-start local search procedure, where each iteration consists of two phases, a construction phase and a local search phase (Feo and Resende 1989, 1995; Festa and Resende 2002). In the construction phase, interactions between greediness and randomization generate a diverse set of quality solutions. The local search phase improves upon the solutions found in the construction phase. In this GRASP implementation, only the construction portion is utilized. Simulated Annealing is a heuristic to find good- quality solutions to optimization problems by approximating the cooling process of metals (Kirkpatrick et al. 1983). At each step, a current solution is perturbed. If the perturbation results in a better solution, then the current solution is replaced. If the perturbed solution is worse than the current solution, it still might replace the current solution; replacement will occur with a probability based on the distance between the current and perturbed solution values and the current temperature in the annealing process. As the heuristic progresses, the temperature is lowered, making it more and more unlikely to replace the current solution with a worse perturbed solution.

For our hybrid GRASP-SA heuristic, the GRASP heuristic determines the task assignment for the UAVs, interacting directly with a Simulated Annealing heuristic which determines the routes that the UAVs should fly to accomplish their tasks. The best solution over all of the GRASP multi-start iterations is retained as the final solution. It is important to note that a solution, for a given UAV, is the tasking and flight path for the UAV, as well as the neighbors of the UAV, over the planning horizon. Figure 64.2 provides pseudocode for the GRASP-SA hybrid heuristic, with the function Ξ representing the SA heuristic function.

Fig. 64.2
figure 2

Pseudo-code for the hybrid GRASP-SA heuristic

Full size image

4 Experimental Results

4.1 Test Environment

The experiments to follow were carried out on a Hewlett-Packard with an Intel(R) Core(TM) 2 Duo E8400 CPU at 3.00 GHz and 3.71GB of RAM running Microsoft Windows 7 Enterprise (64-bit). The implementation of the GRASP and Simulated Annealing heuristics as written in the C++ programming language and compiled with Microsoft Visual C++ 2008. The algorithm used for random-number generation is an implementation of the Mersenne Twister algorithm described in Matsumoto and Nishimura (1998).

4.2 Experiments

While no specific UAV was modeled, the experiments utilized characteristics of the Raven UAV. The simulations in this study model the UAV sensors as omnidirectional radars measuring range and bearing to the targets. Conversions of the measurement and measurement uncertainty from spherical to cartesian coordinates were done utilizing the standard transformations (Lerro and Bar-Shalom 1993). Table 64.1 displays the parameter values used during the simulation. Thirty-two buildings were modeled in the simulation, each with a height of 100 m, while the altitude of the 4 UAVs was fixed to 10 m. Eight moving ground targets were simulated, with minimum and maximum speeds of 0 and 30 miles h−1, respectively. Three different experiments were performed, varying the communication range of the UAVs. In the “no-comms” case, each UAV had an effective communication radius of 0 m, making them truly independent of all the other UAVs. For the “half-comms” case, each UAVs communication radius was set to 979.5 m, half the length of the simulated region of interest. And in the “unlimited comms” case, each UAV had a communication radius larger than the simulated region of interest, meaning as long as there were no obstructions (e.g., buildings) between two UAVs, they could effectively communicate.

Fig. 64.3
figure 3

Simulation results for unlimited communications case, at time-step 44. UAVs 1, 3, and 4 are engaged in the search task, while UAV 2 is tracking the target within its sensor coverage (black circle around UAV)

Full size image
Table 64.1 Parameter settings
Full size table

To highlight a small sample of the simulation, Figs. 64.3–64.5 show the results for time steps 44–46 of the unlimited communications case. This is a top-down view, with the yellow rectangles representing the buildings, the small white rectangles representing the targets, the UAVs numbered, and the planned routes of the UAVs emanating from each UAV. UAVs engaged in a search task have routes colored red, while those engaged in a tracking task have routes colored green. The background represents the search uncertainty map, with blue corresponding to a low level of uncertainty and red a high level of uncertainty. The sensor coverage for each UAV is represented by a black circle about each UAV. At time-step 44, UAVs 1, 3, and 4 are engaged in a search task, while UAV 2 is engaged in tracking the target within its sensor coverage. At this time-step, UAV 1 and 2 are close enough together to share information, so UAV 1 knows about the target UAV 2 is currently tracking. At time-step 45, UAVs 3 and 4 continue searching, while UAV 1 switches to a tracking task, to help track the target UAV 2 has been tracking. Time-step 46 sees UAV 1 with a new trajectory, to better keep the target it is tracking within its sensor coverage. UAV 2 is still engaged in tracking, and UAVs 3 and 4 are still engaged in a search task. Note also that UAV 4 has its route planned to reduce the uncertainty shown in the bottom left region of the scenario.

Fig. 64.4
figure 4

Simulation results for unlimited communications case, at time-step 45. UAVs 3 and 4 are engaged in the search task, while UAVs 1 and 2 are tracking the target within their sensor coverage

Full size image
Fig. 64.5
figure 5

Simulation results for unlimited communications case, at time-step 46. UAVs 3 and 4 are engaged in the search task, while UAV 1 and 2 are continuing to track the target within its sensor coverage. In addition, UAV 1 has changed its trajectory to keep the target within its coverage

Full size image

One method to measure how the UAV communication range affects the searching algorithm is to observe the minimum search uncertainty value across all UAVs at each location for the simulated region of interest. Figure 64.6 displays the resultant mean minimum search uncertainty map value of the UAVs for the simulated region of interest, at each time-step. The mean search plots tend to show spike and dips. What happens in these cases is that a UAV’s search uncertainty map has a group of values that become large in one particular area of the search region. When enough of these values become large, and as long as the UAV is not tasked to track a target, the UAV will eventually plan a route that leads it to search that area of interest. This sudden decrease in many search uncertainly values drives the mean sharply downward. The zero-comms case does not have as many sharp spikes because it has fewer opportunities to switch to tracking (since those UAVs cannot share their state with each other). However, they must conduct their search on their own – this leads to the general upward trend in the zero-comms case in the mean search plot, since they cannot leverage the search information of their neighbors.

Fig. 64.6
figure 6

The mean minimum search uncertainty map value over all UAVs at each time-step, for the three UAV communication cases

Full size image

Figure 64.7 displays the number of UAVs engaged in tracking each target, at each time-step. Of note here is that the mean weighted percentage of targets tracked increases from 48.854 when the communications radius is 0 m to 70.208 when the communication radius is 979.5 m and finally to 80 when the communication radius is infinite. Figure 64.8 displays the mean Mahalanobis distance (Eq. 64.49), between the fused and truthful positions, for each target, for each time-step. As can be seen here, the mean Mahalanobis distance decreases as the communication radius increases. This is because as communication among the UAVs increases, more information on the target kinematics can be shared among the UAVs (and hence fused into each UAVs target map):

$$M_d \left( {x,\,\bar x,\sum,\,\bar \sum } \right) = \left( {x - \bar x} \right)\left( {\sum + \bar \sum } \right)^{ - 1} \left( {x - \bar x} \right)^T $$
(64.49)
Fig. 64.7
figure 7

Number of UAVs engaged in tracking each target, at each time-step. The red curve denotes the communications radius of 0 m, the blue curve denotes the communications radius of 979.5 m, and the black curve denotes the infinite communications radius

Full size image
Fig. 64.8
figure 8

Mean Mahalanobis distance (between the fused position and the truthful position) for each target, for each time-step. The red curve denotes the communications radius of 0 m, the blue curve denotes the communications radius of 979.5 m, and the black curve denotes the infinite communications radius

Full size image

As can be seen in the result plots, a push-and-pull effect is occurring. During the search phase, the UAVs want to fly to areas of high uncertainty (and hence reduce the uncertainty there), but as the UAVs detect targets in these high uncertainty regions, they switch their tasking to tracking (because the initial uncertainty of a target contributes more to the objective function than does the search uncertainty). This can be partially alleviated by modifying the decision variable \(b_{\hat \iota } \) to include a time dimension, \(b_{\hat \iota } \)(t). This would have the effect of allowing each UAV to switch between tasks over the planning horizon, rather than forcing each UAV to make a decision on a task for the whole planning horizon. This can also be achieved by artificially reducing the size of the planning horizon. Both approaches will increase the complexity and computational throughput and are out of the current scope.

5 Conclusions and Future Research Areas

This chapter considered dynamically updating the tasking and flight paths for UAVs in an urban domain. The UAVs were assumed to be Dubins-like vehicles (i.e., point masses with kinematic constraints) with limited communication capabilities. This resulted in a decentralized approach where each UAV dynamically updated flight plans for itself and its neighbors. As it was an urban domain, the UAVs needed to incorporate obstacle avoidance constraints into the flight plan generation as well as taking into account anticipated future line of sight obstructions to the targets and search region. A dynamic feedback control loop was implemented for each UAV, and a rigorous mathematical formulation was presented for the coupled task assignment/flight path optimization problem each UAV had to solve at each time-step.

This approach was successfully applied to a simulated scenario utilizing a hybrid GRASP-SA heuristic. The influence of communication radius among the UAVs on the resultant objective function value was studied. While it is in general expected that the larger the communication radius, the better the performance of the UAVs, as seen from the results, many other factors also influence performance.

It is expected that UAV utilization will continue to increase in scope, both for military and nonmilitary operations. Hence, there is the need to continue to advance the state of the art in autonomous UAV research. Future research directions include applying our general approach to UAVs with heterogeneous sensors (e.g., directional radars, passive sensors) as well as to heterogeneous vehicles, from different domains (e.g., UAVs and UGVs working synergistically). A comparison of the efficiency of our approach, from a computational and functional perspective, to other centralized and decentralized approaches is currently underway. The end goal is geared toward testing these algorithms on real UAVs.