Búsqueda Discreta que Lleva a la Exploración Continua para la Planificación de Movimiento Quodinámico

Este documento presenta el planificador de Búsqueda Discreta que Lleva a la Exploración Continua (DSLX), un enfoque de multi-resolución para la planificación de movimiento que es adecuado para problemas desafiantes que involucran robots con restricciones quodinámicas. Inicialmente, el método descompone el espacio de trabajo para construir un grafo que codifica la adyacencia física de las regiones descompuestas. Este grafo se busca para obtener líderes, es decir, secuencias de regiones que pueden ser exploradas con métodos de árbol basados en muestreo para generar trayectorias de solución. En lugar de tratar la búsqueda discreta del grafo de adyacencia y la exploración del espacio de estado continuo como componentes separados, DSLX pasa información de uno a otro de maneras innovadoras. Cada líder sugiere qué regiones explorar y la exploración retroalimenta información a la búsqueda discreta para mejorar la calidad de los futuros líderes. La información se codifica en pesos de borde, que indican la importancia de incluir las regiones asociadas con un borde en el próximo paso de exploración. El cálculo de pesos, líderes y la exploración real conforman el núcleo del algoritmo. La extensa experimentación muestra que DSLX es muy versátil. La búsqueda discreta puede cambiar drásticamente el líder para reflejar nueva información, lo que permite a DSLX encontrar soluciones incluso cuando los planificadores de árbol basados en muestreo se estancan. Resultados experimentales en una variedad de problemas desafiantes de planificación de movimiento quodinámico muestran acelereaciones computacionales de dos órdenes de magnitud sobre otros métodos de planificación de movimiento ampliamente utilizados.