1. Introduzione

Nella visione cosiddetta "classica" dell'IA di norma si assume che un sistema intelligente sia costituito da 3 componenti o macro-sistemi:

1. un sistema percettivo in grado di estrarre informazione dall'ambiente esterno;

2. un pianificatore in grado di generare una sequenza di azioni (anche detta piano) che, tenuto conto della situazione corrente, permetta al sistema di raggiungere i suoi scopi;

3. un sistema motorio o esecutore che traduca il piano in azioni effettive.

Il pianificatore costituisce dunque il cuore del sistema.

Il pianificatore è un sistema che riceve in ingresso dal sistema percettivo una descrizione dello stato attuale e una descrizione dello stato che si vuole raggiungere (scopo) e, basandosi su un insieme di conoscenze, genera un piano che una volta eseguito è in grado di permettere al sistema di raggiungere lo scopo o gli scopi desiderati.

Il pianificatore opera di norma su informazioni di tipo simbolico. In altre parole, lo stato del mondo, le conoscenze del pianificatore, lo scopo e il piano sono rappresentate con una serie di espressioni simboliche appartenenti ad un linguaggio con una sintassi ben definita.

La pianificazione (pianificazione) dunque è un metodo alternativo al problem solving, e se ne differenzia per il fatto che:

gli stati, gli scopi e le azioni vengono rappresentati esplicitamente;

durante la creazione di un piano, il pianificatore può aggiungere azioni in qualsiasi punto senza necessariamente procedere in modo incrementale a partire dallo stato iniziale o dallo stato finale.

La pianificazione automatica consiste nel sintetizzare una sequenza di azioni che eseguite da un agente a partire da uno stato "iniziale" del mondo provocano il raggiungimento di uno stato "desiderato".

Dati:

- 818g68i 818g68i uno stato iniziale

- 818g68i 818g68i un insieme di azioni eseguibili

- 818g68i 818g68i un obiettivo da raggiungere

Un problema di pianificazione consiste nel determinare un piano, ossia un insieme (parzialmente o totalmente) ordinato di azioni necessarie per raggiungere l'obiettivo.

Un piano deve essere "non decomponibile" e "reversibile", nel senso che, ci può essere interazione fra i sottoproblemi e le scelte fatte durante la generazione del piano sono revocabili. L'esecuzione del piano, intesa come il processo di applicazione della procedura di soluzione per l'effettiva risoluzione del problema, può essere irreversibile oppure non deterministica.

Il non determinismo implica che il piano può avere un effetto diverso nel momento in cui viene applicato al mondo reale poiché questo è spesso impredicibile. In quest'ultimo caso è possibile rifare il piano solo parzialmente, oppure invalidarlo tutto a seconda del problema.

Pianificare è:

• un task di per sé
• un'attività comune a molti task, ad esempio

- 818g68i 818g68i diagnosi: pianificazione di test o azioni per riparare (riconfigurare) un sistema

- 818g68i 818g68i scheduling

- 818g68i 818g68i robotica

Esempio

Pianificare è una attività che tutti gli esseri umani svolgono nel loro quotidiano.

Supponiamo che il nostro obiettivo sia quello di seguire una lezione di Intelligenza Artificiale e di

essere attualmente a casa e di possedere una macchina (stato iniziale).

Al fine di raggiungere lo scopo prefissato dobbiamo fare una serie di azioni in una certa sequenza:

1. prendere materiale necessario per gli appunti

2. prendere le chiavi della macchina

3. uscire di casa

4. prendere la macchina

5. raggiungere la facoltà

6. entrare in aula e seguire la lezione.

Pianificare ci permette di fare le azioni giuste nella sequenza giusta: non possiamo pensare di invertire l'ordine delle azioni 2 e 3.

Per alcune di queste azioni non è necessario pianificare l'ordine (il piano può avere un ordinamento parziale). Per esempio invertendo l'ordine delle azioni 1 e 2 si ottiene un piano corretto analogo al precedente.

Ci possono essere piani alternativi per raggiungere lo stesso obiettivo (posso pensare di andare in facoltà a piedi o in autobus).

Es di piano alternativo

1. prendere materiale necessario per gli appunti

2. prendere biglietto autobus

3. uscire di casa

4. raggiungere la fermata

5. salire sull'autobus

6. raggiungere la facoltà

7. entrare in aula e seguire la lezione.

Gran parte degli esempi che riguardano problemi di pianificazione sono ambientati nel mondo dei

blocchi che consiste nello spostare con un braccio meccanico dei blocchi su di un tavolo. Possono essere spostati solo i blocchi che sono "liberi". Un blocco e' libero se non ci sono altri blocchi su di esso.

2. Concetti base

Un pianificatore automatico è un agente intelligente che opera in un certo dominio e che date:

1. una rappresentazione dello stato iniziale

2. una rappresentazione dell'obiettivo

3. una descrizione formale delle azioni eseguibili

sintetizza dinamicamente il piano di azioni necessario per raggiungere l'obiettivo.

1. Rappresentazione dello stato.

Occorre fornire al pianificatore un modello del sistema su cui opera.

In genere lo stato è rappresentato in forma dichiarativa con una congiunzione di formule atomiche che esprime la situazione di partenza.

Es: sopra(libro,tavolo) AND nome(xyz,libro) AND aCasa(tavolo)

Lo stato di un sistema spesso può essere osservato solo in modo parziale per una serie di motivi:

- 818g68i 818g68i perché alcuni aspetti non sono osservabili;

- 818g68i 818g68i perché il dominio è troppo vasto per essere rappresentato nella sua interezza (limitate capacità computazionali per la rappresentazione);

- 818g68i 818g68i perché le osservazioni sono soggette ad "errori" e quindi si hanno delle osservazioni parziali o imperfette;

- 818g68i 818g68i perché il dominio è troppo dinamico per consentire un aggiornamento continuo della rappresentazione.

