Hoja de ruta probabilística

El planificador de mapa de ruta probabilístico ^{[ 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 de PRM consiste en muestrear aleatoriamente puntos del espacio de configuración del robot, comprobar si se encuentran en el espacio libre y utilizar un planificador local para intentar conectar estas configuraciones con otras cercanas. Se añaden las configuraciones inicial y final, y se aplica un algoritmo de búsqueda en grafos al grafo resultante para determinar una ruta entre ambas.

El planificador de rutas probabilístico consta de dos fases: una de construcción y otra de consulta. En la fase de construcción, se crea un mapa de rutas (grafo) que aproxima los movimientos posibles en el entorno. Primero, se genera una configuración aleatoria. Luego, se conecta con algunos vecinos, generalmente los k vecinos más cercanos o todos los vecinos a una distancia inferior a un valor predeterminado. Se añaden configuraciones y conexiones al grafo hasta que el mapa de rutas sea suficientemente denso. En la fase de consulta, las configuraciones de inicio y destino se conectan al grafo y se obtiene la ruta mediante el algoritmo de Dijkstra para encontrar el camino más corto .

Dadas ciertas condiciones relativamente débiles sobre la forma del espacio libre, se demuestra que PRM es probabilísticamente completo, lo que significa que, a medida que el número de puntos muestreados aumenta indefinidamente, la probabilidad de que el algoritmo encuentre un camino, si existe, se aproxima a uno. La tasa de convergencia depende de ciertas propiedades de visibilidad del espacio libre, donde la visibilidad la determina el planificador local. En términos generales, 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á un camino 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 y Overmars (2002) ^{[ 4 ]} para un análisis.