An exploration strategy by constructing Voronoi Diagrams with provable completeness

Abstract

We present novel exploration algorithms and a control law that enable the construction of Voronoi diagrams over unknown areas using a single autonomous vehicle equipped with range sensors. Our control law and exploration algorithms are provably complete. The control law uses range measurements to enable tracking Voronoi edges between two obstacles. Exploration algorithms make decisions at vertices of the Voronoi diagram to expand the explored area until a complete Voronoi diagram is constructed in finite time. MATLAB simulation results are provided to demonstrate the effectiveness of both the control law and the exploration algorithms.