A general deterministic sequence for sampling d-dimensional configuration spaces

Rosell, Jan | 2007

Previous works have already demonstrated that deterministic sampling can be competitive with respect to probabilistic sampling in sampling-based path planners. Nevertheless, the definition of a general sampling sequence for any d-dimensional Configuration Space satisfying the requirements needed for path planning is not a trivial issue. This paper makes a proposal of a simple and yet efficient deterministic sampling sequence based on the recursive use, over a multi-grid cell decomposition, of the ordering of the 2d descendant cells of any parent cell. This ordering is generated by the digital construction method using a d × d matrix Td. A general expression of this matrix (i.e. for any d) is introduced and its performance analyzed in terms of the mutual distance. The paper ends with a performance evaluation of the use of the proposed deterministic sampling sequence in different well known path planners.