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 » 13.Architetture Reattive a Sussunzione


I vantaggi di programmare con i behaviour

Costruire un sistema robotico secondo il Paradigma Reattivo è spesso riportato come programmare con behaviour, poiché il componente fondamentale di ogni realizzazione sono i behaviour.
Programmare con behaviour ha molti vantaggi, la maggior parte dei quali sono coerenti coi buoni principi di ingegneria del software.
I behaviour sono inerentemente modulari e facili da verificare isolati dal sistema (cioè essi sono unità di test).
I behaviour forniscono anche possibili espansioni incrementali delle capacità di un robot. Un robot diviene più intelligente avendo più behaviour. La decomposizione comportamentale dà luogo ad una realizzazione che opera in tempo reale ed è di solito computazionalmente poco costosa.
Ciononostante vedremo che alcune volte la duplicazione di alcuni sensori specializzati (come i flussi ottici) è lenta. Se i behaviour sono realizzati in economia, allora la realizzazione reattiva può essere lenta.

I vantaggi di programmare con i behaviour (segue)

Generalmente, la velocità di reazione di un robot reattivo è equivalente ai tempi di stimolo-risposta negli animali.

I behaviour rappresentano dei buoni principi di ingegneria del software utilizzando la decomposizione, la modularità e i test incrementali.

Se il sistema robotico è programmato con il più alto grado di indipendenza possibile (anche detto accoppiamento basso), il progettista può implementare biblioteche facili da capire, da manutenere, e può riusare moduli che minimizzano i side effects.

Accoppiamento basso vuole dire che i moduli possono funzionare indipendentemente l’uno dall’altro con minimi collegamenti o interfacce, promuovendo così un facile riuso.

Coesione vuole dire che i dati e le operazioni contenute in un modulo si riferiscono solo al goal di quel modulo.

Architetture rappresentative

Per implementare un Sistema Reattivo il progettista deve identificare il set di behaviour necessario per il task. I behaviour possono essere o nuovi o si possono usare behaviour esistenti. L’azione complessiva del robot emerge da behaviour multipli e concomitanti.

Quindi un’architettura reattiva deve offrire meccanismi per:

  1. gestire behaviour;
  2. determinare quello che accade quando behaviour multipli sono attivi allo stesso tempo.

Un’altra caratteristica che distingue tra loro le architetture reattive è come esse definiscono un behaviour.

Architetture rappresentative (segue)

Ci sono molte architetture che vanno bene con il Paradigma Reattivo.
Le due più conosciute e meglio formalizzate sono la sussunzione e i campi di potenziale.

La sussunzione fa riferimento a come i behaviour sono combinati.

Le metodologie a campi di potenziale costringono i behaviour ad essere implementati come campi di potenziale, ed i behaviour risultanti sono ottenuti dalla sommatoria dei rispettivi vettori risultanti.

Architetture rappresentative (segue)

Un terzo stile di architettura reattiva che è popolare in Europa e in Giappone è il rule encoding, dove il componente schema motore del behaviour ed il meccanismo di combinazione sono implementati secondo regole logiche. Le regole per combinare i behaviour sono spesso ad hoc, e pertanto non le tratteremo in questo corso.

Altri metodi per combinare behaviour esistono, incluso metodi fuzzy e il vincitore-prende-tutto, ma questi tendono ad essere dettagli di realizzazione piuttosto che una vera e propria architettura.

Architettura a Sussunzione

L’architettura a sussunzione di Rodney Brooks è la più nota nei sistemi puramente reattivi.
Parte della popolarità scaturisce dalla pubblicità che circonda i molti robot naturalistici costruiti con la sussunzione. Come si può vedere in figura, questi robot davvero sembrano insetti dell’ordine di grandezza di una scatola di scarpe, con sei gambe ed antenne.

In molte realizzazioni, i behaviour sono inseriti direttamente nel hardware o su piccoli micro-microprocessori, permettendo ai robot di avere tutta la capacità di calcolo on-board (questo non era vero per i microprocessori poco potenti di metà degli anni 1980).