2. Rappresentazione dell'obiettivo

Per rappresentare l'obiettivo si utilizza lo stesso linguaggio formale con cui si esprime lo stato

iniziale. In questo caso la congiunzione rappresenta una descrizione parziale dello stato finale che si vuole raggiungere: descrive solo le condizioni che devono essere verificate affinché l'obiettivo sia soddisfatto.

3. Rappresentazione delle azioni.

È necessario fornire al pianificatore una descrizione formale delle azioni eseguibili sul sistema detta "Teoria del Dominio".

Ciascuna azione è identificata da un nome e modellata in forma dichiarativa per mezzo di precondizioni e postcondizioni.

Le precondizioni rappresentano le condizioni che devono essere verificate affinché l'azione possa essere eseguita; le postcondizioni rappresentano gli effetti dell'azione stessa sul mondo.

Spesso la Teoria del Dominio è costituita da operatori con variabili che definiscono classi di azioni. A diverse istanziazioni delle variabili corrispondono diverse azioni.

Un pianificatore è completo quando riesce sempre a trovare la soluzione se esiste ed è corretto quando la soluzione trovata è sempre corretta.

I problemi di cui un pianificatore deve tener conto sono:

1.Il problema della qualificazione

Tale problema consiste nel definire con precisione quali sono le precondizioni che fanno si che un azione venga eseguita con successo. Il nostro piano potrebbe fallire in seguito ad una vasta serie di motivi, ed ognuno di questi motivi potrebbe venir considerato come una precondizione della azione, siccome possiamo immaginare una immensità di tali motivi elencarli tutti risulterebbe praticamente impossibile.

2.Il problema del frame

Descrive cosa resta immutato una volta che una azione viene eseguita con successo. Gli assiomi che vengono utilizzati per descrivere una certa azione devono specificare in modo completo lo stato del mondo che si ottiene in seguito ad una azione. In altre parole oltre a stabilire che cosa cambia in conseguenza all'esecuzione di una data azione gli assiomi devono indicare anche quali sono le cose che non cambiano e che cosa resta invariato dopo una azione che viene eseguita.

E' necessario avere assiomi che descrivono le cose che l'azione lascia invariate e assiomi di questo tipo sono necessari per ogni predicato utilizzato nel descrivere lo stato del mondo. Per esempio se nel mondo dei blocchi avevamo dei predicati che indicavano il peso, il colore o altro ancora relativamente ad un blocco ci sarebbe stato bisogno di un assioma che asseriva che spostare un blocco non cambia il colore ed il peso di un blocco.

3.Il problema della ramificazione

Il problema della ramificazione: descrivere precisamente cosa cambia una volta che una azione viene eseguita con successo.

Questo problema invece consiste nel fatto che le conseguenze di una azione non sono cosi scontate come sembra cioe' descrivere completamente le conseguenze di una azione e' piu' difficile di quanto una persona si aspetti.

3. Pianificazione Classica

La pianificazione classica rappresenta un tipo di pianificazione off-line che produce l'intero piano prima di eseguirlo lavorando su una rappresentazione istantanea dello stato corrente.

Per poter descrivere l'approccio classico della pianificazione bisogna fare le seguenti assunzioni:

• lo stato iniziale è completamente noto a priori
• il mondo in ogni istante si trova in un determinato stato e ad istanti diversi si può trovare in stati diversi
• il mondo cambia stato solo in conseguenza di un'azione
• in ogni istante può verificarsi al più un'azione
• l' esecuzione del piano rappresenta l'unica causa di cambiamento del mondo

Le tecniche di pianificazione classica si dividono in:

- pianificazione deduttivo

- pianificazione mediante ricerca

- pianificazione gerarchico

3.1 Pianificazione Deduttivo

La tecnica di pianificazione deduttiva utilizza la logica per rappresentare gli stati, gli obiettivi e le azioni e genera il piano come dimostrazione di un teorema.

Un linguaggio di rappresentazione di azioni è il calcolo delle situazioni.

La formalizzazione del linguaggio (basato sulla logica dei predicati del primo ordine) è in grado di rappresentare stati e azioni in funzione del tempo. Si possono distinguere 3 parti principali di un problema:

- Stato iniziale: rappresentazione del mondo e delle proprietà che valgono in un determinato istante S0.

- Azioni: definiscono quali proprietà saranno vere come risultato di un'azione.

- Costruzione di un piano: deduzione, dimostrazione di un obiettivo.

Esempio: mondo dei blocchi

stato iniziale

sopra(b,a,s)   

sulTavolo(c,s)

azioni

sopra(X,Y,S) and libera(X,S) ,

(sulTavolo(X,do(MettiSulTavolo(X),S))) and

(libera(Y,do(MettiSulTavolo(X),S)))

costruzione di un piano

(sulTavolo(b,S)) ?

YES se S=MettiSulTavolo(b,s0)

Il vantaggio del calcolo delle situazioni è rappresentato da un' elevata espressività nella descrizione di problemi complessi, ma presenta il problema del frame.

Il calcolo delle situazioni viene utilizzato da Green per costruire un pianificatore basato sul metodo di risoluzione.

Si cerca la prova di una formula contenente una variabile di stato che alla fine della dimostrazione sarà istanziata al piano di azioni che permette di raggiungere l'obiettivo. Il lavoro del sistema è di provare che l'obiettivo è soddisfattibile ossia che esiste qualche stato in cui la condizione è vera. Una speciale funzione do(azione,stato) denota la funzione che associa uno stato a un altro stato in seguito a un' azione. La formulazione di Green usa anche un frame assertion per stabilire cosa non cambia in seguito a un'azione. Uno svantaggio è che è richiesto un frame assertion per ogni semplice relazione di un'azione.

Esempio

- I seguenti assiomi descrivono tutte le relazioni vere nello stato iniziale s0

A.1 on(a,d,s0).

A.2 on(b,e,s0).

A.3 on(c,f,s0).

