Mobile Robots Running Tuple
Support
Implementazione di un semplice middleware
per la gestione della informazione di stato
globale in una colonia di robots
Coordinazione di Robots

Problema:
colonia di robots (agenti) con esigenza di mantenere una
informazione globale (o stato globale) al fine di agire
complessivamente in modo coordinato.

?
?
?
?
?
?
Analisi del problema (I)

Capacità di comunicazione:

alcuni nodi sono connessi direttamente, altri no
(es. a causa della morfologia del territorio)
...0100111...
Analisi del problema (II)

Capacità di comunicazione:

La capacità di comunicazione, intesa come
relazione sull’insieme dei robots, è perciò
rappresentabile attraverso un grafo che
connette con archi solo i nodi che possono
comunicare direttamente
R8
R1
R9
R4
R5
R2
R10
R7
R3
R6
R11
Analisi del problema (III)

Capacità di comunicazione:


a ciò va aggiunto il fatto che i robots sono mobili e
quindi la relazione di connessione diretta varia nel
tempo in modo non predicibile.
HP:

per ogni nodo esiste sempre un cammino di archi
che lo connette ad un qualunque altro.


non partizionamento nel tempo della rete per permettere
la coordinazione tramite scambio di informazioni
Per queste caratteristiche l’interconnessione
analizzata rappresenta un particolare tipo di
MANET
Comunicazione

Modalità di comunicazione:

Fornita
dalla
relazione
Necessità
di
coordinare
gli agenti


diretta: limitata ai nodi vicini, non necessita di
coordinamento
indiretta (oltre l’insieme dei nodi in connessione
diretta): necessita del coordinamento delle entità
del sistema. Necessaria per permettere ad un
robots di influenzare il comportamento della
colonia.
globale: caso limite della comunicazione indiretta.
Permette ad un robot di notificare la sua
informazione all’intera colonia.
Semplice esempio (I)

GOAL:


AGENTI del sistema:





estrazione di ferro e nichel
2 robot specializzati in estrazione di ferro
1 robot specializzato in estrazione di nichel
1 robot specializzato in riparazione, manutenzione
tutti i robot con capacità esplorative
SITUAZIONE INIZIALE:

robots collocati in un territorio vasto e non noto
Semplice esempio (II)
I robots acumulano
informazioni relative
al territorio e al loro
funzionamento
I robots decidono
quale parte della
loro informazione
sia utile condividere
con la colonia
La mappa globale
deve essere nota a
tutti e aggiornata
nel tempo
Semplice esempio (III)

Conclusioni:



Ogni robots accumula informazioni durante
l’esplorazione del territorio
Emerge la necessità di condividere parte
dell’informazione raccolta dai robots al fine di
ottenere coordinazione globale (nell’esempio
tramite la mappa globale)
Informazione globale (mappa) intesa come
informazione comune a tutti gli agenti

L’informazione una volta identificata come stato globale
deve perciò appartenere non ad un nodo specifico ma a
tutta la colonia
Stato e spazi di tuple

Uno spazio di tuple è in grado di modellare un
insieme di informazioni, strutturate secondo una
relazione nota, di diversa natura, e quindi si presta
anche per modellare l’informazione di stato dei
robots


Soluzione in accordo ad altre proposte per la modellazione
di informazioni in reti MANET
Particolarmente indicato per il disaccoppiamento indotto in
tempo e conoscenza reciproca
S
1
1
3
8
8
9
8
5
8
3
7
5
7
7
7
1
1
2
7
7
Stato e spazi di tuple


Modello di riferimento: LINDA
Altri modelli adottati in ambito MANET:

GVDS-based systems



GVDS intesa come struttura dati condivisa fra i nodi,
visione globale della informazione (tuple space)
presente sulle singole entità
LIME core idea: Transparent Context Maintainace

spazio di tuple globale come partizionato sui nodi e transient
sharing come meccanismo per ottenere visione globale


LIME, XMiddle, etc.
ottimo funzionamento per i nodi vicini, mancanza di pattern per
la diffusione globale di informazione
TOTA?
TOTA: tuple on the air

La tupla è definita come una coppia:

T=(P,C)



P: regole di propagazione
C: contenuto
Attraverso una copia del middleware presente
su ogni nodo (interfaccia standard) la tupla
può:

Utilizzo API del
nodo




decidere se entrare nel nodo
modificare il proprio contenuto C
modificare le regole di propagazione P
modificare l’ambiente locale del nodo
propagarsi verso i vicini
Side effects
sulla tupla
Side effects sul
nodo
TOTA: tuple on the air



In TOTA la tupla è responsabile della propria
propagazione e degli effetti che genera nei nodi
visitati
Concettualmente quindi essa viene iniettata
attraverso alla rete non appartenendo quindi ad un
nodo specifico
Questo modello è concettualmente in accordo
all’idea di stato globalmente condiviso che si vuole
realizzare per il coordinamento dei robots
P RULES
1
1
3
1
Realizzazione di un semplice
Middleware basato su TOTA

Il middleware è composto in tre parti distinte:

ENGINE o Tuple Support: presente sul nodo e accessibile alle
tuple

Componente standard, si deve occupare di:




Tuple base da cui ereditare:

Tupla come cuore del middleware, depositaria delle funzionalità
(meccanismi e politiche)



Esecuzione della tupla
Supporto per le modifiche sul nodo
Supporto alla propagazione
Ereditarietà come strumento per definire nuovi meccanismi e
politiche
Forte incapsulamento e quindi flessibilità nell’aggiunta di nuove
caratteristiche
API vere e proprie che presuppongono l’esistenza di tuple ad
hoc per la loro realizzazione
Realizzazione di un semplice
Middleware basato su TOTA

