Visibility Maximization with Unmanned Aerial Vehicles in Complex Environments by Kenneth Lee Bachelor of Applied Science (BASc), Mechanical Engineering University of Waterloo (2008) Submitted to the Department of Aeronautics and Astronautics in partial fulfillment of the requirements for the degree of Master of Science in Aeronautics and Astronautics at the MASSACHUSETTS INSTITUTE OF TECHNOLOGY September 2010 (cid:13)c Massachusetts Institute of Technology 2010. All rights reserved. Author .............................................................. Department of Aeronautics and Astronautics August 19, 2010 Certified by.......................................................... Jonathan P. How Richard C. Maclaurin Professor of Aeronautics and Astronautics Thesis Supervisor Accepted by......................................................... Eytan H. Modiano Associate Professor of Aeronautics and Astronautics Chair, Graduate Program Committee 2 Visibility Maximization with Unmanned Aerial Vehicles in Complex Environments by Kenneth Lee Submitted to the Department of Aeronautics and Astronautics on August 19, 2010, in partial fulfillment of the requirements for the degree of Master of Science in Aeronautics and Astronautics Abstract Unmanned aerial vehicles are used extensively in persistent surveillance, search and track, border patrol, and environment monitoring applications. Each of these appli- cations requires the obtainment of information using a dynamic observer equipped with a constrained sensor. Information can only be gained when visibility exists be- tween the sensor and a number of targets in a cluttered environment. Maximizing visibility is therefore essential for acquiring as much information about targets as possible, to subsequently enable informed decision making. Proposed is an algorithm that can design a maximum visibility path given models of the vehicle, target, sensor, environment, and visibility. An approximate visibility, finite-horizon dynamic pro- gramming approach is used to find flyable, maximum visibility paths. This algorithm is compared against a state-of-the-art optimal control solver for validation. Complex scenarios involving multiple stationary or moving targets are considered, leading to loiter patterns or pursuit paths which negotiate planar, three-dimensional, or eleva- tion environment models. Robustness to disturbances is addressed by treating targets as regions instead of points, to improve visibility performance in the presence of un- certainty. A testbed implementation validates the algorithm in a hardware setting with a quadrotor observer, multiple moving ground vehicle targets, and an urban-like setting providing occlusions to visibility. Thesis Supervisor: Jonathan P. How Title: Richard C. Maclaurin Professor of Aeronautics and Astronautics 3 4 Acknowledgments I would like to thank my supervisor, Professor Jonathan How for the opportunity to work at the Aerospace Controls Laboratory. I appreciate his guidance and support throughout the two years of course work, projects, and this thesis, which have taught meanimmenseamountaboutcontrols,optimization,andaerospacesystemshardware and software, about which I knew very little before starting at MIT. I feel much more attuned to the fields of aerospace and robotics because of this wonderful learning experience. I would also truly like to thank Dr. Luca Bertuccelli, who supervised me during my second year at MIT. We met when we began the visibility maximization project, and he guided me through the qualification exams, lab talks, projects, and the writing of this thesis. Amazingly he could be called up at any time to bring fresh insight into difficult problems, and point me in the right direction, for which I am really grateful. I want to thank Dr. Peter Cho at Lincoln Laboratory for providing funding support and entrusting me with this project which has become the subject of my thesis. I wish to thank everyone I’ve met in the Aerospace Controls Laboratory for all the help with homework, the lab talks, and the occasional fun events — it’s been quite a memorable time that we’ve spent together. In addition, I want to thank Kathryn for helping make the lab’s daily operations run really smoothly! Plus, my gratitudes towards friends, mentors, colleagues, and professors who have helped me get to this point and whom I’ve met during my stay, and to my family for their constant love and encouragement. 5 THIS PAGE INTENTIONALLY LEFT BLANK 6 Contents 1 Introduction 17 1.1 Importance of Unmanned Aerial Vehicles . . . . . . . . . . . . . . . . 17 1.2 Autonomy in UAV Applications . . . . . . . . . . . . . . . . . . . . . 18 1.3 Visibility Motion Planning Problem . . . . . . . . . . . . . . . . . . . 19 1.4 Contributions of Thesis . . . . . . . . . . . . . . . . . . . . . . . . . . 20 2 Background 23 2.1 Visibility Maximization Motion Planning . . . . . . . . . . . . . . . . 23 2.2 Optimal Control Formulation . . . . . . . . . . . . . . . . . . . . . . 25 2.3 Visibility Maximization Systems View . . . . . . . . . . . . . . . . . 26 2.4 Modeling and Assumptions . . . . . . . . . . . . . . . . . . . . . . . . 27 2.4.1 Target Motion Models . . . . . . . . . . . . . . . . . . . . . . 28 2.4.2 Sensing Tasks and Sensor Models . . . . . . . . . . . . . . . . 30 2.4.3 Observer Models . . . . . . . . . . . . . . . . . . . . . . . . . 32 2.4.4 Environment Models . . . . . . . . . . . . . . . . . . . . . . . 33 2.4.5 Visibility Models . . . . . . . . . . . . . . . . . . . . . . . . . 35 2.5 Literature Review of Visibility Maximization Motion Planning . . . . 39 2.6 Chapter Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . 40 3 Optimal Control for Visibility Maximization 41 3.1 Block Diagram of Proposed Solution . . . . . . . . . . . . . . . . . . 41 3.2 Visibility Maximization Dynamic Programming Solver . . . . . . . . 42 3.2.1 Visibility Approximation Module . . . . . . . . . . . . . . . . 43 3.2.2 Path Planning Optimization Module . . . . . . . . . . . . . . 47 3.2.3 Summary of VMDP . . . . . . . . . . . . . . . . . . . . . . . 51 3.3 VMDP Versus Optimal Control Solver . . . . . . . . . . . . . . . . . 51 3.3.1 General Pseudospectral Optimization Software . . . . . . . . 51 3.3.2 Visibility Maximization in GPOPS . . . . . . . . . . . . . . . 53 7 3.3.3 VMDP Versus GPOPS in Simple 2-D Environments . . . . . . 57 3.3.4 Performance and Computation Versus Resolution . . . . . . . 60 3.4 Results for A Single Stationary Target . . . . . . . . . . . . . . . . . 62 3.4.1 Complex Scenarios in 2-D Environments . . . . . . . . . . . . 62 3.4.2 Scenarios in 3-D and DEM Environments . . . . . . . . . . . . 65 3.5 Chapter Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . 66 4 Multiple Targets and Parametric Optimization 69 4.1 Multiple Target Formulation . . . . . . . . . . . . . . . . . . . . . . . 69 4.1.1 Weights and Weighted Sum of Per-Target Visibilities . . . . . 70 4.1.2 Maximizing the Minimum Per-Target Visibility . . . . . . . . 71 4.1.3 Diminishing Returns on Per-Target Visibility . . . . . . . . . . 72 4.1.4 Receding Horizon Approach for Complex Objectives . . . . . . 73 4.1.5 Multiple Target VMDP Numerical Results . . . . . . . . . . . 74 4.2 Comparison Against Baseline Parametric Paths . . . . . . . . . . . . 79 4.2.1 Comparisons Between Parametric Optimizations . . . . . . . . 84 4.2.2 Comparisons Against Non-Parametric Optimization . . . . . . 85 4.2.3 Comparisons of Objective Functions. . . . . . . . . . . . . . . 88 4.2.4 Effects of Visibility Approximation Error on Optimization . . 91 4.3 Chapter Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . 92 5 Moving Targets and Uncertainty in Motion Models 95 5.1 Extension of VMDP to Moving Targets . . . . . . . . . . . . . . . . . 95 5.1.1 VMDP Revision for Moving Targets . . . . . . . . . . . . . . . 96 5.1.2 Time-Dependent Visibility Table . . . . . . . . . . . . . . . . 96 5.1.3 Results for Known Target Trajectories . . . . . . . . . . . . . 98 5.2 Robust Target Observation . . . . . . . . . . . . . . . . . . . . . . . . 103 5.2.1 Robust Formulations . . . . . . . . . . . . . . . . . . . . . . . 104 5.2.2 Analysis and Numerical Results for Robust Visibility . . . . . 106 5.3 Chapter Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . 107 6 Testbed Implementation 109 6.1 Testbed Modules . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 109 6.1.1 RAVEN Module . . . . . . . . . . . . . . . . . . . . . . . . . . 110 6.1.2 Test Environment . . . . . . . . . . . . . . . . . . . . . . . . . 113 6.1.3 Visibility Planner Module and Real-Time Visibility Feedback . 116 6.2 Experimental Results . . . . . . . . . . . . . . . . . . . . . . . . . . . 120 8 6.2.1 Ground Observer . . . . . . . . . . . . . . . . . . . . . . . . . 120 6.2.2 Aerial Observer . . . . . . . . . . . . . . . . . . . . . . . . . . 125 6.3 Chapter Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . 126 7 Conclusions and Future Work 129 7.1 Conclusions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 129 7.2 Future Work . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 132 A Visibility Formulation 135 A.1 Definition of Visibility, and Necessary and Sufficient Conditions . . . 135 A.2 Visibility Models . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 137 A.2.1 Planar Visibility Model with Point Target . . . . . . . . . . . 137 A.2.2 Planar Visibility Model with Target Region . . . . . . . . . . 140 A.2.3 3-D Visibility Model . . . . . . . . . . . . . . . . . . . . . . . 142 A.2.4 Elevation Model in Visibility . . . . . . . . . . . . . . . . . . . 144 A.3 Target Region Intersection Calculation . . . . . . . . . . . . . . . . . 145 A.3.1 Translating Target Samples . . . . . . . . . . . . . . . . . . . 145 A.3.2 Uniformly Spaced Samples . . . . . . . . . . . . . . . . . . . . 146 B Path Parameterization and Parametric Optimization 149 B.1 Path Parameterization . . . . . . . . . . . . . . . . . . . . . . . . . . 149 B.2 Parametric Optimization Methods . . . . . . . . . . . . . . . . . . . . 151 B.2.1 Simulated Annealing . . . . . . . . . . . . . . . . . . . . . . . 151 B.2.2 Genetic Algorithm . . . . . . . . . . . . . . . . . . . . . . . . 152 B.2.3 Cross Entropy . . . . . . . . . . . . . . . . . . . . . . . . . . . 152 B.2.4 Tabu Search . . . . . . . . . . . . . . . . . . . . . . . . . . . . 152 B.2.5 Ant Colony Optimization . . . . . . . . . . . . . . . . . . . . 152 B.3 Cross Entropy Implementation . . . . . . . . . . . . . . . . . . . . . . 153 References 164 9 THIS PAGE INTENTIONALLY LEFT BLANK 10