On Probabilistic Completeness of Probabilistic Cell Decomposition
This work addresses a theoretical gap for researchers in robotics and AI path planning, but it is incremental as it confirms an existing postulate.
The paper tackles the problem of proving probabilistic completeness for Probabilistic Cell Decomposition (PCD), a path planning method, and provides the first detailed proof of this property.
Probabilistic Cell Decomposition (PCD) is a probabilistic path planning method combining the concepts of approximate cell decomposition with probabilistic sampling. It has been shown that the use of lazy evaluation techniques and supervised sampling in important areas result in a high performance path planning method. Even if it was postulated before that PCD is probabilistically complete, we present a detailed proof of probabilistic completeness here for the first time.