11.1. A tervkészítési probléma
Fontoljuk meg, hogy mi történne, ha egy közönséges, a standard keresési algoritmusokat – mélységi keresés, A* stb.– használó problémamegoldó ágens valós nagyméretű problémákkal kerülne szembe. Ez segíthet abban, hogy jobb tervkészítő ágenseket tervezzünk.
A legkézenfekvőbb nehézség, hogy a problémamegoldó ágenst lebéníthatnák a szükségtelen cselekvések. Vegyük például a Mesterséges intelligencia modern megközelítésben c. könyv internetes megvásárlásának a feladatát. Tegyük fel, hogy minden egyes 10 jegyű ISBN szám megvásárlása egy-egy cselekvés, ez összesen 10 milliárd cselekvést jelent. A keresési algoritmusnak mind a 10 milliárd cselekvés végállapotát meg kellene vizsgálnia, hogy megtalálja a célnak megfelelőt, nevezetesen, hogy birtokoljuk a 9635454112 ISBN számú könyvet. Másrészről egy értelmes tervkészítő ágensnek képesnek kell lenni arra, hogy a pontos cél Birtokol(ISBN9635454112) leírásából visszafelé dolgozva közvetlenül eljusson a Vásárol(ISBN9635454112) cselekvéshez. Hogy ezt megtehesse, az ágensnek arra az általános tudásra van szüksége, hogy a Vásárol(x) következménye a Birtokol(x). Ha adott ez a tudás, a tervező egy egyszerűsítési lépésben el tudja dönteni, hogy a Vásárol(ISBN9635454112) a helyes cselekvés.
A következő nehézség, egy jó heurisztika (heuristic function) meghatározása. Tegyük fel, hogy az ágens feladata négy különböző könyv megvásárlása. Ebből 1040 négylépéses terv adódik, azaz nem kérdéses, hogy egy megfelelő heurisztika nélküli keresés értelmetlen. Az ember számára egy állapot költségének becslésére kézenfekvő heurisztika a továbbiakban még megvásárolandó könyvek száma. Sajnos ez nem nyilvánvaló egy problémamegoldó ágens számára, hisz az a céltesztet egy fekete dobozként látja, mely minden állapotra mindössze egy igaz-hamis értéket ad vissza. Ennek következményeképp a problémamegoldó ágens nem autonóm; azaz emberi beavatkozást igényel minden új problémánál az alkalmazható heurisztika megadására. Másrészről, ha az ágensnek rendelkezésére áll a cél leírása, mint részcélok konjunkciója, akkor használhat egy egyszerű feladatfüggetlen heurisztikát: a még nem teljesített részcélok számát. A könyvvásárlási feladat esetén a cél Birtokol(A) ∧ Birtokol(B) ∧ Birtokol(C) ∧ Birtokol(D) lenne, és a Birtokol(A) ∧ Birtokol(C) állapot költsége 2. Így az ágens számára automatikusan elérhető a helyes heurisztika erre és más problémákra is. A fejezet későbbi részében látni fogjuk, hogy hogyan lehet létrehozni olyan kifinomultabb heurisztikákat, ami a célstruktúráján túl számba veszi a végrehajtható cselekvéseket is.
Végül a problémamegoldó ágens nem hatékony, mert nem tudja kihasználni a problémadekompozíció (problem decomposition) lehetőségét. Vegyük például a következő feladatot: több csomagot kell kiszállítanunk a megfelelő címekre, melyek Ausztrália különböző pontjain találhatók. Jó megközelítés, ha megkeressük a célpontokhoz legközelebb eső reptereket, és felosztjuk a teljes problémát több részfeladatra; repterenként egyre. Az egy reptéren keresztül irányított csomagok esetén a további dekompozíció lehetősége a célvárostól függ. Az 5. fejezetben láttuk, hogy egy ilyen felbontás képessége hozzájárul a kényszerkielégítési feladatmegoldók hatékonyságához. A tervkészítőkre ugyanez igaz: a legrosszabb esetben n csomag legjobb kiszállítási tervének elkészítése O(n!), míg ha a feladat k egyenlő részre bontható ez mindössze O((n/k)! × k) komplexitású feladat.
Ahogy az 5. fejezetben megjegyeztük, a teljesen dekomponálható problémák jók, de ritkák.[111] A legtöbb tervkészítő rendszer felépítése – különösen a 11.3. fejezetben bemutatásra kerülő részben rendezett tervkészítő felépítése – azon a feltételezésen alapul, mely szerint a legtöbb valós, életszerű probléma majdnem dekomponálható (nearly decomposable). Ez annyit jelent, hogy a tervkészítő dolgozhat független részcélokon, de a résztervek összekombinálása további feladatokat eredményezhet. Néhány feladat esetén ez a feltételezés nem helytálló, mert az egyik részcél kidolgozása gyakran megbontja a másik részcélt. Ezek a részcélok közötti kölcsönhatások azok, amelyek a fejtörőket (mint a nyolcas kirakó) valójában fejtörővé teszik.
A fent leírtak alapján a tervkészítési problémák reprezentációjának – ami az állapotokat, cselekvéseket és célokat jelenti – lehetőséget kellene biztosítania a tervkészítő algoritmus számára, hogy a feladat logikai struktúráját kihasználhassa. Ennek kulcsa, hogy olyan nyelvet találjunk, ami kellően kifejező ahhoz, hogy a problémák egy széles körét leírja, ugyanakkor kellően szigorú ahhoz, hogy a leírásokon hatékony algoritmusok működhessenek. Ebben a fejezetben először körvonalazzuk a klasszikus tervkészítők által használt alapnyelvet, ami STRIPS néven ismert.[112] Később rámutatunk a számos módosítási lehetőségből néhányra a STRIPS-szerű nyelvekben.
Az állapotok leírása. A tervkészítők a világot logikai feltételekre dekomponálják, és az állapotokat a pozitív literálok konjunkciójaként írják le. Tekintsük az ítéletlogikai literálokat; például a Szegény ∧ Ismeretlen reprezentálhatja egy szerencsétlen ágens állapotát. Elsőrendű literálokat is felhasználunk; például Ott(Repülő1, Melbourne) ∧ Ott(Repülő2, Sydney) a csomagszállítási feladat egy állapotát írhatja le. Az elsőrendű logikai állapotleírások literáljainak alap- és függvénymentes literálnak (ground and function-free) kell lenniük. Az olyan literálok, mint az Ott(x, y) vagy az Ott(Apja(Ferenc), Sydney) nem megengedettek. A zárt világ feltételezést (closed-world assumption) használjuk, ami annyit tesz, hogy a nem felsorolt állításokat hamisnak vesszük.
A célok leírása. A cél egy részlegesen definiált állapot, melyet pozitív alapliterálok konjunkciója reprezentál, mint Gazdag ∧ Híres vagy Ott(P2, Tahiti). Az s ítéletlogikai állapot kielégíti a c célt (goal satisfiction), ha s tartalmazza a c-ben szereplő összes atomot (és esetleg még továbbiakat). Például a Gazdag ∧ Híres ∧ Szomorú állapot kielégíti a Gazdag ∧ Híres célt.
A cselekvések leírása. A cselekvést a következő két állapot határozza meg: az előfeltétel, aminek teljesülni kell az akció végrehajtásához, és a következmény, ami a végrehajtás eredményeként lép fel. Például két állomás közötti repülés leírása az alábbi:
Cselekvés(Repül(p, honnan, hova),
Előfeltétel: Ott(p, honnan) ∧ Repülő(p) ∧ Repülőtér(honnan) ∧ Repülőtér(hova)
Következmény: ¬Ott(p, honnan) ∧Ott(p, hova))
Ezt pontosabban cselekvési sémának (action schema) nevezzük, ami azt takarja, hogy ez számos különböző cselekvést reprezentál, ami a p, honnan és a hova változók különböző behelyettesítéseivel származtatható. Általánosságban a cselekvési séma három fő részből áll:
-
A cselekvés megnevezése és paraméterlistája – például a Repül(p, honnan, hova) – a cselekvés azonosítására szolgál.
-
Az előfeltétel (precondition), függvényektől mentes pozitív literálok konjunkciója, azt mutatva, hogy milyen feltételeknek kell előzetesen teljesülni a cselekvés végrehajtásához.
-
A következmény (effect), függvényektől mentes literálok konjunkciója, ami leírja, hogy az állapot hogyan változik, amikor a cselekvés végrehajtásra kerül. A cselekmény eredményeképp adódó következményrészben szereplő P pozitív literál igaz értéket kap, míg a ¬P hamis értéket vesz fel. A következményrészben szereplő változóknak a cselekvés előfeltételei között is szerepelni kell.
Az olvashatóság javítása érdekében néhány tervkészítő következményrészt szétválasztja egy hozzáadás listára (add list) a pozitív és egy törlés listára (delete list) a negatív literáloknak.
Most hogy a tervkészítők reprezentációjának szintaxisát definiáltuk, adjuk meg a szemantikát is. Ennek legegyszerűbb módja, ha leírjuk, hogy a cselekvések hogyan módosítják az állapotot. (Egy másik lehetséges módszer, hogy egy direkt fordítást specifikálunk a következő állapot axiómákra, melyek szemantikája az elsőrendű logikából származik. Lásd 11.3. feladat.) Először is azt mondjuk, hogy egy cselekvés alkalmazható (applicable) minden állapotban, ami kielégíti az előfeltételeket; egyébként a cselekvés hatástalan. Egy elsőrendű séma esetében az alkalmazhatóság elérése az előfeltételek egy θ behelyettesítését vonja maga után. Tegyük fel például, hogy a jelen állapot leírása:
Ott(P1, JFK) ∧ Ott(P2, SFO) ∧ Repülő(P1) ∧ Repülő(P2)
∧ Repülőtér(JFK) ∧ Repülőtér(SFO)
Ez teljesíti az
Ott(p, honnan) ∧ Repülő(p) ∧ Repülőtér(honnan) ∧ Repülőtér(hova)
előfeltételt a {p/P1, honnan/JFK, hova/SFO} behelyettesítésekkel (és másokkal is – lásd 11.2. feladat). Így a konkrét Repül(P1, JFK, SFO) cselekvés alkalmazható.
Az s állapotból kiindulva az alkalmazható a cselekvés végrehajtásának eredménye az s' állapot, ami azonos s-sel, kivéve, hogy az a cselekvés következményrészében szereplő pozitív P literálokat az s’-höz adjuk, míg bármilyen ¬P negatív literált eltávolítjuk s’-ből. Így a Repül(P1, JFK, SFO) cselekvés után az állapot a következő:
Ott(P1, SFO) ∧ Ott(P2, SFO) ∧ Repülő(P1) ∧ Repülő(P2)
∧ Repülőtér(JFK) ∧ Repülőtér(SFO)
Vegyük észre, hogy a már szereplő pozitív következményeket nem szúrjuk be még egyszer, illetve ha egy negatív literál nem szerepel az állapotleírásban, akkor a következmény ezen része figyelmen kívül hagyható. Ez a definíció testesíti meg az úgynevezett STRIPS feltételezést (assumption): minden a következményben nem szereplő literál változatlan marad. Így a STRIPS elkerüli a 10. fejezetben bemutatott reprezentációs keret problémát (representional frame problem).
Végezetül definiálhatjuk a tervkészítési probléma megoldását (solution). Legegyszerűbb formájában ez csak egy cselekvéssorozat, melyet a kiindulási állapotból végrehajtva a célállapotot eredményezi. A fejezet további részeiben a megoldások cselekvések részben rendezett sorozatai is lehetnek, amennyiben minden cselekvéssorozat, ami megfelel ennek a részben rendezésnek, megoldás.
A sokféle megkötés, korlátozás amit a STRIPS nyelv tartalmaz, abban a reményben került beépítésre, hogy a tervkészítő algoritmusok egyszerűbbek és hatékonyabbak lehessenek, anélkül hogy a valós problémák leírását megnehezítenék. Egyike a legfontosabb megkötéseknek, hogy a literáloknak függvénymenteseknek kell lenniük. Ezzel a megkötéssel biztosíthatjuk, hogy egy adott problémához tartozó bármely akció séma ítéletkalkulus formára, azaz változómentes ítéletlogikai cselekvés reprezentációk véges halmazára hozható. (A téma bővebb leírását lásd a 9. fejezetben.) Például a légi szállítási problémakörben 10 repülő és 5 repülőtér esetén a Repül(p, honnan, hova) séma 10 × 5 × 5 = 250 ítéletlogikai cselekvésre fordítható. A 11.4. és 11.5. alfejezet tervkészítői közvetlenül az ítéletkalkulusra hozott leírással dolgoznak. Ha függvényszimbólumokat is megengedünk, akkor végtelen sok állapot és cselekvés határozható meg.
11.1. ábra - A Strips és az ADL nyelv összehasonlítása a tervkészítési feladatok reprezentációjának szempontjából. Mindkét esetben a célok úgy viselkednek, mint egy paraméterek nélküli cselekvés előfeltételei.
Napjainkra, nyilvánvalóvá vált, hogy a STRIPS nem eléggé kifejező néhány valós problémakörhöz. Ennek eredményeképpen számos nyelvváltozatot dolgoztak ki. A 11.1. ábra röviden összefoglalja az egyik legfontosabbat, a cselekvésleíró nyelvet (Action Description Language – ADL) úgy, hogy összehasonlítja azt a STRIPS alapverziójával. ADL nyelven a Repülés leírása az alábbi:
Cselekvés(Repül(p : Repülő, honnan : Repülőtér, hova : Repülőtér),
Előfeltétel: Ott(p, honnan) ∧ (honnan ≠ hova)
Következmény: ¬Ott(p, honnan) ∧ Ott(p, hova))
A p : Repülő írásmód az előfeltételek a paraméterlistájában a Repülő(p) egy rövidítése, ami nem növeli a kifejezőképességet, de javítja az olvashatóságot. (Mindemellett redukálja a létrehozható ítéletlogikai cselekvések számát.) A (honnan ≠ hova) előfeltétel azt a tényt fejezi ki, hogy egy repülőút kiindulási és célállomása nem lehet azonos. Ezt a STRIPS nyelvben nem lehetne tömören kifejezni.
A mesterséges intelligenciában használt változatos tervkészítő formalizmusokat egy szabványos szintaxisba rendszerezik, amit tervkészítési terület definíciós nyelvnek (Planning Domain Definition Language – PDDL) neveznek. Ez a nyelv lehetővé teszi a kutatók számára, hogy benchmark problémákat cseréljenek ki egymás között, és összevessék az eredményeket. A PDDL résznyelveket tartalmaz az ADL és a 12. fejezetben bemutatásra kerülő hierarchikus feladathálózatok számára.
A STRIPS és az ADL jelölésrendszere számos valós problémakörre megfelelő. A következő alfejezetek néhány egyszerű példát mutatnak be. Néhány számottevő megkötés azért még megmaradt. A legnyilvánvalóbb, hogy közvetlenül nem tartalmazzák a cselekvések véghatásait (ramifications). Például ha vannak emberek, csomagok vagy porcicák egy repülőn, akkor mindannyian helyet változtatnak egy repülés során. Ezeket a változásokat leírhatjuk, mint a repülés egyenes következményeit, így természetesebbnek tűnik a repülőgép tartalmának helyét, mint a gép helyének logikai következményét ábrázolni. Az ilyen állapotmegkötésekre (state constraints) a 11.5. alfejezet tartalmaz példákat. A hagyományos tervkészítő rendszerek meg sem próbálják megoldani a kvalifikációs problémát (qualification problem), azaz a nem reprezentált körülmények problémáját, melyek a cselekvés meghiúsulását okozhatják. A 12. fejezetben látni fogjuk, hogy a kvalifikációs probléma hogyan közelíthető meg.
A 11.2. ábra egy teherszállítási problémát mutat be, ami a teher be-, illetve kirakodását és állomások közötti légi szállítását tartalmazza. A probléma három cselekvéssel írható le: Berakodás, Kirakodás és Repülés. A cselekvések két predikátumot érintenek: a Benne(c, p) jelentése, hogy a c teher a p repülőgépben van, és az Ott(x, a) jelentése, hogy az x objektum (teher vagy repülőgép) az a repülőtéren található. Vegyük észre, hogy a teher nincs Ott sehol, ha Benne van egy repülőgépben, azaz az Ott valójában azt jelenti, hogy az objektum „elérhető a megadott helyen”. Tapasztalattal kell rendelkezni a cselekvésdefiníciók területén, ahhoz hogy az ilyen részleteket konzisztensen ábrázoljuk. A következő terv megoldása a feladatnak:
[Berakodás(C1, P1, SFO), Repülés(P1, SFO, JFK, Kirakodás(C1, P1, JFK)
Berakodás(C2, P2, JFK), Repülés(P2, JFK, SFO, Kirakodás(C2, P2, SFO)]
A mi reprezentációnk tisztán STRIPS nyelvű. Nevezetesen ez engedélyezi, hogy egy repülő kiinduló és célállomása azonos repülőtér legyen. Az ADL egyenlőtlenség operátorai ezt kizárhatnák.
Vegyük a kerékcsere problémáját. Pontosabban a célunk az, hogy egy jó pótkerék legyen felszerelve az autó tengelyére, ahol a kiinduló állapotban egy lapos kerék van felszerelve, míg a jó pótkerék a csomagtartóban található. Az egyszerűség kedvéért a mi feladatunk elég absztrakt, azaz nincsenek beragadt csavarok vagy egyéb más nehézségek. Csak négy cselekvés van: a pótkerék kivétele a csomagtartóból, a lapos kerék eltávolítása a tengelyről, a pótkerék felszerelése és az autó magára hagyása reggelig. Feltételezzük, hogy az autó egy igen rossz környéken áll, ahol az autó magára hagyása azt eredményezi, hogy reggelre eltűnnek a kerekek.
A 11.3. ábra a feladat ADL leírását tartalmazza. Vegyük észre, hogy ez a megadás pusztán ítéletlogikai. A STRIPS nyelven túlmutat, hogy a TeddFel(Pótkerék, Tengely) cselekvéshez a ¬Ott(Pótkerék, Tengely) negált előfeltétel tartozik. Ezt elkerülhetnénk egy SzabaddáTesz(Tengely) használatával, amint azt a következő példában látni fogjuk.
Az egyik leghíresebb tervkészítési terület a kockavilág (blocks world) probléma. A terület asztallapon elhelyezett kockákból áll.[113] A kockákat egymásra rakhatjuk, de egy kockán közvetlenül mindig csak egyetlen másik helyezhető el. A kockákat egy robotkarral mozgathatjuk, amely fel tud venni egy kockát, majd azt vagy az asztalra, vagy egy másik kocka tetejére le tudja tenni. A robotkar egyszerre csak egy kockát tud felemelni, vagyis olyat nem, amelynek a tetején egy másik kocka van. A cél mindig egy vagy több kockaoszlop építése, amelyekben a kockák egymáshoz képesti elhelyezkedése meghatározott. A cél lehet például két oszlop építése, amelyek közül az egyikben az A kocka a B tetején van, a másikban pedig a C kocka van a D tetején.
A Rajta(b, x) jelölést használjuk annak leírására, hogy a b kocka az x-en van, ahol az x egy másik kockát vagy az asztallapot jelenti. A Mozgat(b, x, y) cselekvés a b kockát a x tetejéről az y tetejére mozgatja. A b kocka mozgatásának előfeltétele, hogy rajta semmi ne legyen. Ennek leírása az elsőrendű logikában a ¬∃x Rajta(x, b) vagy ∀x ¬Rajta(x, b). Az ADL nyelvben ezek előfeltételek lehetnének. A STRIPS nyelv keretei között maradhatunk az Üres(x) predikátum bevezetésével, ami akkor igaz, ha semmi nincs x-en.
A Mozgat cselekvés a b kockát az x-ről az y-ra mozgatja, ha mind a b, mind pedig az y üres. A mozgatás után az x üres, de az y már nem. A Mozgat formális leírása STRIPS-ben a következő:
Cselekvés(Mozgat(b, x, y),
Előfeltétel: Rajta(b, x) ∧ Üres(b) ∧ Üres(y)
Következmény: Rajta(b, y) ∧ Üres(x) ∧ ¬Rajta(b, x) ∧ ¬Üres(y))
Sajnos ez a cselekvés nem kezeli jól az Üres predikátumot, ha az x vagy az y az asztalon van.
Ha x = Asztal, a cselekvés következményei között szerepel az Üres(Asztal) is, de az asztalnak nem kell kiürülnie a mozgatás után, ha pedig y = Asztal, megjelenik az Üres(Asztal) előfeltétel, holott az asztalnak nem kell üresnek lenni ahhoz, hogy bármit is tehessünk rá. Ennek kiküszöbölésére két dolgot tehetünk. Először is bevezetünk egy új cselekvést, amellyel egy b kockát az asztalra tehetünk:
Cselekvés(AsztalraTesz(b, x, y),
Előfeltétel: Rajta(b, x) ∧ Üres(b)
Következmény: Rajta(b, Asztal) ∧ Üres(x) ∧ ¬Rajta(b, x))
Másodszor az Üres(b) predikátumot úgy értelmezhetjük, hogy „b tetején van elég szabad hely, ahová a kockát letehetjük”. Ezek szerint az Üres(Asztal) mindig igaz. Az egyetlen probléma, hogy semmi nem gátolja a tervkészítőt abban, hogy a Mozgat(b, x, Asztal) cselekvést alkalmazza az AsztalraTesz(b, x) helyett. Vagy együtt élünk ezzel a problémával (amely egyébként a szükségesnél nagyobb keresési teret eredményez, de nem vezet hibás válaszokhoz), vagy bevezethetjük a Kocka predikátumot, és a Mozgat cselekvés előfeltételeihez hozzátehetjük a Kocka(x) ∧ Kocka(b) részt.
11.4. ábra - A kockavilág tervkészítési problémája: egy három kockából álló torony építése. A [Mozgat(B, Asztal, C), Mozgat(A, Asztal, B)] cselekvéssor egy lehetséges megoldás.
![A kockavilág tervkészítési problémája: egy három kockából álló torony építése. A [Mozgat(B, Asztal, C), Mozgat(A, Asztal, B)] cselekvéssor egy lehetséges megoldás.](/mi_almanach/sites/default/files/books/35/files/kepek/11-04.png)
Végül itt van még az olyan hibás műveletek esete, mint a Mozgat(B, C, C), amely hatástalan kellene legyen, ehelyett azonban ellentmondó következményekhez vezet. Általában nem foglalkozunk az ilyen jellegű problémákkal, mert nemigen vannak hatással az előállított tervekre. A helyes megközelítés, hogy egyenlőtlenségi előfeltételeket vezetünk be, amint azt a 11.4. ábra mutatja.
[111] Vegyük észre, hogy még a csomagkiszállítási feladat sem teljesen dekomponálható. Vannak esetek, amikor jobb a csomagokat mégis egy távolabbi reptérre irányítani, ha ezzel megspórolhatunk egy külön repülőjáratot a közelire. Mindemellett a legtöbb szállítócég inkább a már bejáratott dekomponált megoldásokhoz ragaszkodik, hogy csökkentse a számítási és szervezési nehézségeket.
[112] A STRIPS a STandford Research Institute Problem Solver rövidítése.
[113] A tervkészítés kutatásában használt kockavilág sokkal egyszerűbb, mint az SHRDLU verzió, amit az 1.3.3. szakasz - Korai lelkesedés, nagy elvárások (1952–1969) részben mutattunk be.
