D* algoritmus

A D* algoritmus (ejtsd "D csillag") a következő három kapcsolódó keresőalgoritmus egyikét jelenti:

• Az eredeti Anthony Stentz-féle D*,^[1] ami egy informált növekményes keresési algoritmus.
• Az Anthony Stentz-féle Fókuszált D*,^[2] ami egy informált növekményes heurisztikus keresési algoritmus, amely ötvözi az A*^[3] és az eredeti D* algoritmus ötleteit. A Fókuszált D* az eredeti D* továbbfejlesztésének eredményeként jött létre.
• A Sven Koenig és Maxim Likhachev által kitalált D* Lite,^[4] amely az LPA*^[5]-ra épül, egy növekményes heurisztikus keresési algoritmus, amely ötvözi az A* és a Dinamikus SWSF-FP ötleteit.^[6]

Mindhárom keresési algoritmus ugyanazon feltételezésen alapuló úttervezési problémákat oldja meg, ideértve a tervezést a szabad tér feltételezésével,^[7] ahol egy robotnak ismeretlen terepen kell navigálnia az adott célkoordinátákhoz. Feltételezéseket tesz a terep ismeretlen részeiről (például: hogy nem tartalmaz akadályokat), és megtalálja a legrövidebb utat a jelenlegi koordinátáktól a célkoordinátákig ezen feltevések alapján. A robot ezután követi az utat. Amikor megfigyeli az új térképinformációkat (például a korábban ismeretlen akadályokat), hozzáadja az információkat a térképéhez, és szükség esetén új legrövidebb utat állít át a jelenlegi koordinátáitól az adott célkoordinátákig. Addig ismételi a folyamatot, amíg el nem éri a célkoordinátákat, vagy meg nem határozza, hogy a célkoordinátákat nem lehet elérni. Ismeretlen terepen való áthaladáskor az új akadályok gyakran kerülhetnek elő, ezért ennek az újratervezésnek gyorsnak kell lennie. Az inkrementális (heurisztikus) keresési algoritmusok az hasonló keresési problémákkal kapcsolatos tapasztalatok felhasználásával gyorsítják fel az aktuális keresést. Feltéve, hogy a célkoordináták nem változnak, mindhárom keresési algoritmus hatékonyabb, mint az ismételt A* algoritmus.

A D*-ot és annak változatait széles körben használják a mobil robotokhoz és az önvezető jármű navigációhoz. A jelenlegi rendszerek általában a D* Lite-on alapulnak, nem az eredeti D*-on vagy a Fókuszált D*-on. Valójában néhány esetben még a Stentz laboratóriumában is D* Lite-ot használnak, nem pedig D*-ot.^[8] Az ilyen navigációs rendszerek magukban foglalják a marsjáró Opportunity és Spirit tesztelt prototípusrendszerét, valamint a DARPA Urban Challenge nyertes navigációs rendszerét. Mindkettőt a Carnegie Mellon Egyetemen fejlesztették ki.

Az eredeti D*-ot Anthony Stentz vezette be 1994-ben. A D* név a "Dynamic A*"^[2] kifejezésből származik, mert az algoritmus úgy viselkedik, mint az A*, azzal az eltéréssel, hogy az ívköltségek az algoritmus futásakor változhatnak.

Műveletei

A D* alapvető működését az alábbiakban ismertetjük.

Dijkstra algoritmusához és A*-hoz hasonlóan a D* fenntartja az értékelendő csomópontok listáját az úgynevezett "OPEN list" néven. A csomópontok meg vannak jelölve, amelyek az alábbi állapotok közül egyet tartalmaznak:

• ÚJ (NEW), azaz soha nem került fel az OPEN listára
• NYITVA (OPEN), azaz jelenleg szerepel az OPEN listán
• ZÁRVA (CLOSED), azaz már nem szerepel az OPEN listán
• EMELT (RAISE), azaz magasabb a költsége, mint amikor utoljára szerepelt az OPEN listán
• CSÖKKENTETT (LOWER), azaz alacsonyabb a költsége, mint amikor utoljára szerepelt az OPEN listán

