A priori and on-line route optimization for unmanned underwater vehicles

The U.S. military considers Unmanned Underwater Vehicles (UUVs) a critical component of the future for two primary reasons - they are effective force multipliers and a significant risk-reducing agent. As the military's technology improves and UUVs become a reliable mission asset, the vehicle's ability to make intelligent decisions will be crucial to future operations. The thesis develops various algorithms to solve the UUV Mission-Planning Problem (UUVMPP), where the UUV must choose which tasks to perform in which sequence in a stochastic mission environment. The objective is to find the most profitable way to execute tasks with restrictions of total mission time, energy, time-restricted areas, and weather conditions. Since the UUV accumulates navigation error over time while maneuvering underwater, the UUV must occasionally halt operations to re-orient itself via a navigation fix. While a navigation fix takes time and increases the likelihood of exposing the vehicle's position to potential adversaries, a reduction in navigation error allows the UUV to perform tasks and navigate with a greater amount of certainty. The algorithms presented in this thesis successfully incorporate navigation fixes into the mission-planning process. The thesis considers Mixed-Integer Programming, Exact Dynamic Programming, and an Approximate Dynamic Programming technique known as Rollout to determine the optimal a priori route that meets operational constraints with a specified probability. The thesis then shows how these formulations can solve and re-solve the UUVMPP on-line. In particular, the Rollout Algorithm finds task route solutions on average 96% of the optimal solution a priori and 98% of the optimal solution on-line compared to exact algorithms; with a significant reduction in computation run time, the Rollout Algorithm permits the solving of increasingly complex mission scenarios.

Department dc:contributor.department

Massachusetts Institute of Technology. Operations Research Center.

Grantor dc:publisher

Massachusetts Institute of Technology

Year dc:date.issued

2012

Author dc:creator

• Crimmel, Brian A

Advisor dc:contributor.advisor

• Eric D. Nelson and Patrick Jaillet.

• Operations Research Center.

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/72848

OAI identifier oai:identifier

oai:dspace.mit.edu:1721.1/72848