Hakualgoritmi D*

Hakualgoritmi D* (lausutaan "De Star" ) on mikä tahansa kolmesta toisiinsa liittyvästä lisähakualgoritmista :

• Anthony Stentzin alkuperäinen D*-algoritmi [1] on tietoinen inkrementaalinen hakualgoritmi.
• Focused D* [2]  on Anthony Stentzin kehittämä inkrementaalinen heuristinen hakualgoritmi, joka yhdistää A* :n [3] ja alkuperäisen D* :n ideat . Fokusoitu D* on alkuperäisen D* :n jatkokehitys .
• Lightweight D* [4]  on Sven Königin ja Maxim Likhachevin luoma inkrementaalinen heuristinen hakualgoritmi, joka perustuu LPA:han* [5] , inkrementaaliseen heuristiseen hakualgoritmiin, joka yhdistää A* -hakualgoritmin ja dynaamisen SWSF-FP :n ideat [6] . ] .

Kaikki kolme hakualgoritmia ratkaisevat samat polun suunnitteluoletukset , mukaan lukien suunnittelu vapaan tilan oletuksilla [7] , kun robotin on navigoitava annettuihin kohdekoordinaatteihin tuntemattomassa maastossa. Se tekee oletuksia maaston tuntemattomasta osasta (esimerkiksi, ettei sillä ole esteitä) ja löytää lyhimmän polun nykyisistä koordinaateistaan ​​kohteen koordinaatteihin näiden oletusten perusteella. Sitten robotti seuraa polkua. Kun se havaitsee kartalla uutta tietoa (esimerkiksi aiemmin tuntemattomia esteitä), se lisää nämä tiedot karttaansa ja tarvittaessa suunnittelee uudelleen uuden lyhimmän reitin nykyisistä koordinaateista annettuihin kohdekoordinaatteihin. Se toistaa prosessia, kunnes se saavuttaa kohdekoordinaatit tai määrittää, että kohdekoordinaatteja ei voida saavuttaa. Tuntematonta maastoa ylitettäessä voi usein havaita uusia esteitä, joten tämän uudelleensuunnittelun tulee olla nopeaa. Inkrementaaliset (heuristiset) hakualgoritmit nopeuttavat samankaltaisten hakuongelmien sekvenssien etsintää käyttämällä aikaisempien ongelmien ratkaisukokemusta nopeuttamaan nykyisen etsintää. Olettaen, että kohdekoordinaatit eivät muutu, kaikki kolme hakualgoritmia ovat tehokkaampia kuin toistuvat A* -haut .

D* :ta ja sen muunnelmia on käytetty laajalti mobiiliroboteissa ja autonomisissa navigointiajoneuvoissa . Nykyaikaiset järjestelmät perustuvat yleensä kevyeen painoon alkuperäisen tai kohdistetun D* sijaan . Itse asiassa jopa Stenzin laboratorio käyttää kevyttä alkuperäisen D* :n sijaan [8] joissakin toteutuksissa . Tällaisia ​​navigointijärjestelmiä ovat esimerkiksi Mars-kulkijoilla Opportunity ja Spirit testattu prototyyppijärjestelmä sekä DARPA Urban Challenge -voittajan navigointijärjestelmä , jotka molemmat kehitettiin Carnegie Mellonin yliopistossa .

Anthony Stentz esitteli alkuperäisen D* :n vuonna 1994 . Nimi D* tulee termistä " D dynamic A * " , koska algoritmi käyttäytyy kuten A * [2] , paitsi että kaaren hinta voi muuttua algoritmin suorituksen aikana .

Toiminnot

D* :n päätoiminnot on kuvattu alla.

Kuten Dijkstran algoritmi ja A* , D* ylläpitää arvioitavien solmujen luetteloa, joka tunnetaan nimellä OPEN-lista . Solmut on merkitty yhdeksi useista tiloista:

• UUSI tarkoittaa, että sitä ei ole koskaan asetettu OPEN-listalle .
• OPEN tarkoittaa, että se on tällä hetkellä OPEN- luettelossa .
• SULJETTU tarkoittaa, että se ei ole enää AVOIN-luettelossa .
• RAISED , osoittaa, että sen arvo on korkeampi kuin viimeksi, kun se oli OPEN-luettelossa .
• LOWER , osoittaa, että sen arvo on pienempi kuin viimeksi, kun se oli OPEN-listalla .

Laajennus

Algoritmi toimii iteratiivisesti valitsemalla solmun OPEN-luettelosta ja arvioimalla sen. Sitten se levittää solmun muutokset kaikkiin viereisiin solmuihin ja sijoittaa ne OPEN-luetteloon . Tätä jakeluprosessia kutsutaan "laajentamiseksi" . Toisin kuin kanoninen A* , joka seuraa polkua alusta loppuun, D* alkaa etsiä taaksepäin kohdesolmusta. Jokaisella laajennetulla solmulla on paluuosoitin, joka viittaa seuraavaan kohteeseen johtavaan solmuun, ja jokainen solmu tietää kohteen tarkan hinnan. Kun aloitussolmu on seuraava laajeneva solmu, algoritmi on valmis ja polku tavoitteeseen löytyy yksinkertaisesti seuraamalla backtickejä.

• Laajennus käynnissä. Loppusolmu (keltainen) on ylimmän pisterivin keskellä, aloitussolmu on alarivin keskellä. Punainen osoittaa estettä; musta/sininen tarkoittaa laajennettuja solmuja (kirkkaus tarkoittaa kustannuksia). Vihreä osoittaa solmuja, jotka laajenevat.

• Laajennus valmis. Polku näkyy sinisenä.

Esteiden voittaminen

Kun este löytyy annetulta polulta, kaikki pisteet, joihin vaikuttaa, sijoitetaan jälleen OPEN-listalle , tällä kertaa merkinnällä UP . Ennen kuin nostaa BOOSTER-solmun kustannuksia , algoritmi tarkistaa sen naapurit ja tutkii, voiko se vähentää solmun kustannuksia. Muussa tapauksessa UP -tila levitetään kaikille solmujen jälkeläisille eli solmuille, joilla on takaosoittimet. Nämä solmut arvioidaan sitten ja UP -tila lähetetään muodostaen aallon. Kun YLÖS-solmua voidaan pienentää, sen taustaosoitin päivitetään ja välittää DOWN -tilan naapureilleen. Nämä UP- ja DOWN -aallot ovat D* : n sydän .

Tässä vaiheessa aallot eivät voi koskettaa useita muita pisteitä. Siksi algoritmi toimi vain pisteillä, joihin arvon muutos vaikuttaa.

• Este lisätään (punainen) ja solmut merkitään UP (keltainen).

• Laajennus käynnissä. LIFT-merkityt solmut on merkitty keltaisella ja LOWER -merkityt solmut vihreällä .

Toinen umpikuja

Tällä kertaa umpikujasta on mahdotonta päästä eroon niin tyylikkäästi. Mikään pisteistä ei löydä uutta reittiä naapurin kautta määränpäähän. Joten he jatkavat arvostuksensa levittämistä. Voit löytää kanavan ulkopuolelta vain pisteitä, jotka voivat johtaa määränpäähän käyttökelpoista reittiä pitkin. Näin kehittyy kaksi BOTTOM -aaltoa, jotka laajenevat uusilla reittitiedoilla saavuttamattomiksi merkittyiksi pisteiksi.

• Kanava on estetty lisäesteillä (punainen).

• Laajennus käynnissä. RAISE- aalto (keltainen), LOWER- aalto (vihreä).

• Löytyi UUSI polku (sininen).

Pseudokoodi