A.4 clear(a,s0).

A.5 clear(b,s0).

A.6 clear(c,s0).

A.7 clear(g,s0).

A.8 diff(a,b)

A.9 diff(a,c)

A.10 diff(a,d)...

- Le azioni si esprimono con assiomi nella forme a clausole

L'azione move(X,Y,Z)

clear(X,S) and clear(Z,S) and on(X,Y,S) and diff(X,Z) -> clear(Y,do(move(X,Y,Z),S)),

on(X,Z,do(move(X,Y,Z),S)).

che sposta un blocco X da Y a Z, partendo dallo stato S (stato risultante do(move(X,Y,Z),S)) si esprime con i seguenti assiomi (effect axioms)

A.11 ~clear(X,S) or ~clear(Z,S) or ~on(X,Y,S) or ~diff(X,Z) or clear(Y,do(move(X,Y,Z),S)).

A.12 ~clear(X,S) or ~clear(Z,S) or ~on(X,Y,S) or ~diff(X,Z) or on(X,Z,do(move(X,Y,Z),S)).

Dato un obiettivo vediamo un esempio di come si riesce a trovare una soluzione usando il metodo

di risoluzione:

OBIETTIVO:- on(a,b,S1)

~on(a,b,S1)

(A.12)

~clear(a,S) or ~clear(b,S) or ~on(a,Y,S) or ~diff(a,b)

(A.4) (A.5) (A.1) (A.8)

, , true

~on(a,b,S1) risulta falso e on(a,b,S1) risulta vero con la sostituzione S1/do(move(a,d,b),s0).

Supponiamo di voler risolvere un problema un po' più complesso

Obiettivo: on(a,b,S), on(b,g,S).

Soluzione: S/do(move(a,d,b),do(move(b,e,g),s0)).

Per poter risolverlo occorre una descrizione completa dello stato risultante dall'esecuzione di ciascuna azione.

Un tentativo di semplificare il frame assertion della formulazione di Green è l'approccio di Kowalsky. In essa viene utilizzato:

- Il predicato holds(rel, s/a) per indicare tutte le relazioni rel vere in un certo stato s o rese vere da una certa azione a

- Il predicato poss(s) che indica che uno stato s è possibile ovvero raggiungibile.

- Il predicato pact(a,s) per affermare che è lecito compiere una determinata azione a in un particolare stato s, ovvero le precondizioni per svolgere l'azione sono soddisfatte in s.

Se uno stato è possibile e se le precondizioni pact sono soddisfatte in quello stato, allora anche lo stato prodotto è possibile:

poss(S) and pact(U,S)   poss(do(U,S))

Quelli che nella formulazione di Green sono predicati qui diventano termini. In pratica, guadagnamo i vantaggi di una formulazione del II ordine mantenendoci in un sistema del I ordine. In questo modo abbiamo bisogno di una singola

frame assertion per ogni azione (vantaggio rispetto a Green). Nell'esempio precedente l'unica frame assertion che deve essere esplicitata è:

holds(V,S) Y diff(V,clear(Z)) Y diff(V,on(X,Y))

holds(V,do(move(X,Y,Z),S)))

che afferma che tutti i termini differenti da clear(Z) e on(X,Y) valgono ancora in tutti gli stati prodotti dall'esecuzione di move.

ESEMPIO

Obiettivo

poss(S), holds(on(a,b),S), holds(on(b,g),S).

Stato iniziale

poss(s0).

holds(on(a,d),s0).

holds(on(b,e),s0).

holds(on(c,f),s0).

holds(clear(a),s0). 

holds(clear(b),s0).

holds(clear(c),s0).

holds(clear(g),s0).

Effetti dell'azione move(X,Y,Z):

holds(clear(Y),do(move(X,Y,Z),S)).

holds(on(X,Z),do(move(X,Y,Z),S)).

Clausola che esprime le precondizioni dell'azione

move(X,Y,Z):

pact(move(X,Y,Z),S):-

holds(clear(X),S), holds(clear(Z),S), holds(on(X,Y),S),

X\=Z.

Clausola per esprimere le condizioni di frame:

holds(V,do(move(X,Y,Z),S)):-

holds(V,S),

V\=clear(Z),

V\=on(X,Y).

Clausola per esprimere la raggiungibilità di uno stato:

poss(do(U,S)):-

poss(S),

pact(U,S).

Soluzione

poss(S), holds(on(b,g),S), holds(on(a,b),S).

Yes per S = do(move(a, d, b), do(move(b, e, g), s0))

3.2 Pianificazione mediante ricerca

La pianificazione classica, non deduttiva, utilizza linguaggi specializzati per rappresentare stati, obiettivo e azioni; e gestisce la generazione del piano come un problema di ricerca in un albero.

Tale ricerca può essere effettuata:

nello spazio degli stati: ogni nodo dell'albero rappresenta uno stato ed ogni arco rappresenta una azione, il problema di pianificazione diventa quello di trovare un cammino dallo stato iniziale allo stato obiettivo;

nello spazio dei piani: ogni nodo dell'albero di ricerca rappresenta un piano parziale e ogni arco un'operazione sul piano.

3.2.1 Ricerca nello spazio degli stati

La ricerca nello spazio degli stati e' una forma di pianificazione lineare.

Lo spazio degli stati è l'insieme di tutti gli stati raggiungibili dallo stato iniziale con una qualunque sequenza di operatori.

Esso è caratterizzato da uno stato iniziale in cui l'agente di pianificazione sa di trovarsi (che tuttavia non e' noto a priori) e da un insieme di azioni possibili che sono disponibili da parte dell'agente (Operatori che trasformano uno stato in un altro o più formalmente una funzione successore S(X) che riceve in ingresso uno stato e restituisce l'insieme degli stati raggiungibili).

