Per far muovere Shankey (circa 1970) fu necessario utilizzare un pianificatore derivato da STRIPS che permetteva di dimostrare teoremi, cioè di risolvere, e operare su una serie di predicati attraverso i quali veniva rappresentato il mondo di Shankey.
Shankey è 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.
Newell & Simon 1972
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
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.
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.
La conoscenza può essere così rappresentata:
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)
NEXTTO(x,y)
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.
Dalla tabella a lato 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.
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.
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.
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.
Dopo l’applicazione di OP2 GOTHRUDOOR(ET,D1) lo stato del mondo è il seguente: (vedi figura).
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!).
Differenza(startstate, goalstate)
Confronto (Matching)
Applicazione
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)
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.
Per lavorare con STRIPS il progettista deve produrre:
I passi che STRIPS compie sono:
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.
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.
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.
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 alternativa
Introdurre, 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.
Descrivere nei dettagli almeno tre veicoli di Braitenberg rappresentandoli con STRIPS e riportando e discutendo le implicazioni psicologiche proposte dallo stesso Braitenberg.
Descrivere nei dettagli la tartaruga di Grey Walter rappresentandola con STRIPS e e discuterne il funzionamento in termini di GPS.
Il Nested Hierarchical Controller (NHC) è una delle più note architetture gerarchiche sviluppata da Meystel (1990).
In essa le tre componenti PERCEPISCI-PIANIFICA-AGISCI sono ben visibili.
Il robot inizia con il raccogliere i dati dai suoi sensori (PERCEPISCI) per costruire il suo modello del mondo (Modello del mondo /Base di conoscenza). Per altro il suo Modello del mondo può anche avere una conoscenza a priori fornita dal progettista (ad esempio una mappa dell’ambiente, regole di comportamento, etc.).
Aggiornato il Modello del mondo con l’attività sensoriale, il modulo PIANIFICA interviene per decidere cosa fare.
Questo modulo ha tre sotto moduli ognuno dei quali interagisce con il Modello del Mondo e con quello che lo precede.
Pianificatore di missione.
Navigatore
Pilota
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 Pilota manda gli opportuni comandi ai controller degli attuatori, ET2 riattiva i suoi sensori.
Il Modello del Mondo è aggiornato. Però non si ripete il ciclo precedente, perché ora ET ha il suo goal e il suo percorso. Il Pilota 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 Pilota verifica che ha raggiunto l’estremità del segmento di cammino assegnatogli dal Navigatore informa quest’ultimo e riceve il nuovo segmento da seguire. Se ha raggiunto il goal allora il Navigatore informa il Pianificatore di missione che decide cosa fare (fermare il tutto, programmare un nuovo goal, etc.).
Se il Pilota trova un ostacolo ne informa il Navigatore 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 Modello del Mondo aggiornato di volta in volta.
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 Pianificatore di Missione è più intelligente e opera ad un livello più astratto di Navigatore 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.
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.
Le attività percettive sono raggruppate in una serie di moduli denominati Percezione Sensoriale.
L’output dei sensori è inviato al Modello del mondo che costruisce una mappa globale usando anche le informazioni già presenti nella sua Base di conoscenza. 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 modulo Valutazione del piano che fornisce la maggior parte delle funzionalità necessarie per l’attività di PIANIFICAZIONE. In altre parole pianifica e simula i piani per assicurarsi che tutto funzioni. Dopo di che invia i piani al modulo Generazione del Behavior che converte i piani in azioni che il robot può realmente eseguire (AZIONE). A questi moduli se ne aggiunge un altro non mostrato che permette il debug all’osservatore umano
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 PERCEZIONE e AZIONE sono sempre disconnessi impedendo così una immediata reazione ad un evento pericoloso.
Questo standard è stato adottato dalla NASA e dal US Bureau of Mines.
Queste architetture, NHC e RCS sembrano molto utili per un controllo semiautonomo. L’operatore umano può fornire il Modello del Mondo, 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 Pilota 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.
La dipendenza da un global Modello del Mondo, e cioè del frame problem, fa sì che queste architetture non siano molto generali ma risentano 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.
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).
Le architetture NHC e RCS/NASREM sono ragionevoli per sistemi semi-autonomi dove:
L’operatore umano potrebbe:
Il robot potrebbe:
Far diventare il robot più intelligente significa trasferirgli alcune delle funzioni dell’operatore umano seguendo a salire la gerarchia precedente.
1. Introduzione
4. Esempi di applicazione del paradigma gerarchico
11. Schema Theory
13. Architetture Reattive a Sussunzione
14. Architetture a Campi di Potenziale
15. Architetture a Campi di Potenziale e Sussunzione
16. Progettazione di un sistema Reattivo - 1
17. Progettazione di un sistema Reattivo - 2
18. Progettazione di un sistema Reattivo - 3