| dbo:abstract
|
- 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*, ami egy informált növekményes keresési algoritmus.
* Az Anthony Stentz-féle Fókuszált D*, ami egy informált növekményes heurisztikus keresési algoritmus, amely ötvözi az A* é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, amely az LPA*-ra épül, egy növekményes heurisztikus keresési algoritmus, amely ötvözi az A* és a Dinamikus SWSF-FP ötleteit. Mindhárom keresési algoritmus ugyanazon feltételezésen alapuló problémákat oldja meg, ideértve a tervezést a szabad tér feltételezésével, 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 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 és az . 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 nyertes navigációs rendszerét. Mindkettőt a fejlesztették ki. Az eredeti D*-ot Anthony Stentz vezette be 1994-ben. A D* név a "Dynamic A*" 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. (hu)
- 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*, ami egy informált növekményes keresési algoritmus.
* Az Anthony Stentz-féle Fókuszált D*, ami egy informált növekményes heurisztikus keresési algoritmus, amely ötvözi az A* é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, amely az LPA*-ra épül, egy növekményes heurisztikus keresési algoritmus, amely ötvözi az A* és a Dinamikus SWSF-FP ötleteit. Mindhárom keresési algoritmus ugyanazon feltételezésen alapuló problémákat oldja meg, ideértve a tervezést a szabad tér feltételezésével, 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 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 és az . 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 nyertes navigációs rendszerét. Mindkettőt a fejlesztették ki. Az eredeti D*-ot Anthony Stentz vezette be 1994-ben. A D* név a "Dynamic A*" 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. (hu)
|
