Algoritm de căutare D*

Algoritmul de căutare D* (pronunțat „De Star” ) este oricare dintre cei trei algoritmi de căutare incrementală înrudiți :

• Algoritmul original D* [1] de Anthony Stentz este un algoritm informat de căutare incrementală.
• Focused D* [2]  este un algoritm de căutare euristic incremental dezvoltat de Anthony Stentz care combină ideile lui A* [3] și originalul D* . Focused D* este o dezvoltare ulterioară a originalului D* .
• Lightweight D* [4]  este un algoritm de căutare euristic incremental creat de Sven König și Maxim Likhachev care se bazează pe LPA* [5] , un algoritm de căutare euristic incremental care combină ideile din algoritmul de căutare A* și SWSF-FP dinamic [6] ] .

Toți cei trei algoritmi de căutare rezolvă aceleași probleme de planificare a traseului , inclusiv planificarea cu ipoteze de spațiu liber [7] când robotul trebuie să navigheze la coordonatele țintei date pe un teren necunoscut. Face ipoteze despre o parte necunoscută a terenului (de exemplu, că nu există obstacole pe acesta) și găsește calea cea mai scurtă de la coordonatele sale curente la coordonatele țintei în aceste ipoteze. Robotul urmează apoi calea. Când observă informații noi pe hartă (de exemplu, obstacole necunoscute anterior), adaugă aceste informații pe harta sa și, dacă este necesar, replanifică o nouă cale cea mai scurtă de la coordonatele curente la coordonatele țintă date. Se repetă procesul până când atinge coordonatele țintă sau determină că coordonatele țintă nu pot fi atinse. Când traversați un teren necunoscut, pot fi adesea descoperite noi obstacole, așa că această replanificare trebuie să fie rapidă. Algoritmii de căutare incrementali (euristici) accelerează căutarea unor secvențe de probleme de căutare similare, folosind experiența rezolvării problemelor anterioare pentru a accelera căutarea celei curente. Presupunând că coordonatele țintă nu se modifică, toți cei trei algoritmi de căutare sunt mai eficienți decât căutările A* repetate .

D* și variantele sale au fost utilizate pe scară largă pentru robotul mobil și vehiculul de navigație autonom . Sistemele moderne se bazează, de obicei, pe D* ușor , mai degrabă decât pe originalul sau concentrat . De fapt, chiar și laboratorul lui Stenz folosește un D* [8] ușor mai degrabă decât originalul în unele implementări . Astfel de sisteme de navigație includ sistemul prototip testat pe roverele Marte Opportunity și Spirit și sistemul de navigație al câștigătorului DARPA Urban Challenge , ambele dezvoltate la Universitatea Carnegie Mellon .

Originalul D* a fost introdus în 1994 de Anthony Stentz . Numele D* provine de la termenul „ D ynamic A* ” deoarece algoritmul se comportă ca A * [2] , cu excepția faptului că costul arcului se poate modifica pe măsură ce algoritmul rulează .

Operațiuni

Principalele operațiuni ale lui D* sunt descrise mai jos.

La fel ca algoritmul lui Dijkstra și A* , D* menține o listă de noduri de evaluat, cunoscută sub numele de listă OPEN . Nodurile sunt marcate ca având una dintre mai multe stări:

• NOU înseamnă că nu a fost niciodată plasat pe lista DESCHIS .
• OPEN înseamnă că se află în prezent pe lista DESCHIS .
• ÎNCHIS înseamnă că nu mai este pe lista DESCHIS .
• RAISED , indică faptul că valoarea sa este mai mare decât ultima dată când a fost pe lista OPEN .
• LOWER , indică faptul că valoarea sa este mai mică decât ultima dată când a fost pe lista OPEN .

Extensie

Algoritmul funcționează prin selectarea iterativă a unui nod dintr-o listă DESCHISĂ și evaluarea acestuia. Apoi propagă modificările nodului către toate nodurile învecinate și le plasează în lista OPEN . Acest proces de distribuție se numește „expansiune” . Spre deosebire de A* canonic , care urmează o cale de la început până la sfârșit, D* începe să caute înapoi de la nodul țintă. Fiecare nod extins are un indicator înapoi care se referă la următorul nod care duce la țintă și fiecare nod știe costul exact pentru țintă. Când nodul de pornire este următorul nod care se extinde, algoritmul este terminat și calea către obiectiv poate fi găsită prin simpla urmărire a backtick-urilor.

• Extindere în curs. Nodul final (galben) se află în mijlocul rândului de sus de puncte, nodul de început este în mijlocul rândului de jos. Roșul indică un obstacol; negru/albastru denotă noduri extinse (luminozitatea denotă cost). Verdele indică nodurile care se extind.

• Extensia finalizată. Calea este afișată cu albastru.

Depășirea obstacolelor

Când se găsește un obstacol pe calea dată, toate punctele afectate sunt din nou plasate pe lista DESCHIS , de data aceasta marcată SUS . Cu toate acestea, înainte de a crește costul unui nod BOOSTER , algoritmul își verifică vecinii și examinează dacă poate reduce costul nodului. În caz contrar, starea UP este propagată către toți descendenții nodurilor, adică nodurilor care au backpointeri. Aceste noduri sunt apoi evaluate și starea UP este transmisă, formând o undă. Când un nod UP poate fi redus, backpointer-ul său este actualizat și transmite starea DOWN vecinilor săi. Aceste unde SUS și JOS sunt inima lui D* .

Până în acest moment, undele nu pot atinge un număr de alte puncte. Prin urmare, algoritmul a funcționat numai cu punctele care sunt afectate de o modificare a valorii.

• Obstacolul este adăugat (roșu) și nodurile sunt marcate ca SUS (galben).

• Extindere în curs. Nodurile marcate ca LIFT sunt marcate cu galben, nodurile marcate ca LOWER sunt marcate cu verde .

Un alt punct mort

De data aceasta este imposibil să ieși din impas atât de elegant. Niciunul dintre puncte nu poate găsi un nou traseu prin vecin până la destinație. Așa că continuă să-și propage aprecierea. Puteți găsi doar puncte în afara canalului care pot duce la o destinație de-a lungul unui traseu viabil. Așa se dezvoltă două valuri BOTTOM , care se extind în puncte marcate ca inaccesibile cu noi informații despre rută.

• Canalul este blocat de obstacole suplimentare (roșu).

• Extindere în curs. RAISE val (galben), LOWER wave (verde).

• Am găsit o cale NOUĂ (albastru).

Pseudocod