1
PRIMITIVE DEI ROBOT
Percepire
Pianificare
Agire
IL PARADIGMA GERARCHICO
modello
piano
percezioni
azioni
mondo
2
Il paradigma gerarchico è storicamente il primo metodo utilizzato per la
progettazione di robot.
E’ stato utilizzato 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 robotico è definito dalle relazioni tra tre primitive (P-P-A)
PERCEZIONE 
PIANIFICAZIONE 
AZIONE
e cioè dalla maniera in cui i dati percepiti dai sensori sono elaborati e
trasmessi lungo il sistema robotico.
PRIMITIVE
Percezione
INPUT
Dati sensoriali
OUTPUT
Informazioni percepite
Pianificazione
Informazioni percepite
o cognitive
Direttive
Direttive
Azione
Comandi agli attuatori
3
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 seguendo la prima direttiva.
Dopo aver concluso il primo ciclo PPA, il robot riapre gli occhi,
percepisce le conseguenze della sua azione, ripianifica e agisce di nuovo
(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 è immerso
b - informazioni sensoriali (mi trovo in questo punto della stanza)
c - ogni ulteriore informazione di tipo cognitivo (es. il goal che deve
perseguire)
4
Modello del mondo
Contiene
•informazioni a priori (es. mappa dei luoghi)
•informazioni sensoriali
•conoscenza addizionale
Conoscenza transitoria
Puramente reattiva
Istantanea
Conoscenza persistente
Mappa acquisita
sensorialmente
Mappa
a priori
Memoria a breve
termine
Memoria a lungo
termine
Asse temporale
5
FRAME PROBLEM
• ipotesi di mondo chiuso (closed world)
il mondo contiene tutto quello di cui ha bisogno il robot
• frame problem
come 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
3
6
2
5
1
4
Lo stato del mondo
cubo(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 meta
azer (avvio)
esegui(azione)
mostra(stato del mondo)
Le azioni elementari
sposta (X,Y)
sopra(X,Y)
sgombra(X)
verifica(X,Y)
8
Lo stato del mondo
cubo(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 elementari
sposta (X,Y)
sgombra(X,Y)
verifica(X,Y)
Le azioni meta
azer (avvio)
esegui(azione)
mostra(stato del mondo)
3
2
1
6
5
4
verifica(X,Y)  sposta (X,Y)  esegui(sposta (X,Y) )
sgombra(X)  sgombra(Y)  ritratta(sopra(X,_))  asserisci(sopra(X,Y) )sposta (X,Y)
9
IL MONDO DEI CUBI
Azione: sposta il cubo 1 sul cubo 4
2
3
3
6
2
15
1
4
6
5
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):- !.
Qualunque cosa sia sopra X lo sposto a10terra
sgombra(X):- sopra(Y,X),!,sposta(Y,0).
sgombra(X).
cubo(0).
cubo(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).
stampa([]):- nl.
stampa([T|C]):- write(T),stampa(C).
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.
sgombra(0):- !.
sposta(X,Y):- sopra(X,Y),!,stampa([' gia ci sta ']),nl.
sgombra(X):- sopra(Y,X),!,sposta(Y,0).
sposta(X,Y):- sgombra(X),sgombra(Y),
sgombra(X).
retract(sopra(X,_)),!,
verifica(X,Y):- cubo(X),cubo(Y).
assert(sopra(X,Y)),
write(' ho spostato '),write(X),write(' su '),write(Y),nl.
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, quindi controlla se è pieno in tal caso 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 (percepts) 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.
N
. .|.
.
0,2
1,2
2,2
0,1
1,1
2,1
0,0
1,0
2,0
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(0,0,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.
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 spazzino
verso(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.
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.
16
Strips è 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.
Vediamo con qualche esempio come questo accade.
17
General Problem Solver
GPS
Newell & Simon 1972
Divide-and-conquer
usa sottopiani per raggiungere sub-gol che permettono il
raggiungimento del goal finale
Means-end analysis
cerca gli operatori significativi
18
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
differenza
nessuna
differenza
Sub-goal
elimina
la differenza
successo
fallimento
2 - Elimina la differenza
fallimento
successo
Cerca un operatore
per eliminare la
differenza
Non trovato
fallimento
trovato
Confronta le
differenza
condizioni
dell’operatore con lo
stato corrente
Sub-goal
elimina
la differenza
Nessuna differenza
Applica operatore
19
Supponiamo di provare a programmare un robot che vuole 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.
20
Distanze
Operatore
Precondizioni
d>=200
Aereo
All’aereoporto
100<d<200
Treno
Alla stazione
d<=100
Auto
d<1
A piedi
Aggiunte
Cancellazioni
A casa
A casa
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 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.
21 In
questa maniera quando un robot applica un operatore può facilmente modificare il suo mondo
Operatore
Precondizioni
Aggiunte
Cancellazioni
d>=200
Aereo
All’aereoporto
Sono a Y
Non sono a X
100<d<200
Treno
Alla stazione
Sono a Y
Non sono a X
d<=100
Auto
All’aereoporto
o alla stazione
Non sono a c
d<1
A piedi
Alla stazione
Non sono a c
Differenza
A casa
A casa
c
X
Y
h
22
STRIPS & SHANKEY
23
Supponiamo di avere un robot ET che si trova in una stanza R1 e deve
andare nella stanza R2 e prendere 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.
R1
R2
ET
D1
B1
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 tipo24room
Con questi predicati che descrivono il mondo, in maniera a priori noi
inizializziamo Strips (il pianificatore) come segue:
Initial state
INROOM(ET,R1)
INROOM(B1,R2)
CONNECT(D1,R1,R2)
CONNECT(D1,R2,R1)
STATUS(D1, OPEN)
R1
R2
ET
D1
B1
Si noti che per ora il predicato NEXTTO(x,t) 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. 25
La tabella del nostro esempio è la seguente:
Difference
NEXTO(ET,D1)=
TRUE
INROOM(ET,R2)=
FALSE
Operator
Preconditions
OP1:
GOTODOOR( ET,dx)
Add-list
Delete-list
INROOM(ET,rk)
NEXTO(ET,dx)
CONNECT( dx,rk,rm)
OP2:
CONNECT( dx,rk,rm) INROOM(ET,rm) INROOM(ET,rk)
GOTHRUDOOR( ET,dx) NEXTO(ET,dx)
STATUS( dx, OPEN)
INROOM(ET,rk)
R1
R2
ET
D1
B1
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
26
FALSE deve diventare TRUE.
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:
R1
R2
ET
D1
CONNECT(dx,rk,rm)
NEXTO(ET,dx)
B1
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
variabile istanziate si verifica se i predicati appartengono al closed world.
Nel verificare NEXTO(ET,dx) ci si accorge che NEXTO(ET,D1) non appartiene27al data
base.
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
R1
R2
ET
INROOM(ET,rk)
CONNECT(dx,rk,rm)
D1
B1
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.
28
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)
R1
R2
ET
D1
B1
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.
29
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)
R1
R2
ET
D1
B1
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!).
30
Difference
NEXTO(ET,D1)=
TRUE
INROOM(ET,R2)=
FALSE
Operator
OP1:
GOTODOOR( ET,dx)
Preconditions
Add-list
Delete-list
INROOM(ET,rk)
NEXTO(ET,dx)
CONNECT( dx,rk,rm)
OP2:
CONNECT( dx,rk,rm) INROOM(ET,rm) INROOM(ET,rk)
GOTHRUDOOR( ET,dx) NEXTO(ET,dx)
STATUS( dx, OPEN)
INROOM(ET,rk)
31
OPERATORE1-OP1
Goal da perseguire G0
RICAPITOLANDO
INROOM(ET,R2)
INROOM(B1,R2)
CONNECT(D1,R1,R2)
CONNECT(D1,R2,R1)
STATUS(D1, OPEN)
OPERATORE2-OP2
GOTODOOR(S,dx)
Precondizioni
•INROOM(S,rk)
•CONNECT(dx,rk,rm)
Add-list
•NEXTTO(S,dx)
Delete-list
GOTHRUDOOR(S,dx)
Precondizioni
•CONNECT(dx,rk,rm)
•NEXTTO(S,dx)
•STATUS(dx, OPEN)
•INROOM(S,rk)
Add-list
•INROOM(S,rm)
Delete-list
•INROOM(S,rk)
32
PIANIFICAZIONE
Difference
NEXTO(ET,D1)=
TRUE
INROOM(ET,R2)=
FALSE
Operator
OP1:
GOTODOOR( ET,dx)
Preconditions
Add-list
Delete-list
INROOM(ET,rk)
NEXTO(ET,dx)
CONNECT( dx,rk,rm)
OP2:
CONNECT( dx,rk,rm) INROOM(ET,rm) INROOM(ET,rk)
GOTHRUDOOR( ET,dx) NEXTO(ET,dx)
STATUS( dx, OPEN)
INROOM(ET,rk)
Differenza(startstate, goalstate)
- INROOM(S,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(S,D1) è FALSE
33
RICORSIONE
•Crea un nuovo sub-goal G1:NEXTTO(S,D1)
•Push G0 nello stack dei goal
•Controlla e confronta la Add-list con G1
•Op1: NEXTTO(S,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
34
MODELLO DEL MONDO
dopo 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 fatto
Considera G0
Op2 è un operatore ancora valido
Verifica le precondizioni di OP2
Applica OP2
Aggiorna il modello del mondo
Elimina G0 dallo stack
Se lo stack dei goal è vuoto manda il piano a Shakey
G1
G0
35
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(y)
r
b
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)
x
y
36
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.
37
Per lavorare con STRIPS il progettista deve produrre:

una rappresentazione del mondo;

un 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 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;
4.
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
38
ricorsivo.
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.
39
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.
40
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.
41
ESERCIZIO
Scrivere e commentare in 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.
Suggerimento
Goal 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
Start State
A
B
Goal State
42
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.
43
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
44
interviene per decidere cosa fare.
World model
PLAN
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 ET2 e dove il goal B1.
Navigator. A partire dalla localizzazione di ET2 e B1 determina un percorso dalla
postazione di ET2 a B1.
Pilot. Riceve il percorso da Navigator. Prende il primo segmento retto o pezzo
di
45
percorso e determina quali azioni ET deve fare per seguire quel percorso.
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.
Il World Model è aggiornato. Però non
si ripete il ciclo precedente, perché ora
ET2 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 ET2 e se per caso non ci sono ostacoli. Se il Pilot verifica che ha
raggiunto l’estremità del segmento di cammino assegnatoli dal
Navigator informa quest’ultimo e riceve il nuovo segmento da seguire.
Se ha raggiunto il goal allora il Navigator informa il Mission planner
46
che decide cosa fare (fermare il tutto, programmare un nuovo goal, etc.)
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.
47
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 nel senso temporale 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 questo fa lo stesso 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.
48
NHC è stato fondamentalmente testato solo in simulazione.
ARCHITETTURE
RCS & NASREM
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.
PLAN
SENSE
Value judgment
changes and events
Sensory
perception
Task goals
Simulated plans
World modelling
Perception,
focus of attention
Plans, state of
actions
Behavior
generation
Knowledge base
ACT
observed input
Commanded
actions 49
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 module 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.
50
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 timeexpensive. In realtà in queste architetture i moduli SENSE e ACT sono
sempre disconnessi impedendo così una immediata reazione ad un
evento pericoloso.
51
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 tele guidare le braccia di un
robot nello spazio, che è ancora oggi utilizzata.
52
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?), dovuta all’imprecisione
dei sensori e degli attuatori.
Inoltre non è sempre chiaro quando è che si può considerare completata
l’azione del robot e come questo si può rilevare.
53
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).
54
Le architetture NHC e RCS/NASREM sono ragionevoli per sistemi
semi-autonomi dove:
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.
55
56
57
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.
58
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).
59
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.
60
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.
61
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.
62