11.7. Összefoglalás

Ebben a fejezetben a tervkészítési feladatot determinisztikus és teljesen megfigyelhető környezetek esetén definiáltuk. Bemutattuk a tervkészítési feladatok leírására használt főbb reprezentációkat, valamint számos algoritmikus megközelítést a megoldásukra. Idézzük fel a fontosabb állításokat:

  • A tervkészítő rendszerek olyan problémamegoldó algoritmusok, melyek állapotok és cselekvések explicit ítéletlogikai (vagy elsőrendű) reprezentációin működnek. Ezek a leírások lehetővé teszik hatékony heurisztikák származtatását, valamint erős és rugalmas algoritmusok kifejlesztését a problémamegoldáshoz.

  • A STRIPS nyelv az előfeltételek és következmények segítségével írja le a cselekvéseket, valamint a kiindulási és célállapotokat pozitív literálok konjunkciójaként adja meg. Az ADL nyelv lazít ezeken a megkötéseken, megengedi a diszjunkciót, a negálást és a kvantorokat.

  • Az állapottér-keresés történhet előrefelé: progreszív (progression) vagy hátrafelé: regresszív (regression). Hatékony heurisztikák származtathatók a részcélok függetlenségét feltételezve és a tervkészítési feladat különböző gyengítéseivel.

  • A részben rendezett tervkészítő (RRT) algoritmusok a tervek terében keresnek anélkül, hogy cselekvések teljesen rendezett sorozatára jutnának. A céltól visszafelé működnek a részcélok eléréséhez szükséges cselekvéseknek a tervhez való hozzáadásával. Ezek az algoritmusok különösen hatékonyak az „oszd meg és uralkodj” megközelítéssel kezelhető problémákra.

  • Egy tervkészítési gráf (planning graph) megalkotható inkrementálisan a kiinduló állapotból elindulva. Minden egyes réteg az adott időpillanatban végrehajtható öszszes cselekvés és literál halmazát tartalmazza, rögzíti a kölcsönös kizárásokat vagy mutexeket, azaz olyan literálok és cselekvések közötti relációkat, melyek egyszerre nem következhetnek be. A tervkészítési gráfok hasznos heurisztikákra vezetnek az állapottér és a részben rendezett tervkészítők esetén, és közvetlenül felhasználhatók a GRAPHPLAN algoritmusban.

  • A GRAPHPLAN algoritmus a tervkészítési gráfot dolgozza fel visszafelé keresést alkalmazva a terv kinyeréséhez. Lehetőséget biztosít továbbá még a cselekvések között bizonyos részben rendezésekre.

  • A SATPLAN algoritmus a tervkészítési problémát ítéletlogikai axiómákra fordítja, és egy kielégíthetőségi algoritmust használ a helyes tervnek megfelelő modell megtalálására. Számos különböző ítéletlogikai reprezentációt fejlesztettek ki különböző mértékű tömörséggel és hatékonysággal.

  • A tervkészítés fő megközelítései mindegyikének vannak nehézségei, és egyelőre nincs egyetértés abban, hogy melyik a legjobb. A versengés és a módszerek ötvözése komoly előrehaladást eredményezett a tervkészítő rendszerek hatékonyságában.

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

A mesterséges intelligenciában a tervezés az állapottér-keresések vizsgálatából, tételbizonyításból, szabályozástechnikából, illetve a robotika, ütemezés és más területek gyakorlati szükségleteiből ered. Az első számottevő tervkészítő rendszer a STRIPS (Fikes and Nilsson, 1971), ezen hatások kölcsönhatását példázza. A STRIPS-et, az SRI-ben zajló Shakey robot projekt szoftverének tervkészítő komponenseként fejlesztették ki. Ennek teljes szabályozási struktúráját egy eszköz-cél analízist használó állapottér-kereső rendszer, a GPS, azaz az általános problémamegoldó (general problem solver) (Newell és Simon, 1961) mintájára készítették. A STRIPS a QA3 tételbizonyító rendszer egy verzióját (Green, 1969b) használta fel a cselekvések előfeltételeinek teljesítésére. Lifschitz a STRIPS precíz definícióit és elemzéseit adja meg (Lifschitz, 1986). Bylander bizonyította, hogy az egyszerű STRIPS tervkészítés PSPACE-teljes (Bylander, 1992). Fikes és Nilsson történelmi áttekintést adnak a STRIPS projektről, és feltárják ennek kapcsolatait az újabb tervkészítési törekvésekkel (Fikes és Nilsson, 1993).

