Parte 2: Pianificazione

(1)

Console, Botta - Dip. Informatica, Univ. Torino Planning 1

Planning

• Importante attività di problem solving

– dati

• una descrizione (parziale) dello stato corrente (eventualmente percepita)

• un insieme di azioni • un obiettivo da raggiungere – determinare:

• un piano, ossia un insieme (parzialmente o totalmente) ordinato di azioni per raggiungere il goal

• un task di per se

• e attività comune a molti task, ad esempio

– diagnosi: pianficazione di test o di azioni per riparare (riconfigurare) un sistema

– scheduling – robotica

• Planning = costruzione di un piano

– rappresentazione dello stato – rappresentazione delle azioni – strategie di ricerca

• Molto differente da problem solving nello spazio degli stati

– stato parziale – azioni complesse

– piano è un insieme (parzialmente) ordinato di azioni

• Vedremo

– tecniche di base di planning

• algoritmo STRIPS

– costruzione di piani parzialmente ordinati e least commitment planning – planning gerarchico

– planning condizionale – planning and acting

(2)

Situation calculus: una soluzione deduttiva

• Situation calculus: un approccio logico per la rappresentazione di stati,

azioni e cambiamento

• Situation: snapshot del mondo e delle proprietà (fluent) che valgono in

quell’istante

– Esempio: mondo dei blocchi holds(on(b,a), s)

holds(ontable(c), s)

• Azioni: definiscono quali fluent saranno veri come risultato di un’azione

– Esempio

holds(on(X,Y),S) and holds(clear(X),S) →

holds((ontable(X), ¬on(X,Y)), result(putOnTable(X,S)))

• Costruzione di un piano: deduzione, dimostrazione di un goal

– Esempio: ? holds(ontable(b),S) YES per S=putOnTable(b,s)

• Problemi: qualification e frame problem

– necessità di forme di logiche non standard a b

c

Rappresentazione di stati e azioni

• Problemi degli approcci deduttivi

• rappresentazioni in linguaggi specializzati e tecniche non deduttive di

pianificazione

• STRIPS (Stanford Research Institute Problem Solver)

– antenato dei sistemi attuali di pianificazione – linguaggio per la rappresentazione di azioni – algoritmo per la costruzione di piani

• Rappresentazione dello stato:

– Insieme di fluent che valgono nello stato – Esempio: on(b,a), clear(b), clear(c), ontable(c)

• rappresentazione del goal

– Insieme di fluent (simile allo stato) – Si possono avere variabili

(3)

• Rappresentazione delle azioni

Tre parti:

– Precondizioni: fluent che devono essere veri per applicare l’azione – DELETE List: fluent che diventano falsi come risultato dell’azione – ADD List: fluent che diventano veri come risultato dell’azione

Esempio

– move(X, Y, Z) (sposta X da sopra a Y a sopra a Z)

• Precondizioni: on(X,Y), clear(X), clear(Z) • Delete List: clear(Z), on(X,Y)

• Add list: clear(Y), on(X,Z)

• Oss: a volte add e delete list rappresentate come EFFECT list con

atomi positivi e negativi

Esempio

• Precondizioni: on(X,Y), clear(X), clear(Z) • Effect List: ¬clear(Z), ¬ on(X,Y), clear(Y), on(X,Z)

Backward (regression) planning

• Ricerca nello spazio delle situazioni

• Ricerca backward a partire dal goal

• Operatori come regole

– riduzione di un goal a sottogoal

– terminazione: sottogoal che è un sottoinsieme dello stato iniziale

• Problema: definire come si effettua riduzione di un goal in sottogoal

tenendo conto della forma delle regole (non solo deduttiva)

PRECOND: Plist DELETE: Dlist ADD: Alist

• Stabilire come si effettua la riduzione di goal attraverso queste regole

GOAL REGRESSION

(4)

Goal regression

• Goal:

G1, G2, …, Gn

• Regola R

PRECOND: Plist

DELETE: Dlist ADD: Alist

• Regr[G1, G2, .., Gn, R] = SottoGoal

determinare quale è il sottogoal SottoGoal tale per cui l’applicazione della regola R in G porta a G1, G2, …, Gn

• Definire per ogni Gj come doveva essere in SottoGoal

G

?

Regr[G,R] = true se G∈Alist

Regr[G,R] = false se G∈Dlist

Regr[G,R] = G altrimenti

Esempio: mondo dei blocchi

• Problema: spostare blocchi su un tavolo con un braccio

• Operatori

