12.7. Multiágens tervkészítés

Eddig egyágenses környezetekkel (single-agent enviroments) foglalkoztunk, amelyben az ágensünk egyedül van. Amikor más ágensek is jelen vannak a környezetben, az ágensünk egyszerűen hozzáveheti őket a környezetről alkotott modelljéhez, az alapvető algoritmusainak módosítása nélkül. Sok esetben azonban ez gyenge teljesítményhez vezetne, mert többi ágenssel való foglalkozás nem azonos a környezet kezelésével. Nevezetesen, a természet (feltételezhetően) közömbös az ágens szándékait illetően, míg más ágensek nem.[132] Ez az alfejezet ezen kérdések kezelésére a multiágens tervkészítést mutatja be.

A 2. fejezetben láthattuk, hogy a multiágens környezetek lehetnek együttműködők (cooperative) vagy versengők (competitive). Egy nagyon egyszerű kooperatív példával kezdünk: egy páros teniszcsapat tervkészítésével. Olyan tervek alkothatók, amelyek a csapat mindkét játékosának a cselekvéseit meghatározzák. Az ilyen tervek hatékony elkészítéséhez használható technikákat mutatjuk be. A hatékony tervkészítés hasznos, de nem garantálja a sikert. Az ágenseknek egyet kell érteniük a felhasznált tervben! Ez valamilyen koordinációt (coordination) feltételez, amit valószínűleg kommunikációval (communication) érhetünk el.

12.7.1. Kooperáció: közös célok és tervek

A páros teniszt játszó ágenscsapatoknak közös céljuk van, a meccs megnyerése, ami különböző részcélokat eredményez. Tegyük fel, hogy a játék egy pontján a közös céljuk az átütött labda visszaadása úgy, hogy legalább egyikőjük a hálót védi. Ezt a gondolatot egy multiágens tervkészítési (multiagent planning) problémával írhatjuk le, amint azt a 12.23. ábra is mutatja.

12.23. ábra - A páros tenisz probléma. Két ágens együtt játszik, és négy pozíció egyikében lehetnek: [Bal, Alapvonal], [Jobb, Alapvonal], [Bal, Háló] és [Jobb, Háló]. A labda visszaadható, ha pontosan egy játékos van a megfelelő helyen.
A páros tenisz probléma. Két ágens együtt játszik, és négy pozíció egyikében lehetnek: [Bal, Alapvonal], [Jobb, Alapvonal], [Bal, Háló] és [Jobb, Háló]. A labda visszaadható, ha pontosan egy játékos van a megfelelő helyen.

Ez a jelölésrendszer két újdonságot vezet be. Először az Ágens(A, B) deklarálja, hogy két ágensünk van, A és B, akik a tervben szerepelnek. (Ebben a problémában a szemben álló játékosokat nem ágensnek vesszük.) Másodszor minden cselekvés az ágenst explicit módon, mint egy paramétert említi, mert pontosan követnünk kell, melyik ágens mit csinál.

A multiágens tervkészítési probléma megoldása egy együttes terv (joint plan), amely minden ágenshez tartalmaz cselekvéseket. Az együttes terv egy megoldás, ha a célt elérjük azáltal, hogy mindegyik ágens végrehajtja a számára kijelölt cselekvéseket. A következő terv a tenisz probléma egy megoldása :

Terv1:

A: [Megy(A, [Jobb, Alapvonal]), Üt(A, Labda)]

B: [NoOp(B), NoOp(B)]

Ha mindkét ágens ugyanazzal a tudásbázissal rendelkezne, és ez lenne az egyetlen megoldás, akkor minden rendben lenne; minden ágens meghatározná a megoldást, és együttesen végrehajtanák. Az ágensek számára sajnálatos (és hamarosan látni fogjuk, hogy ez miért sajnálatos), hogy van egy másik terv is, ami az elsőhöz hasonlóan kielégíti a célt:

Terv 2:

A: [Megy(A, [Bal, Háló]), NoOp(A)]

B: [Megy(B, [Jobb, Alapvonal]), Üt(B, Labda)]

Ha az A a 2. tervet választja, és B az 1-et, akkor senki sem fogja visszaadni a labdát. Fordítva, ha A az 1-et és B a 2-t választja, akkor várhatóan összeütköznek egymással, senki nem adja vissza a labdát, és a háló is fedezetlenül marad. Ezért a helyes együttes terv létezése nem jelenti, hogy a célt el is érjük. Az ágenseknek szükségük van egy koordinációs (coordination) mechanizmusra, hogy ugyanazt az együttes tervet érjék el, sőt mi több, az ágensek közös tudással is kell rendelkezzenek (lásd 10. fejezet) arról, hogy melyik együttes tervet hajtják végre.

12.7.2. Többtestű tervezés