Risolvere il problema in questo contesto, significa trovare un cammino, cioe' una sequenza di azioni, dallo stato iniziale ad uno stato obiettivo nello spazio degli stati, inoltre, potrebbe essere necessario raggiungere una serie di obiettivi 'secondari':trovare la sequenza di operatori che arrivano al obiettivo, trovare tutte le soluzioni o trovare una soluzione ottima.

Una soluzione per essere corretta deve essere efficace, completa e consistente.

Efficace: cioè deve garantire il raggiungimento dell'obiettivo;

Completa: deve essere completa nel senso che le precondizioni necessarie per l'esecuzione di ciascuna azione devono essere verificate e, ove necessario, attuate attraverso l'esecuzione delle azioni precedenti;

Consistente: deve essere consistente nel senso che non ci debbono essere contraddizioni derivanti dall'ordine di esecuzione delle azioni o dall'istanziazione delle variabili.

Per ottenere una soluzione come quella descritta sopra è necessario definire un algoritmo (algoritmo di pianificazione) che, in base allo stato iniziale, all'obiettivo, e alle azioni disponibili costruisca progressivamente un piano con le caratteristiche di efficacia, completezza e consistenza descritte sopra.

Per determinare se l'agente ha raggiunto o meno l'obiettivo si definisce un "TEST OBIETTIVO", la cui verifica può essere fatta testando l'appartenenza dello stato raggiunto all'insieme degli stati finali.

In quest'ultimo caso vuol dire che una soluzione può essere preferibile a un'altra.

Sorge ora il problema di definire l'algoritmo di ricerca e il formalismo per la rappresentazione degli stati e delle azioni.

Algoritmo di ricerca

Generalmente distinguiamo tra due tipi di ricerca:

Forward: se la ricerca avviene in modo progressivo partendo dallo stato iniziale fino al raggiungimento di uno stato che soddisfa l'obiettivo.

Backward: quando la ricerca è attuata in modo regressivo a partire dal obiettivo fino a ridurre l'obiettivo in sottobiettivo soddisfatti dallo stato iniziale.

La ricerca Backward ci pone di fronte al problema della riduzione di un obiettivo in sottoobiettivo, anche se ha il vantaggio di ridurre la ramificazione e il backtracking.

La ricerca Forward e' impraticabile quando il numero di possibili stati e di regole è elevato, in questo caso occorrono delle euristiche per migliorare l'efficienza.

Per determinare se l'agente ha raggiunto o meno l'obiettivo si definisce un 'TEST OBIETTIVO', la cui verifica puo' essere fatta testando l'appartenenza dello stato raggiunto all'insieme degli stati finali.

Un esempio: Il rompicapo dell'8

Stati: posizione di ciascuna delle tessere;

Operatori: lo spazio vuoto si sposta a destra, a sinistra, in alto e in basso;

Test obiettivo: descrizione dello stato finale;

Costo di cammino: ciascun passo costa 1.

3.2.2 STRIPS

Nei primi anni '70 alla universita' di Stanford nasce STRIPS (Stanford Research Institute Problem Solver)

Strips e' in un certo senso l'antenato degli attuali sistemi di pianificazione, esso e' un linguaggio per la rappresentazione di azioni, basato su una sintassi molto più semplice del Situation Calculus (meno espressività, più efficienza), ed e' anche un algoritmo per la costruzione di piani.

L'idea chiave di questo sistema è quella di utilizzare un linguaggio ristretto e un algoritmo di ricerca specifico (adatto al dominio e al linguaggio scelto) in grado di assicurare una pianificazione efficiente piuttosto che un linguaggio generale (come ad es. un formalismo logico) e un risolutore generale di problemi per la ricerca della soluzione.

STRIPS è stato sviluppato originariamente per controllare Shakey, un robot mobile sviluppato allo Stanford Research Institute in quegli stessi anni, che doveva essere in grado di svolgere semplici compiti all'interno di un'area formata da una serie di stanze e un corridoio (ad es. spostare un oggetto da una stanza all'altra).

In STRIPS stati, obiettivi e piani vengono rappresentati con una sequenza di predicati, inoltre esso risolve il problema del 'Frame',attraverso una assunzione detta "Strips Assumption":

"'tutto ciò che non è specificato resta immutato"

STRIPS: Un esempio

Supponiamo che nello stato attuale Shakey si trovi nella stanza A, che l'oggetto 'LIBRO' si trovi nella stanza D, e che lo scopo di Shakey sia quella di far si che l'oggetto sia nella stanza C e che Shakey sia nella stanza B.

Lo stato iniziale del robot e dell'ambiente può essere rappresentato nel modo seguente (dove i puntini indicano una serie di altri predicati che descrivono in modo esaustivo l'ambiente):

Posizione(Shakey, StanzaA), Posizione(OggettoLibro, StanzaD), ..........

Lo scopo del pianificatore può essere rappresentato nel modo seguente:

Posizione(OggettoLibro, StanzaC), Posizione(Shakey, StanzaB)

inoltre nella rappresentazione di un obiettivo oltre alle proprieta' si possono avere anche variabili:

Posizione(X,StanzaC)

Le azioni che Shakey può utilizzare per creare un piano possono essere rappresentate usando la seguente notazione:

• ¬ indica l'operatore logico NOT
• AZIONE indica il nome dell'azione
• PRECONDIZIONI indica le condizioni che debbono essere soddisfatte affinché l'azione possa essere eseguita
• EFFETTI indica le conseguenze dell'azione

Per brevità indichiamo solo le azioni che sono necessarie per raggiungere lo scopo descritto sopra nelle condizioni di partenza indicate:

Operazione(AZIONE: vai(x,y),
PRECONDIZIONI: Posizione(Shakey,x),
EFFETTI: Posizione(Shakey,y), ¬Posizione(Shakey,x))

Operazione(AZIONE: prendi(x,y),
PRECONDIZIONI: Posizione(Shakey,y) Posizione(x,y), Pinza(Shakey,vuota),
EFFETTI: Pinza(Shakey,x), ¬Posizione(x,y), ¬Pinza(Shakey,vuota))

