Szerkesztő:Palkó Tamás/D*

A D* algoritmus ( ejtsd "D csillag") a következő három kapcsolódó keresési 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ó út-tervezé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. 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*"[8] 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űveleteiSzerkesztés

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ésSzerkeszté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.

Akadályok kezeléseSzerkesztés

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.

Újabb holtpontra kerül sorSzerkesztés

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éllálomá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.

PszeudókódSzerkesztés

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

KiterjesztésSzerkeszté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éseSzerkesztés

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áltozatokSzerkesztés

Fókuszált D*Szerkesztés

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* LiteSzerkesztés

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. D* Lite

Minimális költség a jelenlegi költségekkel szembenSzerkesztés

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.

IrodalomSzerkesztés

  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. Stentz, Anthony (1995), "The Focussed D* Algorithm for Real-Time Replanning", Proceedings of the International Joint Conference on Artificial Intelligence: 1652–1659

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

FordításSzerkeszté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 jelzi, nem szolgál a cikkben szereplő információk forrásmegjelöléseként.

HivatkozásokSzerkesztés