16-711 Project Report
Michael Dille
5/11/2010

Overview

For this project, I sought to extend ongoing work I have been performing in UAV target tracking by adding intelligent control that decides how a UAV should move to better accomplish such tasks. I investigate, implement, and compare several methods for doing this.

Background

The grand vision of my current research efforts is cooperation among heterogeneous air (UAVs) and ground (UGVs) robots to search, track, geolocate (accurately determine the world coordinates of), and pursue/capture ground targets. To date, I have concentrated mostly on the UAV side, initially with a study of several methods for visual target tracking and more recently by considering how to filter target observations (a point in image coordinates corresponding to a view of a ground target) by taking into account uncertainty in the UAV's state to accurately estimate the target's location.

Example automatic visual target tracking sequence. Following initial selection by an operator, the target is tracked through succeeding video frames, providing observations in the form of the target's location in image coordinates, which may then be projected to the ground to get an observation in world coordinates.

The other problem I wish to solve is how to efficiently search for one or more targets believed to be located in an area but which are not currently in view. Here we assume that an operator (or detection algorithm) is viewing the live video stream and will detect and designate visible targets successfully with some fixed probability. Thus, the goal is to cover an area quickly, covering areas of high prior target probability as quickly as possible, while ensuring sufficient time over any given patch to provide reasonable likelihood of detecting targets that may be present. To date, fairly straightforward controllers have been implemented that generate open-loop trajectories that efficiently cover an area having uniform prior target probability.

Example execution of coverage controller. An area is initially designated in which targets may lie anywhere (uninformed prior), and a built-in orbit controller (available in most UAV autopilots) is instructed to follow a precessing trajectory of orbit points that in the end produces a uniform coverage pattern.

Method

My approach to accomplishing the dual tasks of accurate target geolocation and efficient search is to pose them as trajectory optimization problems. That is, given a finite amount of time, we seek the trajectory that will provide a series of anticipated observations that maximize the expected accuracy of a target position filter (for accurate geolocation) or that will maximize the probability of target detection (for area search). For simplicity, I am assuming that a UAV autopilot is present that maintains stable flight and which accepts a desired heading angle at each control tick, so that the UAV is steered like a Dubins car, and hence a trajectory is a sequence of steering commands.

Accurate Geolocation

We assume that we have recently observed a target, have a reasonable idea of where it lies, and are running a filter that is continuously accepting any new observations of the target and is providing an estimate of the target's location. In some recent work, I have begun to explore more exotic representations of observation uncertainty (non-Gaussian distributions that more accurately encode actual sensor uncertainty relying on minimal or no linearization), but for now we assume that observations are in the form of a point on the ground and surrounding Gaussian uncertainty ellipse (generated by computing the linearized Jacobian of the target location on the ground with respect to various sensor values [eg UAV position, orientation, camera parameters, etc.] and apply this to an estimate of the sensor value covariance matrix). Prediction and observation updates are assumed to be made using typical EKF equations. Thus, given the current UAV and filter state, we need to decide how to move so that the observations we receive have the most impact on the filter.

I compare several methods for achieving this:

