D * (pronunciado "D estrella") es cualquiera de los siguientes tres algoritmos de búsqueda incremental relacionados :
- El D * original, [1] de Anthony Stentz, es un algoritmo de búsqueda incremental informado.
- Focused D * [2] es un algoritmo de búsqueda heurística incremental informado de Anthony Stentz que combina las ideas de A * [3] y la D * original. Focused D * fue el resultado de un mayor desarrollo del D * original.
- D * Lite [4] es un algoritmo de búsqueda heurística incremental de Sven Koenig y Maxim Likhachev que se basa en LPA * , [5] un algoritmo de búsqueda heurística incremental que combina ideas de A * y SWSF-FP dinámico. [6]
Los tres algoritmos de búsqueda resuelven los mismos problemas de planificación de ruta basados en suposiciones , incluida la planificación con la suposición de espacio libre, [7] donde un robot tiene que navegar hacia coordenadas de objetivo determinadas en un terreno desconocido. Hace suposiciones sobre la parte desconocida del terreno (por ejemplo: que no contiene obstáculos) y encuentra un camino más corto desde sus coordenadas actuales hasta las coordenadas objetivo bajo estas suposiciones. Luego, el robot sigue el camino. Cuando observa nueva información de mapa (como obstáculos previamente desconocidos), agrega la información a su mapa y, si es necesario, reemplaza una nueva ruta más corta desde sus coordenadas actuales hasta las coordenadas de objetivo dadas. Repite el proceso hasta que alcanza las coordenadas de la meta o determina que no se pueden alcanzar las coordenadas de la meta. Al atravesar un terreno desconocido, es posible que se descubran nuevos obstáculos con frecuencia, por lo que esta nueva planificación debe ser rápida. Los algoritmos de búsqueda incremental (heurística) aceleran las búsquedas de secuencias de problemas de búsqueda similares utilizando la experiencia con los problemas anteriores para acelerar la búsqueda del actual. Suponiendo que las coordenadas del objetivo no cambien, los tres algoritmos de búsqueda son más eficientes que las búsquedas A * repetidas.
D * y sus variantes se han utilizado ampliamente para robots móviles y navegación de vehículos autónomos . Los sistemas actuales se basan típicamente en D * Lite en lugar del D * o Focussed D * original. De hecho, incluso el laboratorio de Stentz usa D * Lite en lugar de D * en algunas implementaciones. [8] Dichos sistemas de navegación incluyen un sistema prototipo probado en los rovers Opportunity y Spirit de Marte y el sistema de navegación del ganador del DARPA Urban Challenge , ambos desarrollados en la Universidad Carnegie Mellon .
El D * original fue introducido por Anthony Stentz en 1994. El nombre D * proviene del término "Dynamic A *", [9] porque el algoritmo se comporta como A * excepto que los costos del arco pueden cambiar a medida que se ejecuta el algoritmo.
Operación
El funcionamiento básico de D * se describe a continuación.
Al igual que el algoritmo de Dijkstra y A *, D * mantiene una lista de nodos a evaluar, conocida como la "lista ABIERTA". Los nodos están marcados con uno de varios estados:
- NUEVO, lo que significa que nunca se ha colocado en la lista ABIERTA
- ABIERTO, lo que significa que actualmente está en la lista ABIERTO
- CERRADO, lo que significa que ya no está en la lista ABIERTA
- SUBIR, indicando que su costo es más alto que la última vez que estuvo en la lista ABIERTA
- MÁS BAJO, lo que indica que su costo es menor que la última vez que estuvo en la lista ABIERTA
Expansión
El algoritmo funciona seleccionando iterativamente un nodo de la lista OPEN y evaluándolo. Luego propaga los cambios del nodo a todos los nodos vecinos y los coloca en la lista OPEN. Este proceso de propagación se denomina "expansión". A diferencia de la canónica A *, que sigue el camino de principio a fin, D * comienza buscando hacia atrás desde el nodo objetivo. Cada nodo expandido tiene un indicador de retroceso que se refiere al siguiente nodo que conduce al objetivo, y cada nodo conoce el costo exacto para el objetivo. Cuando el nodo de inicio es el siguiente nodo que se va a expandir, el algoritmo está terminado y la ruta hacia el objetivo se puede encontrar simplemente siguiendo los puntos de retroceso.
Ampliación en curso. El nodo final (amarillo) está en el medio de la fila superior de puntos, el nodo inicial está en el medio de la fila inferior. El rojo indica un obstáculo; negro / azul indica nodos expandidos (el brillo indica el costo). El verde indica los nodos que se están expandiendo.
Expansión terminada. La ruta se indica en cian.
Manejo de obstáculos
Cuando se detecta una obstrucción a lo largo de la ruta prevista, todos los puntos afectados se colocan nuevamente en la lista ABIERTA, esta vez marcados como SUBIR. Sin embargo, antes de que un nodo RAISED aumente de costo, el algoritmo verifica a sus vecinos y examina si puede reducir el costo del nodo. De lo contrario, el estado RAISE se propaga a todos los descendientes de los nodos, es decir, a los nodos que tienen backpointers. Luego, estos nodos se evalúan y se transmite el estado RAISE, formando una onda. Cuando se puede reducir un nodo RAISED, su backpointer se actualiza y pasa el estado LOWER a sus vecinos. Estas ondas de estados SUBIR y BAJAR son el corazón de D *.
En este punto, toda una serie de otros puntos no pueden ser "tocados" por las olas. Por lo tanto, el algoritmo solo ha funcionado en los puntos que se ven afectados por el cambio de costo.
Se ha añadido un obstáculo (rojo) y los nodos marcados SUBIR (amarillo).
Ampliación en curso. El amarillo indica los nodos marcados como SUBIR, el verde indica los nodos marcados como BAJOS.
Ocurre otro punto muerto
Esta vez, el punto muerto no se puede sortear con tanta elegancia. Ninguno de los puntos puede encontrar una nueva ruta a través de un vecino al destino. Por lo tanto, continúan propagando su aumento de costos. Solo se pueden encontrar puntos fuera del canal, que pueden llevar al destino a través de una ruta viable. Así es como se desarrollan dos ondas inferiores, que se expanden como puntos marcados como inalcanzables con nueva información de ruta.
Canal bloqueado por obstáculos adicionales (rojo)
Expansión en curso (Subir onda en amarillo, Bajar onda en verde)
Nueva ruta encontrada (cian)
Pseudocódigo
while ( ! openList . isEmpty ()) { point = openList . getFirst (); expandir ( señalar ); }
Expandir
void expand ( currentPoint ) { boolean isRaise = isRaise ( currentPoint ); doble costo ; para cada ( vecino en currentPoint . getNeighbors ()) { if ( isRaise ) { if ( vecino . nextPoint == currentPoint ) { vecino . setNextPointAndUpdateCost ( currentPoint ); openList . agregar ( vecino ); } else { costo = vecino . calcularCostVia ( currentPoint ); if ( costo < vecino . getCost ()) { currentPoint . setMinimumCostToCurrentCost (); openList . agregar ( currentPoint ); } } } else { costo = vecino . calcularCostVia ( currentPoint ); if ( costo < vecino . getCost ()) { vecino . setNextPointAndUpdateCost ( currentPoint ); openList . agregar ( vecino ); } } } }
Verificar aumento
booleano isRaise ( punto ) { costo doble ; if ( point . getCurrentCost () > point . getMinimumCost ()) { para cada ( vecino en el punto . getNeighbors ()) { costo = punto . calcularCostVia ( vecino ); if ( costo < punto . getCurrentCost ()) { punto . setNextPointAndUpdateCost ( vecino ); } } } punto de retorno . getCurrentCost () > punto . getMinimumCost (); }
Variantes
Enfocado D *
Como sugiere su nombre, Focused D * es una extensión de D * que utiliza una heurística para enfocar la propagación de RAISE y LOWER hacia el robot. De esta manera, solo se actualizan los estados que importan, de la misma manera que A * solo calcula los costos para algunos de los nodos.
D * Lite
D * Lite no se basa en el D * original o Focused D *, pero implementa el mismo comportamiento. Es más sencillo de entender y se puede implementar en menos líneas de código, de ahí el nombre "D * Lite". En cuanto al rendimiento, es tan bueno o mejor que Focused D *. D * Lite se basa en Lifelong Planning A * , que fue introducido por Koenig y Likhachev unos años antes. D * Lite
Costo mínimo versus costo actual
Para D *, es importante distinguir entre costos actuales y mínimos. El primero solo es importante en el momento de la recopilación y el segundo es fundamental porque ordena la OpenList. La función que devuelve el costo mínimo es siempre el costo más bajo hasta el punto actual, ya que es la primera entrada de OpenList.
Referencias
- ^ Stentz, Anthony (1994), "Planificación de ruta óptima y eficiente para entornos parcialmente conocidos", Actas de la Conferencia internacional sobre robótica y automatización : 3310–3317, CiteSeerX 10.1.1.15.3683
- ^ Stentz, Anthony (1995), "The Focussed D * Algorithm for Real-Time Replanning", Actas de la Conferencia conjunta internacional sobre inteligencia artificial : 1652-1659, CiteSeerX 10.1.1.41.8257
- ^ Hart, P .; Nilsson, N .; Raphael, B. (1968), "Una base formal para la determinación heurística de rutas de costo mínimo", IEEE Trans. Syst. Ciencia y cibernética , SSC-4 (2): 100–107, doi : 10.1109 / TSSC.1968.300136
- ^ Koenig, S .; Likhachev, M. (2005), "Replanificación rápida para la navegación en terreno desconocido", Transacciones en robótica , 21 (3): 354–363, CiteSeerX 10.1.1.65.5979 , doi : 10.1109 / tro.2004.838026
- ^ Koenig, S .; Likhachev, M .; Furcy, D. (2004), "Lifelong Planning A *", Inteligencia artificial , 155 (1-2): 93-146, doi : 10.1016 / j.artint.2003.12.001
- ^ Ramalingam, G .; Reps, T. (1996), "Un algoritmo incremental para una generalización del problema de la ruta más corta", Journal of Algorithms , 21 (2): 267–305, CiteSeerX 10.1.1.3.7926 , doi : 10.1006 / jagm.1996.0046
- ^ Koenig, S .; Smirnov, Y .; Tovey, C. (2003), "Performance Bounds for Planning in Unknown Terrain", Inteligencia artificial , 147 (1-2): 253-279, doi : 10.1016 / s0004-3702 (03) 00062-6
- ^ Madera, D. (2006). Planificación de rutas basada en gráficos para robots móviles (tesis). Instituto de Tecnología de Georgia.
- ^ Stentz, Anthony (1995), "The Focussed D * Algorithm for Real-Time Replanning", Actas de la Conferencia conjunta internacional sobre inteligencia artificial : 1652-1659, CiteSeerX 10.1.1.41.8257
enlaces externos
- Página web de Sven Koenig
- Página web de Anthony Stentz