Søgealgoritmen D* (udtales "De Star" ) er en af tre relaterede inkrementelle søgealgoritmer :
Alle tre søgealgoritmer løser de samme sti-planlægningsantagelser problemer, herunder planlægning med frirumsantagelser [7] , når robotten skal navigere til givne målkoordinater i ukendt terræn. Den gør antagelser om en ukendt del af terrænet (f.eks. at der ikke er nogen forhindringer på den) og finder den korteste vej fra sine nuværende koordinater til målets koordinater under disse antagelser. Robotten følger derefter stien. Når den observerer ny information på kortet (for eksempel hidtil ukendte forhindringer), tilføjer den denne information til sit kort og om nødvendigt planlægger den en ny korteste vej fra de aktuelle koordinater til de givne målkoordinater. Den gentager processen, indtil den når målkoordinaterne eller bestemmer, at målkoordinaterne ikke kan nås. Ved krydsning af ukendt terræn kan der ofte opdages nye forhindringer, så denne omplanlægning skal være hurtig. Inkrementelle (heuristiske) søgealgoritmer fremskynder søgningen efter sekvenser af lignende søgeproblemer ved at bruge erfaringen med at løse tidligere problemer til at fremskynde søgningen efter den aktuelle. Forudsat at målkoordinaterne ikke ændres, er alle tre søgealgoritmer mere effektive end gentagne A* -søgninger .
D* og dens varianter er blevet meget brugt til mobile robotter og autonome navigationskøretøjer . Moderne systemer er normalt baseret på den lette , snarere end den originale eller fokuserede D* . Faktisk bruger selv Stenz's laboratorium en letvægts snarere end den originale D* [8] i nogle implementeringer . Sådanne navigationssystemer omfatter prototypesystemet, der er testet på Mars-roverne Opportunity og Spirit , og navigationssystemet fra vinderen af DARPA Urban Challenge , begge udviklet ved Carnegie Mellon University .
Den originale D* blev introduceret i 1994 af Anthony Stentz . Navnet D* kommer fra udtrykket " Dynamic A * " , fordi algoritmen opfører sig som A * [2] , bortset fra at bueomkostningerne kan ændre sig , efterhånden som algoritmen kører .
De vigtigste funktioner for D* er beskrevet nedenfor.
Ligesom Dijkstras algoritme og A * vedligeholder D* en liste over noder, der skal evalueres, kendt som OPEN-listen . Noder er markeret som havende en af flere tilstande:
Algoritmen fungerer ved iterativt at vælge en node fra en OPEN-liste og evaluere den. Den udbreder derefter nodens ændringer til alle tilstødende noder og placerer dem på OPEN-listen . Denne distributionsproces kaldes "udvidelse" . I modsætning til den kanoniske A* , som følger en sti fra start til slut, begynder D* at søge baglæns fra målknuden. Hver udvidet knude har en tilbagemarkør, der refererer til den næste knude, der fører til målet, og hver knude kender den nøjagtige pris for målet. Når startknuden er den næste knude, der udvides, er algoritmen færdig, og stien til målet kan findes ved blot at følge backticks.
Udvidelse i gang. Afslutningsknuden (gul) er i midten af den øverste række af prikker, startnoden er i midten af den nederste række. Rød angiver en forhindring; sort/blå angiver udvidede noder (lysstyrke angiver omkostninger). Grøn angiver noder, der udvider sig.
Udvidelse gennemført. Stien er vist med blåt.
Når en forhindring findes på den givne sti, placeres alle berørte punkter igen på OPEN-listen , denne gang markeret OP . Inden prisen på en BOOSTER-knude øges , tjekker algoritmen dog sine naboer og undersøger, om den kan reducere omkostningerne ved knudepunktet. Ellers spredes UP -tilstanden til alle efterkommere af noder, det vil sige noder, der har backpointere. Disse noder evalueres derefter, og UP -tilstanden transmitteres og danner en bølge. Når en OP-knude kan reduceres, opdateres dens backpointer og videregiver NED -tilstanden til dens naboer. Disse OP- og NED -bølger er hjertet af D* .
På dette tidspunkt kan bølgerne ikke røre en række andre punkter. Derfor fungerede algoritmen kun med punkter, der er påvirket af en værdiændring.
Forhindringen tilføjes (rød), og noderne er markeret som OP (gul).
Udvidelse i gang. Noderne markeret som LIFT er markeret med gult, noderne markeret som LOWER er markeret med grønt .
Denne gang er det umuligt at bryde dødvandet så elegant. Ingen af punkterne kan finde en ny rute gennem naboen til destinationen. Så de bliver ved med at udbrede deres påskønnelse. Du kan kun finde punkter uden for kanalen, der kan føre til en destination langs en levedygtig rute. Sådan udvikler sig to BUNDbølger , som udvider sig til punkter, der er markeret som utilgængelige med ny ruteinformation.
Kanalen er blokeret af yderligere forhindringer (rød).
Udvidelse i gang. HØJ bølge (gul), NEDR bølge (grøn).
Fandt en NY sti (blå).
Som navnet antyder, er fokuseret D* en forlængelse af D* , der bruger en heuristik til at fokusere udbredelsen af OP og NED i retning af robotten. Det er således kun vigtige tilstande, der opdateres, ligesom A* kun beregner omkostninger for nogle noder.
Letvægts D* er ikke baseret på original eller fokuseret D* , men implementerer den samme adfærd. Det er nemmere at forstå og kan gøres på færre linjer kode, deraf navnet Lightweight D* . Den fungerer lige så godt som fokuseret D* . Lightweight D* er baseret på LPA* [5] , som blev introduceret af König og Likhachev et par år tidligere. Lys D*
Det er vigtigt for D* at skelne mellem nuværende og minimumsomkostninger. Førstnævnte er kun vigtige under indsamling, mens sidstnævnte er afgørende, fordi de sorterer OPEN-listen . Funktionen, der returnerer minimumsomkostningerne, er altid den laveste omkostning for det aktuelle punkt, da det er den første post i OPEN-listen .
| Algoritmer til grafsøgning | ||
|---|---|---|
| Uoplyste metoder | ||
| Informerede metoder | ||
| Genveje | ||
| Minimumspændende træ | ||
| Andet | ||