On probabilistic completeness and expected complexity for probabilistic path planning

Abstract

The probabilistic path planner (PPP) is a general planning scheme that yields fast robot path planners for a wide variety of problems, involving, e.g., high degree of freedom articulated robots, nonholonomic robots, and multiple robots. In this paper we gointo theoretical aspects regarding the behaviour of PPP. We formulate general properties that guarantee probabilistic completeness of PPP, and we show how these apply to various robot types. Furthermore, we present results which, under certain assumptions on the free con guration space, give estimates of the expected running times. For example, under one such assumption, we show that the expected running time of PPP grows only logarithmically with the complexity of the problem that it solves. 1