El planificador de hoja 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 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 con otras configuraciones cercanas. Se agregan las configuraciones inicial y final y se aplica un algoritmo de búsqueda de gráficos al gráfico resultante para determinar una ruta entre las configuraciones inicial y final.
El planificador de mapas de ruta probabilístico consta de dos fases: una fase de construcción y una fase de consulta. En la fase de construcción, se construye un mapa de ruta (gráfico), que aproxima 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 que se encuentran a menos de una distancia predeterminada. Se agregan configuraciones y conexiones al gráfico hasta que el mapa de ruta es lo suficientemente denso. En la fase de consulta, las configuraciones de inicio y de destino 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 en la forma del espacio libre, el PRM es demostrablemente 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 una ruta si existe una 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á 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.