12.8. Összefoglalás

Ez a fejezet a valódi világban alkalmazott tervkészítés és cselekvés nehézségeivel foglalkozott. Összefoglaljuk a fő megállapításokat.

  • A legtöbb cselekvés erőforrásokat (resources) használ, például pénzt, benzint vagy nyersanyagokat. Ezen erőforrásokat készletekre vonatkozó mérőszámokként célszerű kezelni, mintsem hogy megpróbáljunk következtetni mondjuk a világ minden egyes pénzérméjéről és papírpénzéről. A cselekvések generálhatnak és elfogyaszthatnak erőforrásokat, és rendszerint olcsó és hatékony, ha a további finomítások végrehajtása előtt a részleges terveket ellenőrizzük, hogy az erőforrásokra vonatozó korlátozásokat kielégítik-e.

  • Az idő az egyik legfontosabb erőforrás. Ez speciális ütemező algoritmusokkal kezelhető, vagy az ütemezést integrálhatjuk a tervkészítésbe.

  • A hierarchikus feladat háló (hierarchical task network) (HFH) tervkészítés lehetővé teszi az ágens számára, hogy dekompozíciós szabályok formájában tanácsokat fogadjon el a feladatkör tervezőjétől. Ez lehetővé teszi, hogy nagyon nagy terveket készítsünk, amelyekre számos valódivilág-beli alkalmazáshoz szükség van.

  • A hagyományos tervkészítő algoritmusok teljes és helyes információt és determinisztikus, teljesen megfigyelhető környezetet feltételeznek. A legtöbb problémakörre nem igaz ez a feltételezés.

  • A hiányos információ kezelhető azáltal, hogy érzékelő cselekvéseket tervezünk, amelyekkel megszerezzük a szükséges információt. A feltételes tervek (conditional plans) lehetővé teszik az ágens számára, hogy a végrehajtás során érzékelje a környezetét, hogy eldönthesse, mely ágát követi a tervnek. Néhány esetben érzékelőmentes (sensorless) vagy alkalmazkodó tervkészítés (conformant planning) használható az érzékelést nem igénylő terv elkészítéséhez. Mind az érzékelőmentes, mind pedig a feltételes tervek előállíthatók a hiedelmi állapotok (belief states) terében történő kereséssel.

  • A helytelen információk kielégítetlen előfeltételeket eredményeznek a cselekvések és a tervek számára. A végrehajtás-monitorozás (execution monitoring) a terv sikeres befejezése érdekében érzékeli az előfeltételek megszegéseit.

  • Az újratervező ágens (replanning agent) végrehajtás-monitorozást használ és szükség esetén javításokat szúr be.

  • A folytonos tervkészítő (continuous planning) ágens előrehaladása során új célokat alkot és valós időben reagál.

  • Multiágens (multiagent) tervezésre van szükség, amikor a környezetben más ágensek is találhatók, melyekkel együttműködni vagy versengeni kell, vagy amelyeket koordinálni kell. A többtestű (multibody) tervkészítés az együttes cselekvésleírások hatékony dekompozícióját felhasználva együttes terveket alkot, de ki kell egészíteni valamilyen koordinációval, amennyiben két együttműködő ágensnek egyet kell érteni abban, hogy melyik együttes tervet hajtsák végre.

12.8.1. Irodalmi és történeti megjegyzések

