El planificador de hoja de ruta probabilística [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 utilizar un planificador local para intentar conectar estas configuraciones con otras configuraciones cercanas. Se agregan las configuraciones inicial y meta, y se aplica un algoritmo de búsqueda de gráficos al gráfico resultante para determinar una ruta entre las configuraciones inicial y meta.
El planificador de hoja de ruta probabilística 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áfico), 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. Se agregan configuraciones y conexiones al gráfico hasta que la hoja de ruta sea lo suficientemente densa. En la fase de consulta, las configuraciones de inicio y objetivo se conectan al gráfico y la ruta se obtiene mediante una consulta de ruta más corta de Dijkstra .
Dadas ciertas condiciones relativamente débiles sobre la forma del espacio libre, PRM es probablemente 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 está determinada por 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á 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 & Overmars (2002) [4] para una discusión.