Publication:
A general deterministic sequence for sampling d-dimensional configuration spaces

Thumbnail Image
Files

Files

A General Deterministic Sequence for Sampling d-dimensional Configuration Spaces.pdf (361.58 KB)
View Statistics
Reference Managers
Mendeley
Indexers
Google Scholar CORE
QR Code
QR Code
Authors

Authors

Rosell, Jan
Roa Garzón, Máximo A.
Pérez Ruiz, Alexander
Abstract (Spanish)
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.
Abstract (English)
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.
Extent
14 páginas
URI: https://repositorio.escuelaing.edu.co/handle/001/2369
Collections

Collections

AB - Ecitrónica
References

M. S. Branicky, S. M. LaValle, K. Olson, and L. Yang. Quasi-randomized path planning. In Proc. of the IEEE Int. Conf. on Robotics and Automation, pages 1481–1487, 2001.

D. Hsu, T. Jiang, J. Reif, and Z. Sun. The bridge test for sampling narrow passages with probabilistic roadmap planners. In Proc. of the IEEE Int. Conf. on Robotics and Automation, pages 4420–4426, 2003.

L. E. Kavraki, P. Svestka, J.-C. Latombe, and M. K. Overmars. Probabilistic roadmaps for path planning in high - dimensional configuration spaces. IEEE Trans. on Robotics and Automation, 12(4):566–580, August 1996.

J. Kuffner. Effective sampling and distance metrics for 3D rigid body path planning. In Proc. of the IEEE Int. Conf. on Robotics and Automation, pages 3993–3998, 2004.

J. J. Kuffner and S. M. LaValle. RRT-connect: An efficient approach to single-query path planning. In Proc. of the IEEE Int. Conf. on Robotics and Automation, pages 995–1001, 2000.

S. M. LaValle, M. S. Branicky, and S. R. Lindemann. On the relationship between classical grid search and probabilistic roadmaps. Int. J. of Robotics Res., 23(7-8):673–692, 2004.

P. Leven and S. Hutchinson. Using manipulability to bias sampling during the construction of probabilistic roadmaps. IEEE Trans. on Robotics and Automation, 19(6):1020–1026, 2003.

S. R. Lindemann, A. Yershova, and S. M. LaValle. Incremental grid sampling strategies in robotics. In Proc. of the Sixth Int. Workshop on the Algorithmic Foundations of Robotics, 2004.

J. Rosell and M. Heisse. An efficient deterministic sequence for samplingbased motion planners. In Proc. of the IEEE Int. Symp. on Assembly and Task Planning, 2005.

G. Sanchez and J.C. Latombe. A single-query bi-directional probabilistic roadmap planner with lazy collision checking. In Proc. of the 9th Int. Symposium on Robotics Research, 2001.