A folytonos idővel való tervkészítést elsőként DEVISER vetette fel (Vere, 1983). Az időnek a tervekben való szisztematikus reprezentációjával Dean és társai dolgoztak a FORBIN rendszerben (Dean és társai, 1990). A NONLIN+ (Tate és Whiter, 1984) és a SIPE (Wilkins, 1988; 1990) kezelni tudta a korlátos erőforrások különböző tervlépésekhez való hozzárendelését. Az O-PLAN (Bell és Tate, 1985) HFH-tervkészítő az idő- és erőforrás-korlátozások egységes és általános reprezentációját tartalmazta. A szövegben említett Hitachi-alkalmazás kiegészítéseképpen, az O-PLAN módszert a Price Waterhouse-ban a szoftverbeszerzési tervkészítéshez alkalmazták, míg a Jaguar Autógyárban a hátsó tengely összeszerelési tervének készítésénél. Számos hibrid tervkészítő és ütemező rendszert alkalmaztak: az ISIS (FOX és társai, 1982; Fox, 1990) egy ütemezési feladatban alkalmazták a Westinghouse-nál, a GARI (Descotte és Latombe, 1985) mechanikus alkatrészek gépesítését és készítését tervezte, a FORBIN-t gyár vezérlésre használták, végezetül a NONLIN+ hajózási logisztikai tervkészítéshez alkalmazták.

Az 1980-as években megindult elméleti munka tetőzése után, napjainkban ismét a temporális tervkészítés kerül előtérbe, amikor az új algoritmusok és a megnövekedett feldolgozási teljesítmény lehetővé tette a gyakorlati felhasználást. A két tervkészítő a SAPA (Do és Kambhampati, 2001) és a T4 (Haslum és Geffner, 2001) előrefelé történő állapottér keresést alkalmaztak, amit az időtartammal és erőforrásokkal rendelkező cselekvések kezeléséhez egy kifinomult heurisztikával egészítettek ki. Egy másik lehetőség a nagyon költséges cselekvésleíró nyelvek használata, melyeket kézzel írt és alkalmazási terület specifikus heurisztikákkal irányíthatunk, amint az az ASPEN (Fukunaga és társai, 1997), a HSTS (Jonsson és társai, 2000) és az IxTeT (Ghallab és Laruelle, 1994) esetén is történik.

Az ütemezés az űrkutatásban nagyon hosszú múltra tekint vissza. A T-SCHED (Drabble, 1990) rendszert az UOSAT–II műhold küldetésvezérlő parancssorozatainak ütemezésére használták. Az O-PLAN-en alapuló OPTIMUM-AIV (Aarup és társai, 1994) és a PLAN-ERS1 (Fuchs és társai, 1990) az űrrepülőgép-összeszerelésben a megfigyelési tervkészítésben használták fel az Európai Űrkutatási Ügynökségnél (ESA).

A SPIKE rendszert (Johnston és Adorf, 1992) a NASA-nál a Hubble-űrteleszkóp megfigyelés-tervezéséhez használták, míg az űrsikló földi feldolgozásütemező rendszer (Deale és társai, 1994) emberi erőforrás ütemezést végez egészen 16 000 munkás-műszak értékig. A Remote Ágens (Muscettola és társai, 1998) lett az első önálló tervkészítő és ütemező, mely űrsiklót vezérelt, mialatt a Deep Space One űrszonda fedélzetén repült 1999-ben. Az emberi erőforrás ütemezés irodalmát Vaessens és társai (Vaessens és társai, 1996) foglalták össze, az elméleti eredményeket Martin és Shmoys (Martin és Shmoys, 1996) jelentette meg.

A STRIPS programban található a macrops – elemi lépések sorozatából álló „makróoperátorok” (macro operators) – tanulásra szolgáló eszköztár, az első hierarchikus mechanizmusnak tekinthető (Fikes és társai, 1972). A hierarchiát szintén alkalmazták a LAWALY rendszerben (Siklossy és Dreussi, 1973). Az ABSTRIPS rendszer (Sacerdoti, 1974) az absztrakciós hierarchia (abstraction hierarchy) ötletét vezette be, ahol a magasabb szintű tervezés megengedte a cselekvések alacsonyabb szintű előfeltételeinek figyelmen kívül hagyását, hogy egy működő terv általános struktúráját származtathassa. Austin Tate PhD-tézise (Tate, 1975b) és Earl Sacerdoti (Sacerdoti, 1977) munkája a HTM tervkészítés modern formájának alapötleteit vezette be. Számos gyakorlati tervkészítő, beleértve az O-PLAN és a SIPE tervkészítőket, HFH-tervkészítő. Yang (Yang, 1990) a HFH-tervkészítést hatékonnyá tevő cselekvések jellemzőit tárgyalja. Erol, Hendler és Nau (Erol és társai, 1994, 1996) egy teljes hierarchikus dekompozíciót alkalmazó tervkészítőt mutat be, valamint számos komplexitásbeli eredményt a tiszta HFH-tervkészítőkhöz. Más szerzők (Ambros-Ingerson és Steel, 1988); Young és társai (Young és társai, 1994); Barrett és Weld (Barett és Weld, 1994); Kambhampati és társai (Kambhampati és társai, 1998) az ebben a fejezetben bemutatott hibrid megközelítést javasolták, melyben a dekompozíciók mindössze a részben rendezett tervkészítéshez használható finomítások egy másik formáját jelentik.

