Ph.D Thesis

Ph.D StudentAdam Amit
SubjectVision-Based Navigation Packages
DepartmentDepartment of Applied Mathematics
Supervisors PROF. Ehud Rivlin
PROF. Ilan Shimshoni


This thesis is about the use of vision for mobile robot navigation. Two basic elements involved in navigation of a mobile robot are a motion planning algorithm, and a sensor which is used to update the position of the robot. The motion planning algorithm is used to solve the geometric problem of finding a nominal path from the initial position to the final desired position. As the robot executes this path, due to numerous reasons, uncertainty in its position develops. The robot then has to use the sensor in order to update its position. Many sensors, and in particular vision-based sensors, exhibit varying performance across the environment. In some areas of the environment the sensor may work very well and yield accurate position estimates, while in other areas it may fail completely. Due to this spatial variation of sensor performance, it is natural to ask how well do the sensor and the motion planning algorithm work together as a ``navigation package''. When we follow a nominal path computed by the motion planning algorithm, can we expect the sensor to perform reasonably along this path ? Which of a number of available motion planners will plan paths along which a given sensor will perform as required ? From a number of different sensors, which is the best to use in combination with a given motion planner ? Towards answering these questions, we first describe a vision-based sensor and a method to predict its (varying) performance across the environment. Our sensor is based on the assumption that a set of matching points between two images is given. We therefore address the issue of obtaining such a set of matches. We present an algorithm which rejects false matches from an input set consisting of both correct and false matches between two images. After discussing a method which reduces the rate at which the position uncertainty grows, we turn to the higher level issue of choosing between different combinations of nominal paths and sensors. Each combination of motion planner and sensor defines a decision process. A policy to be employed in this decision process is searched for. The navigation package whose decision process and associated policy yield a higher gain is the navigation package we prefer to use. We see this work as a basis for the development of a meta-algorithm that will automatically choose the preferred combination of motion planning algorithm and sensor. We emphasize the importance of coordinating the choice of motion planner and sensor. As to the lower level issues associated with visual navigation, our contribution to rejection of outliers in image matching has numerous potential applications beyond navigation.