Kiterjesztés

Az algoritmus úgy működik, hogy iteratívan kiválaszt egy csomópontot az OPEN listából, és kiértékeli azt. Ezután továbbadja a csomópont változásait az összes szomszédos csomópontnak, és felveszi őket az OPEN listára. Ezt a folyamatot "kiterjesztésnek" nevezzük. Az A*-gal ellentétben, amely az utat az elejétől a végéig követi, a D* azzal kezdődik, hogy visszafelé keres a célcsomóponttól. Minden kibővített csomópontnak van egy backpointerje, amely a célhoz vezető következő csomópontra utal, és minden csomópont ismeri a cél pontos költségeit. Amikor a kezdő csomópont a következő kibővítendő csomópont, akkor megtörténik az algoritmus, és a cél elérésének útját a backpointerek egyszerű követésével lehet megtalálni.

• 
  Bővítés folyamatban. A célcsomópont (sárga) a pontok felső sorának közepén, a kezdő csomópont az alsó sor közepén található. Piros akadályt jelöl; fekete/kék jelzi a kibővített csomópontokat (fényerő a költségeket jelzi). A zöld jelzi a kibővített csomópontokat.
• 
  A kiterjesztés kész. Az utat cián jelzi.

Akadályok kezelése

Ha akadályt észlelnek a tervezett úton, akkor az összes érintett pontot újra felveszik az OPEN listába, ezúttal RAISE jelöléssel. Mielőtt egy RAISE csomópont növeli a költségeket, az algoritmus ellenőrzi a szomszédait, és megvizsgálja, hogy képes-e csökkenteni a csomópont költségeit. Ha nem, akkor a RAISE állapotot továbbadják az összes csomópont leszármazottjának, azaz azoknak a csomópontoknak, amelyekhez visszamutató van. Ezeket a csomópontokat ezután kiértékeljük, és a RAISE állapotot továbbítjuk, hullámot képezve. Amikor egy RAISE csomópont csökkenthető, a visszamutató frissül, és átadja a LOWER állapotot a szomszédainak. Ezek a RAISE és LOWER állapotok hullámai a D* szívdobbanásai.

Ekkor egész sor más pontot a hullámok már nem "érintenek meg". Az algoritmus tehát csak azokon a pontokon működött, amelyeket a költségváltozás befolyásol.

• 
  Egy akadályt adtak hozzá (piros) és a csomópontokat RAISE (sárga) jelzéssel látják el
• 
  Bővítés folyamatban. Sárga a RAISE jelöléssel ellátott csomópontokat, a zöld a LOWER jelölésű csomópontokat jelöli

Újabb holtpontra kerül sor

Ezúttal a holtpontot nem lehet elegánsan megkerülni. Egyik pont sem talál új útvonalat egy szomszédon keresztül a célállomás helyéig. Ezért tovább emelkedik a költségük ezeknek a pontoknak. Csak a csatornán kívüli pontok találhatók, amelyek életképes útvonalon vezethetnek a célállomásra. Így kialakul két alsó hullám, amelyek új útvonal-információkkal nem kielégítően megjelölt pontokként terjednek ki.

• 
  A csatornát további akadályok blokkolják (piros)
• 
  Folyamatban lévő bővítés (sárga RAISE hullám, zöld LOWER hullám)
• 
  Új utat találtak (cián)

Pszeudokód

while (!openList.isEmpty()) {
    point = openList.getFirst();
    expand(point);
}

Kiterjesztés

void expand(currentPoint) {
    boolean isRaise = isRaise(currentPoint);
    double cost;
    for each (neighbor in currentPoint.getNeighbors()) {
        if (isRaise) {
            if (neighbor.nextPoint == currentPoint) {
                neighbor.setNextPointAndUpdateCost(currentPoint);
                openList.add(neighbor);
            } else {
                cost = neighbor.calculateCostVia(currentPoint);
                if (cost < neighbor.getCost()) {
                    currentPoint.setMinimumCostToCurrentCost();
                    openList.add(currentPoint);
                }
            }
        } else {
            cost = neighbor.calculateCostVia(currentPoint);
            if (cost < neighbor.getCost()) {
                neighbor.setNextPointAndUpdateCost(currentPoint);
                openList.add(neighbor);
            }
        }
    }
}

