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
 
 
Il Corso Le lezioni del Corso La Cattedra
 
Materiali di approfondimento Risorse Web Il Podcast di questa lezione

Ernesto Burattini » 19.Automi a Stati Finiti


Automi a Stati Finiti (FSA)

Gli Automi a Stati Finiti (FSA) sono un meccanismo utile per specificare quello che un programma dovrebbe fare ad un certo tempo o circostanza.

Il FSA può essere scritto come una tavola o progettato come un diagramma di stato, dando così al progettista una rappresentazione visiva. La maggior parte dei progettisti fanno entrambe le cose.

Ci sono molte varianti di FSA, ma lavorano tutte pressappoco allo stesso modo.

Automi a Stati Finiti (FSA) – segue

Per cominciare, il progettista deve essere capace di specificare un numero limitato di stati distinti nei quali il robot potrebbe trovarsi. Il set di stati è rappresentato da K, e ogni stato q ∈ K è una lista dei behavior che dovrebbero/potrebbero essere attivi contemporaneamente. Nel caso della competizione precedente, c’erano solamente due stati: seguire la linea e muoversi in avanti. Gli stati sono rappresentati in una tavola sotto l’intestazione q, e da cerchi in un grafico.
In figura : rappresentazione con FSA del coordinamento e controllo dei behavior nella gara UGV.

a – diagramma; b – tavola

a – diagramma; b - tavola


Automi a Stati Finiti (FSA) – segue

Per convenzione, vi è sempre un stato di Start, ed il robot dovrebbe partire sempre di là. Lo stato di Start è spesso scritto come s o q0 e disegnato con un doppio cerchio. Nel caso dell’UGR, (Unmanned Ground Vehicle) lo stato di following-line era sempre lo stato di inizio poichè il robot cominciava col behavior di follow-line attivo.
La successiva parte del FSA è l’input (anche detto alfabeto). Gli input sono i releaser comportamentali, ed appaiono sotto la colonna dove campeggia σ. La tavola del FSA considera quello che accade ad ogni stato q per tutti i possibili input.


Automi a Stati Finiti (FSA) – segue

Come mostrato in figura, ci sono solamente due releaser per l’esempio di UGR, così la tavola non ha molte righe.


FSM

La terza parte del FSM è la funzione di transizione, detta δ che specifica in che stato va il robot dato uno stimolo in input. Il set di stimoli o affordances che può essere riconosciuto dal robot è rappresentato da Σ. Questi stimoli sono rappresentati da frecce. Ogni freccia rappresenta il releaser per un behavior. Il nuovo behavior triggerato dal releaser dipende dallo stato nel quale il robot si trova. Questo è lo stesso dell’IRM, dove letteralmente vengono ignorati i releaser che non sono rilevanti per lo stato corrente.


FSM (segue)

Si ricordi anche che nelle lezioni precedenti nella implementazione del programma seriale dell’IRMs l’agente “osservava” i releaser ogni secondo. Ad ogni iterazione, l’agente avrebbe potuto avere fame e “sarebbe entrato” nello stato di alimentarsi. Nella successiva iterazione, ancora avrebbe potuto avere fame e sarebbe rientrato nello stato di alimentarsi. Questo può essere rappresentato avendo frecce che partono dallo stato di alimentarsi e puntano di nuovo allo stesso stato.

Il codice C

Il codice C è implementato come una sequenza implicita, dove l’ordine di esecuzione dipende dal valore dei releaser. Una implementazione come sequenza esplicita potrebbe essere la seguente in figura:


Esempio

Per l’esempio in figura, il robot comincia nello stato di seguire una linea. Questo vuole dire che il robot non è preparato a gestire una distrazione visuale (range near) finché non ha cominciato a seguire una linea. Se lo fa, il programma può fallire perché il FSA chiaramente mostra che non risponderà alla distrazione per almeno un ciclo di aggiornamento. In questo periodo, il robot può dirigersi in direzioni sbagliate. Cominciare nello stato di following-line andava bene per la competizione di UGR, dove si sapeva in anticipo che non c’erano balle di fieno vicino alla linea iniziale.


Caso generale

Un caso più generale è mostrato in figura, dove il robot può partire sia su un percorso libero sia in presenza di una balla.

FSA generale per il problema dell’UGV

FSA generale per il problema dell'UGV


Il task

Il quarto pezzo di informazione che un progettista ha bisogno di sapere è quando il robot ha completato il task.
Ogni stato che il robot può raggiungere e che termina il task è un membro del set di stati finali, F.
Nell’esempio di UGR il robot non si ferma mai e non c’è uno stato finale – il robot funziona finché non è spento a mano o si scarica la batteria.
Così, entrambi gli stati (follow_line e muovi-in_avanti) sono stati finali.
Se il robot potesse riconoscere la linea di arrivo, allora potrebbe aversi un stato finale.

Lo stato finale

Lo stato finale potrebbe essere fermati o potrebbe essere un altro behavior, come in caso di vittoria agitare la telecamera.
Si noti che questo aggiunge altre righe alla tabella del FSA, poiché vi deve essere almeno una riga per ogni singolo stato.
Da molti punti di vista, la tabella del FSA è una estensione della tabella comportamentale. La tabella risultante è nota come una macchina a stati finiti (FSM) abbreviato M.

La notazione

M = {K,Σ,δ, s, F}
è usata per ricordare che per usare un FSA il progettista deve sapere tutti i q stati (K), gli input σ le transizioni tra gli stati δ lo stato iniziale speciale s=q0 e lo stato/i finale (F). Ci deve essere una freccia nel diagramma di stato per ogni riga nella tabella.
La tabella compendia le relazioni tra gli FSA e i behavior.


