D*

D* (izgovara se „D zvezda") je bilo koji od sledeća tri srodna inkrementaciona algoritma pretrage:

• Originalni D*, od A. Stentz, koji je upravo zasnovan na inkrementacionom algoritmu pretrage.
• Fokusirani D*, koji je zasnovan na inkrementacionom heuristički algoritau pretrage u kombinaciji sa idejama A* i originalnom D*. On rezultat za dalji razvoj originalnog D*.
• D* Lite, je inkrementacioni heuristički algoritam za pretragu, konstruisanog od strane S. Koenig and M. Likhachev izgrađenog na osovu LPA*, to je inkrementacioni heuristički algoritam za pretragu koji kombinuje ideje A* i dinamičkog SWSF-FP.

Sva tri algoritma pretrage zasnovane su na istim osnovnim pretpostavkama, a to je problem planiranja putanje, u kojoj robot mora da se kreće ka datom cilju čije su koordinate na nepoznatom terenu. On pravi pretpostavke o nepoznatom delu terena (npr. da na tom terenu ne postoje prepreke i sl.) i pronalazi najkraći put od svoje trenutne koordinate do koordinate cilja pod ovim pretpostavkama. Robot potom sledi put. Kada se posmatra nova mapa informacija, dodaju se i informacije o mapi i ako je potrebno, replaniranje novog najkraćeg puta od svojih trenutne koordinate. Algoritam ponavlja proces dok robot ne dostigne ciljne koordinate ili utvrdi da ciljne koordinate ne mogu biti postignute. Pri prelazu kroz nepoznat teren, nove prepreke mogu biti često otkrivene, tako da ovo replaniranje treba da bude brzo.

D* i njegove varijante su u širokoj upotrebi za mobilne robote kao i kod autonomnih vozila za navigaciju. Trenutni sistemi se obično zasniva na D* Lite.

D*

Originalni D* predstavio je Entoni Stenc 1994. D* Ime potiče od termina „Dinamičan A* ", jer se algoritam ponaša kao zvezda.

Operacije

Osnovne operacije D* su navedene u nastavku. Kao i Dijkstra algoritam i A*, i D* vodi listu čvorova koje treba proceniti, koja je poznata kao „otvorena lista“. Čvorovi su označene jednom od sledećih oznaka:

• NOV, što znači da se nikada nije stavljen na otvorenoj listi;
• OTVOREN, što znači da je trenutno na otvorenoj listi;
• ZATVOREN, što znači da više nije na otvorenoj listi;
• RAST, pokazuje da je njegovo cena veća nego kada je poslednje put bio u otvorenoj listi;
• OPADANjE, ukazuje da je njegovo cena msnja nego kada je poslednje put bio u otvorenoj listi;

Proširenje

Algoritam radi tako iterativno izabira čvor iz otvorene liste i označuje ga. Tada se propagira promene čvora da kod cve susedne čvorove i stavlja ih na otvorenoj listi. Ovaj proces se zove „ekspanzija“. Za razliku od A*, koji sledi put od početka do kraja, D* počinje pretraživanjem unazad od ciljnog čvora. Svaki takav čvor ima pokazivač unazad koji se odnosi na sledeći čvor koji vodi do cilja, a svaki čvor zna tačnu cenu na meti. Kada početni čvor sledeći koji treba bude „proširen“, to znači da je algoritam završen, a put do cilja može se naći jednostavno prateći pokazivače unazad.

Rukovanje preprekama

Kada se otkrije prepreka na putu kroz koji se želi preći, sve tačke koje su pogođene ponovo se postavljaju u otvorenoj listi, i njih ožnačavamo sa RAST. Pre toga tim čvorovima se povećava ceni, međutim, algoritam proverava svoje susede i ispituje da li može da smanji troškove na čvora. Ako ne, stsnje se s prenosi na sve potomke čvorova, odnosno, čvorovi koji imaju pokazivače na njega. Tada se čvorovi ocenjuju. Kada čvorovi označeni sa „RAST“ mogu biti redukovani, njihov bekpointer se ažurira i prelazu stanje „OPADANjA“. Ovi talasi podizanje i spuštanje su srce D*. Algoritam je samo radio na tačkama koje su pogođene promenama cene.

Još jedna prepreka

Ovog puta, prepreka se ne može zaobići tako elegantno. Nijedna tačka ne može da pronađe novi put preko komšija. Stoga, oni nastavljaju da propagiraju svoje povećanje cene. Samo izvan kanala se mogu naći tačke, koje mogu dovesti do odredišta putem održivog puta. Na taj način se dva niža talasa razvijaju, tako što se prošire do nedostupnih označenih tačka sa novim informacijama o rutama.

Fokusirani D*

Kao što samo ime sugeriše, sa fokusom D* je produžetak od D* koji koristi heuristike da se fokusira na propagira RAST i OPADANjE ka robotu. Na ovaj način, samo se važna stanja ažuriraju, na isti način na koji se izračunava cena u A* samo za neke od čvorov.

D* Lite

D* Lite se ne zasniva na originalni D* ili D* Fokusirani, ali primenjuje istu ponašanje. To je jednostavnije za razumevanje i može se realizovati u manjim brojem linija koda, zato se i naziv "D* Lite". Po pperformansama on je bolji od fokusiranog D*. D* Lite je zasnovana na doživotnom planiranju A*, koji je uveden od strane K. Lihačev nekoliko godina ranije.

Minimalna cena naspram tekućoj ceni

Za D*, važno je napraviti razliku između tekuće i minimalne cene. Prvo je važno u trenutku naplate, a drugi je kritičn jer se sortira otvorena lista. Funkcija koja daje minimalnu cenu je uvek ima najnižu cenu u trenutnoj tački, jer je to prvi ulazak u otvorenu listu za nju.

Spoljašnje veze

• Sven Koenig's web page
• Anthony Stentz's web page