Learning polyline maps from range scan data acquired with mobile robots

Geometric representations of the environment play an important role in mobile robotics as they support various tasks such as motion control and accurate localization. Popular approaches to represent the geometric features of an environment are occupancy grids or line models. Whereas occupancy grids require a huge amount of memory and therefore do not scale well with the size of the environment, line models are unable to correctly represent corners or connections between objects. In this paper we present an algorithm that learns sets of polylines from laser range scans. Starting with an initial set of polylines generated from the range scans it iteratively optimizes these polylines using the Bayesian information criterion. During the optimization process our algorithm utilizes information about the angles between line segments extracted from the original range scans. We present experiments illustrating that our algorithm is able to learn accurate and highly compact polyline maps from laser range data obtained with mobile robots.