Definizione della classe base per la
propagazione di informazioni:
Riferimento all’ENGINE
locale del nodo che
fornisce le API di
supporto alla tupla
RunningTuple
tupleSupport: tupleSupport
void init(TupleSupport t)
Regole di propagazione P
sotto forma di codice
eseguito sul nodo
void propagate()
Legame
tra la
tupla e il
supporto
Realizzazione di un semplice
Middleware basato su TOTA

Contenuto
informativo
C
Definizione delle classi depositarie della
gestione del contenuto informativo:
Tuple
QueryTuple
attributes: attributesType
void accept(QueryTuple q)
Meccanismo del double
dispatch per l’accesso
ad una istanza di tupla da
parte di una QueryTuple
attributes: attributesType
void visit(Tuple t)
Contiene le regole
di match M
Oggetto depositario
della interrogazione
dello spazio di tuple.
Realizzazione di un semplice
Middleware basato su TOTA

Realizzazione delle API di alto livello




out: operazione di inserimento di una tupla di
stato nello spazio
inRead: lettura della tupla dallo spazio globale
in: prelievo della tupla dallo spazio globale
in e out simili alle primitive di Linda:

out: incapsulata in una RunningTuple


T=(C,P) {content; propagation rules}
in: incapsulata in una QueryTuple

T=(C,M) {content; matching rules}
Realizzazione di un semplice
Middleware basato su TOTA

out()

Necessita della coordinazione fra i nodi per la diffusione
globale della informazione:


inRead()

Azione locale sul repository delle tuple che rappresenta lo
spazio comune a tutti gli agenti


floading e stato sul nodo
in()

pattern visitor e iterazione sugli oggetti Tuple utilizzando le
regole M della tupla di in()
Rispetto alla inRead necessita di coordinazione per
aggiornamento dello spazio di tuple di tutte le entità


protocollo ad hoc basato su gestore di tupla e notifica globale
del consenso al prelievo da parte di un nodo specifico
induce un forte coordinamento nel gruppo dei robots
(sincronizzazione per accesso in mutua esclusione)
API(I): out()

Diffusione di una tupla tramite il meccanismo
implementato per la primitiva out()
sender
connection
accepted
not accepted
API(II): in()

Diffusione della richiesta e del consenso alla
operazione di in()
in()
gestore tupla
connection
query
consensus
not accepted
Realizzazione di un semplice
Middleware basato su TOTA

Si è ottenuto:


ad alto livello una interfaccia di tipo Linda
il compito di realizzare le specifiche richieste dalla
primitiva è affidato alle tuple dalla quale sono
state generate:



diffusione delle informazioni da parte delle tuple di out
ricerca del corrispondente attraverso un pattern interno
specificato da parte delle tuple di in
Il middleware garantisce in modo trasparente
che lo stato globale sia replicato su ogni
nodo, realizzando la struttura informativa
richiesta
Possibili estensioni del modello

Il modello Linda può essere ancora meglio
mappato nelle tuple del Middleware al fine di
renderlo ancora più flessibile:

LindaTuple:

T=(C,P,M,O)





C: content
P: propagation rules (sia per le in che per le out)
M: matching rules
O: output rules
Flessibilità, context-awarness, adattatività
TOTA come modello di
mobilità (I)



In definitiva cosa distingue il modello TOTA rispetto ad altri
modelli? Qual è la differenza rispetto ad un sistema MA?
Mobile Agent: insieme di codice, dati e stato di esecuzione in
grado di decidere autonomamente di migrare da un nodo ad
un altro con possibilità di riprendere la esecuzione da dove era
terminata (strong-weak mobility)
In TOTA l’elemento base è la TUPLA, essa trasporta:

C
dati



riferimento ad un automatismo (automa) comune a tutti i nodi
che opera in funzione dello stato interno della tupla stessa e dello
stato presente sul nodo

P
generici (es: attributi in accordo ad una relazione)
stato della tupla modificato durante la propagazione, dipendente
dalle precedenti propagazioni della stessa
nuovo _ stato _ nodo  FAUTOMA ( stato _ tupla, stato _ nodo)
nuovo _ stato _ tupla  F ' AUTOMA ( stato _ tupla, stato _ nodo)
side _ effect _ sul _ nodo  F '' AUTOMA ( stato _ tupla, stato _ nodo, dati)
propagazio ne  F ''' AUTOMA ( stato _ tupla, stato _ nodo, dati)
TOTA come modello di
mobilità (II)

Alla creazione della tupla avviene un legame tra la
informazione contenuta nella stessa e l’automa
depositario della propagazione



implementazione di una classe specifica che si appoggia ad
un automa specifico (contenuto nel codice della classe
stessa)
ereditarietà da altre ‘classi automa’ predefinite con
meccanismi e politiche base
La tupla contiene solo lo stato del proprio automa,
modificato durante il trasferimento sul nodo. Il codice
è presente su ogni nodo, essendo le classi note a
tutti gli agenti

T=(C,P) -> T=(C,S0,*A)


basso overhead nella diffusione della tupla!
paradigma ad oggetti per ottenere buona flessibilità
nell’aggiunta di altri meccanismi
Sviluppi futuri

Estensione del middleware:



Supporto del modello di tupla generale
(LindaTuple)


nuove API (join,etc.)
nuovi meccanismi (maggiori garanzie, etc.)
Ridefinizione delle classi base
Verifica dei modelli di stato implementabili,
anche in riferimento alla nozione di tempo fin
qui trascurata (estensione real-time?)