Development and Implementation of a Self-Building Global Map for Autonomous Navigation

Abstract

Students at Virginia Tech have been developing autonomous vehicles for the past five years. The purpose of these vehicles has been primarily for entry in the annual international Intelligent Ground Vehicle Competition (IGVC), however further applications for autonomous vehicles range from UneXploded Ordinance (UXO) detection and removal to planetary exploration. Recently, Virginia Tech developed a successful autonomous vehicle named Navigator. Navigator was developed primarily for entry in the IGVC, but also intended for use as a research platform. For navigation, Navigator uses a local obstacle avoidance method known as the Vector Field Histogram (VFH). However, in order to form a complete navigation scheme, the local obstacle avoidance algorithm must be coupled with a global map.

This work presents a simple algorithm for developing a quasi-free space global map. The algorithm is based on the premise that the robot will be given multiple attempts at a particular goal. During early attempts, Navigator explores using solely local obstacle avoidance. While exploring, Navigator records where it has been and uses this information on subsequent attempts. Further, this thesis outlines the look-ahead method by which the global map is implemented. Finally, both simulated and experimental results are presented.

The aforementioned global map building algorithm uses a common method of localization known as odometry. Odometry, also referred to as dead reckoning, is subject to inaccuracy caused by systematic and non-systematic errors. In many cases, the most dominant source of inaccuracy is systematic errors. Systematic errors are inherent to the vehicle; therefore, the dead reckoning inaccuracy grows unbounded. Fortunately, it is possible to largely eliminate systematic errors by calibrating the parameters such that the differences between the nominal dimensions and the actual dimensions are minimized. This work presents a method for calibration of mobile robot parameters using optimization. A cost function is developed based on the well-known UMBmark (University of Michigan Benchmark) test pattern. This method is presented as a simple time efficient calibration tool for use during startup procedures of a differentially driven mobile robot. Results show that this tool consistently gives greater than 50% improvement in overall dead reckoning accuracy on an outdoor mobile robot.