A STRIPS-ben használt cselekvésreprezentációnak sokkal nagyobb hatása volt, mint algoritmikus megközelítésének. Ezt követően majdnem minden tervkészítő rendszer használta a STRIPS nyelv ilyen vagy olyan módosításait. Sajnos a különböző változatok elburjánzása szükségtelenül megnehezítette az összehasonlításokat. Az idő múlásával jobban megértettük az egyes formalizmusok korlátait és hátrányait. A cselekvésleíró nyelv (Action Description Language – ADL) (Pednault, 1986) lazította a STRIPS nyelv néhány megkötését, és lehetővé tette a valósághoz közelibb problémák leírását. Nebel az ADL leírást STRIPS leírásra fordító sémákat vizsgálja (Nebel, 2000). A problématér leíró nyelvet (Problem Domain Description Language – PDDL) (Ghallab és társai, 1998) egy számítógép által érthető szabványos szintaxisként vezették be a STRIPS, az ADL és egyéb nyelvek leírására. A PDDL-t 1998-tól az AIPS konferencián zajló tervkészítési versenyek szabványos nyelveként használták.

Az 1970-es évek elejének tervkészítői általában teljesen rendezett cselekvéssorokkal dolgoztak. A problémadekompozíciót úgy érték el, hogy minden részcélhoz egy résztervet készítettek, majd ezeket valamilyen sorrendben összefűzték. Hamarosan felfedezték, hogy ez a megközelítést, melyet Sacerdoti lineáris tervkészítésnek (linear planning) nevezett (Sacerdoti, 1975), nem teljes. Nem képes megoldani néhány nagyon egyszerű problémát, mint pédául a Sussman-anomáliát (lásd 11.11. feladat), amit Allen Brown a HACKER rendszerrel végzett kutatásai során fedezett fel (Sussman, 1975). Egy teljes tervkészítőnek meg kell engedni egy mondatban a különböző résztervekből származó cselekvések összefésülését (interleaving). A sorrendezhető részcélok alapötlete (Korf, 1987) pontosan megfeleltethető azon problémák halmazának, melyekre az öszszefésülésre nem alkalmas tervkészítők teljesek.

Az összefésülési probléma egyik megoldása a célregressziós tervkészítés volt, ami egy olyan technika, melyben egy teljesen rendezett terv lépéseit a részcélok közötti konfliktusok elkerülése érdekében újrarendezzük. Ezt Waldinger vezette be (Waldinger, 1975), és Warren WARPLAN rendszerében (Warren, 1974) szintén felhasználták. A WARPLAN-nel kapcsolatban szintén kiemelendő, hogy ez volt az első tervkészítő, melyet logikai programozási nyelven (Prolog) írtak, valamint az egyik legjobb példa arra a kiemelkedő gazdaságosságra, ami a logikai programozással nyerhető: a WARPLAN összesen száz kódsor, azaz csak töredéke az abban az időben ismert hasonló tervkészítők méretének. Az INTERPLAN (Tate, 1975a; 1975b) a Sussman-anomália és hasonló problémák elkerülése érdekében, szintén megengedte a tervlépések tetszőleges összefésülését.

A részben rendezett tervkészítés alapötletei tartalmazzák az ütközések érzékelését (Tate, 1975a) és az elért feltételek kölcsönhatásoktól való védelmét (Sussman, 1975). A részben rendezett tervek (melyeket akkor feladathálóknak – task network – neveztek) készítését a NOAH tervkészítő (Sacerdoti, 1975; 1977) és Tate NONLIN rendszere vezette be (Tate, 1975b; 1977).[117]

