Keresési algoritmus D*

A D* keresési algoritmus (ejtsd: "De Star" ) a három kapcsolódó növekményes keresési algoritmus bármelyike :

• Anthony Stentz eredeti D* algoritmusa [1] egy tájékozott növekményes keresési algoritmus.
• A Focused D* [2]  egy növekményes heurisztikus keresési algoritmus, amelyet Anthony Stentz fejlesztett ki, amely egyesíti az A* [3] és az eredeti D* ötleteit . A fókuszált D* az eredeti D* továbbfejlesztése .
• A Lightweight D* [4]  egy Sven König és Maxim Likhachev által létrehozott növekményes heurisztikus keresési algoritmus, amely LPA* [5] alapú , egy növekményes heurisztikus keresési algoritmus, amely az A* keresési algoritmus és a dinamikus SWSF-FP ötleteit ötvözi [6]. ] .

Mindhárom keresőalgoritmus ugyanazokat az útvonaltervezési feltevéseket oldja meg , beleértve a szabadterület-feltevésekkel [7] történő tervezést is, amikor a robotnak ismeretlen terepen meghatározott célkoordinátákra kell navigálnia. Feltételezéseket tesz a terep egy ismeretlen részével kapcsolatban (például, hogy nincsenek rajta akadályok), és ezen feltételezések alapján megtalálja a legrövidebb utat az aktuális koordinátáitól a cél koordinátáiig. A robot ezután követi az utat. Amikor új információt észlel a térképen (például korábban ismeretlen akadályokat), hozzáadja ezt az információt a térképéhez, és szükség esetén új legrövidebb utat tervez az aktuális koordinátáktól a megadott célkoordinátákig. A folyamatot addig ismétli, amíg el nem éri a célkoordinátákat, vagy megállapítja, hogy a célkoordinátákat nem lehet elérni. Ismeretlen terepen való áthaladáskor gyakran új akadályok fedezhetők fel, ezért ennek az újratervezésnek gyorsnak kell lennie. A növekményes (heurisztikus) keresési algoritmusok felgyorsítják a hasonló keresési problémák sorozatainak keresését, felhasználva a korábbi problémák megoldásának tapasztalatait, hogy felgyorsítsák az aktuális keresését. Feltételezve, hogy a célkoordináták nem változnak, mindhárom keresési algoritmus hatékonyabb, mint az ismételt A* keresés .

A D* -t és változatait széles körben használják mobil robotokhoz és autonóm navigációs járművekhez . A modern rendszerek általában a könnyű súlyon alapulnak , nem pedig az eredeti vagy fókuszált D* -on . Valójában még Stenz laborja is könnyűsúlyt használ az eredeti D* helyett [8] bizonyos megvalósításokban . Ilyen navigációs rendszerek közé tartozik az Opportunity és Spirit Mars-járókon tesztelt prototípusrendszer , valamint a DARPA Urban Challenge nyertesének navigációs rendszere , mindkettőt a Carnegie Mellon Egyetemen fejlesztették ki .

Az eredeti D* -t 1994 -ben vezette be Anthony Stentz . A D* név a " D dinamikus A* " kifejezésből származik, mivel az algoritmus úgy viselkedik, mint A * [2] , kivéve, hogy az ív költsége az algoritmus futása során változhat .

Műveletek

A D* főbb műveleteit az alábbiakban ismertetjük.

Dijkstra algoritmusához és A* -hoz hasonlóan a D* is fenntartja az értékelendő csomópontok listáját, amelyet OPEN listának neveznek . A csomópontok több állapotúként vannak megjelölve:

• ÚJ azt jelenti, hogy soha nem került fel a NYITOTT listára .
• Az OPEN azt jelenti, hogy jelenleg az OPEN listán van .
• A ZÁRVA azt jelenti, hogy már nem szerepel a NYITOTT listán .
• EMELTETT , azt jelzi, hogy értéke magasabb, mint amikor legutóbb szerepelt a NYITOTT listán .
• LOWER (ALACSONY ), azt jelzi, hogy értéke alacsonyabb, mint amikor legutóbb szerepelt a NYITOTT listán .

Kiterjesztés

Az algoritmus úgy működik, hogy iteratív módon kiválaszt egy csomópontot egy OPEN listából , és kiértékeli azt. Ezután továbbítja a csomópont módosításait az összes szomszédos csomópontra, és elhelyezi őket az OPEN listán . Ezt a terjesztési folyamatot "kiterjesztésnek" nevezik . A kanonikus A*-tól eltérően , amely az elejétől a végéig egy utat követ, a D* a célcsomóponttól visszafelé kezdi a keresést. Minden kiterjesztett csomópontnak van egy visszamutatója, amely a célhoz vezető következő csomópontra utal, és mindegyik csomópont ismeri a cél pontos költségét. Amikor a kezdő csomópont a következő csomópont, amelyet ki kell bővíteni, az algoritmus elkészül, és a célhoz vezető út egyszerűen a backticks követésével megtalálható.

• Bővítés folyamatban. A célcsomópont (sárga) a felső pontsor közepén, a kezdő csomópont az alsó sor közepén található. A piros akadályt jelez; a fekete/kék a kiterjesztett csomópontokat jelöli (a fényerő a költséget jelöli). A zöld a bővülő csomópontokat jelzi.

• A bővítés befejeződött. Az útvonal kék színnel látható.

Az akadályok leküzdése

Ha az adott úton akadályt találunk, az összes érintett pont ismét felkerül a NYITOTT listára , ezúttal UP jelzéssel . Mielőtt azonban növelné egy BOOSTER csomópont költségét , az algoritmus ellenőrzi a szomszédait, és megvizsgálja, hogy csökkentheti-e a csomópont költségét. Ellenkező esetben az UP állapot a csomópontok összes leszármazottjára, azaz a visszamutatókkal rendelkező csomópontokra kerül. Ezeket a csomópontokat ezután kiértékeli, és az UP állapotot továbbítja, hullámot képezve. Amikor egy UP csomópont csökkenthető, a háttérmutatója frissül, és átadja a DOWN állapotot a szomszédjainak. Ezek a FEL és LE hullámok a D* szíve .

Ezen a ponton a hullámok nem érinthetnek több pontot. Ezért az algoritmus csak azokkal a pontokkal működött, amelyeket értékváltozás érint.

• Az akadály hozzáadódik (piros), és a csomópontok UP (sárga) jelöléssel vannak ellátva.

• Bővítés folyamatban. A LIFT jelzésű csomópontok sárgával, a LOWER jelzésű csomópontok zölddel vannak jelölve .

Újabb zsákutca

Ezúttal lehetetlen ilyen elegánsan áttörni a holtpontról. Egyik pont sem talál új útvonalat a szomszédon keresztül a célhoz. Tehát folyamatosan propagálják az elismerésüket. Csak olyan csatornán kívüli pontokat találhat, amelyek egy járható útvonalon elvezethetnek egy célhoz. Így alakul ki két BOTTOM hullám, amelyek új útvonalinformációkkal elérhetetlennek jelölt pontokká bővülnek.

• A csatornát további akadályok (piros) blokkolják.

• Bővítés folyamatban. RAISE hullám (sárga), LOWER hullám (zöld).

• Talált egy ÚJ utat (kék).

Pszeudokód