Operazione(AZIONE: lascia(x,y),
PRECONDIZIONI: Pinza(Shakey,x), Posizione(Shakey,y)
EFFETTI: Pinza(Shakey,vuota), Posizione(x,y), ¬Pinza(Shakey,vuota))

La soluzione può essere rappresentata dal piano seguente:
vai(StanzaA, StanzaD),
prendi(OggettoLibro, StanzaD),
vai(StanzaD,StanzaC),
lascia(OggettoLibro, StanzaC),
vai(StanzaC,StanzaB)

3.2.3 Ricerca nello spazio dei piani

I pianificatori non lineari sono algoritmi di ricerca che gestiscono la generazione di un piano come un problema di ricerca nello spazio dei piani e non più degli stati.

L'algoritmo non genera più il piano come una successione lineare (completamente ordinata) di azioni per raggiungere i vari obiettivi, ma costruisce un piano parziale 'iniziale' e attraverso una serie di operazioni su di esso lo espande fino a giungere ad un piano completo che risolve il problema.

Definiamo le operazioni sul piano introducendo 2 operatori:

• Operatore di Raffinamento: prende un piano parziale e vi aggiunge dei vincoli. gli operatori di raffinamento eliminano alcuni piani da questo insieme ma non aggiungono mai nuovi piani.
• Operatore di Modifica: in questa categoria rientrano tutti gli operatori che non sono di raffinamento. Alcuni pianificatori costruiscono dei piani scorretti, che poi correggono mediante l'applicazione di operazioni di modifica

Nell'albero di ricerca ogni nodo rappresenta un piano parziale e ogni arco un'operazione di raffinamento del piano.

Un pianificatore non lineare generativo assume che lo stato iniziale è completamente noto (Close World Assumption: tutto ciò che non è dichiarato nella rappresentazione dello stato iniziale è falso)

Per ridurre il backtracking viene adoperata la tecnica del Least Commitment sugli ordinamenti; infatti non imporre mai più vincoli di quelli strettamente necessari cioè non fare scelte quando non sono imposte evita molti backtracking.

Un piano non lineare è rappresentato come:

• un insieme di azioni (istanze di operatori)
• un insieme (non completo) di ordinamenti fra le varie azioni
• un insieme di 'casual link' o relazioni causali.

Una relazione causale (c,Si,Sj) è una terna costituita da due operatori Si, Sj e un sottoobiettivo c tali che uno degli effetti di Si soddisfa la precondizione c di Sj.

Essa puo' anche essere indicata dalla scrittura: Si->Sj e si legge: 'Si' raggiunge c per 'Sj'

In altre parole tali relazioni servono a momorizzare gli obiettivi dei singoli passi nel piano, cosi' da affrontare in modo efficiente il problema delle interazioni fra 'obiettivo'.

L'ordinamento fra le varie azioni e' espresso invece dall'operatore "<" di solito con la scrittura: Si<Sj si intende che il passo "Si" deve verificarsi prima del passo "Sj".

Il Piano iniziale e' costituito da due azioni: start: senza precondizioni, con effetti una descrizione completa dello stato iniziale stop: con precondizione l'obiettivo del planner

con start < stop

Ad ogni passo si incrementano l'insieme degli operatori, degli ordinamenti parziali (non vengono imposti ordinamenti non richiesti) e dei casual link fino a che tutti i obiettivo sono risolti.

Una soluzione è un insieme di operatori parzialmente specificato e parzialmente ordinato.

Per ottenere un piano effettivo si converte l'ordine parziale in uno tra i diversi ordini totali possibili (operazione di Linearizzazione)

Sebbene sia piu' semplice verificare la validita' di un piano completamente istanziato e totalmente ordinato, generalmente e' preferibile lavorare con piani parzialmente ordinati.

ci sono almeno 3 buone ragioni per farlo, in primo luogo e' piu' naturale che il pianificatore restituisca un piano ordinato parzialmente piuttosto che scegliere arbitrariamente una delle sue tante linearizzazioni; in secondo luogo alcuni agenti sono capaci di compiere azioni in parallelo, infine quando si creano piani che possono successivamente essere combinati con altri piani per risolvere problemi piu' grandi, e' vantaggioso mantenere la flessibilita' permessa dall'ordinamento parziale delle azioni.

3.2.4 Minacce

Le Violazioni ai vincoli causali si dicono 'minacce' si dice che un'azione S3 rappresenta una minaccia ("threat") per un casual link (S1,S2,c) quando contiene un effetto che nega il sottoobiettivo "c" e non c'e' nessun vincolo di ordinamento che impedisce a S3 di essere eseguita dopo di S1 e prima di S2.

Possibili soluzioni

Demotion: si impone il vincolo di ordine S3 <S1

Promotion: si impone il vincolo di ordine S2<<S3

Modal Truth Criterion (MTC)

I due metodi promotion e demotion da soli non bastano a garantire la soluzione di un qualunque problema risolubile di pianificazione non lineare (completezza del pianificatore).

Il Modal Truth Criterion rappresenta un procedimento di costruzione del piano che garantisce la completezza del pianificatore.

Un algoritmo di Partial Order Planning alterna passi di soddisfacimento di precondizioni con passi di risoluzione di minacce.

MTC fornisce 5 metodi di correzione del piano (1 per il soddisfacimento delle precondizioni e 4 per la risoluzione delle minacce) sufficienti a garantire la completezza del pianificatore.

1. establishment: soddisfacimento di una precondizione per mezzo di:

- 818g68i 818g68i inserimento di una nuova azione, di un vincolo di ordinamento con un'azione già nel piano o semplicemente di un assegnamento di variabili.

2. promotion: vincolare una mossa a precederne un'altra nel piano finale;

3. demotion: vincolare una mossa a seguirne un'altra nel piano finale;

