A general deterministic sequence for sampling d-dimensional configuration spaces

Abstract

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.

Trabajos anteriores ya han demostrado que el muestreo determinista puede ser competitivo con respecto al muestreo probabilístico en los planificadores de rutas basados en el muestreo. Sin embargo, la definición de una secuencia de muestreo general para cualquier espacio de configuración d-dimensional que satisfaga los requisitos necesarios para la planificación de rutas no es una cuestión trivial. En este trabajo se propone una secuencia de muestreo determinista, sencilla y eficiente, basada en el uso recursivo, sobre una descomposición de celdas multirejilla, de la ordenación de las 2 celdas descendientes de cualquier celda padre. Esta ordenación se genera mediante el método de construcción digital utilizando una matriz d × d Td. Se introduce una expresión general de esta matriz (es decir, para cualquier d) y se analiza su rendimiento en términos de distancia mutua. El artículo termina con una evaluación del rendimiento del uso de la secuencia de muestreo determinista propuesta en distintos planificadores de rutas conocidos.