Hoja de ruta probabilística
El planificador probabilístico de la hoja de ruta [1] es un algoritmo de planificación de movimiento en robótica, que resuelve el problema de determinar una ruta entre una configuración inicial del robot y una configuración objetivo evitando colisiones.
La idea básica detrás de PRM es tomar muestras aleatorias del espacio de configuración del robot, probarlas para ver si están en el espacio libre y usar un planificador local para intentar conectar estas configuraciones a otras configuraciones cercanas. Se agregan las configuraciones de inicio y objetivo, y se aplica un algoritmo de búsqueda de gráfico al gráfico resultante para determinar una ruta entre las configuraciones de inicio y objetivo.
El planificador probabilístico de hoja de ruta consta de dos fases: una fase de construcción y una fase de consulta. En la fase de construcción se construye una hoja de ruta (gráfica), aproximando los movimientos que se pueden realizar en el entorno. Primero, se crea una configuración aleatoria. Luego, se conecta a algunos vecinos, normalmente los k vecinos más cercanos o todos los vecinos a menos de una distancia predeterminada. Las configuraciones y conexiones se agregan al gráfico hasta que la hoja de ruta sea lo suficientemente densa. En la fase de consulta, las configuraciones de inicio y meta están conectadas al gráfico, y la ruta se obtiene mediante una consulta de ruta más corta de Dijkstra .
Dadas ciertas condiciones relativamente débiles en la forma del espacio libre, PRM es probabilísticamente completo, lo que significa que a medida que el número de puntos muestreados aumenta sin límite, la probabilidad de que el algoritmo no encuentre un camino si existe uno se acerca a cero. La tasa de convergencia depende de ciertas propiedades de visibilidad del espacio libre, donde la visibilidad la determina el planificador local. Aproximadamente, si cada punto puede "ver" una gran fracción del espacio, y también si una gran fracción de cada subconjunto del espacio puede "ver" una gran fracción de su complemento, entonces el planificador encontrará una ruta rápidamente.
La invención del método PRM se atribuye a Lydia E. Kavraki . [2] [3] Existen muchas variantes del método PRM básico, algunas bastante sofisticadas, que varían la estrategia de muestreo y la estrategia de conexión para lograr un rendimiento más rápido. Véase, por ejemplo , Geraerts & Overmars (2002) [4] para una discusión.