Inoltre, i robot di Brooks furono i primi ad essere capaci di camminare, evitando collisioni, salire su ostacoli senza le pause del “muovi-pensa-muovi-pensa” di Shakey.

Architettura a Sussunzione (segue)

Il termine “behaviour” nell’architettura a sussunzione ha un significato meno preciso che nelle altre architetture.

Un behaviour è una rete di moduli percezione-azione che portano a termine un task. I moduli sono Augmented Finite State Machine AFSM, che hanno registri, temporizzatori, e altri miglioramenti per permettere loro di essere connessi con gli altri moduli.

Un AFSM è equivalente all’interfaccia tra gli schemi e la strategia di controllo coordinato in un schema comportamentale.

In termini di schema theory, un behaviour a sussunzione è una raccolta di uno o più schemi in behaviour astratti.

Architettura a Sussunzione (segue)

Una Macchina a Stati Finiti (FSM) è un sistema computazionale che cambia il suo stato in funzione dello stato corrente e dell’input.
Essa può assumere un numero finito di stati differenti e passa da uno stato all’altro secondo precise regole.
Un esempio è un cancelletto girevole che si apre con una moneta.
Se il cancelletto è bloccato (stato 1) e si inserisce una moneta, allora la macchina cambia stato (stato 2 – cancelletto sbloccato).
Se l’input ora è una persona, cioè qualcuno cerca di entrare, e si inserisce una moneta allora si sblocca e subito dopo però torna allo stato 1.
Se è sbloccato e si inserisce una moneta, la macchina resta nello stato 2. Se è bloccato (stato 1) e l’input è una persona esso rimane bloccato.

Esempio di una Macchina a Stati Finiti

Esempio di una Macchina a Stati Finiti


Architettura a Sussunzione (segue)

Le Macchine a Stati Finiti Augmented (AFSM) sono FSM a cui vengono aggiunte alcune facilities (registri, sistemi di timing etc…).

Esempio di una Macchina a Stati Finiti

Esempio di una Macchina a Stati Finiti


Architettura a Sussunzione (segue)

I behaviour sono attivati con una modalità tipo stimolo-risposta, senza un programma esterno che li coordini e controlli esplicitamente.

Ci sono quattro aspetti interessanti della sussunzione in termini di attivazione e controllo :

1. I moduli sono raggruppati in strati di competenza.
Gli strati riflettono una gerarchia dell’intelligenza, o della competenza. Strati più bassi incapsulano funzioni di sopravvivenza di base come evitare collisioni, mentre livelli più alti creano azioni dirette alla meta come ad esempio il mapping di un oggetto.
Ognuno degli strati può essere visto come un behaviour astratto per un particolare compito.

Architettura a Sussunzione (segue)

2. I moduli in un strato più alto possono avere la priorità, o sussumere, l’output del behaviour nello strato adiacente più basso.

Gli strati comportamentali operano concomitantemente ed indipendentemente, quindi si ha bisogno di disporre di un meccanismo che si occupi dei conflitti potenziali.

La soluzione nella sussunzione è del tipo il vincitore-prendere-tutto, dove il vincitore è sempre lo strato più alto.

Architettura a Sussunzione (segue)

3. L’uso di stati interni è evitato.

Per stato interno, in questo caso, si intende un qualunque tipo di rappresentazione locale e persistente che rappresenta lo stato del mondo, o un modello.

Poiché il robot è un agente situato, la maggior parte delle sue informazioni dovrebbero venire direttamente dal mondo.

Se il robot dipende da una rappresentazione interna, quello che esso crede può cominciare a divergere pericolosamente dalla realtà.

Alcuni stati interni sono necessari per attivare behaviour come essere spaventati o affamati, ma una buona progettazione li minimizza.

Architettura a Sussunzione (segue)

4. Un task è portato a termine attivando lo strato opportuno che poi attiva gli strati più bassi sotto di lui e così via.

In pratica, i sistemi a sussunzione non sono facilmente taskable, ovvero, non possono ricevere l’ordine di fare un altro task senza essere riprogrammati.

Architettura a Sussunzione (segue)

