Tools and Algorithms for Mobile Robot Navigation with Uncertain Localization

The ability for a mobile robot to localize itself is a basic requirement for reliable long range autonomous navigation. This thesis introduces new tools and algorithms to aid in robot localization and navigation. I introduce a new range scan matching method that incorporates realistic sensor noise models. This method can be thought of as an improved form of odometry. Results show an order of magnitude of improvement over typical mobile robot odometry. In addition, I have created a new sensor-based planning algorithm where the robot follows the locally optimal path to the goal without exception, regardless of whether or not the path moves towards or temporarily away from the goal. The cost of a path is defined as the path length. This new algorithm, which I call "Optim-Bug," is complete and correct. Finally, I developed a new on-line motion planning procedure that determines a path to a goal that optimally allows the robot to localize itself at the goal. This algorithm is called "Uncertain Bug." In particular, the covariance of the robot's pose estimate at the goal is minimized. This characteristic increases the likelihood that the robot will actually be able to reach the desired goal, even when uncertainty corrupts its localization during movement along the path. The robot's path is chosen so that it can use known features in the environment to improve its localization. This thesis is a first step towards bringing the tools of mobile robot localization and mapping together with ideas from sensor-based motion planning