UC Santa Cruz

Robots are frequently being used to explore environments that are largely inaccessible to humans. Most people are familiar with the ground rovers such as Spirit, Opportunity, and Curiosity that are on Mars. Autonomous underwater vehicles are becoming more widely used to conduct oceanographic surveys, particularly in places that people cannot go, such as under the polar ice caps. A large part of increasing the utility of these robotic missions will involve giving the robots significantly enhanced autonomy, particularly when it comes to planning precisely what aspects of the environment to survey and sample.

Much of the research on robotic path planning has focused on finding minimal cost paths between two points, and being able to rapidly re-plan when environmental conditions change. Less research has been done into how robots should plan paths that allow them to maximize utility, such as information gathered. One of the primary reasons for this is that finding the optimal solution to the maximization problem is NP-hard, and thus cannot be computed in a tractable amount of time, much less in real time.

This dissertation presents a computationally tractable method for allowing robots to plan paths that can approximately maximize information gathered while satisfying any relevant horizon constraints, such as a deadline. It builds atop existing algorithms known to be capable of rapid planning and re-planning, such as D*. The algorithm utilizes these methods for computing lowest-cost paths between nodes in the environment, and then planning which nodes to search based on a function of both the cost of exploration and the expected amount of information contained at the nodes. Experimental results in small environments show that the algorithm will mostly generate paths that are at least 75% of optimal.