A STRIPS-ben szereplő makróoperátorokkal kezdődően a hierarchikus tervkészítés egyik célja a korábbi, általánosított tervek formájában rendelkezésre álló tervkészítési tapasztalat újrahasznosítása. A magyarázatalapú tanulás (explanation-based learning) technikáját, amit részleteiben a 19. fejezet mutat be, számos rendszerben, mint a SOAR Laird és társai (Laird és társai, 1986) és PRODIGY (Carbonell és társai, 1989) alkalmazták a korábban elkészített tervek általánosítására. Egy másik megközelítés, hogy a korábban kiszámított terveket eredeti formájukban tároljuk el, majd az új hasonló feladatokban az eredeti feladat analógiájára újrahasznosítjuk őket. Ezt a megközelítést esetalapú tervkészítésnek (case-based planning) (Carbonell, 1983; Alterman, 1988; Hammond, 1989) nevezzük. Kambhampati (Kambhampati, 1994) érvelése szerint az esetalapú tervkészítést a finomító tervkészítéshez hasonlóan kellene vizsgálni. Emellett lefekteti az esetalapú részben rendezett tervkészítés formális alapjait.

A valós környezetek kiszámíthatatlanságát és részleges megfigyelhetőségét elsőként tervkészítési technikákat használó robotikai projektekben – beleértve a Shakey (Fikes és társai, 1972) és a FREDDY (Michie, 1974) projekteket – ismerték fel. A problémakör több figyelmet kapott McDermott nagy hatású Tervezés és cselekvés (Planning and Acting) c. cikkének megjelenését követően (McDermott, 1978a).

A korai, feltételeket és ciklusokat nem tartalmazó tervkészítők nem tükrözték pontosan a feltételes tervkészítés megközelítésmódját, de ennek ellenére néha kényszerítően reagáltak a környezet bizonytalanságára. Sacerdoti NOAH rendszere kényszerítést használt a „kulcsok és dobozok” (keys and boxes) probléma megoldásában, egy olyan tervkészítési kihívásban, ahol a tervkészítő keveset tud a kiinduló állapotról. Mason (Mason, 1993) kijelentette, hogy a robotikai tervkészítés nélkülözni tudja és nélkülöznie is kell az érzékelést, és bemutatott egy érzékelőmentes tervet, ami a kiindulási pozíciótól függetlenül képes egy eszközt csuklómozdulatok sorozatával az asztal egy megadott pozíciójába mozgatni. Ezt az ötletet a robotika kontextusában tárgyaljuk (lásd 25.17. ábra).