Ci sono quattro aspetti interessanti della sussunzione in termini di attivazione e controllo :

  1. i moduli sono raggruppati in strati di competenza;
  2. i moduli in un strato più alto possono avere la priorità, o sussumere, l’output del behaviour nello strato adiacente più basso;
  3. l’uso di stati interni è evitato;
  4. un task è portato a termine attivando lo strato opportuno che poi attiva gli strati più bassi sotto di lui e così via.

Esempi

Questi aspetti sono illustrati meglio da un esempio, preso e modificato estensivamente dai lavori originali di Brooks al fine di essere consistente con la terminologia della teoria degli schemi e facilitare il paragone con la metodologia dei campi di potenziale.

Un robot capace di muoversi in avanti e non collidere con niente potrebbe essere rappresentato con un solo strato, Livello 0.

In questo esempio, il robot ha sonar multipli (o altri sensori di distanza), ognuno che punta in una direzione diversa, e due attuatori, uno per andare avanti ed uno per girare.

Esempio di sussunzione

Il modulo Sonar legge il range dei sonar, fa ogni possibile filtraggio del rumore, e produce un grafico polare.

Un grafico polare rappresenta le letture di distanze in coordinate polari, (r, Θ), intorno al robot.

Come mostrato in Fig., la trama polare può essere sviluppata linearmente.

Architettura a sussunzione: livello 0 e esempio di diagrammi polare e lineare delle 
letture sonar

Architettura a sussunzione: livello 0 e esempio di diagrammi polare e lineare delle letture sonar


Esempio di sussunzione (segue)

Se la lettura del range del sonar rivolto in avanti è sotto una certa soglia, il modulo RILEVATORE DI COLLISIONI annuncia una collisione e spedisce il segnale di alt all’attuatore che gestisce il FORWARD. Se il robot si sta muovendo in avanti, ora si ferma. Nel frattempo, il modulo di COMPOSIZIONE DI FORZE sta ricevendo lo stesso grafico polare. Esso tratta ogni lettura del sonar come una forza repulsiva che può essere rappresentata come un vettore.

COMPOSIZIONE DI FORZE può essere pensato come un sommatore di vettori formati da ognuna delle letture sonar. Questo dà luogo ad un vettore nuovo. Il vettore repulsivo è passato poi al modulo di GIRA.
Il modulo di GENERAZIONE MOTO trasforma le informazioni connesse al vettore in indicazioni di direzione e velocità per il modulo successivo GIRA.

Architettura a sussunzione: livello 0

Architettura a sussunzione: livello 0


Esempio di sussunzione (segue)

Il modulo di GIRA elabora la direzione per girare e la invia all’attuatore di svolta. GIRA passa il vettore anche al modulo FORWARD che determina la grandezza del prossimo movimento in avanti (quanto lontano o quanto veloce). Così il robot gira e va via evitando l’ostacolo.

Architettura a sussunzione: livello 0

Architettura a sussunzione: livello 0


Esempio di sussunzione (segue)

Il behaviour osservabile consiste nel verificare che il robot è in grado di accorgersi di non trovarsi in un spazio occupato. Questo behaviour si ripete finché il robot non arriva vicino ad un ostacolo. Se l’ostacolo è su un lato del robot, il robot potrà girare di 180° nella direzione opposta e andare via.
Il robot può reagire ad un ostacolo sia se entrambi sono immobili o in lento movimento; la risposta è calcolata ad ogni aggiornamento dei sensori.
Se parte dell’ostacolo, o un altro ostacolo, è messo davanti, il robot si fermerà, poi applicherà i risultati di GENERAZIONE MOTO. Cioè si fermerà, girerà e comincerà a muoversi di nuovo in avanti. La fermata impedisce al robot di urtare l’ostacolo mentre sta girandosi.
Il livello 0 mostra come un set abbastanza complesso di azioni può emergere da moduli molto semplici.

Architettura a sussunzione: livello 0

Architettura a sussunzione: livello 0


Esempio di sussunzione (segue)

È utile rivedere l’architettura a sussunzione nei termini usati finora in questo corso, come mostrato in figura. Si noti come i dati sensoriali circolano attraverso i behaviour concorrenti verso l’attuatore. I behaviour sono indipendenti.
Il modulo SONAR potrebbe essere considerato come un’interfaccia globale verso i sensori, mentre i moduli GIRA e FORWARD sarebbero considerati come parte dell’attuatore (un’interfaccia).

