Abstract:
Reliable and efficient acquisition of data from physical spaces has widespread applications in industry, policy, defense, and humanitarian work. Unmanned Aerial Vehicles (UAVs) are an excellent choice for data gathering applications, due to their capability of gaining information at multiple scales. A robust data gathering system needs to reason about multi-resolution nature of information gathering while being safe, and cognizant of its sensory and battery limitations. The state of the art algorithms with provable worst-case guarantees are unable to present an efficient solution online. This thesis addresses three critical aspects of enabling safe, efficient, and multi-resolution data gathering: (1) online budgeted multi-resolution informative path planning (IPP), (2) guaranteeing safety and, (3) optimization of sensing bandwidth for implicit and explicit data gathering requirements.

First, we present an online navigation algorithm to guarantee the safety of the robot via an Emergency Maneuver Library (EML). We define a vehicle to be safe in static environments if it can stay in known unoccupied space while operating in partially known environments. Finding an optimal solution online for a non-holonomic system with non-linear dynamic constraints, in an online fashion is computationally infeasible. We present an efficient method to construct an EML that fully exploits the vehicle ‘s dynamics capabilities and known unoccupied space available to ensure safety at high speeds. Another advantage of the EML is that it defines a pertinent volume from which uncertainty needs to be removed, to ensure UAV’s safety. Further, we present a sensor motion planning approach that optimizes mission costs while using EML to ensure vehicle safety by gaining information relevant to the mission.

Second, we prove that for a specific class of information gathering problems, which consist of informative actions, such as gaining elevation to gather low-resolution data, traditional Markov Decision Process-based approximate solvers are not optimal. In such cases, the belief space dynamics need to be modeled to obtain efficient solutions to the multi-resolution IPP problems.

Third, we present Randomized Anytime Orienteering (RAOr), an anytime, asymptotically near-optimal algorithm, that enables solving aforementioned multi-resolution IPP problems online by taking heuristically guided random walks in the space of near-optimal routes. Although the work focusses on developing motion planning algorithms, we also describe representations that enable these planning algorithms to run on-board on computationally constraint platforms.

The algorithms developed, form a framework for safe, efficient, multi-resolution data gathering that has enabled UAVs to operate in diverse environments, scales, and applications. Further, we evaluate our algorithms on multiple UAVs varying from full-scale helicopters to small quad-rotors, running closed-loop autonomous missions that cumulatively span hundreds of kilometers.

More Information

Thesis Committee Members:
Sebastian Scherer, Chair
William (Red) L. Whittaker
David Wettergreen
Kostas Alexis, University of Nevada, Reno