Ez az alfejezet a megfelelő együttes tervek megalkotására fókuszál, elodázva egyelőre a koordinációs kérdéskört. Ezt többtestű tervkészítésnek (multibody plannining) nevezzük, és tulajdonképpen az a tervkészítési probléma, mellyel egy egyedülálló centralizált ágens áll szemben, mely cselekvéseket diktálhat minden fizikai entitásnak. Egy valóban multiágens esetben ez lehetővé teszi minden ágens számára, hogy felderítse melyek a lehetséges együttes tervek, melyek együttes végrehajtása sikeres lenne.

Megközelítésünkben a többtestű tervkészítést a 11.3. alfejezetben bemutatott részben rendezett tervkészítésre alapozzuk. Az egyszerűség kedvéért teljes megfigyelhetőséget feltételezünk. Van még egy kérdés, ami nem merül fel az egyedülálló ágens esetén: a környezet a továbbiakban nem igazán statikus (static), mert a többi ágens cselekedhet, amíg egy bizonyos ágens gondolkozik. Ezért foglalkoznunk kell a szinkronizációval (synchronization). Az egyszerűség kedvéért feltételezzük, hogy minden cselekvés végrehajtási ideje azonos, illetve hogy az összetett terv minden pontján a cselekvések végrehajtása szimultán történik.

Bármely időpontban minden ágens pontosan egy cselekvést hajt végre (beleértve a NoOp(Üres) operátort is). Ezen konkurens cselekvések halmazát együttes cselekvésnek (joint action) nevezzük. A tenisz problémában (12.7.1. szakasz - Kooperáció: közös célok és tervek részben) például a ⟨NoOp(A), Üt(B, Labda)⟩ az A és B ágenseknek egy együttes cselekvése. Egy együttes terv együttes cselekvések részben rendezett gráfja. Például a tenisz probléma második terve az együttes cselekvések következő sorozatával írható le:

Megy(A, [Bal, Háló]), Megy(B, [Jobb, Alapvonal])⟩

NoOp(A), Üt(B, Labda)⟩

Végrehajthatnánk a tervkészítést a hagyományos részben rendezett tervkészítő algoritmussal, azt az összes lehetséges együttes cselekvés halmazára futtatva. Az egyetlen probléma a halmaz mérete: 10 cselekvéssel és 5 ágenssel 105 együttes cselekvést kapunk. Elég unalmas lenne az összes cselekvés előfeltételét és következményét helyesen definiálni, és nem lenne hatékony egy ilyen nagy halmazzal tervezni.

Egy másik lehetőség az együttes cselekvések implicit definiálása úgy, hogy minden egyes cselekvéshez leírjuk, hogy milyen kölcsönhatásban áll a többi lehetséges cselekvéssel. Ez egyszerűbb lenne, hiszen a legtöbb cselekvés független a legtöbb másiktól, ezért csak azon néhány cselekvést kellene listáznunk, amelyek valójában kölcsönhatásban vannak. Ezt a hagyományos STRIPS vagy ADL cselekvésleírások egy új tulajdonsággal való kiterjesztésével tehetjük meg: ez a konkurens cselekvések listája (concurrent action list). Ez nagyon hasonlít a cselekvés leírásában szereplő előfeltételhez, kivéve, hogy az állapotváltozók leírása helyett ez cselekvéseket ír le, amelyeket egyszerre kell, vagy éppen nem szabad egyszerre végrehajtani. Például a Találat cselekvés a következőképpen írható le:

Cselekvés(Üt(A, Labda),

Konkurens:†t(B, Labda)

Előfeltétel:Megközelít(Labda, [x, y]) ∧ Ott(A, [x, y])

Következmény:Visszaadott(Labda))

Itt egy tiltó egyidejűségi megkötésünk van, azaz az Üt cselekvés végrehajtása alatt egy másik ágens nem hajthat végre egy másik Üt cselekvést. Hasonlóképpen megkövetelhetünk egyidejű cselekvést. Például amikor két ágensre van szükség egy üdítőkkel teli hűtőtáska teniszpályához cipeléséhez. Ezen cselekvés leírása azt fejezi ki, hogy az A ágens nem hajthatja végre a Cipel cselekvést, hacsak nincs egy másik B ágens, aki egyidejűleg egy Cipel cselekvést hajt végre ugyanazon hűtőtáskával:

Cselekvés(Cipel(A, hűtőtáska, itt, ott),

Konkurens:Cipel(B, hűtőtáska, itt, ott)

Előfeltétel:Ott(A, itt) ∧ Ott(Hűtőtáska, itt) ∧ Hűtőtáska(hűtőtáska)

Következmény:Ott(A, ott) ∧ Ott(hűtőtáska, ott)

∧ ¬Ott(A, itt) ∧ ¬Ott(hűtőtáska, itt))