Goldman és Boddy (Goldman és Boddy, 1996) bevezették az alkalmazkodó tervkészítés (conformant planning) fogalmát, az érzékelőmentes tervkészítőkre, melyek a bizonytalanságot a környezet ismert állapotokba való kényszerítésével kezelik, megjegyezve, hogy az érzékelőmentes tervek gyakran hatékonyak még akkor is, ha az ágens rendelkezik érzékelőkkel. Az első megfelelően hatékony alkalmazkodó tervkészítő Smith és Weld (Smith és Weld, 1998) Conformant Graphplan (CGP) rendszere volt. Ferraris és Giunchiglia (Ferraris és Giunchiglia, 2000), valamint Rintanen (Rintanen, 1999) függetlenül fejlesztettek ki SATPLAN-alapú alkalmazkodó tervkészítőket. Bonet és Geffner (Bonet és Geffner, 2000) a hiedelmi állapotok terén végzett heurisztikus keresésalapú alkalmazkodó tervkészítőt mutat be, olyan ötletekre alapozva, melyeket először 1960-ban fejlesztettek ki a részlegesen megfigyelhető Markov döntési folyamatokhoz (Partially Observable Markov Decision Process – POMDP) (lásd 17. fejezet). Jelenleg a leggyorsabb hiedelmi állapot alkalmazkodó tervkészítők, mint például a HSCP (Bertoli és társai, 2001a) bináris döntési diagramokat (BDD) (Bryant, 1992) használnak a hiedelmi állapotok leírására, valamint öt nagyságrenddel gyorsabbak, mint a CGP.

A WARPLAN-C (Warren, 1976), ami a WARPLAN egy változata, volt az első feltételes cselekvéseket használó tervkészítők egyike. Olawski és Gini (Olawski és Gini, 1990) a feltételes tervkészítés fő problémáit vetette fel.

A fejezetben bemutatott feltételes tervkészítési megközelítés a Jimenez és Torras (Jimenez és Torras, 2000), valamint Hansen és Zilberstein (Hansen és Zilberstein, 2001) által kifejlesztett ciklikus ÉS-VAGY gráfok hatékony keresési algoritmusán alapul. Bertoli és társai (Bertoli és társai, 2001b) egy BDD-alapú megközelítést mutatnak be, ami ciklikus feltételes terveket készít. A C-BURIDAN rendszer (Draper és társai, 1994) egy folytonos tervkészítést végez valószínűségi kimenetelű cselekvésekre, melynek problémája a POMDP vezérlése során is felmerült (lásd 17. fejezet). Szoros kapcsolat van a feltételes tervkészítés és az automatizált programkészítés között. A 9. fejezet számos ilyen hivatkozást tartalmaz. A két területet egymástól függetlenül tárták fel, aminek oka az az óriási költségkülönbség, ami egy gépi utasítás végrehajtása, valamint robot- vagy manipulátorcselekvések végrehajtása között fennáll. Linden (Linden, 1991) a két terület közötti tudásmegosztást szorgalmazza.

Történelmi távlatból már látható, hogy hogyan vezetett a két fő klasszikus tervkészítő algoritmus kibővített verziókhoz a bizonytalan környezetek kezelése céljából. A keresésalapú technikák a hiedelmi állapottér keresésre vezettek (Bonet és Geffner, 2000). A SATPLAN algoritmus a sztochasztikus SATPLAN (Majercik és Littman, 1999) algoritmusra, valamint a kvantorokat alkalmazó logikai tervezésre vezetett (Rintanen, 1999). A részben rendezett tervkészítésből az UWL (Etzioni és társai, 1992), a CNLP (Peot és Smith, 1992) és a CASSANDRA (Pryor és Collins, 1996) származik. A GRAPHPLAN, az érzékeléses GRAPHPLAN (sensory GRAPHPLAN-SGP) (Weld és társai, 1998) algoritmusra vezetett, de a teljesen valószínűségi GRAPHPLAN algoritmus még kifejlesztésre vár.

A végrehajtás monitorozás első fő megjelenése a PLANEX (Fikes és társai, 1972), ami egy STRIPS tervkészítővel működött a Shakey robot irányításán. A PLANEX háromszög táblákat használt – ami egy szükségszerűen hatékony tárolási mechanizmus a terv előfeltételeinek tárolására a terv minden pontján –, hogy teljes újratervezés nélkül helyreállhasson egy részleges végrehajtási hiba után. A végrehajtás Shakey-modelljét a 25. fejezetben tárgyaljuk tovább. A NASL tervkészítő (McDermott, 1978a) a tervkészítési problémát egyszerűen, mint egy komplex cselekvés végrehajtásának specifikációját tekintette, így a tervezés és végrehajtás teljesen egységessé vált. Az összetett cselekvések levezetésére tételbizonyítást használ.

