17.5. Döntéselméleti ágensek

Ebben a fejezetben egy átfogó szemléletmódot vázolunk fel az ágensek megtervezésére részlegesen megfigyelhető, sztochasztikus környezetek esetén. A tervezés alapelemei már ismertek:

  • Az állapotátmenet- és megfigyelési modelleket egy dinamikus Bayes-hálóval (dynamic Bayesian network) ábrázoljuk (a 15. fejezetben leírtak szerint).

  • A dinamikus Bayes-háló kiegészült döntési és hasznossági csomópontokkal, amelyek megegyeznek a 16. fejezetben szereplő döntési hálókban használatosakkal. A kirajzolódó modellt dinamikus döntési hálónak vagy DDH-nak (dynamic decision network, DDN) nevezzük.

  • Egy szűrési algoritmust használunk az új érzékelések és cselekvések befogadására és a hiedelmi állapot reprezentációjának a frissítésére.

  • Döntéseket hozunk lehetséges cselekvéssorozatok elgondolásával és a legjobb kiválasztásával.

Egy dinamikus Bayes-háló felhasználásának elsődleges haszna az állapotátmenet- és érzékelő modellek ábrázolásánál az, hogy felbontja az állapotleírást valószínűségi változók egy halmazára, hasonlóan ahhoz, ahogy a tervkészítési algoritmusok logikai ábrázolást vesznek igénybe az állapottér felbontására, amit a keresési algoritmusok használnak. Az ágensterv ezért a 2. fejezetben vázolt hasznosságalapú ágens egy gyakorlati megvalósítása.

Mivel dinamikus Bayes-hálókat használunk, visszatérünk a 15. fejezetbeli jelöléshez, ahol Xt az állapotváltozók egy halmazát jelölte egy t időpillanatban, Et pedig a bizonyítékváltozókat. Így ahol ebben a fejezetben eddig st-t használtunk (a t-beli állapotra), mostantól Xt-t fogunk használni. A t-beli cselekvést At-vel fogjuk jelölni, így a T(s, a, s′) állapotátmenet-modell ugyanaz, mint a P(Xt+1|Xt, At), és az O(s, o) megfigyelési modell ugyanaz, mint a P(Et|Xt). A t időpontban kapott jutalmat jelöljük Rt-vel, és Ut-vel az állapot hasznosságát a t időpontban. E szerint a jelölés szerint egy dinamikus döntési háló a 17.9. ábrán látható módon néz ki.

17.9. ábra - Egy dinamikus döntési háló általános struktúrája. Az ismert értékű változók árnyékoltak. A jelenlegi időpont t, és az ágensnek el kell döntenie, hogy mit tegyen – azaz választania kell egy értéket At számára. A háló három jövőbeli lépésre van kibontva, és a jövőbeli jutalmakat, valamint az előrelátó horizonton lévő állapot hasznosságát ábrázolja.
Egy dinamikus döntési háló általános struktúrája. Az ismert értékű változók árnyékoltak. A jelenlegi időpont t, és az ágensnek el kell döntenie, hogy mit tegyen – azaz választania kell egy értéket At számára. A háló három jövőbeli lépésre van kibontva, és a jövőbeli jutalmakat, valamint az előrelátó horizonton lévő állapot hasznosságát ábrázolja.

A dinamikus döntési hálók tömör leírást biztosítanak nagy RMMDF-ekre, így bármely RMMDF algoritmus bemenetéül szolgálhatnak, ideértve az érték- és eljárásmód-iterációra való módszereket is. Ebben az alfejezetben az előrenéző módszerekre összpontosítunk, amelyek cselekvéssorozatokat képzelnek el a jelenlegi hiedelmi állapottól kiindulva, nagyon hasonlóan a 6. fejezetbeli játékok algoritmusaihoz. A 17.9. ábrán a háló három jövőbeli lépésig elképzelve szerepel; a jelenlegi és a jövőbeli döntések és a jövőbeli megfigyelések és jutalmak mind ismeretlenek. Figyeljük meg, hogy a háló csomópontokat tartalmaz az Xt+1 és Xt+2-beli jutalmakra, de hasznosságot az Xt+3 esetében. Ez azért van így, mert az ágensnek maximalizálnia kell az összes jövőbeli jutalom (leszámítolt) összegét, és U(Xt+3) reprezentálja az Xt+3-hoz tartozó és az összes ezt követő jutalmat. Ahogyan a 6. fejezetben, most is feltesszük, hogy U-nak csak egy közelítő alakja érhető el: ha elérhetők lennének pontos hasznosságértékek, akkor nem lenne szükség 1 lépésnél hosszabb előretekintésre.

