Two new approaches to minimum distance localization <?xml:namespace prefix = "o" ns = "urn:schemas-microsoft-com:office:office" /><o:p></o:p>

Abstract

The problem of minimum distance localization in environments that may contain self-similarities is addressed. A mobile robot is placed at an unknown location inside a 2D self-similar polygonal environment P. The robot has a map of P and can compute visibility data through sensing. However, the self-similarities in the environment mean that the same visibility data may correspond to several different locations. The goal, therefore, is to determine the robot’s true initial location while minimizing the distance traveled by the robot. We consider four approximation algorithms for the robot localization problem. Two approximation algorithms are presented to solve minimum distance localization. One of them is based on a simple triangulation of a polygon representing a map. And another algorithm is based on using windows of the overlay intersection region of a simple polygon representing a map. A simulation program of experimental studies of these algorithms is conducted. The numerical results and their interpretation are given.