Path planning using probabilistic cell decomposition

We present a new approach to path planning in high-dimensional static configuration spaces. The concept of cell decomposition is combined with probabilistic sampling to obtain a method called probabilistic cell decomposition (PCD). The use of lazy evaluation techniques and supervised sampling in important areas leads to a very competitive path planning method. It is shown that PCD is probabilistic complete, PCD is easily scalable and applicable to many different kinds of problems. Experimental results show that PCD performs well under various conditions. Rigid body movements, maze like problems as well as path planning problems for chain-like robotic platforms have been solved successfully using the proposed algorithm.