3.1. Problémamegoldó ágensek

Az intelligens ágensekről feltesszük, hogy a teljesítménymértéküket maximalizálják. Mint azt a 2. fejezetben láttuk, a feladat valamelyest leegyszerűsödik, ha az ágens egy célt (goal) tud maga elé tűzni, és megpróbálja azt elérni. Először vizsgáljuk meg, hogy az ágens hogyan és miért teheti ezt meg.

Tegyük fel, hogy az ágensünk a romániai Arad városában tartózkodik, és országjáró túrája vége felé közeledik. Az ágens teljesítménymértéke számos tényezőt tartalmaz: például szépen le szeretne barnulni, tökéletesíteni szeretné a román nyelvtudását, látni szeretné az összes nevezetességet, élvezni az éjszakai életet (amilyen van), kerülni a másnaposságot stb. A döntési probléma igen bonyolult, sok kompromisszummal és útikönyvek gondos tanulmányozásával jár. Tételezzük most fel, hogy ágensünk egy Bukarestből érvényes, vissza nem váltható repülőjeggyel rendelkezik másnapra. Ebben a helyzetben értelmes célnak (goal) tűnik, hogy eljusson Bukarestbe. Mindazon cselekvéseket további mérlegelés nélkül el lehet dobni, amelyekkel nem lehet időben Bukarestbe érni, amivel az ágens döntési problémája nagymértékben egyszerűsödik. A célok segítik megszervezni a viselkedést, mivel korlátozzák az ágens által elérendő dolgok számát. A pillanatnyi helyzeten és az ágens hasznosságmértékén alapuló célmegfogalmazás (goal formulation) a problémamegoldás első lépése.

Célnak a világ állapotainak egy halmazát tekintjük, pontosabban azon állapotok halmazát, amelyekben a cél teljesül. Az ágens feladata megkeresni, hogy amely cselekvések sorozata juttatja el őt egy célállapotba. Mielőtt azonban ezt megtehetné, el kell döntenie, hogy milyen cselekvéseket és állapotokat vizsgáljon meg. Amennyiben olyan szintű cselekvésekkel kellene dolgoznia, mint például „a bal lábadat tedd előrébb fél méterrel” vagy „a kormánykereket hat fokkal tekerd balra”, az ágens még a parkolóból sem lenne képes kihajtani, nemhogy időben eljutni Bukarestbe, mivel az ilyen részletek szintjén a világban túl sok a bizonytalanság, és a megoldás túl sok lépésből állna. A problémamegfogalmazás (problem formulation) az a folyamat, amely során eldöntjük, hogy amely cselekvéseket és állapotokat vegyünk figyelembe, ha egy cél adott. Ezt a folyamatot részletesebben is tárgyalni fogjuk. Egyelőre tételezzük fel, hogy az ágens az egyik nagyobb városból egy másik nagyobb városba való autózás szintjén szemléli a cselekvéseket. Ebből adódóan a figyelembe vett állapotok annak felelnek meg, hogy az ágens éppen egy adott városban van.[27]

Az ágensünk azt tűzte ki célul, hogy Bukarestbe megy, és azt fontolgatja, hogy Aradról hová menjen. Három út vezet ki Aradról: egy Nagyszeben felé, egy Temesvár felé és egy Nagyzerénd felé. Ezek egyike sem éri el közvetlenül a célt, így amennyiben ágensünk nem ismeri ki magát tökéletesen Romániában, nem fogja tudni, hogy melyik úton induljon el.[28] Más szóval az ágens nem fogja tudni eldönteni, hogy a lehetséges cselekvések közül melyik a legjobb, mert nincs elegendő információja a cselekvések hatására előálló állapotokról. Amennyiben az ágensnek nem áll rendelkezésére további tudás, akkor itt megakad. A legjobb amit tehet, hogy a cselekvésekből véletlenszerűen kiválaszt egyet.

Fontos

