Umělá inteligence I. Roman Barták, KTIML

Umělá inteligence I Roman Barták, KTIML [email protected] http://ktiml.mff.cuni.cz/~bartak

Plánování Klasickou plánovací úlohu tedy můžeme řešit odvozovacími metodami predikátové logiky. Nešlo by to lépe? Reprezentace plánovacího problému množiny

predikátů (místo formulí)

Plánovací algoritmy plánování

odvozovací mechanismy z logiky přizpůsobíme nové reprezentaci dopředné a zpětné plánování

plánování

v prostoru stavů

v prostoru plánů

stavíme plán po kouskách

Umělá inteligence I, Roman Barták

Klasická reprezentace Klasická reprezentace plánovacího problému používá predikátovou logice: Stavy jsou množiny logických atomů, které jsou v dané interpretaci buď pravda nebo nepravda. Akce jsou reprezentovány plánovacími operátory, které mění pravdivostní hodnotu těchto atomů. Přesněji: L (jazyk) je konečná množina predikátových symbolů a konstant (nemáme funkce!). Atom je predikátový symbol s argumenty, např. on(c3,c1). Můžeme používat proměnné, např. on(x,y).


Reprezentace stavů

Stav je množina instanciovaných atomů (bez proměnných). Je jich konečně mnoho!

pravdivostní hodnota některých atomů se mění

některé atomy nemění svojí pravdivostní hodnotu s různými stavy

flexibilní atomy (fluent) např. at(r1,loc2)

neměnné atomy (rigid) např. adjacent(loc1,loc2)

Předpoklad uzavřeného světa (closed world assumption) Atom, který není ve stavu explicitně uveden, neplatí!


Plánovací operátory operátor o je trojice: (name(o), precond(o), effects(o)) name(o):

jméno operátoru ve tvaru n(x1,…,xk)

n: symbol operátoru (jednoznačný pro každý operátor) x1,…,xk: symboly proměnných (parametry operátoru)

musí obsahovat všechny symboly proměnných v operátoru!

precond(o):

literály, které musí být splnitelné, aby šlo operátor použít

effects(o):

předpoklady

efekty

literály, které se stanou pravdivými aplikací operátoru (nesmí to být neměnné atomy!)


Akce Akce jsou plně instanciované operátory – za proměnné jsou dosazeny konstanty

operátor

akce


Aplikace akce Notace: S+ = {pozitivní atomy v S} S– = {atomy, jejichž negace je v S} Akce a je použitelná na stav s právě když precond+(a) ⊆ s & precond–(a) ∩ s = ∅ Výsledkem aplikace akce a na s je γ(s,a) = (s – effects–(a)) ∪ effects+(a)

Implicitně Implicitně řeší řeší problém problém rámce rámce


Plánovací doména Nechť L je jazyk a O je množina operátorů. Plánovací doména Σ nad jazykem L a s operátory O je trojice (S,A,γ): S ⊆ P({všechny instanciované atomy nad L}) akce A = {všechny instanciované operátory z O nad L} stavy

akce a je použitelná na stav s, pokud precond+(a) ⊆ s & precond–(a) ∩ s = ∅

přechodová

funkce γ:

γ(s,a) = (s – effects-(a)) ∪ effects+(a), je-li a použitelná na s S je uzavřená vzhledem ke γ (je-li s∈S, potom pro každou akci a aplikovatelnou na s platí γ(s,a)∈S)


Plánovací problém Plánovací problém P je trojice (Σ,s0,g): Σ=(S,A,γ)

je plánovací doména s0 je počáteční stav, s0∈S g je množina instanciovaných literálů stav s splňuje g právě tehdy, když g+⊆s & g–∩s = ∅ Sg = {s∈S | s splňuje g} - množina cílových stavů

Zápis plánovacího problému je trojice (O,s0,g).


Plány a řešení Plán π je posloupnost akcí 〈a1,a2,…,ak〉. Plán π je řešením P právě když γ(s0,π) splňuje g.

Dopředné ověření existence plánu Přímí následníci stavu s: Γ(s) = {γ(s,a) | a∈A je aplikovatelná na s} Dosažitelné stavy: Γ∞(s) = Γ(s) ∪ Γ2(s) ∪ … Plánovací problém má řešení právě když Sg ∩ Γ∞(s0) ≠ ∅.

Zpětné ověření existence plánu Akce a je relevantní pro cíl g právě když: akce přispívá do g: g∩effects(a) ≠ ∅ efekty akce nejsou v konfliktu s g: g-∩effects+(a) = ∅ ∧ g+∩effects-(a) = ∅