A 17.9. ábrán látható DDH-hoz tartozó háromlépéses előrenéző keresési fa egy részét a 17.10. ábra mutatja. Mindegyik háromszög alakú csomópont egy olyan hiedelmi állapot, amiben az ágens egy At+i döntést hoz i = 0, 1, 2, ... esetén. A kerek csomópontok a környezet válaszaihoz tartoznak, nevezetesen hogy milyen Et+i megfigyelés fog felbukkanni. Látható, hogy nincsen véletlen csomópont, ami a cselekvések kimeneteléhez tartozna. Ez azért van így, mert egy cselekvésnél a hiedelmi állapot frissítése a konkrét kimeneteltől függetlenül determinisztikus.

A hiedelmi állapot az egyes háromszög csomópontoknál kiszámítható egy szűrési algoritmusnak a hozzávezető megfigyelések és cselekvések sorozatán való alkalmazásával. Ezzel a módszerrel, az algoritmus figyelembe veszi azt a tényt, hogy egy At+i döntésnél az ágens számára elérhetők lesznek az Et+1, ..., Et+i érzékelések, még ha a t időpontban nem is tudja, hogy ezek az érzékelések mi is lesznek. Ezen a módon a döntéselméleti ágens automatikusan figyelembe veszi az információ értékét és információgyűjtő cselekvéseket hajt végre, ha szükséges.

Egy döntés a keresési fából a levelek hasznosságértékének hátrafelé terjesztésével nyerhető ki, a véletlen csomópontoknál átlagot, a döntési csomópontokban pedig maximumot számítva. Ez hasonló a véletlen csomópontokkal rendelkező játékfákra vonatkozó VÁRHATÓMINIMAX algoritmushoz, kivéve, hogy (1) nem csak levélállapotokban lehet jutalom, és (2) a döntési csomópontok hiedelmi állapotokhoz, és nem aktuális állapotokhoz tartoznak. A d mélységű kimerítő keresés időkomplexitása O(|D|d· |E|d), ahol |D| az elérhető cselekvések száma, |E| pedig a lehetséges megfigyelések száma. Olyan problémáknál, ahol a γ leszámítolási tényező nincs közel 1-hez, gyakran elegendő sekély keresés az optimálishoz közeli döntés megtalálásához. Az is lehetséges, hogy az átlagszámítás lépését a lehetséges megfigyelések mintavételezésével közelítjük, az összes lehetséges megfigyelés feletti összegzés helyett. Számos más módja van jó közelítő megoldások gyors megtalálásának, de ezeket a 21. fejezetre hagyjuk.

A dinamikus döntési háló alapú döntéselméleti ágenseknek számos előnye van más, egyszerűbb, a korábbi fejezetekben bemutatott ágensfelépítésekhez képest. Nevezetesen, részlegesen megfigyelhető és sztochasztikus környezeteket kezelnek, és könnyen felülbírálják a „terveiket” a váratlan események kezeléséhez. Megfelelő érzékelő modellekkel képesek kezelni az érzékelőmeghibásodást, és képesek megtervezni az információ begyűjtését. Az idő szorításában és komplex környezetekben „teljesítményromlásuk fokozatos”, különböző közelítő technikák kihasználásával. Így jogos a kérdés, hogy mi is hiányzik még? A DDH-alapú algoritmusunknak a legkomolyabb hiányossága az előrefelé kereséstől való függés, ahogyan a II. részbeli állapottér-keresési algoritmusoknak is. A IV. részben elmagyaráztuk, hogy részlegesen rendezett, absztrakt tervek mérlegelésének képessége célirányos kereséssel hogyan biztosította a problémamegoldó képesség lényegi növekedését, különösen a tervkönyvtárakkal összeillesztve. Ezeket a módszereket megkísérelték a valószínűségi területre is kiterjeszteni, de ez eddig nem bizonyult hatékonynak. Egy második, kapcsolódó probléma a DDH nyelv alapvető kijelentéslogikai természete. Szeretnénk, ha az elsőrendű valószínűségi nyelvek elképzeléseit (lásd 14.6. alfejezet) ki tudnánk terjeszteni a döntéshozatal problémájára. A jelenlegi kutatások azt mutatják, hogy ez a kiterjesztés lehetséges, és jelentős előnyöket rejt magában, ahogy ezt a fejezet végi megjegyzéseknél megtárgyaljuk.

17.10. ábra - A 17.9. ábrán látható DDH előrenéző megoldásának egy része
A 17.9. ábrán látható DDH előrenéző megoldásának egy része