Tegyük fel azonban, hogy ágensünknek akár papíron, akár a fejében van egy Románia-térképe. A térkép jelentősége, hogy információt nyújthat az ágensnek azokról az állapotokról, ahova eljuthat, illetve a végrehajtható cselekvésekről. Az ágens ezen információt felhasználhatja egy hipotetikus utazás megtervezésére ezeken a városokon keresztül, hogy megtalálja a legjobb utat, amely végül elvezet Bukarestbe. Miután a térképen megtalált egy utat Aradról Bukarestbe, a célját el tudja érni, ha az utazás egyes állomásaihoz tartozó vezetési szakaszokat végrehajtja. Általánosságban: amennyiben egy ágens előtt közvetlenül több ismeretlen értékű lehetőség áll, ki tudja választani, hogy mit tegyen, ha először megvizsgálja a különböző lehetséges cselekvéssorozatokat, amelyek ismert értékű állapotokba vezetnek, majd ezután kiválasztja a legjobbat.

Az ilyen sorozat előállítási folyamatát keresésnek (search) nevezzük. A keresési algoritmus bemenete egy probléma, kimenete pedig egy cselekvéssorozat formájában előálló megoldás (solution). Miután előállt egy megoldás, az abban szereplő cselekvéseket végre lehet hajtani. Ezt végrehajtási (execution) fázisnak szokás nevezni. Így előállt egy egyszerű „fogalmazd meg, keresd meg, hajtsd végre” ágenstervezési séma. Az előállt sémát a 3.1. ábra mutatja. A cél és a megoldandó probléma megfogalmazása után az ágens egy keresési eljárást hív meg. Ezek után a megoldást használja cselekvései vezérlésére, azt teszi, amit a megoldás a következő lépésnek javasol – ez tipikusan a cselekvéssorozat első lépése –, és a végrehajtott lépést törli a cselekvéssorozatból. Miután a megoldást végrehajtotta, az ágens új célt keres.

3.1. ábra - Egy egyszerű problémamegoldó ágens. Először a célt és a problémát fogalmazza meg, majd a problémát megoldó cselekvéssorozatot keres, végül a cselekvéseket egyenként végrehajtja. Amikor kész vele, egy másik célt fogalmaz meg, és az egészet újrakezdi. Jegyezzük meg, hogy a cselekvéssorozata végrehajtása alatt az ágens az érzékeléseivel nem foglalkozik. Feltételezi, hogy az általa megtalált megoldás mindig működőképes.
Egy egyszerű problémamegoldó ágens. Először a célt és a problémát fogalmazza meg, majd a problémát megoldó cselekvéssorozatot keres, végül a cselekvéseket egyenként végrehajtja. Amikor kész vele, egy másik célt fogalmaz meg, és az egészet újrakezdi. Jegyezzük meg, hogy a cselekvéssorozata végrehajtása alatt az ágens az érzékeléseivel nem foglalkozik. Feltételezi, hogy az általa megtalált megoldás mindig működőképes.

Először a problémamegfogalmazás folyamatát írjuk le, majd a fejezet további részeit a KERESÉS függvény különböző változatainak ismertetésére fordítjuk. Ebben a fejezetben nem tárgyaljuk részletesen az ÁLLAPOT-FRISSÍTÉS és a CÉL-MEGFOGALMAZÁS függvényeket.

Mielőtt a részletekbe belemerülnénk, egy pillanatra álljunk meg és nézzük meg, hogy a problémamegoldó ágens hogyan illik bele a 2. fejezetben tárgyalt ágensek és környezetek sokaságába. A 3.1. ábrán látható ágenstervezet feltételezi, hogy a környezet statikus (static), mivel a probléma megfogalmazása és megoldása semmilyen változásról nem vesz tudomást, amely esetleg a környezetben beáll. Az ágenstervezet azt is feltételezi, hogy a kezdeti állapot ismert. Ennek ismerete akkor a legkönnyebb, amikor a környezet megfigyelhető (observable). Az „alternatív cselekvések számontartása” tulajdonképpen azt tételezi fel, hogy a környezet diszkrét (discrete). Végül a legfontosabb: az ágenstervezet azt is feltételezi, hogy a környezet determinisztikus (deterministic). A problémamegoldások egyedi cselekvéssorozatok, így a váratlan eseményeket nem is tudják figyelembe venni. A megoldások végrehajtása ráadásul az érzékelésről nem is vesz tudomást! Annak az ágensnek, amely mondhatni csukott szemmel hajtja végre a terveit, eléggé biztosnak kell lennie a dolgában (szabályozáselméletben az ilyen rendszereket nyílt hurkúnak – open-loop – hívják, mert az érzékelések figyelmen kívül hagyása az ágens és a környezete közötti hurkot felbontja). E feltételezések azt jelentik, hogy a környezetek lehető legegyszerűbbikével foglalkozunk, és ez egyben indokolja azt is, hogy e fejezet miért a könyv elején található. A 3.6. alfejezet rövid bepillantást ad abba, hogy mi történik, amikor a megfigyelhetőség és a determinizmus feltételezéséről lemondunk. Ezt a témát sokkal mélyebben a 12. és a 17. fejezet tárgyalja.

