1

2

PRIMITIVE DEI ROBOT

PercepirePianificare

Agire

IL PARADIGMA GERARCHICO

modello

piano

percezioni azioni

mondo

3

Il paradigma gerarchico è storicamente il primo metodo utilizzato per la progettazione di robot.E’ stato introdotto a partire dal 1967 con il primo robot Shakey allo SRI ed è stato utilizzato fino alla fine degli anni ’80 con l’avvento del paradigma reattivo.

Un paradigma gerarchico è definito dalle relazioni tra tre primitive (P-P-A) in inglese (S-P-A) sensing-planning-acting

PERCEZIONE PIANIFICAZIONE AZIONE

e cioè dalla maniera in cui i dati percepiti dai sensori sono elaborati e trasmessi lungo il sistema robotico. PRIMITIVE INPUT OUTPUT

Percezione Dati sensoriali Informazioni percepite

Pianificazione Informazioni percepitee/o cognitive

Direttive

Azione Direttive Comandi agli attuatori

4

Il robot in maniera sequenziale percepisce con i sensori l’ambiente in cui è immerso e se ne costruisce una mappa. Dopo, “ad occhi chiusi”, pianifica tutte le direttive che deve dare agli attuatori per raggiungere il suo goal. Infine opera iniziando dalla prima direttiva. Dopo aver concluso il primo ciclo S-P-A, il robot riapre gli occhi, percepisce le conseguenze della sua azione, ripianifica e agisce di nuovo (eventualmente anche senza far nulla).Tutte le informazioni fornite dai sensori vengono messe in una struttura dati a cui accede il pianificatore. Questa struttura dati è anche detta modello del mondo del robot.In questa struttura dati, nel paradigma gerarchico, sono contenuti:a - una rappresentazione a priori del mondo in cui il robot è immersob - informazioni sensoriali (mi trovo in questo punto della stanza)c - ogni ulteriore informazione di tipo cognitivo (es. il goal che deve

perseguire)

5

FRAME PROBLEM

• ipotesi di mondo chiuso (closed world)il mondo contiene tutto quello di cui ha bisogno il robot

• frame problemcome mantenere il modello del mondo aggiornato e consistente in una maniera che sia computazionalmente trattattabile

6

Una soluzione di un problema di pianificazione deve avere le seguenti proprietà:

•essere efficace, cioè garantire il raggiungimento dell’obiettivo

•essere completa, cioè le precondizioni necessarie per ogni azione

devono essere verificate e ove necessario attuate attraverso

l’esecuzione delle azioni precedenti

•essere consistente, cioè non ci debbono essere contraddizioni

derivanti dall’ordine di esecuzione delle azioni o dall’istanziazione

delle variabili

7

IL MONDO DEI CUBI

1

2

3

4

5

6

Lo stato del mondocubo(1), cubo(2), cubo(3), cubo(4), cubo(5), cubo(6)sopra(1,0), sopra(2,1), sopra(3,2), sopra(4,0), sopra(5,4), sopra(6,5)

Le azioni metaazer (avvio)esegui(azione)mostra(stato del mondo)

Le azioni elementarisposta (X,Y)sopra(X,Y)sgombra(X)verifica(X,Y)

8

Lo stato del mondocubo(1), cubo(2), cubo(3), cubo(4), cubo(5), cubo(6)sopra(1,0), sopra(2,1), sopra(3,2), sopra(4,0), sopra(5,4), sopra(6,5)

Le azioni metaazer (avvio)esegui(azione)mostra(stato del mondo)

Le azioni elementarisposta (X,Y)sgombra(X,Y)verifica(X,Y)

verifica(X,Y) sposta (X,Y) esegui(sposta (X,Y) )

sgombra(X) sgombra(Y) ritratta(sopra(X,_)) asserisci(sopra(X,Y) )sposta (X,Y)

1

2

3

45

6

9

IL MONDO DEI CUBI

1

2

3

4

5

6

3

2 6

5

1

Azione: sposta il cubo 1 sul cubo 4

azer:- stampa(['Sono pronto. Cosa devo fare ? ']),read(C), esegui(C),azer.

esegui(sposta(X,Y)):- verifica(X,Y),!,sposta(X,Y).

sposta(0,Y):- !,stampa([' tu sei pazzo non si puo fare ']),nl.sposta(X,X):- !,stampa([' tu sei scemo non e possibile']),nl.sposta(X,Y):- sopra(X,Y),!,stampa([' gia ci sta ']),nl.sposta(X,Y):- sgombra(X),sgombra(Y),

retract(sopra(X,_)),!,assert(sopra(X,Y)),write(' ho spostato '),write(X),write(' su '),write(Y),nl.

sgombra(0):- !.sgombra(X):- sopra(Y,X),!,sposta(Y,0).sgombra(X).

Qualunque cosa sia sopra X lo sposto a terra

10

cubo(0).cubo(1).cubo(2).cubo(3).cubo(4).cubo(5).cubo(6).

azer:- stampa(['Sono pronto. Cosa devo fare ? ']),read(C), esegui(C),azer.

esegui(fine):- !,stampa([' Arrivederci ']),fail.esegui(mostrami):- !,mostra.esegui(sposta(X,Y)):- verifica(X,Y),!,sposta(X,Y).esegui(X):- stampa(['ma cosa dici non capisco']),tab(15),write(X),nl.