Livello 0 come behavior primitivi

Livello 0 come behavior primitivi


Esempio di sussunzione (segue)

Per gli scopi di questo corso, un behaviour deve consistere di uno schema percettivo e di uno schema motorio. Gli schemi percettivi sono connessi ad un sensore, mentre gli schemi motori sono connessi ad attuatori.
Per il Livello 0, gli schemi percettivi sono contenuti nei moduli COMPOSIZIONE DI FORZE e RILEVATORE DI COLLISIONI.
Gli schemi motori sono i moduli GENERAZIONE MOTO e RILEVATORE DI COLLISIONI.
RILEVATORE DI COLLISIONIcombina sia il processo percettivo (estrae il vettore dal sonar che guarda direttamente avanti) sia il pattern attuativo (dà l’alt se c’è una lettura negativa).
I behaviour primitivi riflettono i due percorsi attraverso lo strato. Uno potrebbe essere chiamato il behaviour di GENERAZIONE MOTO e l’altro il behaviour di RILEVATORE DI COLLISIONI. Insieme, i due behaviour creano un behaviour per evitare ostacoli, o uno strato di competenza.

Livello 0 come behavior primitivi

Livello 0 come behavior primitivi

Behavior del sistema visivo della rana

Behavior del sistema visivo della rana


Esempio di sussunzione (segue)

Si noti che i behaviour usano una percezione diretta, o affordance. La presenza di una lettura di distanza indica che c’è un ostacolo; il robot non sa di che tipo di ostacolo si tratti.
Supponiamo di costruire un robot che va in giro invece di tentare di andare sempre diritto, ma è sempre capace di evitare ostacoli. Sulla base dello schema a sussunzione, può essere aggiunto un secondo strato di competenza (Livello 1).

Architettura a sussunzione: livello 1

Architettura a sussunzione: livello 1


Esempio di sussunzione (segue)

In questo caso, il Livello 1 consiste di un modulo VAI IN GIRO che elabora un andamento casuale ogni n secondi. L’andamento casuale può essere pensato come un vettore. Esso ha bisogno di passare la sua indicazione ai moduli GIRA e FORWARD. Ma non può essere passato direttamente al modulo GIRA. Questo infatti impedirebbe di evitare gli ostacoli, perché GIRA accetta solamente un input alla volta. Una soluzione è di aggiungere un altro modulo al Livello 1, EVITA che combina il vettore di COMPOSIZIONE DI FORZE col vettore di VAI IN GIRO.

Architettura a sussunzione: livello 1

Architettura a sussunzione: livello 1


Esempio di sussunzione (segue)

Aggiungendo un nuovo modulo EVITA si offre un’opportunità di creare una risposta più sofisticata agli ostacoli. EVITA combina la direzione della forza da evitare con la direzione desiderata. Questo dà luogo alla direzione attuale che è rivolta più verso una direzione corretta che verso la svolta che il robot avrebbe dovuto fare facendo un avanzamento diretto. (Si noti anche che il modulo EVITA è capace di “spiare” le componenti dello strato più basso). L’output di una direzione di EVITA ha la stessa rappresentazione dell’output di GENERAZIONE MOTO così che GIRA può accettare input da una delle due fonti.

Architettura a sussunzione: livello 1

Architettura a sussunzione: livello 1


Esempio di sussunzione (segue)

Il problema ora è quello di stabilire quando accettare il vettore di direzione e da quale strato.
La sussunzione rende questo semplice: l’output dal livello più alto sussume l’output dal livello più basso.
La sussunzione è realizzata in uno dei due seguenti modi.

1. Inibizione

Nell’inibizione, l’output del modulo di sussunzione è connesso all’output di un altro modulo. Se l’output del modulo che sussume è “on” o ha un qualunque valore, l’output del modulo sussunto è spento. L’inibizione agisce come un rubinetto, cambiando da on a off l’output.

Esempio di sussunzione (segue)

2. Soppressione