3.1.1. Jól definiált problémák és megoldások

Egy probléma (problem) formális megragadásához az alábbi négy komponensre van szükség:

  • A kiinduló állapot (initial state), amiből az ágens kezdi a cselekvéseit. A romániai ágensünk kezdeti állapotát például Benn(Arad)-ként lehetne leírni.

  • Az ágens rendelkezésére álló lehetséges cselekvések (actions) halmaza. A leginkább használatos leírás[29] az állapotátmenet-függvényt (successor function) alkalmazza. Egy adott x állapot esetén az ÁLLAPOTÁTMENET-FV (x) visszaadja a rendezett ⟨cselekvés, utódállapot⟩ párok halmazát, ahol minden cselekvés az x állapotban legális cselekvések egyike, és minden utódállapotot egy cselekvésnek az x állapotra való alkalmazásával nyerünk. A Benn(Arad) állapotban az állapotátmenet-függvény a romániai problémára a

{⟨Menj(Nagyszeben), Benn(Nagyszeben)⟩, ⟨Menj(Temesvár), Benn(Temesvár)⟩, ⟨Menj(Nagyzerénd), Benn(Nagyzerénd)⟩}

párokat adná vissza.

A kezdeti állapot és az állapotátmenet-függvény együttesen implicit módon definiálják a probléma állapotterét (state space): azon állapotok halmazát, amelyek a kiinduló állapotból elérhetők. Az állapottér egy gráfot alkot, amelynek csomópontjai az állapotok és a csomópontok közötti élek a cselekvések. (Románia 3.2. ábrán látható térképe állapottérként értelmezhető, ha minden útját kétirányú gépkocsi-vezetési cselekvésként fogjuk fel). Az állapottér egy útja (path) az állapotok egy sorozata, amely állapotokat a cselekvések egy sorozata köt össze.

  • A célteszt (goal test), amely meghatározza, hogy egy adott állapot célállapot-e. Néha létezik a lehetséges célállapotok egy explicit halmaza, és a teszt egyszerűen megnézi, hogy az ágens elérte-e ezek egyikét. Romániában az ágens célja a {Benn(Bukarest)} szingleton. Néha a cél valamilyen absztrakt tulajdonsággal van definiálva, nem pedig explicit módon felsorolt állapothalmazzal. A sakkban például az úgynevezett „sakk-matt” állapot elérése a cél, amelyben az ellenfél királya az őt ért támadás elől nem tud elmenekülni.

  • Egy útköltség- (path cost) függvény, amely minden úthoz hozzárendel egy költséget. A problémamegoldó ágens azt a költségfüggvényt fogja választani, amely a saját hatékonysági mértékének felel meg. A Bukarestbe siető ágens számára az idő a lényeg, így az útköltség lehetne például az út a km-ben kifejezett hossza. Ebben a fejezetben az út költségének az utat alkotó egyes cselekvések költségének összegét fogjuk tekinteni az út mentén. Az x állapotból az y állapotba vezető cs cselekvés lépésköltsége (step cost) legyen lk(x, cs, y). Romániában a lépésköltségeket a 3.2. ábra mutatja úttávolságok formájában. Feltételezzük, hogy a lépésköltségek nemnegatívak.[30]

Az előbbi elemek definiálják a problémát és egy közös adatstruktúrába foghatók, amit a problémamegoldó algoritmus bemenetének tekintünk. A probléma megoldása (solution) nem más, mint a kiinduló állapotból a célállapotba vezető út. A megoldás kvalitását az útköltségfüggvény méri, és egy optimális megoldásnak (optimal solution) a megoldások közt a legkisebb lesz az útköltsége.

3.1.2. A problémák megfogalmazása

