Planning Observations by Unmanned Surface Vessels

June 1, 2008

Air Force Research Laboratory

Three algorithms, and software that implements the algorithms, have been conceived and analyzed as means of effecting automated planning of scientific observations by a fleet of unmanned surface vessels (USVs) equipped with sensors and operating over a large and possibly changing ocean area. Typical observations envisioned in the development of these algorithms include water-temperature measurements ahead of the path of a hurricane (see figure) and fluorometer readings to track harmful algal blooms.

USVs are autonomous robotic vessels that, as a result of recent technological advances, are increasingly regarded as preferred means of performing missions too difficult, dangerous, and/or tedious for humans. Moreover, with respect to oceanic and atmospheric observations, in comparison with manned surface vessels, USVs can complete missions with better performance at lower cost.

Planning of observations by the USVs in a fleet must include planning of the travels of the USVs to targets chosen for their scientific value. A planning algorithm is required to coordinate the operations of all the USVs so as to allocate the fleet efficiently, taking account capabilities and limitations of the USVs as well as the scientific value of each target. In a typical scenario, the algorithm should be able to plan for many USVs over possibly thousands of targets. It should also be capable of creating plans very quickly to enable dynamic re-planning to react to changes in the environment or changes in required observations.

The three algorithms of the present development can be characterized as follows:

• A greedy construction heuristic that takes the least computation time but produces suboptimal plans;
• An exact mixed-integer algorithm that produces optimal plans but takes an amount of computation time that increases exponentially with the number of targets and, hence, is impractical for use with more than a few targets; and
• A three-phase algorithm approximate algorithm (3PAA) that generates suboptimal plans better than those produced by the greedy construction heuristic and takes an amount of computation more than that of the greedy construction heuristic but less than that of the exact algorithm.

The phases of the 3PAA are the following:

1. A construction phase involves the use of a modified version of the greedy construction heuristic in which the ratio between the scientific value and the cost for each target is considered across the entire fleet in choosing which USV to assign to which target.
2. An improvement phase comprises three sub-phases, each involving the use of a different iterative local-search algorithm for a set maximum number of iterations.
3. In an insertion phase, an attempt is made to modify the USV routes selected in the first two phases to add targets that would otherwise remain unvisited. In this phase, targets not previously selected to be visited are, variously, selected according to scientific-value- to-cost ratios or rejected if visiting them would violate constraints.

Several refinements of the 3PAA have been suggested for future development efforts. These include modifications to increase robustness of plans, to account for phenomena (e.g., tidal currents) not considered in the initial development, and to enable coordination between successive planning periods. It has also been proposed to extend the present USV-observation- planning methodology to other applications that involve similar planning problems, including use of fleets of robotic aircraft to monitor wildfires and scheduling fleets of trucks and cargo aircraft.

This work was done by John V. Miller of the Sloan School of Management for the Air Force Research Laboratory.

AFRL-0092

---

This Brief includes a Technical Support Package (TSP).

Planning Observations by Unmanned Surface Vessels

(reference AFRL-0092) is currently available for download from the TSP library.

LOGIN TO DOWNLOAD

Don't have an account? Sign up here.

---