A következő húsz év kutatásaiban a részben rendezett tervkészítés dominált, mialatt azonban a problémakört széles körben nem értették. A TWEAK (Chapman, 1987) ezen időszak tervkészítési munkájának logikai reprezentációja és egyszerűsítése volt. Chapman felírása eléggé tiszta volt ahhoz, hogy bizonyítható legyen a tervkészítési problémák különböző megfogalmazásainak teljessége és követhetetlensége (NP-nehézsége és -eldönthetetlensége). Chapman munkája egy teljes részben rendezett tervkészítő első egyszerű és olvasható leírására vezetett (McAllester és Rosenblitt, 1991). A McAllester és Rosenblitt SNLP-nek (Soderland és Weld, 1991) nevezett algoritmusának implementációja széles körben elterjedt, és elsőként tette számos kutató számára lehetővé a részben rendezett tervkészítők megértését és kutatását. Az ebben fejezetben korábban bemutatott RRT algoritmus az SNLP-n alapul.

Weld csoportja fejlesztette ki az UCPOP-ot is (Penberthy és Weld, 1992), az első tervkészítőt ADL-ben kifejezett problémákra. Az UCPOP a kielégítetlen-célok-száma heurisztikát alkalmazta. Valamivel gyorsabban futott, mint az SNLP, de nagyon ritkán volt képes néhány tucat lépésnél többet tartalmazó tervek megtalálására. Bár javított heurisztikákat is kifejlesztettek az UCPOP módszerhez (Joslin és Pollack, 1994); (Gerevini és Schubert, 1996) az 1990-es években, a gyorsabb módszerek megjelenésével a részben rendezett tervkészítők háttérbe szorultak. Nguyen és Kambhampati a módszer visszatérését javasolták (Nguyen és Kambhampati, 2001): a tervkészítési gráfból megfelelő heurisztikák származtatásával a REPOP tervkészítőjük jobban skálázható, mint a GRAPHPLAN, továbbá ez vetélytársa lett a leggyorsabb állapottér-tervkészítőknek is.

Avrim Blum és Merrick Furst felpezsdítette a tervkészítés területét GRAPHPLAN rendszerével (Blum és Furst, 1995; 1997), ami több nagyságrenddel gyorsabb volt az akkori részben rendezett tervkészítőknél. Más gráftervező rendszerek, mint az IPP (Koehler és társai, 1997), a STAN (Fox és Long, 1998) és az SGP (Weld és társai, 1998) hamarosan követték. Egy kicsivel korábban Ghallab és Laurelle a tervkészítő gráfhoz nagyon hasonló adatstruktúrát fejlesztettek ki (Ghallab és Laurelle, 1994). Az IXTET részben rendező tervkészítőjük az adatstruktúrát a keresés irányítására szolgáló heurisztikák kinyerésére alkalmazta. Nguyen és társai a tervkészítő gráfokból származtatott heurisztikák nagyon alapos áttekintését adták (Nguyen és társai, 2001). A mi tervkészítő gráfokról szóló leírásunk részben ezen, részben pedig Subbarao Kambhampati jegyzetein alapul. Ahogyan már a fejezetben említettük, többféle módon használható a tervezési gráf a megoldás keresésének irányítására. A 2002-es AIPS tervkészítő győztese, az LPG (Gerevini és Serina, 2002), a WALKSAT által ösztönözve lokális keresési technikát használt a tervkészítési gráf keresésére.

A tervkészítés mint kielégíthetőség és a SATPLAN algoritmus Kautz és Selman javaslata, akiket a kielégíthetőségi problémákra alkalmazott mohó lokális keresés meglepő sikere inspirált (Kautz és Selman, 1992) (lásd 7. fejezet). Kautz és társai szintén kutatták a STRIPS axiómák ítéletlogikai reprezentációjának különböző módjait, és azt találták, hogy a legtömörebb alakok nem feltétlenül vezettek a leggyorsabb megoldásokra (Kautz és társai, 1996). Ernst és társai szisztematikus elemzést hajtottak végre (Ernst és társai, 1997), valamint kifejlesztettek egy automatikus fordítót PDDL problémák ítéletlogikai megadásának generálására. A Kautz és Selman által kifejlesztett BLACKBOX tervkészítő (Kautz és Selman, 1998) a GRAPHPLAN és SATPLAN alapötleteit kombinálja.

