D*

D* (pronunciado "D estrella") es uno de los siguientes tres algoritmos de búsqueda incremental: * El D* original,​ por Anthony Stentz, es un algoritmo de búsqueda incremental informada. * D* Enfocado​ es un algoritmo heurístico de búsqueda incremental informada creado por Anthony Stentz que combina ideas de A*​ y el D* original. D* Enfocado es el resultado de un desarrollo adicional de D* original. * D* Lite​ es un algoritmo heurístico de búsqueda incremental creado por Sven Koenig y Maxim Likhachev que se basa en LPA*,​ combina ideas de A* y Dynamic SWSF-FP.​ Los tres algoritmos de búsqueda resuelven los mismos problemas de planificación de ruta basada en la suposición, incluyendo la planificación con la suposición de espacio libre,​ donde un robot tiene que navegar hasta las coordenadas de un objetivo dado 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 la meta bajo estas suposiciones. El robot entonces sigue el camino. Cuando se observa nueva información del mapa (como obstáculos previamente desconocidos), se añade la información a su mapa y, si es necesario, planea el nuevo camino más corto a partir de sus coordenadas actuales a las coordenadas del objetivo determinado. Se repite el proceso hasta que llega a las coordenadas del objetivo o determina que no se puede llegar a las coordenadas del objetivo. Al atravesar terrenos desconocidos, nuevos obstáculos se pueden descubrir con frecuencia, por lo que esta nueva planificación tiene que ser rápida. Los algorítmos de búsqueda (heurística) incremental aceleran las búsquedas de secuencias de problemas de búsqueda similares mediante el uso de la experiencia con los problemas anteriores para acelerar la búsqueda de la actual. Suponiendo que las coordenadas del objetivo no cambian, los tres algoritmos de búsqueda son más eficientes que las reiteradas búsquedas A*. D* y sus variantes han sido ampliamente utilizados para robots móviles y navegación de vehículos autónomos. Los sistemas actuales se basan normalmente en D* Lite en lugar del D* original o D* Enfocado. De hecho, incluso el laboratorio de Stentz utiliza D* Lite en lugar de D* en algunas implementaciones.​ Tales sistemas de navegación incluyen un sistema prototipo probado en Marte en los astromóviles Opportunity y Spirit y en el sistema de navegación de la obra ganadora en el DARPA Urban Challenge, todos desarrollados en la Carnegie Mellon University. El D* original fue presentado por Anthony Stentz en 1994. El nombre de D* viene del término "Dynamic A*", ya que el algoritmo se comporta como A* excepto que los costos de los arcos pueden cambiar a medida que se ejecuta el algoritmo.