4.3: Planificación de rutas basada en muestreos

Las secciones anteriores han introducido una serie de algoritmos completos para el problema de planeación de rutas, es decir, encontrarán una solución eventualmente si existe. Las soluciones completas a menudo son inviables, sin embargo, cuando el espacio de estado posible es grande. Este es el caso de los robots con múltiples grados de libertad como los brazos. En la práctica, la mayoría de los algoritmos solo son resolución completa, es decir, solo completa si la resolución es lo suficientemente fina, ya que el espacio de estado necesita ser algo discretizado para que operen (por ejemplo, en una cuadrícula) y algunas soluciones podrían perderse en función de la resolución de la discretización.

Figura\(\PageIndex{1}\): En sentido contrario a las agujas del reloj: Exploración aleatoria de un espacio de búsqueda 2D mediante muestreo aleatorio de puntos y conectándolos a la gráfica hasta que se encuentre un camino factible entre inicio y meta.

En lugar de evaluar todas las soluciones posibles o usar una solución cinemática inversa basada en Jacobian no completa, los planificadores basados en samplingbased crean posibles rutas agregando puntos aleatoriamente a un árbol hasta que se encuentre alguna solución o expire el tiempo. A medida que la probabilidad de encontrar una ruta se acerca a una cuando el tiempo llega al infinito, los planificadores de rutas basados en muestreo son probabilísticos completos. Ejemplos destacados de planificadores basados en muestreos son Rapidlyexploring Random Trees (RRT) (LaValle 1998) y Probabilistic Roadmaps (PRM) (Kavraki, Svestka, Latombe & Overmars 1996). En la Figura 4.3.1 se muestra un ejemplo de ejecución de RRT para un objetivo desconocido, reduciendo así el problema de planificación de ruta a un problema de búsqueda.

Este ejemplo ilustra bien cómo un planificador basado en muestreo puede explorar rápidamente una gran parte del espacio y afina una solución a medida que pasa el tiempo. Mientras que RRT puede entenderse como cultivar un solo árbol desde el punto de inicio de un robot hasta que una de sus ramas alcanza una meta, los mapas probabilísticos crean un árbol mediante el muestreo aleatorio de puntos en el espacio de estados, probando si están libres de colisiones, conectándolos con puntos vecinos usando caminos que reflejar la cinemática de un robot, y luego usar algoritmos de ruta más corta de gráficos clásicos para encontrar las rutas más cortas en la estructura resultante. La ventaja de este enfoque es claramente que tal hoja de ruta probabilística tiene que ser creada solo una vez (asumiendo que el entorno no está cambiando) y luego puede ser utilizada para múltiples consultas. Por lo tanto, los PRM son un algoritmo de planificación de ruta de consulta múltiple. Por el contrario, los RRT se conocen como algoritmos de planificación de ruta de consulta única.

En la práctica, el límite entre los diferentes algoritmos históricos se ha vuelto muy difuso, y existen variantes de consulta única y multiconsulta tanto de RRT como de PRM. Es importante señalar que no hay algorítmo/heurístico de bala plateada e incluso sus conjuntos de parámetros son altamente específicos de problemas. Por lo tanto, limitaremos nuestra discusión sobre heurísticas útiles que son comunes a los planificadores basados en muestreos.

4.3.1. Algoritmo básico

Que X sea un espacio de estado d-dimensional. Este puede ser el estado del robot dado en términos de traslación y rotaciones (6 dimensiones), un subconjunto de los mismos, o el espacio articular con una dimensión por posible ángulo de articulación. Que G X sea una bola d (esfera ddimensional) en el estado-espacio que se considera la meta, y t el tiempo permitido. Un planificador de árboles procede de la siguiente manera:

Tree=Init (X, inicio);

MIENTRAS ElapsedTime () < t Y NoGoalFound (G) HACEN

newpoint = statetoExpandFrom (Árbol);

nuevosegmento = CreatePathToTree (newpoint);

SI elijoToAdd (nuevosegmento) ENTONCES