Az állapottér-tervkészítőkkel kapcsolatos érdeklődés újjáéledésének úttörője Drew McDermott UNPOP programja (McDermott, 1996), amely elsőként javasolta a törlési listát figyelmen kívül hagyó egyszerűsített problémán alapuló távolság heurisztikát. Az UNPOP név a részben rendezett tervkészítőket illető túlzott figyelem egyik reakciója volt; McDermott szerint más megközelítések nem kapták meg a megérdemelt figyelmet. Bonet és Geffner heurisztikus kereső tervkészítője (Heuristic Search Planner – HSP) és ennek későbbi leszármazottjai (Bonet és Geffner, 1999) elsőként tették az állapottér-keresést alkalmazhatóvá nagyméretű tervkészítési feladatokra. A mai napig legsikeresebb állapottér-kereső Hoffmann FASTFORWARD vagy FF keresője, az AIPS 2000 tervkészítő versenyének győztese (Hoffmann, 2000). Az FF egyszerűsített tervkészítési gráf heurisztikát használ egy nagyon gyors, az előrefelé és a lokális keresést újszerűen ötvöző algoritmussal.

Napjainkban a tervek bináris döntési diagram (binary decision diagram) alakú reprezentációja hódít, ami egy véges automata tömör leírási módja, melyet a hardververifikációval foglalkozó közösség részletesen tanulmányozott (Clarke és Grumberg, 1987; McMillan, 1993). A bináris döntési diagramok jellemzőinek mint egy tervkészítési probléma megoldásának való megfelelés tulajdonságának bizonyítására számos technika elérhető. Cimatti és társai egy ezen a megközelítésen alapuló tervkészítőt mutattak be (Cimatti és társai, 1998). Más reprezentációkat szintén felhasználtak; például Vossen és társai az egész programozás tervkészítésre való felhasználhatóságát vizsgálja (Vossen és társai, 2001).

A döntőbizotság még nem döntött, de a különböző tervkészítési algoritmusok néhány nagyon érdekes összevetése már elérhető. Helmert a tervkészítési problémák számos osztályát vizsgálja, és megmutatja, hogy az NP-nehéz problémakörökben a megkötésalapú megközelítések, mint a GRAPHPLAN és a SATPLAN bizonyulnak a legjobbnak, míg a keresésalapú megközelítések azon problémakörökben hasznosak, ahol visszalépések nélkül elérhető egy megfelelő megoldás (Helmert, 2001). A GRAPHPLAN és SATPLAN algoritmusoknak nehézséget okoznak a sok objektumot tartalmazó problémák, mert ezek miatt sok cselekvésre van szükségük. Az esetek egy részében a probléma elkerülhető vagy elodázható, ha a cselekvések bizonyos részét csak szükség esetén generáljuk le dinamikusan, ahelyett hogy már a keresés előtt példányosítanánk mindegyiket. Weld a modern tervkészítő algoritmusok két kitűnő áttekintését adja (Weld, 1994; 1999). Érdekes látni az eltelt öt év változásait az áttekintésekben: az első a részben rendezett tervkészítésre fókuszál, míg a második a GRAPHPLAN és SATPLAN algoritmusokra. A Readings in Planning (Allen és társai, 1990) a terület legjobb korábbi cikkeinek minden részletre kiterjedő antológiája, beleértve néhány áttekintést is. Yang a részben rendezett tervkészítők könyv méretű áttekintését adja (Yang, 1997).

A tervkészítés kutatása a megjelenésétől kezdve központi kérdése a mesterséges intelligencia kutatásának, így a tervkészítésről született cikkek is számottevő részét képezik a folyóiratok és konferenciák anyagának. Specializált konferenciákat is rendeznek, mint az International Conference on AI Planning Systems (AIPS), az International Workshop on Planning and Scheduling for Space vagy a European Conference on Planning.

11.7.2. Feladatok

11.1.

Írja le a különbségeket és hasonlóságokat a problémamegoldás és a tervkészítés között.

11.2.

Adottak a 11.2. ábra axiómái. Melyek az alkalmazható konkrét példányai a Repül(p, honnan, hova) cselekvésnek a következő állapotban:

Ott(P1, JFK) ∧ Ott(P2, SFO) ∧ Repülő(P1) ∧ Repülő(P1)

