Event Location: Newell Simon Hall 1507

Abstract: Motion planning and navigation of outdoor mobile robots has received a lot of attention in the last thirty years, yet today it still remains a challenging problem. Among the many reasons, three stand out. First, most physical mobility systems feature differential constraints that render the coupling between the control and state spaces of the robot quite complicated. Second, outdoor environments are typically partially or entirely unknown; classical motion planning techniques that assume known structure of the world are therefore not directly applicable. Third, such robots typically must be able to operate at speeds commensurate with those of human operators. This poses stringent limitations on available runtime and often hard real-time requirements on the motion planners. The impressive advances in computing capacity in recent years have been unable, by themselves, to meet the computational burden of this problem. New algorithmic approaches to tackle its difficulties continue to be developed to this day.

Most motion planner designs to date are based on evaluating a number of motion alternatives and selecting the best one for the robot to execute. This process of evaluating alternatives is commonly referred to as search. The collection of motion alternatives being evaluated is referred to as a search space, i.e. the space where the search operates. A number of popular approaches to conducting search exist. A few of them are reused so frequently that they are often referred to as standard solutions for implementing search. These are the first algorithms that a beginning roboticist learns, and the first ones to be tried out when developing a new robot. However, if we look at the other component, the search space, we are at a loss to find a similar level of standardization beyond the rudimentary grids.

The goal of this thesis is to formulate the principles of effective search space design in the domain of outdoor mobile robotics, and thereby to make a step forward to standardization in this area. A justified and well-founded result on this topic would be a contribution in at least providing a departing point for evaluation in new robots. In addition, it is likely to lead to faster development cycles and better performance of motion planners in future outdoor mobile robots.

Committee:Alonzo Kelly, Chair

Tony Stentz

Matthew Mason

Steve LaValle, University of Illinois