Regresní (zpětná) množina cíle g pro (relevantní) akci a: γ-1(g,a) = (g - effects(a)) ∪ precond(a) Γ-1(g) = {γ-1(g,a) | a∈A je relevantní pro g} Γ∞-1(g) = Γ-1(g) ∪ Γ-2(g) ∪ … Plánovací problém má řešení právě když s0 je nadmnožinou nějakého prvku z Γ∞-1(g).


Ukázka plánu náš cíl g = {loaded(r1,c3), at(r1,loc2)}

s1 =

〈move(r1,loc2,loc1), 〈move(r1,loc2,loc1), take(crane1,loc1,c3,c1,p1), take(crane1,loc1,c3,c1,p1), load(crane1,loc1,c3,r1), load(crane1,loc1,c3,r1), move(r1,loc1,loc2)〉 move(r1,loc1,loc2)〉 〈take(crane1,loc1,c3,c1,p1), 〈take(crane1,loc1,c3,c1,p1), move(r1,loc2,loc1), move(r1,loc2,loc1), load(crane1,loc1,c3,r1), load(crane1,loc1,c3,r1), move(r1,loc1,loc2)〉 move(r1,loc1,loc2)〉


Plánování se stavy

Prohledávaný prostor odpovídá stavovému prostoru plánovacího problému. uzly

odpovídají stavům hrany odpovídají stavovým přechodům pomocí akcí cílem je najít cestu mezi počátečním stavem a některým koncovým stavem

Typy prohledávání dopředné

začínáme v počátečním stavu a jdeme k některému stavu cílovému

zpětné

(forward search, progression)

(backward search, regression)

začínáme s cílem (pozor to není stav, ale reprezentace množiny stavů!) a jdeme přes podcíle k počátečním stavu liftovaná verze (částečné instanciování akcí, tj. použijeme proměnné) Umělá inteligence I, Roman Barták

Dopředné plánování

take c3

take c2 … move r1


Dopředné plánování příklad

{belong(crane1,loc1), adjacent(loc2,loc1), holding(crane1,c3), unloaded(r1), at(r1,loc2), ¬occupied(loc1), …}

Počáteční stav

move(r1,loc2,loc1) {belong(crane1,loc1), adjacent(loc2,loc1), holding(crane1,c3), unloaded(r1), at(r1,loc1), occupied(loc1), ¬occupied(loc2), …}

load(crane1,loc1,c3,r1) {belong(crane1,loc1), adjacent(loc2,loc1), empty(crane1), loaded(r1,c3), at(r1,loc1), occupied(loc1), ¬occupied(loc2), …}

Cíl loc1

Cíl = {at(r1,loc1),loaded(r1,c3)} Umělá inteligence I, Roman Barták

Zpětné plánování

take c3,c1 take c3,c2 move r1


Zpětné plánování Cíl = {at(r1,loc1),loaded(r1,c3)}

příklad

loc1

load(crane1,loc1,c3,r1) {at(r1,loc1), belong(crane1,loc1), holding(crane1,c3), unloaded(r1)} move(r1,loc2,loc1) {belong(crane1,loc1), holding(crane1,c3), unloaded(r1), adjacent(loc2,loc1), at(r1,loc2), ¬ occupied(loc1)}

Počáteční stav


Zpětné plánování-liftování

standardizace = kopie s novými proměnnými mgu = most general unifier (nejobecnější unifikace) použití volných proměnných zmenšuje větvení, ale komplikuje detekci cyklu Umělá inteligence I, Roman Barták

Plánování v prostoru plánů

Princip podobný zpětnému plánování ve stavovém prostoru: začínáme

z „prázdného“ plánu obsahujícího popis počátečního stavu a cíle přidáváme další akce, které plní dosud nesplněné (otevřené) cíle případně přidáváme vazby mezi již přítomnými akcemi

Na plánování se můžeme dívat jako na opravovaní kazů v částečném plánu přecházíme

od jednoho částečného plánu k dalšímu dokud nenajdeme úplný plán Umělá inteligence I, Roman Barták

Plánování v prostoru plánů příklad

Předpokládejme, že v částečném plánu zatím máme akce: take(k1,c1,p1,l1) load(k1,c1,r1,l1)

Možné úpravy plánu:

Přidání akce

Svázání proměnných

akce move se týká správného robota a správného místa

Přidání podmínky uspořádání

aby šlo použít load, musí být robot r1 na místě l1 přesuň robota r1 na místo l1 move(r1,l,l1)

