Mesterséges Intelligencia MI Tervkészítés
Dobrowiecki Tadeusz Eredics Péter, és mások BME I.E. 437, 463-28-99
[email protected], http://www.mit.bme.hu/general/staff/tade
Utasítsuk a háztartási robotunkat: "Vegyél egy liter tejet, egy kiló banánt és egy akkumulátoros fúrót!" Komplexitás kérdése: O(bd) 4-féle cselekvés, terv 10 lépésben
O(410) = 106 Reális-e a probléma?
100-féle cselekvés, terv 50 lépésben
O(10050) = 10100
= gazdag cselekvéskészlet + komplex célok? Robotok valós környezetben Csapatmozgatások Gyártástervezés Űrhajó szerelése …..
Egy hatékony tervkészítő (un. Planner) input: tervkészítési probléma = rendszer képességei, kezdeti helyzet, cél output: terv (cs1, cs2, …, csN), ill.
un. klasszikus tervkészítés minden véges, teljesen hozzáférhető determinisztikus, csak ágens cselekvése, ismert explicit célok, szekvenciális tervek implicit idő, off-line tervkészítés
doménfüggő (konkrét feladatra kifejlesztett) konfigurálható – Hierarchikus Taszk Háló doménfüggetlen – STRIPS, ADL, PDDL keresés szituációk terében keresés bizonyítás transzformáció (ítéletlogikai kielégíthetőség) SAT, int. progr. keresés tervek terében részben rendezett (POP) tervgráf (Graphplan) heurisztikák hierarchikus, eshetőségi, végrehajtás és monitorozás
A keresés baja: a tudás nem hatékony használata Cselekvések leírása: csak a követő állapotgeneráláshoz. Állapotleírások: csak a követő állapotok generálásakor, heurisztika kiértékelésekor és a célállapot vizsgálatakor. Célok leírása: csak a célállapot vizsgálatára. Tervek leírása: cselekvések végrehajtási sorrendje kötött, a kezdeti állapottól (vagy a célállapotból) indulnak Heurisztika: csak a lehetséges állapotok közül választ, de a vizsgálandó cselekvések körét nem tudja szűkíteni. Ágensnek már a kezdeti állapotban el kell döntenie, merre induljon, de gyakorlatilag semmit sem tud, merre érdemes.
Alapgondolat Ha a cél része „van(Tej)” predikátum, és pl. „Vesz(Tej)” cselekvéssel „van(Tej)” teljesül, akkor célszerű olyan tervet készíteni, amelyben szerepel „Vesz(Tej)” cselekvés.
Vesz(Tej) – a terv első lépése? Utolsó lépése? Hányadik lépése legyen? Nem tudni! De a terv készítését érdemes ezzel kezdeni!
A tervkészítés gyakorlatiassá tétele Leíró nyelv korlátozása: logika, de korlátos, a teljes körű bizonyítás nem lesz használható. Speciális tervkészítő (planner) az általános célú tételbizonyító helyett. ca. 1970 STRIPS (Stanford Research Institute Problem Solver) Állapotok, célok: függvénymentes rögzített literálok konjunkciói helyszín(Otthon) van(Tej) van(Banán) van(Fúró) … Cselekvés: STRIPS operátor előfeltétel: atomi formulák konjunkciója, igaznak kell lennie az operátor alkalmazhatóságához. következmény: (poz. vagy neg.) literálok konjunkciója, megadja, hogyan változik meg a szituáció az operátor alkalmazásakor. szituációváltozó nélkül is nem monoton, mert nem teljes körű logika Fontos gondolat: ez a reprezentáció lassan beépül az Informatika egészébe (robotika, ágens kommunikációs nyelvek, információ-feldolgozó rendszerek a világhálón, …
Szituációtér és tervtér szituációtérbeli tervkészítő progresszív tervkészítő (nagy elágazási tényező, óriási a keresési tér)
Elágazási tényező csökkentése: regresszív tervkészítés: visszafelé keresés a célállapot felől. váltsunk absztrakciót és teret, menjünk oda, ahol a komplexitás kisebb!
Keresés a lehetséges tervek terében – mit nyerünk? Indulás: egyszerű, befejezetlen, részleges (kezdetben „üres”) terv. Részleges terv bővítése újabb cselekvésekkel, míg el nem érünk egy teljes tervet, amely már az egész problémát megoldja. A keresés operátorai most a terveken végezhető finomító/ módosító műveletek: - egy új cselekvés hozzáadása, cselekvés elhagyása - valamilyen rendezési feltételek előírása - egy-egy érték kötése a változókhoz, stb. A megoldás az utolsó lépésben előálló terv (azaz az ágens cselekvéssorozata, a hozzá vezető út érdektelen. Tervtérben sokkal kevesebb (tip. 5-10) a lehetséges művelet, mint az ágens cselekvéskészlete! A legkisebb megkötés elvű Részben Rendezett Tervkészítő – RRT (Partial Order Planning POP) Az adott pillanatban fontos dolgokat dönti el, az összes többit később. A lépések sorrendjét nem kell mesterségesen előre rögzíteni. Ha egy gráf keletkezik, lehet azt utólag sorba rendezni, avagy linearizálni.
Egy terv formálisan: 1. A terv lépései: minden lépés a problémához kapcsolódó ágenscselekvés. 2. A lépések sorrendjére vonatkozó kényszerek: Si Sj Si megelőzi Sj-t, Si végrehajtásának Sj végrehajtása előtt kell megtörténnie, de nem szükségszerűen közvetlenül előtte. 3. A változó értékeinek lekötése: v = x, ahol v egy adott lépésben szereplő változó, és x egy konstans, vagy egy másik változó. 4. Okozati kapcsolatok: Si -- c --> Sj (un. védett kapcsolatok) "Si előállítja c-t Sj számára" - az egyes lépések tervbeli rendeltetését rögzítik: Si rendeltetése, hogy előállítsa Sj számára a c előfeltételét. Az eredeti probléma „becsomagolása”: a kezdeti „üres” terv a még nem megoldott problémát írja le: - fiktív Start és Cél lépések. Egyik lépéshez sem tartozik cselekvés, a kész tervből a végrehajtása előtt elhagyandók. - Start-nak nincsenek előfeltételei, a következménye a kiinduló állapot. - Cél lépés előfeltétele a végállapot, és nincsenek következményei.
Egy „üres” terv
A tervkészítés által visszaadott megoldás: - az ágens által végrehajtható (helyes) - garantálja a cél elérését (teljes) Teljes: Minden tervbeli Sj lépés minden c előfeltétele, vagy igaz a kezdeti állapotban, vagy létezik a tervben egy olyan Si lépés, amely az Sj lépés c előfeltételét előállítja, azaz: c az Si lépés egyik következménye, és az adott előfeltételt egyetlen másik lépés sem szünteti meg: (1) Si < Sj és c Köv(Si) (2) Nincs olyan Sk lépés, melyre (c) Köv(Sk), ahol teljesül a Si < Sk < Sj a terv bizonyos sorba rendezésében. Konzisztens: nincs benne ellentmondó sorba rendezés vagy lekötés.
Vissza a példához
Op(Cselekvés: Start, Következmény: helyszín(Otthon) árusít(SzB, Fúró) árusít(ÉB,Tej) árusít(ÉB, Banán)) Op(Cselekvés: Előfeltétel:
Cél, van(Fúró) van(Tej) van(Banán) helyszín(Otthon))
Op(Cselekvés: Megy(ott), Előfeltétel: helyszín(itt), Következmény: helyszín(ott) helyszín(itt)) Op(Cselekvés: Vesz(x), Előfeltétel: helyszín(bolt) árusít(bolt,x), Következmény: van(x))
Start H(O) Á(SzB,F) Á(ÉB,T) Á(ÉB,B)
V(F) V(T) V(B) H(O)
Cél
Start H(O) Á(SzB,F) Á(ÉB,T) Á(ÉB,B)
Az algoritmus „vadászik”
Alkalmazott ellenszer =
(a) a még nem teljesített előfeltételekre, (b) a fenyegető Si < Sk < Sj „beszúrt” cselekvésekre (ld. a teljesség definíciója).
(a) meglévő operátorok újszerű felhasználása, új operátor hozzáadása, (b) új rendezési kényszerek (ld. a teljesség definíciója).
V(F) V(T) V(B) H(O)
Cél
Start
célállapot-teszt?
H(O) Á(SzB,F) Á(ÉB,T) Á(ÉB,B)
beszúrás
H(b) Á(b,x)
Vesz(F) V(x)
x/F, b/SzB V(F) V(T) V(B) H(O)
Cél
Start
célállapot-teszt?
H(O) Á(SzB,F) Á(ÉB,T) Á(ÉB,B)
lekötés
H(SzB) Á(SzB,F)
Vesz(F) V(F)
V(F) V(T) V(B) H(O)
Cél
Start
célállapot-teszt?
H(O) Á(SzB,F) Á(ÉB,T) Á(ÉB,B)
beszúrás lekötés
H(SzB) Á(SzB,F)
H(ÉB) Á(ÉB,T)
Vesz(F)
Vesz(T)
V(F)
V(T)
V(F) V(T) V(B) H(O)
Cél
célállapot-teszt?
Start
H(O) Á(SzB,F) Á(ÉB,T) Á(ÉB,B)
beszúrás lekötés
H(SzB) Á(SzB,F)
H(ÉB) Á(ÉB,T)
H(ÉB) Á(ÉB,B)
Vesz(F)
Vesz(T)
Vesz(B)
V(F)
V(T)
V(B)
V(F) V(T) V(B) H(O)
Cél
célállapot-teszt?
Start
H(O) Á(SzB,F) Á(ÉB,T) Á(ÉB,B)
újrafelhasználás
H(SzB) Á(SzB,F)
H(ÉB) Á(ÉB,T)
H(ÉB) Á(ÉB,B)
Vesz(F)
Vesz(T)
Vesz(B)
V(F)
V(T)
V(B)
V(F) V(T) V(B) H(O)
Cél
célállapot-teszt?
Start
H(O) Á(SzB,F) Á(ÉB,T) Á(ÉB,B)
beszúrás H(i)
Megy(x) H(o) H(i)
H(SzB) Á(SzB,F)
H(ÉB) Á(ÉB,T)
H(ÉB) Á(ÉB,B)
Vesz(F)
Vesz(T)
Vesz(B)
V(F)
V(T)
V(B)
V(F) V(T) V(B) H(O)
Cél
célállapot-teszt?
Start
H(O) Á(SzB,F) Á(ÉB,T) Á(ÉB,B)
lekötés H(i)
Megy(SzB) H(SzB) H(i)
H(SzB) Á(SzB,F)
H(ÉB) Á(ÉB,T)
H(ÉB) Á(ÉB,B)
Vesz(F)
Vesz(T)
Vesz(B)
V(F)
V(T)
V(B)
V(F) V(T) V(B) H(O)
Cél
célállapot-teszt?
Start
H(O) Á(SzB,F) Á(ÉB,T) Á(ÉB,B)
beszúrás H(i)
lekötés H(i) Megy(SzB)
Megy(ÉB) H(ÉB) H(i)
H(SzB) H(i)
H(SzB) Á(SzB,F)
H(ÉB) Á(ÉB,T)
H(ÉB) Á(ÉB,B)
Vesz(F)
Vesz(T)
Vesz(B)
V(F)
V(T)
V(B)
V(F) V(T) V(B) H(O)
Cél
célállapot-teszt?
Start
H(O) Á(SzB,F) Á(ÉB,T) Á(ÉB,B)
lekötés H(O)
H(O)
Megy(SzB)
Megy(ÉB)
H(SzB) H(O)
H(ÉB) H(O)
H(SzB) Á(SzB,F)
H(ÉB) Á(ÉB,T)
H(ÉB) Á(ÉB,B)
Vesz(F)
Vesz(T)
Vesz(B)
V(F)
V(T)
V(B)
V(F) V(T) V(B) H(O)
Cél
célállapot-teszt?
Start
H(O) Á(SzB,F) Á(ÉB,T) Á(ÉB,B)
újrafelhasználás H(O)
H(O)
Megy(SzB)
Megy(ÉB)
H(SzB) H(O)
H(ÉB) H(O)
H(SzB) Á(SzB,F)
H(ÉB) Á(ÉB,T)
H(ÉB) Á(ÉB,B)
Vesz(F)
Vesz(T)
Vesz(B)
V(F)
V(T)
V(B)
V(F) V(T) V(B) H(O)
Cél
célállapot-teszt?
Start
H(O) Á(SzB,F) Á(ÉB,T) Á(ÉB,B)
H(O)
H(O)
Megy(SzB)
Megy(ÉB)
H(SzB) H(O)
H(ÉB) H(O)
H(SzB) Á(SzB,F)
H(ÉB) Á(ÉB,T)
H(ÉB) Á(ÉB,B)
Vesz(F)
Vesz(T)
Vesz(B)
V(F)
V(T)
V(B)
V(F) V(T) V(B) H(O)
Cél
Fenyegetés!
Start
célállapot-teszt?
H(O) Á(SzB,F) Á(ÉB,T) Á(ÉB,B)
H(O)
H(O)
Megy(SzB)
Megy(ÉB)
H(SzB) H(O)
H(ÉB) H(O)
Egy lépés következménye elrontja egy másik lépés előfeltételét. Igaz, hogy parallel ágban, de majd sorba kell rendezni. H(SzB) Á(SzB,F) H(ÉB) Á(ÉB,B) És akkor ne legyen baj. H(ÉB) Á(ÉB,T)
Vesz(F)
Vesz(T)
Vesz(B)
V(F)
V(T)
V(B)
V(F) V(T) V(B) H(O)
Cél
Fenyegetés!
Védett kapcsolatok: hátramozdítás, előremozdítás
célállapot-teszt?
Start
H(O) Á(SzB,F) Á(ÉB,T) Á(ÉB,B)
rendezések H(SzB)
H(O)
Megy(SzB)
Megy(ÉB)
H(SzB) H(O)
H(ÉB) H(SzB)
H(SzB) Á(SzB,F)
H(ÉB) Á(ÉB,T)
H(ÉB) Á(ÉB,B)
Vesz(F)
Vesz(T)
Vesz(B)
V(F)
V(T)
V(B)
V(F) V(T) V(B) H(O)
Cél
célállapot-teszt?
Start
H(O) Á(SzB,F) Á(ÉB,T) Á(ÉB,B)
rendezések H(SzB)
H(O)
Megy(SzB)
Megy(ÉB)
H(SzB) H(O)
H(ÉB) H(SzB)
H(SzB) Á(SzB,F)
H(ÉB) Á(ÉB,T)
H(ÉB) Á(ÉB,B)
Vesz(F)
Vesz(T)
Vesz(B)
V(F)
V(T)
V(B)
V(F) V(T) V(B) H(O)
Cél
célállapot-teszt?
Start
H(O) Á(SzB,F) Á(ÉB,T) Á(ÉB,B)
H(SzB)
H(O)
Megy(SzB)
Megy(ÉB)
H(SzB) H(O)
H(ÉB) H(SzB)
H(SzB) Á(SzB,F)
H(ÉB) Á(ÉB,T)
H(ÉB) Á(ÉB,B)
Vesz(F)
Vesz(T)
Vesz(B)
V(F)
V(T)
V(B)
V(F) V(T) V(B) H(O)
Cél
előremozdítás hátramozdítás
célállapot-teszt?
Start
H(O) Á(SzB,F) Á(ÉB,T) Á(ÉB,B)
beszúrás H(SzB)
H(O)
Megy(SzB)
Megy(ÉB)
H(SzB) H(O)
H(ÉB) H(SzB)
H(SzB) Á(SzB,F)
H(ÉB) Á(ÉB,T)
H(ÉB) Á(ÉB,B)
Vesz(F)
Vesz(T)
Vesz(B)
V(F)
V(T)
V(B)
H(x) V(F) V(T) V(B) H(O)
Cél
Megy(O) H(O) H(x)
célállapot-teszt?
Start
H(O) Á(SzB,F) Á(ÉB,T) Á(ÉB,B)
lekötés H(SzB)
H(O)
Megy(SzB)
Megy(ÉB)
H(SzB) H(O)
H(ÉB) H(SzB)
H(SzB) Á(SzB,F)
H(ÉB) Á(ÉB,T)
H(ÉB) Á(ÉB,B)
Vesz(F)
Vesz(T)
Vesz(B)
V(F)
V(T)
V(B)
X = O? X = SzB? X = ÉB?
H(x) V(F) V(T) V(B) H(O)
Cél
Megy(O) H(O) H(x)
célállapot-teszt?
Start
H(O) Á(SzB,F) Á(ÉB,T) Á(ÉB,B)
lekötés H(SzB)
H(O)
Megy(SzB)
Megy(ÉB)
H(SzB) H(O)
H(ÉB) H(SzB)
H(SzB) Á(SzB,F)
H(ÉB) Á(ÉB,T)
H(ÉB) Á(ÉB,B)
Vesz(F)
Vesz(T)
Vesz(B)
V(F)
V(T)
V(B)
H(ÉB) V(F) V(T) V(B) H(O)
Cél
Megy(O) H(O) H(ÉB)
Fenyegetés!
célállapot-teszt?
Start
H(O) Á(SzB,F) Á(ÉB,T) Á(ÉB,B)
H(SzB)
H(O)
Megy(SzB)
Megy(ÉB)
H(SzB) H(O)
H(ÉB) H(SzB)
H(SzB) Á(SzB,F)
H(ÉB) Á(ÉB,T)
H(ÉB) Á(ÉB,B)
Vesz(F)
Vesz(T)
Vesz(B)
V(F)
V(T)
V(B)
H(ÉB) V(F) V(T) V(B) H(O)
Cél
Megy(O) H(O) H(ÉB)
célállapot-teszt?
Start
H(O) Á(SzB,F) Á(ÉB,T) Á(ÉB,B)
rendezések H(SzB)
H(O)
Megy(SzB)
Megy(ÉB)
H(SzB) H(O)
H(ÉB) H(SzB)
H(SzB) Á(SzB,F)
H(ÉB) Á(ÉB,T)
H(ÉB) Á(ÉB,B)
Vesz(F)
Vesz(T)
Vesz(B)
V(F)
V(T)
V(B)
H(ÉB) V(F) V(T) V(B) H(O)
Cél
Megy(O) H(O) H(ÉB)
célállapot-teszt!
Start
H(O) Á(SzB,F) Á(ÉB,T) Á(ÉB,B)
H(SzB)
H(O)
Megy(SzB)
Megy(ÉB)
H(SzB) H(O)
H(ÉB) H(SzB)
H(SzB) Á(SzB,F)
H(ÉB) Á(ÉB,T)
H(ÉB) Á(ÉB,B)
Vesz(F)
Vesz(T)
Vesz(B)
V(F)
V(T)
V(B)
H(ÉB) V(F) V(T) V(B) H(O)
Cél
Megy(O) H(O) H(ÉB)
És kész is! a. Az előfeltételek elfogytak. Le kell állni. b. Minden előfeltétel biztosított más lépés által (a Start-ot) beleértve. c. Nincs nem konzisztens változólekötés. d. Minden védett kapcsolat meg van védve. Mi a terv? A lényeg a rendező kényszerek megfelelő figyelembe vétele Lépés
Lépés
Lépés
Lépés
Lépés
Lépés
Start H(O) Á(SzB,F) Á(ÉB,T) Á(ÉB,B)
H(SzB)
H(O)
Megy(SzB)
Megy(ÉB)
H(SzB) H(O)
H(ÉB) H(SzB)
H(SzB) Á(SzB,F)
H(ÉB) Á(ÉB,T)
H(ÉB) Á(ÉB,B)
Vesz(F)
Vesz(T)
Vesz(B)
V(F)
V(T)
V(B)
H(ÉB) V(F) V(T) V(B) H(O)
Cél
Megy(O) H(O) H(ÉB)
Start H(O) Á(SzB,F) Á(ÉB,T) Á(ÉB,B)
H(SzB)
H(O)
Megy(SzB)
Megy(ÉB)
H(SzB) H(O)
H(ÉB) H(SzB)
H(SzB) Á(SzB,F)
H(ÉB) Á(ÉB,T)
H(ÉB) Á(ÉB,B)
Vesz(F)
Vesz(T)
Vesz(B)
V(F)
V(T)
V(B)
H(ÉB) V(F) V(T) V(B) H(O)
Cél
Megy(O) H(O) H(ÉB)
Start H(O) Á(SzB,F) Á(ÉB,T) Á(ÉB,B)
H(SzB)
H(O)
Megy(SzB)
Megy(ÉB)
H(SzB) H(O)
H(ÉB) H(SzB)
H(SzB) Á(SzB,F)
H(ÉB) Á(ÉB,T)
H(ÉB) Á(ÉB,B)
Vesz(F)
Vesz(T)
Vesz(B)
V(F)
V(T)
V(B)
H(ÉB) V(F) V(T) V(B) H(O)
Cél
Megy(O) H(O) H(ÉB)
Start H(O) Á(SzB,F) Á(ÉB,T) Á(ÉB,B)
H(SzB)
H(O)
Megy(SzB)
Megy(ÉB)
H(SzB) H(O)
H(ÉB) H(SzB)
H(SzB) Á(SzB,F)
H(ÉB) Á(ÉB,T)
H(ÉB) Á(ÉB,B)
Vesz(F)
Vesz(T)
Vesz(B)
V(F)
V(T)
V(B)
H(ÉB) V(F) V(T) V(B) H(O)
Cél
Megy(O) H(O) H(ÉB)
Start H(O) Á(SzB,F) Á(ÉB,T) Á(ÉB,B)
H(SzB)
H(O)
Megy(SzB)
Megy(ÉB)
H(SzB) H(O)
H(ÉB) H(SzB)
H(SzB) Á(SzB,F)
H(ÉB) Á(ÉB,T)
H(ÉB) Á(ÉB,B)
Vesz(F)
Vesz(T)
Vesz(B)
V(F)
V(T)
V(B)
H(ÉB) V(F) V(T) V(B) H(O)
Cél
Megy(O) H(O) H(ÉB)
Start H(O) Á(SzB,F) Á(ÉB,T) Á(ÉB,B)
H(SzB)
H(O)
Megy(SzB)
Megy(ÉB)
H(SzB) H(O)
H(ÉB) H(SzB)
H(SzB) Á(SzB,F)
H(ÉB) Á(ÉB,T)
H(ÉB) Á(ÉB,B)
Vesz(F)
Vesz(T)
Vesz(B)
V(F)
V(T)
V(B)
H(ÉB) V(F) V(T) V(B) H(O)
Cél
Megy(O) H(O) H(ÉB)
Start H(O) Á(SzB,F) Á(ÉB,T) Á(ÉB,B)
H(SzB)
H(O)
Megy(SzB)
Megy(ÉB)
H(SzB) H(O)
H(ÉB) H(SzB)
H(SzB) Á(SzB,F)
H(ÉB) Á(ÉB,T)
H(ÉB) Á(ÉB,B)
Vesz(F)
Vesz(T)
Vesz(B)
V(F)
V(T)
V(B)
H(ÉB) V(F) V(T) V(B) H(O)
Cél
Megy(O) H(O) H(ÉB)
Start H(O) Á(SzB,F) Á(ÉB,T) Á(ÉB,B)
H(SzB)
H(O)
Megy(SzB)
Megy(ÉB)
H(SzB) H(O)
H(ÉB) H(SzB)
H(SzB) Á(SzB,F)
H(ÉB) Á(ÉB,T)
H(ÉB) Á(ÉB,B)
Vesz(F)
Vesz(T)
Vesz(B)
V(F)
V(T)
V(B)
H(ÉB) V(F) V(T) V(B) H(O)
Cél
Megy(O) H(O) H(ÉB)
Start H(O) Á(SzB,F) Á(ÉB,T) Á(ÉB,B)
H(SzB)
H(O)
Megy(SzB)
Megy(ÉB)
H(SzB) H(O)
H(ÉB) H(SzB)
H(SzB) Á(SzB,F)
H(ÉB) Á(ÉB,T)
H(ÉB) Á(ÉB,B)
Vesz(F)
Vesz(T)
Vesz(B)
V(F)
V(T)
V(B)
H(ÉB) V(F) V(T) V(B) H(O)
Cél
Megy(O) H(O) H(ÉB)
Start H(O) Á(SzB,F) Á(ÉB,T) Á(ÉB,B)
H(SzB)
H(O)
Megy(SzB)
Megy(ÉB)
H(SzB) H(O)
H(ÉB) H(SzB)
H(SzB) Á(SzB,F)
H(ÉB) Á(ÉB,T)
H(ÉB) Á(ÉB,B)
Vesz(F)
Vesz(T)
Vesz(B)
V(F)
V(T)
V(B)
H(ÉB) V(F) V(T) V(B) H(O)
Cél
Megy(O) H(O) H(ÉB)
Start Megy(SzB) Aminek sorrendjét meg kellett kötni, az megtörtént.
De aminek sorrendjére a feladatban információ nincs, ez a tervre nincs rákényszerítve.
Vesz(F) Megy(ÉB)
Vesz(T) és egy kérdés, amit Megy(O) egyelőre félreteszünk: tervkészítés közben keresés történik, de valóban milyen algoritmussal? Cél
Vesz(B)
PDDL – Planning Domain Definition Language ADL – Action Description Language, … Domain fogalmak, STRIPS-szerű cselekvések (define (domain …) Problem kezdeti állapot, cél állapot (define (problem ...) (:domain ...) (:objects ...) (:init ...) (:goal ...))
Int. Conf. on Automated Planning and Scheduling (ICAPS) Int. Planning Competition (IPC) LPG http://www.icaps-conference.org/ Local search for Planning Graphs http://zeus.ing.unibs.it/lpg/
Utasítsuk a háztartási robotunkat: Vegyél egy liter tejet, egy kiló banánt és egy szabályozható fordulatszámú akkumulátoros fúrót!" (define (domain fbb) (:requirements :strips) (:predicates (hely ?h) (helyszin ?h) (arusit ?b ?a)(van ?v) (aru ?aa))
(:action megy :parameters (?itt ?ott) :precondition (and (hely ?itt) (hely ?ott) (helyszin ?itt)) :effect (and (helyszin ?ott) (not (helyszin ?itt))) ) (:action vesz :parameters (?b ?a) :precondition (and (helyszin ?b) (aru ?a) (arusit ?b ?a)) :effect (van ?a) ) )
Utasítsuk a háztartási robotunkat: Vegyél egy liter tejet, egy kiló banánt és egy szabályozható fordulatszámú akkumulátoros fúrót!" (define (problem fbb) (:domain fbb) (:objects tej banan furo elelmiszer vasaru otthon) (:init (hely otthon) (hely elelmiszer) (hely vasaru) (helyszin otthon) (arusit elelmiszer banan) (arusit elelmiszer tej) (arusit vasaru furo) (aru tej) (aru banan) (aru furo)) (:goal (and (helyszin otthon) (van tej) (van banan) (van furo)) ) )
Utasítsuk a háztartási robotunkat: Vegyél egy liter tejet, egy kiló banánt és egy szabályozható fordulatszámú akkumulátoros fúrót!" ; Version LPG-td-1.0 ; Command line: lpg-td-1.0 -o fbb-domain.pddl -f fbb-problem.pddl -speed ; Problem fbb-problem.pddl ; Time 0.05 ; Actions having STRIPS duration ; Search time 0.03 ; Time 0.05 ; Parsing time 0.00 ; Search time 0.01 ; Mutex time 0.00 ; Parsing time 0.02 ; Quality 6 ; Mutex time 0.00 ; Quality 6 0: (MEGY OTTHON VASARU) 1: (VESZ VASARU FURO) 0: (MEGY OTTHON ELELMISZER) 2: (MEGY VASARU ELELMISZER) 1: (VESZ ELELMISZER TEJ) 3: (VESZ ELELMISZER BANAN) 1: (VESZ ELELMISZER BANAN) 3: (VESZ ELELMISZER TEJ) 2: (MEGY ELELMISZER VASARU) 4: (MEGY ELELMISZER OTTHON) 3: (VESZ VASARU FURO) 4: (MEGY VASARU OTTHON)
Heurisztika tervkészítéshez: tervkészítési gráfok - Graphplan Lehetséges cselekvések Kezdeti állapot Kiegyenlítés (fixpont)
tervgráf
Kölcsönös kizárások cselekvésekben, állapotokban – mutual exclusion - mutex Cél predikátumok kiegyenlített állapot megoldás nincs Cél predikátumok teljesülnek, és célpredikátumok mutex megoldás lehet A gráfból, mint a keresési térből, ki kell nyerni, ehhez gráf jó heurisztikát ad.
Start
A tervek keresési terének egyfajta tömör kódolása
Cél
… … …
Graphplan Cselekvés mutex-ek Inkonzisztens hatások Követk(Cs1) = Követk(Cs2) Interferencia (védett kapcsolat fenyegetése) Követk(Cs1) = Előfelt(Cs2)
Versenyhelyzet Előfelt(Cs1) = Előfelt(Cs2)
Állítás mutex-ek Ha nincs nem mutex cselekvés, aminek hatása lehetne
Graphplan Op(Cselekvés: Start Előfeltétel: Követk: Van(Süti) Op(Cselekvés: Cél Előfeltétel: Van(Süti) Megevett(Süti)
Op(Cselekvés: Eszik(Süti) Előfeltétel: Van(Süti) Követk: Van(Süti) Megevett(Süti) Op(Cselekvés: Süt(Süti) Előfeltétel: Van(Süti) Követk: Van(Süti)
52
Graphplan Op(Cselekvés: Start Előfeltétel: Követk: Van(Süti) Op(Cselekvés: Cél Előfeltétel: Van(Süti) Megevett(Süti)
Op(Cselekvés: Eszik(Süti) Előfeltétel: Van(Süti) Követk: Van(Süti) Megevett(Süti) Op(Cselekvés: Süt(Süti) Előfeltétel: Van(Süti) Követk: Van(Süti)
megőrző cselekvés zárt világ tényleges cselekvés bővítés mutex
kiegyenlítés (u.a) nem mutex
53
Graphplan Op(Cselekvés: Start Előfeltétel: Követk: Van(Süti) Op(Cselekvés: Cél Előfeltétel: Van(Süti) Megevett(Süti)
Op(Cselekvés: Eszik(Süti) Előfeltétel: Van(Süti) Követk: Van(Süti) Megevett(Süti) Op(Cselekvés: Süt(Süti) Előfeltétel: Van(Süti) Követk: Van(Süti)
Kiegyenlített állapotban igaz a cél és nem mutex = a tervet valahogy ki kell nyerni!
54
Graphplan Op(Cselekvés: Start Előfeltétel: Követk: Van(Süti) Op(Cselekvés: Cél Előfeltétel: Van(Süti) Megevett(Süti)
Op(Cselekvés: Eszik(Süti) Előfeltétel: Van(Süti) Követk: Van(Süti) Megevett(Süti) Op(Cselekvés: Süt(Süti) Előfeltétel: Van(Süti) Követk: Van(Süti) Cél
55
Graphplan Op(Cselekvés: Start Előfeltétel: Követk: Van(Süti) Op(Cselekvés: Cél Előfeltétel: Van(Süti) Megevett(Süti)
Op(Cselekvés: Eszik(Süti) Előfeltétel: Van(Süti) Követk: Van(Süti) Megevett(Süti) Op(Cselekvés: Süt(Süti) Előfeltétel: Van(Süti) Követk: Van(Süti)
56
Graphplan Op(Cselekvés: Start Előfeltétel: Követk: Van(Süti) Op(Cselekvés: Cél Előfeltétel: Van(Süti) Megevett(Süti)
Op(Cselekvés: Eszik(Süti) Előfeltétel: Van(Süti) Követk: Van(Süti) Megevett(Süti) Op(Cselekvés: Süt(Süti) Előfeltétel: Van(Süti) Követk: Van(Süti)
57
Graphplan Op(Cselekvés: Start Előfeltétel: Követk: Van(Süti) Op(Cselekvés: Cél Előfeltétel: Van(Süti) Megevett(Süti)
Op(Cselekvés: Eszik(Süti) Előfeltétel: Van(Süti) Követk: Van(Süti) Megevett(Süti) Op(Cselekvés: Süt(Süti) Előfeltétel: Van(Süti) Követk: Van(Süti)
58
Graphplan Op(Cselekvés: Start Előfeltétel: Követk: Van(Süti) Op(Cselekvés: Cél Előfeltétel: Van(Süti) Megevett(Süti)
Op(Cselekvés: Eszik(Süti) Előfeltétel: Van(Süti) Követk: Van(Süti) Megevett(Süti) Op(Cselekvés: Süt(Süti) Előfeltétel: Van(Süti) Követk: Van(Süti)
59
Graphplan Op(Cselekvés: Start Előfeltétel: Követk: Van(Süti) Op(Cselekvés: Cél Előfeltétel: Van(Süti) Megevett(Süti)
Op(Cselekvés: Eszik(Süti) Előfeltétel: Van(Süti) Követk: Van(Süti) Megevett(Süti) Op(Cselekvés: Süt(Süti) Előfeltétel: Van(Süti) Követk: Van(Süti)
60
Graphplan LPG - Local search for Planning Graphs - tervgráf elkészítése - üres tervből indul (gráf végétől) - terv módosítás lokális kereséssel aktuális részterv „környezetében” - cselekvés beválasztása/kiiktatása (tervgráf alapján, tervgráf bekötéseket figyelembe véve) - heurisztika: szabad előfeltételek és még meglévő mutexek súlyozott összegéből - lokálisan „szimulált lehűtés” jelleg, globális optimum reményében
61
Tervkészítés nem determinisztikus problémakörben Végrehajtás felügyelete Egyszerű tervkészítő ágens a tervet "csukott szemmel" hajtja végre, a soron következő cselekvés kiválasztásánál nem használja föl a megfigyeléseit. Nagyon sérülékeny stratégia! - a terv végrehajtása közben bekövetkező események nyomon követése - az ágens fel tudja fedni, ha valamit elhibáz, ha közben a világ megváltozott - ezután újratervezést hajthat végre, hogy a megváltozott helyzetből az eredeti célt elérje. Monitorozás, „megtorpanás”, P helyett O, javítás megtervezése, javítás végrehajtása, az eredeti terv további végrehajtása
újratervezési stratégiák
62
Érdekes előadások „zh-s” hetekre (nem ZH anyag) XI. 29. kedd, 10.15-12, E1B Bolgár Bence: "Neurális hálók állatkertje"
XII. 6. kedd, 10.15-12, E1B Engedy István: "Mély (deep) megerősítéses tanulás alkalmazásai"
XII. 7. szerda, 10.15-11, Q-I Mészáros Tamás: "Beszélj a robotodhoz!" XII. 7. szerda, 11.15-12, Q-I Pataki Béla: "Tudás és tudatlanság fúziója"