A teljes megfigyelhetőség jelentése, hogy az ágens mindig ismeri az aktuális állapotot. Nemdeterminisztikus környezet esetén azonban, az ágens nem képes megjósolni a cselekvéseinek kimenetelét. A feltételes tervkészítő ágens a nemdeterminisztikusságot úgy kezeli, hogy a tervekbe feltételes lépéseket épít be (tervkészítési időben), amelyek ellenőrzik a környezet állapotát (futási időben), hogy a továbbiakról dönthessen. A kérdés tehát, hogyan készíthetők el az ilyen feltételes tervek.

Példaként a porszívóvilág (vacuum word) problémakört használjuk, amelynek állapotterét a determinisztikus esetre a 3.2. szakasz - Példaproblémák részben fektettük le. Emlékezzünk vissza, hogy a Balra, a Jobbra és a Szív a rendelkezésre álló cselekvések. Szükségünk lesz néhány propozícióra, hogy definiáljuk az állapotokat: legyen az OttBal (OttJobb) igaz, ha az ágens a bal (jobb) állapotban van, és legyen a TisztaBal (TisztaJobb) igaz, ha a bal (jobb) állapot tiszta.^[122] Az első feladatunk a STRIPS nyelv kiterjesztése, hogy megengedje a nemdeterminisztikusságot. Ennek érdekében megengedjük a cselekvésekben a diszjunktív következményeket (disjunctive effects), ami azt jelenti, hogy egy cselekvést bármikor végrehajtva annak kettő vagy több különböző kimenetele is lehet. Tegyük fel például, hogy a Balra lépés néha sikertelen. Ekkor a

Cselekvés(Balra, Előfeltétel:OttJobb, Következmény:OttBal ∧ ¬OttJobb)

normál cselekvésleírást módosítanunk kell, hogy diszjunktív következményt is tartalmazzon:

Cselekvés(Balra, Előfeltétel:OttJobb, Következmény:OttBal ∨ OttJobb) (12.1)

Szintén hasznosnak találjuk a feltételes következményeket (conditional effects), amikor is egy cselekmény következménye függ attól az állapottól, amelyben végrehajtjuk. A feltételes következmények a cselekvés KÖVETKEZMÉNY részében jelennek meg a „when <feltétel>: <következmény>” szintaxissal. Például a Szív cselekvés modellezésére a

Cselekvés(Szív, Előfeltétel:, Következmény:(when OttBal: TisztaBal)

∧ (when OttJobb: TisztaJobb))]

kifejezést írnánk fel. A feltételes következmények nem vezetik be a nemdeterminisztikusságot, de segítséget nyújtanak annak modellezésében. Tegyük fel például, hogy egy körmönfont porszívónk van, ami néha, ha mozog, piszkot szór a célnégyzetre, de csak akkor, ha az tiszta. Ez a

