The Surveillance Planning Problem

The central challenge in planning surveillance missions is that there's a need to maintain awareness of a large number of sites but only a single (or a few) UAV(s) to do it with. Since a UAV cannot be everywhere at once, it should move from site to site, observing at each, in whichever order produces the best overall situation awareness for human decision-makers on the ground.

In some cases, the best mission plan will be a repeating patrol pattern that minimizes the total time to complete a circuit and therefore minimizes the time between visits to each site. But not always. For instance, the likelihood of an event that needs to be observed might be much higher at some sites than others. The best plan might involve visiting those sites more often than the others. Similarly, events at some sites might be far more time-critical than at others; again, it may be best to observe these especially often.

Our approach to generating surveillance mission plans is founded on a formal definition of what it means to perform such surveillance tasks optimally. In particular, given that the vehicle can generally observe only a single target at a time and must spend time transiting to and examining each target, it will necessarily not be observing most targets most of the time - i.e. it will be "ignorant" of the state of these targets. We define Expected Cost of Ignorance (ECI) as a function of the likelihood of important events occurring at each target and the cost of delay in observing such events. The goal of surveillance is to minimize this quantity.

Plan generation algorithms

Information on the likelihood and cost of critical events is specified by a human operator using the Mission Planning Interface. This information is passed to a mission planning process in Apex which determines the best way to sequence observations of the targets.

We have explored 2 kinds of algorithms for generating surveillance mission plans and also compared these approaches to human-generated plans. One of the automated approaches is to find the best repeating cycle. In general, there is no requirement to visit each target once per cycle; targets may be visited several times or not at all. The second approach is to find the "best sequence" consisting of n targets (or out to some time horizon).

We expected and found that different planning algorithms have different strengths and weaknesses - i.e. that different algorithms would generate the best plans under different conditions. Our test examined performance of 2 algorithms (one best-cycle and one best-sequence) and a group of human subjects in 243 conditions representing the following 5 independent variables.

1. Number of mission targets
2. Size of mission area
3. Geometric dispersion pattern of targets
4. Variability of target value (part of cost function)
5. Variability of target cost rate

The results, summarized in the table below show which algorithm is best (or whether a human planner should be expected to perform best) in each of the 243 conditions.

Given the predictable difference in performance of different algorithms, getting the best overall surveillance performance from the UAV depends on picking the best algorithm for given MPI-specified mission goals. Our approach couples the planning algorithm selection process to the plan generation process. Whenever a plan is needed, either prior to flight or in flight, the first step is to analyze the mission goals to determine which of the 243 basic mission types the current mission best resembles. After performing this match, Apex selects the planning algorithm identified as best for that mission type, invokes it to generate the plan and then begins executing that plan.

Return to ARP page