NAPVIG: Local Generalized Voronoi Approximation for Reactive Navigation in Unknown and Dynamic Environments

In this paper, we propose a novel online approach for reactive local navigation of a robotic agent, based on a fast approximation of the Generalized Voronoi Diagram in a neighborhood of the robot’s position. We consider the context of an unknown environment characterized by some narrow passages and a dynamic configuration. Given the uncertainty and unpredictability that affect the scenario, we aim at computing trajectories that are farthest away from every obstacle: this is obtained by following the Voronoi diagram. To ensure full autonomy, the navigation task is performed relying only upon onboard sensor measurement without any a-priori knowledge of the environment. The proposed technique builds upon a smooth free space representation that is spatially continuous and based on some raw measurements. In this way, we ensure an efficient computation of a trajectory that is continuously re-planned according to incoming sensor data. A theoretical proof shows that in ideal conditions the outlined solution exactly computes the local Generalized Voronoi Diagram. Finally, we assess the reactiveness and precision of the proposed method with realistic real-time simulations and with real-world experiments.