RRT, un algoritmo de exploración basado en árboles
Las siglas RRT provienen de Rapidly-exploring Random Tree. Es un algoritmo de exploración de un espacio n-dimensional y utilizado para la planificación de movimiento de robots basándose en la trayectoria dada por las ramas del árbol generado (a diferencia otros algoritmos como A*).
Procedimiento:
Partimos de un nodo inicial, la raíz del árbol, en un espacio en 2 dimensiones de ancho spaceX y alto spaceY. La siguiente iteración consistiría en:
//seleccionamos al azar cualquier punto de nuestro espacio
random_pos = random(spaceX, spaceY)//calculamos el vértice más cercano a ese punto
nearest_vertex = findNearestVertexTo(random_pos)//con estas dos posiciones se puede definir una dirección de avance //creamos un nuevo vertice en esa direccion y según un STEP
vertex_to_add = vertexInDirection(nearest_vertex, random_pos, STEP)//lo añadimos al grafo
g.addVertexToExistingVertex(vertex_to_add, nearest_vertex)
Repetiendo esta iteración una y otra vez conseguimos que el árbol explore el espacio:
Búsqueda hacia el objetivo:
Una vez tenemos nuestro árbol que se expande si queremos llegar a una zona concreta del espacio en el que se encuentra basta con comprobar si el nuevo vértice a añadir está en esa zona objetivo. En ese caso, la ruta estaría definida por las conexiones que unen este nuevo vértice con la raíz, es decir, recorrer todos los sucesivos padres de este nuevo vértice (siendo los nuevos vértices que colocamos los hijos y padres los vértices con los que éstos se unen).
Para evitar obstáculos habría que comprobar si la trayectoria entre el vértice a añadir y su padre está libre. Con obstáculos lo suficientemente grandes basta con comprobar si el vértice a añadir cae dentro del obstáculo.
Aún así, debido a la aleatoriedad de su formación, el camino creado no suele ser óptimo, presenta zigzags innecesarios.
Variantes:
- En la selección de la posición aleatoria se puede añadir un sesgo de zona objetivo parq que elija con más probabilidad zonas cercanas al objetivo. También se puede añadir otro sesgo para favorecer que las ramas crezcan por igual haciendo que los nuevos vértices aparezcan más cerca de zonas menos densas (mediante regiones de Voronoi)
- RRT*: esta versión mejora los caminos en cada iteración, recableando los vértices en una zona cercana al nuevo vértice a añadir. De esta manera, al cabo de muchas iteraciones se llega a una solución muy cercana a la óptima.
- Informed RRT*: se hace uso de la heurística para acelerar la convergencia de RRT* a la mejor solución.
- RRT*-FND: extensión de RRT* para entornos dinámicos.
- Real-Time RRT*: permite que el árbol creado siga pegado a un agente en movimiento, aprovechando las ramas anteriores que puedan seguir siendo utilizadas y descartando las que hayan quedado bloqueadas.
Código:
Podéis encontrar el código escrito en Processing en