A SIPE (System for Interactive Planning and Execution Monitoring) (Wilkins, 1988, 1990) volt az első tervkészítő, ami az újratervezés problémáját szisztematikusan kezelte. Különböző problémakörök demonstrációs feladataiban is felhasználták, például az űrsiklóhordozó fedélzeti terv készítésére vagy emberi erőforrás ütemezésére egy ausztrál sörgyárban. Egy másik vizsgálat a SIPE rendszert többemeletes épületek tervezésében alkalmazta, ami az egyik legbonyolultabb problémakör, amit tervkészítő valaha kezelt.

Az IPEM (Intergrated Planning, Execution, and Monitoring) (Ambros-Ingerson és Steel, 1988) volt az első rendszer, ami integrálta a részben rendezett tervkészítést és a végrehajtást, hogy folytonos tervkészítő ágensre jusson. Az általunk tárgyalt folytonos, részben rendezett tervkészítő ágens (CONTINUOUS-POP-AGENT) az IPEM a PUCCINI (Golden, 1998) és a CYPRESS (Wilkins és társai, 1995) tervkészítők ötleteit kombinálja.

Az 1980-as évek közepén néhányan úgy gondolták, hogy a részben rendezett tervkészítés és a kapcsolódó technikák soha nem futhatnak eléggé gyorsan, hogy egy valódivilág-beli ágens számára használható viselkedést biztosítsanak (Agre és Chapman, 1987). Ezek helyett a reaktív tervkészítő (reactive planning) rendszereket vezették be. Ezek alapesetben reflexszerű ágensek, esetenként belső állapottal, melyek számos különböző feltétel-cselekvés szabályábrázolás segítségével implementálhatók. Brooks (Brooks, 1986) bennfoglalási architektúrája (lásd. 7. és 25. fejezet) rétegzett véges állapotú állapotgépeket használt, lábbal és kerékkel ellátott robotok mozgásának és akadályok elkerülésének a szabályozására. Pengi (Agre és Chapman, 1987) egy (teljesen megfigyelhető) videojátékot tudott játszani, az aktuális célok „látott” reprezentációja, az ágens belső állapota, valamint kétértékű áramkörök kombinálásával.

Az „univerzális tervek” (Schoppers, 1987) a reaktív tervkészítés keresőtábla módszereként került kifejlesztésre, de mint kiderült, ez a Markov döntési folyamatokban használt eljárásmód (policy) ötletének újrafelfedezése volt. Egy univerzális terv (vagy egy eljárásmód) bármely állapotban az adott állapotban végrehajtandó cselekvésre mutató leképezést tartalmazza. Ginsberg (Ginsberg, 1989) lelkes támadást indított az univerzális tervek ellen, ami kezelhetetlenségi eredményeket is tartalmazott a reaktív tervkészítési probléma néhány alakjára. Erre Schoppers 1989-ben egy hasonlóan lelkes választ adott (Schoppers, 1989).

Mint a legtöbb esetben a hibrid megközelítés feloldja az ellentmonást. Jól tervezett hierarchiák használatával a HFH tervkészítők, mint a PRS (Georgeff és Lansky, 1987) és a RAP (Firby, 1996), valamint a folytonos tervkészítő ágensek használható válaszidőket és összetett hosszú távú terveket érhetnek el számos problémakörben.

A multiágens tervkészítés napjainkban vált népszerűvé, bár hosszú történelme van. Konolige (Konolige, 1982) a multiágens tervkészítés elsőrendű logikai leírását adta meg, míg Pednault (Pednault, 1986) egy STRIPS-alakú leírást készített. A kölcsönös szándék ötlete, ami elengedhetetlen, ha az ágensek együttes tervet hajtanak végre, a kommunikációs viselkedés kutatásából ered (Cohen és Levesque, 1990; Cohen és társai, 1990). Az általunk bemutatott többtestű részben rendezett tervkészítés Boutilier és Brafman (Boutilier és Brafman, 2001) munkáján alapul.

