Planning and scheduling of concurrent high-level activities for UUV mission operations

This thesis develops a mission planning and scheduling algorithm that enables a single Unmanned Undersea Vehicle (UUV) to concurrently perform high level activities, while managing various resources in a dynamic ocean environment. Such activities may include wide area surveillance of a specified region and focused inspection tasks. Concurrent execution of activities allows a UUV to perform portions of different activities that share overlapping regions consecutively to increase vehicle productivity. Resources considered in this algorithm range from concrete quantities, such as the remaining battery energy, to variables representing operational restrictions, such as the maximum allowable navigation uncertainty. The first step in the development defines a parameterization that describes each high level activity in terms of smaller atomic tasks. In order to determine a sequence/path of tasks for the UUV to perform, a Prize Winning Salesman Problem with Replenishment Arcs (PW-RATSP) formulation transforms the set of atomic tasks into a set of nodes representing sequences of non-resource-replenishment tasks and a set of arcs that represent sequences of resource-replenishment tasks. The algorithm then expresses and solves the PWRATSP formulation as a mixed integer linear program (MILP). Finally, the algorithm employs a receding horizon approach to improve MILP computational performance and account for unexpected events and changes to the environment. Simulation results for test cases combining surveillance and inspection activities, and multiple resource replenishment activities show that the PW-RATSP UUV mission planning algorithm provides the ability to manage concurrent activities, perform temporal reasoning, and account for a mix of replenishable and non-replenishable vehicle resources.

Department dc:contributor.department

Massachusetts Institute of Technology. Dept. of Aeronautics and Astronautics.

Grantor dc:publisher

Massachusetts Institute of Technology

Year dc:date.issued

2007

Author dc:creator

• Chang, Larry, S. M. Massachusetts Institute of Technology

Advisor dc:contributor.advisor

• Lance A. Page and Emilio Frazzoli.

• Aeronautics and Astronautics.

Statement dc:rights

• M.I.T. theses are protected by copyright. They may be viewed from this source for any purpose, but reproduction or distribution in any format is prohibited without written permission. See provided URL for inquiries about permission.

Licence dc:rights.uri

• http://dspace.mit.edu/handle/1721.1/7582

Language dc:language.iso

eng

Handle dc:identifier.uri

http://hdl.handle.net/1721.1/46569

OAI identifier oai:identifier

oai:dspace.mit.edu:1721.1/46569