∧ Repülőtér(JFK) ∧ Repülőtér(SFO)

11.3.

Nézzük meg, hogyan fordíthatunk le egy STRIPS sémahalmazt a szituációkalkulus követő állapot axiómáira (lásd 10. fejezet).

  • Vegyük a Repül(p, honnan, hová) sémát. Írja le a RepülElőfeltétel(p, honnan, hová, s) predikátum logikai definícióját, ami igaz, ha a Repül(p, honnan, hová) előfeltételei teljesülnek az s szituációban.

  • Ezután írjuk fel a Ott(p, x, s) követő állapot axiómáját, ami a cselekvéssémával azonos információt tartalmazza, feltételezve, hogy a Repül(p, honnan, hová) az ágens számára rendelkezésre álló egyetlen cselekvésséma.

  • Most feltételezzük, hogy van egy további utazási lehetőség: Teleportálás(p, honnan, hová). Ennek egy további előfeltétele a ¬Torzult(p), extra következménye pedig a Torzult(p). Magyarázza meg, hogyan kell módosítani a szituációkalkulus tudásbázisát.

  • Végezetül fejlesszen ki egy általános és pontosan specifikált megoldást egy STRIPS sémahalmaz követő állapot axióma halmazra való lefordításához.

11.4.

Egy majom a „majom-és-banán” feladattal találkozik egy laboratóriumban, ahol elérhetetlen banánfürtök lógnak a plafonról. Van egy doboz, ami lehetővé teszi a majom számára a banán elérését, amennyiben felmászik rá. Kiindulásképp a majom az A-ban van, a banánok a B helyen és a doboz a C-n. A majom és a doboz magassága Alacsony, de ha a majom a dobozra mászik, magassága Magas lesz, megegyezik a banánok magasságával. A majom számára elérhető cselekvések tartalmazzák a Menj egyik helyről a másikra, a Tol egy tárgyat egyik helyről a másikra, a Felmászik egy tárgyra, illetve Lemászik egy tárgyról, és a Megfog, illetve Elenged egy tárgyat cselekvéseket. A megmarkolás a tárgy megfogását eredményezi, ha a majom és a tárgy ugyanazon a helyen és ugyanabban a magasságban vannak.

  1. Írja fel a kiinduló állapotot.

  2. Írja le a hat cselekvés definícióját STRIPS alakban.

  3. Tegyük fel, hogy a majom meg akarja tréfálni a tudósokat, akik teázni mentek, azáltal hogy megragadja a banánokat, de a dobozt az eredeti helyén hagyja. Írja fel ezt mint általános célt (például nem feltételezve, hogy a doboz szükségszerűen a C helyen van) a szituációkalkulus nyelvén. Megoldható ez egy STRIPS-szerű rendszerrel?

  4. A tolási axiómája valószínűleg helytelen, mert a tárgy túl nehéz, így a pozíció azonos marad, ha a Tol operátort alkalmazzuk. Ez elágazási vagy értékelési feladatra ad példát? Javítsa ki a feladat leírását, hogy figyelembe vegye a nehéz tárgyakat.

11.5.

Magyarázza meg, hogy a hátrafelé keresésben a megelőző állapotok generálásának folyamata miért nem igényli, hogy a cselekvés negatív következményeinek megfelelő literálokat is szerepeltessük.

11.6.

Magyarázza meg, miért vezet relaxált problémára a negatív következmények eldobása egy STRIPS probléma minden cselekvés sémájából.

11.7.

Vizsgálja meg a 3. fejezetben szereplő kétirányú keresés (bidirectional search) definícióját.

  1. A kétirányú állapottér-keresés használata jó ötlet lenne tervkészítéshez?

  2. És a részben rendezett tervek terében történő kétirányú keresés?

  3. Tervezze meg a részben rendezett tervkészítő azon verzióját, melyben egy cselekvés akkor adható hozzá a tervhez, ha az előfeltételei elérhetők a tervben már szereplő cselekvések következményein keresztül. Magyarázza meg, hogyan kezeljük a konfliktusokat és a rendezési megkötéseket. Szükségszerűen azonos ez az algoritmus az állapottérben történő előrefelé kereséssel?

  4. Vegyünk egy részben rendezett tervkészítőt, ami kombinálja a c) részfeladat módszerét azzal az általános módszerrel, ahol a nyitott feltételek eléréséhez cselekvéseket adunk a tervhez. Azonos lesz az így előálló algoritmus a b) részfeladattal?