Az itt szereplő, a multiágens tervkészítésben az együttműködést célzó munka bemutatása éppcsak a jéghegy csúcsa. Durfee és Lesser (Durfee és Lesser, 1989) azt tárgyalja, hogy a feladatok hogyan oszthatók meg az ágensek között egyezkedés útján. Kraus és társai (Kraus és társai, 1991) egy Diplomacyt – egy egyezkedést, együttműködést, felbomlást és ügyeskedést igénylő táblajátékot – játszó rendszert mutatnak be. Stone (Stone, 2000) bemutatja, hogy az ágensek hogyan tudnak csapattagként együttműködni a robotfoci versengő, dinamikus, részben megfigyelhető környezetében. A (Weiss, 1999) a multiágens rendszerek egy könyvhosszúságú áttekintése. Az 12.7.3. szakasz - Koordináló mechanizmusok rész moid modellje Reynoldsnak köszönhető (Reynolds, 1987), aki ennek a Batman visszatér (Batman returns) c. film denevérseregeire és pingvincsapatára való alkalmazásával Oscar-díjat is nyert.

12.8.2. Feladatok

12.1.

Vizsgáljuk meg figyelmesen a 12.1. alfejezetben az idő és az erőforrások reprezentációját.

  1. Miért jobb, ha egy cselekvés következménye az Időtartam(d), mint ha a cselekvésnek egy IDŐTARTAM:d alakú külön mezője lenne? (Segítség: vegyük figyelembe a feltételes következményeket és a diszjunktív következményeket.)

  2. Az ERŐFORRÁS: m miért egy külön mező a cselekvésben, nem pedig egy következmény?

12.2.

Egy fogyóeszköz (consumable resource) egy olyan erőforrás, ami (részlegesen) felhasználásra kerül a cselekvésben. Például a motor beszerelése az autóba csavarokat igényel. Miután a csavarokat felhasználtuk, már nem használhatók további rögzítésekhez.

  1. Magyarázza meg, hogyan módosítsuk a 12.3. ábra reprezentációját úgy, hogy 100 kiinduló csavarunk legyen az E1 motor 40 csavart, az E2 pedig 50 csavart igényel. A + és – szimbólumok felhasználhatók az erőforrásokat leíró következményliterálokban.

  2. Mutassa meg, hogy a részben rendezett tervkészítésben alkalmazott okozati kapcsolatok és cselekvések közötti ütközés (conflict) definícióját hogyan kell módosítani, hogy a fogyóeszközöket kezelje.

  3. Néhány cselekvés, például a gyár ellátása csavarokkal vagy egy autó feltankolása, növelheti az erőforrások készletét. Egy erőforrás monoton nem növekvő, ha egyetlen cselekvés sem növeli. Magyarázza meg, hogyan használható ez a tulajdonság a keresési tér megmetszéséhez.

12.3.

Adjon dekompozíciót a 12.7. ábra KivitelezőtVeszFel és EngedélytSzerez lépéseire, és mutassa meg, hogy a dekomponált résztervek hogyan állnak össze egy teljes tervvé.

12.4.

Adjon példát a házépítési problémakörben két olyan absztrakt résztervre, ami nem egyesíthető egy teljes tervvé lépések megosztása nélkül. (Segítség: azok a pontok, ahol egy ház fizikai részei csatlakoznak, egyúttal a résztervek várható csatlakozási kölcsönhatási pontjai is.)

12.5.

Sokan mondják, hogy a HFH-tervkészítés előnye, hogy „tegyünk egy körutat Los Angelesből New Yorkba, és vissza” típusú problémákat is meg tud oldani, amelyeket nehéz nem HFH-jelölésekkel kifejezni, hiszen a kiinduló és a célállapotok azonosak lennének (Ott(LA)). Tud mondani megfelelő reprezentációt, illetve meg tudja-e oldani ezt a problémát HFH-k nélkül?

