Date of Award

Winter 2011

Project Type

Thesis

Program or Major

Computer Science

Degree Name

Master of Science

First Advisor

Wheeler Ruml

Abstract

Autonomous robots are increasingly becoming incorporated in everyday human activities, and this trend does not show any signs of slowing down. One task that autonomous robots will need to reliably perform among humans and other dynamic objects is motion planning. That is, to reliably navigate a robot to a desired pose as quickly as possible while minimizing the probability of colliding with other objects. This involves not only planning around the predicted future trajectories of dynamic obstacles, but doing so in a real-time manner so that the robot can remain reactive to its surroundings. Current methods do not directly address this problem. This thesis proposes a new real-time planning algorithm called real-time R* (RTR*). RTR* is based on the R* search algorithm that couples random sampling with heuristic search and has been shown to work well in several different robotics domains. Several modifications needed to transform R* into a real-time algorithm are described. Additional modifications that were developed specifically for this problem domain are also detailed. An empirical evaluation is given comparing RTR* with several state-of-the-art motion planning and real-time search algorithms. RTR* shows promising performance and improves on R*, however it underperforms the current state-of-the-art. Several enhancements are discussed that could improve the behavior of RTR*.

Download

Share

COinS