11.8.

Készítse el a 11.2. ábrán szereplő probléma tervkészítési gráfjának 0., 1. és 2. szintjét.

11.9.

Bizonyítsa be az alábbi tervkészítő gráfokra vonatkozó állításokat:

  • Az a literál, ami nem jelenik meg a gráf utolsó szintjén, nem érhető el.

  • Egy soros gráfban szereplő literál szintköltsége nem lehet nagyobb, mint az őt elérő optimális terv költsége.

11.10.

Összevetettük az állapottérben előre- és hátrafelé kereső tervkészítőket a részben rendezett tervkészítőkkel úgy, hogy az utóbbit egy tervtérkeresőnek vettük. Magyarázza meg, hogyan tekinthető az előre- és hátrafelé történő állapottér-keresés tervtérkeresőnek, és mondja meg, mik a tervfinomító operátorok.

11.11.

A 11.16. ábra a kockavilág problémát mutatja, ami Sussman-anomáliaként (Sussman anomaly) ismert. A problémát azért tekintették anomáliának, mert az 1970-es évek nem összefésülős tervkészítői nem tudták megoldani. Írjuk fel a probléma definícióját STRIPS alakban, és oldjuk meg, kézzel vagy egy tervkészítő programmal. A nemösszefésülő tervkészítő egy olyan tervkészítő, ami ha két G1 és G2 részcélt kap, akkor vagy egy G1 elérésére szolgáló tervet fűz hozzá egy G2 elérésére szolgáló tervhez, vagy fordítva. Magyarázza meg, hogy egy nem összefésülő tervkészítő miért nem tudja megoldani a kockavilág problémát.

11.12.

Vegyük a cipő és zokni felvételének problémáját, ahogy a 11.3. alfejezetben definiáltuk. Alkalmazzuk a GRAPHPLAN algoritmust erre a problémára, és mutassuk meg, hogyan áll elő a megoldás. Adjuk hozzá a kabát és a kalap felvételére szolgáló cselekvéseket. Adjuk meg azt a részben rendezett tervet, ami megoldás, és mutassuk meg, hogy ennek 180 különböző sorrendezése van. Mi a 180 különböző sorrendezés reprezentációjához szükséges különböző tervkészítő gráf megoldások minimális száma?

11.16. ábra - A Sussman-anomália kockavilág tervkészítési probléma
A Sussman-anomália kockavilág tervkészítési probléma

11.17. ábra - Shakey világa. Shakey képes egy szobán belül mozogni, át tud menni a szobák közötti ajtókon, fel tud mászni tárgyakra, el tudja tolni a mozdítható tárgyakat, valamint a villanyt tudja kapcsolni.
Shakey világa. Shakey képes egy szobán belül mozogni, át tud menni a szobák közötti ajtókon, fel tud mászni tárgyakra, el tudja tolni a mozdítható tárgyakat, valamint a villanyt tudja kapcsolni.

11.13.

Az eredeti STRIPS programot a Shakey robot irányítására készítették. A 11.17. ábra a Shakey világának egy változatát mutatja, melyben négy szoba sorakozik egy folyosó mentén, melyek mindegyikének van egy ajtaja és van benne egy villanykapcsoló.

