Descripción: |
Los algoritmos de planeación de movimiento basados en muestras, tales como el mapa de caminos
probabilísticos (PRM) y sus variantes PRM perezoso y PRM*, construyen una representación basada
en un grafo del espacio libre de colisiones en el espacio de configuraciones. Para resolver problemas
que involucren muchos grados de libertad (alta dimensión) o una gran cantidad de obstáculos, estos
algoritmos requieren un muestreo denso del espacio de configuraciones. Cada vez que se agrega una
nueva muestra al grafo, es necesario realizar el cálculo de sus k-vecinos más cercanos en el mismo, lo
que resulta ser el componente más costoso del algoritmo y requiere de una estructura de datos adicional
para la búsqueda. El objetivo de este trabajo es reducir el tiempo de construcción de los mapas de caminos
en espacios de configuraciones de altas dimensiones. Para ello, en lugar de construir una estructura de
datos adicional para efectuar la búsqueda de vecinos más cercanos, como se hace tradicionalmente en
planeación de movimiento, se propone utilizar el grafo del mapa de caminos para realizar las búsquedas.
Con el fin de mejorar el tiempo de consulta, se hace uso del grafo de proximidad aproximada (APG),
desarrollado para realizar búsquedas en espacios métricos. En este trabajo, se propone una modificación
del algoritmo de búsqueda utilizado en el APG integrándolo en la construcción del mapa de caminos y
se presenta una técnica de refinamiento del grafo en dos etapas. Los resultados experimentales muestran
que el tiempo de construcción del PRM y sus variantes es menor en comparación a utilizar los algoritmos
de búsqueda de k-vecinos más cercano,s descritos en el estado del arte en planeación de movimiento,
para problemas en altas dimensiones. In motion planning, sampling-based path planning algorithms, such as probabilistic roadmaps (PRM)
and its variant Lazy PRM and PRM*, maintain a collision-free roadmap in the configuration space. In
problems with large number of degrees of freedom (high dimension) or environments containing many
obstacles, these algorithms require a large number of samples from the configuration space. Each time
a new configuration is added to the roadmap, it is necessary to compute the k-nearest neighbors of that
configuration in the roadmap. This procedure is usually the most expensive component of the algorithm
and requires an external index for making the search. The goal of this work is to reduce the construction
time of the probabilistic roadmaps in high dimensional configuration spaces. To achieve this goal, the
proposal in this work is to use the same roadmap to perform the searches; Rather than constructing
an additional data structure, as is traditionally done in motion planning.To improve the query time,
this work makes use of the Approximate Proximity Graph (APG) that has been developed for search in
general metric spaces. In this work the search algorithms used in APG have been adapted to work in
roadmaps produced using the PRM algorithm and a two-stage graph refinement technique is proposed.
Experimental results show that by using the APG algorithm the time to build a roadmap PRM and its
variants is reduced, compared to the most popular algorithms for k-nearest neighbor search in motion
planning problems in high dimensional configuration spaces. |