4. scopertura: inserire un operatore S2 nuovo o già nel piano (detto white knight) fra due mosse

vecchie S1 ed S3 tale che i suoi effetti contengano la precondizione di S3 minacciata da S1.

5. separazione: inserire vincoli di non codesignazione fra le variabili dell'effetto negativo e della precondizione minacciata in modo da prevenire la possibile unificazione. Possibile quando queste variabili non sono ancora state istanziate.

È' preferibile applicare la promozione prima della scopertura (con aggiunta di nuove azioni).

3.2.5 POP: Partial Order Planner

Questo pianificatore parte da un piano parziale minimo e lo estende mediante passi che generano relazioni causali e precondizioni tramite operatori selezionati da un insieme di operatori e di passi esistenti.

Precisamente l'algoritmo di pianificazione, inizia con un piano formato da una operazione iniziale che ha come effetto lo stato iniziale del mondo e una operazione finale che ha come precondizione l'obiettivo del piano e cerca progressivamente di estenderlo inserendo all'interno altre operazioni che rendano il piano via via più completo e consistente fino ad arrivare ad una soluzione.

Se si giunge ad un piano inconsistente, si fa ricorso al backtracking provando in altro ramo dello spazio di ricerca.

Per focalizzare la ricerca, il pianificatore prende in considerazione solo passi aggiuntivi che servono a raggiungere una precondizione che non sia ancora stata raggiunta.

Le relazioni casuali vengono usate per tenere conto di questo.

Purtroppo questi pianificatori possono generare piani molto inefficienti anche se corretti, perché ognuno dei passi di selezione non è deterministico e quindi come abbiamo visto in caso di fallimento si può avere backtracking, ed inoltre perché la pianificazione è semi-decidibile: se esiste un piano che risolve un problema il pianificatore lo trova, ma se non esiste, il pianificatore può lavorare indefinitivamente.

All'aumento della complessità diventa difficile pensare ad un pianificatore corretto e completo, efficiente ed indipendente dal dominio: occorrono metodi ad hoc.

In conclusione quindi algoritmi di pianificazione semplici come questo possono risolvere solo problemi relativamente semplici.

Esempio: Algoritmo POP

Ritornando a "Shakey" e all'esempio visto precedentemente il piano iniziale potrebbe essere:

Operazione(AZIONE: Inizio(),
EFFETTI: Posizione(Shakey, StanzaA), Posizione(OggettoLibro, StanzaD))

Operazione(AZIONE: Fine(),
PRECONDIZIONI: Posizione(Shakey, StanzaB), Posizione(OggettoLibro, StanzaC))

L'algoritmo procede cercando di inserire delle azioni che siano in grado di rendere verificate le precondizioni insoddisfatte. Ad es., l'algoritmo può decidere di inserire tra le azioni Inizio() e Fine() l'azione Lascia(OggettoLibro, StanzaC) allo scopo di rendere vera la precondizione Posizione (OggettoLibro, StanzaC).

Naturalmente l'aggiunta di questa azione nel piano può implicare che nuove condizioni debbano essere verificate (in particolare Shakey deve trovarsi nella stanza C prima che tale azione venga eseguita).

Come abbiamo detto un piano parziale come questo può essere elaborato seguendo diverse strade alternative alcune delle quali possono rivelarsi dei vicoli ciechi. In questo caso l'algoritmo di pianificazione deve tornare indietro e provare un'altra strada.

Si noti come la possibilità di inserire nuove azioni dove è necessario senza alcun vincolo, a differenza del problem solving, può ridurre significativamente lo spazio della ricerca. Nel caso illustrato sopra, ad es., non è necessario prendere in considerazione tutte le possibili azioni che potrebbero essere svolte da Shakey a partire dallo stato iniziale. Shakey può decidere di lasciare l'oggetto "Libro" nella stanza A prima di decidere come arrivarci e come prendere l'oggetto.

Il pianificatore termina quando ha raggiunto tutte le precondizioni di tutti i passi ed ha quindi una soluzione.

Lo schema generico seguito da un algoritmo di tipo POP è quindi il seguente:

While (piano non terminato) do

seleziona una azione SN del piano che ha una precondizione C non soddisfatta;

seleziona una azione S (nuova o già nel piano) che abbia C tra i suoi effetti;

aggiungi il vincolo di ordine S < SN;

­se (S è nuova) aggiungi il vincolo d'ordine Start<Stop;

­ aggiungi il casual link <S, SN, C<;

­risolvi eventuali violazioni a casual links

end

3.2.6 Conclusioni

