Vai alla Home Page About me Courseware Federica Living Library Federica Federica Podstudio Virtual Campus 3D Le Miniguide all'orientamento Gli eBook di Federica La Corte in Rete
 
I corsi di Scienze Matematiche Fisiche e Naturali
 
Il Corso Le lezioni del Corso La Cattedra
 
Materiali di approfondimento Risorse Web Il Podcast di questa lezione

Ernesto Burattini » 3.Il paradigma gerarchico


Primitive dei robot

Struttura del paradigma gerarchico

Struttura del paradigma gerarchico


Paradigma gerarchico

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) percepire-pianificare-agire
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.

Tabella del paradigma gerarchico

Tabella del paradigma gerarchico


Paradigma gerarchico (segue)

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 è immerso;
b – informazioni sensoriali (mi trovo in questo punto della stanza);
c – ogni ulteriore informazione di tipo cognitivo (es. il goal che deve perseguire).

Closed world e 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

Closed world e Frame problem (segue)

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

  • essere efficace, cioè garantire il raggiungimento dell’obiettivo;
  • essere completa, cioè le pre-condizioni 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.

Il mondo dei cubi


Lo stato del mondo


Il mondo dei cubi (segue)

Un esempio di applicazione del paradigma gerarchico in Prolog

Un esempio di applicazione del paradigma gerarchico in Prolog


Il mondo dei cubi (segue)


Una esecuzione in LPA WIN-PROLOG 4.040


Una esecuzione in LPA WIN-PROLOG 4.040 (segue)


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.

Esempio dello spazzino

Esempio dello spazzino


Robot spazzino

Soluzione Prolog dell’esempio dello spazzino

Soluzione Prolog dell'esempio dello spazzino


Robot spazzino (segue)


Robot spazzino (segue)


Esercizio

L’elaborazione di tutte queste informazioni può essere dal punto di vista computazionale molto onerosa.

Esercizio

Rappresentare 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.
Suggerimento: usare un albero dove ogni nodo rappresenta la situazione sulle due sponde e ogni arco un operatore che indica quali soggetti sono traghettati.

Esercizio

Albero degli stati del problema dei missionari e cannibali

Albero degli stati del problema dei missionari e cannibali


Esercizio

Tabella degli stati del problema dei missionari e cannibali

Tabella degli stati del problema dei missionari e cannibali


I materiali di supporto della lezione

Missionari

  • Contenuti protetti da Creative Commons
  • Feed RSS
  • Condividi su FriendFeed
  • Condividi su Facebook
  • Segnala su Twitter
  • Condividi su LinkedIn
Progetto "Campus Virtuale" dell'Università degli Studi di Napoli Federico II, realizzato con il cofinanziamento dell'Unione europea. Asse V - Società dell'informazione - Obiettivo Operativo 5.1 e-Government ed e-Inclusion