D* (se pronuncia "D estrella") es cualquiera de los siguientes tres algoritmos de búsqueda incremental relacionados :
Los tres algoritmos de búsqueda resuelven los mismos problemas de planificación de rutas basados en suposiciones, incluida la planificación con la suposición de espacio libre [7] , donde un robot tiene que navegar hacia coordenadas de destino dadas en un terreno desconocido. Hace suposiciones sobre la parte desconocida del terreno (por ejemplo: que no contiene obstáculos) y encuentra una ruta más corta desde sus coordenadas actuales hasta las coordenadas de destino bajo estas suposiciones. El robot luego sigue la ruta. Cuando observa nueva información del mapa (como obstáculos previamente desconocidos), agrega la información a su mapa y, si es necesario, vuelve a planificar una nueva ruta más corta desde sus coordenadas actuales hasta las coordenadas de destino dadas. Repite el proceso hasta que alcanza las coordenadas de destino o determina que no se pueden alcanzar las coordenadas de destino. Al atravesar un terreno desconocido, es posible que se descubran nuevos obstáculos con frecuencia, por lo que esta replanificació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 al usar la experiencia con los problemas anteriores para acelerar la búsqueda del problema actual. Suponiendo que las coordenadas del objetivo no cambian, los tres algoritmos de búsqueda son más eficientes que las búsquedas A* repetidas.
El D* y sus variantes se han utilizado ampliamente para la navegación de robots móviles y vehículos autónomos . Los sistemas actuales se basan típicamente en el D* Lite en lugar del D* original o Focused D*. De hecho, incluso el laboratorio de Stentz utiliza el D* Lite en lugar del D* en algunas implementaciones. [8] Dichos sistemas de navegación incluyen un sistema prototipo probado en los exploradores marcianos Opportunity y Spirit 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 "A* dinámico", [9] porque el algoritmo se comporta como A* excepto que los costos del arco pueden cambiar a medida que se ejecuta el algoritmo.
A continuación se describe el funcionamiento básico de D*.
Al igual que el algoritmo de Dijkstra y A*, D* mantiene una lista de nodos para evaluar, conocida como la "lista ABIERTA". Los nodos se marcan según su estado:
El algoritmo funciona seleccionando iterativamente un nodo de la lista ABIERTA y evaluándolo. Luego propaga los cambios del nodo a todos los nodos vecinos y los coloca en la lista ABIERTA. Este proceso de propagación se denomina "expansión". A diferencia del A* canónico, que sigue la ruta desde el principio hasta el final, D* comienza buscando hacia atrás desde el nodo objetivo. Esto significa que el algoritmo está calculando realmente la ruta óptima de A* para cada nodo de inicio posible. [10] Cada nodo expandido tiene un puntero hacia atrás 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á listo y la ruta hacia el objetivo se puede encontrar simplemente siguiendo los punteros hacia atrás.
Cuando se detecta una obstrucción a lo largo de la ruta prevista, todos los puntos afectados se colocan de nuevo en la lista ABIERTA, esta vez marcada como ELEVADA. Sin embargo, antes de que un nodo ELEVADO aumente su coste, el algoritmo comprueba a sus vecinos y examina si puede reducir el coste del nodo. Si no, el estado ELEVADO se propaga a todos los descendientes de los nodos, es decir, los nodos que tienen punteros hacia atrás que lo apuntan. A continuación, se evalúan estos nodos y se transmite el estado ELEVADO, formando una onda. Cuando se puede reducir un nodo ELEVADO, se actualiza su puntero hacia atrás y se transmite el estado INFERIOR a sus vecinos. Estas ondas de estados ELEVADO y INFERIOR son el corazón de D*.
En este punto, toda una serie de otros puntos ya no pueden ser "tocados" por las ondas, por lo que el algoritmo sólo ha funcionado en los puntos que se ven afectados por el cambio de coste.
Esta vez, el punto muerto no se puede sortear de forma tan elegante. Ninguno de los puntos puede encontrar una nueva ruta a través de un vecino hasta el destino. Por lo tanto, continúan propagando su aumento de costes. Solo se pueden encontrar puntos fuera del canal que puedan 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.
mientras ( ! openList . isEmpty ()) { punto = openList . getFirst (); expandir ( punto ); } void expand ( currentPoint ) { boolean isRaise = isRaise ( currentPoint ) ; double cost ; for each ( vecino en currentPoint.getNeighbors ( ) ) { if ( isRaise ) { if ( vecino.nextPoint == currentPoint ) { vecino.setNextPointAndUpdateCost ( currentPoint ) ; openList.add ( vecino ) ; } else { cost = vecino.calculateCostVia ( currentPoint ) ; if ( costo < vecino.getCost ( ) ) { currentPoint.setMinimumCostToCurrentCost ( ) ; openList.add ( currentPoint ) ; } } } else { cost = vecino.calculateCostVia ( currentPoint ) ; if ( costo < vecino.getCost ( ) ) { vecino.setNextPointAndUpdateCost ( currentPoint ) ; openList.add ( vecino ) ; } } } boolean isRaise ( punto ) { double costo ; si ( punto.getCurrentCost ( ) > punto.getMinimumCost ( ) ) { para cada ( vecino en punto.getNeighbors ( ) ) { costo = punto.calculateCostVia ( vecino ) ; si ( costo < punto.getCurrentCost ( ) ) { punto.setNextPointAndUpdateCost ( vecino ) ; } } } devuelve punto.getCurrentCost ( ) > punto.getMinimumCost ( ) ; } Como su nombre lo sugiere, 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 no se basa en el D* original ni en 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 como Focused D* o mejor. D* Lite se basa en Lifelong Planning A* , que fue introducido por Koenig y Likhachev unos años antes. D* Lite
Para D*, es importante distinguir entre los costos actuales y los 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 la OpenList.