08. Planning

Cos'è il planning?

Riguarda la costruzione di un piano per raggiungere certi obiettivi. Dunque si cambia lo stato del sistema da un certo stato iniziale Si ad un certo stato finale Sf .
Gli stati cambiano sia perchè cambia lo stato interno dell'agente intelligente che esegue il piano, sia perchè cambia lo stato dell'ambiente dove si trova l'agente.

Cos'è un piano?

Si definiscono per prima cosa delle azioni primitive o "atomiche" che può fare l'agente intelligente. Dopodichè si cerca una composizione di queste (non una sequenza di queste, anche se alla fine useremo il termine sequenza quindi in questo contesto composizione e sequenza sono sinonimi) che si faccia passare da Si ad Sf .

Costruire un piano o problema di sintesi

Il problema di sintesi è: Dato un'insieme A di azioni primitive, dobbiamo prelevare le componenti del piano P.
Tuttavia il numero di piani che potenzialmente ci fanno passare da Si ad Sf è molto elevato (o anche illimitato), se poi consideriamo anche i piani non corretti il numero diventa molto più grande, quindi noi vorremmo costruire il piano più efficiente, ovvero quello corretto e più corto.

Problema adbduttivo vs problema di planning in termini di difficoltà

In un problema abduttivo con un set di k ipotesi ho $2^k$ (insieme potenza, comprende l'insieme vuoto) possibili set di queste k ipotesi per spiegare le manifestazioni. Con un problema di planning date k azioni elementari non ho solo $2^k$ possibili piani, ma molto di più (posso ripetere le azioni, ad esmepio), quindi il problema di planning è teoricamente più difficile con spazi di ricerca superesponenziali.

Prime strategie per costruire un piano

Supponiamo di aver costruito un piano con k azioni che ancora non ci ha portato ad Sf, la parte restante del piano rimane sempre un problema di sintesi.
Potrei cambiare punto di vista del problema e dire: dato il set di azioni A e le azioni già presenti nel piano, quale azione mi conviene fare al passo successivo? Dunque "completo" ogni volta un problema composto di un solo passo, e diventa un problema di classificazione ("qual'è l'azione migliore?") ma in generale non funziona.

Alternativamente potrei dimostrare in modo costruttivo (quindi costruendo una soluzione) che un piano da Si ad Sf esiste. Anche questa strategia, tuttavia, non funziona poichè a volte si riesce a dimostrare che il piano esiste senza però costruirlo (quindi non c'è una dimostrazione costruttiva).

Planning ed adversary search

Ad esempio in un gioco con avversario siamo nella situazione di costruire un piano con l'ambiente che cambia autonomamente (perchè l'avversario muove), ma siamo sicuri che l'esistenza di un piano esiste (prima o poi si vince, si perde o si pareggia) tuttavia non sappiamo costruirlo a priori.

Librerie di piani e classificazione

Potremmo pensare di avere una libreria di piani completi e cercare il migliore per risolvere il problema (di nuovo riduciamo il planning ad un problema di classificazione), ma in generale non funziona neanche questo approccio perchè se si usa la libreria di piani per problemi di planning simili si osserva che a piccoli cambiamenti dell'ambiente il piano cambia di molto.
Ad esempio bisogna andare da un punto A ad un punto B, e si cerca la strada più veloce. Si trova una scorciatoia passando da un giardino. Poi quel giardino viene chiuso meglio e quindi bisogna fare un giro lungo (es: il giardino è il canale di Panama, quindi bisogna passare dallo stretto di Magellano), cosa che piani simili a quello precedente non prevedono.

Tipi di pianificatori

Esistono due tipi di pianificatori:

  • Speciali -> costruiti ad hoc su un dato problema.
  • Generali -> riescono a trovare un piano su diversi problemi di planning.

Se troviamo un piano tramite un classificatore allora stiamo usando uno special planner (appunto un caso speciale che riduce il planning alla classificazione) e stiamo facendo planning by classification.

Mondo dei blocchi

E' composto da un piano infinito su cui sono appoggiati, in diverse locazioni o l'uno sull'altro, dei blocchi etichettati.

d17.jpg

Lo stato dell'ambiente è definito da predicati, ad esempio: loc(b,l) che indica che il generico blocco 'b' è nella generica locazione 'l'.
Le azioni primitive sono: A = move (b,l) (cioè muovi il generico blocco 'b' nella locazione 'l').

Ci sono una serie di condizioni che devono essere soddisfatte per poter effettuare un'azione, ad esempio posso muovere un blocco se un blocco è libero, ovvero non esistono blocchi poggiati sopra questo. Inoltre come rappresentiamo la modifica dello stato in seguito ad un'azione?
Potremmo usare i costruitti logici della logica di primo ordine:
move(b,l) -> loc (b,l)
Però questo approccio non funziona perchè se avessimo la sequenza di azioni: move(b,l1), move(b,l2) ; sarebbe implicato che un blocco ha il dono dell'ubiquità, ovvero sta in due posti diversi (l1 ed l2). Questo perchè non abbiamo aggiornato lo stato del sistema.

Quindi la logica proposizionale (o di primo ordine, ricordiamo che la logica del primo ordine è sempre riconducibile alla logica proposizionale se non esistono funtori con arità > 0) non va bene allo scopo perchè non permette di modellare agevolmente lo stato del sistema, insomma è "stateless".

Modellare il mondo dei blocchi con la logica del primo ordine

Allora posso usare la logica del primo ordine non riconducibile (quindi con funtori di arità > 0) alla logica proposizionale (ricordo che la logica del primo ordine, anche se non sempre molto maneggevole, è turing completa) potrei scrivere:
move (b,l,s) -> loc (b,l,next(s)
Ovvero sottolineando il cambiamento di stato con il funtore next(s), dunque a partire da uno stato iniziale poi avrò gli stati next(s), next(next(s)), etc… .
In questo modo non inidividuiamo per bene gli stati (o ancora non riconosciamo stati uguali), quindi sfruttiamo il fatto che noi sappiamo la differenza tra stati quindi scriviamo:
loc (b, l, result(move(b,l),s) )
Ovvero lo stato della posizione di 'b' in 'l' è il risultato (result è un funtore di arità 2) di un movimento (la move diventa funtore) di 'b' su 'l' da uno stato s precedente.

Possiamo quindi dire cosa è possibile fare facendo riferimento alla libertà di movimento di certi blocchi in certi stati:

clear(b,s) and clear(l,s) -> loc(b,l,result(move(b,l),s))
  //se il blocco 'b' e la locazione 'l' sono liberi in s, allora è possibile muovere 'b' su 'l' e lo stato sarà il risultato di questo movimento.

Reificazione

E' una tecnica per trasformare i predicati in funtori. E' solo accennata, anche se si capisce in modo intuitivo che un dato predicato è diventato un funtore.

Uso di un solo predicato. Situation calculus.

Introducendo un predicato generale (holds) abbiamo che la formula precedente diventa:

holds (clear(b), s) and holds(clear(l), s) -> holds (loc(b,l), result(move(b,l),s))

Questo ci permette di trattare un solo predicato (pianificatore leggermente meno complesso) e ci permette di dire delle cose in modo più flessibile grazie ai quantificatori: $\forall f , \neg \mbox{holds(f,s)}$ (nello stato s tutto è falso).

Il predicato holds ha arità 2. Il primo termine è detto fluente ed indica le caratteristiche del sistema in un dato stato (tipo "il blocco b è libero"), in questo contesto è un funtore. Il secondo termine è lo stato a cui è associato quel fluente. Se dico holds (f, s) allora il fluente f è vero nello stato s, viceversa not holds (f,s) indica che il fluente f è falso nello stato s.

Questo tipo di linguaggio logico è detto situation calculus. L'alternativa sarebbe quella di usare un linguaggio non dichiarativo, come un linguaggio procedurale.

Problemi classici del planning nel mondo dei blocchi

Ci sono 3 problemi classici che qualsiasi planner deve riuscire a risolvere che abbiamo già visto nella forma generale quando abbiamo discusso di logiche non monotone.

Problema del frame (frame problem)

Specificare cosa non è cambiato in seguito ad un'azione. Ad esempio se ho il blocco C sopra quello A e poi ho il blocco B su un'altra locazione, eseguire: move(C,B) muove C su B, ma è anche vero che A è rimasto nella sua posizione.

Se non c'è supporto diretto per questa specificazione nel linguaggio allora il problema di elencare le cose che non sono cambiate diventa un problema difficile.
Ad esempio nel linguaggio STRIPS c'è la STRIPS assumption che dice "tutto ciò che non è coinvolto nell'azione che porta il sistema da uno stato all'altro non è cambiato". Questa assunzione è data dal linguaggio (se si usa STRIPS si accetta la STRIPS assumption) e quindi è un supporto per risolvere il problema del frame.

Qualfication problem (problema qualificazione)

Specificare tutte le precondizione di un'azione, che devono essere tutte soddisfatte altrimenti l'azione non può essere eseguita.
Esempio:

move(b,l)
- precondizioni:
    clear(b), clear(l), detachable (b, table) //b si può muovere dal tavolo

questa serie di precondizioni è insufficiente poichè potrei fare l'azione
move(b,b) che è assurda (muovo il blocco su se stesso).
Dunque serviva anche la precondizione 'b != l', che deve valere per ogni azione quindi si avrebbe:
forall s,l not holds(loc(l,l),s)
  //in ogni stato non può essere vero che una locazione stia su se stessa.

Il qualification problem è un problema che si è rivelato difficile per il mondo dei blocchi, figurarsi per sistemi più complessi.
Inoltre le precondizioni ad un'azione potrebbero essere semplicemente troppe per essere elencate, allora potremmo usare un ragionamento "non monotono", simile alla default logic. Cioè verifichiamo che alcune precondizioni chiave siano vere e, se non c'è evidenza del contrario, assumiamo che le altre siano vere senza elencarle e che quindi l'azione si può fare.

Ramification problem (problema della ramificazione)

Specificare ciò che cambia stato di verità (cioò che diventa vero e ciò che diventa falso) in seguito all'esecuzione di un'azione.
Esempio:

move (B,C) -> diventano vere:
                loc(B,C)
                not clear (C)
                not loc (B, previusBpos) //cioè la previusBpos ora è libera, equivalentemente
                                         //si poteva scrivere clear(previusBpos)

Sostanzialmente è un'elencazione di conseguenze. Ora, se il mondo dei blocchi diventa complesso (blocchi colorati che possono essere ricolorati) allora l'insieme delle conseguenze diventa difficile da gestire.

STRIPS

Non è un linguaggio logico. Lavora su insiemi di fluenti.
Un'azione 'x' di strips è una terna:
x -> <p, a, d>
'p' è l'insieme delle precondizioni che devono essere verificate (devono trovarsi nell'insieme dei fluenti veri).
'a' è l'add list, insieme di fluenti che diventano veri come conseguenza dell'azione x.
'd' è la delete list, insieme di fluenti che diventano falsi come conseguenza dell'azione x.

'a' e 'd' aggiungono e tolgono fluenti dall'insieme di fluenti considerati come veri. Quindi il linguaggio, come detto, lavora su insiemi, e l'insieme di fluenti considerati come veri è ciò che descrive, principalmente, il sistema (perchè anche i fluenti falsi lo descrivono, dicendo cosa non è, ma i fluenti veri danno più informazione1).

'p' risolve il problema della qualficazione.
'a' e 'd' risolvono il problema della ramificazione.
La strips assumption (ciò che non è coinvolto nell'azione, cioè non sta in 'a' o 'd', non cambia stato)) risolve il problema del frame.

Un piano è la composizione di azioni base di strips.

Vantaggi e svantaggi.

Il vantaggio di questo formalismo è la semplicità.
Gli svantaggi sono:

  • Poichè non è un linguaggio logico c'è il problema della rappresentazione della conoscenza che di solito si esprime con regole logiche, tipo not a non ha senso in strips, perchè per dire che 'a' è falso basta che non sia nell'insieme delle cose vere.
  • Azioni non ben definite non possono essere espresse in STRIPS, mentre in altri formalismi si. (Ad esempio "se non c'è evidenza che i presequisiti non siano veri" è un ragionamento alla default logic non attuabile in strips)
  • Non c'è il concetto di tempo, le azioni vengono virtualmente eseguite tutte nella stessa unità di tempo. Non si riesce a rappresentare azioni parallele, ma solo sequenziali.
  • L'alternativa a strips è il situation calculus il quale, però, soffre del problema del frame.

Quindi il formalismo da usare si sceglie a seconda del problema di planning da risolvere.

Come generare un piano (approfondimento)

Approfondiamo ora il problema della creazione di un piano, dopo aver esposto alcune strategie in una sezione precedente.
Date delle azioni possibili, possiamo generare diversi piani. Se consideriamo anche quelli scorreti abbiamo un enorme spazio di soluzioni (corrette o meno) da dover vagliare. Quindi è un problema di ricerca.
Si può effettuare un approccio top down, ovvero dividere il problema in sottoproblemi e cercare un piano per ognuno di essi (l'uomo di solito ragiona così, specie se non "vede" subito la soluzione globale e quindi invece di perder tempo si aiuta su soluzioni più piccole).
Ovviamente non è detto che le azioni date permettano di risolvere il problema (e quindi tutti i sottoproblemi), siamo sempre sotto l'assunzione che le azioni date ci permettano di risolvere tutto il problema.

Tuttavia supponiamo che esista un set di azioni che riesca a risolvere il problema ed eventuali sottoproblemi di questo. Come definiamo queste azioni "utili" ? O individuiamo un buon insieme di azioni (operazione molto difficile, poichè sostanzialmente dovremmo risolvere il problema e trovare un piano) oppure rimuoviamo delle precondizioni dalle azioni più comuni per ottenere azioni più generali (di più alto livello). Ovvero un'azione con meno precondizioni potrebbe equivalere ad una sequenza di azioni originali, quindi sostanzialmente sintetizziamo sequenze di azioni originali in una azione di più alto livello. Tipo una move con meno precondizioni potrebbe equivalere a diverse move originali. (Questo approccio è usato da ABSTRIPS).

Un altro metodo è quello di riconoscere nei piani precedentemente generati (andati a buon fine) per altri problemi delle sequenze di azioni ricorrenti, così da sintetizzarle in un'azione fittizzia di alto livello.

Problemi semplici di planning

Problemi in cui il dominio (il sistema da modellare) o i cambiamenti sono facilmente prevedibili e/o rappresentabili.

Subgoal e costruizione di piani con sequenze di azioni non conflittuali

Come accennato prima potremmo pensare di suddividere il problema in sottoproblemi da risolvere, questi sottoproblemi hanno nella loro soluzione un goal, quindi dobbiamo ottenere subgoal. Tuttavia è evidente che alcuni subgoal sono ottenibili solo in una certa sequenza e quindi non è possibile identificarli in parallelo (lavorando contemporaneamente o in ordine sparso, sui sottoproblemi).
Ad esempio se ho 3 blocchi distinti A, B, C e voglio formare la pila A-B-C , devo muovere prima B su C e poi A su B.

Dunque, sia che si stia provando a risolvere l'intero problema o un sottoproblema, bisogna muoversi bene altrimenti in seguito si dovrà disfare quello che si era fatto per raggiungere la soluzione.
Un possibile rimedio a questo problema è analizzare se le conseguenze di un'azione vanno a modificare i prerequisiti di altre azioni che dovremmo fare (per risolvere altri sottoproblemi), se li modificano allora le due azioni sono conflittuali.

Quindi analizzando di volta in volta i conflitti tra le azioni disponibili dovremmo riuscire a stabilire la giusta sequenza di azioni, posto di sapere quali azioni dobbiamo fare (quindi ci manca di determinare solo la sequenza).

Ad esempio supponiamo di avere un problema "semplice", dove sappiamo determinare banalmente le operazioni da fare per ottenere la soluzione. Abbiamo un certo numero di blocchi A,B,C,D, etc… posati in diverse locazioni, quindi pronti per esser mossi e vogliamo costruire una pila A-B-C-D-etc… , sappiamo che le azioni che ci porteranno alla soluzione sono move(A,B), move(B,C), etc… solo che dobbiamo individuarne la giusta sequenza.
Quindi al primo passo verifichiamo le conseguenze di una singola azione rispetto ai prerequisiti delle varie azioni e vediamo se c'è conflitto (il conflitto c'è se un prerequisito da vero diventa falso e non il contrario). Questo lo facciamo per ogni azione. Così individuiamo che la prima azione da fare è move(W,Z) con un costo pari a $\frac{n\cdot(n-1)}{2}$ confronti di insiemi di conseguenze e precondizioni (se considerassimo le singole conseguenze e le singole condizioni potrebbe essere maggiore. Se invece gli insiemi sono di randezza costante allora il costo asintotico rimane uguale). Questo per ogni passo (ma ogni passo diminuisce le azioni disponibili). Tuttavia si avrebbe una somma di termini al più qudratici nel numero delle azioni quindi il costo complessivo sarebbe quadratico.

Con l'operazione di confronto per cercare conflitti si genera un poset (partially ordered set) tra le azioni, un reticolo che indica quali azioni possono essere fatte prima di altre solo che a volte gruppi di azioni non sono direttamente confrontabili tra loro (per questo partially ordered). Ad esempio sappiamo che l'azione 'a' viene prima di 'b' e di 'c', queste non sono confrontabili ma vengono sicuramente prima dell'azione 'd'. Tuttavia questo poset è costruito in base ai confronti che dobbiamo fare preventivamente, quindi ha un costo non banale (è solo n^2 per l'esempio semplice fatto sopra).

Nei casi più disperati possiamo procedere a tentativi, ovvero via backtracking provando di volta in volta a costruire sequenze di azioni finchè non ci ritroviamo ad un vicolo cieco, arrivati al vicolo cieco tornieamo indietro e facciamo un'altra scelta.

A volte i subgoal non sono sequenze di una singola azione ma sono sequenze intermedie di azioni per arrivare ad una certa configurazione del sinstema. In altri casi possono esserci subgoal non espliciti (cioè non si riconosce che bisogna portare il sistema prima in una certa configurazione), che sono dette anomalie di sussman.

Backward planner per STRIPS

Un modo per costruire un piano, in strips, è quello di costruire una sequenza di azioni all'indietro (in sostanza backward search) che ci portano dallo stato finale allo stato iniziale. Richiamiamo un secondo la notazione, modificandola.

a //azione strips
P(a) //precondizioni per eseguire a
A(a) //conseguenze di 'a', fluenti resi veri da a
D(a) //fluenti resi falsi da 'a', delete list

S set di fluenti "veri" prima di applicare l'azione a.

Quindi si costruisce l'albero di ricerca, ma, dato un generico nodo quali sono i figli di questo? In altri termini come si costruisce l'albero di ricerca?

Diciamo che, dati 'a' ed 'S' come descritto prima, 'a' ha successo (success) se $P(a) \in S \wedge \mbox{result}(S,a)=(S \setminus D(a)) \cup A(a)$, dove result restituisce il nuovo stato dopo l'applicazione di a.

Generalizziamo il concetto avendo la sequenza di azioni $a_1, \ldots, a_n$ partendo da S0 .
$S_i = \mbox{result}(S_{i-1},a_1, \ldots, a_i) \ , i=1, \ldots, n$
e quindi diremo che la sequenza $a_1, \ldots, a_n$ ha successo in S se $\forall i (a_i \mbox{ succeeds in } S_i )$ e si può aggiungere che un goal 'g' è ottenuto (is achieved) in S con la sequenza $a_0, \ldots, a_n$ se $g \in S_n$ ovvero g è un fluente vero dopo l'applicazione della sequenza su S0 .

2 azioni di movimento

Cerchiamo di generalizzare le azioni per doverne trattare poche, quindi utilizziamo:

move(x,y,z)
    muovo il blocco x dalla locazione y alla locazione z

movett(x,y)
    muovo il blocco x dalla locazione y sul tavolo. Cioè move2table o movett. Posso anche
    muovere da tavolo a tavolo, quindi possiamo avere movett(x,table)

Il tavolo ha sempre posizioni libere perchè è infinito.

Definizione strips di queste azioni:

move(x,y,z)
    P(a)
      clear(x)
      loc(x,y)
      clear(z)
    A(a)
      loc(x,z)
      clear(y)
    D(a)
      loc(x,y)
      clear(z)

movett(x,y)
    P(a)
      clear(x)
      loc(x,y)
    A(a)
      loc(x,table)
      clear(y)
    D(a)
      loc(x,y)

Poi ci sarebbero alcune operazioni semanticamente assurde da evitare, tipo il muovere il blocco sullo stesso blocco. Tuttavia possiamo ipotizzare che queste azioni siano evitate a monte.

Nodi dell'albero di ricerca

I nodi dell'albero di ricerca (ricerca backward) sono coppie: (G, Acl).
G: insieme di goal da conseguire
Acl: una lista parziale di azioni che permettono di arrivare al prossimo nodo.

Se 'S' è la situazione iniziale, Sf è la situazione finale che è descrivibile da un insieme di goal finali, detto Gf .

Siccome la ricerca è all'indietro, la radice dell'albero è lo stato finale: (Gf , []) ; dove '[]' sono le azioni vuote (non dobbiamo fare nulla perchè non dobbiamo muoverci su nuovi nodi.)

Prendiamo un nodo generico, quando questo è una foglia (quindi un possibile punto d'inizio dell'applicazione delle azioni)?
Dato il nodo (z, [a1 , …, an] ) questo è foglia quando $z \subseteq S$, ovvero io riesco a portare S o parte di esso (z), applicando la sequenza di azioni [a1 , …, an] , nello stato finale. Nel caso in cui esistesse un nodo simile con uno z' tale che $z' \subseteq z$ non sarebbe di nostro interesse perchè a noi interessa partire dall'insieme di fluenti (o da un sottoinsieme di questo) dell'insieme di partenza, qualsiasi miglioramento (in termini di insieme minimale) a noi non interessa.
Acl è la sequenza di azioni che si costruisce di nodo in nodo, fino ad arrivare alla sequenza finale definita dai nodi foglia, ovvero [a1 , …, an] .

Definiamo ora i successori di nodi non foglia (SPOILER: questa definizione non va bene, vedi esempio sotto). nodoNonFoglia = (z, [a1 , …, an])
Sia 'a' un'azione tale che $A(a) \cap z \ne \emptyset$, ovvero che a potrebbe aver contribuito a formare 'z'. Quindi se 'a' contribuisce a creare z io riesco a creare il nodo successore (che, essendo la ricerca backward, è in realtà il nodo precedente) in questo modo:
$( ( z \setminus A(a) ) \cup P(a), [a, a_1, \ldots, a_n] )$
Ovvero il nodo successore (precedente nell'esecuzione normale, non backward) avrà che il set di fluenti vero è pari a 'z' meno i set di fluenti resi da veri unito al set di precondizioni che attivano a, e la sequenza di azioni che porterà allo stato successivo parte da 'a' (che infatti porterà al nodo da cui siamo partiti) e finisce ad an (che porterà allo stato finale).

Definizioni non molto solide, lo vediamo con un esempio.

Date i seguenti stati iniziale e finale:

d18.jpg

Costruiamo l'albero di ricerca e per semplicità scriviamo solo le azioni nei nodi e non i fluenti, ovvero invece di scrivere nodo = (insiemeFluenti, sequenza azioni) , scriveremo nodo = sequenza azioni

[] //root, nessuna azione da fare siamo arrivati allo stato finale (backward)
  [liv1] 
  move (A, table, B)
    si nota che l'addlist di questa azione ha un'intersezione non vuota con l'insieme dei
    fluenti dello stato successivo (identificato dal nodo '[]'). Cioè, per esempio, ha loc(A,B) che è un fluente
    vero nello stato finale.
    [liv2]
    move (B, table, C), move (A, table, B)
      come prima, addlist dell'azione move (B, table, C) ha intersezione non vuota con i fluenti resi veri nel nodo identificato dalla sola
      move (A, table, B).
      Questo è uno stato foglia perchè il set di fluenti vero in questo nodo è un sottoinsieme (proprio o improprio) 
      dei fluenti veri nello stato iniziale. Infatti si ha, ad esempio, che A,B,C sono tutti sul tavolo perchè ancora bisogna
      muoverli.
  [liv1]
  move (B, table, C)
    Qui si avrebbe una contraddizione, perchè A nello stato finale è sopra B e non possiamo inserire blocchi
    nel "mezzo". Tuttavia bisogna seguire strettamente la definizione, poichè un automatismo non si accorgerebbe,
    a differenza di un umano, della contraddizione.
    [liv2]
    move (A, table, B), move (B, table, C)
      Il piano di questo ramo non è ammissibile poichè le mosse precedenti falsificano
      le precondizioni delle mosse successive, ad esempio il fatto che B deve essere libero per esser mosso su C,
      ma se muovo A sopra B, B non si può muovere.
  [liv1]
  move (A, B, C)
    Stesso commento del nodo di pari livello precedente.

Quindi abbiamo visto che, con la definizione di nodo data, si hanno contraddizioni, quindi bisogna modificarla tenendo conto della delete list di un'azione.

Ridefinizione: nodo successore.

Quella dei nodi foglia rimane quella precedente, quindi cambia la definizione di nodi successori a nodi non foglia:
nodoNonFoglia = (z, [a1 , …, an])
Sia 'a' un'azione tale che $A(a) \cap z \ne \emptyset$, ovvero che a potrebbe aver contribuito a formare 'z' senza generare contraddizioni, ovvero deve essere anche vero che $D(a) \cap z = \emptyset$, altrimenti potremmo falsificare qualcosa che deve esser vero in 'z' in quanto 'z' è noto e quindi bisogna evitare contraddizioni. Quindi se 'a' contribuisce a creare z senza contraddizioni io riesco a creare il nodo successore (che, essendo la ricerca backward, è in realtà il nodo precedente) in questo modo:
$( ( z \setminus A(a) ) \cup P(a), [a, a_1, \ldots, a_n] )$
Ovvero il nodo successore (precedente nell'esecuzione normale, non backward) avrà che il set di fluenti vero è pari a 'z' meno i set di fluenti resi da veri unito al set di precondizioni che attivano a, e la sequenza di azioni che porterà allo stato successivo parte da 'a' (che infatti porterà al nodo da cui siamo partiti) e finisce ad an (che porterà allo stato finale).

In questo modo la costruzione dell'albero funziona e quindi, risolto il problema della generazione dell'albero, rimane il problema della ricerca del path nell'albero, argomento che abbiamo già visto in precedenza (blind search, heuristic search e simili).

Altre informazioni sul planning

Trasformare un problema di planning in un problema noto

Spesso i problemi di planning sono trasformati in problemi differenti ma maggiormente studiati. Ad esempio SAT. Questo perchè alcuni problemi sono stati studiati più approfonditamente e quindi sono stati sviluppati degli strumenti risolutivi più potenti.

Realtime planning

Quando ad un evento corrisponde un'azione, ovvero decisioni realtime (e la conseguenza della decisione modificherà l'ambiente). Il problema è che l'agente deve conoscere il dominio degli eventi, altrimenti potrebbe non saper rispondere ad un dato evento.

Case based planning

Abbiamo una libreria di piani già fatti che risolvono certe situazioni, quindi si cerca un piano tra questi che meglio si adatta a risolvere la situazione corrente e poi lo si modifica in modo tale che la possa risolvere appieno. Il problema è che a piccole variazioni ambientali il piano può cambiare molto quindi la modifica può essere molto complicata.

Dynamic planning

Partiamo con un piano completo, monitoriamo l'ambiente e modifichiamo il piano di conseguenza. Simile al realtime planning, ma il realtime planning costruisce piani a breve termine, invece nel dynamic il piano è potenzialmente completo (se l'ambiente non cambia).

Unless otherwise stated, the content of this page is licensed under Creative Commons Attribution-ShareAlike 3.0 License