Learning And Vision Algorithms For Robot Navigation PDF Download

Abstract: "This thesis studies problems that a mobile robot encounters while it is navigating through its environment. The robot either explores an unknown environment or navigates through a somewhat familiar environment. The thesis addresses the design of algorithms for 1. environment learning, 2. position estimation using landmarks, 3. visual landmark recognition. In the area of mobile robot environment learning, we introduce the problem of piecemeal learning of an unknown environment: the robot must return to its starting point after each piece of exploration. We give linear time algorithms for exploring environments modeled as grid- graphs with rectangular obstacles. Our best algorithm for piecemeal learning of arbitrary undirected graphs runs in almost linear time. It is crucial for a mobile robot to be able to localize itself in its environment. We describe a linear time algorithm for localizing the mobile robot in an environment with landmarks. The robot can identify these landmarks and measure their bearings. Given such noisy meaurements, the algorithm estimates the robot's position and orientation with respect to the map of the environment. The algorithm makes efficient use of our representation of the landmarks by complex numbers. The thesis also addresses the problem of how landmarks in the robot's surroundings can be recognized visually. We introduce an efficient, model-based recognition algorithm that exploits a fast version of simulated annealing. To avoid false recognition, we propose a method to select model images by measuring the information content of the images. The performance of the algorithm is demonstrated with real-world images of traffic signs."