Ezen reprezentáció segítéségével a részben rendezett tervkészítőhöz nagyon közeli tervkészítő hozható létre. Mindössze három különbség van:

  1. Az AB temporális rendezési relációt kiegészítendő megengedjük az A = B-t és az -t, ami „egyidejűséget”, illetve „megelőzőséget vagy egyidejűséget” jelent.

  2. Amikor egy új cselekvés egyidejű cselekvéseket igényel, példányosítani kell ezen cselekvéseket a terv új vagy létező cselekvéseinek felhasználásával.

  3. A tiltottan egyidejű cselekvések a megkötések újabb forrásai. Minden megkötést fel kell oldani az ütköző cselekvések egymás elé vagy mögé rendelésével.

Ez a reprezentáció a többtörzsű problémakörökhöz alkalmazott, részben rendezett tervkészítővel ekvivalens. Kiterjeszthetnénk ezt a megközelítést az utolsó két fejezet finomításaival – HFH-ek részleges megfigyelhetőség, feltételek, végrehajtás-monitorozás és újratervezés –, de ez túlmutat a könyv célkitűzésein.

12.7.3. Koordináló mechanizmusok

A legegyszerűbb módszer, amivel ágensek egy csoportja biztosíthatja az egyetértést egy együttes tervben, hogy egy konvenciót (convention) fogadnak el az együttes cselekvés megkezdése előtt. A konvenció az együttes tervek közötti választásra vonatkozó bármely olyan megkötés, amely túlmutat az alapmegkötésen, amely szerint egy együttes tervnek működni kell, ha minden ágens alkalmazza. Például a „maradj a saját térfeleden” konvenció a páros partnereket a második terv kiválasztására sarkallja, míg az „egy játékos mindig a hálónál marad” konvenció az egyes tervhez vezetné őket. Néhány konvenció, mint az út megfelelő oldalán való vezetés, olyan széles körben elterjedt, hogy ezeket már társadalmi törvényszerűségekként (social laws) kezeljük. Az emberi nyelvek szintén konvencióknak tekinthetők.

Az előző alfejezet konvenciói alkalmazási terület specifikusak és a cselekvésleírások megkötéseivel implementálhatók, amelyekkel kizárjuk a konvenciók megszegéseit. Egy általánosabb megközelítés, hogy problémakör-független konvenciókat használjunk. Például ha mindegyik ágens ugyanazon többtestű tervkészítő algoritmust futtatja ugyanazon bemenetekkel, követi azt a konvenciót, miszerint az elsőként megtalált, használható összetett tervet hajtsa végre, miközben biztos benne, hogy a többi ágens ugyanezzel a választással él. Egy sokkal robusztusabb, de jóval költségesebb stratégia lenne az összes összetett terv elkészítése, majd az ebből való választás (mondjuk annak kiválasztása, amelynek leírt reprezentációja ábécé-sorrendben az első).

Konvenciók szintén adódhatnak a folyamatok evolúciós fejlődésével. Például a közösségben élő rovarok nagyon kidolgozott összetett terveket hajtanak végre, melyeket a kolónia egyedeinek közös genetikus összeállítása biztosít. Az azonosságot szintén nyomatékosítja a tény, hogy a konvencióktól való eltérés csökkenti az evolúciós alkalmasságot, így bármely alkalmazható összetett terv stabil egyensúlyi helyzetet eredményezhet. Hasonló megfontolások alkalmazhatók az emberi nyelv fejlődésére, ahol nem az a fontos, hogy egyes személyek milyen nyelvet beszélnek, hanem az a tény, hogy minden személy ugyanazt a nyelvet beszéli.

Egy utolsó példa a madarak gyülekezési viselkedése. Megfelelő szimulációt nyerhetünk, ha minden egyes madár ágens (melyet néha madaroidnak vagy roidnak (boid) nevezünk) a következő három szabályt követi valamilyen kombináció alapján:

  1. Különválás: távolodjunk el a szomszédoktól, amikor túl közel kerülünk;

  2. Kohézió: kerüljünk átlagos távolságra a szomszédainktól;

  3. Irányultság: kerüljünk a szomszédokhoz képest átlagos orientációba (haladási irányba).

Ha minden madár azonos szabályrendszert hajt végre, a csapat repülése egy kialakuló viselkedést (emergent behavior) mutat, hasonlóan egy nagyjából azonos sűrűségű pszeudomerev test viselkedéséhez, amely nem bomlik fel az idő során. Mint a bogaraknál, itt sincs szükség arra, hogy minden ágens ismerje a teljes összetett tervet, ami a többi ágens cselekvését modellezi.

