La traducción de esta página aún no se ha actualizado a la versión más reciente. Haga clic aquí para ver la última versión en inglés.

Hojas de ruta probabilísticas (PRM)

Una hoja de ruta probabilística (PRM) es una gráfica de red de posibles rutas en un mapa determinado basada en los espacios libres y ocupados. El objeto mobileRobotPRM genera nodos aleatoriamente y crea conexiones entre ellos basándose en los parámetros del algoritmo PRM. Los nodos se conectan basándose en las ubicaciones de los obstáculos que se han especificado en Map y en el valor de ConnectionDistance especificado. Puede personalizar el número de nodos, NumNodes, para adaptarlo a la complejidad del mapa y para encontrar la ruta más eficiente. El algoritmo PRM utiliza la red de nodos conectados para encontrar una ruta libre de obstáculos desde una ubicación inicial hasta una final. Para planificar una ruta por un entorno de forma efectiva, ajuste las propiedades NumNodes y ConnectionDistance.

Cuando se crea o actualiza la clase mobileRobotPRM, las ubicaciones de los nodos se generan aleatoriamente, lo que puede afectar a la ruta final entre múltiples iteraciones. Esta selección de nodos se produce solo cuando se especifica Map al inicio, se cambian los parámetros o se llama a update. Para obtener resultados uniformes con la misma asignación de nodos, use rng para guardar el estado de la generación aleatoria de números. Consulte Adaptar la distancia de conexión para ver un ejemplo de uso de rng.

Adaptar el número de nodos

Use la propiedad NumNodes del objeto mobileRobotPRM para ajustar el algoritmo. NumNodes especifica el número de puntos, o nodos, situados en el mapa, que el algoritmo utiliza para generar una hoja de ruta. Si se usa la propiedad ConnectionDistance como umbral de la distancia, el algoritmo conecta todos los puntos que no tienen obstáculos que bloqueen la ruta directa entre ellos.

Incrementar el número de nodos puede aumentar la eficiencia de la ruta proporcionando rutas más factibles. No obstante, mayor complejidad implica mayor tiempo de cálculo. Para obtener una buena cobertura del mapa, puede ser necesario un gran número de nodos. Debido a la colocación aleatoria de los nodos, es posible que en algunas zonas del mapa no haya suficientes nodos para conectar con el resto del mapa. En este ejemplo, se crea un número de nodos grande y pequeño en una hoja de ruta.

Cargue un archivo de mapa como matriz lógica, simpleMaps, y cree una cuadrícula de ocupación.

load exampleMaps.mat
map = binaryOccupancyMap(simpleMap,2);

Cree una hoja de ruta simple con 50 nodos.

prmSimple = mobileRobotPRM(map,50);
show(prmSimple)

Cree una hoja de ruta densa con 250 nodos.

prmComplex = mobileRobotPRM(map,250);
show(prmComplex)

Los nodos adicionales incrementan la complejidad, pero ofrecen más opciones para mejorar la ruta. Basándose en estos dos mapas, puede calcular una ruta utilizando el algoritmo PRM y ver los efectos.

Calcule una ruta simple.

startLocation = [2 1];
endLocation = [12 10];
path = findpath(prmSimple,startLocation,endLocation);
show(prmSimple)

Calcule una ruta compleja.

path = findpath(prmComplex, startLocation, endLocation);
show(prmComplex)

Incrementar los nodos permite obtener una ruta más directa, pero encontrar una ruta factible toma más tiempo de cálculo. Debido a la colocación aleatoria de los puntos, la ruta no es siempre más directa o eficiente. Usar una pequeña cantidad de nodos puede hacer que las rutas sean peores que las ilustradas e incluso restringir la capacidad de encontrar una ruta completa.

Adaptar la distancia de conexión

Use la propiedad ConnectionDistance del objeto PRM para adaptar el algoritmo. ConnectionDistance es un umbral superior para los puntos que están conectados en la hoja de ruta. Cada nodo está conectado con todos los nodos dentro de esta distancia de conexión cuando no hay obstáculos entre ellos. Puede limitar el número de conexiones disminuyendo la distancia de conexión para reducir el tiempo de cálculo y simplificar el mapa. Sin embargo, una distancia menor limita el número de rutas disponibles entre las cuales debe encontrarse una ruta completa libre de obstáculos. Si trabaja con mapas simples, puede utilizar una distancia de conexión mayor con una pequeña cantidad de nodos para aumentar la eficiencia. Para los mapas complejos con muchos obstáculos, una mayor cantidad de nodos con una distancia de conexión menor aumenta las posibilidades de encontrar una solución.

Cargue un mapa como una matriz lógica, simpleMap, y cree una cuadrícula de ocupación.

load exampleMaps.mat
map = binaryOccupancyMap(simpleMap,2);

Cree una hoja de ruta con 100 nodos y calcule la ruta. El valor predeterminado de ConnectionDistance está establecido en inf. Guarde la configuración de generación de un número aleatorio utilizando la función rng. La configuración guardada permite reproducir los mismos puntos y ver el efecto de cambiar ConnectionDistance.

rngState = rng;
prm = mobileRobotPRM(map,100);
startLocation = [2 1];
endLocation = [12 10];
path = findpath(prm,startLocation,endLocation);
show(prm)

Vuelva a cargar la configuración de generación de un número aleatorio para que PRM use los mismos nodos. Disminuya ConnectionDistance a 2 m. Muestre la ruta calculada.

rng(rngState);
prm.ConnectionDistance = 2;
path = findpath(prm,startLocation,endLocation);
show(prm)

Crear o actualizar PRM

Al utilizar el objeto mobileRobotPRM y modificar las propiedades, con cada nueva llamada de función, el objeto activa los puntos y las conexiones de la hoja de ruta que se desean recalcular. Dado que recalcular el mapa puede ser una tarea con alta carga computacional, puede reutilizar la misma hoja de ruta llamando a findpath con diferentes ubicaciones de inicio y de fin.

Cargue el mapa, simpleMap, desde un archivo .mat como una matriz lógica y cree una cuadrícula de ocupación.

load('exampleMaps.mat')
map = binaryOccupancyMap(simpleMap,2);

Cree una hoja de ruta. Sus nodos y conexiones pueden tener un aspecto diferente, debido a la colocación aleatoria de los nodos.

prm = mobileRobotPRM(map,100);
show(prm)

Llame update o cambie un parámetro para actualizar los nodos y las conexiones.

update(prm)
show(prm)

El algoritmo PRM recalcula la colocación de los nodos y genera una nueva red de nodos.

Referencias

[1] Kavraki, L.E., P. Svestka, J.-C. Latombe, and M.H. Overmars. "Probabilistic roadmaps for path planning in high-dimensional configuration spaces," IEEE Transactions on Robotics and Automation. Vol. 12, No. 4, Aug 1996 pp. 566—580.

Consulte también

mobileRobotPRM | findpath