Per affrontare problemi più complessi è necessario utilizzare algoritmi di ricerca mirati e linguaggi di rappresentazione più potenti (Russell e Norvig, 1995). Per quanto riguarda il problema del linguaggio di rappresentazione, sono stati elaborati formalismi più complessi che permettono di: specificare piani a diversi livelli di descrizione (un livello alto in cui vengono indicate una sequenza di macro-azioni e uno o più livelli più bassi in cui ciascuna macro- azione viene tradotta in una sequenza di azioni più semplici;

gestire il tempo (ad es. gestire il fatto che ciascuna azione ha una durata o che alcune azioni devono essere svolte entro un certo tempo limite);

tenere conto di limiti di gestione (ad es. il fatto che ci possono essere dei limiti sul numero e il tipo di attività che si possono svolgere in contemporanea).

La pianificazione è stata utilizzata con successo in diverse aree come ad es. nella pianificazione di missioni spaziali. Tuttavia in altre aree, per es. il controllo di robot mobili come Shakey, ha prodotto risultati deludenti.

Ciò è dovuto ad una serie di ragioni:

- 818g68i 818g68i Come abbiamo detto all'inizio il pianificatore non si occupa direttamente di come lo stato attuale del mondo gli venga fornito in input e di come il piano prodotto venga effettivamente tradotto in pratica (queste due funzioni devono essere svolte dal sistema percettivo e motorio rispettivamente). Inoltre, abbiamo visto che il pianificazione si aspetta di ricevere in ingresso e produce in uscita delle rappresentazioni di tipo simbolico. Purtroppo estrarre dal mondo attraverso dei sensori fisici una descrizione simbolica dell'ambiente esterno è tutt'altro che ovvio e può rivelarsi una impresa impossibile se ci si aspetta una rappresentazione esatta e completa dell'ambiente esterno. Ciò è dovuto ad una serie di difficoltà: i sensori sono in grado di misurare informazioni quantitative non simboliche, i valori misurati dai sensori sono una indicazione molto indiretta e rumorosa delle quantità misurate, il mondo reale è pieno di ambiguità e spesso in continuo cambiamento, le informazioni estratti dai sensori sono di tipo egocentrico mentre il pianificatore si aspetta una rappresentazione di tipo allocentrico. Dal punto di vista motorio i problemi sono simili. Quando le informazioni fornite in ingresso sono incomplete, rumorose, e parzialmente errate non c'è alcuna garanzia che il piano sviluppato dal pianificatore sulla base di esse sia efficace e, nella misura in cui il sistema percettivo e motorio risultano delle scatole nere inaccessibili al pianificatore, risulta estremamente difficile compensare eventuali malfunzionamenti.

- 818g68i 818g68i Il secondo problema riguarda il fatto che se l'ambiente si modifica durante l'esecuzione del piano non c'è alcuna garanzia che il piano possa avere successo visto che il piano viene sviluppato sulla base di una descrizione del mondo valida prima dell'esecuzione del piano stesso. Questo problema è particolarmente presente in ambienti fortemente dinamici come ad es. nel caso di Robocup (Kitano et al., 1998, si veda pure https://www.robocup.org/ ) una competizione tra laboratori di ricerca di tutto il mondo che consiste nello sviluppare squadre di robot calciatori che si fronteggiano in un torneo annuale.

- 818g68i 818g68i Infine il terzo problema consiste nel fatto che operare in un ambiente reale spesso richiede di prendere decisioni in tempi brevi (per es. per evitare un ostacolo un robot mobile può dover modificare la propria traiettoria nel giro di poche decine o centinaia di millisecondi. Un tempo che può essere troppo breve per un pianificatore nonostante le attuale potenze di calcolo dei computer).

La ricerca attuale, in particolare nell'ambito della robotica, è proprio incentrata nel tentativo di sviluppare nuove architetture e tecniche di pianificazione (anche basate su formalismi diversi come le reti neurali e i sistemi fuzzy) che possano rispondere in modo più efficace a questi problemi.

Alcune linee di ricerca inoltre stanno esplorando la possibilità di sviluppare sistemi ibridi che includono, oltre ad un sistema di pianificazione, un sistema reattivo basato sulle tecniche che descriveremo nella sezioni seguenti.

3.3 PIANIFICAZIONE GERARCHICA

Il difetto principale dei pianificatori visti fino ad ora è quello di considerare gli obiettivi da raggiungere tutti di pari complessità e di pari importanza. Infatti i pianificatori lineari non fanno distinzioni tra obiettivi che risultano critici per risolvere il problema e obiettivi che riguardano solo aspetti di dettaglio e che possono, quindi, venir eventualmente differiti finché non siano stati raggiunti gli obiettivi più importanti. Quindi i pianificatori potrebbero perder tempo inutile per risolvere problemi irrilevanti.

Queste osservazioni sono alla base dell'approccio gerarchico della pianificazione. Il modo più semplice per realizzare tale metodo consiste nel classificare per ogni azione una gerarchia di precondizioni, in cui le precondizioni a livello più basso sono quelle di minore importanza che verranno risolte solo in un secondo momento dopo aver prima risolto le precondizioni che vengono classificate come più cruciali. Quindi la costruzione del piano procede per stadi, cioè si risolvono prima le precondizioni di livello più alto che risultano come le più critiche in quanto sono quelle che potrebbero far fallire il nostro piano. Se ad un determinato livello il piano fallisce si ritorna ai livelli superiori e si ripianifica.

Il piano è realizzato in ABSTRIPS, un pianificatore gerarchico che usa la definizione delle azioni di Strips dove in più a ciascuna precondizione di ogni azione è associato un valore di criticità che consiste nella sua difficoltà di raggiungimento e che viene utilizzata per costruire dei piani a diversi livelli di astrazione. Questi indici possono essere assegnati a priori dal costruttore del pianificatore ma si possono anche aggiornare in base all'esperienze che si acquisiscono durante la risoluzione del problema, infatti se una precondizione di livello inferiore fa fallire il nostro piano diverse volte allora si può considerare come più critica di quanto era stata definita prima.

In pratica ABSTRIPS esplora interamente lo spazio di un determinato livello di astrazione prima di

passare ad un livello più dettagliato: ricerca in lunghezza.

Ad ogni livello di astrazione viene generato un piano completo.

Esempi applicativi:

- 818g68i 818g68i costruzione di un palazzo;

- 818g68i 818g68i organizzazione di un viaggio;

- 818g68i 818g68i progetto di un programma top-down;

Costruzione di un palazzo:

Consideriamo il problema di costruire una casa. L'operatore astratto Costruisci(casa) puo' essere decomposto in un piano che consiste nei 4 passi OttieniPermesso, AssumiMuratore, Costruzione e PagaMuratore

I passi di questo piano possono venire a loro volta decomposti in piani ancora piu' specifici. Vediamo una decomposizione del passo Costruzione

- 818g68i 818g68i Metodologia di soluzione:

1. Viene fissato un valore di soglia.

2. Si considerano vere tutte le precondizioni il cui valore di criticità è minore del valore di soglia.

3. Si procede come STRIPS (ad ogni livello possiamo utilizzare un planner diverso, non necessariamente STRIPS) per la ricerca di un piano che soddisfi tutte le precondizioni con valore di criticità superiore o uguale al valore di soglia.

4. Si usa poi lo schema di piano completo così ottenuto come guida e si abbassa il valore di soglia di 1.

5. Si estende il piano con gli operatori che soddisfano le precondizioni. di livello di criticità maggiore o uguale al nuovo valore di soglia.

6. Si abbassa il valore di soglia fino a che si sono considerate tutte le precondizioni delle regole

originarie.

È importante assegnare bene i valori di criticità delle precondizioni!!!

Gli algoritmi di pianificazione gerarchica più diffusi sono:

- 818g68i 818g68i STRIPS-LIKE

- 818g68i 818g68i Partial-Order

Esempio: Algoritmo STRIPS-LIKE

- Stato iniziale:

clear(b)

c

clear(c)

on(c,a)

a

b

handempty

ontable(a)

ontable(b)

	a

c

- Obiettivo:

	b

on(c,b) ^ on(a,c)

Specifichiamo una gerarchia di obiettivi e precondizioni assegnando dei valori di criticità (che riflettono il grado di difficoltà nel soddisfarli):

on (3)

ontable, clear, holding (2)

handempty (1)

Utilizziamo le regole STRIPS:

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)

- Al primo livello di astrazione si considerano solo le precondizioni con valore di criticità 3 e si ottiene il seguente stack obiettivo:

on(c,b)

on(a,c)

on(c.b) ^ on(a,c)

- L'azione stack(c,b) viene aggiunta al piano per soddisfare on(c,b).

- Visto che le sue precondizioni hanno tutte valore di criticità minore di 3 vengono considerate soddisfatte.

Per cui viene generato una nuova descrizione di stato simulando l'azione stack(c,b).

state description stack obiettivo

clear(b)

clear(c) on(a,c)

ontable(a) on(c,b) ^ on(a,c)

ontable(b)

on(c,b)

handempty

on(c,a)

Nota: nella descrizione dello stato vengono aggiunti o cancellati solo i letterali delle ADD e DELETE list con valore di criticità maggiore o uguale a 3. Ci possono quindi essere contraddizioni nella descrizione dello stato ma questo non causa problemi.

- Si aggiunge al piano l'azione stack(a,c) con cui si effettua lo stesso procedimento visto per stack(c,b). Si ottiene il piano completo di livello 1:

1. stack(c,b)

2. stack(a,c)

Passiamo la soluzione al livello 2: si riconsidera la descrizione di stato iniziale e il stack obiettivo di partenza diventa:

holding(c)

clear(b)

holding(c) ^ clear(b)

stack(c,b)

holding(a)

clear(c)

holding(a) ^ clear(c)

stack(a,c)

on(c,b) ^ on(a,c)

- la condizione holding(c) è soddisfacibile con un' azione unstack(c,X) per cui lo stack diventa clear(c)

on(c,X)

unstack(c,X)

clear(b)

holding(c) ^ clear(b)

stack(c,b)

holding(a)

clear(c)

holding(a) ^ clear(c)

stack(a,c)

on(c,b) ^ on(a,c)

- le precondizioni di unstack(c,X) da considerare a livello 2 (clear(c) e on(c,X)) sono tutte soddisfatte nello stato iniziale con la sostituzione X/a.

Simulando l'azione unstack(c,a) si ottiene:

state description stack obiettivo

clear(b) clear(b)

clear(a) holding(c) ^ clear(b)

ontable(a) stack(c,b)

ontable(b) holding(a)

handempty clear(c)

holding(c) holding(a) clear(c)

stack(a,c)

on(c,b) ^ on(a,c)

E così via fino ad ottenere il piano completo:

1. unstack(c,a)

2. stack(c,b)

3. pickup(a)

4. stack(a,c)

- A livello 3 abbiamo il seguente stack obiettivo:

handempty ^ clear(c) ^ on(c,a)

unstack(c,a)

holding(c) ^ clear(b)

stack(c,b)

handempty ^ clear(a) ^ ontable(a)

pickup(a)

holding(a) ^ clear(c)

stack(a,c)

on(c,b) ^ on(a,c)

Tutte le precondizioni sono già state soddisfatte ai livelli di astrazione precedenti a parte handempty. La ricerca di una soluzione a livello 3 in questo caso risulta semplicemente una verifica della soluzione trovata a livello 2 che risulta essere corretta anche a livello 3.

Nota: A livello 1 sarebbe stato altrettanto valido il piano

1. stack(a,c)

2. stack(c,b)

che si sarebbe ottenuto considerando i due obiettivi in ordine inverso. Ma ai livelli più bassi questo piano sarebbe fallito causando backtracking.

A livello 2 lo stack obiettivo iniziale

holding(a) ^ clear(c)

stack(a,c)

holding(c) ^ clear(b)

stack(c,b)

on(c,b) ^ on(a,c)

avrebbe portato ad una soluzione tipo:

unstack(c,a)

pickup(a)

putdown(c)

stack(a,c)

unstack(a,c)

pickup(c)

stack(c,b)

dove pero' la descrizione di stato finale derivante dalla simulazione delle azioni del piano non soddisfa la congiunzione di goal on(c,b) ^ on(a,c). Occorre cercare una soluzione diversa a livello 1.

Pianificazione Gerarchica con Operatori Macro

Due tipologie di operatori:

- operatori atomici

- operatori macro.

- Gli operatori atomici rappresentano azioni elementari tipicamente definite come regole STRIPS.

- Gli operatori macro a loro volta rappresentano una sequenza di azioni elementari: sono decomponibili in operatori "atomici". La loro decomposizione può essere precompilata o da pianificare.

1. Nel primo caso la descrizione dei macro operatori contiene anche la DECOMPOSITION che rappresenta la sequenza di operatori base in cui viene espanso l'operatore macro in questione durante la sua esecuzione.

Azione: Cook(X)

Precondizioni:have(X), have(pot), have(salt), in(water,pot)

S2

S1    S4

S3