Gli ostacoli

In domini più complessi, i robot hanno bisogno di evitare ostacoli (specialmente le persone).
AVOID dovrebbe essere sempre attivo, per cui è spesso implicito nel FSA.

Move_to_goal è spesso inteso come move_to_goal e EVITA.

Questo raggruppamento implicito di “behavior interessante per il task” e “quei behavior che proteggono il robot” sono anche visti come behavior strategici e tattici.

Un altro punto importante circa l’uso dei FSA è che essi descrivono il behavior complessivo di un sistema, mentre le implementazioni possono variare.

Cambi di stato

In figura c’è una descrizione accurata dei cambi di stato all’inizio dell’UGV. Il controllo per il behavior poteva essere implementato come indicato dal FSA: se following-line è attiva e range ritorna distanza vicino, allora muovi_in_avanti.
Gli esempi seguenti mostreranno come il concetto di FSA può essere implementato con la sussunzione e i sistemi a schema-theory.

 Cambi di stato

Cambi di stato


Un FSA per la raccolta dell’immondizia

Come altro esempio di come costruire ed applicare un FSA, si consideri il task della raccolta dell’immondizia. Supponiamo che il robot sia un piccolo veicolo, come quelli usati dalla Georgia Tech o il Pioneer mostrati in figura, con un bumper, per dire quando il robot ha urtato qualche cosa, ed una telecamera.

In entrambi i casi, il robot ha un semplice gripper. Si presume che il robot può dire se il gripper è vuoto o pieno. Un modo per fare questo è mettere un sensore a IR attraverso la mascella del gripper. Quando l’IR ritorna uno short range, il gripper è pieno e si può immediatamente chiudere, con un riflesso di presa.

Un FSA per la raccolta dell’immondizia (segue)

Un problema con i gripper è che non sono efficienti come una mano umana. Così, c’è sempre la possibilità che la lattina scivoli o cada fuori del gripper.
Il robot dovrebbe però rispondere adeguatamente se mentre sta portando una lattina o della immondizia la perde.

In fugura: due vincitori della gara per la raccolta della spazzatura.

Un FSA per la raccolta dell’immondizia (segue)

L’ambiente in questo esempio è visualmente semplice, e ci sono ovvie affordances. Le lattine di Coca-cola sono gli unici oggetti rossi nell’ambiente, e i bidoni di immondizia sono gli unici oggetti blu. Estrarre perciò visualmente macchie rosse e blu dovrebbe essere sufficiente. Tutti gli oggetti sono sul pavimento, così il robot si deve preoccupare solamente di dove sono gli oggetti sull’asse x.

Lo scenario

Uno scenario di base per il robot è cominciare a vagare nella stanza alla ricerca di macchie rosse. Dovrebbe tirare diritto verso il centro della macchia rossa più grande finché non arriva alla lattina. Poi dovrebbe tentare tre volte di afferrare la lattina, e, se ci riesce, dovrebbe cominciare a vagare cercando una macchia blu.

Ci dovrebbe essere solamente una macchia blu alla volta nell’immagine perché i due bidoni di immondizia sono messi in angoli opposti della stanza. Non appena vede una macchia blu, il robot deve muoversi diritto al centro della macchia finché la macchia diventa di una certa grandezza nell’immagine (potendo essere vista anche da lontano).

La tavola dei behavior

Il robot allora dovrebbe fermarsi, lasciare cadere la lattina, rivolgersi in una nuova direzione casuale e riprendere il ciclo. Il robot dovrebbe evitare ostacoli, ma muovendosi verso una macchia rossa o blu dovrebbe avere un’azione di riferimento prefissata, altrimenti immediatamente il robot dimentica dove stava andando.

In figura: la tavola dei behavior.

Tavola dei behavior

Tavola dei behavior


La tavola dei behavior (segue)

Le chiamate di funzione nella tavola mostrano per brevità solo gli argomenti rilevanti.
Il behavior EVITA è interessante. Il robot quando urta qualche cosa indietreggia o a destra o a sinistra. Può urtare un muro dell’ambiente in diverse posizioni, allora si muoverà in wander in una qualunque direzione. Se il robot urta una lattina (invece di afferrarla con il suo gripper), indietreggiando ha una seconda opportunità.

La tavola dei behavior (segue)

Questa tavola mostra che il progetto conta sul gripper per sapere a che punto della sequenza nominale si trova il robot. Un gripper vuoto vuole dire che il robot dovrebbe essere nella fase di raccolta dell’immondizia, oppure sta cercando una lattina o si sta muovendo attorno ad essa. Un gripper pieno vuole dire che il robot è nella fase di deposito.

Il releaser significativo estrae la taglia della regione blu in pixels e la paragona ad una taglia N prefissata. Se la regione è maggiore o uguale a N allora il robot è abbastanza vicino al bidone e può gettare la lattina.

La tavola dei behavior (segue)

Ci sono due problemi con la tavola dei behavior.

  • Il primo è che essa non mostra la sequenza o il flusso di controllo chiaramente.
  • Il secondo è come fa il progettista a rappresentare graficamente questi behavior?

Qui è dove un FSA può essere particolarmente utile.

Esso permette al progettista di saldare le varie sequenze e rappresentare il progetto dei behavior graficamente.
Nella slide successiva è mostrato un FSA equivalente alla tabella.

L’FSA permette di esprimere la sequenza dei behavior. Questo avviene al prezzo di non poter mostrare, con precisione, come la sequenza vada implementata, incoraggiando così il progettista a creare stati interni.

Tavola dei behavior

Tavola dei behavior


FSA

FSA per il problema dello spazzino

FSA per il problema dello spazzino


FSA


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