12.6.

Mutassa meg, hogy az eredeti STRIPS cselekvésleírás hogyan írható át HFH-dekompozícióvá. Használja az Eléri(p) cselekvést a p feltétel eléréséhez szükséges cselekvés jelölésére.

12.7.

A hagyományos programozási nyelvekben számos művelet modellezhető olyan cselekvéssel, amely megváltoztatja a világ állapotát. Például egy értékadási operátor egy memóriaterület tartalmát másolja, míg egy nyomtatás operátor megváltoztatja a kimenet állapotát. Egy, ezekből a műveletekből álló programot tervnek tekinthetünk, melynek célját a program specifikációja definiálja. A felkészítő algoritmusok ezért felhasználhatók egy adott specifikációjú program elkészítéséhez.

  1. Írjon egy operátorsémát az értékadási operátorhoz (egy változó értékének átadása egy másik változónak). Vegye figyelembe, hogy az eredeti érték felülíródik!

  2. Mutassa meg, hogy az objektumok létrehozása hogyan használható a felkészítő által két változó értékének egy átmeneti változó felhasználásával történő felcserélésére.

12.8.

Tekintsük a következő indoklást: egy bizonytalan kiinduló állapotot megengedő keretrendszerbe a diszjunktív következmények (disconjuctive effects) csak jelölési könnyebbséget jelentenek, és nem a kifejezőképesség növelésére szolgálnak. Egy PQ diszjunktív következményt tartalmazó a cselekvéssémát mindig helyettesíthetünk a when R: Pwhen ¬R: Q feltételes következményekkel, ami cserében két hagyományos cselekvésre redukálható. Az R kifejezés egy a kiinduló állapotban ismeretlen véletlen állítást takar, melyhez nem tartozik érzékelő cselekvés. Helyes ez az indoklás? Vegyünk külön két esetet, egyet, melyben csak egy a cselekvésséma szerepel a tervben, és egy másikat, melyben több mint egy példány van.

12.9.

Miért nem tudja a feltételes tervkészítés kezelni a nem korlátos nemdeterminisztikusságot?

12.10.

A kockavilágban két STRIPS cselekvést kellett bevezetnünk, hogy az Üres predikátumot helyesen megtartsuk, a Mozgat és az AsztalraTesz cselekvéseket. Mutassuk meg, hogy a feltételes következmények hogyan használhatók mindkét eset egyetlen cselekvéssel történő leírására.

12.11.

A feltételes következményeket a porszívóvilág Szív cselekvésére mutattuk be, ahol az, hogy melyik kocka lesz tiszta, attól függ, hogy mely kockán áll a robot. Tud mondani olyan ítéletlogikai változókat, melyek a porszívóvilág állapotait definiálják úgy, hogy a Szív cselekvésnek feltétel nélküli leírása legyen? Adja meg a Szív, a Balra és a Jobbra cselekvések leírását az állításaik felhasználásával, és mutassa meg, hogy ezek kielégítők a világ összes lehetséges állapotának leírásához.

12.12.

Adja meg a Szív cselekvés teljes leírását a dupla-Murphy porszívó problémára, ami néha piszkot hagy maga után, amikor egy tiszta célterületre mozog, és néha piszkot rak le, ha a Szív cselekvést egy tiszta négyzeten hajtjuk végre.

12.13.

Keressen egy megfelelően piszkos szőnyeget, amely akadálymentes és porszívózza ki. Rajzolja le a porszívó által választott útvonalat, amilyen pontosan csak tudja. Indokolja a választ hivatkozva a fejezetben tárgyalt tervkészítési módszerekre.

12.14.

A következő idézetek samponos flakonok hátuljáról származnak. Azonosítsa mindegyiket, mint egy feltétel nélküli, feltételes vagy végrehajtás monitorozó tervet. (a) „Mosás. Öblítés. Ismételje.” (b) „Tegye a sampont a fejére, és hagyja ott néhány percig. Öblítsen és ismételje, ha szükséges.” (c) „Amennyiben az irritáció nem szűnik, forduljon orvoshoz.”

