View-Invariant Regions and Mobile Robot Self-Localization

Simsarian, Kristian and Olson, Thomas J. and Nandhakumar, N. (1996) View-Invariant Regions and Mobile Robot Self-Localization. [SICS Report]



This paper addresses the problem of mobile robot self-localization given a polygonal map and a set of observed edge segments. The standard approach to this problem uses interpretation tree search with pruning heuristics to match observed edges to map edges. Our approach introduces a preprocessing step in which the map is decomposed into 'view-invariant regions' (VIRs). The VIR decomposition captures information about map edge visibility, and can be used for a variety of robot navigation tasks. Basing self-localization search on VIRs greatly reduces the branching factor of the search tree and thereby simplifies the search task. In this paper we define the VIR decomposition and give algorithms for its computation and for self-localization search. We present results of simulations comparing standard and VIR-based search, and discuss the application of the VIR decomposition to other problems in robot navigation.

Item Type:SICS Report
Uncontrolled Keywords:Robot, Self-localization, range data, computational geometry
ID Code:2231
Deposited By:Vicki Carleson
Deposited On:28 Jul 2009
Last Modified:18 Nov 2009 16:02

Repository Staff Only: item control page