D*

D* (pronunciat "D estrela") és un dels següents tres algoritmes de busca incremental:

• El D* original, per Anthony Stentz, és un algoritme de busca incremental informada.
• D* Enfocat és un algoritme heurístic de busca incremental informada creat per Anthony Stentz que combina idees d'A* i el D* original. D* Enfocat és el resultat d'un desenroll adicional de D* original.
• D* Lite és un algoritme heurístic de busca incremental creat per Sven Koenig i Maxim Likhachev que es basa en LPA*, combina idees d'A* i Dynamic SWSF-FP.

Els tres algoritmes de busca resolen els mateixos problemes de planificació de ruta basada en la suposició, incloent la planificació en la suposició d'espai lliure, a on un robot té que navegar fins a les coordenades d'un objectiu donat en un terreny desconegut. Fa suposicions sobre la part desconeguda del terreny (per eixemple: que no conté obstàculs) i troba un camí més curt des de les seues coordenades actuals fins a la meta baix estes suposicions. El robot llavors seguix el camí. Quan s'observa nova informació del mapa (com a obstàculs prèviament desconeguts), s'afig l'informació al seu mapa i, si és necessari, planeja el nou camí més curt a partir de les seues coordenades actuals a les coordenades de l'objectiu determinat. Es repetix el procés fins que aplega a les coordenades de l'objectiu o determina que no es pot aplegar a les coordenades de l'objectiu. En travessar terrenys desconeguts, nous obstàculs es poden descobrir en freqüència, per lo que esta nova planificació té que ser ràpida. Els algorítmos de busca (heurística) incremental acceleren les busques de seqüències de problemes de busca similars per mig de l'us de l'experiència en els problemes anteriors per a accelerar la busca de l'actual. Suponent que les coordenades de l'objectiu no canvien, els tres algoritmes de busca són més eficients que les reiterades busques A*.

D* i les seues variants han segut àmpliament utilisats per a robots mòvils i navegació de vehículs autònoms. Els sistemes actuals es basen normalment en D* Lite en lloc del D* original o D* Enfocat. De fet, inclús el laboratori de Stentz utilisa D* Lite en lloc de D* en algunes implementacions. Tals sistemes de navegació inclouen un sistema prototip provat en Mart en els astromóviles Opportunity i Spirit i en el sistema de navegació de l'obra guanyadora en el DARPA Urban Challenge, tots desenrollats en la Carnegie Mellon University.

El D* original va ser presentat per Anthony Stentz en 1994. El nom de D* ve del terme "Dynamic A*", ya que l'algoritme es comporta com A* excepto que els costs dels arcs poden canviar a mida que s'eixecuta l'algoritme.

Funcionament

El funcionament bàsic de D* es descriu a continuació.

De la mateixa manera que l'algoritme de Dijkstra i A*, D* manté una llista de nodos per a ser evaluats, coneguda com la "llista oberta". Els nodos estan marcats per tindre un de varis estats:

• NUEVO, lo que significa que mai ha segut colocat en la llista oberta
• ABIERTO, lo que significa que es troba actualment en la llista oberta
• CERRADO, lo que significa que ya no està en la llista oberta
• SUPERIOR, indicant el seu cost és més alt que l'última volta que estava en la llista oberta
• INFERIOR, indicant el seu cost és menor que l'última volta que estava en la llista oberta

Expansió

L'algoritme funciona per mig de la selecció iterativa d'un nodo de la llista oberta i evaluant-ho. A continuació, propaga els canvis del nodo a tots els nodos veïns i els coloca en la llista oberta. Este procés de propagació es denomina "expansió". A diferència de A*, que seguix el camí de principi a fi, D* comença per buscar cap a arrere des del nodo objectiu. Cada nodo expandit té un backpointer que es referix al següent nodo que conduïx a l'objectiu, i cada nodo coneix el cost exacte a l'objectiu. Quan el nodo de partida és el següent nodo a expandir-se, l'algoritme per a, i el camí cap a la meta es pot trobar, simplement seguint els backpointers.

Maneig d'obstàculs

Quan es detecta una obstrucció a lo llarc de la trayectòria prevista, tots els punts que es veuen afectats es coloquen de nou en la llista oberta, esta volta marcats a SUPERIOR. Abans de marcar-los a SUPERIOR s'aumenta els costs, no obstant, l'algoritme comprova els seus veïns i examina si es pot reduir el cost del nodo. Si no, l'estat SUPERIOR es propaga a tots els descendents dels nodos, és dir, els nodos que tenen backpointers a ella. Estos nodos s'evaluen llavors, i l'estat SUPERIOR es transmet, formant una ona. Quan un nodo SUPERIOR es pot reduir, el seu backpointer s'actualisa i pansa a l'estat LOWER als seus veïns. Estes ones d'estats SUPERIOR i LOWER són el cor de D*.

En este moment, s'evita que una série d'atres punts siguen "tocats" per les ones. L'algoritme, per tant, solament ha treballat en els punts que es veuen afectats pel canvi dels costs.

Ocurrència d'algun deadlock

Esta volta, el deadlock no pot anular-se en tanta elegància. Des de cap dels punts es pot trobar una nova ruta a través d'un veí per al destí, per lo tant, ells seguixen propagant el seu aument de costs. Solament fora del canal es poden trobar punts, que poden dur al destí a través d'una ruta viable. Açò tracta de cóm es desenrollen dos ones LOWER, que expandixen punts marcats inalcançables en nova informació de la ruta.

D* Enfocat

Com el seu nom indica, D* Enfocat és una extensió de D* que utilisa una heurística per a enfocar la propagació de SUPERIOR i INFERIOR cap al robot. D'esta manera, solament els estats que importen són actualisats, de la mateixa manera que A* solament calcula els costs per a alguns dels nodos.