Robust multi-UAV planning in dynamic and uncertain environments

Future unmanned aerial vehicles (UAVs) are expected to operate with higher level of autonomy to execute very complex military and civilian applications. New methods in planning and execution are required to coordinate these vehicles in real-time to ensure maximal efficiency of the team activities. These algorithms must be fast to enable rapid replanning in a dynamic environment. The planner must also be robust to uncertainty in the situational awareness. This thesis investigates the impact of information uncertainty and environmental changes to the task assignment and path planning algorithms. Several new techniques are presented that both speed up and embed robustness into previously published algorithms. The first is an incremental algorithm that significantly reduces the time required to update the cost map used in the task assignment when small changes occur in a complex environment. The second introduces a new robust shortest path algorithm that accounts for uncertainty in the arc costs. The algorithm is computational tractable and is shown to yield performance and robustness that are comparable to more sophisticated algorithms that are not suitable for real-time implementation. Experimental results are presented using this technique on a rover testbed. This thesis also extends a UAV search algorithm to include moving targets in the environment. This new algorithm coordinates a team of UAVs to search an unknown environment while balancing the need to track moving targets. These three improvements have had a big impact because they modify the Receding Horizon Mixed-Integer Linear Programming (RH-MILP) control hierarchy to handle uncertainty and properly react to rapid changes in the environment. Hence, these improvements enable the RH-MILP controller to be implemented in more realistic scenarios.

Department dc:contributor.department

Massachusetts Institute of Technology. Dept. of Mechanical Engineering.

Grantor dc:publisher

Massachusetts Institute of Technology

Year dc:date.issued

2004

Author dc:creator

• Tin, Chung, 1980-

Advisor dc:contributor.advisor

• Jonathan P. How and Daniela Pucci de Farias.

• Mechanical Engineering.

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

OAI identifier oai:identifier

oai:dspace.mit.edu:1721.1/30293