árboles al azar que exploran rápidos

Question

http://msl.cs.uiuc.edu/rrt/

Puede alguien explicar cómo funciona con RRT redacción simple que es fácil de entender? Leí la descripción en el sitio y en wikipedia.

Lo que me gustaría ver, es un corto implementación de un TSR o una explicación detallada de lo siguiente:

¿Por qué crece el RRT hacia el exterior en lugar de sólo crece muy denso alrededor del centro? ¿Cómo es diferente de un árbol aleatorio ingenuo?

¿Cómo se selecciona el siguiente vértice nuevo que intentamos alcanzar?

Sé que hay una Motion Strategy Library que podría descargar, pero preferiría entender la idea antes de profundizar en el código y no al revés.

Answer 1

El algoritmo RRT más simple posible ha tenido tanto éxito porque es bastante fácil de implementar. Las cosas tienden a complicarse cuando:

• necesidad de visualizar los conceptos de planificación en más de dos dimensiones
• no están familiarizados con la terminología asociada con la planificación, y;
• en la gran cantidad de variantes de RRT que se han descrito en la literatura.

Pseudo código

El algoritmo básico se ve algo como esto:

1. de inicio con un árbol de búsqueda vacío

2. Añadir su ubicación inicial (configuración) a la búsqueda árbol

3. mientras que su árbol de búsqueda no ha alcanzado el objetivo (y no se ha quedado sin tiempo)

   3.1. Elija una ubicación (configuración), q_r, (con alguna estrategia de muestreo)

   3.2. Encuentre el vértice en el árbol de búsqueda más cercano a ese punto al azar, q_n

   3.3. Intente agregar un borde (ruta) en el árbol entre q_n y q_r, si puede vincularlos sin que se produzca una colisión.

A pesar de que la descripción es adecuada, después de un tiempo trabajando en este espacio, la verdad es que prefiero el pseudocode of figure 5.16 on RRT/RDT en el libro de Steven Lavalle "Algoritmos de planificación".

estructura de árbol

La razón por la que el árbol termina cubriendo todo el espacio de búsqueda (en la mayoría de los casos) es debido a la combinación de la estrategia de muestreo, y siempre en busca de conectarse desde el punto más cercano en el árbol.Este efecto se describe como la reducción del Voronoi bias.

estrategia de muestreo

La elección de dónde colocar el siguiente vértice que va a intentar conectar con el problema de muestreo. En casos simples, donde la búsqueda es de baja dimensión, la colocación aleatoria uniforme (o colocación aleatoria uniforme sesgada hacia la meta) funciona adecuadamente. En problemas de gran dimensión, o cuando los movimientos son muy complejos (cuando las articulaciones tienen posiciones, velocidades y aceleraciones), o la configuración es difícil de controlar, las estrategias de muestreo para RRT siguen siendo un área de investigación abierta.

Bibliotecas

El MSL library es un buen punto de partida si realmente estás atascado en la aplicación, pero no se ha mantenido activa desde el año 2003. Una biblioteca de más arriba-hasta la fecha es el Open Motion Planning Library (OMPL). También necesitarás una buena biblioteca de detección de colisiones.

Planificación Terminología & consejos

Desde el punto de vista de la terminología, lo difícil es darse cuenta de que a pesar de muchos de los diagramas que se ven en los (primeros años de) Publicaciones en TSR son en dos dimensiones (árboles que unen 2 puntos), que este es el caso más simple .

Normalmente, se requiere una forma matemáticamente rigurosa de describir situaciones físicas complejas. Un buen ejemplo de esto es la planificación de un brazo robótico con enlaces n. La descripción del extremo de un brazo de este tipo requiere un mínimo de n ángulos de unión. Este conjunto de parámetros mínimos para describir una posición es una configuración (o algunas publicaciones estado). Una sola configuración es a menudo denota q

La combinación de todas las configuraciones posibles (o un subconjunto de los mismos) que se pueden lograr compensar un espacio de configuración (o estado espacio). Esto puede ser tan simple como un plano bidimensional sin límites para un punto en el plano, o combinaciones increíblemente complejas de rangos de otros parámetros.