přesunutí robota se musí uskutečnit před load na pořadí vzhledem k take ale nezáleží

Přidání kauzální (příčinné) vazby

nová akce byla přidána, aby se robot dostal tam, kam má kauzální vazba mezi move a load nám zajistí, že mezi těmito akcemi robota někdo zase neodvolá Umělá inteligence I, Roman Barták

Principy PSP

Počáteční stav i cíl zakódujeme jako speciální akce, které jsou v prvotním částečném plánu: Akce

a0 reprezentuje počáteční stav tak, že nemá žádné předpoklady a počáteční stav je zakódován jako efekt. Tato akce je před všemi ostatními akcemi. Akce a∞ reprezentuje cíl, který je zakódován jako předpoklad, efekt akce je prázdný. Tato akce je za všemi ostatními akcemi.

Plánování bude založeno na odstraňování kazů (flaws) částečného plánu. Budeme

přecházet od jednoho částečného plánu k dalšímu, dokud nenajdeme řešící plán. Umělá inteligence I, Roman Barták

Uzly jsou plány Uzly prohledávaného prostoru jsou tvořeny částečnými plány. Částečný plán Π je čtveřice (A,<,B,L), kde A

je množina částečně instanciovaných plánovacích operátorů {a1,…,ak} < je částečné uspořádání na A (ai

Částečný plán: příklad předpoklady předpoklady akce akce

kauzální kauzální vazby vazby

částečné částečné spořádání spořádání

efekty efekty akce akce


Otevřený cíl

Otevřený cíl (open goal) je kazem plánu. Jedná se o předpoklad p nějakého operátoru b, o kterém zatím nebylo rozhodnuto, jak ho splnit (neexistuje kauzální vazba ai→pb). Odstranění otevřeného cíle p akce b: najdi

operátor a (buď již přítomný v plánu nebo nový), který lze použít na splnění p (má p mezi efekty a může být před b) svaž proměnné vytvoř kauzální vazbu


Hrozba

Hrozba (threat) je dalším kazem plánu. Jedná se o akci, která může porušit kauzální vazbu. je-li ai→paj kauzální vazba a akce b má efekt unifikovatelný s negací p a může se nacházet mezi ai a aj , potom je b hrozbou (může porušit platnost kauzální vazby).

Přesněji,

Odstranění hrozby lze udělat třemi způsoby: uspořádáním

b před ai uspořádáním b za aj navázáním proměnných v b tak, že neruší platnost p Umělá inteligence I, Roman Barták

Řešící plán

Částečný plán Π = (A,<,B,L) je řešícím plánem pro problém P = (Σ,s0,g) pokud: částečné

uspořádání < a vazby B jsou globálně konzistentní

v částečném uspořádání nejsou cykly mohu proměnné přiřadit hodnotu z příslušné domény tak, že najdu hodnoty ostatních proměnných splňující B

libovolná

lineárně uspořádaná posloupnost plně instanciovaných akcí A splňující < a vazby B vede z s0 do stavu splňujícího g

Definice nám bohužel přímo nedává výpočtovou proceduru, jak ověřit, zda je plán řešící! Tvrzení: Částečný plán Π = (A,<,B,L) je řešící pokud:

nemá žádné kazy, tj. otevřené cíle ani hrozby částečné uspořádání < a vazby B jsou globálně konzistentní Umělá inteligence I, Roman Barták

Procedura PSP

PSP = Plan-Space Planning (plánování v prostoru plánů)

Volba kazu je deterministická (musí se odstranit všechny kazy). Volba zjemnění je nedeterministická (v případě neúspěchu se zkouší další alternativa).


Detaily PSP

Otevřené cíle lze efektivně zjistit udržováním agendy předpokladů akcí. Přidání kauzální vazby pro p vyřadí p z agendy. Všechny hrozby lze najít prozkoumáním všech trojic akcí (O(n3)) nebo inkrementálně: po přidání akce se zjistí, komu je hrozbou (O(n2)), a po přidání kauzální vazby se ověří její hrozby (O(n)). Pro odstraněné otevřených cílů a hrozeb se používají pouze konzistentní zjemnění plánu. konzistence

uspořádání buď detekcí cyklů nebo lépe udržováním tranzitivního uzávěru konzistence vztahů B

pokud není negace, lze rychle (například pomocí AC) je-li přítomna negace jedná se o NP-úplný problém


Více o plánování

Přednáška Plánování a rozvrhování

http://kti.mff.cuni.cz/~bartak/planovani/


Umělá inteligence I. Roman Barták, KTIML

Recommend Documents