Esta página aún no se ha traducido para esta versión. Puede ver la versión más reciente de esta página en inglés.

Hojas de ruta probabilísticas (PRM)

Una hoja de ruta probabilística (PRM) es un gráfico de red de posibles rutas en un mapa determinado basado en espacios libres y ocupados. El objeto genera aleatoriamente nodos y crea conexiones entre estos nodos en función de los parámetros del algoritmo PRM.mobileRobotPRM Los nodos se conectan en función de las ubicaciones de obstáculoespecificadas en , y en el especificado .MapConnectionDistance Puede personalizar el número de nodos, , para ajustarse a la complejidad del mapa y el deseo de encontrar la ruta más eficiente.NumNodes El algoritmo PRM utiliza la red de nodos conectados para encontrar una ruta libre de obstáculos desde una ubicación inicial hasta una ubicación final. Para planificar una ruta de acceso a través de un entorno de forma eficaz, ajuste las propiedades y.NumNodesConnectionDistance

Al crear o actualizar la clase, las ubicaciones de nodo se generan aleatoriamente, lo que puede afectar a la ruta de acceso final entre varias iteraciones.mobileRobotPRM Esta selección de nodos se produce cuando se especifica inicialmente, se cambian los parámetros o se llama.Mapupdate Para obtener resultados coherentes con la misma ubicación de nodo, utilice para guardar el estado de la generación de números aleatorios.rng Vea un ejemplo usando .Sintonice la distancia de conexiónrng

Sintonice el número de nodos

Utilice la propiedad del objeto para ajustar el algoritmo. especifica el número de puntos, o nodos, colocados en el mapa, que el algoritmo utiliza para generar una hoja de ruta.NumNodesmobileRobotPRMNumNodes Utilizando la propiedad como umbral de distancia, el algoritmo conecta todos los puntos que no tienen obstáculos que bloquean la ruta directa entre ellos.ConnectionDistance

Aumentar el número de nodos puede aumentar la eficiencia de la ruta de acceso dando rutas más factibles. Sin embargo, el aumento de la complejidad aumenta el tiempo de cálculo. Para obtener una buena cobertura del mapa, es posible que necesite un gran número de nodos. Debido a la colocación aleatoria de nodos, es posible que algunas áreas del mapa no tengan suficientes nodos para conectarse al resto del mapa. En este ejemplo, se crea un número grande y pequeño de nodos en una hoja de ruta.

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

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

Cree una hoja de ruta sencilla 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 aumentan la complejidad, pero producen más opciones para mejorar la ruta de acceso. Dados estos dos mapas, puede calcular una ruta utilizando el algoritmo PRM y ver los efectos.

Calcular una ruta simple.

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

Calcular una ruta compleja.

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

Aumentar los nodos permite una ruta de acceso más directa, pero agrega más tiempo de cálculo para encontrar una ruta de acceso factible. Debido a la colocación aleatoria de puntos, la ruta no siempre es más directa o eficiente. El uso de un pequeño número de nodos puede empeorar las rutas de acceso de lo que se muestra e incluso restringir la capacidad de encontrar una ruta completa.

Sintonice la distancia de conexión

Utilice la propiedad del objeto para ajustar el algoritmo. es un umbral superior para los puntos que están conectados en la hoja de ruta.ConnectionDistancePRMConnectionDistance Cada nodo está conectado a todos los nodos dentro de esta distancia de conexión que no tienen obstáculos entre ellos. Al reducir la distancia de conexión, puede limitar el número de conexiones para reducir el tiempo de cálculo y simplificar el mapa. Sin embargo, una distancia reducida limita el número de caminos disponibles desde los que encontrar un camino completo sin obstáculos. Al trabajar con mapas simples, puede utilizar una distancia de conexión más alta con un pequeño número de nodos para aumentar la eficiencia. Para mapas complejos con muchos obstáculos, un mayor número de nodos con una distancia de conexión baja aumenta la posibilidad de encontrar una solución.

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

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

Cree una hoja de ruta con 100 nodos y calcule la ruta. El valor predeterminado se establece en inf.ConnectionDistance Guarde la configuración de generación de números aleatorios mediante la función rng. La configuración guardada le 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 números aleatorios para que PRM utilice los mismos nodos. De baja a 2 m.ConnectionDistance Mostrar la ruta calculada.

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

Crear o actualizar PRM

Cuando se utiliza el objeto y se modifican las propiedades, con cada nueva llamada de función, el objeto desencadena los puntos de hoja de ruta y las conexiones que se van a volver a calcular.mobileRobotPRM Dado que volver a calcular el mapa puede ser intensivo desde el punto de vista informático, puede reutilizar la misma hoja de ruta llamando a diferentes ubicaciones inicial y final.findpath

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

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

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

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

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

update(prm) show(prm)

El algoritmo PRM vuelve a calcular la ubicación del nodo 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

|