– pickup(X) PRECOND: ontable(X), clear(X), handempty DELETE: ontable(X), clear(X), handempty ADD: holding(X)

– putdown(X) PRECOND: holding(X) DELETE: holding(X)

ADD: ontable(X), clear(X), handempty – stack(X,Y) PRECOND: holding(X), clear(Y)

DELETE: holding(X), clear(Y) ADD: handempty, on(X,Y), clear(X) – unstack(X,Y) PRECOND: handempty, on(X,Y), clear(X)

DELETE: handempty, on(X,Y), clear(X) ADD: holding(X), clear(Y)

(5)

Esempi di regressione

• regola R1: unstack(b,Y)

– Regr[holding(b), R1] = true – Regr[handempty,R1]=false – Regr[ontable(c),R1 ]=ontable (c) – Regr[clear (c), R1] = dipende se y=c Y=c clear (c)

quindi due sottogoal possibili

• Regressione è il meccanismo di base per ridurre un goal in sottogoal in

un planner backward

= = Y=c ∨clear(c)

Riduzione di goal in sottogoal

• Goal:

G1, G2, …, Gn

• Regola R

PRECOND: Plist = P1, P2, …Pm

DELETE: Dlist = D1, D2, …, Dk ADD: Alist = A1, A2, … Al

• Sottogoal che si ottiene da G con R

– Regr[G1, R], Regr[G2, R], …, Regr[Gn,R], D1, D2, …,Dk, P1, P2, … Pm – se Regr[Gi,R]=false allora tagliare

• Esempio

on(a,b), on(b,c) stack(a,b)

True, on(b,c), holding(a), clear(b)

Prec, Del: holding(a), clear(b) Add: handempty on(a,b), clear(a)