mostra:- sopra(X,Y),write(X),write(' sta su '),write(Y),nl,fail.mostra:- stampa([' questo e tutto ']),nl.

sposta(0,Y):- !,stampa([' tu sei pazzo non si puo fare ']),nl.sposta(X,X):- !,stampa([' tu sei scemo non e possibile']),nl.sposta(X,Y):- sopra(X,Y),!,stampa([' gia ci sta ']),nl.sposta(X,Y):- sgombra(X),sgombra(Y),

retract(sopra(X,_)),!,assert(sopra(X,Y)),write(' ho spostato '),write(X),write(' su '),write(Y),nl.

sopra(1,0).sopra(2,1).sopra(3,2).sopra(4,0).sopra(5,4).sopra(6,5).

sgombra(0):- !.sgombra(X):- sopra(Y,X),!,sposta(Y,0).sgombra(X).verifica(X,Y):- cubo(X),cubo(Y).

stampa([]):- nl.stampa([T|C]):- write(T),stampa(C).

11

ESERCIZIO Consideriamo un agente spazzino a cui sia stato dato il compito di ripulire un’ambiente e versare la spazzatura nel secchio. Supponiamo che l'ambiente in cui si muove sia una griglia NxN, che inizialmente il robot sia nella casella (0,0), e che se trova la spazzatura la raccoglie, e poi, se ha fatto il pieno, va a versare la spazzatura nel secchio che è in (N,N). Le azioni che l'agente può compiere sono solo quelle di: aspirare la spazzatura se questa si trova nella casella in cui si trova l'agente, avanzare di un passo in una delle quattro possibili direzioni permesse

(N, S, E, W), se ha fatto il pieno portare la spazzatura nel secchio in (N,N) e quindi ricominciare a pulire .Le informazioni (percetti) che l’agente può ricevere sono: c’è lo sporco, c’è il secchio, nessuna informazione. Le azioni che può compiere sono: vai avanti, pulisci, gira, deposita. Il goal è quello di attraversare continuamente la stanza e ripulirla quando trova lo sporco.

0,2 1,2 2,2

0,1 1,1 2,1

0,0 1,0 2,0. ..

|.

N

W E

S

12

Robot spazzino

:- dynamic robot/3, sporco/2.

sporco(5,5).sporco(2,8).sporco(3,7).sporco(7,1).sporco(1,1).sporco(4,9).sporco(9,2).

robot(9,9,0).

cestino(0,0).

vai :- sporco(X,Y), robot(X,Y,0), raccogli, vai.vai :- sporco(X,Y), robot(X1,Y1,0), verso(X,Y), vai.vai :- cestino(X,Y), robot(X,Y,1), svuota, vai.vai :- cestino(X,Y), robot(X1,Y1,1), verso(X,Y), vai.vai.

 

 

 

 

 

 

 

 

 

4

          9

         8

          7

          6

          5

          4

          3

          2

          1

          

9876543210

0

13

Robot spazzino

raccogli :- robot(X,Y,0), retract(sporco(X,Y)), retractall(robot(_,_,_)), write('Immodizia raccolta!'), nl, assert(robot(X,Y,1)).

svuota :- robot(X,Y,1), retractall(robot(_,_,_)), write('Serbatoio svuotato!'), nl, assert(robot(X,Y,0)).

14

Robot spazzinoverso(X,Y) :- robot(X1,Y1,S), Dx is X-X1, Dy is Y-Y1, muoviti(Dx,Dy,DX,DY), retract(robot(X1,Y1,S)), X2 is X1+DX, Y2 is Y1+DY, write('Robot in: '), write(X2), write(', '), write(Y2), nl, assert(robot(X2,Y2,S)).

muoviti(0,Dy,0,DY) :- DY is Dy/abs(Dy). muoviti(Dx,0,DX,0) :- DX is Dx/abs(Dx). muoviti(Dx,Dy,DX,DY) :- DY is Dy/abs(Dy), DX is Dx/abs(Dx).

15

L’elaborazione di tutte queste informazioni può essere dal punto di vista

computazionale molto onerosa.

Suggerimento: usare un albero dove ogni nodo rappresenta la situazione sulle due sponde e ogni arco un operatore che indica quali soggetti sono traghettati.

EsercizioRappresentare e risolvere il problema dei 3 missionari e 3 cannibali

3 missionari e 3 cannibali fanno un viaggio insieme e devono attraversare un fiume sfruttando una zattera che può ospitare al massimo 2 persone. Bisogna fare in maniera che sulle due sponde il numero dei cannibali non superi mai quello dei missionari.

16

CC

MMMCCC/

-C

MMMC/CC

MMMCC/C

1MCMMCCC/M

M

MMCC/MC

-C -MC

MMMCCC/MMCCC/M

-M

MM

MMM/CCC

MMMC/CC

MC/MMCC

MMCC/MC

CC/MMMC

CCC/MMM

C/MMMCC

CC/MMMC

/MMMCCC

CC

-C

-MC

MM

-C

CC

-C

C

-C

MMCCC/M

CMMM

MMMC/CC MMCC/CM MMM/CCC MMC/CMCMCC/MMC

CM

CC

MMMCC/C

CMMM

MMMC/CC MMCC/CM MMM/CCC MMC/CCMMCC/MMC

C MCC

MMMC/CCMMMCC/C MMMCCC/

-C-CC

MCCC/M MMMCCC/

-C -CM-M

-C

-CC

17