Nella soppressione, l’output del modulo che sussume è connesso all’input di un altro modulo. Se l’output del modulo che sussume è on, esso sostituisce l’input normale al modulo sussunto.
La soppressione agisce come uno switch, scambiando un input con un altro.
In questo caso, il modulo EVITA sopprime (segnato nel diagramma con una S) l’output da GENERAZIONE MOTO.

GENERAZIONE MOTO sta ancora operando, ma il suo output non va da nessuna parte.
Invece, l’output di EVITA va a GIRA.

Esempio di sussunzione (segue)

L’uso di strati e sussunzione permette a nuovi strati di essere costruiti sopra lo strato meno competente, senza cambiare gli strati più bassi. Questa è buona ingegneria del software, poiché facilita la modularità e semplifica il test. Essa aggiunge anche un po’ di robustezza nel senso che se qualche cosa dovesse disabilitare il Livello 1, il Livello 0 è probabile che rimanga intatto. Il robot sarebbe almeno capace di preservare il suo meccanismo di autodifesa e quindi di fuggire quando si avvicina agli ostacoli.

Architettura a sussunzione: livello 1

Architettura a sussunzione: livello 1


Esempio di sussunzione (segue)

La Fig. mostra il Livello 1 rivisto come behaviour. Si noti che COMPOSIZIONE DI FORZE è usato da GENERAZIONE MOTO e EVITA.
COMPOSIZIONE DI FORZE è la componente percettiva (nello schema) di ambo i behaviour, con i moduli EVITA e GENERAZIONE MOTO che sono il componente motorio. Spesso accade che i behaviour sono chiamati con il nome dell’azione osservabile. Questo vuole dire che il behaviour (che consiste di percezione ed azione) e la componente azione hanno lo stesso nome. La figura non mostra che i behaviour EVITA e GENERAZIONE MOTO hanno lo stesso schema percettivo COMPOSIZIONE DI FORZE. Come sarà visto nel prossimo capitolo, le proprietà object-oriented dello schema theory facilitano il riuso e la condivisione di componenti percettive e motorie.

Livello 1 come behavior primitivi

Livello 1 come behavior primitivi


Esempio di sussunzione (segue)

Ora supponiamo di aggiungere un terzo strato per permettere al robot di muoversi lungo un corridoio, come mostrato in Fig. (il terzo strato nel lavoro originale di Brooks è “esplorare”, perché lui stava considerando un task di mappatura). Il modulo di CERCA esamina il plot polare del sonar ed identifica un corridoio. (Si noti che questo è un altro esempio di behaviour che condivide gli stessi dati sensoriali ma li usa localmente per scopi diversi). Poiché identificare un corridoio è più costoso computazionalmente che estrarre solo i dati di distanza, CERCA può richiedere più tempo di elaborazione di quello richiesto dai behaviour a livelli più bassi. CERCA passa il vettore che rappresenta la direzione in mezzo al corridoio al modulo STAI NEL MEZZO. STAI NEL MEZZO sussume il modulo VAI IN GIRO e manda il suo output al modulo EVITA che può eventualmente girare attorno agli ostacoli.

Architettura a sussunzione: livello 2

Architettura a sussunzione: livello 2


Esempio di sussunzione (segue)

Ma come fa il robot se il modulo di CERCA non ha calcolato una direzione nuova? In questo caso il modulo INTEGRA sta osservando il moto attuale del robot dagli shaft encoders (odometri) degli attuatori. Questo dà una stima di quanto lontano dal centro il robot abbia viaggiato dall’ultimo aggiornamento di CERCA.
STAI NEL MEZZO può usare i dati raccolti per calcolare il vettore per il nuovo corso. Questo serve a colmare i vuoti negli adattamenti dovuti a diverse velocità di aggiornamento dei diversi moduli. Si noti che CERCA e STAI NEL MEZZO sono alquanto sofisticati da un punto di vista software.

Architettura a sussunzione: livello 2

Architettura a sussunzione: livello 2


Esempio di sussunzione (segue)

