Generalized local Voronoi diagram of visible region

Abstract

A circular robot in unknown environment, populated by non-overlapping obstacles is considered. The robot is equipped with a discrete scanner e.g. laser range scanner. We present a method for local construction of a one-dimensional structure, similar to the generalized Voronoi diagram. We call this structure a generalized local Voronoi diagram (GLVD). GLVD is constructed from scan points of the visible region around the robot. We showed that GLVD partly matches, within the tolerances determined by the uncertainties of the scan points, the generalized Voronoi diagram generated by the free-form obstacles. The existence of a function, which groups the scan points into appropriate clusters, is required. The typical results of the experiments, conducted in the laboratory using SICK's laser range scanner PLS200, are presented.