12.15.

A 12.10. ábrán szereplő ÉS-VAGY-GRÁF-KERESÉS algoritmus csak a gyökér és az aktuális állapot közötti útvonalat ellenőrzi le ismétlődő állapotokra. Mindehhez tegyük fel, hogy az algoritmus eltárolt minden meglátogatott állapotot, és összeveti ezzel a listával (lásd például 3.19. ábra GRÁF-KERESÉS). Határozza meg, hogy milyen információt kellene tárolni, és azt, hogy az algoritmus hogyan használja ezt fel, amikor ismétlődő állapotot talál. (Segítség: szüksége lesz arra, hogy különbséget tegyen azon állapotok, melyekhez egy sikeres részterv készült korábban, és azon állapotok között, melyekre nem talált résztervet.) Magyarázza meg, hogyan használhatunk címkéket (labels), hogy elkerüljük a résztervek duplikálását.

12.16.

Mutassa meg precízen, hogy hogyan módosítjuk az ÉS-VAGY-GRÁF-KERESÉS algoritmust, hogy ciklikus tervet generáljon, amennyiben ciklusmentes terv nem létezik. Ehhez három problémával kell megküzdenie: a terv lépéseinek címkézése, hogy egy ciklikus terv vissza tudjon mutatni a terv egy korábbi pontjára, a VAGY-KERESÉS módosításával, hogy egy ciklikus terv megtalálása után ciklusmentes tervet keressen, és a terv leírásának olyan bővítésével, mely jelzi, hogy a terv ciklikus. Mutassa meg, hogyan működik az algoritmus (a) a tripla-Murphy porszívóvilágban, (b) a váltakozó dupla-Murphy porszívóvilágban. Használhat számítógépes implementációt az eredmények ellenőrzéséhez. A (b) eset terve felírható egy hagyományos ciklusszintaxis használatával?

12.17.

Specifikálja teljesen a hiedelem állapot módosító folyamatot részben megfigyelhető környezetekre. Azaz a módszert, ami az új hiedelmi állapot leírást számítja (mint ismeret állítások listáját) az aktuális hiedelmi állapot leírásból és a feltételes következményeket tartalmazó cselekvésleírásokból.

12.18.

Írjon a (12.2.) egyenlettel analóg cselekvésleírásokat a Jobbra és a Szív cselekvésekre. Adja meg a leírását a PozícióEllenőrzés cselekvésnek, a (12.3.) egyenletnek megfelelően. Ismételje ezt meg a 12.11. feladat alternatív állítás halmazának felhasználásával.

12.19.

Tekintse meg az 12.6. szakasz - Folytonos tervkészítés rész listáját, ami felsorolja, hogy mit nem tud az újratervező ágens végrehajtani. Vázoljon fel egy algoritmust néhány probléma kezelésére.

12.20.

Vegyük a következő feladatot: egy páciens olyan tünetekkel érkezik az orvoshoz, amelyet kiszáradás vagy D fertőzés okozhat (de nem mindkettő). Két lehetséges cselekvés van: Iszik, ami feltétel nélkül kúrálja a kiszáradást, és Gyógyszert szed, amely a D fertőzést kúrálja ki, de káros mellékhatása van, ha a páciens kiszáradt. Írja fel a probléma leírást PDDL-ben, és az összes releváns világ számbavétele mellett ábrázolja az érzékelőmentes tervet, ami megoldja a problémát.

12.21.

Az előző feladat gyógyszerszedési problémájához adja hozzá a Vizsgál cselekvést, melynek feltételes következménye a TenyészetNövekedés, amennyiben a Fertőzés igaz, és minden esetben van egy érzékelési következménye: Ismert(TenyészetNövekedés). Ábrázolja a feltételes tervet, ami megoldja a problémát és minimalizálja a GyógyszertSzed cselekvés felhasználását.