Planning Observations by Unmanned Surface Vessels
Operations of multiple autonomous agents are scheduled and coordinated automatically.
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:
- 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.
- 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.
- 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.
Don't have an account? Sign up here.
Top Stories
INSIDERManned Systems
Turkey's KAAN Combat Aircraft Completes First Flight - Mobility Engineering...
INSIDERMaterials
FAA Expands Boeing 737 Investigation to Manufacturing and Production Lines -...
INSIDERImaging
New Video Card Enables Supersonic Vision System for NASA's X-59 Demonstrator -...
INSIDERManned Systems
Stratolaunch Approaches Hypersonic Speed in First Powered TA-1 Test Flight -...
INSIDERUnmanned Systems
Army Ends Future Attack and Reconnaissance Helicopter Development Program -...
ArticlesEnergy
Can Solid-State Batteries Commercialize by 2030? - Mobility Engineering...
Webcasts
AR/AI
From Data to Decision: How AI Enhances Warfighter Readiness
Energy
April Battery & Electrification Summit
Manufacturing & Prototyping
Tech Update: 3D Printing for Transportation in 2024
Test & Measurement
Building an Automotive EMC Test Plan
Manufacturing & Prototyping
The Moon and Beyond from a Thermal Perspective
Software
Mastering Software Complexity in Automotive: Is Release Possible...