PASSO AZIONE RIVA di RIVA di

PARTENZA ARRIVO

1 Situazione iniziale MMMCCC /

2 traghettano 2 cannibali MMMC CC

3 1 cannibale torna indietro MMMCC C

4 traghettano 2 cannibali MMM CCC

5 1 cannibale torna indietro MMMC CC

6 traghettano 2 missionari MC MMCC

7 tornano 1 cannibale e 1 missionario MMCC MC

8 traghettano 2 missionari CC MMMC

9 1 cannibale torna indietro CCC MMM

10 traghettano 2 cannibali C MMMCC

11 1 cannibale torna indietro CC CMMM

12 traghettano 2 cannibali / MMMCCC

18

Per far muovere Shakey (circa 1970) fu necessario utilizzare un

pianificatore derivato da STRIPS che permetteva di dimostrare

teoremi, cioè di operare su, e risolvere, una serie di predicati

attraverso i quali veniva rappresentato il mondo di Shakey.

19

Shakey è il primo robot mobile in AI che ha usato un algoritmo generalizzato per pianificare lo svolgimento dei suoi compiti.

Il metodo applicato era una variante del GPS.

Questo programma usa un approccio detto analisi means-ends dove se il robot non può svolgere un compito o raggiungere il goal in un solo movimento prende in considerazione una azione che possa ridurre la differenza fra lo stato in cui si trova e quello verso cui vuole andare.

20

General Problem SolverGPS

Newell & Simon 1972

Divide-and-conquerusa sottopiani per raggiungere sub-gol che permettono ilraggiungimento del goal finale

Means-end analysiscerca gli operatori significativi

21

Means-end analysis del GPS

1 - Trasforma lo stato corrente in uno stato goal

Confronta lo stato corrente con il goal e trova la differenza

Sub-goalelimina

la differenza

differenza

fallimento

successo

nessuna differenza

2 - Elimina la differenza

Cerca un operatore per eliminare la differenza

Sub-goalelimina

la differenza

trovato

Nessuna differenza

Applica operatore

Non trovatofallimento

Confronta le condizioni

dell’operatore con lo stato corrente

successo

differenza

fallimento

22

Supponiamo di voler programmare un robot che deve andare da Milano a Napoli.

A meno che il robot non sia già nel punto di arrivo, rappresentato come una variabile goal, allora il viaggio deve essere organizzato.

Supponiamo che il robot si trovi a Milano (stato iniziale).

Il robot può rappresentare il processo di decisione di come raggiungere un nuovo luogo con una funzione detta operatore che prende in considerazione ad esempio la distanza fra il punto iniziale e quello finale utilizzando una cosiddetta Tavola delle Differenze.

23

Obiettivo del robot è annullare la differenza, cioè la distanza tra se stesso e Napoli. Se il robot vuole prendere l'aereo bisogna tenere conto che l' aeroporto di Milano è lontano dalla città 50 chilometri. Allora in questo caso il robot ha una nuova differenza da minimizzare. Dalla tavola si ricava che potrebbe andare in auto. La scelta si fa mediante una lista di precondizioni che devono essere soddisfatte prima di eseguire un certo operatore.

Quando il robot prende l’aereo da Milano e giunge a Napoli allora il suo stato cambia. Il suo stato iniziale ora è aeroporto di Napoli e non più quello di Milano. Quindi ogni qualvolta il robot esegue un'operazione vi è quasi sempre qualche cosa che deve essere aggiunta alla sua conoscenza dello stato del mondo. Aggiungiamo allora due colonne nella tabella una per le aggiunte e un'altra per le cancellazioni. In questa maniera quando un robot applica un operatore può facilmente modificare il suo mondo

A piedid<1

Autod<=100

Treno100<d<200

Aereod>=200

OperatoreDistanze

A casa

Precondizioni

All’aereoporto

Alla stazione

Vicino Napoli

CancellazioniAggiunte

24

A piedid<1

Autod<=100

Treno100<d<200

Aereod>=200

OperatoreDifferenza

A casa

Precondizioni

All’aereoporto

Alla stazione

Vicino a Y

X Y

c

h

All’aereoportoo alla stazione

Non sono a XSono a Y

Non sono a XSono a Y

CancellazioniAggiunte

Sono a Y

Non sono a X

Non sono a X

25

STRIPS & SHANKEY

26

Supponiamo di avere un robot ET che si trova in una stanza R1 e deve andare nella stanza R2 dove si trova lo scatolo B1. Le due stanze sono separate da una porta D1.Dobbiamo ora, secondo il paradigma gerarchico, descrivere il mondo del robot. Lo facciamo attraverso dei predicati. Usiamo nella definizione dei predicati, nomi con lettere maiuscole per indicare fatti VERI, e nomi con lettere minuscole per indicare variabili che possono essere VERE o FALSE.Nel mondo del robot ci sono solo tre tipi di cose: movable_object, room, door.

ET

R2R1

B1

D1

La conoscenza può essere così rappresentata:INROOM(x,r) l’oggetto x (di tipo movable_object) si trova

nella stanza r (di tipo room)NEXTTO(x,t) l’oggetto x (di tipo movable_object) si trova

vicino a t che è un tipo door o movable_object

STATUS(d,s) d è di tipo door e s può essere OPEN o CLOSED

CONNECT(d,rx,ry) d è di tipo door e rx,ry sono di tipo room

27