INTEGRA è un esempio di modulo che si preoccupa di un eventuale stato interno pericoloso: esso opera sulla base di un feedback dal mondo reale. Se per qualche ragione, il modulo di CERCA non aggiorna mai, allora il robot potrebbe operare senza alcuni dati sensoriali per sempre. O almeno finché non si rompe! Perciò, sistemi con lo stile a sussunzione includono costanti di tempo sulla soppressione e sull’inibizione.
Se la soppressione da STAI NEL MEZZO funziona più a lungo di n allora la soppressione cessa. Il robot comincia a vagare con una buona speranza che qualunque sia il problema (come essere entrato in un ambiente molto grande) che aveva condotto alla perdita dei segnali si risolva.

Architettura a sussunzione: livello 2

Architettura a sussunzione: livello 2


Esempio di sussunzione (segue)

Chiaramente, un altro problema è: come sa il robot che non ha cominciato a percorrere il corridoio come avrebbe dovuto?
Risposta: non lo sa.
Il progetto presume che un corridoio sarà sempre presente nella nicchia ecologica del robot.
Se non c’è, il robot non si comporta come previsto.
Questo è un esempio della connotazione che i sistemi reattivi sono “senza memoria.”

Sommario Sussunzione

  • La sussunzione ha una debole definizione di behaviour come accoppiamento stretto di percezione e azione. Anche se non è un’architettura a schema-theory, essa può essere descritta in questi termini. Essa raggruppa moduli tipo schema in strati di competenza, o behaviour astratti.
  • Strati più alti possono sopprimere e inibire behaviour in strati più bassi, ma behaviour in strati più bassi non sono mai riscritti o sostituiti. Da un punto di vista della programmazione, questo può sembrare strano. Comunque, così si imita l’evoluzione biologica. Si ricordi che il behaviour descritto per le rane (Lezione 3) era il risultato di due behaviour, uno che si muoveva sempre verso gli oggetti in movimento e l’altro che sopprimeva questo behaviour quando l’oggetto era grande.

Sommario Sussunzione (segue)

  • Il progetto di strati e componenti di behaviour per una realizzazione della sussunzione, come con ogni altro progetto comportamentale, è difficile; è più un’arte che una scienza. Questo è vero per tutte le architetture reattive.
  • Non vi è nulla che assomigli ad una pianificazione tipo STRIPS nella sussunzione. Invece i behaviour sono attivati dalla presenza dello stimolo nell’ambiente.

Sommario Sussunzione (segue)

  • La sussunzione risolve il Frame problem eliminando il bisogno di modellare il mondo. Non ci deve preoccupare se il mondo aperto è non-monotono e non ha un tipo di meccanismo di mantenimento di verità, perché i behaviour non ricordano il passato. Ci può essere della persistenza percettiva che conduce ad un tipo di behaviour con un pattern di azione fisso (e.g. seguire un corridoio), ma non c’è nessun meccanismo che evidenzi i cambi nell’ambiente. I behaviour semplicemente rispondono a qualunque stimolo dell’ambiente.
  • La Percezione è diretta, usando le affordance. Il releaser per un behaviour è quasi sempre il percetto per guidare lo schema motore.
  • La percezione è ego-centrica e distribuita. Nell’esempio del VAI IN GIRO (strato 1), il plot polare del sonar è relativo al robot. Un plot polare nuovo viene creato ad ogni aggiornamento dei sensori. Il plot polare è anche disponibile per qualunque processo ne abbia bisogno (memoria globale e condivisa), permettendo ai moduli utente di essere distribuiti. L’output dallo schema percettivo può essere condiviso con gli altri strati.

Proposte di progetti

Simulazione
Operai – Dato un ambiente con ostacoli fissi di colore blu, contenenente un certo numero di oggetti gialli. Progettare un team di robot (da due a 5 a scelta) che individuano gli oggetti gialli e li spingono (o trasportano insieme) in una prefissata posizione di accumulo.

Proposte di progetti

Hardware

Cataglyphis. Simulare il comportamento di due formiche Cataglyphis. Entrambe partono dalla tana e in maniera casuale vanno a cercare il cibo. Quando una delle due lo trova, accende una luce si fa raggiungere dall’altra e poi va direttamente alla tana. La stessa cosa farà la seconda formica.

  • 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