Szerkesztő:Palkó Tamás/Lifelong Planning A*
Sablon:Infobox algorithm Az LPA * vagy az Lifelong Planning A* egy heurisztikus keresési algoritmus, amely az A*-on alapul. Először Sven Koenig és Maxim Likhachev írta le 2001-ben.
Leírás[szerkesztés]
Az LPA * az A* egy növekményes változata, amely alkalmazkodni tud a grafikon változásaihoz anélkül, hogy a teljes grafikonot újra kiszámítaná, frissíti a g-értékeket (a kezdetektől való távolságot) az előző keresésből az aktuális keresés során, hogy szükség esetén helyesbítse azokat. Az A* -hoz hasonlóan az LPA* heurisztikát is használ, amely az adott csomóponttól a célig vezető út költségeinek alsó határa. A heurisztika elfogadható, ha garantáltan nem negatív (nulla megengedett), és soha nem haladja meg a cél elérésének legolcsóbb útjának költségét.
Elődök és utódok[szerkesztés]
A kezdő és a cél csomópont kivételével minden n csomópont rendelkezik elődökkel és utódokkal :
- Bármely csomópont, amelybe él vezet n egy elődje.
- Bármelyik csomópont, amelyből él vezet az n utódja.
A következő leírásban ez a két kifejezés csak a közvetlen elődökre és utódokra utal, nem pedig az elődök elődeire vagy az utódok utódaira.
A távolság becslései[szerkesztés]
Az LPA* a g*(n) kezdési távolság két becslését készíti el minden csomópontnál:
- g(n), az előzőleg kiszámított g-érték (kezdeti távolság) mint az A* algoritmusban
- rhs(n), a előrejelzett érték amelyek a csomópont elődjeinek g-értékén alapul (a g(n' ) + d(n' , n) minimuma, ahol n' az n elődje és d(x, y) az x és y csomópontokat összekötő él költsége)
A kezdő csomópont esetében a következő mindig igaz:
Ha rhs(n) megegyezik g(n)-nel akkor n-t lokálisan konzisztensnek nevezzük. Ha az összes csomópont lokálisan konzisztens, akkor a legrövidebb utat meg lehet határozni, mint az A*-nál. Ha azonban az élköltségek megváltoznak, a lokális konzisztenciát csak az útvonal szempontjából releváns csomópontokban kell kiszámítani.
Prioritási sor[szerkesztés]
Amikor egy csomópont lokálisan inkonszisztenssé válik (mivel elődjének költsége vagy az elődjének összekötő élének költsége megváltozott), akkor az algoritmus prioritási sorba helyezi az újraértékeléshez. Az LPA* kétdimenziós kulcsot használ:
A bejegyzések először k1 (amely közvetlenül megfelel az A*-ban használt f-értékeknek), majd k2 szerint vannak rendezve.
Csomópont bővítés[szerkesztés]
A sor felső csomópontja az alábbiak szerint bővül:
- Ha egy csomópont rhs-értéke megegyezik g-értékével, akkor a csomópont lokálisan konzisztens, és eltávolításra kerül a sorból.
- Ha egy csomópont rhs-értéke kisebb, mint g-értéke ( helyileg túlkonzisztens csomópontnak nevezik), akkor a g-értéket úgy módosítja, hogy megfeleljen az rhs-értéknek, így a csomópont lokálisan konzisztens lesz. Ezután a csomópontot eltávolítják a sorból.
- Ha egy csomópont rhs-értéke nagyobb, mint g-értéke ( helyileg aligkonzisztens csomópontként nevezik), akkor a g-értéket végtelenre állítják (ami a csomópontot lokálisan túlkonzisztensnek vagy lokálisan konzisztensnek tekinti). Ha a csomópont lokálisan konzisztens, akkor azt eltávolítják a sorból, a kulcs megújul.
Mivel egy csomópont g-értékének megváltoztatása megváltoztathatja utódjainak rhs-értékeit (és így lokális konzisztenciájukat), ezeket kiértékeljük, és a sor sorrendjük és kulcsuk szükség esetén frissül.
A csomópontok bővítése a sor tetején lévő következő csomóponttal folytatódik, amíg két feltétel teljesül:
- A cél lokálisan konzisztens, és
- A prioritási sor tetején levő csomópontnak olyan kulcsa van, amely nagyobb vagy egyenlő a cél kulcsával.
Kezdeti futás[szerkesztés]
A grafikon inicializálása úgy történik, hogy a kezdő csomópont rhs-értékét 0-ra, g-értékét végtelenre állítja. Az összes többi csomópontnál mind a g-értéket, mind az rhs-értéket végtelennek tekintik, amíg azok nem változnak meg. Ez kezdetben a kezdő csomópontot az egyetlen lokálisan inkonzisztens csomóponttá, és ezáltal a sor egyetlen csomópontjává teszi. Ezután megkezdődik a csomópont-bővítés. Az LPA* első futtatása tehát ugyanúgy viselkedik, mint az A*, azaz ugyanazon csomópontok kibővítése történik ugyanabban a sorrendben.
Költségváltozások[szerkesztés]
Amikor egy él költsége megváltozik, az LPA* megvizsgálja a változás által érintett összes csomópontot, azaz azokat a csomópontokat, amelyeknél az egyik megváltozott él lezárul (ha egy él mindkét irányban áthaladhat, és a változás mindkét irányba hat, az él mindkét végét megvizsgáljuk):
- A csomópontok rhs-értékei frissülnek.
- Azok a csomópontok, amelyek lokálisan konzisztensek lettek, eltávolításra kerülnek a sorból.
- Azok a csomópontok, amelyek lokálisan inkonzisztenssé váltak, hozzáadódnak a sorhoz.
- Azok a csomópontok, amelyek lokálisan inkonzisztensek maradnak, a kulcsokat frissítik.
Ezt követően a csomópont kibővítése folytatódik, amíg a végső feltételt elérik.
A legrövidebb út megkeresése[szerkesztés]
Amint a csomópont kibővítése befejeződött (azaz a kilépési feltételek teljesülnek), a legrövidebb utat kiértékelik. Ha a cél költsége megegyezik a végtelenséggel, akkor nincs elegendő költségút az indulástól a célig. Egyébként a legrövidebb utat visszafelé haladással lehet meghatározni:
- Kezdje a céltól.
- Lépjen az aktuális n csomópont n' elődjére, ahol a g(n' ) + d(n' , n) a legalacsonyabb (ha a legalacsonyabb pontszámot több csomópont is eléri, akkor mindegyik érvényes megoldás, és ezek közül bármelyiket lehet választani).
- Ismételje meg az előző lépést, amíg el nem éri a startot.
Pszeudókód[szerkesztés]
Ez a kód feltételezi a queue
prioritási sort, amely támogatja a következő műveleteket:
topKey()
visszaadja a sorban lévő bármely csomópont (numerikusan) legalacsonyabb prioritását (vagy végtelennek, ha a sor üres)pop()
eltávolítja a sorból a legalacsonyabb prioritású csomópontot, és visszatérinsert(node, priority)
beszúr egy adott prioritással rendelkező csomópontot a sorbaremove(node)
eltávolítja a csomópontot a sorbólcontains(node)
igaz értéket ad, ha a sor a megadott csomópontot tartalmazza; hamist, ha nem
Tulajdonságok[szerkesztés]
Mivel algoritmikusan hasonló az A* -hoz, az LPA* számos tulajdonságát megosztja.
- Minden csomópontot az LPA* futtatásakor legfeljebb kétszer kibontunk (látogatunk meg). A lokálisan túlkonszisztens csomópontok LPA* futtatásonként legfeljebb egyszer kibővülnek, így az első futtatás (amelyben minden csomópont túlkonzisztens állapotba lép) hasonló teljesítményű, mint az A*, amely minden csomópontot egyszerre meglátogat.
- Az egyes futtatásokhoz kibővített csomópontok kulcsai monoton módon nem csökkennek az idő múlásával, mint az A* esetében.
- Minél informáltabb (és így nagyobb) a heurisztika (miközben továbbra is teljesíti az elfogadhatósági kritériumokat), annál kevesebb csomópontot kell kibővíteni.
- A prioritási sor végrehajtása jelentős hatást gyakorol a teljesítményre, mint az A* esetében. A Fibonacci-halom használata jelentős teljesítménynövekedést eredményezhet a kevésbé hatékony megvalósításokhoz képest.
Az A* megvalósítás esetén, amely megszakítja a két csomópont közötti egyenlő f-értékek közötti kapcsolatokat a kisebb g-értékű csomópont javára (amelyet az A* nem határoz meg pontosan), a következő állítások is igazak:
- A lokálisan túlkonzisztens csomópontok kibővítésének sorrendje megegyezik az A* -el.
- Az összes lokálisan túlkonzisztens csomópont közül csak azokat - amelyek költsége nem haladja meg a célt - kell kibővíteni, mint az A* esetében.
Az LPA* ezen felül a következő tulajdonságokkal rendelkezik:
- Amikor az élköltségek megváltoznak, az LPA* felülmúlja az A* -ot (feltételezve, hogy az utóbbi a nulláról indul), mivel csak a csomópontok töredékét kell kibővíteni.
Változatok[szerkesztés]
- D* Lite, a D* algoritmus újbóli megvalósítása LPA* alapján
Irodalom[szerkesztés]
Forráshivatkozás-hiba: a <references>
címkében definiált „KoenigLikhachev2001” nevű <ref>
címke nem szerepel a szöveg korábbi részében.
Forráshivatkozás-hiba: a <references>
címkében definiált „KoenigLikhachev2002” nevű <ref>
címke nem szerepel a szöveg korábbi részében.
Forráshivatkozás-hiba: a <references>
címkében definiált „KoenigLikhachev2005” nevű <ref>
címke nem szerepel a szöveg korábbi részében.
[[Kategória:Mesterséges intelligencia]]