Por favor, use este identificador para citar o enlazar este ítem:
http://cicese.repositorioinstitucional.mx/jspui/handle/1007/456| Planeación de movimientos con índices métricos Motion planning with metric indexes | |
| ANGELLO JAHIR HOYOS IBARRA | |
| EDGAR LEONEL CHAVEZ GONZALEZ UBALDO RUIZ LOPEZ | |
| Acceso Abierto | |
| Atribució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. | |
| 2016 | |
| Tesis de maestría | |
| Español | |
| Hoyos Ibarra, A. 2016. Planeación de movimientos con índices métricos. Tesis de Maestría en Ciencias. Centro de Investigación Científica y de Educación Superior de Ensenada, Baja California. 60 pp. | |
| CIENCIAS TECNOLÓGICAS | |
| Aparece en las colecciones: | Tesis - Ciencias de la Computación |
Cargar archivos:
| Fichero | Descripción | Tamaño | Formato | |
|---|---|---|---|---|
| tesis_ajhoyos_final.pdf | Versión completa de la tesis | 5.54 MB | Adobe PDF | Visualizar/Abrir |