A konvenciók ahelyett, hogy minden egyes új problémához kifejlesztenénk őket, tipikusan egyedi multiágens tervkészítő problémák egy egész csoportjához készülnek. Ez rugalmatlansághoz és hibához vezethet, amit néha láthatunk, ha a páros tenisz játszmában a labda nagyjából azonos távolságra van a két partner között. Egy alkalmazható konvenció hiányában az ágensek kommunikálhatnak (communication), hogy egy közös tudást érjenek el az alkalmazható összetett tervből. Például a teniszpáros egy játékosa felkiálthat „Enyém!” vagy „Tiéd!”, hogy jelezze a preferált tervet. A kommunikációs mechanizmusokat nagyobb mélységben a 22. fejezetben tárgyaljuk, ahol megfigyelhetjük, hogy a kommunikáció nem szükségszerűen szóbeli információcserét jelent. Például egy játékos úgy is közölheti az általa előnyben részesített összetett tervét a másikkal, hogy végrehajtja annak kezdő részletét. A teniszjátszma problémánkban, ha az A ágens elindul a hálóhoz, akkor a B ágens rákényszerül, hogy visszamenjen az alapvonalhoz megütni a labdát, mivel a második terv az egyetlen összetett terv, ami A hálóhoz mozgásával kezdődik. Ez az irányítási megközelítés, amelyet gyakran a terv felismerésének (plan recognition) nevezünk, akkor működik, ha egyetlen cselekvés (vagy cselekvések rövid sorozata) elegendő, hogy egyértelműen azonosítsuk az összetett tervet.

Azt a terhet, amely biztosítja, hogy az ágensek egy sikeres összetett tervhez jussanak, vagy az ágensek készítőire, vagy magukra az ágensekre helyezhetjük. Az első esetben mielőtt az ágensek tervezni kezdenének, az ágens készítőjének bizonyítania kell, hogy az ágensek szabályai és stratégiái sikeresek lesznek. Az ágensek önmagukban lehetnek reaktívak, amennyiben ez működik az őket körülvevő környezetben, valamint ha nem kell, hogy pontos modelljük legyen a többi ágensről. Az utóbbi esetben az ágensek megfontoltak: bizonyítaniuk vagy demonstrálniuk kell, hogy a tervük hatékony lesz, figyelembe véve a többi ágens megfontolásait. Például egy A és B logikai ágenst tartalmazó környezetben mindketten rendelkezhetnek a következő definícióval:

p, s Megfelelő(p, s) ⇔ KözösTudás({A, B}, Eléri(p, s, Cél))

Ez azt mondja, hogy bármely s szituációban, a p terv egy alkalmazható összetett terv, ha az ágensek közösen tudják, hogy a p eléri a célt. További axiómákra van szükségünk, hogy biztosítsuk egy adott összetett terv végrehajtására vonatkozó közös szándék (joint intention) együttes ismeretét. Az ágensek csak ebben az esetben kezdhetnek cselekedni.

12.7.4. Versengés

A többágenses környezeteknek nem mindegyike áll együttműködő ágensekből. Az egymásnak ellentmondó működésű ágensek versenyben (competition) vannak egymással. Erre egy példát jelentenek a két játékost igénylő, de zérus összegű játékok, mint amilyen a sakk. A 6. fejezetben láthattuk, hogy a sakkozó ágensnek figyelembe kell vennie az ellenfél következő néhány lehetséges lépését is. Azaz egy versengő környezetben levő ágensnek (a) fel kell ismernie, hogy vannak más ágensek, (b) meg kell határoznia a többi ágens lehetséges terveit, (c) meg kell határoznia, hogy a többi ágens hogyan tervezi a saját terveivel való kölcsönhatást, és (d) el kell döntenie, hogy ezek fényében mi a legjobb cselekvés. A versengés, hasonlóan az együttműködéshez, a többi ágens tervének modelljét igényli. Másrészről, egy versengő környezetben nincs elhatározás egy összetett terv mellett.

A 12.4. alfejezet felvázolta a játékok és a feltételes tervkészítési problémák közötti analógiát. A 12.10. ábrán szereplő feltételes tervkészítő algoritmus olyan tervet készít, amely a környezetről a legrosszabb esetet feltételezve is működik, így olyan versenyhelyzetekben is alkalmazható, ahol az ágenst csak a siker vagy a bukás érdekli. Amikor az ágens és ellenfelei a terv költségeivel is foglalkoznak, akkor a minimax megoldás a helyénvaló. Eddig nagyon kevés munkát fordítottak a minimax módszer olyan módszerekkel való kombinálására, mint a részben rendezett tervkészítés vagy a HFH-tervkészítés, ami túlmutat a 6. fejezetben használt állapottér-keresési modellen. A versengés kérdésére a játékelmélettel foglalkozó 17.6. alfejezetben még visszatérünk.



[132] Nem biztos, hogy az Egyesült Királyság lakói, ahol egy pikniknek már pusztán a tervezése is esőt garantál, egyetértenek ezzel.