Con questi predicati che descrivono il mondo, in maniera a priori noi inizializziamo Strips (il pianificatore) come segue:

Initial stateINROOM(ET,R1)INROOM(B1,R2)CONNECT(D1,R1,R2)CONNECT(D1,R2,R1)STATUS(D1, OPEN)

Si noti che per ora il predicato NEXTTO(x,y) non è utilizzato perché non c’è nessun oggetto vicino a una porta o ad un altro oggetto. Le sue variabili quindi rimangono non istanziate.Il pianificatore lavora sulla base di una tabella che contiene dei possibili operatori che il robot può applicare, le precondizioni purché siano applicabili, i predicati che si aggiungono o modificano rispetto allo stato iniziale o precedente e quelli che si eliminano perché non più veri.

ET

R2R1

B1

D1

NEXTTO(x,y)

28

La tabella del nostro esempio è la seguente:

Da questa tabella si ha che il robot è programmato per eseguire due sole

operazioni: andare verso una porta, passare attraverso una porta.

Poiché il goal da raggiungere è nella stanza R2 allora la differenza logica

da annullare è il non essere nella stanza R2.

Per annullarla il predicato INROOM(ET,R2) che inizialmente risulta

FALSE deve diventare TRUE.

DifferenceNEXTO(ET,dx)=TRUEINROOM(ET,rm)=FALSE

OperatorOP1:GOTODOOR(ET,dx)

OP2:GOTHRUDOOR( ET,dx)

PreconditionsINROOM(ET,rk)CONNECT(dx,rk,rm)

CONNECT(dx,rk,rm)NEXTO(ET,dx)STATUS(dx, OPEN)INROOM(ET,rk)

Add-listNEXTO(ET,dx)

INROOM(ET,rm)

Delete-list

INROOM(ET,rk)

ET

R2R1

B1

D1

Initial stateINROOM(ET,R1)INROOM(B1,R2)CONNECT(D1,R1,R2)CONNECT(D1,R2,R1)STATUS(D1, OPEN)

,D1)=

,R2)=

29

Se guardiamo tra gli operatori troviamo che l’unico che ha nella sua add-list un predicato

che potrebbe annullare la differenza INROOM(ET,R2)=FALSE, è OP2 con

INROOM(ET,rm). Allora in OP2 istanziamo rm=R2. Le precondizioni che devono essere

soddisfatte affinché OP2 sia applicabile sono:

CONNECT(dx,rk,rm)

NEXTO(ET,dx)

STATUS(dx, OPEN)

INROOM(ET,rk)

Di queste solo CONNECT(dx,rk,rm) contiene rm che quindi sostituiamo con R2. Ora

STRIPS cerca nella base dati se vi sono istanze di CONNECT(dx,rk,R2). L’unica che

trova è CONNECT(D1,R1,R2), (l’altra ha al posto di rm R1). Quindi da qui in poi

STRIPS pone dx=D1, rk=R1, rm=R2.

Con questi valori si va a vedere se le altre precondizioni sono soddisfatte, cioè sostituendo

le variabili istanziate si verifica se i predicati appartengono al closed world.

Nel verificare NEXTO(ET,dx) ci si accorge che NEXTO(ET,D1) non appartiene al data

base.

ET

R2R1

B1

D1

Difference

NEXTO(ET,D1)=

TRUE

INROOM(ET,R2)=

FALSE

Operator

OP1:

GOTODOOR( ET,dx)

OP2:

GOTHRUDOOR( ET,dx)

Preconditions

INROOM(ET,rk)

CONNECT( dx,rk,rm)

CONNECT( dx,rk,rm)

NEXTO(ET,dx)

STATUS( dx, OPEN)

INROOM(ET,rk)

Add-list

NEXTO(ET,dx)

INROOM(ET,rm)

Delete-list

INROOM(ET,rk)