Árbol=Insertar (Árbol, nuevosegmento);

ENDIF

ENDMIENTRAS

Regreso Árbol

Este proceso se puede repetir en el árbol resultante mientras el tiempo lo permita. Esto se conoce como algoritmo AnyTime. Dada una métrica de distancia adecuada, el costo a meta se puede almacenar en cada nodo del árbol (mucho más fácil si se cultiva el árbol desde la meta hasta el inicio), lo que permite recuperar el camino más corto fácilmente. Hay cuatro puntos clave en este algoritmo:

1. Encontrar el siguiente punto para agregar al árbol (o descartar) (statetoExpandFrom).
2. Averiguar dónde y cómo conectar este punto al árbol tomando en cuenta la cinemática del robot (CreatePathToTree).
3. Probar si esta ruta es adecuada, es decir, libre de colisiones.
4. Encontrar el siguiente punto para agregar.

Un método prominente es elegir un punto aleatorio en el espacio de estados y conectarlo al punto existente más cercano en el árbol o a la meta. Esto requiere buscar en todos los nodos del árbol y calcular su distancia al punto candidato. Otros enfoques ponen preferencias en nodos con menos grados de salida (aquellos que aún no tienen muchas conexiones) y eligen un nuevo punto dentro de su vecindad. Ambos enfoques hacen que sea probable que explore rápidamente todo el estado-espacio.

Si hay restricciones impuestas en el camino del robot, por ejemplo, el robot necesita sostener una copa y por lo tanto no se supone que gire su muñeca, esta dimensión simplemente puede sacarse del espacio estatal.

Una vez que se encuentra una ruta posible, este espacio se puede reducir al elipsoide que limita la longitud máxima de la ruta. Este elipsoide se puede construir montando un cable de la longitud máxima de trayectoria entre el inicio y la portería y empujándolo hacia afuera con una pluma. Toda el área a la que se puede llegar con la pluma restringida por el cable puede contener un punto que posiblemente pueda conducir a una trayectoria más corta. Este enfoque es particularmente efectivo cuando se ejecutan múltiples copias del mismo planificador en paralelo e intercambian las rutas más cortas una vez que se encuentran (Otte & Correll 2013).

4.3.2. Puntos de conexión con el árbol

Un nuevo punto está conectado clásicamente al punto más cercano ya en el árbol o a la meta. Esto se puede hacer calculando la distancia a todos los puntos que ya están en el árbol. Esto no necesariamente genera el camino más corto, sin embargo. Una mejora reciente ha sido realizada por RRT*, que conecta el punto con el árbol de una manera que minimiza la longitud total del camino. Esto se puede hacer considerando todos los puntos en el árbol dentro de una bola d (en un mapa 2D, d = 2, es decir, un círculo) desde el radio fijo desde el punto a sumar y encontrando el punto que minimice la longitud total del camino hasta el inicio.

Agregar un punto al árbol también es un buen momento para tomar en cuenta la cinemática específica de un robot, por ejemplo un automóvil. Aquí, se puede utilizar un planificador local para generar una trayectoria adecuada que tome en cuenta la orientación del vehículo en cada punto del árbol.

4.3.3. Comprobación de colisiones

Los algoritmos eficientes para probar colisiones merecen una sección dedicada. Si bien el problema es intuitivo en la planificación del espacio de configuración en 2D (el robot se reduce a un punto) y se puede resolver mediante una simple prueba de punto en polígono, el problema es más complicado para los manipuladores que están sujetos a autocolisión.

Como la comprobación de colisiones toma hasta el 90% del tiempo de ejecución en el problema de planificación de rutas, un método exitoso para aumentar la velocidad computacional es la “evaluación de colisión perezosa”. En lugar de verificar cada punto en busca de una posible colisión, el algoritmo primero encuentra una ruta adecuada. Sólo entonces, comprueba cada segmento de esta ruta en busca de colisiones. En caso de que algunos segmentos estén en colisión, se eliminan y el algoritmo continúa, pero mantiene los segmentos de la ruta exitosa que estaban libres de colisión.