Cselekvés(Balra, Előfeltétel:OttJobb, Következmény:OttBal

∨ (OttBal ∧ (when TisztaBal: ¬TisztaBal))

leírással modellezhető, ami mind diszjunktív, mind pedig feltételes.^[123] Hogy feltételes terveket készíthessünk, feltételes lépésekre (conditional steps) van szükségünk. Ezeket az „if <teszt> then terv_A else terv_B” szintaxis használatával írjuk le, ahol a <teszt> egy kétértékű függvénye az állapotváltozóknak. Az „if OttBal ∧ TisztaBal then Jobbra else Szív” például a porszívóvilág egy feltételes lépése lehet. Egy ilyen lépés végrehajtása a kézenfekvő módon történik. A feltételes lépések egymásba ágyazásaival a tervek fák lesznek.

A feltételes tervektől elvárjuk, hogy működjenek, függetlenül attól, hogy valójában a cselekvés mely kimenetele következik be. Ezzel a problémával egy másik köntösbe bújtatva már találkoztunk korábban. A kétszemélyes játékokban (lásd 6. fejezet) olyan lépéseket szeretnénk, amelyek az ellenfél lépéseitől függetlenül győzelemhez vezetnek. A nemdeterminisztikus tervkészítési problémákat ezért gyakran természet elleni játékoknak (games against nature) nevezik.

Vegyük a porszívóvilág egy speciális példáját. A kiinduló állapotban a robot a tiszta világ jobb oldali négyzetén van. Mivel a környezet teljesen megfigyelhető, az ágens ismeri a teljes OttJobb ∧ TisztaBal ∧ TisztaJobb állapotleírást. A célállapotban a robot a tiszta világ bal oldali négyzetén van. Ez a feladat elég triviális lenne, ha nem a „dupla-Murphy” porszívóval lenne dolgunk, amely néha piszkot hagy maga után, amikor egy tiszta célnégyzetre lép, és néha bepiszkolja a tiszta négyzetet, ha a Szívás cselekvés végrehajtódik.

Ennek a környezetnek a „játékfáját” a 12.9. ábrán mutatjuk be. A cselekvéseket a robot a fa „állapot” csomópontjaiban hajtja végre, majd a körrel jelölt „valószínűségi” csomópontokban a természet dönt a cselekvés kimeneteléről. A megoldás egy részfa, mely (1) minden levelében egy cél csomópontot tartalmaz, (2) minden „állapot” csomóponthoz egy cselekvést specifikál, és (3) minden „valószínűségi” csomópontban tartalmazza az összes kimenetelhez tartozó ágat. Az ábrán a megoldást vastag vonallal jelöltük, ami a [Balra, if OttBal ∧ TisztaBal ∧ TisztaJobb then [] else Szív] tervnek felel meg. (Mivel állapottér-tervkészítőt használunk, a feltételes lépésekben használt tesztek egyelőre teljes állapot leírások.)

12.9. ábra - A „dupla-Murphy” porszívóvilág keresési fájának első két szintje. Az állapotcsomópontokban és a VAGY csomópontokban cselekvéseket kell választani. A valószínűségi csomópontok, amelyeket körökkel jelöltünk ÉS csomópontok, ahol, ahogy azt a kimenő ágakon szereplő ív is jelöli, minden kimenetelt kezelni kell. A megoldást vastag vonallal jelöltük.

A játékok pontos megoldásához a minimax algoritmust használjuk (lásd 6.3. ábra). Ehhez a feltételes tervkészítésben tipikusan két módosítás tartozik. Először is, a MAX és a MIN csomópontok VAGY és ÉS csomópontokká válhatnak. Nyilvánvalóan a tervnek minden elért állapotban választania kell valamilyen cselekvést, de kezelnie kell ezen cselekvés minden kimenetelét. Másodszor, az algoritmusnak nemcsak egy lépést kell megadnia, hanem egy feltételes tervet kell készítenie. Egy VAGY csomópontban a terv egyszerűen a választott cselekvés, amelyet bármi követhet. Egy ÉS csomópontban a terv if-then-else lépések egymásba ágyazott sorozata, melyek minden lehetséges kimenetelhez egy résztervet adnak meg. Ezen lépésekben a feltétel vizsgálatokban teljes állapotleírások szerepelnek.^[124]

12.10. ábra - Egy algoritmus a nemdeterminisztikus környezetek által generált ÉS-VAGY gráfok keresésére. Feltételezzük, hogy az ÁLLAPOTÁTMENET függvény a cselekvések egy listáját adja vissza, melyek mindegyike egy lehetséges kimenetel halmazhoz tartozik. A cél egy feltételes terv megtalálása, ami bármilyen körülmények között elér egy célállapotot.

Formálisan az eddig definiált keresési tér egy és-vagy gráf. Az ÉS-VAGY gráfok korábban a 7. fejezetben az ítéletlogikai Horn-klóz következtetésben jelentek meg. Itt az ágak logikai következtető lépések helyett cselekvések, de az algoritmus azonos. A 12.10. ábra az ÉS-VAGY gráfok keresésére egy rekurzív, mélységi kereső algoritmust ad meg.

A bemutatott algoritmusban kulcsfontosságú a nemdeterminisztikus tervkészítési problémákban gyakran felmerülő ciklusok kezelésének módja (például ha egy cselekvésnek néha nincs következménye vagy egy helytelen következmény kijavítható). Ha az aktuális állapot azonos a gyökértől idáig vezető útvonal egy állapotával, akkor hibával tér vissza. Ez nem jelenti, hogy nincs megoldás az aktuális állapotból, egyszerűen annyit jelent, hogy van egy nemciklikus megoldás, ami elérhető az aktuális állapot korábbi előfordulásából, így az állapot újabb bekövetkezése kihagyható. Ezzel az ellenőrzéssel biztosítjuk, hogy az algoritmus minden véges állapottér esetén leálljon, mivel minden útvonal célt ér, zsákutcába jut, vagy egy állapot ismétlése. Vegyük észre, hogy az algoritmus nem ellenőrzi, hogy az aktuális állapot egy másik útvonalon szereplő állapot ismétlése-e. A 12.15. feladat ezt a kérdést járja körül.

12.11. ábra - A „tripla-Murphy” porszívóvilág keresési gráfjának első szintje, ahol a ciklusokat explicit megjelöltük. A probléma összes megoldása ciklikus terv.

Az ÉS-VAGY-GRÁF-KERESÉS által visszaadott tervek feltételes lépéseket tartalmaznak, melyek a teljes állapotleírást megvizsgálják, hogy egy ágról döntsenek. A legtöbb esetben ennél jóval kevésbé kimerítő ellenőrzésekkel is megúszhatjuk. Például a 12.9. ábrán látható megoldás a [Balra, if TisztaBal then [] else Szív] megadással egyszerűen leírható. Ennek oka, hogy a TisztaBal teszt elegendő, hogy az ÉS csomópont állapotait két egyelemű halmazba sorolja úgy, hogy a tesztek után az ágens pontosan ismerje az állapotát. Valójában az egyváltozós if-then-else tesztek sorozata mindig elegendő, hogy állapotok egy halmazát egyelemű halmazokra ossza, feltéve, hogy az állapot teljesen megfigyelhető. Ezért az általánosság teljes megőrzése mellett a teszteket egyváltozós tesztekre szűkíthetjük.

Az utolsó nehézség, ami gyakran felmerül a nemdeterminisztikus feladatkörökben, a következő: a dolgok nem mindig működnek elsőre, így újra kell próbálkozni. Vegyük például a „tripla-Murphy” porszívó példáját, mely (a korábban bemutatott szokások mellett) néha nem mozdul az utasítás ellenére. Például csakúgy, mint a (12.1) egyenletben, a Balra cselekvés tartalmazhatja a OttBal ∨ OttJobb diszjunktív hatást. Ekkor a [Balra, if TisztaBal then [] else Szív] terv már nem garantált, hogy működik. A 12.11. ábra a keresési gráf egy részletét mutatja. Tisztán látható, hogy a továbbiakban nincsenek ciklusmentes megoldások, és az ÉS-VAGY-GRÁF-KERESÉS hibával térne vissza. Létezik azonban egy ciklikus megoldás (cyclic solution), ami addig próbálgatja a Balra lépést, mígnem egyszer működik. Ez a megoldás könnyebben kifejezhető, ha a terv egy részét egy címkével (label) jelöljük meg, és a terv ismételgetése helyett erre a címkére hivatkozunk. Így a ciklikus megoldásunk

[L1 : Balra, if OttJobb then L1 else if TisztaBal then [] else Szív]

alakú. (A „while OttJobb do Balra” kifejezés egy jobb szintaxis a terv ciklikus részére.) Az ÉS-VAGY-GRÁF-KERESÉS-ben szükséges módosításokat a 12.16. feladat dolgozza fel. A megvalósítás kulcsa, hogy az állapottérben egy L állapotba visszalépő hurok a tervben egy arra a pontra visszamutató hurkot jelent, ahol az L állapotba vezető résztervet végrehajtjuk.

Így már képesek vagyunk feltételeket és ciklusokat tartalmazó programokhoz hasonlatos összetett tervek létrehozására. Sajnos ezek a ciklusok végtelen ciklusok lehetnek. Például a tripla-Murphy világ cselekvés reprezentációjában a semmi jelentése, hogy a Balra szükségszerűen sikeres. A ciklikus tervek ezért kevésbé előnyösek, mint a ciklus nélküliek, de megoldásnak tekinthetők, amennyiben minden levél egy célállapot, és a terv minden pontjából elérhető egy levél.

Az előző alfejezet teljesen megfigyelhető környezetekkel foglalkozott, amelyek előnye, hogy a feltételes ellenőrzések bármit kérdezhetnek, és biztosak lehetnek a választ kapnak. A valódi világban a részleges megfigyelhetőség jóval gyakoribb. Egy részlegesen megfigyelhető tervkészítési feladat kiinduló állapotában az ágens csak bizonyos dolgokat tud az aktuális állapotról. Ennek a helyzetnek a legegyszerűbb modellezése, ha a kiinduló állapotról annyit mondunk, hogy egy állapothalmazba tartozik. Az állapothalmaz az ágens kiinduló hiedelmi állapotát (belief state) írja le.^[125]

Tegyük fel, hogy a porszívóvilág ágens tudja, hogy a jobb oldali négyzeten van, és az tiszta, de nem tudja érzékelni a piszok jelenlétét vagy hiányát a többi négyzeten. Ekkor, legjobb ismeretei szerint két állapotban lehet: a bal oldali négyzet vagy piszkos, vagy tiszta. Ezt a hiedelmi állapotot a 12.12. ábrán A-val jelöltük. Az ábra a „váltakozó dupla-Murphy” porszívóvilág ÉS-VAGY gráfjának egy részét mutatja be, melyben a tiszta négyzetet elhagyó ágens piszkot hagyhat maga után.^[126] Ha a világ teljesen megfigyelhető volna, az ágens egy „Mozogj balra és jobbra, és szívd fel a piszkot, amennyiben találsz, amíg mindkét kocka tiszta nem lesz, és a bal oldali kockán vagyok” formájú ciklikus megoldást készíthetne (lásd 12.16. feladat). Sajnos csak lokális szemétérzékeléssel ez a terv végrehajthatatlan, hiszen a „mindkét kocka tiszta” teszt igazságértéke nem határozható meg.

Figyeljük meg az ÉS-VAGY gráf felépítését. Az A hiedelmi állapotból a Balra mozgás kimenetelét mutatjuk. (A többi cselekvésnek nincs értelme.) Mivel az ágens piszkot hagyhat maga után, a két kiinduló világból négy lehetséges világ adódhat, ahogy az a B és C állapotokban látható. A rendelkezésre álló érzékelő információk alapján a világ két különálló hiedelmi állapotra osztható.^[127] A B-ben, az ágens tudása a TisztaBal, míg C-ben a ¬TisztaBal. A piszok feltakarítása C-ben az ágenst a B-be mozgatja. A B-ből a jobbra mozgás vagy hagy piszkot maga után, vagy nem, így az ágensnek azon tudása alapján, hogy TisztaJobb igaz (vissza az A-ra) vagy hamis (D hiedelmi állapot), ismét négy lehetséges világ adódik.

Összegezve a nemdeterminisztikus, részben megfigyelhető környezetek a hiedelmi állapotok egy ÉS-VAGY gráfját eredményezik. Ebből adódóan feltételes tervek találhatók pontosan ugyanazon algoritmusokkal, mint a teljesen megfigyelhető esetben, nevezetesen az ÉS-VAGY-GRÁF-KERESÉS-sel. Ez abból is könnyen megérhető, ha belátjuk, hogy az ágens hiedelmi állapota mindig teljesen megfigyelhető, azaz mindig tudja, hogy mit tud. A „hagyományos” teljesen megfigyelhető problémamegoldás csak egy speciális eset, melyben minden hiedelmi állapot egy egyelemű halmaz, pontosan egy fizikai állapottal.

12.12. ábra - A „váltakozó dupla-Murphy” porszívóvilág ÉS-VAGY gráfjának egy részét mutatja be, melyben a tiszta négyzetet elhagyó ágens piszkot hagyhat maga után. Az ágens nem tudja érzékelni a más négyzetben levő piszkot.

Ezzel készen vagyunk? Nem egészen! Még meg kell határoznunk, hogy hogyan reprezentáljuk a hiedelmi állapotokat, hogyan működik az érzékelés, és hogy ebben az új helyzetben hogyan írjuk le a cselekvéseket.

A hiedelmi állapotok esetén alapvetően három választásunk van:

{(OttJobb ∧ TisztaJobb ∧ TisztaBal), (OttJobb ∧ TisztaJobb ∧ ¬TisztaBal)}

Ezzel a leírással könnyű dolgozni, de nagyon költséges: ha n kétértékű ítéletállítás definiál egy állapotot, akkor a hiedelmi állapot O(2ⁿ) fizikai állapotleírást tartalmazhat, melyek mindegyike O(n) méretű. Ha az ágens az ítéletállításoknak csak egy töredékét ismeri, exponenciálisan nagy hiedelmi állapotok adódnak — minél kevesebbet tud, annál több lehetséges állapotban lehet.

OttJobb ∧ TisztaJobb

formában adható meg. Nyilvánvaló, hogy bármely hiedelmi állapot pontosan befoglalható egyetlen logikai mondatba. Ha akarjuk, az összes konjuktív állapotleírás diszjunkcióját vehetjük, de a példánk mutatja, hogy ennél tömörebb mondatok létezhetnek.

Az általános logikai mondatok egyik hátulütője, hogy mivel sok ekvivalens, de különböző logikai mondat írhatja le ugyanazt a hiedelmi állapotot, az ismétlődő állapotok ellenőrzése általános tételbizonyító képességeket vár el a gráfkereső algoritmustól. Ezért a mondatok egy kanonikus reprezentációját szeretnénk, amelyben minden hiedelmi állapot pontosan ugyanannak a mondatnak felel meg.^[128] Egy ilyen reprezentáció, azaz ítéletállítások nevei alapján rendezett literálok konjukcióját használja, melynek egy példája a ¬OttJobb ∧ TisztaJobb. Ez a 11. fejezet nyílt világ feltételezésében (open-world assumption) egy egyszerű állapotleírás. Nem minden logikai mondat írható fel ilyen alakban (például nincs mód az OttBal ∨ TisztaJobb felírására), de számos probléma kezelhető.

K(OttJobb) ∧ K(TisztaJobb)

ahol K jelentése „tudja” és K(P) jelentése, hogy az ágens tudja, hogy P igaz.^[129] A tudás ítéletállításokkal zárt világ feltételezést használunk, azaz ha egy állítás nem jelenik meg a listában, akkor hamisnak feltételezzük. Például a ¬K(TisztaBal) és a ¬K(¬TisztaBal) implicit szerepelnek a fenti mondatban, így az rögzíti a tényt, hogy az ágens érzéketlen a TisztaBal igazságértékére.

Kimutatható, hogy a második és harmadik lehetőségek durván azonosak, de mi a harmadik tudás, az ítéletállítás lehetőséget használjuk, mert ez az érzékelés egy erősebb leírását adja, és mert már tudjuk, hogy hogyan írhatunk a zárt világ feltételezés (closed-world assumption) mellett STRIPS kifejezéseket.

Most arról kell döntenünk, hogy az érzékelés hogyan működik. Itt két választásunk van. Használhatunk automatikus érzékelést (automatic sensing), ami annyit tesz, hogy az ágens minden időlépésben az összes elérhető érzetet megkapja. A 12.12. ábrán látható példa a helyzet és a helyi tisztaság meghatározására automatikus érzékelést feltételez. Használhatunk ellenben aktív érzékelést (active sensing), ami annyit jelent, hogy az érzékelt információk csak megadott érzékelési cselekvések (sensory actions), (mint TisztaságEllenőrzés és PozícióEllenőrzés) végrehajtásával nyerhetők. Az érzékelési típusokat sorban tárgyalni fogjuk.

Most használjunk tudás állításokat a cselekvések leírásához. Tegyük fel, hogy az automatikus helyi tisztaságérzékeléssel felruházott váltakozó-dupla-Murphy világ problémában az ágens Balra lép. Az erre a világra vonatkozó szabályoknak megfelelően az ágens hagy, vagy talán nem hagy piszkot maga után, ha a négyzet tiszta volt. Mint fizikai következmény, ez diszjunktív lenne, de mint tudás következmény ez egyszerűen törli az ágens TisztaJobb tudását. Emellett az ágens a helyi piszokérzékelés miatt így vagy úgy tudni fogja, hogy vajon a TisztaBal igaz-e, és tudni fogja, hogy a pozíciója OttBal:

Cselekvés(Balra, Előfeltétel:OttJobb,

Következmény:K(OttBal) ∧ ¬K(OttJobb) ∧

when TisztaJobb: ¬K(TisztaJobb) ∧

when TisztaBal: K(TisztaBal) ∧

when ¬TisztaBal: K(¬TisztaBal) (12.2)

Vegyük észre, hogy az előfeltételek és a when feltételek egyszerű állítások és nem tudás állítások. Ez úgy van, ahogy lennie kell, hiszen a cselekvések kimenetele függ az aktuális világtól, de hogyan ellenőrizhetnénk ezen feltételek igazságértékét csupán a hiedelmi állapot alapján? Ha az ágens az aktuális hiedelmi állapotban tudja mondjuk a K(OttJobb) állítást, akkor az állításnak igaznak kell lennie az aktuális fizikai állapotban, így egyben a cselekvés is alkalmazható. Ha az ágens nem ismeri az állítást (például TisztaBal az if feltételt), akkor a hiedelmi állapotnak tartalmaznia kell olyan világokat, melyekben a TisztaBal igaz, és olyan világokat, amelyekben a TisztaBal hamis. Pontosan ez az, ami miatt egy cselekvés többszörös hiedelmi állapotokat eredményez. Így, ha a kiinduló állapot a (K(OttJobb) ∧ K(TisztaJobb)), akkor a Balra lépés után a (K(OttBal) ∧ K(TisztaBal)) és a (K(OttBal) ∧ K(¬TisztaBal)) a két lehetséges hiedelmi állapot. Mindkét esetben ismert a TisztaBal értéke, így a TisztaBal teszt felhasználható a tervben.

Aktív érzékelés (mint az automatikus érzékelés ellentettje) esetén, az ágens csak kérésre kap új megfigyeléseket. Így a Balra lépés után az ágens nem tudja, hogy a bal oldali négyzet piszkos-e, ezért a (12.2) cselekvésleíró egyenletben az utolsó két feltételes következmény már nem jelenik meg. Az ágens a TisztaságEllenőrzés cselekvéssel derítheti ki, hogy a négyzet piszkos-e:

Cselekvés(TisztaságEllenőrzés, Következmény: when OttBal ∧ TisztaBal: K(TisztaBal) ∧

when OttBal ∧ ¬TisztaBal: K(¬TisztaBal) ∧

when OttBal ∧ TisztaJobb: K(TisztaJobb) ∧

when OttBal ∧ ¬TisztaJobb: K(¬TisztaJobb) (12.3)

Könnyű megmutatni, hogy aktív érzékelés esetén a Balra lépéssel követett TisztaságEllenőrzés cselekvés ugyanazt a két hiedelmi állapotot eredményezi, amit az automatikus érzékelés esetén a Balra adott. Aktív érzékelés esetén a fizikai cselekvések egy hiedelmi állapotot mindig egyetlen követő hiedelmi állapotra képeznek le. A többszörös hiedelmi állapotok csak az érzékelő cselekvések által jöhetnek létre, melyek specifikus tudást adnak, s ezért lehetővé teszik a feltételvizsgálatok használatát a tervekben.

Az eddigiekben az állapottér ÉS-VAGY keresésén alapuló feltételes tervkészítésre mutattunk be egy általános megközelítést. Ez a megközelítés néhány tesztproblémán elég hatékonynak bizonyult, de más feladatokra alkalmatlan. Bizonyítható, hogy a feltételes tervkészítés nagyobb algoritmikus komplexitású, mint a hagyományos. Emlékezzünk vissza, hogy az NP osztály definíciója alapján egy megoldásról ellenőrizhető, hogy polinomiális idejű-e. Ez a hagyományos tervekre (legalábbis a polinomiális méretűekre) igaz, így a hagyományos tervkészítés az NP osztályba tartozik. A feltételes tervkészítés esetén egy jelöltre ellenőrizni kell, hogy az összes lehetséges állapotra a tervben létezik-e valamilyen, a célt kielégítő útvonal. Az „összes/valamilyen” összeállítás nem ellenőrizhető polinomiális időben, így a feltételes tervkészítés nehezebb, mint NP. Ez csak úgy kerülhető el, hogy a tervkészítési fázisban figyelmen kívül hagyunk néhány lehetséges eshetőséget, és ezeket csak akkor kezeljük, ha valójában fellépnek. A következő alfejezetben ezt a megközelítést elemezzük.