Shakey világának cselekvései tartalmazzák az egyik helyről a másikra való mozgást, mozgatható tárgyak (mint dobozok) eltolását, szilárd testekre (mint dobozokra) való fel- és lemászást, és villanykapcsolók fel-, illetve lekapcsolását. A robot önmagában soha nem volt elég ügyes ahhoz, hogy egy dobozra másszon vagy egy kapcsolót átkapcsoljon, de a STRIPS tervkészítő képes a robot képességein túlmutató terveket találni és megadni. Shakey hat cselekvése a következő:

  • A Megy(x, y), ami feltételezi, hogy Shakey x-ben van, valamint az x és y helyek ugyanazon szobában vannak. Konvenció alapján a két szoba közötti ajtó mindkét szobában benne van.

  • A b doboz eltolása x pozícióból ugyanazon szoba y pozíciójába: Tol(p, x, y). Szükségünk lesz a Doboz predikátumra és konstansokra a dobozokhoz.

  • Dobozra felmászás: Felmászik(b); dobozról lemászás: Lemászik(b). Szükségünk lesz a Rajta predikátumra és a Padló konstansra.

  • A villany felkapcsolása: Felgyújt(s); lekapcsolása: Leolt(s). A lámpa fel-, illetve lekapcsolásához Shakey-nek egy dobozon kell állnia a villanykapcsoló mellett.

A 11.17. ábra alapján írja fel Shakey hat cselekvését és a kiinduló állapotot STRIPS jelölésekkel. Készítsen tervet Shakey számára, hogy a Doboz2 dobozt a Szoba2 szobába mozgassa.

11.14.

Láttuk, hogy a tervkészítési gráfok, csak ítéletlogikai cselekvéseket képesek kezelni. Mi van, hogyha a tervkészítő gráfokat a célban változókat is tartalmazó problémákra kívánjuk alkalmazni, mint az Ott(P1, x) ∧ Ott(P2, x), ahol x egy véges terület pozícióiból kerül ki? Hogyan tudna egy ilyen problémát átkódolni, hogy tervkészítő gráfokkal dolgozhasson? (Segítség: emlékezzen a részben rendezett tervkészítés Vége cselekvésére. Ehhez milyen előfeltételeknek kellene tartozni?)

11.15.

Egészen eddig feltételeztük, hogy a cselekvések csak a megfelelő helyzetekben kerülnek végrehajtásra. Nézzük, hogy az ítéletlogikai követő állapot axiómák (mint a 11.1 egyenlet axiómája) mit mondanak az olyan cselekvésekről, melyek előfeltételei nem teljesülnek.

  1. Mutassa meg, hogy az axiómák azt jósolják, hogy semmi sem történik, amikor egy cselekvést olyan állapotban hajtunk végre, melyben az előfeltételei nem teljesülnek.

  2. Vegyünk egy p tervet, ami tartalmazza a cél eléréséhez szükséges cselekvéseket és illegális cselekvéseket is. Igaz, hogy ebben az esetben

kiinduló állapot ∧ követő állapot axiómák ∧ p ⊨ cél

  1. Egy szituációkalkulusban elsőrendű követő állapot axiómák esetén (mint a 10. fejezetben) lehetséges bizonyítani, hogy egy illegális cselekvéseket tartalmazó terv elérje a célt?

11.16.

A repülőtér problémakörből adott példákkal magyarázza meg, hogy a szimbólumszétválasztás hogyan csökkenti az előfeltétel és a cselekvéskizárási axiómák méretét. Származtasson egy általános képletet, mely az axiómahalmazok méretét adja meg az időlépések száma, a cselekvéssémák száma, ezek aritása, valamint a tárgyak száma függvényében.

11.17.

A 11.15. ábrán szereplő SATPLAN algoritmusban a minden kielégíthetőségi algoritmus hívás egy további gT célt eredményez, ahol a T értékkészlete 0 … Tmax. Tegyük fel, hogy ehelyett a kielégíthetőségi algoritmust csak egyszer hívjuk meg a g0 ∨ g1 ∨ ... ∨ gTmax céllal.

  1. Ez mindig ad vissza tervet, amennyiben létezik egy Tmax hosszúságú vagy annál rövidebb terv?

  2. Eredményez ez a módszer új hibás megoldásokat?

  3. Vizsgáljuk meg, hogy hogyan lehetne módosítani egy kielégíthetőségi algorimust, például a WALKSAT algoritmust, hogy az (amennyiben létezik) rövid megoldásokat találjon, amennyiben hasonló diszjunktív célt kap.


[117] A terminológia kissé zavaros. Sok szerző a nemlineáris (nonlinear) jelzőt a „részben rendezett” értelemben használja. Ez kissé különbözik Sacerdotti eredeti szóhasználatától, aki ezt az összefésült tervekre használta.

fel