{

Regr Regr

(6)

Esempio completo

• Stato iniziale

clear(b), clear(c), on(c,a), handempty, ontable(a), ontable(b)

A C B

• Stato finale

on(a,b), on(b,c) C B A

Grafo di ricerca

on(a,b), on(b,c) stack(a,b) stack(b,c)

holding(a), clear(b), on(b,c) holding(b), clear(c), on(a,b)

ontable(a), clear(a) handempty, on(b,c), clear(b) holding(b), clear(c), holding(a) handempty, clear(X), on(X,b), X≠a, holding(a), on(b,c) handempty, clear(a), on(a,b), on(b,c) unstack(a,b) unstack(X,b) stack(b,c) pickup(a) handempty clear(X), on(X,a), ontable(a), FALSE on(b,c), clear(b) handempty clear(X), on(X,b), ontable(a), FALSE on(b,c), clear(a) X≠a holding(b), ontable(a), clear(a), on(b,c) holding(b) clear(c) ontable(a) clear(a) holding(X) ontable(a) clear(a) X≠a on(b,c) clear(b) holding(a) on(b,c) clear(b) putdown(a)

putdown(b) stack(b,c) putdown(X) unstack(X,a)

unstack(X,b)

...

_...

...

(7)

Console, Botta - Dip. Informatica, Univ. Torino Planning 13 holding(b) clear(c) ontable(a) clear(a) pickup(b) ontable(b), clear(b), handempty clear(c), ontable(a), clear(a)

putdown(c) holding(c), ontable(b), clear(b), ontable(a), clear(a)

unstack(c,a) handempty, clear(c), on(c,a) ontable(b), clear(b), ontable(a)

Questo coincide con lo stato iniziale

unstack(b,Y) handempty, clear(b), on(b,Y), clear(c), clear(a) ontable(a), Y≠a, Y≠c

...

putdown(a) holding(a), ontable(b), clear(b), clear(c)

...

unstack(c,Y) handempty, clear(c) on(c,Y), ontable(b), clear(b), Y≠b, clear(a) ontable(a), Y≠a

...

Un problema: interacting goals

• Quando due (o più) goal interagiscono possono sorgere dei problemi

ci possono essere problemi di interazione tra le due soluzioni

– goal G1, G2

• pianifico azioni per G2

• poi mi trovo però nella situazione che per risolvere G1 devo smontare tutto, compreso lo stato che avevo prodotto con G2 risolto

• Esempio

A C B stato iniziale

goal: on(b,c), on(a,b)

•azione per risolvere on(b,c) porta a stato in cui per risolvere l’altro goal devo smontare tutto

• Risolvere due goal indipendentemente non funziona

G1 G2

A1 A2

devo considerarli insieme

sia A1 dopo A2 che A2 dopo A1 non funzionano

(8)

• Soluzione completa. provare tutti gli ordinamenti

– dei goal

– dei loro sottogoal

• Soluzione efficiente (pratica)

– provare a risolverli indipendemente – verificare che la soluzione funzioni

– se non funziona, provare gli ordinamenti possibili uno alla volta

Algoritmo STRIPS

• Planner basato su ricerca backward appena discussa

• Utilizza due strutture dati

– stack di goal - descrizione S dello stato corrente

• Algoritmo

while stack non è vuoto do

if top(stack) = a and aθ = a’θ con a’∈S

then elimina a dallo stack ed esegui sost θ sullo stack; if top(stack) = a1 ∧ a2 ∧ … ∧ an

then push(ai1), push(ai2), …, push(ain) in un qualche ordine (punto di scelta non deterministica; si noti che la congiunzione rimane sullo stack e verrà riverificata dopo - interacting goals) if top(stack) = a

then - seleziona regola R con a ∈ Addlist(R) - pop(a); push(R), push(Precond(R)) if top(stack) = R

(9)

Esempio

state goal

on(c,b) ∧on(a,c) ac b clear(b) clear(c) on(c,a) ontable(a) ontable(b) handempty state goal ac b clear(b) clear(c) on(c,a) ontable(a) ontable(b) handempty state goal on(a,c) on(c,b) on(c,b) ∧on(a,c) ac b clear(b) clear(c) on(c,a) ontable(a) ontable(b) handempty on(c,b) on(a,c) on(c,b) ∧on(a,c) state goal clear(b) clear(c) on(c,a) ontable(a) ontable(b) handempty clear(c) ∧holding(a) stack(a,c) on(c,b) on(c,b) ∧on(a,c) ac b state goal clear(b) clear(c) on(c,a) ontable(a) ontable(b) handempty clear(b) ∧holding(c) stack(c,b) on(a,c) on(c,b) ∧on(a,c) ac b

...

_...

state goal clear(b) clear(c) on(c,a) ontable(a) ontable(b) handempty holding(c) clear(b) clear(b) ∧holding(c) stack(c,b) on(a,c) on(c,b) ∧on(a,c) ac b state goal clear(b) clear(c) on(c,a) ontable(a) ontable(b) handempty handempty∧clear(c) ∧on(c,Y) unstack(c,Y) clear(b) clear(b) ∧holding(c) stack(c,b) on(a,c) on(c,b) ∧on(a,c) a c b con {a/Y} la congiunzione unifica con S (evito ordini) state goal clear(b) clear(c) on(c,a) ontable(a) ontable(b) handempty unstack(c,a) clear(b) clear(b) ∧holding(c) stack(c,b) on(a,c) on(c,b) ∧on(a,c) ac b

eseguo azione unstack(c,a)

state goal clear(b) clear(a) ontable(a) ontable(b) holding(c) clear(b) clear(b) ∧holding(c) stack(c,b) on(a,c) on(c,b) ∧on(a,c) a c b state goal clear(b) clear(a) ontable(a) ontable(b) holding(c) stack(c,b) on(a,c) on(c,b) ∧on(a,c) a c b

verificato goal e congiunz.

(10)

Console, Botta - Dip. Informatica, Univ. Torino Planning 19 state goal clear(c) clear(a) ontable(a) ontable(b) on(c,b) handempty on(a,c) on(c,b) ∧on(a,c) a bc state goal clear(c) clear(a) ontable(a) ontable(b) on(c,b) handempty clear(c) ∧holding(a) stack(a,c) on(c,b) ∧on(a,c) a bc state goal clear(c) clear(a) ontable(a) ontable(b) on(c,b) handempty holding(a) clear(c) ∧holding(a) stack(a,c) on(c,b) ∧on(a,c) a bc clear(c) vero in S state goal clear(c) clear(a) ontable(a) ontable(b) on(c,b) handempty ontable(a) ∧clear(a) ∧handempty pickup(a) clear(c) ∧holding(a) stack(a,c) on(c,b) ∧on(a,c) a bc

cong OK eseguo stack

state goal clear(c) ontable(b) on(c,b) holding(a) clear(c) ∧holding(a) stack(a,c) on(c,b) ∧on(a,c) a b c state goal clear(a) ontable(b) on(c,b) on(a,c) handempty on(c,b) ∧on(a,c) a b c

cong OK eseguo pickup

elimino goal, stack vuoto FINITO

• Ricostruendo da configurazione iniziale a finale ho una soluzione

unstack(c,a) stack(c,b) pickup(a) stack(a,c)

• Ricerca

– abbiamo visto un cammino – varie alternative

• scelte non deterministiche ordinamento dei goal • più operatori applicabili per ridurre un goal

• Strategie euristiche

– strategie di ricerca

– strategie per scegliere quale goal ridurre e quale operatore

• MEANS-ENDS ANALYSIS

– cercare la differenza più significativa tra stato e goal – ridurre quella differenza per prima

(11)

Ricerca nello spazio dei piani

• STRIPS: ricerca nello spazio delle situazioni

• approccio alternativo: ricerca nello spazio dei piani

– rappresentazione di piani parziali – operatori di trasformazione di piani

• Piano:

– Insieme delle azioni che lo costituiscono con precondizioni – Ordine parziale tra le azioni: Si p Sj

– Link causali tra azioni:

• l’azione Si produce come effetto la precondizione c di Sj

• Piano iniziale: due azioni

– start: senza precondizioni

– stop: con precondizione il goal del planner – start p stop

c

Si Sj

Esempio: piano per mettersi le scarpe

• azioni

– mettiScarpaDX: PRECOND: calzaDX(on) EFFECT scarpaDX(on) – mettiScarpaSX: PRECOND: calzaSX(on) EFFECT scarpaSX(on) – mettiCalzaDX: PRECOND: - EFFECT calzaDX(on)

– mettiCalzaSX: PRECOND: - EFFECT calzaSX(on)

• Piano iniziale

Piano finale

start stop scarpaDX(on) scarpaSX(on) start stop scarpaDX(on) scarpaSX(on) mettiScarpaDX mettiScarpaSX mettiCalzaDX mettiCalzaSX calzaDx(on) calzaSx(on)

(12)

Osservazioni

• piano con ordine parziale, non vengono imposti ordinamenti non

richiesti

• Least Commitment: non imporre mai più vincoli di quelli strettamente

necessari

– non fare scelte quando don’t care – evita molti backtracking

• Linearizzazione: trasformazione da ordine parziale a ordine totale

– in generale molte soluzioni

• Algoritmo:

– ricerca nello spazio dei piani

– operatori per costruire e trasformare un piano

Algoritmo di partial order planning

(intuitivo)

While (piano non terminato) do

– seleziona una azione SN che ha una precondizione C non soddisfatta – seleziona una azione S che abbia C tra i suoi effetti

– aggiungi il vincolo di ordine S p SN – aggiungi il vincolo d’ordine Start p S p Stop – aggiungi il legame causale S --C --> SN – risolvi eventuali violazioni a legami causali

end

• ognuno dei passi di selezione è non-deterministico

• in caso di fallimento si può avere backtracking su selezioni non

deterministiche

(13)

• Violazioni a vincoli causali

ordine Legame causale S1 S2 S3 c ¬c

• Due possibili soluzioni (ma a volte non funziona nessuna delle due,

altro punto di fallimento)

demotion

promotion

S1 S2 S3 c ¬c S3 ¬c S1 S2 c

Esempio: pianificazione di acquisti

• stato iniziale: at(home), sells(hws,drill), sells(sm,milk), sells(sm,banana) • Goal: at(home), have(drill), have(milk), have(banana)

• azioni – go(Y):

• PRECOND: at(X) • EFFECT: at(Y), ¬at(X)

– buy(Y)

• PRECOND: at(S), sells(S,Y) • EFFECT: have(Y)

start

stop

at(home), sells(hws,drill), sells(sm,milk), sells(sm,banana) have(drill), have(milk), have(banana), at(home)

(14)

Primo passo:

– seleziono una azione e precondizione: have(drill)

– seleziono azione che ha la precondizione come effetto: buy(drill) – modifico il piano

start

stop

at(home), sells(hws,drill), sells(sm,milk), sells(sm,banana)

have(drill), have(milk), have(banana), at(home) buy(drill)

at(X), sells(X,drill),

Legame causale tra buy(drill) e stop per proteggere have(drill)

Secondo e terzo passo:

– procedo in modo analogo per gli altri acquisti

start

stop

at(home), sells(hws,drill), sells(sm,milk), sells(sm,banana)

have(drill), have(milk), have(banana), at(home) buy(drill) at(X), sells(X,drill) buy(milk) at(X), sells(X,milk) buy(banana) at(X), sells(X,banana),

(15)

Passi successivi:

– seleziono sells(hws,drill), sells(sm,milk), sells(sm,banana) – già veri nello stato iniziale

– devo quindi solo proteggerli con legami causali start

stop at(home)

have(drill), have(milk), have(banana), at(home) buy(drill) at(hws), sells(hws,drill) buy(milk) at(sm), sells(sm,milk) buy(banana) at(sm), sells(sm,banana),

Passo successivo:

– seleziono at(hws) precondizione di buy(drill) – seleziono azione go(hws)

start

stop at(home)

have(drill), have(milk), have(banana), at(home) buy(drill) at(hws), sells(hws,drill) buy(milk) at(sm), sells(sm,milk) buy(banana) at(sm), sells(sm,banana), go(hws) at(X)

(16)

Passo successivo:

– seleziono at(X) precondizione di go(hws)

– soddisfatta in start con at(home) per cui lo proteggo start

stop at(home)

have(drill), have(milk), have(banana), at(home) buy(drill) at(hws), sells(hws,drill) buy(milk) at(sm), sells(sm,milk) buy(banana) at(sm), sells(sm,banana), go(hws)

Passo successivo:

– procedo in modo analogo per at(sm)

start

stop at(home)

have(drill), have(milk), have(banana), at(home) buy(drill) at(hws), sells(hws,drill) buy(milk) sells(sm,milk), at(sm) buy(banana) sells(sm,banana), at(sm) go(hws) go(sm) at(home)

(17)

• A questo punto ci sono problemi

– violazioni di vincoli causali tra le azioni go(hws) e go(sm)

• se agente esegue go(hws), non può essere at(home) per fare azione go(sm) • e viceversa

– spostare ordine tra le azioni non funziona – si deve fare backtracking su ultimo passo

• risoluzione di at(sm) semplicemente da start proteggendo at(home) • eseguire go(sm) partendo da hws

start

stop at(home)

have(drill), have(milk), have(banana), at(home) buy(drill) at(hws), sells(hws,drill) buy(milk) sells(sm,milk), at(sm) buy(banana) sells(sm,banana), at(sm) go(hws) go(sm) at(hws) Due passi prima at(x) ...

Ordine tra buy(drill) e go(sm) in quanto at(hws) è protetto

legame causale go(hws) buy(drill)

(18)

• Ultimo passo

– risolvere at(home) di stop: unico modo è di metterla prima di stop start

stop at(home)

have(drill), at(home), have(milk), have(banana) buy(drill) at(hws), sells(hws,drill) buy(milk) sells(sm,milk), at(sm) buy(banana) sells(sm,banana), at(sm) go(hws) go(sm) at(hws) go(home)at(sm)

Ossia: una sola scelta non ordinata

start

stop at(home)

have(milk), at(home), have(banana), have(drill) buy(drill) at(hws), sells(hws,drill) buy(milk) sells(sm,milk), at(sm) buy(banana) at(sm), sells(sm,banana go(hws) go(sm) at(hws) go(home)at(sm)

(19)

Algoritmo partial order planning

function POP(initialGoal, operators) returns plan

plan := INITIAL_PLAN(start, stop, initialGoal)

loop

if SOLUTION(plan) then return plan;

SN, C := SELECT_SUBGOAL(plan);

CHOOSE_OPERATOR(plan, operators, SN, C);

RESOLVE_THREATS(plan)

end

function SELECT_SUBGOAL(plan)

seleziona azione SN da STEPS(plan)

con una condizione C non ancora risolta;

return SN, C

procedure CHOOSE_OPERATOR(plan, operators, SN, C)

seleziona S da operators o da STEPS(plan) che abbia C come effetto;

if non esiste S con tali proprietà then fail;

aggiungi il link causale S SN

aggiungi il vincolo di ordinamento S p SN

if S è un nuovo operatore aggiunto al piano

then aggiungi S a STEPS(plan)

aggiungi il vincolo Start p S p Stop

procedure RESOLVE_THREAT(plan)

for each azione S che viola il vincolo causale Si Sj

choose either

promotion: aggiungi il vincolo S p Si

demotion: aggiungi il vincolo Sj p S

if NOT_CONSISTENT(plan) then fail

endfor

C

(20)

Osservazioni

• più efficiente dell’approccio alla STRIPS

• possibilità di definire operatori più complessi

– effetti condizionali

Esempio: mondo dei blocchi move(B,X,Y)

PRECOND: on(B,X), clear(B), clear(Y)

EFFECT: on(B,Y), clear(X), ¬on(B,X), ¬ clear(Y) if Y≠ table – operatori logici

• effetti disgiuntivi o negazione nel goal Esempio: moneta

FLIP(C)

EFFECT testa(C) ∨ croce(C) • quantificazione universale

Esempio: operatore per trasportare un insieme di oggetti carry(BAG, X, Y)

PRECOND: bag(BAG), at(BAG,X)

EFFECT: at(BAG, Y), ¬at(BAG,X), ∀Z in(Z, BAG)→ (at(Z, Y), ¬at(Z,X))

Planning in pratica

• Molte applicazioni in domini complessi

– aereospaziale, industriale, ….

• Algoritmi visti vanno bene, ma

– problemi di efficienza in caso di molti operatori

• Tecniche per rendere più efficiente il processo di pianificazione

– Planning gerarchico

• definire operatori a diversi livelli di astrazione • pianificare ad livello alto

• sostitituire macro azioni con loro espansione (magari già precompilata)

Esempio

• planning per comprare al supermercato come visto

• azioni elementari di spostamento di un robot portano a dover pianificare più in dettaglio le azioni (macro) “go” e “buy”

– Sharing di azioni

(21)

Planning gerarchico

• Definizione di operatori a diverso livello di dettaglio

• Espansione di piani astratti in piani concreti

– pianificando parti astratte in termini di azioni più specifiche – macro-espansione di piani già precostruiti

– adattamento di piani (schemi di piani) già precostruiti

• Rappresentazione operatori astratti

– come gli altri operatori: PRECOND, EFFECT

– se macro (già costruiti) anche loro decomposizione in piani più elementari Esempio Construction

PRECOND: ownland, haveMoney EFFECT: haveHouse

DECOMPOSITION: S1: build(foundation), S2: build(frame), S3: build(roof), S4:build(walls), S5: build(interior) ORDER: S1 p S2 p S3, S2 p S4, S3 p S5, S4 p S5 S3 S4 frame S1foundationS2 _frame S5 walls roof decomposes to Have(House) Have(House) Build House Move In Move In Hire Builder Construction Own Land Have Money Buy Land Buy Land Get Loan Get Loan Own Land Have Money Obtain Permit Pay Builder

(22)

Un planner gerarchico

• Stesso algoritmo POP di prima, ma ad ogni passo si può scegliere tra

– selezionare un operatore ed estendere il piano (compresi operatori macro) – espandere un macro step del piano (usando

function HD_POP(initialGoal, methods, operators) returns plan

plan := INITIAL_PLAN(start, stop, initialGoal)

loop

if SOLUTION(plan) then return plan;

choose between

• SN, C := SELECT_SUBGOAL(plan);

CHOOSE_OPERATOR(plan, operators, SN, C);

• SnonPrim := SELECT_STEP_NON_PRIMITIVO(plan)

CHOOSE_DECOMPOSITION(SnonPrim, methods, plan)

RESOLVE_THREATS(plan)

end

Condizioni su planning gerarchico

Affinché planning gerarchico funzioni, devono essere garantite alcune

proprietà

• Vincoli sulla decomposizione

– Se azione macro A ha come effetto X e viene espansa con piano P

• X deve essere effetto di almeno una delle azioni in cui A viene decomposta e deve essere protetta fino alla fine del piano P

• ogni precondizione delle azioni in P deve essere garantita dai passi precedenti A nel piano oppure deve essere una precondizione di A

• le azioni di P non devono violare vincoli causali quando P viene sostituito ad A nel piano che si sta costruendo

Solo in questo modo si può sostituire la azione macro A con il piano P

• Sostituzione di A con P

– Si devono mettere a posto sia le relazioni d’ordine che i link causali

• Ordine s

– per ogni B tale per cui B p A si impone B p first(P) (prima azione di P) – per ogni B tale per cui A p B si impone last(P) p B (ultima azione di P)

(23)

Console, Botta - Dip. Informatica, Univ. Torino Planning 45 • Link causali

– se S A era un link nel piano, allora si deve sostituire con una serie di link S Si

dove Si sono le azioni di P che hanno C come precondizione e nessun altro passo di A prima di Si ha C come precondizione

– se A S era un link nel piano, allora si deve sostituire con una serie di link Si S

dove Si sono le azioni di P che hanno C come effetto e nessun altro passo di P dopo Si ha C come effetto

• Correttezza e completezza della pianificazione gerarchica

– Completezza: ogni volta che una macro azione A viene scartata dal

planner come inconsistente, allora tutte le sue espansioni devono

portare a inconsistenza

– Correttezza: ogni volta che una macro azione A viene inserita in un

piano, allora almeno una delle sue espansioni deve portare ad un

piano consistente

C C

Gestione di risorse limitate

• Spesso in planning necessità di trattare vincoli su risorse

– tempo: vincoli temporali sulle attività

• durata delle attività • ritardi tra attività

• vincoli sulla terminazione del piano • vincoli sull’uso di risorse • …

– altre risorse quali:

• denaro: ad esempio in planning su acquisti • materie prime: in planning su produzione • …

• Tempo: integrazione tra planning e gestione di vincoli temporali sulle

attività e sulle risorse

– vincoli temporali su goal

– ogni azione comporta vincoli temporali – mantenimento della consistenza dei vincoli – inconsistenza fa fallire il piano

(24)

Esempio: planning di attività con scadenze

– goal: prodottoP entro le 12:00 – azioni

produceP

PRECOND: liberoMaccM(T), materiePrime(T1) EFFECT: prodottoP(T2)

VINCOLI: T1 before start(T), T2 = end(T)+0:10, T lasting 2:00 – dato goal prodottoP(12:00) si ha che azione produceP può essere usata per

raggiungere goal ma vincoli temporali

ProduceP prodottoP(12:00)

liberoMacchM(T), materiePrime(T1) T between 9:50 and 11:50 T1 before 9:50

– Nuovi goal devono essere soddisfatti rispettando i vincoli temporali

• Integrazione tra planner e temporal reasoner

• Altre risorse: un possibile approccio

– variabili che memorizzano stato della risorsa – azioni possono specificare

• condizioni sulle variabili • modifiche di valore delle variabili

Esempio

– variabile $ per tener traccia dei soldi disponibili – assegnamento iniziale $=2000

buy(Y)

PRECOND: at(S), sells(S,Y), cost(Y,C), $ > C EFFECT: have(Y), $ := $-C

– Planner deve tener traccia delle variabili e aggiornarle durante la costruzione del piano

(25)

Planning and acting

• Tecniche viste fino ad ora permettono di costruire piani per

raggiungere goal

• Piani vengono poi eseguiti da agente

• Esecuzione può portare a problemi:

– alcune condizioni possono essere diverse da come previsto

• conoscenza incompleta o non corretta del planner • condizioni inaspettate

• trasformazioni del mondo

– effetti delle azioni possono essere diversi dal previsto, anche per errori dell’esecutore

• Agente in grado di

– percepire, – pianificare – agire

• Due possibili approcci

– Planning condizionale

– Monitoring della esecuzione e re-planning

Planning condizionale

• Piano costituito da

– azioni

– verifica di condizioni

– comportamento condizionale a seconda dei risultati delle verifiche

• Esempio: sostituzione ruote in una auto

remove(X) PRECOND: on(X)

EFFECT: off(X), clearHub(X), ¬on(X) putOn(X) PRECOND: off(X), clearHub(X)

EFFECT: on(X), ¬ clearHub(X), ¬off(X) inflate(X) PRECOND: intact(X), flat(X)

EFECT: inflated(X), ¬flat(X) checkTire(X) PRECOND: tire(X)

EFFECT: knowsWhether(intact(X)) – situazione iniziale:on(tire1), flat(tire1), inflated(spare) – goal: on(X), inflated(X)

(26)

Planning tradizionale produrrebbe il seguente piano:

start on(tire1)flat(tire1) inflated(spare)

stop

on(X) inflated(X)

start on(tire1)_flat(tire1)

inflated(spare) stop on(tire1) inflated(tire1) Inflate(tire1) flat(tire1) intact(tire1)

• A questo punto c’è la condizione intact(tire1) che non può essere ottenuta con nessuna azione

– fallimento nel piano

– usare le azioni che permettono di fare verifiche e costruire un piano condizionale

• Problemi

– intact(tire1) vale in una delle possibili risposte alla verifica in un contesto

– in quel contesto il piano è a posto

– però si devono considerare anche tutti gli altri possibili contesti e costruire piani anche per quei casi

Generare una copia del goal del piano per ogni altro possibile contesto – in questo modo si avrà un piano condizionale che può funzionare in

diversi contesti start on(tire1)_flat(tire1)

inflated(spare) stop on(tire1) inflated(tire1) inflate(tire1) flat(tire1) intact(tire1) check(tire1) [intact(tire1)] [¬intact(tire1)] [intact(tire1)]

(27)

Si costruisce quindi il piano

start on(tire1)_flat(tire1)

inflated(spare) stop on(tire1) inflated(tire1) inflate(tire1) flat(tire1) intact(tire1) check(tire1) _{[intact(tire1)]} [¬intact(tire1)] stop on(X) inflated(X)

start on(tire1)flat(tire1) inflated(spare) stop on(tire1) inflated(tire1) inflate(tire1) flat(tire1) intact(tire1) check(tire1) [intact(tire1)] [¬intact(tire1)] stop on(spare) inflated(spare) remove(tire1) putOn(spare) ¬intact(tire1) ¬intact(tire1) [intact(tire1)] [intact(tire1)]

Algoritmo per conditional planning

function CPOP (initialGoal, operators) returns plan INITIAL_PLAN(start, stop, initialGoal) loop

if non ci sono precondizioni non soddisfatte o contesti non analizzati then return plan;

if sono stati generati piani per i contesti C1, … Cn

then aggiungi nuovo stop goal con contesto ¬(C1 ∨... ∨ Cn); seleziona uno step SN con precondizione C;

seleziona S da operatori che aggiunge C oppure che permette di verificare C ed è compatibile con contesto corrente; if non esiste una tale azione then fail;

aggiungi S SN ai legami causali; aggiungi S p SN ai vincoli di ordinamento; if S è una nuova azione

then aggiungi S a step(plan),

aggiungi il vincolo start p S p stop C

(28)

risoluzione threats:

for each azione S che viola il vincolo causale Si Sj choose either

promotion: aggiungi il vincolo S p Si demotion: aggiungi il vincolo Sj p S

conditioning: trovare uno step condizionale Scond in cui – il contesto di Scond è compatibile con S e Sj

– Scond ha possibili risultati compatibili uno con Si e un altro con Sj; aggiungere link condizionali da Scond a Si e da Scond a Sj if nessuna scelta consistente then fail

endfor end

C

Integrazione tra planning ed esecuzione dei piani

• Pianificazione avviene per poi eseguire le azioni

• Esecuzione delle azioni può avvenire in modo corretto senza problemi

• In molti casi tuttavia si deve tener conto di eventuali situazioni

“anomale” che possono avvenire durante l’esecuzione di un piano

– errori nell’esecuzione di azioni da parte dell’agente

– modifiche impreviste allo stato per effetto di azioni di altri agenti o della “natura” (che può essere vista come un altro agente)

• Necessità di integrazione tra pianificazione ed esecuzione di piani

– verificare effetto di ogni azione – ripianificare se vi sono stati problemi

– correggere i piani se avvengono azioni esterne impreviste

• Un esempio

– pianificazione nel mondo dei blocchi con

• azioni esterne • errori di esecuzione

(29)

Console, Botta - Dip. Informatica, Univ. Torino Planning 57 Situazione iniziale _A B_E C_F D_G Goal A BE C F D G una sola azione possibile

move(X,Y)

PRECOND: clear(X), clear(Y), on(X,Z)

EFFECT: on(X,Y), ¬on(X,Z), clear(Z), ¬ clear(Y) Piano start ontable(a) on(b,e) on(c,f) on(d,g) clear(a) clear(c) clear(d) clear(b) stop on(c,d) on(d,b) move(c,d) move(d,b) on(d,g) clear(d) clear(b) on(c,f) clear(c) clear(d)

Prima di eseguire il piano qualcuno sposta D su B

start ontable(a) on(b,e) on(c,f) on(d,b) clear(a) clear(c) clear(d) clear(g) stop on(c,d) on(d,b) move(c,d) move(d,b) on(d,b) clear(d) clear(b) on(c,f) clear(c) clear(d) A BE CF D G Nuova situazione in cui si deve ri-pianificare

Ci si accorge in questo punto che la prima azione è ridondante Nuovo piano start ontable(a) on(b,e) on(c,f) on(d,b) clear(a) clear(c) clear(d) clear(g) stop on(c,d) on(d,b) move(c,d) on(c,f) clear(c) clear(d)

(30)

Azione viene eseguita, supponiamo che fallisca lasciando cadere C su A Situazione: start ontable(a) on(b,e) on(c,a) on(d,b) clear(f) clear(c) clear(d) clear(g) stop on(c,d) on(d,b) A BE C F D G

Sistema verifica che goal non soddisfatto: nuova pianificazione

start on(c,d)on(d,b) stop

move(c,d) on(c,a) clear(c) clear(d) ontable(a) on(b,e) on(c,a) on(d,b) clear(f) clear(c) clear(d) clear(g)