RAISE pontok ellenőrzése

boolean isRaise(point) {
    double cost;
    if (point.getCurrentCost() > point.getMinimumCost()) {
        for each(neighbor in point.getNeighbors()) {
            cost = point.calculateCostVia(neighbor);
            if (cost < point.getCurrentCost()) {
                point.setNextPointAndUpdateCost(neighbor);
            }
        }
    }
    return point.getCurrentCost() > point.getMinimumCost();
}

Változatok

Fókuszált D*

Amint a neve is sugallja, a Fókuszált D* a D* egy kiterjesztése, amely heurisztikát használ a RAISE és LOWER terjedésének a robot felé fókuszálására. Ilyen módon csak az adott állapot frissül, ugyanúgy, mint az A* csak néhány csomópont költségeit számolja ki.

D* Lite

A D* Lite nem az eredeti D* vagy a Fókuszált D* alapú, de ugyanazt a viselkedést valósítja meg. Egyszerűbb megérteni, és kevesebb kódsorban valósítható meg, innen származik a "D* Lite" név. Teljesítmény-szempontból ugyanolyan jó vagy jobb, mint a Fókuszált D*. A D* Lite a Lifelong Planning A* algoritmuson alapul, amelyet Koenig és Likhachev néhány évvel korábban vezettek be.^[9]

Minimális költség a jelenlegi költségekkel szemben

A D* esetében fontos különbséget tenni a jelenlegi és a minimális költségek között. Az előbbi csak a gyűjtéskor fontos, az utóbbi pedig kritikus, mivel rendezi az OpenList. A minimális költséget visszatérő funkció mindig a legalacsonyabb költség az aktuális pontig, mivel ez az OpenList első bejegyzése.

Irodalom

1. Stentz, Anthony (1994), "Optimal and Efficient Path Planning for Known Environments", Proceedings of the International Conference on Robotics and Automation: 3310–3317
2. Stentz, Anthony (1995), "The Focussed D* Algorithm for Real-Time Replanning", Proceedings of the International Joint Conference on Artificial Intelligence: 1652–1659
3. Hart, P., "A Formal Basis for the Heuristic Determination of Minimum Cost Paths", IEEE Trans. Syst. Science and Cybernetics: 100–107
4. Koenig, S., "Fast Replanning for Navigation in Unknown Terrain", Transactions on Robotics: 354–363
5. Koenig, S., "Lifelong Planning A*", Artificial Intelligence: 93–146
6. Ramalingam, G., "An incremental algorithm for a generalization of the shortest-path problem", Journal of Algorithms: 267–305
7. Koenig, S.; Smirnov, Y. & Tovey, C. (2003), "Performance Bounds for Planning in Unknown Terrain", Artificial Intelligence 147 (1–2): 253–279, DOI 10.1016/s0004-3702(03)00062-6
8. Wooden, D. (2006), Graph-based Path Planning for Mobile Robots, Georgia Institute of Technology
9. http://idm-lab.org/bib/abstracts/papers/aaai02b.pdf D* Lite

Forráshivatkozás-hiba: a <references> címkében definiált <ref> címkének nincs név attribútuma.

Fordítás

• Ez a szócikk részben vagy egészben a D* című angol Wikipédia-szócikk ezen változatának fordításán alapul. Az eredeti cikk szerkesztőit annak laptörténete sorolja fel. Ez a jelzés csupán a megfogalmazás eredetét és a szerzői jogokat jelzi, nem szolgál a cikkben szereplő információk forrásmegjelöléseként.

Hivatkozások

• Sven Koenig weblapja
• Anthony Stentz weboldala