Az előbbi részben a „hogyan jutunk el Bukarestbe” probléma olyan megfogalmazását javasoltuk, amely a kezdeti állapotból, az állapotátmenet-függvényből, a célállapottesztből és az útköltségből áll. Ez a megfogalmazás értelmesnek tűnik, a valós világ számos aspektusát mégis figyelmen kívül hagyja. Hasonlítsuk csak össze az általunk választott egyszerű állapotleírást, Benn(Arad), egy tényleges országjáró kirándulással, ahol a világ állapota rengeteg mindent tartalmazhat: kivel utazunk, mit közvetít a rádió, milyen tájat látunk az ablakon át, van-e közelben rendőr, milyen messze van a következő pihenőhely, milyen az út állapota, milyen az időjárás és sok-sok más.

Ezeket a részleteket kihagytuk az állapotleírásokból, mert nem lényegesek a Bukarestbe vezető út megkeresésében. Egy reprezentációból a részletek eltávolítását absztrakciónak (abstraction) nevezzük.

Az állapotleírás absztrahálása mellett magukat a cselekvéseket is absztrahálni kell. Egy vezetési cselekvésnek számos hatása van. Amellett, hogy megváltoztatja a gépkocsi és utasai helyét, időbe telik, üzemanyagot fogyaszt, szennyezi a levegőt és megváltoztatja az ágenst (azt mondják, hogy az utazás kiszélesíti a látókört). A mi megfogalmazásunkban csak a helyváltoztatást vesszük figyelembe. Van számos olyan cselekvés, amit teljesen elhagyunk: például a rádió bekapcsolását, az ablakon való kinézést, a lassítást, mert rendőr van a közelben stb. És persze a „fordítsd a kormányt balra 3 fokkal” szintű cselekvésekkel sem foglalkozunk.

Lehetünk-e pontosabbak a megfelelő absztrakciós szint meghatározásában? A megválasztott absztrakt állapotokra és cselekvésekre úgy gondolunk, hogy azok a részletes valós állapotok és cselekvések egész halmazaihoz tartoznak. Most tekintsük az absztrakt probléma egy megoldását: például az Aradról Nagyszebenbe, majd Rimnicu Vilceába, Pites¸tibe és Bukarestbe vezető utat. Ez az absztrakt megoldás rengeteg részletesebb útnak felel meg. Például Nagyszeben és Rimnicu Vilcea között vezethettünk bekapcsolt rádióval, majd az utazás további részére kikapcsolhattuk a rádiót. Az absztrakció érvényes, ha az absztrakt megoldást megoldássá fejthetjük ki egy részletesebb világban is. Elégséges feltétel az, hogy minden olyan részletes állapothoz, mint az „Aradon van”, létezik egy részletes út valamelyik olyan állapothoz, mint a „Nagyszebenben van” stb. Az absztrakció hasznos, ha a megoldásbeli cselekvések végrehajtása az eredeti problémánál egyszerűbb. Ebben az esetben ezek eléggé egyszerűek ahhoz, hogy egy átlagos gépkocsivezető ágens végre tudja azokat hajtani minden további keresés vagy tervkészítés nélkül. Így egy jó absztrakció megválasztása magában foglalja az érvényesség megőrzése mellett a lehető legtöbb részlet törlését, és annak biztosítását, hogy az absztrakt cselekvéseket könnyű legyen véghezvinni. Ha nem lenne meg a hasznos absztrakciók megalkotásának képessége, akkor az intelligens ágensek a valós világban teljesen hasznavehetetlenek lennének.

3.2. ábra - Románia egy részének sematikus országúti térképe
Románia egy részének sematikus országúti térképe



[27] Vegyük észre, hogy ezek az állapotok valójában a világ állapotaiból képezett nagy halmazoknak felelnek meg, mivel a világ állapotai a valóság minden aspektusát meghatározzák. Fontos észben tartani a problémamegoldás állapotai és a világ állapotai közötti különbséget.

[28] Feltételezzük, hogy legtöbb olvasónk ugyanebben a cipőben jár, és könnyen át tudja érezni ágensünk tanácstalanságát. Ezúton elnézést kérünk a romániai olvasóktól, akik számára ezen pedagógiai eszköz nem jelent segítséget.

[29] Egy alternatív megfogalmazás az operátorok (operators) egy halmaza, amelyeket egy állapotra alkalmazva lehet az utódállapotokat generálni.

[30] A negatív költségek következményeivel a 3.17. feladatban foglalkozunk.