Initial stateINROOM(ET,R1)INROOM(B1,R2)CONNECT(D1,R1,R2)CONNECT(D1,R2,R1)STATUS(D1, OPEN

30

In maniera ricorsiva ora STRIPS si pone NEXTO(ET,D1) come obiettivo da perseguire e quindi come differenza da colmare NEXTO(ET,D1). Pertanto pone nello stack della ricorsione il primo goal, diciamo G0, non ancora soddisfatto, a cui aggiunge il nuovo G1. Cerca ora se tra gli operatori rimasti ce n’è uno nella cui add-list c’è un predicato che annulli la differenza, cioè se c’è NEXTO(ET,D1). Non appena lo trova, nel nostro caso si tratta di OP1, ripete il procedimento di verifica delle precondizioni con il nuovo vincolo di dx=D1.

Le precondizioni sono in questo caso

INROOM(ET,rk)CONNECT(dx,rk,rm)

instanziando rk=R1, e rm=R2 troviamo che nel data base CONNECT(D1,R1,R2) è vera così come INROOM(ET,r1).

A questo punto STRIPS pone OP1 nello stack e prova a risolvere il problema.

ET

R2R1

B1

D1

Difference

NEXTO(ET,D1)=

TRUE

INROOM(ET,R2)=

FALSE

Operator

OP1:

GOTODOOR( ET,dx)

OP2:

GOTHRUDOOR( ET,dx)

Preconditions

INROOM(ET,rk)

CONNECT( dx,rk,rm)

CONNECT( dx,rk,rm)

NEXTO(ET,dx)

STATUS( dx, OPEN)

INROOM(ET,rk)

Add-list

NEXTO(ET,dx)

INROOM(ET,rm)

Delete-list

INROOM(ET,rk)

31

Dopo l’applicazione di OP1 (GOTODOOR(ET,D1)) lo stato del mondo è il seguente:

INROOM(ET,R1)INROOM(B1,R2)CONNECT(D1,R1,R2)CONNECT(D1,R2,R1)STATUS(D1, OPEN)NEXTO(ET,D1)

E il robot si trova vicino alla porta D1.

A questo punto dallo stack emerge OP2 che può essere applicato perché tutte le sue precondizioni sono soddisfatte.

ET

R2R1

B1

D1

32

Dopo l’applicazione di OP2 GOTHRUDOOR(ET,D1) lo stato del mondo è il seguente:

INROOM(ET,R1)INROOM(ET,R2)INROOM(B1,R2)

CONNECT(D1,R1,R2)CONNECT(D1,R2,R1)

STATUS(D1, OPEN)NEXTO(ET,D1)

La differenza prevista per OP2 è ora annullata dato che ora INROOM(ET,R2) è vera e quindi STRIPS si ferma, avendo raggiunto il suo scopo, e l’azione, così come previsto dai due operatori GOTHRUDOOR(ET,D1) e GOTODOOR(ET,D1) può essere eseguita (solo ora!).

ET

R2R1

B1

D1

33

Goal da perseguire G0

INROOM(ET,R2)INROOM(B1,R2)CONNECT(D1,R1,R2)CONNECT(D1,R2,R1)STATUS(D1, OPEN)

OPERATORE1-OP1

GOTODOOR(ET,dx)

Precondizioni•INROOM(ET,rk)•CONNECT(dx,rk,rm)

Add-list•NEXTTO(ET,dx)

Delete-listOPERATORE2-OP2

GOTHRUDOOR(ET,dx)

Precondizioni•CONNECT(dx,rk,rm) •NEXTTO(ET,dx)•STATUS(dx, OPEN)•INROOM(ET,rk)

Add-list•INROOM(ET,rm)

Delete-list•INROOM(ET,rk)

RICAPITOLANDO

34

PIANIFICAZIONE

Differenza(startstate, goalstate)- INROOM(ET,R2) è FALSE

Confronto (Matching)- Confronta la ADD-LIST con la differenza- Op2: IF rm=R2 allora applicando OP2 si potrebbe

eliminare la differenza

Applicazione- Controlla le precondizioni dello stato attuale- CONNECT(D1, R1, R2)

•NEXTTO(ET,D1) è FALSE

DifferenceNEXTO(ET,D1)=TRUEINROOM(ET,R2)=FALSE

OperatorOP1:GOTODOOR(ET,dx)

OP2:GOTHRUDOOR( ET,dx)

PreconditionsINROOM(ET,rk)CONNECT(dx,rk,rm)

CONNECT(dx,rk,rm)NEXTO(ET,dx)STATUS(dx, OPEN)INROOM(ET,rk)

Add-listNEXTO(ET,dx)

INROOM(ET,rm)

Delete-list

INROOM(ET,rk)

35

RICORSIONE

•Crea un nuovo sub-goal G1:NEXTTO(ET,D1)•Push G1 nello stack dei goal•Controlla e confronta la Add-list con G1•Op1: NEXTTO(ET,dx), dx=D1•Riassegna i valori

• es. (dx,rk,rm)=(D1,R1,R2)•Tutte le precondizioni di Op1 sono soddisfatte•Applica OP1 e fai il pop sullo stack G1

G0

36

MODELLO DEL MONDOdopo l’applicazione di OP1

INROOM(ET,R1)INROOM(B1,R1)STATUS(D1, OPEN) CONNECT(D1,R1,R2)CONNECT(D1,R2,R1)NEXTTO(ET,D1)

G1

G0

G1 fattoConsidera G0Op2 è un operatore ancora validoVerifica le precondizioni di OP2Applica OP2Aggiorna il modello del mondoElimina G0 dallo stackSe lo stack dei goal è vuoto STRIPS manda il piano a Shakey

37

STRIPS quindi lavora in maniera ricorsiva. Se non può raggiungere

direttamente un goal identifica il problema che glielo impedisce

nelle precondizioni che falliscono. Si propone queste come sub-goal

e ricomincia. Quando tutti i sub goal sono soddisfatti, fa il pop dello

stack cercando di risalire al goal di partenza.

STRIPS pianifica più che agire, in effetti crea una lista di operatori

che si possono applicare per raggiungere lo scopo.

38

Per lavorare con STRIPS il progettista deve produrre:una rappresentazione del mondo;una tavola delle differenze con operatori, precondizioni, add e delete list;un valutatore delle differenze.

I passi che STRIPS compie sono:

1. calcolo della differenza tra stato iniziale e stato finale (quello del goal) usando la funzione di valutazione delle differenze;

2. se vi è qualche differenza la riduce cercando tra gli operatori il primo che presenta nella ADD-LIST un predicato che neghi la differenza;

3. esamina quindi le precondizioni per vedere se esiste un insieme di possibili instanziazioni per tutte le variabili non instanziate. Se così non è, prende la

4. prima precondizione non verificata, se la propone come nuovo goal e memorizza il goal originale in uno stack. Ricorsivamente quindi riduce la differenza ripetendo i passi precedenti;

5. quando tutte le precondizioni per un operatore sono soddisfatte, inserisce l’operatore nello stack e aggiorna il suo modello del mondo con le nuove asserzioni; passa poi all’operatore che segue nello stack e ripete il procedimento ricorsivo.

39

Closed World Assumption e Frame problem.

L’ipotesi di Closed World impone che il modello del mondo costruito dal progettista contenga tutto quanto serve al robot. Non ci possono essere sorprese. Se questa ipotesi è violata il robot potrebbe non funzionare più bene. Questo è un primo problema.

L’opposto dell’ipotesi di Closed World è detta ipotesi di Open World.

40

Un secondo problema sorge dalla considerazione che solo per due

stanze, nell’esempio fatto, abbiamo scritto molti predicati ai quali se

ne aggiungeranno altri se le stanze sono più di due, se ci sono ostacoli

e così via.

In effetti risulta evidente che il numero di fatti (o assiomi) che il

problema deve maneggiare, ordinandoli e ricercandoli, ad ogni passo

attraverso la tavola delle differenze diventa rapidamente intrattabile,

dal punto di vista computazionale, per applicazioni reali.

Il problema di rappresentare una situazione di un mondo reale in

maniera computazionalmente trattabile è noto come frame problem.

41

Si noti ancora che sotto l’ipotesi di Closed World se qualcosa di nuovo viene introdotto dall’esterno allora bisogna rivedere tutto l’apparato degli assiomi. Con questo e con il problema che lo stack ricorsivo può alla fine andare in overflow si capisce quanto questa via non sia troppo praticabile.

Si cercò negli anni ’80 di affrontare questo aspetto suddividendo il problema in tante parti sempre più astratte.

Di qui emersero due distinte linee di ricerca: una sulla pianificazione e una detta di robotica in cui si studiava prevalentemente la sensoristica.

42

RELAZIONE

Introdurre, scrivere e commentare usando STRIPS un algoritmo che risolva il problema dei cubi:

Dati 5 cubi, collocati o a terra o sovrapposti tra loro produrre un piano che permetta lo spostamento di un qualunque cubo su un qualunque altro spostando gli eventuali ostacoli.

In alternativaIntrodurre, scrivere e commentare usando STRIPS un algoritmo che risolva il problema del robot spazzino come illustrato precedentemente (ricordando la soluzione adottata in Prolog)

• Descrivere in termini GPS la soluzione individuata.

Da consegnare entro 15 giorni da oggiLa valutazione dell’elaborato contribuisce al voto finale

43

Alcune architetture gerarchiche.

Il Nested Hierarchical Controller (NHC) è una delle più note architetture gerarchiche sviluppata da Meystel (1990). In essa le tre componenti SENSE-PLAN-ACT sono ben visibili.

44

Il robot inizia con il raccogliere i dati dai suoi sensori (SENSE) per costruire il suo modello del mondo (World Model/Data Base). Per altro il suo World Model può anche avere una conoscenza a priori fornita dal progettista (ad esempio una mappa dell’ambiente, regole di comportamento, etc.).Aggiornato il World Model con l’attività sensoriale, il modulo PLAN interviene per decidere cosa fare.

45

Questo modulo ha tre sotto moduli ognuno dei quali interagisce con il World Model e con quello che lo precede.Mission planner. Riceve dall’uomo o genera da solo una missione da compiere (esempio prendi lo scatolo nella camera accanto), instanziando una serie di variabili (es. box=B1; rm=R2). Ciò fatto il Mission Planner accede al World Model per determinare dove si trova il robot ET e dove il goal B1.Navigator. A partire dalla localizzazione di ET2 e B1 determina un percorso dalla postazione di ET a B1.Pilot. Riceve il percorso da Navigator. Prende il primo segmento retto o pezzo di percorso e determina quali azioni ET deve fare per seguire quel percorso.

PLAN

Wor

ld m

odel

ET1

B1

46

Cosa accade se il percorso è molto lungo o un ostacolo improvviso si para davanti a ET? Contrariamente a Shakey questo robot non va in giro necessariamente con gli occhi chiusi. Non appena infatti Pilot manda gli opportuni comandi ai controller degli attuatori, ET2 riattiva i suoi sensori.

47

assegnatogli dal Navigator informa quest’ultimo e riceve il nuovo segmento da seguire. Se ha raggiunto il goal allora il Navigator informa il Mission planner che decide cosa fare (fermare il tutto, programmare un nuovo goal, etc.)

Il World Model è aggiornato. Però non si ripete il ciclo precedente, perché ora ET ha il suo goal e il suo percorso. Il Pilot semplicemente, sulla base delle nuove informazioni verifica se e a quale punto del percorso previsto si trova ET e se per caso non ci sono ostacoli. Se il Pilot verifica che ha raggiunto l’estremità del segmento di cammino

48

Se il Pilot trova un ostacolo ne informa il Navigator che gli fornisce un nuovo percorso da seguire per raggiungere il goal. Il tutto avviene con una costante interazione tra i moduli, in maniera gerarchica e con il World Model aggiornato di volta in volta.

49

I vantaggi di NHC consistono nell’alternare pianificazione e azione. L’attività inizia a eseguire una pianificazione. Se il mondo nel frattempo cambia allora anche NHC cambia i suoi piani. Si noti che i tre livelli gerarchici lo sono non solo in termini temporali ma anche dal punto di vista della ”intelligenza”, nel senso che Mission Planner è più intelligente e opera ad un livello più astratto di Navigator e lo stesso avviene rispetto a Pilot. Questa organizzazione la ritroveremo anche in altre architetture.Lo svantaggio dell’architettura NHC è che essa sembra adatta a problemi di navigazione ma meno adeguata per problemi tipo prendi l’oggetto o ruota una manopola e così via.NHC è stato fondamentalmente testato solo in simulazione.

50

Jim Albus (1996) ai fini di applicazioni industriali nell’ambito dei

manipolatori sviluppò un’architettura detta Real-Time Control System

(RCS) per aggiungere, usando la NHC, più intelligenza ai robot

industriali.

ARCHITETTURERCS & NASREM

Sensoryperception

observed input

changes and events

Value judgment

World modelling

Knowledge base

Behavior generation

Perception,focus of attention

Plans, state ofactions

Task goals

Commandedactions

Simulated plans

SENSEPLAN

ACT

51

Le attività percettive sono raggruppate in una serie di moduli denominati Percezione

Sensoriale.

L’output dei sensori è inviato al World Model che costruisce una mappa globale

usando anche le informazioni già presenti nella sua Knowledge Base. Questa

organizzazione è simile a quella del NHC. La principale differenza consiste nel fatto

che il modulo sensoriale effettua un preprocessing delle informazioni percepite

(feature extraction). Queste informazioni vengono elaborate dal Value Judgment

modulo che fornisce la maggior parte delle funzionalità necessarie per l’attività di

PLAN. In altre parole pianifica e simula i piani per assicurarsi che tutto funzioni.

Dopo di che invia i piani al modulo Behavior generation che converte i piani in

azioni che il robot può realmente eseguire (ACT). A questi moduli se ne aggiunge un

altro non mostrato che permette il debug all’osservatore umano.

Sensory perceptionPreprocessing

observed input

changes and events

Value judgment

World modelling

Knowledge base

Behavior generation

Perception,focus of attention

Plans, state ofactions

Task goals

Commandedactions

Simulated plans

SENSE PLAN

ACT

52

Questi tipi di architettura hanno fornito una serie di indicazioni sulla opportunità di introdurre modularità nel progetto di un robot.

Questa modularità però non consente molta portabilità poiché in genere le due architetture prima viste sono state realizzate e, si pensa lo siano sempre, per ristrette nicchie di applicazioni.

NHC è prevalentemente utilizzata per problemi di navigazione mentre RCS è stata utilizzata per controllo di strumentazioni in sottomarini e scavi in miniera. Il vero problema rimane quello del tempo di reazione all’evento quando questo può essere catastrofico. Infatti i moduli di pianificazione, prevedendo una simulazione, sono in genere molto time-expensive. In realtà in queste architetture i moduli SENSE e ACT sono sempre disconnessi impedendo così una immediata reazione ad un evento pericoloso.

53

Questo standard è stato adottato dalla NASA e dal US Bureau of Mines. In fig. ci sono tre differenti robot che hanno adoperato questa architettura.

Queste architetture, NHC e RCS sembrano molto utili per un controllo semiautonomo. L’operatore umano può fornire il world model, decidere la missione, decomporla in piani e quindi in azioni. A livello inferiore il robot esegue le azioni. Ovviamente man mano che si eleva l’intelligenza del robot questo può occuparsi dei moduli di livello superiore al Pilot nella gerarchia prima vista. Sulla base di queste considerazioni Albus ha sviluppato una architettura chiamata NASREM per teleguidare le braccia di un robot nello spazio, che è ancora oggi utilizzata.

54

La dipendenza da un global world model, e cioè del frame problem, fa sì che queste architetture non sono molto generali ma risentono delle applicazioni per le quali sono state pensate.

Altro problema non risolto è quello dell’incertezza che può essere semantica (NEXTTO che significa veramente?) e dovuta all’imprecisione dei sensori e degli attuatori.

Inoltre non è sempre chiaro quando si può considerare completata l’azione del robot e come questo si può rilevare.

55

Dal punto di vista dei linguaggi di programmazione data la presenza della ricorsione e della logica dei predicati STRIPS favorisce linguaggi come il Lisp e il PROLOG.

Il paradigma gerarchico incoraggia una programmazione monolitica piuttosto che una orientata agli oggetti.

Sebbene NHC decomponga la pianificazione in più parti, questa divisione è però strettamente funzionale (di qui l’uso prevalente del Lisp).

56

Le architetture NHC e RCS/NASREM sono ragionevoli per sistemi semi-autonomi dove:

L’operatore umano potrebbe:•Fornire il modello del mondo•Decidere la missione•Decomporre la missione in piani•Decomporre i piani in azioni

Il robot potrebbe:•Eseguire azioni

Far diventare il robot più intelligente significa trasferirgli alcune delle funzioni dell’operatore umano seguendo a salire la gerarchia precedente.

57

58

59

Nel modello gerarchico tipo juke-box, ogni strato è formato da 4 componenti introdotte da Albus: sensory processing, world modelling, task decomposition, value judgement.Tutti gli strati sono connessi tramite una GLOBAL MEMORY attraverso la quale la conoscenza simbolica è messa a disposizione. L’aspetto più significativo introdotto da Albus riguarda la percezione. Essa è utilizzata per stabilire e mantenere relazioni fra la rappresentazione interna contenuta nel world model e il mondo esterno reale. Le azioni sono la conseguenza di ragionamenti fatti sul world model. Quindi la percezione non è direttamente collegata alla azione.

60

A metà degli anni ’80 gli USA adottarono questo modello come standard (NASRAM) riportato in fig.. Ciò nonostante questo standard è adoperato solo nell’ambito della telerobotica nelle stazioni spaziali della NASA (Lumia 1994).

61

I sei livelli di questo sistema catturano ciascuno una specifica funzionalità. Dal basso verso l’alto si ha:SERVO: fornisce posizione, velocità, forza ai servo controlli di tutti

gli attuatori;PRIMITIVE: determina le primitive di moto per generare traiettorie

senza spigoli;ELEMENTAL MOVE: definisce e pianifica percorsi liberi da ostacoli;TASK: converte l’azione desiderata per un singolo oggetto del mondo in una sequenza di movimenti elementari che la realizzano;SERVICE BAY: converte le azioni su gruppi di oggetti in compiti che devono essere eseguti su i singoli oggetti, schedulando questi compiti nell’ambito di questa area;SERVICE MISSION: decompone l’intera missione in parti che colloca nella service bay.

Come si vede i livelli più in alto creano subgoal per i livelli più bassi.

62

Un altro modello inserito in questo filone è stato sviluppato alla Drexel University. Il suo control model possiede le seguenti caratteristiche (v. fig…..).Mette in relazione il team umano con le strutture di controllo del robot;Una gerarchia di decisori implementa questa idea;I sistemi di controllo autonomi sono organizzati come team di decisori;Assume che il task sia decomponibile in sub-task strutturati;Le gerarchie sono generate ricorsivamente usando un controllore generalizzato;Le precondizioni son stabiliti a ogni livello della ricorsione per assicurare una

corretta esecuzione.In fig. è mostrato un sistema di controllo formato da sei livelli.

63

Al Research Polytechnic Institute la gerarchia è stata ristretta a tre livelli primari:ORGANIZATION LEVEL: per la pianificazione ad alto livello e il ragionamento;COORDINATION LEVEL: per la coordinazione tra i vari sotto sistemi hardware;EXECUTION LEVEL: fornisce i controlli di base e l’hardware.Questo approccio implementa il principio dell’aumento della precisione con la diminuizione dell’intelligenza scendendo lungo la gerarchia.Il controllo gerarchico in definitiva sembra buono per ambienti ben noti e altamente prevedibili.

64

65

Modello del mondo

Contiene•informazioni a priori (es. mappa dei luoghi)•informazioni sensoriali•conoscenza addizionale

Conoscenza transitoria

Puramente reattiva

Istantanea

Mappa acquisitasensorialmente

Memoria a brevetermine

Conoscenza persistente

Mappa a priori

Memoria a lungotermine

Asse temporale

66

Esempio di tipi di azioni che Shakey può fare:

Vai da x a y (da un posto ad un altro)GO(y):

PRECOND: Sta_a(Shakey,x)Sta_in(x,r) /\ Sta_in(y,r)Su(Shakey,Terra)

RISULTATO: Sta_a(Shakey,y)

bx

y

Spingere un oggetto mobile b da x a y:PUSH(b,x,y):

PRECOND: Mobile(b)Sta_a(b,x)Sta_a(Shakey,x)Sta_in(x,r) /\ Sta_in(y,r)Su(Shakey,Terra)

RISULTATO: Sta_a(b,y)

r

67

68

C

331/000

-C

311/020

321/010

1MC131/200

M

221/110

-C -1M

321/010231/100

-1MC

331/000

M

301/030

311/020

111/220

221/110

021/310

031/300

011/320

021/310

001/330

C

-C

-1MC

M

-C

C

-C

C

M C 1MC

121/210 301/030 211/120

-C

311/020

MC

1MC

111/220 301/030201/130

-C -1M -1MC

121/210 211/120 221/110

-C -C

311/020 321/010

69

Difference

NEXTO(ET,D1)=

TRUE

INROOM(ET,R2)=

FALSE

Operator

OP1:

GOTODOOR( ET,dx)

OP2:

GOTHRUDOOR( ET,dx)

Preconditions

INROOM(ET,rk)

CONNECT( dx,rk,rm)

CONNECT( dx,rk,rm)

NEXTO(ET,dx)

STATUS( dx, OPEN)

INROOM(ET,rk)

Add-list

NEXTO(ET,dx)

INROOM(ET,rm)

Delete-list

INROOM(ET,rk)

70

DifferenceNEXTO(ET,D1)=TRUEINROOM(ET,R2)=FALSE

OperatorOP1:GOTODOOR(ET,dx)

OP2:GOTHRUDOOR( ET,dx)

PreconditionsINROOM(ET,rk)CONNECT(dx,rk,rm)

CONNECT(dx,rk,rm)NEXTO(ET,dx)STATUS(dx, OPEN)INROOM(ET,rk)

Add-listNEXTO(ET,dx)

INROOM(ET,rm)

Delete-list

INROOM(ET,rk)

71

SuggerimentoGoal State: SU(A,B)Start State: SU(A,Terra); SU(B,Terra); VUOTOSOPRA(A); VUOTOSOPRA(B);Operator:

- MOVE(x,y):Preconditions: SU(x,Terra); VUOTOSOPRA(y);Add-List: SU(x,y)Delete-List: VUOTOSOPRA(y); SU(x,Terra)

A B BA

Start State Goal State