Pl´anov´an´ı • M´ame stavy, oper´atory, poˇca´ tek, c´ıl. • Ot´azka zn´ı, jak pouˇz´ıt oper´atory, abychom dos´ahli stavu, ktery´ je c´ılovy. ´
Uˇz zn´ame: • Prohled´av´an´ı stavov´eho prostoru. • Situaˇcn´ı kalkul - pop´ısˇ i svˇet v logice a pouˇziji rezoluˇcn´ı metody, aˇt za mˇe prohled´av´a.
Situaˇcn´ı kalkul • Fakta plat´ı v situac´ıch napˇr. holding( gold, now) • Situace jsou propojeny predik´atem result( a, s), ktery´ definuje vysledek akce a v ´ situaci s. ˇ Sikovn y, ´ ale potˇrebujeme pˇr´ıliˇs mnoho axiomu˚ pro reprezentaci r´amce, proto se pod´ıv´ame na specializovan´e metody
STRIPS, Shakey Vlastnosti
Akce
At(Shakey,x), In(x,r) & In(y,r) & On(Shakey, Floor)
Go(y)
Pushable(b),At(Shakey,x), In(x,r) & In(y,r)
Push(b,x,y)
Climbable(b), At(Shakey,x) &At(b,x)
Climb(b) Down(b) TurnOn(ls) TurnOff(ls)
STRIPS ve svˇetˇe kostek Akce: • UNSTACK(A,B) • STACK(A,B) • PICKUP(A) - ze stolu ˚ • PUTDOWN(A) - na stul Popis prostˇred´ı: • ON(A,B) • ONTABLE(A) • CLEAR(A) • HOLDING(A) • ARMEMPTY
STRIPS - pokraˇc. Axiomy:
(∃ x : HOLDING ( x)) ←→ ¬ ARMEMPTY ∀ x : (ONTABLE( x) ←→ ¬∃ y : ON ( x, y)) ∀ x : (¬∃ y : ON ( y, x)) ←→ CLEAR( x)) Plny´ popis akc´ı akce
PRECONDITIONS
DELETE
ADD
UNSTACK(x,y)
ON(x,y) & CLEAR(x) & ARMEMPTY
ON(x,y) & ARMEMPTY
HOLDING(x) & CLEAR(y)
STACK(x,y)
CLEAR(y) & HOLDING(x)
CLEAR(y) & HOLDING(x)
ARMEMPTY & ON(x,y)
PICKUP(x)
CLEAR(x) & ONTABLE(x) & ARMEMPTY
ONTABLE(x) & ARMEMPTY
HOLDING(x)
PUTDOWN(x)
HOLDING(x)
HOLDING(x)
ONTABLE(x) & ARMEMPTY
Pl´anovaˇc Pl´anovaˇc obsahuje: • z´asobn´ık c´ılu, ˚ na kter´em jsou c´ıle i oper´atory navrˇzen´e pro splnˇen´ı tˇechto c´ılu˚ • datab´azi popisuj´ıc´ı souˇcasnou situaci • mnoˇzinu oper´atoru˚ • (axiomy popisuj´ıc´ı prostˇred´ı pro odvozen´ı vlastnost´ı, kter´e nejsou rˇ eˇceny explicitnˇe) Pozn: jedn´a se vlastnˇe o zpˇetn´e prohled´av´an´ı do hloubky, kde m´ame zjednoduˇseny´ vypoˇ ´ cet r´amce n´asleduj´ıc´ıho stavu ve situaˇcn´ım kalkulu.
Algoritmus STRIPS push(GOAL,STACK) while not empty(STACK) G←pop(STACK) if G = akce then PERFORM(C) elseif G = conjunction then if G is not true in the current database push(G,STACK) foreach L literal of G that is not true in the current database push(L,STACK) endif else /* G is a subgoal*/ if G not true in current database then choose an action S with G as its effect push(G,STACK)
push(PRECONDITIONS(G),STACK) /* testuj slep´e cesty a backtrack*/ endif endwhile
Sloˇzky pl´anovac´ıho syst´emu ˚ 1. vybrat nejvhodnˇejˇs´ı pravidlo (analyza ´ prostˇredku˚ a c´ılu) ´ 2. aplikovat vybran´e pravidlo a vypoˇc´ıst novy´ stav ulohy 3. zjistit, zda bylo nalezeno rˇ eˇsen´ı 4. naj´ıt slep´e cesty 5. detekovat skoro spr´avn´e rˇ eˇsen´ı (a aplikovat opravn´e techniky)
Neline´arn´ı pl´anov´an´ı Pl´anov´an´ı jakoˇzto prohled´av´an´ı prostoru pl´anu˚
POP (partially ordered plan) ˇ asteˇcnˇe uspoˇra´ dany´ pl´an sest´av´a z: C´ • Kroku˚ pl´anu (STEPS). Kaˇzdy´ krok je jedna instance oper´atoru. • Podm´ınky na uspoˇra´ d´an´ı (ORDERINGS). Kaˇzd´a podm´ınka rˇ´ık´a, zˇ e jeden krok mus´ı pˇredch´azet jin´emu kroku, zapisujeme Si ≺ S j . • Dosazen´ı za jednotliv´e promˇenn´e. Kaˇzd´e pˇriˇrazen´ı je typu v = x, kde v je promˇenn´a v nˇekter´em kroku a x je budˇ konstanta, nebo jin´a promˇenn´a.
→ • Mnoˇzinu kauz´aln´ıch hran Si − c S j s vyznamem Si spln´ı c pro S j . ´ ˚ Kauz´aln´ı harny slouˇz´ı k pamatov´an´ı duvodu kroku˚ v pl´anu – ˚ duvod pˇr´ıtomnosti Si v pl´anu je splnˇen´ı pˇredpokladu c pro S j .a a Obˇ cas
se nazyvaj´ ´ ı protection intervals.
Obr´azek: minim´aln´ı pl´an, ponoˇzky a boty, linearizace pl´anu ˇ sen´ım ulohy ´ Reˇ pl´anov´an´ı je naj´ıt takovy´ pl´an, ktery´ garantuje ´ splnˇen´ı c´ıle. Pl´an nech´av´ame v podobnˇe neuplnˇ e uspoˇra´ dan´e a instancializovan´e, aby mˇel prov´adˇec´ı agent v´ıce volnosti, napˇr. pro paralelismus cˇ i kombinaci s dalˇs´ımi pl´any. ˇ sen´ım je upln ´ Reˇ ´ y´ a konzistentn´ı pl´an. Upln y´ pl´an je takovy, ´ zˇ e kaˇzdy´ pˇredpoklad kaˇzd´eho kroku je splnˇene nˇejakym ´ dalˇs´ım ˇ krokem. Krok splnuje podm´ınku pokud je podm´ınka jedn´ım z jeho ˚ ze zruˇsit platnost t´eto podm´ınky. efektu˚ a zˇ a´ dny´ dalˇs´ı krok nemuˇ
Form´alnˇe, krok Si pln´ı podm´ınu c kroku S j pokud • Si ≺ S j a c ∈ EFFECTS( Si ) • neexistuje krok Sk takovy, ´ zˇ e ¬c ∈ EFFECTS( Sk ) a Si ≺ Sk ≺ S j je konzistentn´ı linearizace pl´anu. Konzistentn´ı pl´an je pl´an bez sporu v uspoˇra´ d´an´ı a pˇriˇrazen´ı promˇennych. ´ Pˇr´ıklad: koupit ml´eko, ban´any a vrtaˇcku, oper´atory: Go pro pˇresun, Buy pro koupi. HWS je HW obchod, SM je supermarket, At je predik´at na pamatov´an´ı si pozice, Sells reprezentuje znalost, kde se co prod´av´a. Theorem 1 (Korektnost a uplnost ´ POP) Algoritmus POP je korektn´ı a upln´ ´ y, pokud pouˇz´ıv´ame prohled´av´an´ı do sˇ´ırˇky cˇ i iterativnˇe prohlubuj´ıc´ı se prohled´av´an´ı v bodech volby choose.
Algoritmus POP (z´akladn´ı) function POP(initial, goals, operators) returns plan plan=MAKE–MINIMAL–PLAN(initial, goals) loop do Termination: if there are no insatisfied preconditions then return plan Subgoal selection: find a plan step Sneed with an open precondition c Action selection: choose a step S add from operators or STEPS(plan) that has c as an effect if there is no such step then fail add the causal link S add
c
Sneed to LINKS(plan)
−→ add the ordering constraint S add ≺ Sneed to ORDERINGS(plan) if S add is a newly added step from operators then add S add to STEPS(plan)
add Start ≺ S add ≺ Finish to ORDERINGS(plan) Therat resolution: for each Sthreat that threatens a link Si
c
−→
S j in LINKS(plan) do
choose either Promotion: Add Sthreat ≺ Si to ORDERINGS(plan) Demotion:Add Sthreat S j to ORDERINGS(plan) if not CONSISTENT(plan) then fail endloop
Modifikace pro promˇenn´e Algoritmus CHOOSE–OPERATOR s unifikac´ı procedure CHOOSE–OPERATOR(plan, operators, Sneed ,c ) choose a step S add from operators or STEPS(plan) that has c add as an effect such that u = UN IFY (c, c add , BINDINGS( plan)) if there is no such step then fail add u to BI NDINGS( plan)) add S add .. .
c
−→
Sneed to LINKS(plan)
Algoritmus RESOLVE THREATS –resolve later verze .. . c|
is an effect of Sthreat that threatens c in the link Si
c
Sj
−→ if SUBST ( BINDINGS( plan), c) = SUBST ( BINDI NGS( plan), ¬c| ) then choose either Promotion: Add Sthreat ≺ Si to ORDERINGS(plan) Demotion:Add Sthreat S j to ORDERINGS(plan) if not CONSISTENT(plan) then fail .. .
V praxi pouˇzit´e pl´anovaˇce O–Plan (Currie and Tate, 1991) – otevˇren´a pl´anovac´ı architektura podobn´a POP. Na n´ı zaloˇzen OPTIMUM–AVI a pl´anov´an´ı v Hitachi tov´arnˇe. OPTIMUM–AVI byl pouˇz´ıvany´ European Space Agency na podporu mont´azˇ e, integrace a verifikace vesm´ırnych ´ lod´ı. Byl pouˇz´ıv´an pro tvorbu pl´anu i monitoring. Schopnost rychl´eho pˇrepl´anov´an´ı se uk´azala b´yt kl´ıcˇ ov´a. Spoleˇcnˇe s pl´anov´an´ım se cˇ asto pouˇz´ıvaj´ı n´astroje na job–sheduling, jako napˇr. PERT grafy cˇ i critical path method. Tyto pl´any ale neobsahuj´ı kauz´aln´ı vazby mezi akcemi a proto nejsou schopny zmˇenit pl´an a lidsk´e pˇrepl´anov´an´ı je cˇ asto velmi pomal´e.
Hubble space telescope ˚ teleskop je dobry´ pˇr´ıklad nutnosti automatick´eho Hubbluv pl´anov´an´ı. ˚ ze navrhnout pozorov´an´ı. Ta se pak oznaˇc´ı jako Kaˇzdy´ astronom muˇ high priority (ty zaberou cca. 70% cˇ asu), low priority (moˇzn´a se provedou, moˇzn´a ne), a zam´ıtnut´a. Kaˇzdy´ n´avrh obsahuje strojovˇe cˇ itelnou specifikaci, co m´a byt ´ nasmˇerov´ano na kter´e m´ısto nebo a jaky´ typ expozice m´a byt ´ proveden. Nˇekter´a pozorov´an´ı mohou byt ´ provedena vˇzdy, nˇekter´a jen, je–li druˇzice v zemsk´em st´ınu, nˇekter´a periodicky s t´ım, zˇ e vˇsechna maj´ı byt ´ ve stejn´em zast´ınˇen´ı.
SIPE SIPE – pracoval se stavy, ne logickym ´ popisem. Pro n´avrh stavby mnohapatrov´e budovy. Pracoval pˇr´ıliˇs dlouho, O(n2.5 ) kde n je poˇcet pater. Rozumnˇe by mˇel byt ´ mnohem bl´ızˇ e O(n), protoˇze skoro vˇse staˇc´ı pl´anovat pro jednotliv´a patra samostatnˇe.
Pro re´aln´e aplikace pl´anovaˇc potˇrebuje: 1. hierarchick´e pl´any 2. komplexnˇejˇs´ı podm´ınky, univerz´aln´ı kvantifikaci ”Start vynese ˇ VSECHNY vˇeci na orbitu”. Podobnˇe je tˇreba podm´ınˇen´e oper´atory ”jde–li vˇse dobˇre, start vynese vˇse na orbitu, jinak to hod´ı do moˇre”. 3. cˇ as – vˇeci mus´ı byt ´ hotov´e v dany´ cˇ as, akce maj´ı dobu trv´an´ı, nˇekter´e stroje jsou dosaˇziteln´e jen v urˇcitou dobu atd. ˚ poˇcet d´ılen a testovac´ıch 4. zdroje = finance, poˇcet zamˇestnancu, stanic.
Hierarchick´a dekompozice Ve sloˇzitˇejˇs´ıch probl´emech pl´anov´an´ı se neobejdeme bez hierarchick´e dekompozice. Ta n´am umoˇzn´ı pˇrev´adˇet pl´any na vyˇssˇ´ı hladinˇe abstrakce na pl´any konkr´etnˇejˇs´ı. Abstraktn´ı pl´an je napˇr. [ Go( Supermarket), Buy( Milk), Buy( Bananas), Go( Home)], ´ ˚ ze vypadat: pl´an na nejniˇzsˇ´ı urovni muˇ [ Forward(1cm), Turn(1deg), Forward(1cm), . . .] ´ Pˇr´ımym abstrakce bychom ´ hled´an´ım pl´anu na nejniˇzsˇ´ı urovni pravdˇepodobnˇe nedospˇeli k rˇ eˇsen´ı, protoˇze bychom museli ˚ ze obsahovat prohled´avat pˇr´ıliˇs mnoho moˇznost´ı – tento pl´an muˇ ˚ tis´ıce kroku. Pˇri hierarchick´e dekompozici zavedeme abstraktn´ı oper´atory a pro kaˇzdy´ abstraktn´ı oper´ator jednu cˇ i v´ıce dekompozic, tj. skupin kroku˚ kter´e implementuj´ı pl´an pro dany´ oper´ator. Kromˇe abstraktn´ıch oper´atoru˚ m´ame oper´atory primitivn´ı.
´ Pl´an je upln y´ pokud je kaˇzdy´ jeho krok primitivn´ı oper´ator, takˇze ˚ ze byt muˇ ´ pˇr´ımo proveden agentem. Dekompozice m´a vˇetˇs´ı efekt, pokud je pro abstraktn´ı akce v´ıce ´ moˇznych ´ dekompozic´ı – v´ıc prohled´av´an´ı se udˇel´a na vyˇssˇ´ı urovni. Napˇr´ıklad ”Postav zdi” lze prov´est ze dˇreva, cihel, betonu cˇ i nˇejak´eho sandwitche. Pˇr. sˇ patn´e dekompozice – dev´ıtka. My nyn´ı: • rozˇs´ırˇ´ıme jazyk o abstraktn´ı oper´atory a jejich dekompozice • rozˇs´ırˇ´ıme POP algoritmus o dekompozici abstraktn´ıch oper´atoru˚
Oper´ator Decompose(o,p) rozloˇz´ı oper´ator o na pl´an p, napˇr´ıklad: Decompose(Construction, Plan( STEPS:{S1 :Build(Foundation),S2 :Build(Frame), S3 :Build(Roof), S4 :Build(Walls), S5 :Build(Interior)} ORDERINGS:{ S1 S2 ≺ S3 ≺ S5 , S2 ≺ S4 ≺ S5 } BINDINBS:{} LINKS: −−−−−−−→ −−→ −−−→ −−−→ −−−→ { S1 FoundationsS2 , S2 FrameS3 , S2 FrameS4 , S3 Roo f S5 , S4 WallsS5 }))
Potˇrebujeme rozumnˇe definovan´e rozklady, proto n´asleduj´ıc´ı definice. ´ Pl´an p korektnˇe implementuje oper´ator o (tj. je upln y´ a konzistentn´ı pl´an pro dos´ahnut´ı efektu˚ o za pˇredpokladu splnˇenych ´ PRECONDITIONS o) pokud: 1. p je konzistentn´ı (tj. bez kontradikce v ORDERINGS i BINDINGS promˇennych) ´ 2. Kaˇzdy´ efekt o je plnˇen asponˇ jedn´ım krokem p takovym, ´ zˇ e nen´ı n´aslednˇe zruˇsen dalˇs´ım krokem z p. 3. Kaˇzdy´ pˇredpoklad kaˇzd´eho kroku v p mus´ı byt ´ dosaˇzen nˇekterym ´ krokem v p nebo byt ´ obsaˇzen v pˇredpokladech o.
Pokud se n´am povede takto definovat oper´atory dekompozice, tak se pˇri proveden´ı dekompozice nemus´ıme starat o vnitˇrn´ı konzistenci pl´anu p. Mus´ıme ale ovˇerˇ it konzistenci pl´anu p s ostatn´ımi cˇ a´ stmi ˚ zou nastat konflikty. pl´anu, protoˇze tady muˇ Pl´anovaˇc staˇc´ı m´ırnˇe modifikovat – napˇr. ke kaˇzd´emu vybˇ ´ eru kroku a c´ıle k hled´an´ı oper´atoru pˇridat dalˇs´ı krok, ktery´ vybere abstraktn´ı oper´ator a metodu dekompozice, kterou na nˇem provede.
Pˇri dekompozici se mˇen´ı celkovy´ pl´an n´asledovnˇe: • STEPS: odstran´ıme Snonprim , pˇrid´ame vˇsechny kroky pl´anu p. • BINDINGS: Pˇrid´ame vˇsechna pˇriˇrazen´ı z pl´anu p. Pokud dojde ke sporu, selˇzeme a vynut´ıme backtracking. • ORDERINGS: opˇet se chov´ame podle ”least commintment principle”. Nahrad´ıme – vˇsechny S a ≺ Snonprim podm´ınkami S a ≺ Slast , kde Slast reprezentuje posledn´ı akci v p – vˇsechny Snonprim ≺ S a podm´ınkami S f irst ≺ S a , kde S f irst reprezentuje prvn´ı akce v p. Pak mus´ıme zavolat RESOLVE–THREATS pro kontrolu dalˇs´ıch ˚ moˇznych ´ konfliktu. • LINKS:
→ → – Si − c Snonprim nahrad´ıme mnoˇzinou hran Si − c Sm , kde Sm je ˚ krok pl´anu p s c v pˇredpokladech, ktery´ nem´a pˇrechudce vp s c v pˇredpokladech. Pokud takovy´ Sm nen´ı, vazba byla ˚ zeme j´ı zapomenout. zbyteˇcn´a a muˇ − → → – Podobnˇe S c S nahrad´ıme mnoˇzinou hran S − c S, nonprim
j
m
j
kde Sm je krok pl´anu p s efektem c, ktery´ nem´a n´asledn´ıka v p ´ s efektem c. Takovy´ krok byt a. ´ mus´ı, je–li dekompozice upln´ Pˇr´ıklad.
Analyza ´ hierarchick´e dekompozice Dekompozice vypad´a jako dobry´ n´apad. Jestli – a kolik – opravdu uˇsetˇr´ı pr´ace, to se snaˇz´ı osvˇetlit n´asleduj´ıc´ı rozbor. Naj´ıt abstraktn´ı rˇ eˇsen´ı by nemˇelo byt ´ pˇr´ıliˇs sloˇzit´e. Jde sp´ısˇ o to, aby to bylo uˇziteˇcn´e, tedy abychom zam´ıt´an´ım nekonzistentn´ıch abstraktn´ıch rˇ eˇsen´ı dˇelali nˇeco uˇziteˇcn´eho – tj. zam´ıtali ´ nekonzistentn´ı upln´ a rˇ eˇsen´ı a nezam´ıtali rˇ eˇsen´ı konzistentn´ı. ˇ Proto bychom r´adi, aby dekompozice splnovala: • upward solution property – aby kaˇzd´a abstrakce konzistentn´ıho rˇ eˇsen´ı byla konzistentn´ı, tj. pokud najdeme nekonzistentn´ı ˚ zeme ho zam´ıtnout, abstraktn´ı rˇ eˇsen´ı, muˇ • downward solution property – aby kaˇzdy´ konzistentn´ı abstraktn´ı ´ pl´an byl abstrakc´ı nˇejak´eho upln´ eho konzistentn´ıho rˇ eˇsen´ı (obsahuj´ıc´ıho pouze primitivn´ı akce). Pak by n´am staˇcilo
n´asledovat konzistentn´ı abstraktn´ı rˇ eˇsen´ı a backtrackovat jen na nejniˇzsˇ´ı – tj. nejm´enˇe abstraktn´ı – hladinˇe.
Redukce poˇctu ”choose” bodu˚ Pˇredpokl´adejme, zˇ e existuje asponˇ jedno rˇ eˇsen´ı o n z´akladn´ıch kroc´ıch a zˇ e cˇ as na RESOLVE THREATS a pr´aci s podm´ınkami je zanedbatelny´ vzhledem k cˇ asu na zpracov´an´ı kroku pl´anovaˇce. Nechˇt b je faktor vˇetven´ı (branching faktor) dekompozice, kaˇzd´a ´ dekompozice obsahuje s kroku˚ pl´anu a poˇcet hierarchickych ı ´ urovn´ je d. Nehierarchick´e pl´anov´an´ı potˇrebuje v nejhorˇs´ım pˇr´ıpadˇe cˇ as O(bn ). Pro dekompozici s upward i downward solution property potˇrebujeme proj´ıt maxim´alnˇe d
∑ bsi = O(bsd )
i =1
´ kroku˚ (na pˇredposledn´ı urovni pro kaˇzdy´ STEP d moˇznost´ı jak ´ rozloˇzit, kr´at poˇcet urovn´ ı). Pro parametry b = d = 3, s = 4, n = sd = 64 dostaneme 3 × 1030
nehierarchicky versus 576 kroku˚ hierarchicky. Pokud neplat´ı upward a downward solution property a nem´ame za nˇe rozumnou n´ahradu, pak n´am hierarchick´e rˇ eˇsen´ı zrychlen´ı ˚ ern´em chov´an´ı muˇ ˚ ze pˇrin´est). negarantuje (i kdyˇz v prumˇ
Sd´ılen´ı akc´ı v dekompozici v dekompozici se pro kaˇzdy´ oper´ator v p nedeterminitsticky rozhodneme, jestli pro nˇej vyuˇzijeme nˇektery´ z kroku˚ planu nebo pro nˇej vytvoˇr´ıme novou instanci. Vˇetˇsinou je uˇziteˇcn´a heuristika ˚ pokud to lze. preferovat sd´ılen´ı kroku, Mnoh´e hierarchick´e pl´anovaˇce pouˇz´ıvaj´ı dekompozici bez sd´ılen´ı a n´aslednˇe modifikuj´ı vysledn y´ pl´an. Kritika (critics) je funkce, kter´a ´ bere na vstupu pl´an a vr´at´ı pl´an s opravenymi konflikty nebo–a ´ dalˇs´ımi anom´aliemi. Pˇr´ıklad: kompil´atory na sin( x) + cos( x) se chovaj´ı jako kritiky, tj. nesd´ılej´ı akce, protoˇze by analyza ´ moˇzn´eho sd´ılen´ı trvala pˇr´ıliˇs dlouho.
Dekompozice versus aproximace ˚ zeme hledat pl´an pomoc´ı M´ısto (pˇresn´e a korektn´ı) dekompozice muˇ ˇ an´ı aproximace. postupn´eho zjemnov´ ˚ zitosti Kaˇzd´emu pˇredpokladu akce pˇriˇrad´ıme hladinu duleˇ (criticality level), napˇr. pro akci Buy(x) srovn´ame pˇredpoklady od ˚ zitˇejˇs´ıho: nejduleˇ 1. Sells(store,x) 2. At(store) 3. Have(Money) ˚ zitosti 1. Pak nejdˇr´ıv rˇ eˇs´ıme probl´em jen s pˇredpoklady akc´ı duleˇ ˇ sen´ı nakoup´ı spr´avn´e vˇeci ve spr´avnych Reˇ ´ obchodech, ale nebude se starat o to, jak proch´azet mezi obchody a jak platit za zboˇz´ı. Aˇz najdeme rˇ eˇsen´ı na prvn´ı hladinˇe, rozˇs´ırˇ´ıme ho o hladinu druhou,
´ a tak d´ale, dokud nenajdeme upln y´ a konzistentn´ı pl´an. ˚ ˚ zeme reprezentovat i v Tento zpusob aproximativn´ıho pl´anov´an´ı muˇ HD–POP tak, zˇ e definujeme akci Buy1 pouze z kritickymi ´ pˇredpoklady, pro tuto akci definujeme dekompozici na Buy2 s rozˇs´ırˇ enymi pˇredpoklady. Pak uˇz zbyv´ ´ ´ a jen upravit poˇrad´ı prohled´av´an´ı – nejdˇr´ıve vyrobit cely´ pl´an bez dekompozic, pak ´ echu nejprve backtrackovat teprve prov´est dekompozice. Pˇri neuspˇ na hladinˇe nejm´enˇe kritickych ´ premis. V t´eto dekompozici plat´ı upward solution property, protoˇze akce s vyˇssˇ´ımi cˇ ´ısly hladin vˇzdy zdˇed´ı vˇsechny premisy akc´ı pˇredchoz´ıch, tj. m´ame–li rˇ eˇsen´ı na hladinˇe s vysokym ´ cˇ ´ıslem, m´ame rˇ eˇsen´ı i na hladin´ach s niˇzsˇ´ımi cˇ ´ısly. ˚ zitosti pˇredpokladu˚ by se dalo d´ale zjemnit t´ım, Toto pˇriˇrazen´ı duleˇ ˚ zitosti mˇenit podle kontextu – napˇr. zˇ e bychom dovolili hladinu duleˇ pen´ıze se stanou daleko v´ıce kritick´e pˇri koupi domu (ve srovn´an´ı s
koup´ı ml´eka).
Rozˇsı´rˇen´ı jazyka akc´ı • Podm´ınˇen´e efekty • Negovan´e a disjunktivn´ı c´ıle • Univerz´aln´ı kvantifikace • Fluents (ˇcas, pen´ıze – spec. promˇenn´e)
Podm´ınˇen´e efekty Uˇz ve svˇetˇe kostek jsme narazili na probl´em, zˇ e po poloˇzen´ı kostky A na kostku B kostka B pˇrestane byt ´ voln´a, ale po poloˇzen´ı kostky A ˇ sen´ı pomoc´ı dvou ruzn ˚ na stole stejnˇe zbyde m´ısto. Reˇ ˚ ych na stul ´ akc´ı a predik´atu˚ je krkolomn´e a neefektivn´ı, lepˇs´ı je rozliˇsit efekt ˚ akce podle toho, jestli kostku pokl´ad´ame na jinou kostku cˇ i na stul. akce
PRECONDITIONS
STACK(x,y)
CLEAR(y) & HOLDING(x)
DELETE
(CLEAR(y) when y 6= Table) & HOLDING(
M´ame–li podm´ınˇeny´ efekt, tak podm´ınku tohoto efektu vyb´ır´ame za c´ıl pouze v pˇr´ıpadˇe, zˇ e efekt potˇrebuje nˇejak´a kauz´aln´ı hrana. Tak´e mus´ıme odstranit potenci´aln´ı hrozby. Jedna z moˇznost´ı je tzv. → konfrontace – pokud hranu Si − c S j ohroˇzuje podm´ınˇeny´ efekt (¬c when p), tak zajist´ıme, aby p nebylo splnˇeno – napˇr. dosazen´ım
y = Table ve vyˇ ´ se uveden´em pˇr´ıkladu.
Negovan´e a disjunktivn´ı c´ıle Konfrontace vyˇ ´ se n´am zavedla negovany´ c´ıl ¬ p. To n´am ale nezvyˇsuje sloˇzitost – opˇet jen projdeme efekty akc´ı a vybereme ty, kter´e c´ıl obsahuj´ı. Jen mus´ıme d´at pozor, aby unifikace spojila p a ¬¬ p. Tak´e mus´ıme zav´est speci´aln´ı pravidlo pro poˇca´ teˇcn´ı stav, kde negativn´ı vlastnosti nespecifikujeme pˇr´ımo, ale pˇredpokl´ad´ame, zˇ e plat´ı negace vˇseho, co nen´ı rˇ eˇceno pozitivnˇe. ˚ zeme pˇridat disjunktivn´ı pˇredpoklady – prostˇe Jeˇstˇe snadnˇeji muˇ nedeterministicky vybereme jeden jako podc´ıl, aˇz pˇrijde cˇ as. Horˇs´ı je to s disjunktivn´ımi efekty, protoˇze n´am mˇen´ı deterministick´e prostˇred´ı na nedeterministick´e.
Univerz´aln´ı kvantifikace Ve svˇetˇe kostek jsme museli zav´est predik´at Clear( B). Lepˇs´ı by bylo napsat pˇr´ımo do pˇredpokladu˚ oper´atoru definici predik´atu Clear( B), tj. ∀ x( Block( x) → ¬On( x, b)). To n´am dovol´ı nejen zruˇsit udrˇzov´an´ı predik´atu Clear( B), ale tak´e pl´anov´an´ı ve sloˇzitˇejˇs´ıch svˇetech, napˇr. ˚ ych kostkami ruzn ´ velikost´ı. ˚ zeme zav´est univerz´aln´ı kvantifik´ator do efektu. ˚ Podobnˇe muˇ Napˇr´ıklad pˇrenesen´ım batohu pˇreneseme i vˇsechny pˇredmˇety uvnitˇr batohu, tj. efekt Carry(Bag, x,y) je ∀i( Item(i) → (¬ At(i, x)&At(i, y)whenIn(i, bag))). I kdyˇz to vypad´a jako univerz´aln´ı kvantifikace, udrˇz´ıme svˇet omezeny´ t´ım, zˇ e na zaˇca´ tku budou dan´e typy vˇec´ı a budeme zn´at vˇsechny pˇredmˇety dan´eho typu. T´ım pak budeme moci nahradit univerz´aln´ı kvantifikaci vyˇ ´ ctem vˇsech prvku˚ dan´eho typu. Nen´ı to
pˇr´ıliˇs efektivn´ı, ale nen´ı obecn´e lepˇs´ı rˇ eˇsen´ı. Univerz´alnˇe kvantifikovan´e efekty nemus´ıme expandovat, protoˇze n´am na vˇetˇsinˇe efektu˚ nez´aleˇz´ı – mus´ıme jen zajistit, aby si jich vˇsiml RESOLVE–THREATS jako moˇznych ´ hrozeb a CHOOSE–OPERATOR ˚ kauz´aln´ıch hran. jako moˇznych ´ ”ocasu” Pozn: moˇznost nahradit detailn´ıho typu predik´aty (Actual(House1)), v pˇr´ıpadˇe velk´eho poˇctu nerozliˇsitelnych ´ objektu˚ je br´at jako zdroje – resources – napˇr. pen´ıze, cˇ as, lidsk´e s´ıly. Pozn: Russel–Norvig – POP–DUNC – algoritmus, kde je vˇse dohromady.
Omezen´ı na zdroje jako cˇ as a lid´e • Fluents – pˇredem definovan´e promˇenn´e, specieln´ı zach´azen´ı • Hruby´ odhad – doln´ı a horn´ı hranice, odhad ceny za jednotku atd. • v pˇredpokladech testy na nerovnosti s fluents • v efektech aritmeticky´ vypoˇ ´ cet nov´e hodnoty fluent ze star´e hodnoty fluent Je ot´azkou, nakolik ovˇerˇ ovat konzistenci – vˇetˇsinou se hl´ıd´a jen na hrubo, zˇ e akce samostatnˇe potˇrebuje jen zdroje, kter´e jsou ˇ by i rˇ eˇsit constraint satisfaction problem, ale to by dosaˇziteln´e. Slo mohlo trvat moc dlouho na to, jak cˇ asto to potˇrebujeme dˇelat. ˇ je skoro jako jin´e fluent, ale Cas ˚ zeme • nelze poslat pozp´atku (i kdyˇz tˇreba n´adrˇz benz´ınu muˇ
doplnit). • Nav´ıc cˇ as mus´ı korespondovat s uspoˇra´ d´an´ım ≺.
