Stochastic Artificial Potentials for Online Safe Navigation

Consider a convex set of which we remove an arbitrary number of disjoints convex sets-the obstacles-and a convex function whose minimum is the agent's goal. We consider a local and stochastic approximation of the gradient of a Rimon-Koditschek navigation function where the attractive potential is the convex function that the agent is minimizing. In particular, we show that if the estimate available to the agent is unbiased, convergence to the desired location while avoiding the obstacles is guaranteed with probability one under the same geometrical conditions as in the deterministic case. Qualitatively these conditions are that the ratio between the maximum and minimum eigenvalue of the Hessian of the objective function is not too large and that the obstacles are not too flat or too close to the desired destination. Moreover, we show that for biased estimates convergence to a point arbitrarily close to the goal is achieved with probability one. The assumptions on the bias for the result to hold are motivated by the study of the estimate of the gradient of a Rimon-Koditschek navigation function for sensor models that fit circles around the obstacles. Numerical examples explore the practical value of these theoretical results.