Probability Navigation Function for Stochastic Static Environments

The navigation function (NF) is widely used for motion planning of autonomous vehicles. Such a function is bounded, analytic, and guarantees convergence due to its Morse nature, while having a single minimum value at the target point. This results in a safe path to the target. Originally, the NF was developed for deterministic scenarios where the positions of the robot and the obstacles are known. Here we extend the concept of NF for static stochastic scenarios. We assume the robot, the obstacles and the workspace geometries are known, while their positions are random variables. We define a new Probability NF that we call PNF by introducing an additional permitted collision probability, which limits the risks (to a set value) during the robot's motion. The Minkowski sum is generalized for the geometries of the robot and the obstacles with their respective Probability Density Functions (PDF), that represent their locations' uncertainties. The probability for a collision is therefore the convolution of the robot's geometry, the obstacles' geometries and the PDFs of their locations The novelty of the proposed algorithm is in its ability to provide a converging trajectory in stochastic environment without inflating the ambient space dimension. We demonstrate our algorithm performances using a simulator, and compare its results with the conventional NF algorithm and with a version of the well known RRT* and Voronoi Uncertainty Fields methods for uncertain scenarios. Finally, we show simulation results of the PNF in disc-shaped world, as well as in star-shaped world.