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. Two randomized approximation algorithms are presented that solve minimum distance localization. The performance of the proposed algorithms is evaluated empirically.
Brown, R. and Donald, B. (2000). Mobile robot self-localization without explicit landmarks. Algorithmica, 26(3/4): 515—559.
2.
Buck, M., Schfer, D., and Noltemeier, H. (1999). Practical strategies for hypotheses elimination on the self-localization problem. Technical Report.
3.
Chazelle, B. and Edelsbrunner, H. (1992). An optimal algorithm for intersecting line segments in the plane. Journal of the Association of Computing Machinery,39: 1—54.
4.
Dudek, G. and Jenkin, M. (2000). Computational Principles of Mobile Robotics. Cambridge University Press.
5.
Dudek, G., Romanik, K., and Whitesides, S. (1998). Localizing a robot with minimum travel. SI AM Journal on Computing, 27(2): 583—604.
6.
Fleischer, R., Romanik, K., Schuierer, S., and Trippen, G. (2001). Optimal robot localization in trees. Information and Computation, 171: 224—247.
7.
Fox, D., Burgard, W., and Thrun, S. (1998). Active markov localization for mobile robots. Robotics and Autonomous Systems, 25: 195—207.
8.
Gindy, H.E. and Avis, D. (1981). A linear algorithm for computing the visibility polygon from a point. Journal of Algorithms, 2: 186—197.
9.
Gonzalez-Banos, H. and Latombe, J. (1998). Planning robot motions for range-image acquisition and automatic 3d model construction. In In Proceedings of AAAI Fall Symposium SeriesMenlo Park, CA.
10.
Guibas, L., Motwani, R., and Raghavan, P. (1997). The robot localization problem. SIAM Journal on Computing, 26(4): 1120—1138.
11.
Hsu, D., Kavraki, L., Latombe, J.C., Motwani, R., and Sorkin, S. (1998). On finding narrow passages with probabilistic roadmap planners. In Proceedings of International Workshop on Algorithmic Foundations of Robotics. March 1998 , Houston, TX.
12.
Kavraki, L. and Latombe, J.C. (1998). Probabilistic roadmaps for robot path planning . In K. G. and A. P., De Pobil (eds) Practical Motion Planning in Robotics: Current Approaches and Future Challenges, pp. 33—53. John Wiley . West Sussex.
13.
Kleinberg, J. (1994). The localization problem for mobile robots. In Proceedings of 35th IEEE Conference on Foundations of Computer Science, Santa Fe, NM, pp. 521—533 IEEE Computer Society Press.
14.
Koenig, S., Mudgal, A., and Tovey, C. (2006). A near-tight approximation lower bound and algorithm for the kidnapped robot problem. In Proceedings of Symposium on Discrete Algorithms, Miami, Florida, pp. 133—142.
15.
Lee, D.T. and Preparata, F. (1984). Euclidean shortest paths in the presence of rectilinear barriers. Networks, 14: 393— 410.
16.
O'Kane, J.M. and LaValle, S.M. (2005). Almost-sensorless localization. In Proceedings of IEEE International Conference on Robotics and Automation , Barcelona, Spain, pp. 3764—3769.
17.
O'Kane, J.M. and LaValle, S.M. (2006). Global localization using odometry. In Proceedings of IEEE International Conference on Robotics and Automation , Orlando, Florida, pp. 37—42.
18.
O'Rourke, J. (1998). Computational Geometry in C. Cambridge University Press.
19.
Rao, M., Dudek, G., and Whitesides, S. (2004). Randomized algorithms for minimum distance localization . In Proceedings of the Sixth Workshop on Algorithmic Foundations of Robotics (WAFR), Zeist, The Netherlands.
20.
Rao, M., Dudek, G., and Whitesides, S. (2005). Minimum distance localization for a robot with limited visibility. In Proceedings of IEEE International Conference on Robotics and Automation. pp. 2438—2445. April 2005 , Barcelona, Spain.
21.
Schuierer, S. (1996). Efficient robot self-localization in simple polygons , In Intelligent Robots: Sensing, Modelling and Planning, Intelligent Robots: World Scientific, pp. 129— 146.
22.
Toussaint, G.T. (1986). A linear-time algorithm for solving the strong hidden-line problem in a simple polygon. Pattern Recognition Letters, 4: 449—451.