• (Baseline) Direct or ad-hoc observation inducement. Intuitively, this is all about observability: observing the target frequently, from varied locations. For a side-mounted camera, we can accomplish this directly by initiating an orbit with the target at its center. For other camera mountings (eg forward or downward-facing), an ad-hoc controller that applies heuristics to keep the target in view (typically resulting in figure-eight, cloverleaf, or lighthouse flight patterns) may be applied.
• Total uncertainty minimization. For a Gaussian filter representing target position uncertainty as a covariance matrix, the trace of this matrix represents the "total uncertainty" in the target's state. For a candidate trajectory, we may thus run the filter forward without actual observations, at each step predicting the target's new location using the filter's motion model, applying estimated process noise in that model to inflate the covariance, and then (by assuming the target actually lies at the location representing our current best estimate) update the covariance again as though an observation had arrived. For an EKF, these steps may look like the following: Applying the metric of trace of the coveriance matrix, we may then choose for instance the trajectory that minimizes the average trace over the trajectory (if for instance we are performing operations that wish to have as accurate an answer as possible at all times) or simply the terminal trace (if we simply want the best answer possible by the end of the trajectory).
• Filter observability maximization. Rather than explicitly minimizing expected reduction in uncertainty, we can consider maximizing the usefulness of the observations to the filter, based on the notions that we want to avoid filter divergence and that "useful" observations are likely to reduce state uncertainty. The metric for this is typically derived by formulating the filter as an information filter and maximizing the expected incremental "information" to be collected, denoted Y:
• Information gain maximization. Going beyond maximizing observability, we may wish to ensure that the incremental information collected is in fact new information, typically referred to as an information gain. This is typically defined in terms of entropy (H), a measure of uncertainty: where for a Gaussian EKF:
• Observation probability maximization. Given a probability distribution of target location on the ground (from the filter), a probability that a given point on the ground is visible in the current camera view (from the distribution of UAV state uncertainty), and a probability of target detection at a given pixel (modeling a detector or tracker's tendancy to do better near the center of a frame), we can compute given a current UAV and filter state the probability of observing the target. This may itself be used as a metric, and we may either want to maximize the average probability of target detection over a trajectory (maximizing observation frequency), the probability of observing the target at least once over the course of the trajectory (ensuring that we are as likely as possible to detect the target while executing the trajectory), or the terminal probability of observing the target (eg, to choose trajectories that move us to an area of high target probability).

The above information-theoretic metrics are derived from an ongoing literature search, from which for instance

D. Casbeer, P. Zhan and A.L. Swindlehurst, "A Non-Search Optimal Control Solution for a Team of MUAVs in a Reconnaissance Mission," In Proc. 2006 IEEE ICASSP, Toulouse,France, May, 2006.

is a particularly useful example.

Efficient Search

In this scenario, we assume that we have a map representing the current (initially, the prior) distribution of target location probability, and we wish to search this map as efficiently as possible. Stated more precisely, given a finite time duration, we wish to find the trajectory to execute that will maximize the probability of detecting a target.

To ease implementation, I am assuming the probability map is represented as a discrete cellular map, which may be a grid or an arbitrary collection of polygons (eg, a triangularization map), points outside of which are simply assumed to not be relevant. This allows, for instance, maps constraining targets to road networks to be easily represented.

Observations are assumed to be made using Bayesian updates. A map may either represent a probability distribution on location of a single target (all the cells sum to 1), or alternatively no assumptions can be made on the number of targets and each cell treated as independently having some probability of containing a target (and updated indepdendently).

To accomplish this, I consider the following methods:

• (Baseline) Open-loop coverage trajectories. As a point of comparison, we can apply the open-area coverage orbits described in the background section. In the case of a static target lying in a dense map with uniform prior, we may expect this method to perform quite well, since it explicitly avoids observing areas already seen. However, for moving targets or complex/sparse probability maps, it could perform arbitrarily badly.
• (Greedy) Probability gradient following. Applying similar intuition as for the accurate geolocation case, we want to move so that any probable target locations will lie in the camera's field of view. One obvious way of doing this is to move so that the center of the camera's footprint on the ground moves in the direction of the gradient of the probability map. This is itself a myopic local approach, and it is further complicated by the fact that due to the non-holonomic constraints of a fixed-wing aircraft, it is impossible to move the sensor footprint in an arbitrary direction, requiring the use of heuristics that "best" accomplish this. I have experimented with several such heuristics previously; here I just choose one, without elaborating on its relative merits.
• Observation probability maximization. Using exactly the same principle as for the accurate geolocation task, we can evaluate a candidate trajectory by simulating the UAV moving along this trajectory, updating the map assuming negative observations (under the assumption a positive detection would result in a behavior switch, eg to pursuit/accurate-geolocation), and at each timestep computing a probability of detecting the target given the anticipated UAV position and updated probability map. Here again, we may choose to maximize the average probability of detection over the trajectory, the probability of observing a target at least once, or the terminal probability of observing a target.

Implementation

All experimentation described here took place in a simulation environment of my own design that allows for relatively easy migration of promising-looking ideas from simulation to actual UAVs. The open-loop coverage and heuristic controller existed previously; all other controller implementations were written during the course of this project.

Experimental Results

Accurate Geolocation

First, an EKF with a constant-position/uncertainty-diffusion target process model is run, accumulating observations when they occur. A subset of the above control metrics were each run over 50 trials in which the UAV was placed at random initial locations and headings such that a stationary target lies in the field of view (ie, starting at a point of first detection). Trials lasted for 180s, regardless of the state of the filter or controller. Results were then averaged to populate the following table.

Side-mounted Camera

Forward-looking Camera

Interpretation

Unsurprisingly, when using a side-mounted camera, merely orbiting the best estimate of the target's location did the best job of keeping it in view, and hence a very good job at providing useful observations to the filter. The heuristic I used for locally moving the center of the camera footprint towards the estimated target location simply didn't perform very well, since it often converged to tightly orbiting directly above the target yet never observing it (the target lying just below the field of view). As hoped, planning to minimize filter uncertainty or maximizing probability of observing the target performed reasonably well. In both cases, attempting to optimize for the average case provided better observations overall than just optimizing for the terminal point. Attempting to minimize filter uncertainty performed a bit worse at keeping the target in view (as it does not explicitly attempt to do so and hence does not value a target dangerously close to an image edge below one near the image center). Ironically (probably as a result of this fact), it actually did worse at minimizing filter uncertainty, though it happened to provide answers with lower error.

Essentially similar conclusions may be drawn for the forward-looking camera case. This is trickier since given the UAV's minimum velocity constraint, it is necessary to overfly the target each time. Not unexpectedly, orbiting the target doesn't do much, since this actually aims the camera away from the target. The heuristic performed slightly better than this because it achieves limited success at moving towards the target before again falling into a tight orbit above it. Ironically, the average filter error is actually lowest for the heuristic since it only stopped integrating observations once the estimated mean it tightly orbits coincides closely to the actual target location. Planners did better overally and generated flowery patterns. These are unlike, however, the more commonly known tight flower petal patterns that are typically optimal in such scenarios. This may be due to the relatively small search depth and large inter-action timestep.

Example Videos

For the side-mounted camera case, most strategies resulted (unsurprisingly) in somewhat of an orbit. Examples of two such cases are provided below.

Orbit controller Windows MPEG4 Mac MPEG4	Max avg observability prob planner Windows MPEG4 Mac MPEG4

For the front-mounted camera case, somewhat more bizarre behaviors resulted:

Min avg trace(cov) planner Windows MPEG4 Mac MPEG4

In these examples, the actual location of the UAV and target are shown in green and red, respectively. The actual camera footprint is shown in bold green; the (incorrect) measured footprint the UAV believes it sees is fainter green. The instantaneous observation is denoted by a black dot with surrounding gray 90% confidence ellipse. The orange dot surrounded by a 90% orange confidence ellipse is the filter's best estimate. Note that as these examples show, the filter is in fact slightly inconsistent, owing to the incorrectness of linearization of the projection function with pose and camera uncertainties of the reasonably moderate magnitude chosen here.

Efficient Search

Due to inevitably underestimated implementation complexity, though I finished implementations of efficient search controllers, I was unable to compare their behavior by the end of the project. I will nevertheless continue to work on this given its relevance to my research.

Future Work

I anticipate extending this to include multiple trackers (UAVs) and moving targets (initially constant velocity or wandering). I also intend to add 1-step rules (basically, depth-1 versions of some of the planners) for comparison. Conversely, I wish to explore other, less brute-force, trajectory optimization methods to achieve much larger search depths. I intend to more carefully study the task of efficient search as well as investigating more elaborate uncertainty representations (eg non-Gaussian, non-linearized) and target state constraints (eg position constrained to a road network) for accurate geolocation filtering. Finally, I hope to make this all much more interesting by introducing the notion of occluding scenery that the optimization/planner must take into account, so that the "best" trajectories aren't the boring intuitive ones.