Universita degli Studi di PadovaDipartimento di Ingegneria dell’Informazione

Tesi di Laurea Specialistica in Ingegneria dell’Automazione

Controllo di Veicoli

Anolonomi su Ruota

Relatore: Prof. Luca Schenato

Laureando: Alessandro Agnoli

Padova, 2 ottobre 2007

ii

Indice

Sommario v

1 Pianificazione del movimento in ambienti privi di ostacoli 11.1 Introduzione . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11.2 Definizione del problema . . . . . . . . . . . . . . . . . . . . . . . 4

1.2.1 Approccio generale . . . . . . . . . . . . . . . . . . . . . . 41.2.2 Esempio: il problema di guida di un veicolo di Dubins . . . 5

1.3 Simmetrie e primitive di movimento . . . . . . . . . . . . . . . . . 71.3.1 Definizione di invariante . . . . . . . . . . . . . . . . . . . 71.3.2 Primitive di movimento . . . . . . . . . . . . . . . . . . . 81.3.3 Concatenazione di primitive di movimento . . . . . . . . . 91.3.4 Equilibri relativi e manovre . . . . . . . . . . . . . . . . . 101.3.5 Simmetrie e primitive di movimento per un veicolo di Dubins 11

1.4 Automa delle manovre . . . . . . . . . . . . . . . . . . . . . . . . 131.4.1 Definizione dell’automa delle manovre (MA) . . . . . . . . 131.4.2 Piani di movimento . . . . . . . . . . . . . . . . . . . . . . 141.4.3 Esempio: automa delle manovre di un veicolo di Dubins . 16

1.5 Pianificazione del movimento basata sulle manovre . . . . . . . . 231.5.1 Controllabilita di un MA . . . . . . . . . . . . . . . . . . . 231.5.2 Esistenza di soluzioni “ottime” e loro determinazione . . . 241.5.3 Pianificazione del movimento per un veicolo di Dubins . . 26

1.6 Costruzione dell’anello di controllo ad alto livello . . . . . . . . . 271.6.1 Difficolta della stabilizzazione di un sistema non lineare . . 281.6.2 Controllo model-predictive di un veicolo di Dubins . . . . . 311.6.3 Simulazione dell’algoritmo su un uniciclo . . . . . . . . . . 37

1.7 Conclusioni . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 41

2 Pianificazione del movimento in ambienti con ostacoli 432.1 Introduzione . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 432.2 Definizione del problema e sue proprieta . . . . . . . . . . . . . . 452.3 Algoritmo per la pianificazione del movimento . . . . . . . . . . . 46

2.3.1 Un algoritmo per guidare un veicolo di Reeds-Shepp at-traverso un ambiente con ostacoli . . . . . . . . . . . . . . 46

2.3.2 L’algoritmo di Dijkstra . . . . . . . . . . . . . . . . . . . . 47

iii

2.3.3 Un algoritmo per guidare un veicolo di Dubins attraversoun ambiente con ostacoli . . . . . . . . . . . . . . . . . . . 50

3 Rendezvous di molteplici robot mobili 613.1 Introduzione . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 61

3.1.1 Breve panoramica sulla swarm robotics . . . . . . . . . . . 613.1.2 Un problema particolare: il rendezvous . . . . . . . . . . . 64

3.2 Un algoritmo per il rendezvous di robot onnidirezionali . . . . . . 653.2.1 Considerazioni preliminari . . . . . . . . . . . . . . . . . . 653.2.2 Algoritmo di convergenza a un punto . . . . . . . . . . . . 673.2.3 Analisi dell’algoritmo . . . . . . . . . . . . . . . . . . . . . 69

3.3 Un algoritmo per il rendezvous di veicoli di Dubins . . . . . . . . 723.3.1 Considerazioni preliminari sulle traiettorie . . . . . . . . . 723.3.2 Rivisitazione dell’algoritmo proposto da Ando et al. . . . . 743.3.3 Primo metodo per il rendezvous di veicoli di Dubins . . . . 763.3.4 Secondo metodo per il rendezvous di veicoli di Dubins . . . 81

4 Conclusioni 914.1 Risultati ottenuti . . . . . . . . . . . . . . . . . . . . . . . . . . . 914.2 Sviluppi ulteriori . . . . . . . . . . . . . . . . . . . . . . . . . . . 94

A Cenni sui gruppi e le algebre di Lie 97

iv

Sommario

Nell’ultima ventina d’anni il controllo di veicoli non olonomi e stato un campodi ricerca largamente studiato. Almeno due sono le ragioni alla base di questointeresse: anzitutto i veicoli mobili su ruota costituiscono il mezzo di trasportoattualmente piu diffuso, in secondo luogo le equazioni della cinematica di sistemianolonomi sono fortemente non lineari, e sono dunque di particolare interesse perlo sviluppo e l’applicazione della teoria dei controlli non lineari.

Questa tesi affronta tre tematiche relative al controllo di veicoli anolonomisu ruota. Nel primo capitolo si considera il problema della pianificazione e delcontrollo del movimento di un singolo veicolo mobile in ambienti privi di ostacoli.La soluzione proposta prevede l’impiego di un controllore ibrido, che utilizziad anello chiuso l’informazione proveniente da sensori propriocettivi di bordo eabbia la possibilita di ricevere la comunicazione della propria posizione da unsistema di localizzazione globale (GPS) esterno, eventualmente con frequenzadi campionamento bassa e non uniforme, per correggere la propria traiettoria.Le traiettorie generate dal controllore costituiscono una famiglia finita di curve,ma sufficiente a garantire l’ottimalita nel senso della minima lunghezza. Latecnica proposta non prevede pero alcuna onerosa operazione di minimizzazionenumerica, come accade invece per i metodi di controllo ottimo classici, ed e quindiapplicabile a sistemi con capacita computazionali limitate.

Il controllore proposto e integrato, nel secondo capitolo, con un regolatoredi alto livello per la pianificazione di cammini privi di collisioni per macchinedi Dubins che si muovano in ambienti con ostacoli poligonali. Il regolatore dialto livello utilizza unicamente l’informazione esterocettiva fornita dal sistema dilocalizzazione globale, determina un cammino privo di collisioni verso un pun-to desiderato e comunica al veicolo solo alcune configurazioni intermedie, allastregua di pietre miliari. E il controllore a bordo del veicolo descritto nel primocapitolo a ricostruire il cammino nella sua interezza a partire dalle configurazioniintermedie comunicategli. Si vedra che, sotto precise ipotesi, il cammino che siottiene e quello ottimo per veicoli di Dubins.

Il terzo e ultimo capitolo affronta invece il tema del coordinamento di piuveicoli mobili e, in particolare, il problema del rendezvous di veicoli di Dubins.Il fatto di avere molteplici agenti in moto in uno stesso ambiente rende la pia-nificazione centralizzata del movimento un approccio poco scalabile. Si rinunciaqui all’impiego di sistemi di localizzazione globali e si assume invece che ciascunveicolo disponga a bordo di un proprio sensore per il rilevamento della posizione

v

relativa di altri agenti entro un raggio limitato. Si propone un metodo di ren-dezvous per la convergenza di tutti i veicoli entro un intorno di raggio dell’ordinedi due volte quello di minima curvatura. Si dimostra in simulazione che taletecnica e rapida e robusta ad errori di rilevamento da parte dei sensori di bordo.

vi

Capitolo 1

Pianificazione del movimento inambienti privi di ostacoli

1.1 Introduzione

Il controllo di veicoli mobili anolonomi e da anni un campo di ricerca moltoattraente per almeno due ragioni: pressoche ogni veicolo, aereo, terrestre o mari-no, puo essere modellato, almeno in prima approssimazione, come un veicoloanolonomo, inoltre le equazioni della cinematica di sistemi anolonomi sono forte-mente non lineari e pertanto di particolare interesse per lo sviluppo della teoriadei controlli non lineari.

Uno dei problemi principali che devono essere risolti per i robot mobili e iveicoli autonomi e la pianificazione del movimento per raggiungere un obiettivoda una data condizione iniziale. Il piano di movimento deve soddisfare un as-segnato sistema di equazioni differenziali e di vincoli algebrici, rappresentanti,ad esempio, vincoli anolonomi per la dinamica del sistema, limiti di ampiezzae banda delle uscite degli attuatori e condizioni dettate da motivi di sicurezza.Ulteriori vincoli possono essere imposti dalla presenza di ostacoli nell’ambientein cui il veicolo si trovi ad operare. Si assumera in questo capitolo l’assenza diostacoli, che saranno invece introdotti nel seguito. Spesso si vuole, inoltre, cheil piano di movimento faccia un buon uso delle risorse disponibili, ottimizzandocioe una funzione obiettivo che dia una misura significativa delle prestazioni.

La dinamica dei veicoli autonomi e inerentemente continua ed e descritta daequazioni differenziali ordinarie, tipicamente non lineari. D’altra parte i con-trollori sono quasi sempre digitali, per cui il sistema di controllo complessivorisultera discreto. La regolazione a basso livello delle singole parti meccanichedel veicolo richiede ai controllori una banda tipicamente molto elevata, tanto chein alcuni casi si puo considerare che i regolatori di basso livello condividano lanatura continua del processo. I livelli di regolazione superiori si possono inveceprogettare come agenti dotati di capacita logiche, in grado di prendere decisioniin uno spazio di stato discreto, a una frequenza notevolmente piu bassa dei pri-mi. I sistemi che includono dinamiche sia continue sia discrete sono chiamati in

1

letteratura sistemi ibridi. Una scelta naturale per la progettazione dei controllidi sistemi ibridi, dunque, e la suddivisione dell’azione di controllo su almeno duelivelli, in modo da poter regolare separatamente le dinamiche continue e quellediscrete.

La distinzione tra controllori di basso e di alto livello e dettata dalla tipolo-gia, dal volume e dalla frequenza di acquisizione dell’informazione sensoriale cheviene utilizzata per la regolazione. I controllori di basso livello operano unaretroazione sulla base dell’informazione sensoriale locale, proveniente cioe datrasduttori propriocettivi on-board, composta di pochi bit e ricevuta ad istan-ti di campionamento brevi e tipicamente equispaziati nel tempo. Al contrarioi controllori di alto livello elaborano maggiori quantita di dati, provenienti dasensori esterocettivi, che possono essere a bordo (ad esempio: sensori di prossi-mita, telecamere, radar o sonar di bordo) oppure off-board (ad esempio: GPS,rete fissa di sensori wireless, postazione radar fissa).

I controllori di alto livello hanno il compito di pianificare il movimento delveicolo, elaborare cioe quello che nel seguito sara detto piano di movimento,mentre quelli di basso livello hanno la funzione di garantire l’inseguimento dellatraiettoria pianificata, rendendo il sistema robusto ad eventuali disturbi esterni ead errori di modello. La progettazione dei controllori di basso livello dipende dalparticolare veicolo e risulta relativamente semplice, poiche tipicamente a bassolivello non compaiono in maniera preponderante le non linearita di cui invecesi deve tenere conto in fase di pianificazione del movimento. Il controllo dellesingole parti meccaniche puo essere molto spesso espletato in maniera piu chesoddisfacente con tecniche di controllo “classiche”. Nel seguito si assumera perciocome preesistente il livello di regolazione piu basso, e si focalizzera l’analisi sulcontrollo ad alto livello per la pianificazione della traiettoria. I requisiti dellalegge di controllo di alto livello sono:

• la possibilita di operare con tempi di campionamento molto lunghi e nonuniformi: l’informazione sensoriale off-board e soggetta a ritardi di comuni-cazione possibilmente aleatori e a eventuali temporanee assenze di comuni-cazione; i sensori off-board sono risorse potenzialmente condivise tra moltiagenti, che non possono essere utilizzate simultaneamente, pertanto ciascunregolatore deve attendere un intervallo di tempo non determinabile a prioriper disporre di informazioni quali, ad esempio, la posizione e l’orientazionedel veicolo sul piano;

• la semplicita: i veicoli mobili sono dotati di capacita computazionali limi-tate

Forse il metodo piu generale e precisamente formulato per affrontare proble-mi di pianificazione del movimento e l’impiego del controllo ottimo. Tuttavianella maggior parte dei problemi di motion-planning, le tecniche di controllo ot-timo soffrono di un elevato carico computazionale, che le rendono inadatte per

2

molte applicazioni in tempo reale, tanto piu se i robot mobili hanno capacitacomputazionali ridotte.

D’altra parte, piloti umani esperti sono in grado di operare efficacemente abordo di veicoli con dinamica altamente complicata ed eventualmente instabile,spesso al limite delle loro condizioni operative. La trattazione che segue e moti-vata, in particolare, dall’osservazione che i piloti umani sono in grado di eseguireacrobazie attraverso la concatenazione di singole manovre ben studiate. Il pre-sente capitolo ha lo scopo di dare una definizione formale di questo concetto,esplorandone le implicazioni nell’ambito della pianificazione del movimento.

L’approccio qui presentato consiste nella cosiddetta quantizzazione del con-trollo [21], [23]. Anziche quantizzare il tempo, lo stato del sistema o i valori diingressi ed uscite, si sceglie un numero finito di traiettorie di controllo, dette pri-mitive di movimento (in inglese motion primitives). Tali primitive sono tra lorocombinate per generare traiettorie ammissibili (in inglese feasible) per il sistema.Le regole di concatenazione sono espresse dal linguaggio generato da un automa.

La trattazione del problema della pianificazione del movimento sara condottain questo capitolo nel contesto piu generale possibile, per mostrare che l’approccioproposto, basato sulla quantizzazione del controllo, e applicabile a sistemi nonlineari generici. A conclusione di ciascuna delle sezioni si applicheranno i risultati,visti nel contesto generale, ad un sistema particolare: la macchina di Dubins.L’analisi di quest’esempio sara condotta di pari passo con la trattazione generale,per aiutare a chiarirla. La scelta del veicolo di Dubins e motivata dalle seguentiragioni:

• quasi tutti i veicoli, terrestri, marini ed anche aerei che volino a quotacostante, possono essere modellati, almeno in prima approssimazione, comeveicoli di Dubins sul piano;

• si tratta di un modello largamente studiato in letteratura, poiche, da unlato, e descritto da equazioni semplici, dall’altro e fortemente non lineare;tuttavia quasi tutti gli studi condotti sinora presumono la regolazione atempo continuo, mentre il controllo digitale di un veicolo di Dubins e statoscarsamente considerato;

• il modello di Dubins si puo applicare con ottima approssimazione, in par-ticolare, agli unicicli e-puck, in dotazione al laboratorio Navlab del diparti-mento d’Ingegneria dell’Informazione dell’Universita di Padova: il controllodel movimento degli e-puck e il primo passo per studi futuri di roboticacoordinata.

3

1.2 Definizione del problema

1.2.1 Approccio generale

Sia dato un sistema dinamico tempo-invariante e non-lineare S descritto da uninsieme di equazioni differenziali ordinarie (ODE) del tipo

x(t) :=d

dtx(t) = f(x(t), u(t)) (1.1)

dove lo stato x appartiene alla varieta n-dimensionale X e l’ingresso di controllou prende valori nell’insieme U ⊆ Rm (con m < n).

Sotto opportune condizioni su f (limitatezza e dipendenza localmente lips-chitziana dagli argomenti), data una legge di controllo in catena aperta continuaa tratti µ : [0, tf ] → U , la ODE (1.1) puo essere integrata per calcolare lo statodel sistema ad ogni istante t ∈ [0, tf ], come funzione delle condizioni iniziali:

x(t) = ϕµ(x(0), t),

dove la funzione ϕµ descrive l’evoluzione di stato del sistema dinamico tempoinvariante x(t) = fµ(x(t), t) = f(x(t), µ(t)), corrispondente a (1.1) sotto l’azionedell’assegnata legge di controllo in catena aperta µ. Dati una condizione inizialex(0) = x0 e un insieme finale desiderato F ⊂ X , il problema della guida (ininglese, steering problem) puo essere formulato come quello di trovare una leggedi controllo µ tale che x(tf ) = ϕµ(x0, tf ) = xf ∈ F , per qualche tf > 0.

Nelle applicazioni pratiche, la legge di controllo deve anche soddisfare uninsieme di vincoli dettati, ad esempio, da condizioni di sicurezza e dalla satu-razione degli attuatori. Tali condizioni possono essere codificate in un sistema didisuguaglianze, che coinvolgono lo stato e l’ingresso di controllo, della forma

F (x(t), u(t)) ≤ 0 ∀t ∈ [0, tf ], (1.2)

dove F e una funzione vettoriale e la disuguaglianza e da intendersi componenteper componente. Nel seguito ci si riferira a (1.2) come ai vincoli d’inviluppooperazionale. Tipicamente questi vincoli condividono con il sistema S le stesseproprieta di invarianza, sia rispetto al tempo, sia in relazione all’azione di ungruppo. (Le proprieta di invarianza di S saranno discusse nella sezione seguente).

Come indice di qualita di un piano di movimento, si considera una funzionedi costo del tipo

J(x, u) =

∫ tf

0

γ(x(t), u(t))dt. (1.3)

Cosı come per i vincoli, si assume che anche la funzione di costo incrementale γgoda delle stesse proprieta di invarianza di S.

In generale il problema della pianificazione del movimento include, oltre a(1.2), anche vincoli puntuali nel tempo, quali l’aggiramento di ostacoli, o inte-grali, come ad esempio limiti di carburante o delle batteria. Il problema dell’ag-giramento di ostacoli sara affrontato nel prossimo capitolo, mentre la trattazionedi vincoli di natura integrale esula dagli scopi di questa tesi.

4

Per il momento si affrontera il problema della pianificazione del movimento incatena aperta. L’anello di retroazione ad alto livello sara introdotto nel seguito.

1.2.2 Esempio: il problema di guida di un veicolo di Du-bins

A fronte della trattazione generale del problema, appena formalizzato, della gui-da di un sistema non lineare S, si prendera in considerazione, al termine di tuttele sezioni di questo capitolo, un modello dinamico notevole: il veicolo di Dubins.L’analisi di un’applicazione particolare degli argomenti trattati nel presente capi-tolo ha il valore di un esempio e si auspica possa rendere piu chiare le nozioniintrodotte nel contesto generale. D’altra parte si vuole cosı mostrare che l’ap-proccio adottato per il controllo di veicoli mobili su ruota, argomento di questatesi, non e limitato a questa sola applicazione, ma puo essere esteso efficacementea sistemi dinamici non lineari generici.

Il veicolo e modellato come una regione R in movimento rigido sul piano,alla quale e solidale un vettore unitario v: l’orientazione. Essendo il movimentorigido, il veicolo ha tre gradi di liberta: le coordinate x1 e x2 danno la posizionesul piano di un qualche punto di R (ad esempio, il centro di massa), e θ de-nota l’angolo che il vettore di orientazione v forma con l’asse x1 (figura 1.1).Relativamente a tali coordinate, il vettore v e dato da v = (cos θ, sin θ).

Figura 1.1. Veicolo di Dubins

Si assumera che il veicolo possa muoversi unicamente nel verso di v, convelocita u1v e u1 ∈ [0, vmax]. In altri termini il veicolo puo andare avanti ma nonindietro. La motivazione di questa scelta e di natura pratica: la maggior parte deiveicoli terrestri ed acquatici, pur avendo la possibilita di retrocedere, ha un versodi moto preferenziale fissato sia dalla locomozione (automobili e navi possonoprocedere all’indietro solo a velocita ridotta) sia dal campo visivo del conducente

5

(in retromarcia la visibilita e ridotta). In particolare, i robot mobili e-puck, chesono stati scelti come modello fisico di riferimento per questa tesi, sono dotati diuna telecamera fissa: per futuri sviluppi, sembra consigliabile che l’algoritmo dicontrollo del movimento li faccia avanzare in quella direzione. Come si vedra nelseguito, la limitazione del moto a un unico verso consente, poi, di semplificare lacaratterizzazione della famiglia parametrica di curve contenente le traiettorie dilunghezza minima sul piano. E tuttavia possibile estendere in maniera diretta latrattazione seguente al caso di veicoli che possono muoversi avanti e indietro.

Il veicolo puo anche cambiare direzione; si indichera con u2 la velocita ango-lare: u2 = θ. Lo stato del sistema e dunque la terna (x1, x2, θ), lo spazio di statoe X = R2×S1, dove S1 e l’insieme dei punti sulla circonferenza unitaria, [0, 2π)1,e U = [0, vmax]× R.

In questo caso l’equazione generale (1.1) prende la forma seguente:

x1 = u1 cos(θ)

x2 = u1 sin(θ) (1.4)

θ = u2.

Si impone inoltre che il raggio di curvatura sia limitato inferiormente: ilvincolo (1.2) e dunque qui semplicemente

u1(t)

u2(t)≥ rmin ∀t ∈ [0, tf ]. (1.5)

Il modello appena descritto e noto in letteratura con il nome di veicolo di Dubins(in inglese Dubins’car), dal nome del matematico L.E. Dubins che nel 1957 pub-blico lo studio [19] sulle traiettorie di lunghezza minima per questo sistema. Unveicolo di Dubins che puo muoversi avanti e indietro e invece detto di Reeds-Shepp[45].

Sia il veicolo di Dubins, sia quello di Reeds-Shepp sono anolonomi. Il fatto chesiano controllabili2 e intuitivo dal punto di vista geometrico; una dimostrazioneformale richiede invece di ricorrere al concetto di rango di un’algebra di Lie. Sirimanda a [47] e a [51] per approfondimenti. Si dimostra inoltre che, mentre ilveicolo di Reeds-Shepp e localmente controllabile in tempo breve3, la macchinadi Dubins non lo e.

1Sarebbe piu corretto scrivere X ' R2×S1 per indicare che lo spazio X delle configurazionidi un veicolo potrebbe essere un qualsiasi spazio omeomorfo a R2 × S1, come ad esempio ilgruppo euclideo speciale

SE(2) ={(

R p0 1

)∣∣∣∣ R ∈ SO(2), p ∈ R2

}

oppure SO(2)× R2, dove SO(2) e il gruppo delle rotazioni sul piano2Un sistema si dice controllabile se per ogni coppia di punti p e q nel suo spazio di stato X

esiste una traiettoria che va da p a q in tempo finito3Un sistema si dice localmente controllabile in tempo breve (in inglese, small-time locally

controllable) da un punto p, se per ogni tempo T > 0 esiste un intorno B(T, p) di p i cui puntisono tutti raggiungibili da p in un tempo non superiore a T .

6

Assegnati un punto iniziale e uno finale, l’indice di costo che si vuole mini-mizzare e il tempo tf richiesto per compiere la traiettoria; quindi (1.3) si riducequi a

J =

∫ tf

0

dt = tf .

Si noti che il problema a tempo minimo per il modello di veicolo sopra descrittoe equivalente al problema del cammino minimo

J =

∫ tf

0

√x1(t)2 + x2(t)2 dt

nell’ipotesi, formulata nell’articolo originale di Dubins [19], che u1 ∈ {vmax} ={1}, anziche u1 ∈ [0, vmax], come assunto qui e in [51].

1.3 Simmetrie e primitive di movimento

1.3.1 Definizione di invariante

Una proprieta geometrica fondamentale, che caratterizza la dinamica di moltisistemi meccanici di interesse, compresi la maggior parte dei veicoli e dei robotmobili, e l’invarianza rispetto a una certa classe di trasformazioni sullo stato delsistema. Per dare una descrizione formale e, al tempo stesso, generale di questiconcetti si fara riferimento nel seguito alla teoria dei gruppi e delle algebre di Lie,una cui prima definizione, corredata di esempi utili per la trattazione seguente,si trova in appendice.

Definizione 1.1. Si consideri il gruppo di Lie di dimensione finita G, con ele-mento identita e. Un’azione (sinistra) del gruppo G sulla varieta X degli statidel sistema e una mappa regolare (in inglese smooth) Ψ : G × X → X , tale che

1. Ψ(e, x) = x ∀x ∈ X

2. Ψ(g, Ψ(h, x)) = Ψ(gh, x) ∀g, h ∈ G e ∀x ∈ X .

Si usera spesso, per semplicita di notazione, la scrittura Ψg(x) per indicareΨ(g, x).

Definizione 1.2. Il sistema dinamico S, descritto da (1.1), si dice invarianterispetto all’azione del gruppo Ψ, o, equivalentemente, che G e un gruppo disimmetria per S, se per ogni g ∈ G, x0 ∈ X , t ∈ [0, tf ], e per ogni legge dicontrollo continua a tratti µ : [0, tf ] → U , vale la seguente uguaglianza:

Ψg(ϕµ(x0, t)) = ϕµ(Ψg(x0), t).

7

In altri termini, G e un gruppo di simmetria per S se la sua azione sullo statocommuta l’evoluzione temporale. L’invarianza implica inoltre che se una curvat 7→ (x(t), u(t)) e un integrale di (1.1), allora lo e anche t 7→ (Ψg(x(t)), u(t)), perogni g ∈ G. Si noti che la tempo-invarianza di S implica che l’asse reale, conl’operazione di addizione, e un gruppo di simmetria, agente su S per traslazionetemporale.

L’invarianza rispetto all’azione di un gruppo fornisce una relazione di equi-valenza fra traiettorie. Si dice che due traiettorie sono equivalenti se possonoessere sovrapposte tramite una traslazione temporale e l’azione di un gruppo disimmetria G. Formalmente:

Definizione 1.3. Due traiettorie π1 : t ∈ [ti,1, tf,1] 7→ (x1(t), u1(t)) e π2 : t ∈[ti,2, tf,2] 7→ (x2(t), u2(t)) si dicono equivalenti se tf,1− ti,1 = tf,2− ti,2 ed esistonog ∈ G e T ∈ R tali che (x1(t), u1(t)) = (Ψg(x2(t−T )), u2(t−T )) ∀t ∈ [ti,1, tf,1].

1.3.2 Primitive di movimento

Si considerino il sistema tempo-invariante S, invariante rispetto all’azione di ungruppo G, e una traiettoria π : t ∈ [0, tf ] → X × U soddisfacente (1.1) e (1.2).Una primitiva di movimento e la classe delle traiettorie equivalenti a π. Con unabuso di notazione, si utilizzera il simbolo π per indicare anche la primitiva dimovimento corrispondente, ovvero la classe di tutte le traiettorie equivalenti aπ. Con |π| si denota la durata temporale di π. P(S,G) indica invece l’insiemedi tutte le primitive di movimento per il sistema S con gruppo di simmetria G.

Osservazione 1.1. Nell’ipotesi che i vincoli (1.2) condividano le proprieta d’in-varianza di S, ovvero,

F (x, u) = F (Ψg(x), u) ∀g ∈ G,

si ha che se una traiettoria soddisfa i vincoli dell’inviluppo operazionale, altret-tanto fanno tutte le traiettorie ad essa equivalenti. Quest’assunzione e verificatatipicamente per i limiti degli attuatori e per l’inviluppo operazionale del veicolo(ad esempio, per i vincoli sul minimo raggio di curvatura).

Osservazione 1.2. Sotto analoghe condizioni sulla funzione di costo incremen-tale γ, ossia,

γ(x, u) = γ(Ψg(x), u) ∀g ∈ G,

tutte le istanze di una primitiva di movimento hanno lo stesso costo. Quest’as-sunzione e soddisfatta in una vasta classe di problemi di controllo ottimo diinteresse, tra cui quelli del tempo minimo, del cammino minimo e della minimaenergia.

In assenza di vincoli sull’inviluppo operazionale (1.2), una primitiva potrebbeessere ottenuta semplicemente applicando un’arbitraria legge di controllo µ con-tinua a tratti al sistema S, a partire da una qualsivoglia condizione iniziale, per

8

un intervallo temporale di durata finita. La traiettoria risultante potrebbe esserepercio ottenuta integrando (1.1), oppure eseguendo un esperimento sul sistemafisico. Se invece sono presenti dei vincoli di tipo (1.2), le traiettorie valide devonosottostare a queste limitazioni: ovviamente gli esperimenti devono essere limitatiall’inviluppo dato da (1.2) per ragioni di sicurezza. Si noti infine che ogni fram-mento di traiettoria ammissibile definito su un intervallo temporale compatto daesso stesso una primitiva valida.

1.3.3 Concatenazione di primitive di movimento

Il metodo di pianificazione di traiettorie qui presentato si basa sulla selezionedi una famiglia di primitive di movimento, che vengono combinate per formaredelle traiettorie (coppie stato e ingresso di controllo), che soddisfino i vincoliimposti dal problema di guida. L’operazione di combinazione di due primitive performarne una terza sara detta concatenazione. Al fine di mantenere la validitadelle traiettorie, le primitive non possono essere concatenate ad arbitrio, masi deve accertare che siano verificate delle condizioni di compatibilita. Nellospecifico, si deve verificare che lo stato finale della prima primitiva coincida conlo stato iniziale della seconda, modulo un’azione del gruppo G.

Definizione 1.4. Siano date due primitive di movimento π1 : t ∈ [0, T1] 7→(x1(t), u1(t)) e π2 : t ∈ [0, T2] 7→ (x2(t), u2(t)). Si dice che π1 e π2 sonocompatibili, e si scrive π1Cπ2, se esiste g12 ∈ G tale che x1(T1) = Ψ(g12, x2(0))

Si noti che C non e simmetrica.

Definizione 1.5. Se π1Cπ2, la concatenazione di π1 e π2 e definita come π1π2 :[0, T1 + T2] → X × U , con

π1π2(t) =

{(x1(t), u1(t)), se t ≤ T1;(Ψ(g12, x2(t− T1)), u2(t− T1)), altrimenti.

Proposizione 1.1. L’insieme P(S,G) e chiuso rispetto alla concatenazione diprimitive compatibili, ovvero, se π1, π2 ∈ P(S,G) e π1Cπ2, allora π1π2 ∈ P(S,G).

Dimostrazione: Poiche π1π2 coincide con π1 sull’intervallo [0, T1], c’e sola-mente da provare che e continua in t = T1 e che soddisfa (1.1) e (1.2) su[T1, T1+T2]. La continuita in t = T1 e garantita dalla condizione di compatibilita:

limt→T−1

π1π2(t) = π1(T1)

e

limt→T+

1

π1π2(t) = limt→T+

1

Ψ(g12, π2(t− T1)) = Ψ(g12, π2(0)) = π1(T1).

9

L’ammissibilita per t ∈ [T1, T1 + T2] e conseguenza dell’invarianza rispetto allatraslazione temporale e all’azione del gruppo G:

x12(t) = ϕµ12(x12(0), t),

che per t′ = t− T1 > 0 si puo riscrivere come di seguito:

x12(t′) = ϕµ2(x1(T1), t

′) = ϕµ2(Ψ(g12, x2(0)), t′) =

= Ψ(g12, ϕµ2(x2(0), t′)) = Ψ(g12, x2(t′)).

Sostituendo nuovamente t = T1+t′, la formula precedente mostra che x12 soddisfa(1.1) e (1.2) per t ∈ [T1, T1 + T2]. ¤

1.3.4 Equilibri relativi e manovre

Si introdurranno ora due classi di primitive di movimento, che possono essere uti-lizzate per costruire una ”libreria” per la pianificazione del movimento: equilibrirelativi e manovre. Intuitivamente, se l’insieme delle primitive e finito, dato unpunto iniziale, l’insieme dei punti raggiungibili attraverso la combinazione di unnumero finito di tali primitive sara discreto. Se invece si desidera che l’insiemeraggiungibile con un numero finito di primitive sia continuo, si deve considerareuna libreria contenente infinite primitive. Per mantenere una descrizione finitadella libreria, si prendera in considerazione una particolare classe parametrica diprimitive di movimento: quella dei movimenti in stato stazionario, detti ancheequilibri relativi o traiettorie in assetto (in inglese trim trajectories). Durantel’esecuzione di tali primitive gli ingressi di controllo sono mantenuti costanti.

Definizione 1.6. Un equilibrio relativo e una primitiva di movimento α : t ∈[0, T ] 7→ (xα(t), uα(t)) tale che

{xα(t) = Ψ(exp(ξαt), xα(0))uα(t) = uα

∀t ∈ [0, T ]

dove ξα e un elemento di g, algebra di Lie di G.

In altre parole gli equilibri relativi corrispondono ad evoluzioni finite del sistemalungo campi vettoriali invarianti a sinistra. Si indichera l’insieme degli equilibrirelativi per il sistema S con gruppo di simmetria G come E(S,G). L’esempio piusemplice di equilibrio relativo e un punto di equilibrio.

Dato un equilibrio relativo α, si puo costruire una famiglia di primitiveparametrizzata dallo scalare τ ≥ 0 allargando o restringendo il dominio didefinizione:

α(τ) : t ∈ [0, τ ] 7→ (Ψ(exp(ξαt), xα(0)), uα). (1.6)

Sia Eα = {α(τ), τ ≥ 0} ⊂ E(S,G) l’insieme di tutti gli equilibri relativi ottenuticambiando il dominio di un equilibrio relativo α. Lo scalare non negativo τ saradetto coasting time ed indica la durata dell’intervallo in cui il sistema e lasciatoevolvere lungo il corrispondente campo vettoriale invariante a sinistra.

10

Definizione 1.7. Si definisce manovra una primitiva compatibile, a sinistra e adestra, con un equilibrio relativo, ovvero una primitiva che comincia e si concludein condizioni stazionarie.

Denotando con M(S,G) ⊂ P(S,G) l’insieme delle manovre, si ha che π ∈M(S,G) ⇔ ∃α, β ∈ E(S,G) : απβ ∈ P(S,G). Gli equilibri relativi compat-ibili con π a sinistra saranno detti predecessori di π, e si indicheranno comePred(π) ⊆ E(S,G). Analogamente con Succ(π) si indicheranno i successoridi π, cioe gli equilibri relativi compatibili con π da destra. Si osservi che,se α ∈ Pred(π) (rispettivamente β ∈ Succ(π)), allora Pred(π) = Eα(S,G)(rispettivamente Succ(π) = Eβ(S,G)).

Definizione 1.8. Si consideri una manovra π ∈ M(S,G), di durata |π| = Tπ.Poiche per definizione la manovra π e compatibile con un equilibrio relativo αda sinistra e con β da destra, allora esistono gαπ, gπβ ∈ G tali che xπ(0) =Ψ(gαπ, xα(0)) e xπ(Tπ) = Ψ(gπβ, xβ(0)). Si definisce lo spostamento sul gruppodella manovra π come gπ = g−1

απgπβ.

Si osservi che, mentre gαπ e gπβ dipendono dalla scelta della particolaremanovra π, lo spostamento sul gruppo, gπ, e uguale per tutte le manovre equi-valenti a π, cioe e G-invariante.

1.3.5 Simmetrie e primitive di movimento per un veicolodi Dubins

A conclusione della sezione dedicata alla presentazione delle simmetrie e delle pri-mitive di movimento per un sistema dinamico non lineare S generico, si riprendel’esempio del veicolo di Dubins, per comprendere come i concetti definiti nelcontesto generale si applichino a questo caso particolare.

Si assume che il moto del veicolo sul piano sia invariante per traslazionee per rotazione rispetto all’asse normale al piano stesso. Si tratta di ipotesivalide in innumerevoli applicazioni in cui lo spazio in cui il veicolo si muovee omogeneo ed isotropo. Quindi il sistema e invariante rispetto all’azione delgruppo G ∼= SE(2) ∼= R2 × S1. Si puo pertanto identificare G con lo spazio dellematrici 3× 3 del tipo

g(p, ϕ) =

cos ϕ − sin ϕ p1

sin ϕ cos ϕ p2

0 0 1

=

(R(ϕ) p

0 1

),

dove R(ϕ) ∈ SO(2) rappresenta una rotazione di un angolo ϕ attorno alla nor-male al piano e p ∈ R2 e una traslazione. L’azione (sinistra) di G sullo stato(x, θ) puo essere definita come

Ψ : G × X → X

Ψ(g(p, ϕ), (x, θ)) 7→ (R(ϕ)x + p, θ + ϕ).

11

Si noti che identificando lo spazio di stato X ∼= R2×S1 con lo spazio delle matrici3× 3, in maniera analoga a quanto fatto per G, la mappa Ψ si riduce al consuetoprodotto tra matrici. Il generico elemento ξ dell’algebra di Lie g associata algruppo G puo scriversi come

ξ =

0 −ϕ v cos θϕ 0 v sin θ0 0 0

.

Inseguendo una traiettoria di equilibrio relativo per un intervallo di durata τ siha uno spostamento sul gruppo G dato da

gr.e.(τ) = exp(ξτ) =

cos ϕτ − sin ϕτ 2vϕ

cos(θ + ϕτ2

) sin( ϕτ2

)

sin ϕτ cos ϕτ 2vϕ

sin(θ + ϕτ2

) sin( ϕτ2

)

0 0 1

che al variare di v, ϕ e τ corrisponde all’insieme di tutti gli archi sul piano, conraggio di curvatura (con segno) r = v/ϕ; si noti che r puo essere infinito, ilche corrisponde ad una linea retta. Posti u1 = v e u2 = ϕ, si considerano glispostamenti sul gruppo associati ad alcuni equilibri relativi particolari:

• I (idle): stato di quiete (u1 = u2 = 0):

gI(τ) = I3;

• S (straight): moto rettilineo uniforme con velocita massima (u1 = vmax eu2 = 0):

gS(τ) =

1 0 vmaxτ cos θ0 1 vmaxτ sin θ0 0 1

;

• L (left): moto circolare uniforme in senso antiorario con raggio di curvaturaminimo rmin e velocita tangenziale massima: u1 = vmax e u2 = vmax/rmin

gL(τ) =

cos ∆ϕ − sin ∆ϕ 2rmin cos(θ + ∆ϕ2

) sin(∆ϕ2

)

sin ∆ϕ cos ∆ϕ 2rmin sin(θ + ∆ϕ2

) sin(∆ϕ2

)0 0 1

dove ∆ϕ = vmaxτ/rmin;

• R (right): moto circolare uniforme in senso orario con raggio di curvaturaminimo rmin e velocita tangenziale massima (u1 = vmax e u2 = −vmax/rmin):

gR(τ) =

cos ∆ϕ sin ∆ϕ 2rmin cos(θ − ∆ϕ2

) sin(∆ϕ2

)

− sin ∆ϕ cos ∆ϕ 2rmin sin(θ − ∆ϕ2

) sin(∆ϕ2

)0 0 1

.

Si osservi che gli equilibri relativi I, S, L e R sono mutuamente compatibili dadestra e da sinistra. La definizione di questi quattro equilibri relativi sara utilein seguito.

12

1.4 Automa delle manovre

1.4.1 Definizione dell’automa delle manovre (MA)

La tecnica di pianificazione del movimento qui proposta si basa sulla scelta diun insieme finito di manovre Σ ⊂ M(S,G) e sulla generazione di traiettoriecomplesse attraverso la concatenazione di manovre in Σ. Poiche non tutte le ma-novre sono compatibili, e necessario definire delle regole per la caratterizzazionedelle sequenze valide. Una maniera conveniente di rappresentare tali regole e ladefinizione di un linguaggio formale. Le parole del linguaggio sono costituite dallaconcatenazione di piu manovre, quindi una parola e un elemento della cosiddettachiusura di Kleene Σ∗ dell’alfabeto Σ, cioe l’insieme di tutte le possibili sequenzedi simboli in Σ. L’elemento identita e la stringa nulla ε. In generale, non tuttele stringhe in Σ∗ corrispondono a traiettorie valide per (1.1), dunque solo primi-tive compatibili possono essere concatenate. Si conviene di rappresentare tuttele stringhe di Σ∗ costituite dalla concatenazione di primitive compatibili comel’insieme delle parole accettate da una macchina deterministica a stati finiti, chesara detta automa delle manovre (MA).

Definizione 1.9. Un MA e una quintupla

MA = {Σ, Q, δ, q0, F}

dove:

• Σ ⊂M(S,G) e l’alfabeto delle manovre, un insieme finito di manovre.

• Q = Q0 ∪ {¤} e l’insieme finito degli stati. Q0 ⊂ E(S,G) e un insiemedi equilibri relativi tali che, per ogni π ∈ Σ, Pred(π), Succ(π) ∈ Q0 eche

⋃π∈Σ{Pred(π), Succ(π)} = Q0. In altre parole Q0 e l’insieme minimo

contenente tutti gli equilibri relativi dai quali puo iniziare una manovra ein cui una manovra puo concludersi. Il simbolo ¤ rappresenta uno statod’errore, utilizzato per rilevare stringhe non valide.

• δ : Q × Σ → Q e la funzione di transizione di stato, che mappa lo statoprecedente alla manovra nello stato successivo:

δ(α, π) =

{β ∈ Q : β ∈ Succ(π), se α ∈ Pred(π);¤, altrimenti.

• q0 ∈ Q e lo stato iniziale

• F ⊂ Q e l’insieme degli stati finali, o accettati.

Un MA puo essere associato a un grafo diretto in cui i vertici rappresentano glistati (cioe le primitive in assetto) e gli archi le manovre. Il grafo associato ad unMA non deve essere necessariamente connesso, ne fortemente connesso, ammette

13

Figura 1.2. Esempio di grafo associato ad un MA. Gli equilibri relativi sono indicati conlettere maiuscole all’interno di cerchi, mentre le manovre con delle frecce etichettate con lettereminuscole. Lo stato iniziale e indicato con una freccia, quelli finali con un doppio cerchio.

archi paralleli, cioe piu manovre possono connettere gli stessi equilibri relativi, ecappi, ovvero archi con nodi iniziale e finale coincidenti (figura 1.2).

Si definisce il linguaggio L(MA) ⊆ Σ∗ come l’insieme delle stringhe accettate4

da un dato MA. Una stringa ω ∈ L(MA) sara detta sequenza di manovre. Poicheun MA e una macchina a stati finiti, il linguaggio L(MA) e regolare.

Si introduce l’ipotesi che le condizioni iniziale e finale per il problema dellapianificazione del movimento siano rappresentabili come equilibri relativi in Q,ovvero che esistano g0 ∈ G e α ∈ Q tali che x0 = Ψg0(xα(0)). Simili assunzioni sifanno per l’insieme degli stati finali: ∀xf ∈ F, ∃(gf , β) ∈ G×F : xf = Ψgf

(xβ(0)).Queste ipotesi sono solitamente verificate nei problemi di pianificazione del movi-mento, poiche le condizioni iniziali e finali sono tipicamente definite come con-dizioni di equilibrio. Si noti infine che, mentre Q, Σ e δ in un MA dipendonodal sistema e dalla scelta delle primitive da includere nel linguaggio, q0 ed Fdipendono dalla specifica istanza del problema da risolvere. Per la discussione diproprieta che devono valere uniformemente, per ogni scelta di q0 e F , come adesempio la controllabilita, queste saranno lasciate indefinite.

1.4.2 Piani di movimento

Il ruolo degli equilibri relativi e stato sinora semplicemente quello di fornire unmetodo conveniente per la definizione formale di un tipo particolare di primitivedi movimento, le manovre, e dotarle di una comune interfaccia per la concate-nazione. Tuttavia gli equilibri relativi possono essere sfruttati per arricchire

4Si dice che una parola ω ∈ Σ∗ e accettata da un automa finito deterministico se esisteuna produzione che genera ω a partire dallo stato iniziale e raggiungendo uno stato finale.La parola ω si dice invece generata se esiste una produzione che genera ω a partire dallostato iniziale. L’insieme delle parole accettate (generate) costituisce il linguaggio accettato(generato) dall’automa.

14

ulteriormente le traiettorie rappresentabili utilizzando i linguaggi degli automi dimanovre.

Si consideri la sequenza di manovre ω = π1, π2, . . . , πN ; interponendo equili-bri relativi di lunghezza nulla tra due manovre consecutive, ω puo essere equiv-alentemente riscritta come ω = α1(0)π1, α2(0)π2, . . . , αN(0)πNαN+1(0) con αi ∈Pred(πi) per i = 1, . . . , N e αN+1 ∈ Succ(πN). Si puo dunque ottenere unapiu ampia classe di primitive frapponendo delle primitive di assetto di duratanon nulla tra manovre successive. In altri termini si possono considerare delleprimitive della forma

(ω, τ) = α1(τ1)π1, α2(τ2)π2, . . . , αN(τN)πNαN+1(τN+1), τi ≥ 0 ∀i ∈ {1, N + 1}.

Si noti che (ω, τ) ∈ P(S,G) per costruzione. Alla luce delle considerazioni appenaesposte si introduce la seguente

Definizione 1.10. Si definisce piano di movimento per un MA una coppia(ω, τ) ∈ L(MA) × RN(ω)+1

+ , dove N(ω) e il numero di simboli in ω e τ e ilvettore degli N(ω) + 1 coasting time.

Mente una sequenza di manovre puo essere associata ad un cammino sul grafodiretto associato ad un MA, il piano di movimento arricchisce quest’informazionespecificando il tempo speso in ciascuno stato (traiettoria in assetto). La duratacomplessiva del piano di movimento (ω, τ) e la somma della durata della sequenzadi manovre ω e di tutte le componenti di τ .

Una proprieta rilevante del linguaggio introdotto per la pianificazione ditraiettorie e la possibilita di determinare completamente lo stato del sistemain qualsiasi istante senza ricorrere alla simulazione o all’integrazione numericadelle equazioni differenziali in (1.1). Per convincersene, si consideri un pia-no di movimento composto da una singola manovra, preceduta e seguita dauna traiettoria in assetto. Il piano di movimento e individuato dalla primitiva(ω, τ) = (π1, [τ1, τ2]) = α1(τ1)π1α2(τ2). Se x(0) = Ψg0(xα1(0)), la traiettoria edescritta, in spazio di stato, da

x(t) =

Ψ(g0 exp(ξα1t), xα1(0)), t ∈ [0, τ1];Ψ(g0 exp(ξα1τ1)gα1π1 , π1(t− τ1)) t ∈ (τ1, τ1 + |π1|];Ψ(g0 exp(ξα1τ1)gπ1 exp(ξα2(t− τ1 − |π1|))), xα2(0)) altrimenti.

La formula precedente e estendibile a un piano di movimento di lunghezza ar-bitraria. In particolare, lo stato finale al termine dell’esecuzione del piano dimovimenti p (ω, τ) di lunghezza N(ω) e dato da xf = Ψ(g0gp, xαN(ω)+1

(0)), dovelo spostamento sul gruppo gp e dato da

gp =

N(ω)∏i=1

exp(ξαiτi)gπi

exp(ξαN(ω)+1

τN(ω)+1), (1.7)

15

dove πi e l’i-esima manovra della sequenza ω, αi ∈ Pred(πi), i = . . . , N(ω)e αN(ω)+1 ∈ Succ(πN(ω)). L’equazione (1.7) puo essere riscritta in manieraequivalente come

gp = gω

N(ω)+1∏i=1

exp(ηiτi), (1.8)

dove gω =∏N(ω)

i=1 gπie lo spostamento sul gruppo corrispondente al piano di

movimento (ω, 0) e i campi vettoriali ηi sono definiti dalla seguente relazione:

ξαi= Ad

N(ω)∏j=i

gπj, ηj

e ηN(ω)+1 = ξαN(ω)+1; Ad(g, ·) e la trasformazione aggiunta di g ∈ G, ovvero

Ad(g, ξ) = gξg−1. La prova dell’equivalenza di (1.7) e (1.8) si ottiene eseguendoin sequenza le seguenti sostituzioni in (1.7):

exp(ξαiτi)gπi

= exp(gπiηig

−1πi

τi)gπi= gπi

exp(ηiτi)g−1πi

gπi= gπi

exp(ηiτi)

per i = N(ω), N(ω)− 1, . . . , 1.L’equazione (1.8) mostra che lo spostamento dovuto all’esecuzione del pia-

no di movimento p puo essere scomposto in uno spostamento gω, relativo allasequenza di manovre ω, e alla composizione delle evoluzioni del sistema lungocampi vettoriali invarianti a sinistra η, che possono essere calcolati a partire dallacondizione iniziale q0 e dalla sequenza delle manovre ω. E importante osservareche (1.8) ha la struttura, ben nota nell’ambito della robotica, di una mappa dicinematica diretta, come quelle che associano, ad esempio, la posizione del ma-nipolatore posto all’estremita di un braccio meccanico alla configurazione degliangoli delle giunture. In altre parole il sistema dinamico non lineare (1.1) puoessere trasformato, utilizzando il formalismo degli automi, in uno che si compor-ta formalmente come un sistema cinematico. La trasformazione e esatta, cioee stata introdotta alcuna approssimazione, ma limita le traiettorie ammissibilialla concatenazione sequenziale di un numero finito di primitive di movimentodeterminate a priori.

1.4.3 Esempio: automa delle manovre di un veicolo diDubins

A titolo di esempio, questa sezione e dedicata alla definizione di un automa dellemanovre per il veicolo di Dubins, introdotto in precedenza. In particolare nellasezione 1.3.5 si sono definiti gli equilibri relativi I, S, L e R, e si e osservato chesono mutuamente compatibili. Un automa delle manovre per il veicolo di Dubinscoerente con le definizioni generali date sopra puo essere il seguente:

MA = {Σ, Q, δ, q0, F},dove:

16

• l’alfabeto delle manovre Σ contiene unicamente la stringa nulla, Σ = {ε}:essendo I, S, R e L compatibili non e necessaria alcuna manovra di tran-sizione;

• Q = {I, S, L, R, ¤};

• la funzione di transizione δ e definita graficamente in figura 1.3.

• q0 = F = I.

Figura 1.3. Grafo associato al MA di un veicolo di Dubins.

Si osservi che il linguaggio accettato dall’automa L(MA) contiene il l’insiemedi parole L′(MA) = {ILSLI, IRSRI, ILSRI, IRSLI, ILRLI, IRLRI}. Si ve-dranno nel seguito le importanti proprieta di L′(MA). Per il momento i pianidi movimento associati alle stringhe di L′(MA) saranno presi in considerazionea puro titolo di esempio. Si veda la figura 1.4.

Figura 1.4. Cammini per un veicolo di Dubins associati a stringhe in L′(MA). I camminiLSR, LSL e RLR si ottengono da quelli raffigurati per simmetria

17

Piani di movimento di tipo LSL

Sia pLSL = (ω, τ) = I(τ0)εL(τ1)εS(τ2)εL(τ3)εI(τ4). Il veicolo cioe rimane fermoper un intervallo τ0, quindi, con una transizione di durata nulla, compie unacurva a sinistra di raggio minimo per un periodo τ1, poi procede in moto rettilineoper un intervallo τ2, curva nuovamente a sinistra, il tutto sempre alla massimavelocita vmax, e infine si ferma. Nel seguito, per brevita, si converra di scriverepLSL = L(τ1)S(τ2)L(τ3), omettendo di indicare l’equilibrio relativo I e le stringhenulle ε. Lo spostamento totale compiuto si calcola utilizzando l’equazione (1.7),che porge, essendo nulli gli spostamenti associati alle manovre e quelli associatialla primitiva I:

gpLSL= gL(τ1)gS(τ2)gL(τ3),

dove i termini del membro di destra sono stati definiti nella sezione 1.3.5. Dettiα = vmaxτ1/rmin e γ = vmaxτ3/rmin, i due angoli di curvatura, e β = vmaxτ2, lalunghezza del tratto rettilineo intermedio, eseguendo il prodotto si ricava:

gLSL =

cos(α + γ) − sin(α + γ) rmin sin(α + γ) + β cos αsin(α + γ) cos(α + γ) rmin[1− cos(α + γ)] + β sin α

0 0 1

.

Il problema appena risolto e di cinematica diretta, ovvero, data una sequenzadi primitive di movimento e un punto iniziale, si e determinato il punto finale.Al fine della pianificazione di traiettorie, pero, maggiore interesse rivestono iproblemi di cinematica inversa: date una configurazione iniziale g0 e una finalegf si vuole determinare una traiettoria ammissibile, se esiste, che le congiunga.Si vogliano, ad esempio, determinare i parametri τi, i ∈ {1, 2, 3} di un piano dimovimento pLSL, se esiste, che porta il sistema dalla configurazione g0 a gf . Insostanza, si tratta di risolvere il sistema di equazioni non lineari

g−10 gf = gL(τ1)gS(τ2)gL(τ3),

nelle incognite τi, i ∈ {1, 2, 3}. Indicando con gij = (g−10 gf )ij l’elemento in po-

sizione (i, j) della matrice nota g−10 gf , dal confronto con l’equazione precedente,

si ricava che5:∆ϕ := α + γ = atan2(g11, g21)

da cui

α = atan2(g13 − rmin sin ∆ϕ, g23 − rmin(1− cos ∆ϕ));

β =√

(g13 − rmin sin ∆ϕ)2 + (g23 − rmin(1− cos ∆ϕ))2;

γ = ∆ϕ− α.

5La scrittura atan2(x, y) denota la funzione arcotangente a due argomenti, in cui la primaindeterminata e l’ascissa e la seconda e l’ordinata. Talvolta viene utilizzata la convenzioneopposta, come, ad esempio, in Matlab. Si noti anche che gli angoli sono qui definiti comeelementi di S1, ma per implementare queste formule al calcolatore, ad esempio in Matlab, sideve aver cura di specificare che si tratta di numeri reali mod 2π.

18

La soluzione trovata e ben definita per ogni g ∈ SE(2), quindi data una qualsiasicoppia di configurazioni, iniziale e finale, esiste sempre uno (ed un solo) pianodi movimento di tipo pLSL che le congiunge. A rigore, il problema di cinematicainversa richiede il calcolo di τi, i ∈ {1, 2, 3}, ma questi sono facilmente ottenibilidalle ampiezze dei due archi e dalla lunghezza del segmento appena trovate:

τ1 =α rmin

vmax

; τ2 =β

vmax

; τ3 =γ rmin

vmax

.

Piani di movimento di tipo RSR

I piani di movimento di tipo RSR sono simmetrici rispetto a quelli di tipo LSLappena discussi e corrispondono a traiettorie ottenute interponendo un trattorettilineo tra due archi orientati in verso orario. Ripetendo passo a passo ilragionamento appena condotto per i piani LSL, con analoga simbologia, si ottieneper il problema di cinematica diretta:

gRSR =

cos(α + γ) sin(α + γ) rmin sin(α + γ) + β cos α− sin(α + γ) cos(α + γ) −rmin[1− cos(α + γ)]− β sin α

0 0 1

.

Da questa si ricava la soluzione al problema di cinematica inversa:

∆ϕ := 2π − α− γ = atan2(g11, g12)

α = atan2(g13 + rmin sin ∆ϕ, −g23 − rmin(1− cos ∆ϕ));

β =√

(g13 + rmin sin ∆ϕ)2 + (g23 + rmin(1− cos ∆ϕ))2;

γ = 2π −∆ϕ− α.

In maniera simmetrica al caso precedente, un piano di movimento RSR soluzionedel problema di cinematica inversa esiste sempre ed e unico.

Piani di movimento di tipo LSR

Con la simbologia usuale, cioe indicando con α, β e γ, gli angoli dei tre tratticurvilinei di traiettoria o le lunghezze di quelli rettilinei, in ordine, posto ∆ϕ =α− γ, la soluzione al problema di cinematica diretta si scrive:

gLSR =

cos ∆ϕ − sin ∆ϕ β cos α + 2rmin sin α− rmin sin ∆ϕsin ∆ϕ cos ∆ϕ β sin α− 2rmin cos α + rmin(1 + cos ∆ϕ)

0 0 1

.

Per quanto concerne il problema di cinematica inversa si puo trovare subito:

∆ϕ = α− γ = atan2(g11, g21);

β =√

(g13 + rmin sin ∆ϕ)2 + [g23 − rmin(1 + cos ∆ϕ)]2 − 4r2min.

19

Si noti che l’ultima equazione e definita solamente se l’argomento sotto radicee non negativo; solo sotto questa condizione esiste (ed e unico) un piano dimovimento di tipo LSR. Eguagliando gli elementi in posizione (1,3) e (2,3) dellagenerica matrice g ∈ SE(2) con gLSR si ottiene il sistema di equazioni

x = β cos α + 2rmin sin α

y = − 2rmin cos α + β sin α,

dove x = g13 + rmin sin ∆ϕ e y = g23 − rmin(1 + cos ∆ϕ). Riscrivendo il sistemain forma matriciale nel vettore incognito (cos α, sin α), si ottiene:

(cos αsin α

)=

(β 2rmin

−2rmin β

)−1 (xy

);

si osservi che il termine di destra e costituito da tutti termini noti e che l’inversaesiste e la matrice da invertire e definita positiva. Utilizzando il metodo diCramer si ha:

cos α = det

(x 2rmin

y β

)[det

(β 2rmin

−2rmin β

)]−1

sin α = det

(β x

−2rmin y

)[det

(β 2rmin

−2rmin β

)]−1

.

In conclusione:

α = atan2(xβ − y2rmin, βy + x2rmin);

γ = α−∆ϕ.

Piani di movimento di tipo RSL

Posto ∆ϕ = 2π − α + γ si ha:

gRSL =

cos ∆ϕ − sin ∆ϕ β cos α + 2rmin sin α + rmin sin ∆ϕsin ∆ϕ cos ∆ϕ −β sin α + 2rmin cos α− rmin(1 + cos ∆ϕ)

0 0 1

.

Con calcoli analoghi ai precedenti, si ottiene la soluzione al problema di cinema-tica inversa:

∆ϕ = atan2(g11, g21);

x = g13 − rmin sin ∆ϕ;

y = g23 + rmin(1 + cos ∆ϕ);

β =√

x2 + y2 − 4r2min;

α = atan2(2rminx− yβ, 2rminy + xβ);

γ = ∆ϕ + α.

Come nel caso precedente, tale soluzione esiste solo se x2 + y2 ≥ 4r2min.

20

Piani di movimento di tipo LRL

Posto ∆ϕ = α− β + γ si ottiene:

gLRL =

cos ∆ϕ − sin ∆ϕ rmin[2 sin(β − α) + 2 sin α + sin ∆ϕ]sin ∆ϕ cos ∆ϕ rmin[2 cos(β − α)− 2 cos α + (1− cos ∆ϕ)]

0 0 1

.

Da questa si ricava la soluzione al problema di cinematica inversa: definiti

∆ϕ = atan2(g11, g21);

x = g13 − rmin sin ∆ϕ;

y = g23 − rmin(1− cos ∆ϕ);

si ha che

x2 + y2 = 8r2min(1 + sin(β − α) sin(α)− cos(β − α) cos(α)) = 8r2

min(1− cos β).

L’equazione ammette soluzione se |8r2min − x− y| ≤ 8r2

min, nel qual caso si ha:

β = 2π − arccos8r2

min − x2 − y2

8r2min

che e compreso nell’intervallo [π, 2π] essendo l’arcocoseno definito su [0, π]; lasoluzione esplementare 2π − β e certamente da scartare, essendo necessario perl’ottimalita che β ∈ [π, 2π), come dimostrato da Dubins in [19]. Si ha poi che

(xy

)= 2

(sin β 1− cos β

−(1− cos β) sin β

) (cos αsin α

)

da cui (cos αsin α

)= 0.5

(sin β 1− cos β

−(1− cos β) sin β

)−1 (xy

).

Si osservi che la prima matrice del membro di destra e effettivamente invertibile edefinita positiva. Utilizzando il metodo di Cramer, come gia fatto in precedenza,si ottiene:

cos α = det

(x 1− cos βy sin β

) [det

(sin β 1− cos β

−(1− cos β) sin β

)]−1

sin α = det

(sin β x

−(1− cos β) y

)[det

(sin β 1− cos β

−(1− cos β) sin β

)]−1

;

da cui finalmente

α = atan2(x sin β − y(1− cos β), y sin β + x(1− cos β)).

Infineγ = ∆ϕ + β − α.

21

Piani di movimento di tipo RLR

Si considera infine il caso di un piano di movimento di tipo RLR. Posto ∆ϕ =2π − α + β − γ si ricava, per il problema di cinematica diretta:

gRLR =

cos ∆ϕ − sin ∆ϕ rmin[2 sin α− 2 sin(α− β)− sin ∆ϕ]sin ∆ϕ cos ∆ϕ rmin[2 cos α− 2 cos(α− β)− (1− cos ∆ϕ)]

0 0 1

.

Con calcoli analoghi a quelli condotti nel caso precedente si perviene alla seguentesoluzione del problema di cinematica inversa:

∆ϕ = atan2(g11, g21);

x = g13 + rmin sin ∆ϕ;

y = g23 + rmin(1− cos ∆ϕ);

β = 2π − arccos8r2

min − x2 − y2

8r2min

;

α = atan2(x sin β + y(1− cos β), x(1− cos β)− y sin β);

γ = 2π −∆ϕ− α + β.

che esiste se e solo se |8r2min − x− y| ≤ 8r2

min.

Pianificazione del moto per veicoli con attuatori a banda limitata

Il modello di Dubins prevede che i veicoli che si muovano a velocita costantenella direzione del moto. Si e pertanto assunto sinora che i segnali di controllosiano funzioni del tempo continue a tratti, ammettendo cioe che il comando possaavere delle discontinuita di prima specie in corrispondenza dell’istante in cui duesuccessive primitive di movimento vengono concatenate. La banda dei segnali dicontrollo si e pertanto ipotizzata infinita.

Quest’assunzione e lecita, ad esempio, nel caso degli unicicli. Ad esempio,i robot mobili e-puck, come si avra modo di dire in seguito, sono dotati di duemotori elettrici a passo, uno per ciascuna ruota. Le ruote sono percio in gradodi muoversi compiendo un assegnato numero di passi e quindi di bloccarsi quasiistantaneamente; anche l’accelerazione del veicolo fermo fino alla velocita massi-ma richiede un transitorio inferiore ad un passo di campionamento e puo dunquepensarsi di durata nulla. La particolare semplicita della dinamica consente diassociare ad un uniciclo tipo e-puck un MA avente, come primitive di moto,unicamente degli equilibri relativi. L’insieme delle manovre M(S,G) e, come sie visto, costituito dalla sola stringa nulla ε.

Esistono pero dei veicoli, modellabili solo in prima approssimazione comemacchine di Dubins, dalla dinamica piu complicata degli unicicli, il cui motonon e descrivibile semplicemente dalla concatenazione di equilibri relativi. Sipensi, ad esempio, alle automobili o agli aerei. La complicazione della dinamica,grazie al formalismo degli MA, non ne rende piu ardua la pianificazione del moto.

22

La quantizzazione del controllo comporta, per definizione, un numero finito diequilibri relativi: le coppie di equilibri relativi compatibili sono in numero finitoe definite a priori. Pertanto e possibile definire a priori delle manovre che lecongiungano e calcolarne lo spostamento a priori. Fissata una stringa di manovreω se ne calcola lo spostamento complessivo gω come prodotto degli spostamentidelle singole manovre, quindi si utilizza (1.8): invertendo gω ci si riconduce adun problema di pianificazione di traiettorie composte da soli equilibri relativi.

Si dimostra che la traiettoria di lunghezza minima per un veicolo di Dubins,con il vincolo aggiuntivo della continuita della curvatura, esiste ed e costituitada segmenti di retta, archi di raggio rmin e tratti di spirale con massima derivatadella curvatura; tuttavia la traiettoria ottima puo essere costituita da un’infinitadi tali parti, il che rende la pianificazione ottima impraticabile [50]. La scelta dicammini sub-ottimi e quindi una necessita. Per la definizione di una libreria dellemanovre, si possono sostituire le discontinuita “a salto” del comando, ad esempio,con dei transitori a rampa della pendenza massima consentita dai limiti degliattuatori, come suggerito in [50]. In alternativa si puo utilizzare una funzioneinterpolatrice generica, anche non lineare, come quella che si ottiene applicandoil metodo proposto in [31]. Una terza possibilita e quella di fare compiere lamanovra manualmente ad un pilota umano, campionando e memorizzando lasequenza di comandi. Quest’opzione richiede, ovviamente, maggiore disponibilitadi memoria.

1.5 Pianificazione del movimento basata sulle

manovre

1.5.1 Controllabilita di un MA

L’approccio proposto alla soluzione dei problemi di pianificazione di traiettoriepuo essere cosı riassunto: anziche cercare una legge di controllo in un insiemedi dimensione infinita, come, ad esempio, quello delle funzioni continue a trat-ti, si limita la ricerca in un insieme definito su un linguaggio regolare L(MA).Restringendo la ricerca a piani di movimento costituiti da un numero finito diprimitive, si riformula un problema differenziale in uno algebrico.

I vantaggi computazionali che derivano da questa semplificazione, si paganocon la restrizione dell’insieme delle traiettorie ottenibili con il sistema S. Laquestione fondamentale, a questo punto, e la scelta dell’insieme finito di primitivedi movimento da includere nell’alfabeto delle manovre Σ. Una richiesta essenzialesu Σ e sul MA risultante, e la conservazione delle proprieta di controllabilita delsistema originale S.

Definizione 1.11. Si dice che un MA e controllabile (uniformemente su q0 e F )se, per ogni condizione iniziale x(0) = Ψ(g0, xq0(0)) e per ogni equilibrio relativo

23

finale qf ∈ F esiste un T che e un limite superiore al tempo necessario perraggiungere lo stato finale xf = Ψ(gf , xqf

(0)).

Condizioni necessarie e sufficienti per la controllabilita di un automa MAgenerico sono state derivate in [23]. Ci si limita qui a rammentare che il fatto cheil grafo associato all’automa sia fortemente connesso e una condizione necessaria,che discende direttamente dalla definizione di controllabilita. Si dedichera nellasezione 1.5.3 maggior spazio alle considerazioni sulla controllabilita dell’automaMA associato ad un veicolo di Dubins.

1.5.2 Esistenza di soluzioni “ottime” e loro determinazione

L’impiego degli automi delle manovre consente di approssimare le soluzioni delproblema differenziale infinito-dimensionale dato dalla minimizzazione della fun-zione costo (1.3), con i vincoli (1.1) e (1.2), con un problema algebrico di dimen-sione finita. D’altra parte la restrizione della classe delle soluzioni alla combi-nazione di un numero finito di primitive di movimento si traduce nell’aggiuntadi vincoli ulteriori. Percio il metodo proposto non conduce, in generale, allasoluzione ottima. E tuttavia possibile chiedersi se esista un piano di movimen-to dell’automa MA di costo minimo e, in caso affermativo, come sia possibiledeterminarlo.

Il primo passo e la riscrittura della funzione di costo (1.3), come propostodalla seguente

Proposizione 1.2. La funzione di costo (1.3) del piano di movimento p = (ω, τ)puo riscriversi come

J(xp, up) = JMA(p) =N∑

i=1

(Γπi+ γαi

τi) + γαN+1τN+1 (1.9)

dove Γπ e il costo associato alla manovra π e γα rappresenta il costo per unita ditempo dell’equilibrio relativo α.

Dimostrazione: Si decomponga il piano di movimento p in due parti, cosicchep = p1p2. Essendo (1.3) additiva rispetto agli estremi d’integrazione e tempo-invariante si ha

J(xp , up) = J(xp1 , up1) + J(xp2 , up2) =

∫ |p1|

0

γ(xp1 , up1)dt +

∫ |p2|

0

γ(xp2 , up2)dt.

In maniera analoga e possibile suddividere il costo del piano di movimento p nellasomma dei costi di ciascuna delle primitive che lo compongono. Come notatonell’osservazione 1.2, il costo di un equilibrio relativo e invariante per traslazione

24

temporale e non dipende dallo stato iniziale. Inoltre il costo di un equilibriorelativo e lineare rispetto alla sua durata:

J(xα, uα) =

∫ |τ |

0

γ(xα, uα)dt =

∫ |τ |

0

γ (Ψ(g0 exp(ξαt), xα(0)), uα) dt =

=

∫ |τ |

0

γ(xα(0), uα)dt = γατ.

Quindi (1.9) corrisponde alla decomposizione del costo di un piano di movimentonella somma delle singole primitive che lo compongono. ¤

Osservazione 1.3. Il costo di un piano p = (ω, τ) di movimento e affine neicoasting time τ .

Data una libreria di primitive di movimento che definiscono il linguaggio ac-cettato da un MA, il piano di movimento piu efficiente per la soluzione del pro-blema della guida puo essere trovato risolvendo il problema di programmazionenon lineare seguente:

(ω∗, τ ∗) = arg min(ω,τ)

JMA(ω, τ) (1.10)

con i vincoli

gω

N(ω)+1∏i=1

exp(ηi, τi) = g−10 gf

ω ∈ L(MA)

τi ≥ 0, i = 1, . . . , N(ω) + 1

Prima di procedere e necessario garantire che esista una soluzione al problema(1.10).

Teorema 1.1. Se l’automa MA e controllabile, allora esiste una soluzione alproblema di controllo ottimo (1.10). Il piano di movimento ottimo ha lunghezzae costo finiti.

Dimostrazione: Se il MA e controllabile, allora esiste un piano di movimentop = (ω, τ) soddisfacente i vincoli e avente costo finito. Poiche un piano di movi-mento non vuoto ha un costo non inferiore a ε = min{π : π ∈ Σ} > 0, esiste unnumero finito di sequenze in L(MA) che corrispondano a dei piani di movimen-to con costo inferiore a JMA(ω, τ). Per ciascuna di queste sequenze, cioe per ωfissato, il problema (1.10) con il vincolo ulteriore JMA(p) ≤ JMA(p) presenta unafunzione di costo continua su un compatto. Quindi o il problema non ammettesoluzione poiche ω e tale che non e possibile soddisfare i vincoli, o, per il teoremadi Weierstrass esiste un minimo. Quindi, oltre a ω ci sono un numero finito disoluzioni candidate. E ottima la soluzione di costo minimo. La soluzione ottimanon e necessariamente unica. ¤

25

Il problema (1.10) e, in generale, non convesso e di difficile soluzione, matrattandosi di un problema di dimensione finita, la sua soluzione e, in linea diprincipio, piu semplice di quella della sua controparte differenziale. Con oppor-tune ipotesi ulteriori su Q e su G e tuttavia possibile ricondursi a un problemadi programmazione polinomiale o lineare: per ulteriori approfondimenti si veda[23]. Basti qui accennare al fatto che nel caso del veicolo di Dubins, come sivedra, la soluzione del problema (1.10) risulta semplice.

Una linea guida per la risoluzione del problema (1.10) e la seguente. Lastruttura del problema (1.10) si presta ad essere decomposta in due fasi: primasi scelgono i coasting time ottimi τ ∗(ω) per ω fissato, risolvendo un problemadi cinematica inversa, poi si determina ω∗ = arg minω∈L(MA) τ ∗(ω). Poiche ω∗

e una stringa finita l’algoritmo termina in un numero finito di passi. L’efficien-za dell’algoritmo puo poi essere consistentemente incrementata con tecniche dibranch-and-bound e di pruning.

1.5.3 Pianificazione del movimento per un veicolo di Du-bins

Nel caso del veicolo di Dubins la scelta della libreria delle manovre risulta es-tremamente piu semplice rispetto al caso generale, data l’abbondanza di risul-tati teorici presenti in quel filone della letteratura tecnica che ha tratto originedall’articolo pionieristico [19] del matematico L.E. Dubins. In quello studio sidimostra che il cammino minimo per il veicolo definito nella sezione 1.2.2 esisteed appartiene a una famiglia parametrica di soli sei cammini-tipo, composti alpiu di tre parti, ciascuna delle quali puo essere o un arco di circonferenza diraggio minimo rmin o un segmento di linea retta. Con la notazione introdottanella sezione 1.4.3 si puo riformulare il risultato ottenuto da Dubins in manieraseguente: un automa MA associato a un veicolo di Dubins che accetta il linguag-gio L′(MA) = {RSL,LSR,RSR, LSL, LRL, RLR} non solo e controllabile, macontiene tutte le stringhe corrispondenti a traiettorie a tempo minimo tra duegenerici punti di X ∼= R2 × S1.

Dubins ha inoltre dimostrato delle ulteriori condizioni necessarie per l’otti-malita della traiettoria; vincoli aggiuntivi sono stati introdotti da Bui et al. in[12]. Indicando con Lα (rispettivamente Rα) una curva a sinistra (rispettiva-mente destra) di raggio minimo rmin e angolo α (in radianti) e con Sβ un trattorettilineo di lunghezza β (in metri), tali condizioni necessarie per l’ottimalita diun cammino possono essere riassunte come nella seguente tabella.

26

Tipo di traiettoria Vincoli

LαRβLγ o RαLβRγ

β ∈ (π, 2π) e

α, γ ∈ [0, β] e

0 ≤ α < β − π o 0 ≤ γ < β − π

RαSβRγ o LαSβLγ α, γ ∈ [0, 2π) e α + γ ≤ 2π

RαSβLγ o LαSβRγ α, γ ∈ [0, 2π)

Un analogo risultato e stato ottenuto da Reeds e Shepp in [45] per un veicoloche possa muoversi in avanti e indietro. Gli autori hanno ricavato, partendo daun’analisi al calcolatore, una famiglia parametrica di curve sufficiente per l’otti-malita, contenente 48 traiettorie, ciascuna composta da al piu 5 parti dei 3 tipivisti sopra. Nel caso della macchina di Reeds-Shepp, la traiettoria ottima puonon essere regolare, essendo ammesse delle cuspidi. Successivamente Sussmanne Tang in [51] hanno rivisto il lavoro di Reeds e Shepp alla luce della teoria delcontrollo ottimo, ricavando una famiglia di traiettorie sufficiente per l’ottimalitacontenente solo 46 traiettorie. Nel seguito, come gia detto, si prendera in consid-erazione unicamente il caso di un veicolo di Dubins, oltre che per le ragioni giaenunciate, per semplificare la trattazione, riducendo il numero delle traiettorie daconsiderare e focalizzando invece l’attenzione sulle problematiche del controllo.L’estensione al caso di un veicolo in grado di muoversi anche all’indietro si puocondurre con ragionamenti analoghi a quelli esposti e non comporta differenzesostanziali.

Per un veicolo di Dubins si puo ottenere dunque la soluzione del problema(1.10) in maniera semplice ed e inoltre possibile garantire che essa coincide conla soluzione ottima di (1.3). Come accennato al termine della sezione precedentee sufficiente considerare tutte le stringhe ω ∈ L′(MA): si tratta solamente di seicasi possibili. Per ciascun caso si risolve un problema di cinematica inversa, sepossibile, come mostrato nella sezione 1.4.3, ottenendo cosı τ ∗(ω) = τ1+τ2+τ3. Ilpiano di movimento ottimo e (ω∗, τ ∗(ω∗)), dove ω∗ = arg minω τ ∗(ω). L’efficienzadella soluzione puo essere incrementata con tecniche di pruning, scartando apriori quelle stringe ω che non soddisfano le condizioni necessarie per l’ottimalitariassunte nella tabella precedente.

1.6 Costruzione dell’anello di controllo ad alto

livello

Si e considerato sinora un controllo in retroazione a basso livello, mentre lapianificazione della traiettoria e stata eseguita in catena aperta. Il controlloredi livello inferiore ha il compito di garantire la reiezione dei disturbi e deglierrori di modello, assicurando che la traiettoria calcolata dal livello superiore sia

27

effettivamente eseguita. In questa sezione si introdurra un anello di retroazioneanche ad alto livello.

La letteratura dedicata al controllo di veicoli anolonomi si concentra essen-zialmente su tre problemi:

• del posteggio (o parking problem): concerne la stabilizzazione di un veicolointorno a un punto fisso;

• dell’inseguimento (o tracking): consiste nell’inseguimento di una traiettorianon puntuale data;

• della pianificazione del cammino (o path planning): consta nella pianifica-zione di traiettorie con predeterminati caratteri di ottimalita, tra due o piupunti eventualmente in presenza di ostacoli fissi o mobili.

Quasi tutte le soluzioni ai primi due problemi proposte in letteratura ipotizzanodi disporre della posizione, assoluta o relativa alla traiettoria, a tempo continuo.Un’eccezione e data da [39]. Per quanto riguarda il terzo problema, esso e spessoaffrontato da un punto di vista prettamente geometrico, senza considerare la di-namica del veicolo. Si tratta di tre questioni di natura differente, affrontate contecniche molto diverse: in particolare il problema del posteggio non puo consid-erarsi come un problema d’inseguimento in cui la traiettoria data degenera in unpunto, poiche quasi tutti gli algoritmi di tracking non si applicano a traiettoriedegeneri [38].

Il presente capitolo si propone di dare una soluzione unica a questi tre pro-blemi e tale da essere implementabile a tempo discreto.

1.6.1 Difficolta della stabilizzazione di un sistema nonlineare

Molti degli studi sull’argomento hanno tratto spunto e motivazione dallo studio[11] condotto da R.W. Brockett sulle condizioni di esistenza di leggi di controlloregolari asintoticamente stabilizzanti. Si sintetizzeranno qui le idee e i risultatiprincipali di quello studio.

Si consideri inizialmente un sistema di controllo lineare a tempo continuo

x = Ax + Bu. (1.11)

Sia la coppia (A,B) controllabile e sia K una matrice tale che A + BK unamatrice asintoticamente stabile. Si consideri poi una traiettoria di riferimentot 7→ xr(t), con xr = Axr + Bur. Allora la legge di controllo in retroazione

u(x, xr, ur) := ur + K(x− xr) (1.12)

applicata al sistema (1.11) conduce a

xe = (A + BK)xe,

28

con xe := x−xr, come ben noto dalla teoria dei sistemi lineari. Poiche la matriceA+BK e asintoticamente stabile, la legge di controllo (1.12) stabilizza qualsiasitraiettoria di riferimento.

Se, anziche considerare il sistema lineare (1.11), si analizza un sistema nonlineare

x = f(x, u), f(x0, 0) = 0, (1.13)

dove f(·, ·) e differenziabile con continuita rispetto ad entrambi gli argomen-ti, cosa si puo dire circa l’esistenza di una legge di controllo asintoticamentestabilizzante? Definite

A :=

(δf

δx

)∣∣∣∣x=x0

B :=

(δf

δu

)∣∣∣∣u=0

,

si costruisce un sistema governato dall’equazione (1.11), detto sistema lineariz-zato. Come noto, Ljapunov ha dimostrato che esiste una legge di controllo stabi-lizzante se i modi instabili del sistema linearizzato sono controllabili, mentre nonesiste alcuna legge di controllo stabilizzante se il sistema linearizzato ha (almeno)un modo instabile non controllabile. L’unico caso in cui l’analisi di Ljapunov nonconduce ad alcuna conclusione sulla stabilizzabilita e quello in cui la matrice Adel sistema linearizzato abbia autovalori sull’asse immaginario associati a modinon controllabili e tutti gli altri modi non controllabili del sistema linearizzatocorrispondano ad autovalori con parte reale negativa. Nello studio della stabilita,i casi in cui

(δfδx

)ha uno o piu autovalori con parte reale che si annulla nel punto

di equilibrio x0 sono detti casi critici.Il teorema di Brockett si applica ai casi critici e fornisce delle condizioni

necessarie per l’esistenza di una legge di controllo differenziabile con continuita.Una immediata conseguenza del teorema di Brockett [11] e che per un sistemadel tipo

x =m∑

i=1

Xi(x)ui, (1.14)

dove x ∈ X ⊆ Rn e Xi(x) sono vettori linearmente indipendenti in x0, esiste unasoluzione al problema della stabilizzazione se e solo se il numero di ingressi meguaglia n, la dimensione dello spazio di stato X . In altri termini gli ingressidi controllo devono essere in numero pari alla dimensione di X . Si noti cheequazioni della struttura (1.14) sono tipiche della cinematica dei veicoli mobili.In particolare, detti x = (x1, x2, θ) il vettore di stato e X = R2 × S1 il relativospazio di stato, il sistema d’equazioni (1.4) che descrive la cinematica di unveicolo di Dubins (o di Reeds-Shepp) si puo riscrivere come

x =

cos θsin θ

0

u1 +

001

u2

che ha evidentemente la struttura (1.14). In questo caso n = 3, mentre il numerodegli ingressi di controllo e m = 2. Pertanto il teorema di Brockett consente

29

di concludere che non esiste alcuna legge di controllo di retroazione dallo stato,tempo invariante, continua e differenziabile in grado di stabilizzare un veicolo diDubins (o di Reeds-Shepp) attorno ad un punto fisso x0 ∈ X .

Si dimostra inoltre che non esiste alcuna legge di controllo in retroazione con-tinua in grado di stabilizzare qualsiasi traiettoria ammissibile per i veicoli mobiliin considerazione [38]. Sorge allora la questione seguente: poiche non e possibiledeterminare una legge di controllo universale per l’asintotica stabilizzazione di unriferimento qualsiasi, come invece accade per sistemi lineari, cos’altro e possibilefare? Tre approcci sono considerati dalla letteratura dedicata:

• Controllo in retroazione dell’uscita: consiste nella stabilizzazione di unaparte solamente dello spazio di stato del sistema. Un esempio tipico edato dal controllo della sola posizione del veicolo, senza alcuna regolazionedell’orientazione.

• Stabilizzazione pratica: si basa sull’idea di rilassare l’obiettivo della rego-lazione, ovvero la stabilizzazione asintotica. Ci si limita, cioe, a richiedereche lo stato del sistema si trovi in un intorno di raggio ε > 0 del riferi-mento; ε puo scegliersi arbitrariamente piccolo, ma non puo essere nullo.Un grande contributo a quest’approccio e stato dato dagli studi di Morine Samson, tra cui si citano [37] e [38].

• Stabilizzazione asintotica di traiettorie specifiche: restringendo l’insiemedelle traiettorie ammissibili, tramite l’imposizione di adeguati vincoli ul-teriori, il problema della stabilizzazione asintotica diviene risolvibile. Glistudi presenti in letteratura si rifanno a due principali tipologie di tra-iettorie: i punti fissi (problemi di posteggio) e traiettorie non stazionarie(problemi di inseguimento) [5], [6], [7]. Le tecniche di quantizzazione delcontrollo proposte in questa tesi e in [21] [23], in particolare, si possonoascrivere a questa classe.

La maggior parte degli studi sul controllo di veicoli mobili presenti in let-teratura e affrontata a tempo continuo ed assume che l’informazione sullo statodel sistema sia disponibile ad ogni istante. Nella pratica, invece, i controllorisono digitali e l’informazione proveniente dai sensori off-board, che si consideranoqui risorse condivise da un numero possibilmente elevato di agenti, puo esserericevuta a una frequenza media molto bassa. Inoltre il controllo ottimo per ve-icoli mobili con raggio di curvatura inferiormente limitato si dimostra essere ditipo bang-bang [51], cioe con escursioni istantanee, in istanti detti di commu-tazione (in inglese switching time), dei segnali di comando dal valore massimoa quello minimo. Qualitativamente dunque i controllori per i veicoli mobili de-vono avere una banda molto ampia, all’ottimo infinita. Cio fa comprendere che,pur ammettendo di disporre dell’informazione sensoriale ad ogni istante, la dis-cretizzazione di leggi di controllo progettate a tempo continuo conduce a unnotevole peggioramento delle prestazioni, proprio perche si introduce un errore

30

sul switching time dell’azione di controllo che puo essere pari ad un quanto tem-porale. Se, poi, la frequenza di campionamento dovesse essere, come si assumequi, molto bassa, le tecniche di campionamento progettate a tempo continuorisultano completamente inadatte [39].

1.6.2 Controllo model-predictive di un veicolo di Dubins

Si propone in questa sezione un algoritmo di controllo per veicoli mobili chesoddisfa i seguenti requisiti:

1. E in grado di operare con informazione trasmessa dai sensori off-board confrequenza di campionamento bassa e non uniforme. Il regolatore deve ge-stire l’eventualita di assenza di comunicazione, prendendo delle decisioniopportune. Si supporra nel seguito che l’informazione sensoriale esterocetti-va di cui il controllore di alto livello dispone sia costituita dalla posizionee dall’angolazione, misurate da un sistema GPS.

2. E semplice da implementare, in particolare deve applicarsi ad un unicicloe-puck.

3. E in grado di inseguire una traiettoria di riferimento arbitraria, data dallasuccessione di punti isolati di R2 × S1 in tempo minimo. In particolare latraiettoria puo ridursi ad un unico punto, percio lo stesso algoritmo deveimpiegarsi per problemi di inseguimento di traiettorie non stazionarie e perproblemi di posteggio.

Nelle sezioni precedenti si e parlato solamente di problemi di pianificazio-ne del movimento in catena aperta, nell’ipotesi che sia predisposto un anello diregolazione di basso livello per la reiezione dei disturbi e degli errori di model-lazione. D’altro canto, tra due successivi istanti in cui si ha la comunicazioneda parte del sistema GPS di posizione ed angolazione, il controllo ad alto livellodel veicolo non puo che operare ad anello aperto. L’idea di base e semplice ede assimilabile a quella di un controllo model predictive6. Quando vengono rice-vute le misure di posizione ed orientazione, il controllore pianifica la sequenzadi comandi per guidare il veicolo attraverso la sequenza di punti specificata; ilcomputo della traiettoria ottima puo essere condotto come esposto precedente-mente. Negli istanti in cui non c’e comunicazione da parte del GPS il regolatoreesegue l’ultimo piano di movimento calcolato. Una volta che l’informazione daparte del GPS sara nuovamente disponibile, un nuovo piano di movimento saracalcolato e quello vecchio verra sovrascritto.

Dato che, ogni volta che viene ricevuta informazione dal sistema GPS, ilpiano di movimento viene ricalcolato, si vede che non e necessario determinare lasequenza di controllo ottima lungo l’intera traiettoria, ma e sufficiente limitare

6Per una descrizione generale di tecniche di controllo model predictive si rimanda a [13]

31

l’orizzonte di previsione sino al prossimo punto. Una volta che questo vieneraggiunto, si pianifica la traiettoria fino al punto successivo e cosı via.

In assenza di alcun tipo di disturbo si ha che la distanza di Dubins7 dallaconfigurazione finale decresce in maniera monotona. Tuttavia questa versionedell’algoritmo e estremamente sensibile ad eventuali disturbi sulla posizione osull’orientazione del veicolo. Persino i rumori di quantizzazione dovuti alla pre-cisione numerica finita del processore su cui e implementato l’algoritmo possonodar luogo a comportamenti indesiderati, assimilabili a dei cicli limite, che por-tano il veicolo a girare su una circonferenza di raggio minimo in corrispondenzadei punti intermedi della traiettoria. Tali fenomeni possono essere occasionali oaddirittura, nel caso peggiore, portare il veicolo a ruotare indefinitamente.

La ragione di questo problema risiede nel fatto che, come gia accennato sopra,il veicolo di Dubins non e controllabile in tempo breve. Per chiarire il concettosi osservi la figura 1.5, ove sono rappresentati i punti del piano R2 equidistantidal punto (0, 0, 0) ∈ R2 × S1. Si noti che si e volutamente trascurata l’orien-tazione del punto finale, che richiederebbe di avere grafici diversi al variare delladifferenza tra l’orientazione finale e quella iniziale. Si rimanda a [12] e a [49] perapprofondimenti. Il fenomeno che si vuole analizzare appare quindi in manierapiu immediata in figura 1.5.

Figura 1.5. Le curve indicano l’insieme dei punti del piano R2 aventi la stessa distanza dalpunto (0, 0, 0) ∈ R2 × S1.

Cio che si puo osservare dalla figura 1.5 e che, mentre per punti la cui distanzaeuclidea dall’origine e maggiore di due volte il raggio di curvatura minimo rmin

i fronti assomigliano a circonferenze, quindi la distanza di Dubins e prossima a

7La distanza di Dubins tra due configurazioni x1 e x2 ∈ R2×S1 e definita come la lunghezzadel cammino minimo di Dubins che le congiunge. Si noti che la distanza di Dubins non e unametrica non essendo simmetrica. Si considerino, ad esempio, x1 = (0, 0, 0) e x2 = (1, 0, 0): ladistanza di Dubins da x1 a x2 e 1, mentre da x2 a x1 e 1 + 2πrmin. Al contrario la distanza diReeds-Shepp e una metrica. Per approfondimenti si rimanda a [53]

32

quella euclidea, nell’intorno dell’origine si ha un andamento completamente di-verso. In particolare, raggiungere posizioni che si trovano ”a lato” del veicoloo ”dietro” di esso richiede lunghe manovre. Si osserva anche che la distanza diDubins presenta dei punti di discontinuita in ogni intorno dell’origine. Fin tantoche il veicolo e distante (nel senso della metrica euclidea sul piano) dalla punto fi-nale, la ri-pianificazione della traiettoria, dovuta alla ricezione d’informazione daparte del sistema GPS, non determina un cambiamento sensibile della lunghezzapiano di movimento. Mano a mano che il veicolo si avvicina all’obiettivo, i puntidi discontinuita della distanza di Dubins sono sempre piu prossimi. In un intorno(con riferimento alla metrica euclidea sul piano) del punto finale e quindi suffi-ciente una piccola deriva, un errore di modellazione o di misurazione da parte delsistema GPS o, addirittura, un errore di posizione dovuto puramente al rumore diquantizzazione, legato alla precisione finita dell’aritmetica del processore su cuie implementato l’algoritmo di regolazione, per portare il sistema su una curva dilivello superiore. Se la ri-pianificazione del movimento avviene pochissimi istantiprima che venga raggiunto un punto della traiettoria, c’e il rischio che l’algoritmofaccia eseguire al veicolo un giro completo per correggere un errore possibilmenteinfinitesimale sulla posizione. Piu la frequenza media di ricezione del segnale dalGPS e elevata, piu e probabile che al termine della manovra correttiva si ripetalo stesso fenomeno. In tal caso il veicolo inizia a ruotare indefinitamente su unacirconferenza limite di raggio minimo passante per il punto finale, non riuscendoa proseguire nel cammino.

Una semplice soluzione al problema e la seguente: anziche sovrascrivere il vec-chio piano di movimento ogni volta che nuova informazione e disponibile, si puoscartare il nuovo piano se questo comporta un cammino troppo piu lungo delladistanza residua di quello vecchio. Il regolatore deve dunque aggiornare ad ognipasso, decrementandola, la distanza d mancante al raggiungimento del prossimoobiettivo. Quando viene calcolato un nuovo piano di movimento, di lunghezza l,per raggiungere il prossimo punto in traiettoria, questo viene accettato se e solose l < λd, dove λ > 1 e una costante che dev’essere tarata. Questo accorgimentoconsente di rimuovere il comportamento anomalo sopra descritto. Si e osservatosperimentalmente che la taratura di λ non risulta essere critica: λ = 1.1 produceuna legge di controllo che non e quasi distinguibile da quella ottenuta con λ = 3.Il motivo sta nel fatto che la discontinuita della distanza di Dubins in un intornodell’origine e molto forte e porta a valori di l ben piu grandi di d, mentre, invece,quando il veicolo e lontano dall’obiettivo d ' l.

Algoritmo di controllo

Il punto, o la sequenza di punti, in R2 × S1, che si vogliono raggiungere conun cammino minimo di Dubins con raggio di curvatura non inferiore a rmin,vengono memorizzati in una coda, denominata TRAJECTORY. In generale, essapuo essere aggiornata in maniera dinamica in “run time”, in modo da simulare

33

l’invio al veicolo, da parte di una eventuale stazione di comando, di ulterioripunti-obiettivo (xf , yf , θf ) durante il moto.

FINISHED e NEXT_POINT_REACHED sono variabili booleane inizializzate a false,che tengono traccia rispettivamente del completamento dell’intera traiettoria edel raggiungimento del prossimo punto della stessa.

CURRENT_POS e NEXT_POINT memorizzano i punti, in R2 × S1, da cui ha avu-to inizio il piano di movimento corrente e in cui si conclude. L’aggiornamentodi CURRENT_POS e conseguente alla ricezione da parte del GPS della posizione-orientazione del veicolo oppure al completamento del piano di movimento cor-rente. Il suo valore iniziale puo essere arbitrario, poiche viene sovrascritto conla prima ricezione della posizione da parte del GPS: solo allora il movimentoha inizio. L’aggiornamento di NEXT_POINT, avviene solamente al completamentodel piano di movimento corrente; inizialmente e impostato essere il primo puntodella traiettoria.

MOTION_PLAN memorizza il piano di movimento corrente da CURRENT_POS aNEXT_POINT. Contiene tre campi dati: TYPE, in cui e specificato il tipo di traiet-toria (LSR, RSL, ...); PARAM, in cui e memorizzata la lunghezza dei tre segmentidella traiettoria di Dubins, espressa in numero di passi di campionamento Ts delcontrollore di basso livello; LENGTH, che da la lunghezza del cammino, anch’essamisurata in numero di passi. Ogni aggiornamento di CURRENT_POS comporta ilcomputo di un nuovo MOTION_PLAN. SEGMENT_IN_EXECUTION serve da indice, permemorizzare quale dei tre segmenti che compongono il piano di movimento si staeseguendo; al completamento del terzo ed ultimo tratto si pone pari a 4.

TIMER e d fungono infine da contatori alla rovescia: il primo tiene traccia delnumero di passi mancanti al completamento del segmento corrente, periodo du-rante il quale i segnali di comando sono mantenuti costanti, il secondo memorizzala distanza, espressa in numero di passi, dal punto finale del piano di movimento.

Ad ogni istante di campionamento Ts (fissato) il processore a bordo del veicoloesegue il seguente algoritmo.

UPDATE_TRAJECTORY = false;

% FASE 1: Controllo fine traiettoriaIF (FINISHED) THEN{

Idle;}

IF (NEXT_POINT_REACHED) THEN{IF (ci sono ancora altri punti in TRAJECTORY) THEN{

CURRENT_POS = NEXT_POINT;NEXT_POINT = prossimo punto in TRAJECTORY;UPDATE_TRAJECTORY = true;

}ELSE{

FINISHED = true;

34

Set comandi a zero;Motion plan terminato: STOP;

}}

% FASE 2: Controllo ricezione informazione dal GPSIF (e stata ricevuta la posizione dal sistema GPS) THEN{

CURRENT_POS = quella fornita dal GPS;UPDATE_TRAJECTORY = true;

}

% FASE 3: Pianificazione della traiettoria, se necessarioIF (UPDATE_TRAJECTORY) THEN{

NEW_MOTION_PLAN = Traiettoria minima di Dubins da CURRENT_POS aNEXT_POINT;

IF (NOT e stata ricevuta la posizione dal sistema GPS) OR(NEW_MOTION_PLAN.LENGTH < lambda*d) THEN{MOTION_PLAN = NEW_MOTION_PLAN;

}ELSE {

% La correzione prodotta in seguito alla segnalazione del GPS% porta ad una manovra correttiva troppo lunga: il veicolo e% ormai troppo vicino alla configurazione voluta per tentare una% correzione; il prossimo punto si considera raggiunto.NEXT_POINT_REACHED = true;IF (ci sono ancora altri punti in TRAJECTORY) THEN{

NEXT_POINT = prossimo punto in TRAJECTORY;MOTION_PLAN = Traiettoria minima di Dubins da CURRENT_POS

a NEXT_POINT;}ELSE{

FINISHED = true;Set comandi a zero;Motion plan terminato: STOP;

}}SEGMENT_IN_EXECUTION = indice (1,2 o 3) del primo segmento non

nullo dei 3 che compongono il motion plan;d = MOTION_PLAN.LENGTH; % in numero di passiTIMER = numero totale di passi del segmento in esecuzione;

}

% FASE 4: Attuazione del comando

35

IF (TIMER > 0) THEN {TIMER = TIMER-1;mantenere comandi costanti;d = d-1;

ELSE {SEGMENT_IN_EXECUTION = indice del prossimo segmento non nullo del

motion plan; se non ce ne sono altri set 4;

IF (SEGMENT_IN_EXECUTION < 4) THEN {% Non sono stati ancora percorsi tutti e tre i segmenti di% traiettoriaTIMER = numero totale di passi del segmento in esecuzione -1;set comandi in modo da seguire il segmento in esecuzione;d = d-1;

}ELSE {

% Sono stati percorsi tutti e tre i segmenti di traiettoriaNEXT_POINT_REACHED = true;GO TO FASE 1; % Controllo fine traiettoria e ripianificazione

}}

Si osserva che il controllore appena definito e dead-beat in un passo, poiche,almeno in assenza di disturbi esterni, il veicolo raggiunge il primo punto della trai-ettoria assegnata senza errore. Ovviamente la presenza di un minimo disturboinvalida questa proprieta, ma, come si vedra in seguito dai grafici delle simu-lazioni, un andamento di tipo dead-beat dell’errore di inseguimento e comunqueriscontrabile.

Si noti che l’algoritmo proposto puo operare in real time, dato che il mas-simo tempo di esecuzione si ha quando, in prossimita di un punto intermedio,viene calcolato un piano di movimento “troppo lungo”, che dev’essere scartato esostituito con uno nuovo. Questo e l’unico caso che richiede il motion planning,l’operazione piu onerosa dal punto di vista computazionale, due volte in unostesso ciclo; tutte le altre istruzioni si riducono alla lettura di ingressi, a semplicioperazioni logiche, all’aggiornamento elementare di variabili e all’attuazione deicomandi. La pianificazione del moto per un dato veicolo ha comunque comp-lessita costante, poiche si calcola la traiettoria ottima solamente tra due puntialla volta. Come osservato nella sezione 1.5.3, inoltre, non e necessario risolverealcun problema di minimizzazione per via numerica: la traiettoria ottima e quel-la di lunghezza minima tra, al piu, sei possibili. Tecniche di pruning possono poiincrementare l’efficienza del motion-planning.

L’operazione di pianificazione e un evento relativamente raro, nell’ipotesi incui la frequenza media delle comunicazioni con il sistema GPS sia bassa: lamaggior parte dei cicli puo essere gestita semplicemente con il decremento diun timer. Questo rende disponibile il processore di bordo per altre operazioni,

36

di natura diversa dal controllo del movimento, quali, ad esempio, la raccolta el’elaborazione di dati dall’ambiente circostante.

1.6.3 Simulazione dell’algoritmo su un uniciclo

Descrizione del modello utilizzato per la simulazione

Per poter testare in simulazione l’algoritmo proposto e necessario disporre di unmodello fisico del veicolo. Si e scelto l’uniciclo e-puck perche si tratta di unveicolo dalla dinamica semplice, che e modellabile come una macchina di Dubinscon ottima approssimazione.

Figura 1.6. Uniciclo e-puck

L’ e-puck e dotato di svariati sensori a bordo: un accelerometro 3D, unatelecamera, 8 sensori di prossimita IR, per citarne alcuni. A differenza di altrimodelli di uniciclo non e dotato di odometro, poiche il controllo di posizione delleruote e garantito da due motori a passo. Il controllo a basso livello sulle ruote,dunque, e gia implementato. In quest’applicazione si utilizzano solo gli encoderdei motori a passo come trasduttori propriocettivi della posizione angolare delleruote. Test condotti presso il laboratorio Navlab, eseguiti facendo percorrereall’e-puck una traiettoria circolare su una superficie liscia per oltre due ore, finoall’esaurimento delle batterie, hanno rilevato l’assenza di derive, mostrando labuona qualita del controllo a basso livello compiuto dal motore a passo. Comesensore esterocettivo si assume un sistema di telecamere fisse, collegate ad uncomputer per l’elaborazione delle immagini, facente funzione di GPS. Si ipotizzache l’elaboratore ricavi la posizione e l’orientazione del veicolo dalle immagini ecomunichi con l’e-puck via radio. Il periodo che intercorre tra due comunicazionie una variabile aleatoria di media TGPS À 1 ms.

37

L’uniciclo si muove su una superficie orizzontale liscia. Le sue due ruotehanno un diametro di 41 mm e sono distanziate di 53 mm circa. Sono mosseda due motori a passo, che compiono 20 passi per giro, dotati di motoriduttorecon rapporto di riduzione 50:1, che porta a 1000 il numero di passi che il motoredeve compiere per un giro completo della ruota. La massima velocita angolare edi 1000 passi per secondo, che corrisponde a un giro al secondo e a una velocitatraslazionale di 12.88 cm/s. Il tempo di campionamento del controllore di bassolivello Ts e, per quanto detto, pari a 1 ms.

L’uniciclo e-puck non e vincolato ad un limite inferiore sul raggio di curvatura,bensı e in grado di ruotare su se stesso facendo girare le due ruote in versi opposti.Si impone, pero, all’uniciclo di muoversi in accordo con le equazioni del veicolo diDubins, fissando un unico verso di rotazione per entrambe le ruote. Con questascelta si ha che una curva di raggio minimo a destra (sinistra) e percorsa facendogirare solamente la ruota sinistra (destra). Il raggio minimo di curvatura haquindi lunghezza pari al semiasse delle ruote: 26.5 mm.

Simulazioni Matlab

L’apparato sperimentale e stato simulato con Matlab, in particolare utilizzan-do il pacchetto Simulink. Per semplicita e generalita d’implementazione si sonoutilizzate due S-function per poter scrivere in maniera diretta e piu astratta leequazioni cinematiche dell’uniciclo e l’algoritmo di controllo. Le equazioni dell’u-niciclo (1.4) sono state modificate aggiungendo degli ingressi esterni di disturbo,d1, d2 e d3, che provochino la deriva di ciascuno dei tre stati del sistema:

x1 = u1 cos(θ) + d1

x2 = u1 sin(θ) + d2

θ = u2 + d3.

Il codice necessario alla pianificazione della traiettoria di lunghezza minima estato raccolto in una function esterna, invocata dalla S-function del control-lore, che implementa direttamente le formule delle sezioni 1.4.3 e 1.5.3, e adottale condizioni necessarie di ottimalita riportate nella tabella della sezione 1.5.3per eseguire il pruning, incrementando l’efficienza complessiva dell’algoritmo.

Numerose simulazioni sono state eseguite variando la traiettoria da seguire, ilperiodo medio che intercorre tra due successive comunicazioni con il GPS, TGPS,il parametro λ, che regola la soglia decisionale per l’accettazione o il rifiuto di unnuovo piano di movimento, e i disturbi d1, d2 e d3.

Le figure seguenti sono state ottenute simulando coppie di esperimenti incui l’intervallo che intercorre tra due successivi rilevamenti del sistema GPS euna variabile aleatoria normale di media TGPS, pari a 2 secondi in un caso ea 5 nell’altro, e di varianza 0.1TGPS. Si tratta di frequenze di campionamentoestremamente basse. I disturbi sono stati volutamente scelti di molto superioriai valori sperimentali, che avevano mostrato assenza di derive: d1 = 1 mm/s,

38

d2 = −1 mm/s e d3 = 0.01 rad/s. Le traiettorie scelte sono: una circonferenza(fig. 1.7), una traiettoria a forma di 8 (fig. 1.8), per testare l’algoritmo su uncammino con raggio di curvatura variabile, e uno zig-zag molto stretto (fig. 1.9),in cui le configurazioni obiettivo hanno orientazioni sfasate di π e sono distanziatedi meno di 2rmin, per cui il raggio di curvatura medio della traiettoria e inferiorea quello minimo dell’uniciclo. La configurazione iniziale, rappresentata in nero,non e in nessun caso allineata con il primo punto della traiettoria di riferimento,disegnata in rosso; al riferimento e sovrapposta la traiettoria effettiva del robot,in blu. I triangoli indicano l’orientazione, i cerchi le dimensioni dell’e-puck. Lefigure sono in scala.

−0.4 −0.3 −0.2 −0.1 0 0.1 0.2 0.3 0.4

−0.3

−0.2

−0.1

0

0.1

0.2

0.3

x [m]

y [m

]

Unycicle configuration

−0.4 −0.3 −0.2 −0.1 0 0.1 0.2 0.3 0.4

−0.3

−0.2

−0.1

0

0.1

0.2

0.3

x [m]

y [m

]

Unycicle configuration

Figura 1.7. Inseguimento di una traiettoria circolare di raggio 30 cm, con TGPS = 2 s, asinistra, e 5 s a destra.

−0.4 −0.3 −0.2 −0.1 0 0.1 0.2 0.3 0.4

−0.3

−0.2

−0.1

0

0.1

0.2

0.3

x [m]

y [m

]

Unycicle configuration

−0.4 −0.3 −0.2 −0.1 0 0.1 0.2 0.3 0.4

−0.3

−0.2

−0.1

0

0.1

0.2

0.3

x [m]

y [m

]

Unycicle configuration

Figura 1.8. Inseguimento di una traiettoria a forma di 8 con TGPS = 2 s, a sinistra, e 5 s adestra.

39

−0.1 0 0.1 0.2 0.3 0.4 0.5−0.1

−0.05

0

0.05

0.1

x [m]

y [m

]

Unycicle configuration

−0.1 0 0.1 0.2 0.3 0.4 0.5−0.1

−0.05

0

0.05

0.1

x [m]

y [m

]

Unycicle configuration

Figura 1.9. Inseguimento di una traiettoria a zig-zag formata da 10 configurazioni con orien-tazioni sfasate di π e distanziate di 45 mm (< 2rmin = 51 mm). TGPS = 2 s, a sinistra, e 5 sa destra.

Il grafico riportato in figura 1.7 e da confrontarsi con quello mostrato nellafigura 10 di [39], articolo in cui si propone un algoritmo di controllo per robotmobili con frequenza di campionamento molto bassa. Il miglioramento delleprestazioni appare piuttosto evidente.

L’algoritmo di controllo proposto in [39] prevede essenzialmente di pianificarela traiettoria a tempo continuo interpolando due punti successivi, (x1i

, x2i, θi) e

(x1f, x2f

, θf ), con archi di circonferenze. D’altra parte, in generale, non esistealcuna circonferenza tangente due punti orientati in R2×S1, ma, data una confi-gurazione iniziale (x1i

, x2i, θi), si possono determinare l’arco passante per il punto

finale, (x1f, x2f

) in R2, avente pero errata orientazione θf , e l’arco di circonferenzatangente la retta passante per (x1f

, x2f, θf ), che termina in un punto avente cor-

retta orientazione θf , ma posizione (x1f, x2f

) diversa da quella desiderata. L’ideaproposta in [39] e di attuare una combinazione lineare convessa degli ingressi nec-essari per inseguire i due archi. Si osserva, pero, che tale approccio da originea delle oscillazioni sistematiche poiche la configurazione finale, in generale, nonviene mai raggiunta esattamente.

Il metodo qui presentato consiste, invece, nel congiungere due configurazioniconsecutive con un cammino ottimo di Dubins. In questo modo e possibile garan-tire che ciascun punto venga raggiunto con errore nullo, almeno in assenza didisturbi esterni. A differenza di quello in [39], l’algoritmo di controllo espostoqui e dunque dead-beat. Le figure riportate mettono in luce questa caratteristica:si possono individuare, infatti, gli istanti in cui interviene una nuova pianificazio-ne del movimento, che pone fine alla deriva del sistema, provocata dai disturbiesterni, riportando il veicolo sul riferimento. Il comando di controllo non e man-tenuto costante tra due successive ricezioni della trasmissione del GPS, come in[39], ma e costante a tratti: cio e reso possibile dall’introduzione di un controlloredi basso livello, che opera sempre ad alta frequenza di campionamento. Grazie aquesto schema a due livelli, in assenza di disturbi, si puo garantire un errore diinseguimento nullo anche senza ricezione di informazione dal GPS. In presenzadi perturbazioni esterne, i grafici precedenti evidenziano un buon inseguimentoanche con tempi di campionamento di 5 secondi.

Il metodo presentato si basa sulla quantizzazione del controllo, ovvero sullarestrizione a priori delle traiettorie ammissibili per il sistema. D’altro canto, si e

40

−0.2 −0.1 0 0.1 0.2 0.3 0.4 0.5 0.6

0

0.1

0.2

0.3

0.4

0.5

0.6

x [m]

y [m

]

Unycicle configuration

1

2

3

4

5

6

Figura 1.10. Inseguimento di una traiettoria composta da 6 punti generati in maniera pseudo-aleatoria con densita di probabilita uniforme nel compatto [0, 0.6]× [0, 0.6]× [0, 2π] ⊂ R2×S1.TGPS = 2 s. La traiettoria di riferimento, in rosso, e quasi perfettamente sovrapposta a quellaeffettiva, in blu.

anche detto che non esiste nessuna legge di controllo continua in grado di stabi-lizzare qualsiasi traiettoria. La classe delle traiettorie ottenibili con l’algoritmoproposto e pero sufficiente a congiungere qualsiasi sequenza di punti isolati inR2×S1 in tempo minimo. La figura 1.10, a tale proposito, mostra che l’algoritmoe in grado di guidare l’e-puck in tempo minimo attraverso una sequenza di puntigenerata in maniera pseudo-aleatoria.

1.7 Conclusioni

L’approccio proposto al problema della pianificazione del movimento fonde iprincipi fondamentali della pianificazione ottima di traiettorie per un veicolo diDubins, quelli della quantizzazione del controllo e del model predictive control.Questa tecnica presenta alcuni vantaggi:

1. Non richiede che l’informazione GPS sia ricevuta ad istanti equidistantinel tempo. Per sistemi drift-less, se il modello e verosimile, sfruttando lecapacita del motion-planner, la frequenza con cui e richiesta informazionedal GPS e molto bassa.

2. I risultati teorici ricavati da Dubins [19] garantiscono l’ottimalita delletraiettorie generate, ma il processore a bordo del veicolo non deve ri-solvere alcun problema di minimizzazione per via numerica, riducendocosı il carico computazionale. Se si risolvesse per via numerica un pro-blema di minimizzazione si dovrebbero memorizzare gli ingressi ottimi

41

u∗(0), u∗(1), . . . , u∗(h), dove l’orizzonte h potrebbe essere molto grande.Invece la traiettoria ottima di Dubins e individuata da quattro parametrisolamente: il tipo, e le tre lunghezze dei segmenti che la compongono.

3. La traiettoria viene pianificata con un orizzonte ristretto: dalla configura-zione corrente fino al prossimo punto solamente. Questo garantisce che l’al-goritmo funzioni in tempo reale anche per traiettorie molto lunghe. Inoltrela maggiore quantita dei calcoli viene eseguita in fase di pianificazione dellatraiettoria, quindi relativamente di rado. Per la maggior parte del tempoil processore puo gestire altri task. La traiettoria da seguire puo poi essereaggiornata con veicolo gia in movimento.

4. Nel caso a tempo continuo, gli algoritmi proposti in letteratura per il track-ing e per il posteggio sono molto diversi: nel caso a tempo discreto, in-vece, l’algoritmo presentato risolve entrambi i problemi. Inoltre l’algoritmoproposto e applicabile a una qualsiasi sequenza di punti isolati in R2 × S1.

5. In simulazione si sono ottenuti risultati buoni anche in presenza di unleggero drift. In tal caso pero le prestazioni sono tanto migliori tanto piualta e la frequenza media di ricezione dell’informazione da parte del GPS. Isensori di bordo infatti non sono in grado di rilevare disturbi esterni agentisul veicolo, ma solamente quelli agenti sulle ruote. Solo il GPS puo rilevarel’azione di disturbi esterni.

L’algoritmo presentato prevede che le manovre, cioe i transitori tra due in-tervalli in cui comandi restano costanti, abbiano durata nulla. In altri termini ilveicolo viene pilotato con comandi costanti a tratti. Il modello di Dubins [19],d’altra parte, non prevede alcun vincolo sulla continuita della legge di control-lo, ne questo e un requisito per il controllo di un uniciclo con motori a passo.D’altra parte l’estensione ad automi MA aventi un insieme delle manovre nonnullo e immediato, alla luce del quadro teorico generale. La complicazione delladinamica, poi, non porta quasi alcun aggravio computazionale, poiche il proble-ma di pianificazione, in questo caso, richiede, in piu, solamente il computo dellamatrice 3× 3 associata a gω, tramite moltiplicazione di matrici note, in numeropari a quello delle manovre da eseguire, e la sua inversione.

Trattandosi di una tecnica fondata sulla quantizzazione del controllo, nontutte le traiettorie possibili per il veicolo vengono generate ed inseguite. L’au-toma considerato per il controllo del robot e-puck, ad esempio, prevede unica-mente l’avanzamento alla velocita massima. Non e quindi possibile procederea una velocita ridotta. E possibile aggirare il problema aumentando la libre-ria delle primitive di movimento, a scapito pero della rapidita di calcolo delmotion-planner.

42

Capitolo 2

Pianificazione del movimento inambienti con ostacoli

2.1 Introduzione

Nella maggior parte delle applicazioni, i veicoli mobili si trovano a doversi muo-vere in ambienti in cui sono presenti ostacoli. Nasce dunque il problema digenerare ed eseguire un piano di movimento che consenta di far muovere il vei-colo da un punto ad un altro evitando la collisione con gli ostacoli presenti. Uncammino che non provoca la collisione del veicolo con gli ostacoli circostanti edetto sicuro (in inglese, safe).

Il problema della pianificazione di traiettorie in ambienti con ostacoli e statooggetto di considerevole interesse da parte di studiosi di robotica e d’intelligenzaartificiale. A grandi linee e possibile individuare quattro approcci generali alproblema della pianificazione del movimento [22]:

• Metodi basati sulla decomposizione dello spazio di stato in un numero finitodi celle, all’interno delle quali e semplice individuare dei cammini che nondanno luogo a collisioni. Il problema si riduce dunque all’individuazione diuna sequenza di celle adiacenti che comprenda le configurazioni iniziali efinali.

• Metodi basati su roadmap. Questa categoria di tecniche e fondata sullacostruzione di una rete di traiettorie predefinite in grado di generare tut-to lo spazio delle configurazioni sicure. Il problema della pianificazionedel cammino attraverso un campo di ostacoli viene ricondotto ad uno diindividuazione di un cammino minimo su grafo, risolvibile con algoritmiben noti, quale quello di Dijkstra. A questa famiglia di metodi si possonoascrivere gli studi pubblicati in [9], [29], [30], [36] e [44].

• Una terzo approccio e l’impiego di campi di potenziale artificiali. Un cam-mino sicuro viene generato facendo muovere il veicolo in accordo a delle“forze” locali definite come il gradiente negativo di una qualche funzione

43

potenziale. Questa funzione e tale da produrre forze attrattive verso l’obi-ettivo (in corrispondenza dell’obiettivo la funzione ha un minimo) e repul-sive, in modo da allontanare il veicolo dagli ostacoli (ove la funzione ha deimassimi) [27], [40].

• Una quarta opzione e rappresentata da metodi roadmap probabilistici. Lospazio delle configurazioni viene esplorato costruendo un albero con radicenella configurazione iniziale. Ogni ramo viene generato in maniera pseudocasuale: se il percorso associato e sicuro il ramo viene effettivamente ag-giunto all’albero, altrimenti viene scartato. Lo scopo e raggiungere una con-figurazione dalla quale esiste un percorso diretto verso l’obiettivo. Questetecniche sono particolarmente efficienti per sistemi in cui lo spazio di confi-gurazione abbia dimensione elevata. Gli algoritmi sinora disponibili hannoinfatti complessita che cresce esponenzialmente con la dimensione dellostato [22].

Il metodo forse piu generale e meglio formulato per affrontare problemi dipianificazione e l’impiego del controllo ottimo [48]. Come visto nel primo capito-lo, la traiettoria ottima si potrebbe ottenere minimizzando il funzionale di costo(1.3), con i vincoli (1.1) e (1.2); gli ostacoli potrebbero, cioe, essere rappresentaticon vincoli di tipo (1.2) e tra questi compresi. Tuttavia l’impiego delle tecni-che tradizionali di controllo ottimo, quali il principio del massimo, renderebbe lasoluzione del problema intrattabile dal punto di vista computazionale, in casi nonbanali, tanto piu che, si vuole poter implementare l’algoritmo di pianificazione surobot dalle limitate risorse hardware. Inoltre l’unificazione del problema dell’in-seguimento di una data traiettoria e quello della determinazione di un camminosicuro attraverso gli ostacoli richiederebbe al controllore del veicolo di conoscerela topologia globale di tutto l’ambiente circostante. Quest’ipotesi non e com-patibile con il quadro esposto nel capitolo precedente, in cui si assumeva che ilveicolo ricevesse l’informazione esterocettiva da un’unita esterna, collegata ad unsistema di telecamere. Solo l’unita esterna e in grado di rilevare informazionedalla globalita dell’ambiente in cui il veicolo si trova.

Dalle precedenti considerazioni emerge la necessita di suddividere il problemasu due livelli: il piu alto dev’essere implementato nell’unita esterna, deve deter-minare un cammino sicuro e comunicarlo al controllore del veicolo, mentre illivello inferiore deve consentire al veicolo di inseguire il riferimento calcolato. Lostudio di quest’ultimo livello di controllo e gia stato condotto nel capitolo prece-dente: rimane da progettare un metodo efficiente per il computo di un camminosicuro, che soddisfi i vincoli sul raggio di curvatura e che, possibilmente, abbialunghezza minima.

La soluzione proposta in questo capitolo e ascrivibile alla classe dei metodibasati su roadmap. Si tratta di un algoritmo deterministico: i veicoli di Du-bins, infatti, hanno uno spazio di stato di dimensione tre, quindi relativamentepiccolo. In queste condizioni i metodi deterministici consentono risultati piu che

44

soddisfacenti ed e piu semplice analizzarne le prestazioni rispetto alle contropartiprobabilistiche.

2.2 Definizione del problema e sue proprieta

Per la definizione del problema si fa riferimento a quanto esposto nel precedentecapitolo, nella sezione 1.2.2. Rispetto a quanto ivi scritto si devono introdurreipotesi e vincoli ulteriori.

Si rammenta che il veicolo e modellato come una regione R in movimentorigido sul piano, alla quale e solidale un vettore unitario v: l’orientazione. Lospazio di stato del sistema e X ∼= R2 × S1, dove S1 e l’insieme dei punti sullacirconferenza unitaria, e lo stato del sistema e descritto dalla terna (x1, x2, θ).La cinematica del veicolo e governata dalle equazioni del veicolo di Dubins (1.4),dove l’ingresso di comando e la coppia (u1, u2) ∈ U = [0, vmax] × R, u1 essendoil modulo della velocita di traslazione nella direzione del veicolo v e u2 essendoil modulo della velocita angolare di rotazione attorno alla normale al piano. Ilraggio di curvatura e non inferiore a rmin, come affermato dall’equazione (1.5).Come gia nel primo capitolo, assegnati un punto iniziale (x1i

, x2i, θi) e uno finale

(x1f, x2f

, θf ) in X , l’indice di costo che si vuole minimizzare e il tempo tf richiestoper compiere la traiettoria.

Rispetto a quanto gia affermato in precedenza si introducono delle ipotesiulteriori: la forma del veicolo si assume simmetrica rispetto al suo asse principalev, e la sua semi-larghezza sara indicata con h. Ci si limita a considerare ostacolipoligonali, indicati con Oi, i = 1, . . . , l; l’insieme dei loro N vertici sara denotatocon V . Oltre al vincolo anolonomo (1.5), si impone anche una condizione diassenza di collisioni:

R(x1(t), x2(t), θ(t)) ∩ Oi = ∅, i = 1, . . . , l, ∀t ∈ [0, tf ], (2.1)

dove la scrittura R(x1(t), x2(t), θ(t)) esplicita la dipendenza della regione Roccupata dal veicolo dalla sua configurazione al tempo t.

Trovare una soluzione a tale problema e piuttosto difficile in generale. Esistepero un caso in cui le considerazioni sui cammini ottimi ricavate da Dubins [19](e Reeds-Shepp [45]) rimangono valide, come afferma la seguente

Proposizione 2.1. Si consideri un veicolo di forma circolare di raggio h = rmin.La soluzione al problema appena formulato, se esiste, e una traiettoria data dallaconcatenazione di segmenti di retta e di archi di circonferenza di raggio rmin.

Dimostrazione: La prova della proposizione e riportata in [9]. ¤

45

2.3 Algoritmo per la pianificazione del movi-

mento

L’algoritmo qui proposto si ispira a quello pubblicato da Bicchi et. al. in [9], permacchine di Reeds-Shepp. La guida di un veicolo di Dubins attraverso campi diostacoli risulta piu difficile di quella di una macchina di Reeds-Shepp, non essendopossibile retrocedere per compiere manovre cosiddette di back-up. L’algoritmosopra citato puo produrre dei cammini non regolari, contenenti cuspidi. Il metodoqui proposto, invece, grazie ad accorgimenti aggiuntivi, quali l’esplorazione “adalbero” dell’ambiente e la costruzione dinamica del grafo di visibilita, consente dirisolvere questo problema, rendendo il cammino generato percorribile dal veicolosenza mai bisogno di retrocedere. Alcuni “punti morti” dell’algoritmo di Bicchi,poi, sono stati rimossi.

Prima di presentare il nuovo algoritmo proposto in questa tesi, si riassumequello pubblicato in [9]. Alla base di entrambi i metodi, infatti, c’e il risultato es-posto nella proposizione 2.2. Nella sezione seguente si prendera in considerazionel’algoritmo di Dijkstra per la ricerca di un cammino minimo su un grafo pesatocon costi non negativi: esso si fonda infatti, come si vedra, su una proprieta difondamentale importanza, compendiata nella proposizione 2.3. Tale proprieta ebasilare anche per il nuovo algoritmo proposto nella sezione 2.3.3.

2.3.1 Un algoritmo per guidare un veicolo di Reeds-Sheppattraverso un ambiente con ostacoli

L’algoritmo proposto in [9] puo cosı riassumersi:

1. Tracciare N circonferenze di raggio ρ = max{rmin, h} centrate in ciascunodei vertici in V . Tracciare poi le due circonferenze passanti per il puntoiniziale (x1i

, x2i) e tangenti la retta passante per (x1i

, x2i) con pendenza θi.

Fare lo stesso per il punto finale.

2. Considerare tutte le N+4 circonferenze cosı ottenute a due a due e tracciarei quattro segmenti che giacciono sulle tangenti comuni e sono compresitra i punti di tangenza. Si considerino poi tutti gli archi di circonferenzacongiungenti due punti di tangenza. Il diagramma del cammino di base(BPD, per basic path diagram) contiene due segmenti orientati per ciascunodei segmenti lineari e circolari ottenuti.

3. Il BPD puo contenere cammini non sicuri, che cioe non possono essereseguiti dal veicolo senza collisioni. Ciascun segmento diretto dev’esseretestato e i segmenti che provocano collisioni devono essere rimossi. Ingenerale, un segmento potrebbe essere sicuro se percorso in un verso enon esserlo nell’altro. Se pero il veicolo e simmetrico rispetto alla lineapassante per il suo punto di riferimento e parallela all’asse principale del

46

veicolo, la direzione del moto e irrilevante e un BPD piu semplice puo essereconsiderato.

4. Dal diagramma del cammino cosı emendato, si costruisce un grafo G comesegue:

(a) le configurazioni iniziale e finale sono nodi di G;

(b) tutti i punti di tangenza tra un segmento lineare e un arco (conorientamento parallelo al segmento di retta) sono nodi di G;

(c) due nodi i e j di G sono connessi da un arco orientato da i a j se esisteun segmento o un arco orientato che li congiunge nel diagramma delcammino emendato;

(d) ciascun arco ha un costo pari alla lunghezza del segmento ad essoassociato.

5. Si ricerca un cammino di costo minimo sul grafo G dal nodo associato a(x1i

, x2i) a quello corrispondente a (x1f

, x2f).

L’algoritmo appena presentato gode di un’importante proprieta, compendiatanella seguente

Proposizione 2.2. Sia dato un veicolo di forma circolare di raggio h = rmin chesi muova in uno spazio bidimensionale con ostacoli poligonali. Una condizionesufficiente affinche un cammino per tale veicolo sia una soluzione ottima del pro-blema enunciato nella sezione 2.2, e che sia regolare (cioe non contenga cuspidi)e sia stato generato con l’algoritmo appena presentato.

Dimostrazione: Per la prova di rimanda a [9]. ¤

La proposizione precedente offre solo una condizione sufficiente, non una nec-essaria, essenzialmente per due ragioni. Innanzitutto l’algoritmo puo generaredei cammini contenenti delle cuspidi, nel qual caso non e piu possibile dimostrarel’ottimalita. In secondo luogo non genera tutte le soluzioni ottime al problemadel cammino minimo attraverso gli ostacoli: l’algoritmo cioe non e completo.La difficolta maggiore nasce dal fatto che non e garantito che il veicolo giungaal punto finale con l’orientazione desiderata θf , bensı potrebbe invece arrivareruotato nel verso opposto, cioe con orientazione θf + π (fig 2.1, sinistra). Unasoluzione euristica e quella di compiere, a posteriori, una manovra di inversione,come rappresentato in fig 2.1, a destra.

2.3.2 L’algoritmo di Dijkstra

L’algoritmo di Dijkstra e ben noto nell’ambito della ricerca operativa e consentedi calcolare in tempo O(n2) i cammini minimi da un assegnato vertice s a tut-ti gli altri vertici t di un grafo pesato con n nodi e costi non negativi. Sulla

47

Figura 2.1. A sinistra: esempio di errata orientazione della configurazione del finale delcammino generato dall’algoritmo presentato in [9]; soluzione ivi proposta, a destra.

sua rivisitazione si basa l’algoritmo per la ricerca di un cammino minimo si-curo per un veicolo di Dubins attraverso un ambiente con ostacoli proposto inquesta tesi. Si richiameranno qui brevemente le sue peculiarita, che sarannosfruttate nella trattazione del nuovo algoritmo, delegata alla sezione successiva.Per approfondimenti si rimanda a testi didattici di ricerca operativa, come [20].

Sia G = (V, E) un grafo orientato e pesato in cui V e l’insieme dei nodi edE quello degli archi. Sia C la matrice il cui generico elemento cij memorizza ilcosto dell’arco (i, j); sia cij ≥ 0 per ogni coppia (i, j).

Definizione 2.1. Dato un sottoinsieme di vertici S ⊆ V , un taglio orientato (ininglese, directed cut) di G e un sottoinsieme di archi del tipo

δ+G(S) := {(i, j) ∈ E : i ∈ S, j /∈ S}

oppure del tipoδ−G(S) := {(i, j) ∈ E : i /∈ S, j ∈ S}.

L’algoritmo di Dijkstra si basa sulla seguente notevole proprieta.

Proposizione 2.3. Siano noti i costi Li dei cammini minimi da s ad ogni verticei appartenente ad un dato insieme S ⊂ V con s ∈ S (Ls := 0). Sia inoltre(v, w) := arg min{Li + cij : (i, j) ∈ δ+

G(S)}. Se cij ≥ 0 per ogni (i, j) ∈ E, alloraLv + cvw rappresenta il costo del cammino minimo da s a w.

Dimostrazione: Per la semplice prova si rimanda a [20]. ¤

La proprieta appena enunciata suggerisce immediatamente un algoritmo perla ricerca del cammino minimo su un grafo. Inizialmente il sottoinsieme S deivertici contiene solo il nodo iniziale s. Ad ogni passo viene introdotto in S unnuovo nodo w, come indicato dalla precedente proposizione. In tal modo, ad

48

ogni ciclo, S e l’insieme dei nodi verso cui e noto un cammino orientato di costominimo. E garantito che l’algoritmo termina in n passi, quando cioe S = V .

Un’implementazione efficiente dell’algoritmo richiede una struttura dati cosıdefinita per ogni j ∈ S\{s}:

FLAG(j) =

{TRUE, se j ∈ SFALSE, altrimenti;

L(j) =

{costo del cammino minimo da s a j, se j ∈ Smin{L(i) + cij : i ∈ S}, altrimenti;

PRED(j) =

{predecessore di j nel cammino minimo da s a j, se j ∈ Sarg min{L(i) + cij : i ∈ S}, altrimenti;

mentre, per definizione, FLAG(s) := TRUE, L(s) := 0 e PRED(s) := s. L’algoritmodi Dijkstra puo dunque scriversi nella maniera seguente:

% InizializzazioneFOR j = 1:n{

FLAG(j) = FALSE;PRED(j) = s;L(j) = C(s,j);

}FLAG(s) = TRUE;L(s) = 0;

% Espansione di SFOR k = 1:n-1 {

L_min = INF;% Individua w = arg min {L(j): j non e in S}FOR j = 1:n {

IF (NOT FLAG(j) AND L(j) < L_min) THEN {L_min = L(j);w = j;

}}% Aggiorna S = S U {w}FLAG(w) = TRUE;FOR j = 1:n {

% Aggiorna L(j) e PRED(j) per ogni j non in SIF (NOT FLAG(j) AND L(w) + C(w,j) < L(j)) THEN {

L(j) = L(w) + C(w,j);PRED(j) = w;

}}

}

Si vede facilmente che si tratta di un algoritmo di complessita O(n2), poichecontiene due cicli annidati che scandiscono tutti gli n vertici del grafo, eseguendoad ogni passo operazioni di complessita costante.

49

2.3.3 Un algoritmo per guidare un veicolo di Dubins at-traverso un ambiente con ostacoli

La regolarita dei cammini generati dall’algoritmo presentato nella sezione 2.3.1 euna condizione che consente di provarne l’ottimalita, ma, fatto ancor piu impor-tante, e necessaria per la guida di veicoli di Dubins. Si osserva che l’algoritmoproposto nella sezione 2.3.1 e in grado di generare, tra gli altri, un camminoottimo regolare, a livello di quello che e stato chiamato diagramma del camminoemendato, ma non e sempre in grado di individuarlo. Cio e dovuto, intuitiva-mente, al fatto che l’esplorazione dell’ambiente non avviene in maniera orientata,a partire, cioe, dal punto iniziale verso tutti gli altri vertici, bensı il grafo G vienecostruito in un’unico passo. In un secondo momento il problema viene risoltosul grafo G con algoritmi ben noti, quali, ad esempio, l’algoritmo di Dijkstra.Al contrario, solo espandendo l’albero di ricerca un vertice dopo l’altro si puogarantire che il cammino finale non contenga manovre di back-up. Per di piul’algoritmo di Dijkstra fa esattamente questo, costruendo un albero minimo suun grafo dato. L’intuizione e dunque quella di costruire la matrice dei costi delgrafo poco alla volta.

Alcune considerazioni geometriche preliminari

Figura 2.2. Due circonferenze di raggio ρ e le loro tangenti comuni

Prima di scrivere lo pseudo-codice dell’algoritmo proposto si espongono al-cune semplici considerazioni geometriche. Date due circonferenze C e C ′ di ugualeraggio ρ e centri C e C ′, esistono quattro rette tangenti comuni se le circonferenzesono disgiunte, mentre solo due tangenti se le circonferenze si intersecano, cioe||CC ′|| < 2ρ. Con riferimento alla figura 2.2, le tangenti mutuamente paralleleAA′ e EE ′ esistono sempre, per qualsiasi scelta di C e C ′, mentre le tangenti chesi intersecano BB′ e DD′ no. Se pero si fissa un verso di percorrenza delle circon-ferenze, orario oppure antiorario, dato un punto p su C esiste al piu un camminoorientato, composto da un arco di C e da un segmento di retta tangente, che

50

comincia in p e raggiunge C ′ con orientamento concorde a quello fissato. Pre-cisamente, se le circonferenze sono orientate concordemente, entrambe o in sensoorario o antiorario, tale cammino esiste sempre ed e composto da un segmentodi una delle due rette tangenti parallele; se invece il verso di percorrenza dellecirconferenze e discorde, un cammino esiste se e solo se ||CC ′|| ≥ 2ρ e constadi un segmento di una delle tangenti secanti. Quindi, fissata una configurazione(x1i

, x2i, θi) in R2 × S1, con (x1i

, x2i) ∈ C e θi pari all’inclinazione della tangente

alla circonferenza orientata C in (x1i, x2i

), esistono al piu due configurazioni ditipo (x1f

, x2f, θf ), con (x1f

, x2f) ∈ C ′ e θf pari all’inclinazione della tangente

a C ′ in (x1f, x2f

), raggiungibili da (x1i, x2i

, θi) percorrendo un tratto di arco diC e un segmento di una tangente comune a C e C ′. I due valori di (x1f

, x2f, θf )

dipendono solamente dal verso di percorrenza che (x1i, x2i

, θi) induce su C (orarioo antiorario). La lunghezza del cammino da (x1i

, x2i, θi) a (x1f

, x2f, θf ), invece,

dipende anche dalla posizione angolare di (x1i, x2i

, θi) su C.

Presentazione dell’algoritmo

Le semplici considerazioni geometriche appena esposte suggeriscono un nuovoalgoritmo per la guida di una macchina di Dubins attraverso ostacoli poligonali.Come proposto in [9] ad ogni vertice in V si associa una circonferenza di raggioρ. Ciascuna circonferenza puo percorrersi in senso orario oppure antiorario: adogni circonferenza dunque si associano due nodi del grafo (anziche quattro comein [9]). Tali nodi non sono associati a punti del piano con una posizione definitaa priori, come in [9], bensı ai versi di percorrenza delle circonferenze centrate suivertici degli ostacoli. Fanno eccezione i nodi 1 e 2 assegnati rispettivamente allaconfigurazione iniziale e a quella finale. Per tenere traccia della configurazionecon la quale il veicolo puo raggiungere una generica circonferenza orientata C enecessario introdurre una matrice CONFIG di dimensione (2N + 2)× (2N + 2).

In principio sono note solamente la configurazione iniziale, associata conven-zionalmente al nodo 1 del grafo, e quella finale, corrispondente al nodo 2. Alprimo passo si cerca di raggiungere dalla configurazione iniziale quella finale e,se cio non produce un cammino sicuro, tutte le 2N circonferenze orientate. Se laj-esima circonferenza orientata e raggiunta da un cammino privo di collisioni apartire dalla configurazione iniziale, allora CONFIG(1, 2+ j) memorizzera la confi-gurazione di arrivo. I costi dei cammini corrispondenti saranno invece allocati inC(1, 2 + j). La matrice dei costi associata al grafo viene dunque costruita manoa mano che i cammini vengono generati. Si assegna costo infinito ai camminiche danno luogo a collisioni. Fatto cio, si considera il cammino generato aventelunghezza minima: il nodo associato alla circonferenza orientata raggiunta dalcammino minimo e il prossimo nodo ad essere elaborato o, usando la simbologiaintrodotta nella sezione dedicata all’algoritmo di Dijkstra, e il prossimo nodo wad entrare in S. Al ciclo successivo, la configurazione associata a w, CONFIG(1, w),sara considerata come nuova configurazione iniziale e si cerchera di raggiungereda questa la configurazione finale; se cio non produce un cammino sicuro, si

51

genereranno i cammini per raggiungere le altre circonferenze orientate, come fat-to al primo passo, e cosı via. Come per l’algoritmo di Dijkstra, la terminazionee garantita dopo, al piu, 2N + 1 passi, quando cioe il sottoinsieme dei nodi es-plorati S coincide con l’insieme di tutti i nodi del grafo. Ad ogni passo, infatti,un nuovo nodo viene elaborato; una volta elaborati, i nodi non necessitano dioperazioni ulteriori. L’esplorazione dello spazio avviene costruendo un albero dicosto minimo, cioe si ricercano nuovi cammini a partire da una configurazionenon ancora elaborata solo se questa e stata raggiunta con un cammino minimoche parte dal punto iniziale.

Si riporta qui, nel dettaglio, lo pseudo-codice dell’algoritmo proposto. Glioutput sono costituiti da PATH, lista delle configurazioni che seguono xi in uncammino sicuro di lunghezza minima verso xf , e LENGTH, che ne restituisce lalunghezza.

% FASE 1: Verifica casi banaliIF (x_i o x_f collidono con ostacoli) THEN{

errore: problema impossibile!}ELSE{

PATH = lista vuota;LENGTH = 0;

}

Cerca un cammino minimo P di Dubins da x_i a x_f;IF(P e sicuro) THEN{

PATH = {x_f};LENGTH = lunghezza di P;% Fine.

}ELSE{

% FASE 2: Inizializzazione% Tutti i nodi hanno il nodo iniziale (1) come predecessore in un% cammino minimo.PRED = vettore di tutti 1 di lunghezza 2N+2;% Nessun nodo esplorato fuorche quello iniziale (1)FLAG = vettore con il primo elemento TRUE e gli altri 2N+1 FALSE;% Nessuna configurazione individuataCONFIG = matrice vuota (2N+2)x(2N+2);% Tutti i costi dei cammini tra nodi distinti sono infinitiC = matrice (2N+2)x(2N+2) nulla sulla diagonale INF fuori;% Elaborazione del nodo 1FOR n = 3:2N+2 {

C(1,n) = lunghezza del cammino minimo da x_i alla circonferenzaorientata associata al nodo n, se un cammino non esisteallora INF;

52

CONFIG(1,n) = configurazione del punto finale del cammino da x_ialla circonferenza orientata associata al nodo n;

}% Il costo del cammino minimo da 1 al generico nodo n noto sinora e% quello del cammino diretto da 1 a nL = prima colonna di C;

% FASE 3: Algoritmo di DjikstraFOR j = 1:2N+1

% Cerca tra i nodi non ancora elaborati quello verso cui il% cammino e il piu breve tra quelli generati sinoraw = Arg min {L(w)| FLAG(w)=FALSE};% w e il prossimo nodo da elaborareFLAG(w) = TRUE;% Elaborazione del nodo wIF (w=2) THEN{

Non fare nulla: non si devono cercare cammini che pertantodalla configurazione finale!

}ELSE{

% Elabora un cammino verso il punto finaleCerca i cammini P1 e P2 dal punto CONFIG(PRED(w),w) al punto

finale x_f considerando entrambe le possibili circon-ferenze associate a x_f;

IF (NOT P1 e sicuro) THEN length(P1) = INF;IF (NOT P2 e sicuro) THEN length(P1) = INF;C(w,2) = min{length(P1),length(P2)};CONFIG(w,2) = configurazione con cui viene raggiunta la

circonferenza tangente a x_f associata al cammino piubreve tra P1 e P2;

% Elabora un cammino verso tutte le circonferenze orientateFOR n = 3:2N+2{

Cerca un cammino minimo P dal punto CONFIG(PRED(w),w)alla circonferenza orientata associata al nodo n;

Testa la sicurezza di P;C(w,n) = lunghezza di P oppure INF se P non e sicuro;CONFIG(w,n) = configurazione finale di P;

}}% Aggiorna L e PRED per tutti i nodi non elaboratiFOR n = 1:2N+2{

IF(NOT FLAG(n) & L(w)+C(w,n) < L(n)) THEN{L(n) = L(w)+C(w,n);PRED(n) = w;

}}

}

53

% FASE 4: Output del cammino ottimoPATH = {x_f};NEW_POINT = 2;WHILE (NEW_POINT != 1){

PATH = {CONFIG(PRED(NEW_POINT), NEW_POINT), PATH};LENGTH = LENGTH + C(PRED(NEW_POINT), NEW_POINT);NEW_POINT = PRED(NEW_POINT);

}

% Controllo: il cammino e ammissibile?IF (LENGTH = INF) THEN{

PATH = lista vuota;}

}

L’algoritmo richiede un metodo per testare l’assenza di collisioni, cioe la si-curezza, di un cammino. Un metodo possibile e quello di calcolare analitica-mente l’espressione della porzione del piano descritta dalla regione R associa-ta al veicolo durante il suo moto e verificare che l’intersezione con gli ostacoliOi, i = 1, . . . , l, e l’insieme vuoto. Questa tecnica e detta in letteratura sweptvolume technique, ovvero del “volume spazzato” [34]. Un’alternativa piu semplicee quella di campionare il tempo con passo Ts e considerare l’intersezione dell’in-sieme finito delle regioni {R(x1(t), x2(t), θ(t)| t ∈ Z(Ts))}, associate al veicolonel suo moto, con Oi, i = 1, . . . , l. Ovviamente la frequenza di campionamentodev’essere tarata sulla base della velocita del veicolo e sulla dimensione degli osta-coli. Questo secondo metodo, seppure piu semplice, presenta due inconvenienti:il carico computazionale risulta dipendente dalla durata del percorso (percorsilunghi necessitano il test su molti campioni), e puo dar luogo ad errori, nel casoin cui il veicolo sfiori un ostacolo tra due istanti di campionamento successivi.Quest’ultimo problema e comunque compensabile sovradimensionando il veicolo,impostando cioe un valore di h leggermente superiore a quello reale. In tal modosi introduce un margine di sicurezza. Inoltre il sovradimensionamento del veicoloe necessario sempre, per consentire un margine d’errore all’algoritmo di trackingnell’inseguimento della traiettoria pianificata. Per traiettorie brevi, dunque, iltest sull’assenza di collisioni in un cammino basato sul campionamento da buoneprestazioni ed e impiegato nelle simulazioni che saranno mostrate in seguito.

Analisi dell’algoritmo e simulazione

L’algoritmo appena descritto ha complessita polinomiale. L’istruzione principale,cosı come per l’algoritmo di Dijkstra, e costituita da due cicli for annidati chescandiscono tutte le coppie di nodi del grafo. La complessita non e pero O(n2) =O((2N + 2)2) = O(N2), come per l’algoritmo di Dijkstra, poiche qui il grafonon e assegnato a priori, bensı e necessario costruirlo, testando la sicurezza dei

54

cammini generati. Indicando con m il numero di lati totale degli ostacoli presenti,il test della sicurezza di un cammino richiede O(m) passi se si utilizza la tecnicaswept volume: si tratta infatti di verificare in totale m disuguaglianze. Se invecesi utilizza la tecnica del campionamento si devono verificare m disuguaglianze perciascun campione e il numero di campioni dipende dal rapporto tra le distanze trai vertici degli ostacoli e l’intervallo spaziale che separa due campioni successivi.Se la regione con gli ostacoli e vasta o il test di sicurezza si esegue con frequenzadi campionamento elevata, la tecnica swept volume e da preferirsi e la complessitaglobale dell’algoritmo e O(mN2).

L’algoritmo presentato garantisce che il cammino generato sia regolare. In-fatti ciascuna porzione di cammino si compone di archi orientati e segmenti dilinea retta tangenti alla circonferenza orientata, quindi e regolare, e l’algoritmoricerca un cammino a partire da una generica configurazione x solo se questa eraggiunta a sua volta da un cammino regolare che comincia dal punto inizialexi. L’algoritmo qui proposto prende in considerazione gli stessi cammini generaticon il metodo proposto in [9], ma esclude, per sua stessa definizione, camminicontenenti cuspidi. In altri termini l’algoritmo garantisce di non dover compieremanovre di back-up.

Da quest’osservazione e dalla proposizione 2.1 si potrebbe erroneamente farel’illazione che i cammini generati dall’algoritmo sono garantiti essere soluzioniottime del problema enunciato nella sezione 2.2 per veicoli di Dubins circolaricon raggio h = rmin. In realta cio non e corretto. Un controesempio e riportatoin figura 2.3.

La proposizione 2.1 vale infatti per veicoli in grado di muoversi avanti e indie-tro. Come si e detto nel primo capitolo, se i veicoli possono muoversi in un unicoverso, la traiettoria ottima si compone o di segmenti interposti fra due archi dicirconferenza (manovre di tipo LSR, RSL, LSL o RSR), o di tre archi (LRL oRLR). L’algoritmo e in grado di generare cammini che richiedono manovre dellaprima categoria, ma non della seconda. Pertanto, per veicoli circolari di raggioh = rmin, se il cammino ottimo esiste e non contiene tratti di tipo LRL o RLR,allora il metodo presentato e in grado di restituirlo. Se invece non e cosı, none garantito che l’algoritmo restituisca un output, o se viene individuato un per-corso questo non e quello ottimo. Si veda, ad esempio, la situazione illustrata infigura 2.4: il metodo qui proposto non individua alcun percorso. In figura 2.3 eriportato un caso in cui l’output c’e ma non e ottimo.

Dalle considerazioni precedenti segue immediatamente che l’algoritmo none completo, cioe non e garantita l’individuazione di un percorso dalla configu-razione iniziale a quella finale, anche se questo esiste. Inoltre l’algoritmo nongarantisce una soluzione ottima. Si osservi comunque che l’incompletezza o lasub-ottimalita del metodo si manifestano qualora sia richiesto compiere manovredi inversione di tipo LRL o RLR, il che puo talvolta accadere in presenza dipassaggi molto stretti, in situazioni piuttosto rare. Punti morti sistematici comequello mostrato in figura 2.1 per l’algoritmo proposto in [9] sono stati qui rimossi.Si confronti la figura 2.5 con la 2.1. Nella maggioranza dei casi l’algoritmo e in

55

Figura 2.3. Simulazione del movimento di un e-puck attraverso un ambiente con ostacoli.La configurazione iniziale e in nero, quella finale in rosso; in verde e mostrato il camminopianificato dall’algoritmo ad alto livello che viene passato come traiettoria al veicolo; la lineablu e quella seguita dal centro di massa del veicolo. La semilarghezza h e sovradimensionatadel 30%; TGPS = 1 s . Il cammino pianificato e sub-ottimo: quello ottimo e tratteggiato innero e richiede una manovra di tipo LRL.

grado di individuare il cammino ottimo, anche attraverso ostacoli numerosi edalla geometria complicata.

Si puntualizza che se rmin < h l’algoritmo richiede di tracciare le circonferenzerelative al punto iniziale e a quello finale con raggio rmin anziche ρ = h comeper tutte le altre. Le considerazioni appena svolte sotto l’ipotesi h = rmin siestendono immediatamente al caso rmin < h. Se invece rmin > h la completezzadell’algoritmo viene ulteriormente ridotta, analogamente a quanto mostrato in[9], qualora sia necessario attraversare delle strettoie di larghezza L tale che2h < L < h + rmin. In [9] si propone un metodo euristico per risolvere ilproblema che puo applicarsi direttamente anche al metodo qui presentato. Sirimanda a tale articolo per dettagli ulteriori.

Al pari del metodo proposto in [9], l’algoritmo qui presentato puo applicarsicon prestazioni soddisfacenti anche a veicoli di forma generica, benche sia difficileargomentare sulla sua ottimalita se si rimuove l’ipotesi della forma circolare.

Inseguimento delle traiettorie pianificate

Una volta pianificata una traiettoria, si pone il problema del suo inseguimen-to. Nel quadro di ipotesi formulato, l’algoritmo di pianificazione del camminoattraverso gli ostacoli e quello di tracking sono distinti. Il primo fa uso di infor-mazioni globali sulla geometria del sistema che non sono disponibili al veicolo,su cui invece opera il controllore deputato all’inseguimento. La pianificazione del

56

−0.1 −0.05 0 0.05 0.1

−0.1

−0.05

0

0.05

0.1

Algorithm deadlock

x

y

Figura 2.4. Punto morto per l’algoritmo. La configurazione iniziale e disegnata in nero,quella finale in rosso; in blu e mostrata la traiettoria ottima, che pero non puo essere generatacon l’algoritmo presentato. L’algoritmo e in grado di trovare una traiettoria solo se e possibilecompiere un’inversione di marcia all’interno della fenditura, che quindi deve avere larghezzaL > 4rmin + 2h per garantire che cio sia sempre possibile.

Figura 2.5. Output dell’algoritmo proposto in una situazione analoga a quella riportatain figura 2.1: mentre l’algoritmo di Bicchi et al. porta ad una configurazione finale errata,l’algoritmo qui proposto e corretto ed evidentemente restituisce il cammino ottimo.

57

cammino deve avvenire pertanto a livello di una qualche unita centrale. Si ponedunque il problema della trasmissione della traiettoria al veicolo mobile: il cam-mino generato e una curva continua, pero solo una quantita finita di informazionipuo essere trasmessa. Il campionamento della traiettoria e ovviamente una sceltainefficiente poiche sarebbe necessario comunicare un numero elevato di configu-razioni. Una scelta piu efficiente potrebbe essere quella di decomporre il camminogenerato in archi e segmenti e comunicare al veicolo una sequenza di coppie datedal tipo di traiettoria (curva a destra, sinistra o tratto rettilineo) e dalla lorolunghezza. C’e pero una terza opzione, che trae giustificazione dalle precedentiosservazioni; quest’ultimo metodo e particolarmente adatto ad essere impiegatoin combinazione con l’algoritmo di pianificazione del movimento introdotto nelprimo capitolo. Passando il vettore PATH, cosı com’e generato dall’algoritmo dipianificazione appena presentato, come traiettoria di riferimento, al controlloreintrodotto nel primo capitolo, questo sara in grado di ricostruire ed inseguire ilcammino pianificato a tempo continuo. Questa proprieta discende dalla quasiottimalita dei cammini generati. Il vettore PATH e costituito dalla successionedelle configurazioni con cui il cammino ottimo raggiunge le circonferenze cen-trate nei vertici degli ostacoli. Tra due successive configurazioni il cammino noninterseca ostacoli ed e quello di minima lunghezza tra quelli di tipo LSR, RSL,LSL, RSR. Il controllore presentato nel primo capitolo e in grado di generareed inseguire tale cammino se gli viene passata come traiettoria il vettore PATH:l’unico accorgimento e quello di inibire, finche che il veicolo attraversa un campodi ostacoli, la generazione di traiettorie LRL e RLR.

In applicazioni di tracking del cammino generato attraverso campi di ostacolinon possono essere trascurati i disturbi esterni. Sara dunque necessario pas-sare all’algoritmo un valore di h superiore alla reale dimensione del veicolo, perevitare l’impatto con gli ostacoli dovuto ad errori prodotti dalle perturbazioni. Laquantita da aggiungere al valore effettivo di h cresce con l’entita delle derive cheagiscono sul veicolo e diminuisce all’aumentare della frequenza di campionamentoTGPS. Un esempio e mostrato in figura 2.6

58

0 0.1 0.2 0.3 0.4 0.5

−0.2

−0.15

−0.1

−0.05

0

0.05

0.1

0.15

0.2

0.25

x [m]

y [m

]

Simulation of an e−puck moving through obstacles

Figura 2.6. Simulazione del movimento di un e-puck attraverso un ambiente con ostacoli.La configurazione iniziale e in nero, quella finale in rosso; in verde e mostrato il camminopianificato dall’algoritmo ad alto livello che viene passato come traiettoria al veicolo; la lineablu e quella seguita dal centro di massa del veicolo. La semilarghezza h e sovradimensionatadel 40%; TGPS = 500 ms. Sul veicolo agiscono le derive d1 = 5 mm/s lungo l’asse delle ascisse,d2 = −5 mm/s lungo l’asse delle ordinate e d3 = 0.01 rad/s sull’orientazione.

59

60

Capitolo 3

Rendezvous di molteplici robotmobili

3.1 Introduzione

3.1.1 Breve panoramica sulla swarm robotics

Si e preso sinora in considerazione il problema della pianificazione del movimentodi un singolo veicolo mobile. Nel presente capitolo si vuole affrontare invece iltema del coordinamento di molteplici robot mobili. Si tratta di un campo diricerca assai vasto e in gran parte ancora da esplorare. Si tenta qui di dare unasuccinta panoramica delle motivazioni, delle problematiche e delle applicazioniaffrontate dalla letteratura dedicata. Nel seguito si focalizzera l’attenzione su unproblema particolare e ben definito: il rendezvous di veicoli mobili.

L’espressione swarm intelligence descrive un tipo di comportamento collet-tivo intelligente, o virtuoso, che emerge dalla cooperazione di piu agenti per ilraggiungimento di un obiettivo unitario e che si ispira all’osservazione, in natu-ra, del comportamento degli animali sociali. L’interesse verso sistemi artificialibasati sui fondamenti della swarm intelligence ha originato una branca dell’au-tomazione detta swarm robotics. L’applicazione dei principi della swarm intelli-gence a sistemi composti da una molteplicita di robot comporta essenzialmentetre vantaggi:

• la scalabilita dell’architettura di controllo, da poche fino a migliaia di unita;si tratta infatti di un’architettura decentralizzata in cui non vi e alcunagente con capacita computazionali o di comunicazione superiori, che eleader prestabilito del gruppo, bensı tutti gli agenti hanno le stesse capacitae comunicano solo localmente;

• la capacita di auto-organizzazione (self-organization), che consiste nellapossibilita di aggiungere, rimuovere od assegnare altri compiti le unita senzaalcun intervento esterno esplicito di riorganizzazione;

61

• la robustezza del sistema, dovuta non solo alla ridondanza delle unita ope-ranti parallelamente (in caso di guasto di un agente il compito puo co-munque essere ultimato dai rimanenti), ma anche all’assenza di punti criticidi rottura di modo comune e al fatto che le singole unita risultano essereparticolarmente semplici, per cui e relativamente facile per il progettistagarantirne la robustezza elettromeccanica;

Nei sistemi progettati sulla base del paradigma della swarm intelligence ilcomportamento complessivo non e codificato esplicitamente in alcun punto, mae una conseguenza emergente dall’interazione tra singoli agenti o tra ciascunagente e l’ambiente circostante. Le potenzialita del sistema nel suo complessotrascendono quelle del singolo agente, che da solo non sarebbe in grado di svolgereil compito desiderato. I vantaggi offerti dalla swarm robotics, di cui si e appenafatto cenno, si ottengono dunque al prezzo di una piu complessa validazione delcomportamento complessivo del sistema. Non e infatti sufficiente asserire che ungruppo di agenti esibisce il comportamento desiderato, ma si deve anche garan-tire che, in nessun caso, emerga un comportamento indesiderato. La proceduraper stabilire tale proprieta richiede anzitutto l’individuazione di tutti i compor-tamenti indesiderabili, quindi un’approfondita analisi statistica di rischio [54],[55].

Il paradigma della swarm robotics risulta estremamente versatile ed apertoa molteplici applicazioni in un prossimo futuro. Senza alcuna pretesa di dareuna classificazione completa ed esaustiva, bensı per fornire una rapida e succintapanoramica delle problematiche, si possono individuare nella letteratura tecnicaalmeno cinque filoni [43].

Mappatura ed esplorazione di ambienti : l’obiettivo di questa tipologia diapplicazioni e l’attraversamento o la copertura della piu vasta porzione pos-sibile di ambiente circostante da parte della squadra di robot. Sovente glialgoritmi proposti per queste applicazioni sono messi a punto dapprima sulsingolo robot e poi implementati su una schiera di robot identici, e non sifondano sul paradigma del controllo distribuito. Per citare alcuni esempidi possibili applicazioni: Correll et al. [16] [17] hanno studiato il problemadell’esplorazione di ambienti con una struttura geometrica regolare, qualile pale delle turbine dei jet, con robot di scala ridotta; Howard et al. [28]hanno sviluppato un algoritmo per la disposizione incrementale di robotdotati di telecamera la fine di esplorare e monitorare la piu vasta porzionepossibile di un ambiente sconosciuto mantenendo ciascun agente in costantecontatto visivo con gli altri (problema della galleria d’arte); in [2] si proponeun algoritmo per il coordinamento di robot “pulitori” in grado di “pulire”la zona in cui si trovano, con lo scopo di contenere un’area “sporca” chetende ad espandersi in maniera dinamica, simulando una contaminazioneo un incendio; in [35] e invece presentato un algoritmo distribuito per l’oc-cupazione della massima area di un ambiente con ostacoli da parte di unasquadra di robot che sono dotati di sensori con un range limitato e che

62

necessitano periodicamente di ricaricare le batterie ad una stazione fissa;in [15] si propongono degli algoritmi per l’esplorazione di ambienti da partedi squadre di robot finalizzati ad operazioni di sminamento.

Localizzazione : questa branca della swarm robotics e assimilabile a quella chesi occupa dell’esplorazione di ambienti, ma richiede un esplicito scambio diinformazione locale tra gli agenti al fine di localizzare un dato obiettivo.L’obiettivo puo essere esterno rispetto alla squadra di robot, ad esempio unasorgente luminosa [42] o odorosa [26], oppure cio che si vuole localizzare e laposizione degli stessi robot, che devono quindi precedentemente accordarsisu un sistema di riferimento comune [14].

Trasporto e manipolazione di oggetti : lo scopo comune a questo filone distudi e il trasporto di oggetti da parte di squadre di robot verso un puntofinale desiderato. Gli oggetti da spostare possono essere troppo grandi peressere mossi da un singolo robot e cio richiede la cooperazione di piu agenti.Un problema classico e quello dello spingere oggetti di grandi dimensioni[25]: i robot che spingono l’oggetto (pusher) devono necessariamente coop-erare, ma hanno la visuale ostruita dallo stesso oggetto da muovere, per cuic’e bisogno dell’intervento di un robot esterno (watcher) che possa rilevarela posizione dell’obiettivo rispetto a quella corrente dell’oggetto e che guidii pusher verso la meta.

Riconfigurazione e auto-assemblaggio : questo ramo della swarm roboticsha come oggetto dei robot che hanno la possibilita di cambiare configura-zione e, in particolare, di auto-assemblarsi in differenti maniere. Lo scopo equello di produrre una configurazione piu adatta per il raggiungimento del-l’obiettivo. In [46] e in [52] si considerano, ad esempio, robot mobili dotatidi bracci meccanici in grado di afferrarsi reciprocamente e di sollevarsi l’unl’altro per superare dei dislivelli, oppure di formare una catena rigida peroltrepassare precipizi, formando una sorta di ponte.

Coordinamento del movimento : questa categoria di problematiche e forsequella meno recente e piu intensamente studiata, essendo il movimento ne-cessario per lo svolgimento di tutti gli obiettivi piu complessi delle categorieprecedenti. Essenzialmente la problematica comune agli studi in questosettore e quella di muovere una squadra di robot dalle loro posizioni in-iziali verso punti desiderati, mantenendo il gruppo compatto, con il vincoloaggiuntivo di evitare collisioni mutue o con ostacoli fissi o mobili eventual-mente presenti nell’ambiente circostante [40]. Problemi di coordinamentosono anche l’intercettazione di obiettivi mobili [8], la costruzione di unaformazione geometrica e il suo mantenimento durante il moto [24]. In par-ticolare, se la formazione che si vuole ottenere e data semplicemente da unsingolo punto si parla di rendezvous : il problema del rendezvous consistenel far convergere tutti i robot di una squadra in un unico punto, sfrut-tando l’informazione locale che ciascun agente e in grado di ottenere dai

63

propri sensori di bordo ed eventualmente dalla comunicazione con i vicini.Anche per quanto riguarda i problemi del coordinamento del moto di piurobot, si possono individuare in letteratura due categorie di approcci: quel-lo centralizzato e quello decentralizzato. Il primo prevede l’esistenza diun’unita centrale in grado di rilevare lo stato dell’intero sistema, di comuni-care con tutti i robot e di coordinarli [10]. Lo svantaggio di quest’approcciorisiede nel notevole carico computazionale che grava sull’unita centrale, so-lo parzialmente compensato dalla possibilita di garantire l’ottimalita. Perquesta ragione grande impulso ha avuto lo studio di tecniche di controllodecentralizzato e distribuito in cui ciascun agente e in grado di pianificareautonomamente la propria traiettoria, almeno parzialmente, riducendo ilcarico computazionale per l’unita centrale o prescindendo completamentedalla sua esistenza.

Si vede dunque come le problematiche legate alla swarm robotics siano moltepli-ci e variegate. Tutti i filoni di ricerca menzionati sono tuttora aperti a nuovesoluzioni. Le applicazioni sono ancora limitate quasi esclusivamente ad ambien-ti di laboratorio e non hanno conosciuto uno sviluppo su scala industriale. Lascalabilita, la robustezza e la capacita di auto-organizzazione dei sistemi proget-tati sulla base del paradigma della swarm robotics, pero, rendono questo ramodell’automazione accattivante e promettente per un prossimo futuro.

3.1.2 Un problema particolare: il rendezvous

Non essendo possibile una trattazione estesa di tutte le tematiche, il seguito delcapitolo si focalizza esclusivamente sul problema del rendezvous. La motivazionedi questa scelta sta nel fatto che la necessita di raggruppare tutti i robot in unapiccola area puo nascere in molteplici applicazioni, durante una qualsiasi missionecomplessa che richieda, ad esempio, che ciascun robot si trovi all’interno delcampo di visibilita degli altri. I problemi di rendezvous sono importanti, inoltre,per la loro stretta relazione con problemi di consenso.

I primi algoritmi di rendezvous proposti in letteratura si applicano a robotmobili onnidirezionali. Si ricordano, in particolare [4] e [3]. Tali algoritmi siapplicano a robot sincroni [4] e asincroni [3] e garantiscono la convergenza adun unico punto del gruppo di robot se il grafo di visibilita ha un nodo global-mente raggiungibile; si avra modo di notare in seguito che nessun algoritmo puogarantire di far convergere i veicoli in un unico punto se questa condizione none soddisfatta. Solo piu recentemente e stato provato che e possibile condurreal rendezvous, sotto le stesse ipotesi, anche veicoli anolonomi [32] e sono statiproposti algoritmi in questo senso [33] [18]. Queste tecniche si applicano pero arobot anolomi bidirezionali, che cioe possono muoversi avanti e indietro, e conraggio di curvatura non limitato. L’autore di questa tesi non e a conoscenza dialgoritmi di rendezvous per veicoli di Dubins (monodirezionali e con raggio di cur-vatura limitato) sviluppati a tutt’oggi. La difficolta di far convergere in un unico

64

punto una squadra di macchine di Dubins, utilizzando solamente informazionelocale, risiede nella necessita di avvicinare i robot mantenendo al tempo stessoi vicini mutuamente all’interno del range dei sensori. I veicoli di Dubins nonsono controllabili in tempo breve, quindi l’avvicinamento ad un punto desideratopotrebbe causare inevitabilmente la perdita di contatto con uno dei vicini, tantopiu se il raggio minimo di curvatura e comparabile col range dei sensori.

Dapprima si presentera un algoritmo per la convergenza di un gruppo di robotmobili onnidirezionali verso un unico punto gia presente in letteratura [3]; nelseguito si mostrera come l’algoritmo proposto sia adattabile con qualche modificaa veicoli di Dubins. Il metodo proposto in [3] e basato su un approccio geometricoe questo lo rende piu adatto di altre tecniche, come ad esempio quelle di gradiente[33] [18], ad essere impiegato in combinazione con il controllore di basso livello peril movimento del singolo robot proposto nel primo capitolo. La prima versionepresentata dell’algoritmo soffre di una convergenza piuttosto lenta. Si proporra,quindi, una modifica per rendere l’avvicinamento al rendezvous piu veloce.

3.2 Un algoritmo per il rendezvous di robot

onnidirezionali

Questa sezione e dedicata alla presentazione di un algoritmo distribuito per laconvergenza verso un unico punto di veicoli onnidirezionali, cioe in grado diruotare su se stessi e traslare sul piano in qualunque direzione, autonomi e conraggio di visibilita limitato . La tecnica qui presentata e dovuta ad Ando et al.[3] [4]. L’algoritmo sara presentato in maniera estesa, per comprendere qualiaspetti sono adattabili anche al caso di veicoli di Dubins e quali modifiche sianoinvece necessarie per l’applicazione di questo algoritmo a veicoli anolonomi conraggio di curvatura limitato.

3.2.1 Considerazioni preliminari

L’approccio perseguito e quello del controllo distribuito: ciascun robot decideindividualmente il proprio piano di movimento unicamente sulla base dell’infor-mazione disponibile localmente, utilizzando un algoritmo condiviso da tutti gliagenti. Non si utilizza alcun controllore globale ne alcuno strumento di navi-gazione come sistemi di coordinate globali, funzioni potenziale, bussole o land-mark. I robot si assumono asincroni ed omogenei, nel senso che non esistonoleader. Sono inoltre anonimi, ovvero non hanno alcun identificativo che consentadi distinguerli. L’algoritmo non richiede alcun sistema di comunicazione e la solainformazione globale che i robot condividono e il fatto che tutti obbediscono allostesso algoritmo. Si assume che i sensori a bordo dei robot siano in grado dirilevare la posizione relativa degli altri agenti che distano meno di un dato raggiodi visibilita limitato V > 0.

65

Ovviamente, sotto l’ipotesi di visibilita limitata, non esiste alcun algoritmoche garantisca di poter sempre radunare i robot in una piccola area a partire dauna qualsiasi configurazione iniziale. Se, ad esempio, un robot inizialmente non ein grado di rilevare alcun altro agente, e possibile che non rilevera mai altri robot,non raggiungendo dunque il punto di rendezvous. Si puo dunque formulare l’obi-ettivo dell’algoritmo di rendezvous in maniera seguente: data una distribuzioneiniziale dei robot, si rappresenta la mutua visibilita dei robot tramite un grafonon orientato (in inglese undirected) i cui i nodi rappresentano i robot e i lati cor-rispondono a coppie di robot mutuamente visibili; un algoritmo di convergenzaad un punto ha lo scopo di muovere tutti i robot associati a ciascuna componenteconnessa del grafo verso un singolo punto.

L’algoritmo che si propone e senza memoria, nel senso che la posizione suc-cessiva di un robot e determinata unicamente dalla posizione dei robot che sonocorrentemente visibili, indipendentemente dalla storia pregressa del sistema. Cione facilita l’implementazione, in particolare su veicoli dalle limitate capacita com-putazionali. Fatto ancora piu importante e che un algoritmo senza memoria eauto-stabilizzante, intendendo con cio affermare che, se l’algoritmo funziona cor-rettamente a partire da qualsiasi configurazione iniziale quando non si verificaalcun errore, allora funzionera correttamente anche in presenza di un numero fini-to di errori transitori, poiche lo stato immediatamente successivo all’occorrenzadi un errore puo essere considerato come una nuova distribuzione iniziale.

Sia R = {r1, . . . , rn} l’insieme dei robot. Per semplicita si modellera ciascunrobot come un cerchio di diametro h sul piano euclideo. Si denota con ri(t) laposizione del centro di ri all’istante t e si assume che d(ri(t), rj(t)) ≥ h ∀i 6= j,dove d(p, q) indica la distanza euclidea di p e q. La distribuzione dei robotall’istante t e P (t) = {r1(t), . . . , rn(t)} e P (0) e la distribuzione iniziale. Siassume che ciascun robot non ostruisca la visuale degli altri, per cui l’insiemeSi(t) degli agenti rilevabili da ri coincide con quello dei robot che distano da ri(t)non piu di V : formalmente Si(t) = {rj| d(ri(t), rj(t)) ≤ V }. I robot in Si(t) sonochiamati vicini di ri all’istante t; si noti che la precedente definizione implica checiascun robot e vicino di se stesso.

Ciascun robot ri esegue ciclicamente una fase, che consiste nelle seguenti treoperazioni:

1. osserva la posizione relativa rj(t) di ciascun robot rj ∈ Si(t) (t e l’istantecorrente; )

2. calcola la propria nuova posizione x utilizzando l’algoritmo proposto sullabase dell’osservazione appena compiuta

3. muove verso x (ri non puo cambiare la propria destinazione x durante ilmoto verso x).

Poiche un robot reale e in grado di monitorare l’ambiente circostante e quin-di correggere il proprio movimento con tempi di campionamento molto piccoli,

66

si assume che la distanza d(ri(t), x) dalla posizione corrente alla destinazionex calcolata dall’algoritmo non possa eccedere una costante piccola σ > 0. Irobot si ipotizzano asincroni, nel senso che potrebbero cominciare una fase nonsimultaneamente.

Dato P (t), si definisce il grafo di prossimita al tempo t, G(t) = (R,E(t)),come un grafo non orientato, dove (ri, rj) ∈ E(t) se e solo se i 6= j e d(ri(t), rj(t)) ≤V . Dato che si ipotizza che i robot non ostruiscano la visuale ai sensori di al-tri agenti, il grafo di prossimita e quello di visibilita coincidono e i due terminisaranno nel seguito impiegati come sinonimi. L’obiettivo che ci si prefigge e l’indi-viduazione di un algoritmo che muova i robot in ciascuna componente connessa1

di G(0) entro un intorno arbitrariamente piccolo di un unico punto.

3.2.2 Algoritmo di convergenza a un punto

Si presenta qui un algoritmo per la convergenza a un punto. Il metodo presentatopreserva le seguenti due proprieta ad ogni istante t.

• I robot nella stessa componente connessa del grafo di prossimita G(t) si“avvicinano”

• I robot che sono mutuamente visibili all’istante t rimangono a una distanzainferiore a V , il che equivale ad affermare che nessuna componente connessadi G(t) si divide in due o piu componenti.

Si denoti con Ci(t) la piu piccola circonferenza contenente l’insieme {rj(t)| rj ∈Si(t)} delle posizioni dei robot visibili da ri all’istante t. Il centro di Ci(t) edenotato con ci(t). Chiaramente, per ogni insieme S di punti, il piu piccolocerchio contenente S e unico ed effettivamente computabile. Si tratta di unproblema classico di ricerca operativa noto con il nome di minimum spanningcircle problem (o minimum enclosing circle problem o minimax location problem),con un secolo e mezzo di storia alle spalle (fu formulato per la prima volta daSylvester nel 1857). Esistono nella letteratura tecnica svariati algoritmi per lasua risoluzione, altamente efficienti. Per lungo tempo si e creduto si trattasse diproblema di complessita O(n log n), dove n e il numero di punti, ma studi piurecenti hanno individuato algoritmi di complessita O(n) per la sua risoluzione.Si rimanda a [41] e a [56] per ulteriori approfondimenti. Basta qui ricordare chevale la proprieta espressa dal seguente

Lemma 3.1. Sia C il cerchio di raggio minimo che inscrive l’insieme S di punti.Allora vale una delle proposizioni seguenti:

1Dato un grafo non orientato G = (V, E) il vertice v si dice connesso al vertice w se(v, w) ∈ E; si noti che essendo il grafo non orientato la proprieta e simmetrica. Un grafo sidice connesso se i vertici v e w sono connessi, per ogni v, w ∈ V . La relazione di connessioneinduce una partizione dei vertici del grafo, formata dalle sue componenti connesse, cioe daisottoinsiemi massimali che inducono sottografi connessi.

67

a) ci sono due punti p, q in S sulla circonferenza di C, tali che il segmento pqe un diametro, oppure

b) ci sono tre punti p, q, r in S sulla circonferenza di C, tali che il centro c diC e interno al triangolo (non ottusangolo) ∆pqr.

Dal lemma segue immediatamente che il centro c di C appartiene al guscioconvesso (in inglese, convex hull) contenente S.

Figura 3.1. Il robot ri si muove verso ci(t). La circonferenza tratteggiata circoscrive i puntiin Si(t), mentre la circonferenza a tratto continuo raffigura il cerchio minimo contenete i puntiin Si(t).

Si supponga che il robot ri si attivi e cominci una fase all’istante t. L’algo-ritmo prevede di muovere ri verso ci(t) (figura 3.1), ma solamente per una certadistanza, che sara chiamata move, per garantire il mantenimento della mutuavisibilita. Precisamente l’algoritmo calcola una nuova posizione x per il robotri, utilizzando Si(t) come input, nella maniera seguente. Se ri non rileva nessunrobot all’infuori di se stesso, allora ri non si muove all’istante t; formalmente, seSi(t) = {ri} allora x = ri(t). Altrimenti, l’algoritmo sceglie come x il punto sulsegmento ri(t)ci(t) piu vicino a ci(t) che soddisfa le seguenti condizioni:

1. d(ri(t), x) ≤ σ

2. Per ogni robot rj ∈ Si(t), x giace sul cerchio Dj, il cui centro mj e il puntomedio tra ri(t) e rj(t) e il cui raggio e V/2 (figura 3.2, sinistra).

La prima condizione discende dalle restrizioni sulla massima distanza che unrobot puo compiere in una singola fase. Si rammenta che durante l’esecuzione diuna fase il robot non ricalcola la propria traiettoria, quindi non sfrutta il sensoredi bordo per modificare il proprio movimento. Tanto piu σ e piccola tanto meglio

68

Figura 3.2. A sinistra: i robot ri e rj rimangono entro una distanza mutua di V se restanoentrambi entro Dj ; a destra: massima distanza lj che ri puo percorrere verso ci(t) senza lasciareDj .

l’algoritmo, che e ad eventi discreti, approssima una tecnica di controllo a tempocontinuo, che corregge le traiettorie in maniera istantanea. La seconda condizioneassicura invece che se ri e rj eseguono una fase simultaneamente all’istante t, poirimangono a una distanza inferiore a V l’uno dall’altro. Come mostrato in figura3.2, a destra, la posizione x che soddisfa queste condizioni puo essere calcolatasemplicemente. La massima distanza lj che puo essere percorsa dal robot ri versoci(t) senza lasciare Dj e data da

lj =dj

2cos θj +

√(V

2

)2

−(

dj

2sin θj

)2

dove dj = d(ri(t), rj(t)) e la distanza euclidea tra ri e rj e θj = ∠ci(t)ri(t)rj(t)e la direzione del moto di ri rispetto alla retta passante per ri(t) e rj(t), con0 ≤ θj ≤ π. Si calcola cosı lj per ogni rj ∈ Si(t)− {ri} e si pone

limit = minrj∈Si(t)−{ri}

{lj}.

Inoltre siagoal = d(ri(t), ci(t))

la distanza fra ri(t) e ci(t). Utilizzando questi valori e σ si calcola

move = min{goal, limit, σ}.Pertanto x e il punto del segmento ri(t)ci(t) che dista move da ri(t).

3.2.3 Analisi dell’algoritmo

Ci si sofferma qui su un’analisi dell’algoritmo, che ripercorre quella condotta daAndo et al. in [3]. Lo scopo e quello di individuare quali proprieta dell’algoritmo

69

si estendano direttamente a robot dalla cinematica piu complicata, quali i veicolidi Dubins, e quali siano invece le modifiche da apportare all’algoritmo soprapresentato.

In [3] l’analisi e condotta su due livelli, uno teorico, l’altro simulativo, uti-lizzando due diversi modelli di robot. L’analisi teorica si basa su un modelloastratto di robot, pensato come un punto, che non ostacola i sensori degli altriagenti, che e in grado di compiere movimenti istantanei e che e dotato di sensoriideali non affetti da errori. Inoltre il problema delle collisioni e trascurato. Sottoqueste condizioni e possibile dimostrare formalmente che tutti i robot di ciascunacomponente connessa entrano in un intorno arbitrariamente piccolo di un puntoin un numero finito di passi e ivi permangono.

L’obiettivo dell’analisi che impiega la simulazione al calcolatore e quello diprevedere le prestazioni dell’algoritmo quando e implementato su robot reali, percui non valgono le assunzioni dell’analisi teorica. Su quest’analisi empirica nonci si soffermera in questa tesi, poiche da essa non si possono ricavare facilmentedegli spunti per modificare l’algoritmo nell’ottica della sua applicazione a ve-icoli di Dubins. Basta qui osservare che l’algoritmo appena presentato risultapiu robusto di quanto sia dimostrato formalmente in [3]. Gli autori osservanosperimentalmente che l’algoritmo consente di raggiungere il rendezvous anchecon robot realistici, di dimensioni fisiche non nulle, che non compiono movimentiistantanei, che ostacolano la visuale degli altri robot, che devono compiere ma-novre per evitare di scontrarsi, che hanno sensori affetti da rumore e da disturbisul controllo dell’orientazione e della distanza percorsa. Si tratta dunque di unalgoritmo effettivamente adatto per applicazioni reali.

Cenni dell’analisi teorica

Si riassumono qui i passi fondamentali della dimostrazione di correttezza del-l’algoritmo proposto da Ando et al. in [3]. Per maggiori dettagli e per unadimostrazione completa si rimanda alla bibliografia. Si vogliono cogliere solo leidee fondamentali, per capire le differenze rispetto al caso in cui i veicoli nonsono onnidirezionali, bensı sono anolonomi e hanno raggio di curvatura limitato.

L’algoritmo sopra presentato risulta essere corretto per robot soddisfacenti leseguenti ipotesi.

I1: Un robot e onnidirezionale e puo essere rappresentato come un punto.

I2: I robot non ostruiscono la visuale di altri robot: Si(t) = {rj| d(ri(t), rj(t)) ≤V } ∀t.

I3: Si ignorano le collisioni tra robot

I4: Ogni robot puo eseguire un’infinita di fasi.

I5: La durata di una fase e trascurabile.

I6: I sensori a bordo del robot sono accurati.

70

L’ipotesi I4 garantisce che ciascun robot porti a compimento tutte le fasi chesono richieste, quindi non si blocchi mai, come potrebbe accadere nella realta, acausa di guasti o dell’esaurimento delle batterie. Non si fanno ulteriori ipotesi sulmeccanismo con cui i robot si attivano, ovvero sulla scelta della successione degliistanti di attivazione di ciascun robot. L’assunzione I5 implica che una fase sipuo considerare come un evento istantaneo, pertanto, quando un robot cominciauna fase, osserva gli altri agenti solo in stato stazionario. Quindi, senza perditadi generalita, si puo pensare il sistema come se fosse a tempo discreto.

Si vuole dimostrare che, sotto le ipotesi appena formulate, l’algoritmo conducei robot in ogni componente connessa di G(0) a convergere in un unico punto.

Il seguente lemma afferma formalmente che se due robot si rilevano mutua-mente, rimangono mutuamente visibili da quell’istante in poi. Si rammenta cheE(t) e l’insieme dei lati del grafo di prossimita G(t).

Lemma 3.2. Per ogni coppia di robot ri, rj e per ogni istante t ≥ 0, (ri, rj) ∈E(t) implica (ri, rj) ∈ E(t + 1)

Dimostrazione: Se (ri, rj) ∈ E(t), allora per I2 ri ∈ Sj(t) e rj ∈ Si(t). Allora,per definizione di limit, ri(t + 1) e rj(t + 1) stanno nel cerchio di centro mj

(punto medio di ri(t) e rj(t)) e raggio V/2, indipendentemente dal fatto che ri erj siano attivi o meno all’istante t. Allora d(ri(t + 1), rj(t + 1)) ≤ V e dunque(ri, rj) ∈ E(t + 1). ¤Quindi, per ogni istante t ≥ 0, i robot che appartengono ad una stessa com-ponente connessa di G(t), appartengono alla stessa componente connessa anchein G(t + 1). Poiche c’e un numero finito di robot, il numero di volte in cui duediverse componenti connesse del grafo si fondono e finito. Percio esiste un istantet∗ dopo il quale non si ha piu la fusione di componenti connesse del grafo. Si fissiuna componente connessa (S, A) di G(t∗), e per ogni t ≥ t∗, sia CH(t) il guscioconvesso delle posizioni dei robot in S all’istante t, ovvero il guscio convesso del-l’insieme di punti {rj(t)| rj ∈ S}. Il seguente lemma afferma che CH(t) non puocrescere.

Lemma 3.3. Per ogni t ≥ t∗, CH(t + 1) ⊆ CH(t).

Dimostrazione: Si fissi un robot ri ∈ S e si supponga che all’istante t siaattivo, ovvero stia eseguendo una fase. Allora ri sta muovendosi verso ci(t),centro della circonferenza Ci(t). Si rammenta che Ci(t) e definita come la piupiccola circonferenza contenente l’insieme di punti {rj(t)| rj ∈ Si(t)}. Dal lemma3.1 segue che ci(t) appartiene al guscio convesso CHi(t) contenente le posizionidei robot in Si(t) all’istante t. Poiche la traiettoria seguita da ri e un tratto delsegmento che congiunge ri(t) con ci(t) e poiche, come si e detto, gli estremi delsegmento stanno entrambi nello stesso guscio convesso CHi(t), allora anche lasuccessiva posizione del robot vi apparterra: ri(t + 1) ∈ CHi(t). CertamenteCHi(t) ⊆ CH(t), dato che Si(t) ⊆ S. Allora ri(t + 1) ∈ CH(t).

Se il robot ri non e attivo all’istante t, allora ri(t + 1) = ri(t) e quindi e veroche CH(t + 1) ⊆ CH(t). ¤

71

Si osservi come, nella dimostrazione, sia fondamentale il fatto che le traiettoriesono segmenti, fatto che permette di dimostrare che se il punto iniziale e quellofinale sono in uno stesso guscio convesso, l’intera traiettoria vi e contenuta. Eevidente che una tale argomentazione non puo applicarsi a veicoli di Dubins,come si avra modo di osservare nella prossima sezione.

Il lemma garantisce che la successione delle (CH(t)| t = t∗, t∗ + 1, . . .) sia lim-itata e monotona, quindi convergente ad un certo CH. CH e certamente unpoligono convesso, includendo tra i poligoni convessi i casi degeneri del segmentoe del punto. Resta da provare che CH e effettivamente un singolo punto. Ladimostrazione di questo fatto e piuttosto laboriosa e non sara svolta qui, ancheperche non ha grande rilevanza per le considerazioni seguenti. Si rimanda a [3]per approfondimenti.

E importante invece sottolineare che dai lemmi 3.2 e 3.3 e dal fatto che CH(t)converge a un punto si deduce che l’algoritmo risolve correttamente il problemadella convergenza a un punto sotto le ipotesi I1 - I6.

3.3 Un algoritmo per il rendezvous di veicoli di

Dubins

3.3.1 Considerazioni preliminari sulle traiettorie

Si osservi anzitutto che, nel problema del rendezvous, cosı come e stato formulato,non ha importanza l’orientazione finale dei veicoli, ne nell’algoritmo presentatoessa ha alcun rilievo per nessun obiettivo intermedio che il veicolo deve raggiun-gere. Modellando i robot come punti sul piano euclideo, si e implicitamenteassunto che l’orientazione non abbia alcun effetto sul range dei sensori di bordo,che sono cioe isotropi. Mantenendo tale ipotesi, si trascurera anche nel caso deiveicoli di Dubins l’orientazione con la quale ciascun robot raggiunge il rendezvous.In altri termini i cammini si considerano congiungere un punto in R2 × S1 conuno in R2. Quest’assunzione consente di semplificare la famiglia parametrica dicurve che un veicolo puo seguire: anziche sei tipologie di traiettorie ottime (LSL,RSR, LSR, RSL, RLR, LRL e loro sottostringhe) se ne hanno solamente quattro,ovvero LS, RS, LR e RL [53]. La partizione del piano indotta dalla famiglia dicammini sufficiente per l’ottimalita, che dipende dall’orientazione finale, risultaqui fissata. In figura 3.3 se ne da una rappresentazione: per ciascun punto delpiano e indicata la tipologia del cammino che lo congiunge con il punto iniziale(0, 0, 0) ∈ R2 × S1.

Ogni punto che non giace sul semiasse negativo delle ascisse e raggiunto dauno e un solo cammino ottimo di Dubins che puo essere costruito come segue.

Regione LS I punti in questa regione sono raggiunti con cammini compostida un arco di raggio minimo, percorso in senso antiorario per un angolo

72

Figura 3.3. Partizione del piano indotta dalla famiglia di cammini sufficiente per l’ottimalita.Le circonferenze raffigurate sono quelle di raggio di curvatura minimo.

α ∈ [0, 2π), seguito da un segmento di retta di lunghezza β ≥ 0 (figura 3.4,sinistra).

Regione RS Simmetrica alla precedente.

Regione RL I cammini che conducono a punti nella regione RL sono compostida un arco di circonferenza di raggio minimo, percorso in senso orario perun angolo α ∈ [0, π/3), seguito da un secondo arco di circonferenza di raggiominimo, percorso in senso antiorario per un angolo β ∈ (π, 2π) (figura 3.4,destra).

Regione LR Simmetrica alla precedente.

Il calcolo esplicito dei parametri α e β puo essere condotto ripetendo calcoli deltutto analoghi a quelli svolti nel primo capitolo per la risoluzione del problemadi cinematica inversa.

73

Figura 3.4. A sinistra: cammino minimo verso un punto della regione LS; a destra: camminominimo verso un punto della regione RL.

3.3.2 Rivisitazione dell’algoritmo proposto da Ando et al.

Presentazione dell’algoritmo rivisitato

Alla luce delle precedenti considerazioni, si potrebbe pensare di adattare diretta-mente l’algoritmo proposto da Ando et al. e riassunto nella sezione precedente,sostituendo alle traiettorie rettilinee dei cammini ottimi di Dubins da una confi-gurazione in R2 × S1 ad un punto in R2. E abbastanza intuitivo, e si dimostreranel seguito, che quest’operazione non fornisce un algoritmo per il rendezvous diveicoli di Dubins. Mentre l’algoritmo di Ando et al. per robot onnidirezionaligarantisce che, ad ogni passo, i robot in una stessa componente connessa di G(t)si “avvicinano” e che le componenti connesse del grafo non si disconnettono mai,il vincolo sul minimo raggio di curvatura rende difficile conservare contempo-raneamente entrambe le proprieta. Benche l’algoritmo rivisitato, da solo, nonconduca al rendezvous, si vedra che esso e parte di un metodo piu complesso cheraggiunge tale obiettivo. E pertanto opportuno definire in maniera chiara cio chesi intende per algoritmo rivisitato.

Sia, come in precedenza, R = {r1, . . . , rn} l’insieme dei robot. Si modelleraciascun robot come un punto sul piano euclideo dotato, inoltre, di una propriaorientazione. La posizione ri(t) del robot ri all’istante t non e dunque piu suf-ficiente a descriverne la configurazione, bensı e necessario considerare la coppia(ri(t), θi(t)), dove θi(t) e l’orientazione di ri al tempo t, calcolata rispetto ad unsistema di riferimento globale. I sensori di bordo sono in grado di calcolare laposizione relativa dei robot entro un raggio di visibilita V , ma non ne rilevano

74

l’orientazione.Si denoti con Ci(t) la circonferenza di raggio minimo contenete l’insieme

{rj(t)|rj ∈ Si(t)} delle posizioni dei robot che all’istante t distano da ri meno diV . Il centro di Ci(t) e denotato con ci(t). Si supponga che il robot ri si attiviall’istante t. L’algoritmo rivisitato prevede di muovere ri verso ci(t) seguendoun cammino ottimo di Dubins che congiunga (ri(t), θi(t)) con ci(t). Non haimportanza l’orientazione di arrivo in ci(t). Il cammino non viene completatointeramente in un’unica fase, ma viene compiuto, in generale, solo parzialmenteper una distanza, intesa nel senso della pseudo-metrica di Dubins, move. Comeper l’algoritmo originale, move e il minore tra tre parametri: σ, goal e limit.Essi sono definiti in maniera analoga a quelli dell’algoritmo originale, avendocura di intendere le distanze nel senso della pseudo-metrica di Dubins: σ e lamassima distanza percorribile in una singola fase, goal la lunghezza del camminocongiungente (ri(t), θi(t)) con ci(t), e limit e ancora definito come

limit = minrj∈Si(t)−{ri}

{lj},

dove lj e la lunghezza della porzione del cammino pianificato contenuta nel cer-chio di raggio V/2 e centrato nel punto medio mj di ri(t) e rj(t). Per il restol’algoritmo rivisitato e identico a quello originale.

L’algoritmo rivisitato non conduce al rendezvous

E immediato mostrare che, per definizione di limit, il lemma 3.2 rimane vali-do anche per l’algoritmo rivisitato. Pertanto e garantito il mantenimento dellaconnettivita del grafo G(t): se all’istante t due robot distano meno di V , simanterranno entro V per tutti gli istanti successivi a t.

Cio che, invece, non e valido per l’algoritmo rivisitato e il lemma 3.3. For-malmente, cio e dovuto al fatto che i punti di una traiettoria di Dubins nonsi possono esprimere come combinazione convessa degli estremi, fatto impiega-to nella prova del lemma 3.3 per dimostrare la convergenza della successione(CH(t) : t = t0, t0 + 1, . . .). La difficolta nasce dalla non controllabilita in tempobreve dei veicoli di Dubins: e possibile guidare un veicolo di Dubins verso unqualsiasi punto, quindi anche verso il generico x, determinato dall’algoritmo pro-posto, che si trova in un intorno della posizione corrente di raggio “piccolo” σ,ma non si puo garantire che, per farlo, non sia costretto a compiere una “lunga”manovra che lo porti temporaneamente ad allontanarsi dall’obiettivo e dunquedai robot con cui e in contatto. Durante tale manovra, dunque il guscio convessoCH(t + 1) puo risultare piu grande di CH(t).

Cio fa nascere situazioni patologiche, come quella rappresentata in figura3.5. Si tratta di un caso limite, che compendia le problematiche che si possonoincontrare nell’applicazione dell’algoritmo appena presentato, valido per robotonnidirezionali, a robot che si muovano invece come veicoli di Dubins.

In figura 3.5 e rappresentato un gruppo di due soli robot r1 e r2, posti a unadistanza V , pari al raggio di visibilita. All’istante t il robot r1 si attiva e, secondo

75

Figura 3.5. Esempio in cui l’algoritmo di Ando et al. rivisitato non si applica con successo aveicoli di Dubins.

l’algoritmo visto in precedenza, calcola il centro della circonferenza contenentese stesso e r2. Questo coincide, ovviamente, con il punto medio m2 del segmentor1(t)r2(t). Il robot r1 e pero un veicolo di Dubins e, non potendo ruotare suse stesso, deve compiere la traiettoria disegnata in rosso per raggiungere c1(t).Si vede pero che limit vale zero per entrambi i robot dell’esempio in figura 3.5,pertanto nessuno dei due puo muoversi e il rendezvous non viene raggiunto.

Si noti che la situazione rappresentata in figura 3.5 non emerge solamente sei veicoli hanno distanza esattamente pari a V , ma puo emergere anche se sonosufficientemente prossimi a V : in tal caso limit non e zero ma e sufficientementepiccolo da non consentire ai veicoli di completare la manovra d’inversione. Inquesto caso dunque i veicoli si muovono fino a raggiungere il bordo del cerchio diraggio V/2, portandosi nuovamente in una situazione analoga a quella mostratain figura 3.5. Si tratta percio di una vera e propria patologia.

La situazione in figura 3.5 appare risolvibile se uno solo dei due robot si muovecompiendo un cammino completo sino a c1(t) in un’unica fase e si ammette laperdita temporanea della connessione.

Alla luce delle precedenti considerazioni, si puo quindi concludere che la ricer-ca di un algoritmo che garantisca il mantenimento della connettivita del grafo dicomunicazione in ogni istante sembra essere una via impraticabile per la soluzionedel problema del rendezvous per veicoli di Dubins.

3.3.3 Primo metodo per il rendezvous di veicoli di Dubins

Presentazione dell’algoritmo

Un approccio per superare le difficolta appena discusse potrebbe essere quello difar muovere un solo robot alla volta. In altri termini, un generico robot ri puoattivarsi all’istante t se sono soddisfatte entrambe le seguenti condizioni:

a) non c’e alcun robot in movimento in Si(t)− {ri};

76

b) sono presenti in Si(t) tutti i robot che erano stati rilevati all’ultima atti-vazione di ri.

Se un robot verifica che sono soddisfatte ambedue le condizioni allora si attiva,pianifica una traiettoria e inizia a seguirla, altrimenti ri rimanda il controllo dellecondizioni di attivazione a un istante t′ > t scelto in maniera pseudo-aleatoria.Ovviamente e necessario gestire l’eventualita di conflitti, che potrebbero insorgerese due veicoli si attivano contemporaneamente all’istante t. Si potrebbe incorrerein tale caso se e soddisfatta b) e due robot verificano simultaneamente anche a),ponendosi contemporaneamente in moto. La situazione potrebbe essere gestitacome segue: se, immediatamente dopo l’istante t di attivazione ri rileva un al-tro robot in movimento, si blocca e torna nello stato inattivo fino a un istantet′ > t scelto in maniera pseudo-aleatoria. In tal modo entrambi i robot coinvoltitorneranno ad uno stato di inattivita dal quale usciranno trascorso un interval-lo aleatorio. Naturalmente ri potrebbe intercorrere nuovamente in un conflittoall’istante t′, ma la probabilita che questo accada decresce esponenzialmente.

Con tale scelta non sarebbe piu necessario il parametro limit, introdotto pergarantire il mantenimento della connettivita nel caso in cui due robot vicini sianosimultaneamente in movimento.

Anche σ, introdotto nella sezione precedente, perde la sua utilita. Il parametroσ limita infatti la lunghezza degli spostamenti, in modo da sfruttare meglio lecapacita sensoriali che, per scelta progettuale, non vengono impiegate duranteil movimento del robot. Riducendo σ si aumenta dunque la frequenza con cuiviene osservata la posizione relativa dei robot visibili. Se, pero, ri inizia una faseall’istante t, tutti i robot in Si(t) rimangono immobili, per scelta progettuale,finche ri non completa la fase. Non e dunque necessario compiere rilevamentimolteplici della posizione dei robot in Si(t), perche il punto finale non cambia.

Quindi ciascun robot attivo non percorre, come nell’algoritmo presentato so-pra, solo una parte del movimento, ma completa sempre l’intera traiettoria pi-anificata. Con riferimento alla simbologia introdotta precedentemente, si vuoleche, se ri si attiva all’istante t, allora move = goal e x = ci(t). Per il resto,l’algoritmo modificato, e identico a quello descritto nella sezione precedente.

Un’importante differenza tra l’algoritmo proposto e quello originario risiedenel fatto che non si tratta piu di un metodo senza memoria. Il robot ri al gene-rico istante t non pianifica il proprio movimento solo sulla base della posizioneistantanea dei propri vicini, ma anche tenendo conto dei robot rilevati all’ultimaattivazione, di cui e necessario tenere traccia in memoria. Inoltre i robot nonsono piu anonimi, essendo necessario rilevare la presenza o l’assenza di un vicino.Per fare cio non e sufficiente rilevare semplicemente il numero dei vicini, poichela mancanza di un robot, impegnato in una manovra che causa la temporaneaperdita di contatto con un vicino, potrebbe essere non rilevata a causa dell’arrivodi un nuovo agente. E essenziale quindi distinguere i robot.

77

Analisi dell’algoritmo

Evidentemente la modifica proposta risulta piuttosto conservativa, tuttavia epossibile dimostrare che gode di importanti proprieta, analoghe a quelle del-l’algoritmo di Ando et al.. Si prova anzitutto il seguente lemma, analogo al3.2.

Lemma 3.4. Sia (ti,1, ti,2, ti,3 . . . | 0 ≤ ti,1 < ti,2 < ti,3 < . . .) la successione degliistanti temporali in cui il generico robot ri si attiva. Si ha che Si(ti,1) ⊆ Si(ti,2) ⊆Si(ti,3) ⊆ . . ., ovvero la successione (Si(tk)| k ∈ N) e monotona crescente.

Prima di passare alla dimostrazione e importante fare una puntualizzazione.Il lemma precedente e piu debole del lemma 3.2. Qui infatti non si garantisce che,osservando il sistema ad istanti arbitrariamente prossimi si abbia il mantenimentodi tutti gli archi gia presenti sul grafo di prossimita. Il sistema viene osservatosolo agli istanti di attivazione del robot ri, che non possono essere in generalearbitrariamente vicini, poiche prima di una nuova attivazione, ri deve completareuna manovra che non ha lunghezza massimizzata da una costante arbitrariamentepiccola σ e ri si muove con una velocita massima finita. In secondo luogo, alla k+1-esima attivazione di ri all’istante ti,k+1 ci si limita a constatare il mantenimentodella connessione nel sottografo indotto da Si(ti,k). Non e garantito che Sj(ti,k) ⊆Sj(ti,k+1) per i 6= j. Cioe, all’istante in cui ri si attiva, un altro robot rj potrebbeaver perso il contatto con uno dei suoi vicini che sta compiendo una manovra.Il fatto fondamentale e che negli istanti in cui un robot fermo perde il contatto,rimane inattivo. Un robot che e attivo e perde il contatto con un vicino, invece,sicuramente lo riacquistera al termine della propria manovra.

Dimostrazione: Se all’istante ti,k il robot ri si attiva per la k-esima volta, ilgenerico robot rj ∈ Si(ti,k)−{ri} non puo muoversi sino al completamento dellafase corrente di ri, che si conclude in ci(ti,k), centro della circonferenza di raggiominimo contenente i punti di Si(ti,k). Tale circonferenza contiene rj e ha raggionon superiore a V . Pertanto ri e rj si mantengono in contatto. Al termine dellafase di ri, rj ha la possibilita di muoversi, ma per le argomentazioni appenaesposte non puo concludere una manovra allontanandosi da ri piu di V . Quindi,all’istante ti,k+1 di inizio della k + 1-esima fase di ri, si ha che ri e rj sono incontatto. ¤

Si osservi che la successione (Si(ti,k)|k ∈ N) e limitata, perche il numero dirobot e finito. Pertanto (Si(ti,k)|k ∈ N) e convergente per ogni ri ∈ S. Dunqueesiste un istante t∗ dopo il quale non si ha piu l’entrata in contatto di nuovecoppie di robot. A questo punto, necessariamente, tutti i robot appartenenti aduna stessa componente connessa sono mutuamente in contatto; formalmente, perti,k > t∗ si ha che Si(ti,k) = Sj(ti,k) se rj ∈ Si(ti,k). Si indichi la generica com-ponente connessa Si(ti,k) per ti,k > t∗, semplicemente con il simbolo S. Ad ogniistante c’e, al piu, un robot attivo in S. Si consideri la successione degli istanti

78

temporali di attivazione di uno dei robot in S: T = (ti,k| ti,k > t∗, ri ∈ S, k ∈ N).E’ possibile indicare gli elementi di tale successione piu semplicemente con i sim-boli t1, t2, t3, . . .. Si denoti con CH(tk) il guscio convesso delle posizioni dei robotin S all’istante tk ∈ T . Non e difficile provare il seguente

Lemma 3.5. CH(tk+1) ⊆ CH(tk) per ogni tk ∈ T .

Dimostrazione: Per ogni tk ∈ T c’e uno e un solo robot attivo in S. Sia ri

il generico robot attivo all’istante tk. All’istante tk+1 il robot ri ha completatola fase iniziata in tk e si trova in ci(tk): ri(tk+1) = ci(tk). Tutti gli altri robotin S non si sono mossi: rj(tk+1) = rj(tk) per j 6= i. Per definizione ri(tk+1) ∈CH(tk+1) e per il lemma 3.1 ci(tk) ∈ CH(tk). Allora CH(tk+1) ⊆ CH(tk). ¤

Pertanto la successione (CH(tk)|k ∈ N) e limitata inferiormente ed e mono-tona decrescente, quindi e convergente ad un certo CH. Certamente CH e unpoligono convesso, includendo i casi degeneri del segmento e del punto. Resta daprovare l’effettiva convergenza ad un punto. La dimostrazione risulta piu sem-plice rispetto a quella analoga condotta da Ando et al. in [3], poiche qui, fissatauna componente connessa (S,A) del grafo di prossimita G(tk), con tk ≥ t∗, si ha,al piu, un solo robot in movimento per ogni istante e la traiettoria pianificataviene sempre seguita per intero sino al punto finale, centro della circonferenza diraggio minimo contenente i robot in S. Tale punto e, per definizione, il punto cheminimizza la massima distanza tra il robot correntemente attivo e ciascuno deirobot in S. Evidentemente, la massima distanza tra i robot e minima, cioe e nul-la, se e solo se essi si trovano tutti nello stesso punto. Se, dunque, la successione(CH(tk)|k ∈ N) converge, non puo che convergere a un punto.

Si noti, tuttavia, che la velocita di convergenza risulta essere notevolmenteinferiore rispetto a quella esibita dall’algoritmo di Ando et al. per robot onni-direzionali. Questo fatto non stupisce, poiche qui si assume che ciascun robotnon possa avere piu di un vicino, compreso se stesso, in moto. Il movimentosimultaneo dei robot e qui proibito.

Per tentare di quantificare la riduzione della velocita di convergenza, sonostate condotte alcune prove al simulatore, come quella riportata in figura 3.6.Otto veicoli e-puck sono stati disposti in maniera casuale, con orientazione ca-suale, in un’area di due metri per due. Nei capitoli precedenti, al fine di imporreun raggio minimo di curvatura agli e-puck, si era assunto che questo fosse paria quello ottenibile muovendo una soltanto delle due ruote. Qui, invece, per ev-idenziare gli effetti di questo vincolo, si e scelto un rmin cinque volte maggiore,pari cioe a 13.25 cm. Si e fissato V pari a un metro. In figura 3.7 e riporta-to l’andamento temporale della massima distanze tra i robot. Assumendo che ilrendezvous sia raggiunto quando tutti i veicoli si trovino ad una distanza euclideamutua inferiore a rmin, i tempi per il raggiungimento del rendezvous registrati alsimulatore superano i due minuti e mezzo. Nelle stesse condizioni sperimentali,implementando l’algoritmo di Ando su robot onnidirezionali aventi la stessa ve-locita massima e dotati degli stessi sensori, si e raggiunto il rendezvous sempre in

79

0 0.5 1 1.5 2

0

0.2

0.4

0.6

0.8

1

1.2

1.4

1.6

1.8

2

Rendezvous: t = 0 s

x [m]

y [m

]

0 0.5 1 1.5 2

0

0.2

0.4

0.6

0.8

1

1.2

1.4

1.6

1.8

2

Rendezvous: t = 25 s

x [m]

y [m

]

0 0.5 1 1.5 2

0

0.2

0.4

0.6

0.8

1

1.2

1.4

1.6

1.8

2

Rendezvous: t = 50 s

x [m]

y [m

]

0 0.5 1 1.5 2

0

0.2

0.4

0.6

0.8

1

1.2

1.4

1.6

1.8

2

Rendezvous: t = 75 s

x [m]

y [m

]

0 0.5 1 1.5 2

0

0.2

0.4

0.6

0.8

1

1.2

1.4

1.6

1.8

2

Rendezvous: t = 100 s

x [m]

y [m

]

0 0.5 1 1.5 2

0

0.2

0.4

0.6

0.8

1

1.2

1.4

1.6

1.8

2

Rendezvous: t = 125 s

x [m]

y [m

]

0 0.5 1 1.5 2

0

0.2

0.4

0.6

0.8

1

1.2

1.4

1.6

1.8

2

Rendezvous: t = 150 s

x [m]

y [m

]

0 0.5 1 1.5 2

0

0.2

0.4

0.6

0.8

1

1.2

1.4

1.6

1.8

2

Rendezvous: t = 175 s

x [m]

y [m

]

Figura 3.6. Successione temporale delle configurazioni di 8 veicoli di Dubins tipo e-puck,con rmin = 13.25 cm e V = 1 m, che implementano l’algoritmo di rendezvous proposto. Laconfigurazione iniziale e stata generata in maniera pseudo-aleatoria con una distribuzione diprobabilita uniforme in [0, 2]× [0, 2]× [0, 2π) ⊂ R2 × S1 (le distanze si intendono in metri, gliangoli in radianti). I grafici rappresentano la configurazione del sistema a intervalli di 25 s.

80

0 20 40 60 80 100 120 140 160 1800

0.5

1

1.5

2

2.5

3Convergence of 8 robots

time [s]

Max

imum

dis

tanc

e be

twee

n ro

bots

[m]

Figura 3.7. Evoluzione temporale della massima distanza tra robot relativa all’esperimentomostrato in figura 3.6. Le linee tratteggiate orizzontali indicano rmin e 4rmin.

meno di dieci secondi: oltre quindici volte in meno del tempo richiesto dall’altroalgoritmo.

Si e inoltre osservato che, all’aumentare del numero di robot, il tempo richiestoper il rendezvous cresce sensibilmente, in maniera ben piu che lineare, mentre none cosı per i robot onnidirezionali. Si veda in proposito il grafico mostrato in figura3.12. L’algoritmo proposto quindi peggiora le proprie prestazioni all’aumentaredel numero di agenti, a scapito della scalabilita. Se, infatti, quando i robotsono sufficientemente lontani si possono avere contemporaneamente piu unita inmovimento, che non sono vicina l’una dell’altra, mano a mano che ci si avvicinaal rendezvous il numero delle unita simultaneamente attive tende a decrescere,fino a quando tutti i robot giungono in prossimita gli uni degli altri: da allora inpoi al piu un solo agente ha la facolta di essere attivo. La velocita di convergenzadiminuisce con l’avvicinarsi del rendezvous.

Si comprende dunque che l’algoritmo, benche garantisca il rendezvous, comesi e dimostrato, risulta lento e soffre di scarsa scalabilita.

3.3.4 Secondo metodo per il rendezvous di veicoli di Du-bins

Presentazione dell’algoritmo

Il “primo metodo” appena proposto per il rendezvous di veicoli di Dubins risultaessere piuttosto conservativo. Il fatto di avere un solo robot in movimento rendeinfatti la convergenza considerevolmente piu lenta rispetto al caso di robot onni-direzionali in moto simultaneo. Se, da un lato, imponendo che ogni robot rilevial piu un robot in movimento, e semplice garantire la convergenza a un punto,dall’altro si intuisce che non e necessario richiedere di avere un solo robot attivose gli agenti sono sufficientemente vicini.

81

Si potrebbe pensare quindi di utilizzare l’algoritmo di Ando rivisitato nellasezione 3.3.2, ricorrendo al “primo metodo” solamente nei casi in cui si pervengaad una situazione di stallo, come quella rappresentata in figura 3.5. In tal modosi potrebbe tentare di risolvere il problema della lenta convergenza del “primometodo”, ma al tempo stesso garantire l’assenza di configurazioni patologiche distallo.

L’algoritmo che si propone sara detto ”secondo metodo” e puo descriversicome segue. Il generico robot ri si attiva ad istanti t scelti in maniera pseudo-aleatoria, calcola ci(t), goal e limit esattamente come nell’algoritmo di Ando etal. rivisitato nella sezione 3.3.2. A differenza di quanto ivi esposto, prima dicalcolare move e di iniziare a muoversi, ri testa il valore di limit. Se esso risul-ta superiore ad una lunghezza minima ε prestabilita, allora l’algoritmo procedecome descritto nella sezione 3.3.2, ovvero move e il minimo tra goal, limit e σ, ilrobot ri intraprende una traiettoria ottima di Dubins verso ci(t), ma la percorresolo parzialmente per un tratto di lunghezza move. Se, invece, limit ≤ ε allorari rileva una situazione di stallo analoga a quella riportata in figura 3.5: anche unmovimento di lunghezza ε molto piccola potrebbe causare la perdita di connet-tivita con qualche vicino. Per evitare lo stallo, si puo allora utilizzare l’idea del“primo metodo”: il robot ri intima a tutti i suoi vicini di bloccarsi, inviando loroun apposito segnale, che sara detto freeze, e intraprende un cammino completoverso ci(t). Solo a cammino ultimato, ri comunica ai vicini il termine dello statofreeze. Un robot che riceve il segnale freeze si ferma se era in moto, si disattivase era attivo, cancella la traiettoria eventualmente pianificata e non si riattivafino a quando non gli viene consentito di uscire dalla modalita freeze dallo stessoagente che l’ha invocata.

L’implementazione dell’algoritmo qui proposto, come per il “primo metodo”,richiede robot non anonimi, dotati di memoria e di un identificativo che puoessere rilevato dai sensori di bordo. Inoltre e qui necessario che i robot siano ingrado di comunicare con tutti gli agenti che si trovano entro un raggio V , perpoter inviare il segnale freeze.

Analisi dell’algoritmo

Si osserva anzitutto che situazioni patologiche di stallo, come quelle mostratein figure 3.5, sono state rimosse. Se si dovesse incorrere in tale configurazio-ne, infatti, il primo robot ad attivarsi invierebbe il segnale freeze all’altro e sisposterebbe verso il centro della circonferenza, punto in cui la connettivita delgrafo di prossimita e garantita.

E immediato verificare inoltre che l’algoritmo proposto conserva la proprieta,espressa dal lemma 3.4, valida per il primo metodo. Quindi, se c’e perdita diconnettivita nel grafo di prossimita, questa e temporanea e nessun veicolo pi-anifica una nuova traiettoria se non e piu in prossimita di uno dei suoi vicini.Si puo quindi dedurre, seguendo lo schema delle argomentazioni precedenti, che

82

0 0.2 0.4 0.6 0.8 1 1.2 1.4 1.6 1.8 2

0

0.2

0.4

0.6

0.8

1

1.2

1.4

1.6

1.8

2

Rendezvous: t = 0 s

x [m]

y [m

]

0 0.2 0.4 0.6 0.8 1 1.2 1.4 1.6 1.8 2

0

0.2

0.4

0.6

0.8

1

1.2

1.4

1.6

1.8

2

Rendezvous: t = 7 s

x [m]

y [m

]

0 0.2 0.4 0.6 0.8 1 1.2 1.4 1.6 1.8 2

0

0.2

0.4

0.6

0.8

1

1.2

1.4

1.6

1.8

2

Rendezvous: t = 14 s

x [m]

y [m

]

0 0.2 0.4 0.6 0.8 1 1.2 1.4 1.6 1.8 2

0

0.2

0.4

0.6

0.8

1

1.2

1.4

1.6

1.8

2

Rendezvous: t = 21 s

x [m]

y [m

]

0 0.2 0.4 0.6 0.8 1 1.2 1.4 1.6 1.8 2

0

0.2

0.4

0.6

0.8

1

1.2

1.4

1.6

1.8

2

Rendezvous: t = 28 s

x [m]

y [m

]

0 0.2 0.4 0.6 0.8 1 1.2 1.4 1.6 1.8 2

0

0.2

0.4

0.6

0.8

1

1.2

1.4

1.6

1.8

2

Rendezvous: t = 35 s

x [m]

y [m

]

0 0.2 0.4 0.6 0.8 1 1.2 1.4 1.6 1.8 2

0

0.2

0.4

0.6

0.8

1

1.2

1.4

1.6

1.8

2

Rendezvous: t = 42 s

x [m]

y [m

]

0 0.2 0.4 0.6 0.8 1 1.2 1.4 1.6 1.8 2

0

0.2

0.4

0.6

0.8

1

1.2

1.4

1.6

1.8

2

Rendezvous: t = 49 s

x [m]

y [m

]

Figura 3.8. Successione temporale delle configurazioni di 20 veicoli di Dubins tipo e-puck, conrmin = 13.25 cm e V = 1 m, che implementano la seconda versione dell’algoritmo di rendezvous.La configurazione iniziale e stata generata in maniera pseudo-aleatoria con una distribuzionedi probabilita uniforme in [0, 2] × [0, 2] × [0, 2π) ⊂ R2 × S1 (le distanze si intendono in metri,gli angoli in radianti). I grafici rappresentano la configurazione complessiva a intervalli di 7 s.

83

0 5 10 15 20 25 30 35 40 45 500

0.5

1

1.5

2

2.5Convergence of 20 robots

time [s]

Max

imum

dis

tanc

e be

twee

n ro

bots

[m]

Figura 3.9. Evoluzione temporale della massima distanza tra robot relativa all’esperimentomostrato in figura 3.8. Le linee tratteggiate orizzontali indicano rmin e 4rmin.

esiste un istante t∗ dopo il quale non si ha piu l’aggiunta di nuovi archi al grafodi connettivita.

Una proprieta che, invece, non e estendibile all’algoritmo appena presentato,come, del resto, all’algoritmo di Ando rivisitato nella sezione 3.3.2, e il lemma diconvergenza 3.3. Non si possono cioe utilizzare le argomentazioni della prova dellemma 3.3 per provare che il guscio convesso contenente le posizioni dei robotconverge. Cio e dovuto, come gia si e detto, al fatto che i punti di una traiettoriadi Dubins non si possono esprimere come combinazione convessa degli estremi.La difficolta nasce dalla non controllabilita in tempo breve dei veicoli di Dubins:non si puo escludere l’eventualita che il movimento di un veicolo porti ad unaumento del diametro del guscio convesso, anziche ad una sua diminuzione.

Prove sperimentali condotte al calcolatore evidenziano, effettivamente, che iveicoli di una stessa componente connessa tendono ad avvicinarsi fino a quando ilraggio del guscio convesso non e confrontabile con il raggio minimo di curvatura.A questo punto i veicoli si trovano a pianificare traiettorie relativamente lunghe,rispetto alla distanza euclidea dall’obiettivo. E dunque elevata la probabilitache il generico robot ri, attivandosi, rilevi i propri vicini relativamente lontanidall’obiettivo, dunque, nel tentativo di avvicinarvisi compia esso stesso una nuovamanovra di inversione. Il risultato complessivo e uno sciamare dei veicoli attornoad un punto di rendezvous che si sposta continuamente secondo una passeggiataaleatoria. La successione temporale dei diametri del guscio convesso contenentei robot appare dunque essere definitivamente limitata ma non convergente.

Questo fatto e messo in evidenza dai grafici raccolti in successione temporalein figura 3.8 e dall’andamento della massima distanza tra robot registrata du-rante lo stesso esperimento, riportato in figura 3.9. L’esperimento, condotto alsimulatore, coinvolge venti veicoli di Dubins di tipo e-puck con rmin = 13.25 cme V = 1 m, esattamente come in figura 3.6. Si osserva che il sistema tende al

84

rendezvous con fasi successive di allontanamento e avvicinamento. Si tratta diun comportamento che puo essere considerato come un ciclo limite del sistema.

Benche l’algoritmo non porti tutti i robot ad entrare in un intorno arbi-trariamente piccolo e a rimanervi definitivamente, come sarebbe richiesto dalladefinizione di rendezvous, si osserva comunque che la massima distanza tra robottendenzialmente decresce. Si puo anche tentare di dare una stima della massimaampiezza della perturbazione del ciclo limite. Dall’analisi delle traiettorie ottimedi Dubins condotta all’inizio della sezione, emerge in maniera evidente che se unpunto q dista d dalla posizione attuale p, la traiettoria che porta da p a q nonsi allontana dal segmento pq piu di 2rmin. Si potrebbe dunque pensare che sela distanza massima tra i robot e dmax ad un certo istante t, questa non possacrescere piu di dmax + 4rmin dopo t. Il grafico in figura 3.9 sembra confermarequesta stima. Si tratta comunque di un calcolo approssimato, perche muovendosii robot fanno si che anche il centro della circonferenza minima si sposti, seppurepiu lentamente dei singoli agenti, rendendo inesatto il ragionamento precedente.Il valore della massima ampiezza del ciclo limite registrato sperimentalmente ecomunque in ottimo accordo con questa stima: si vedano, ad esempio, i graficidi figura 3.11 in cui la massima distanza mutua tra i robot, sia nel caso medio(sinistra) che in quello peggiore (destra) pare mantenersi definitivamente limitataentro 4rmin.

Si comprende dunque che richiedere la convergenza a un punto per un gruppodi veicoli di Dubins e un obiettivo troppo esigente. Le difficolta evidenziate dalleconsiderazioni precedenti non nascono dalle caratteristiche dell’algoritmo pro-posto, ma risiedono invece nella non controllabilita in tempo breve dei veicoli diDubins e paiono pertanto di difficile risoluzione. Si profilano quindi due possibiliapprocci al problema.

Una prima idea potrebbe essere quella di formulare delle ipotesi ulteriori suiveicoli, assumendo possibile la comunicazione con i vicini. In tal caso ciascunrobot potrebbe rilevare la posizione dei vicini e comunicarla a loro. Se il grafodi prossimita e connesso la risoluzione di un problema di consenso e possibile. Siosservi pero che non e sufficiente raggiungere il consenso solamente sulla posizioneiniziale dei robot, come ad esempio in [14], ma anche sulla loro orientazione. Inquesto modo tutti i robot potrebbero accordarsi su un unico punto e quindiconvergervi.

Senza queste ipotesi aggiuntive pare molto difficile individuare un algorit-mo di rendezvous per veicoli di Dubins che garantisca la convergenza ad unpunto. D’altro canto la convergenza ad un punto non e mai necessaria in pra-tica, dato che i veicoli hanno delle dimensioni fisiche non nulle, ed e di scarsautilita far convergere tutte le unita in un intorno di raggio comparabile con rmin,poiche poi i veicoli si ostacolerebbero a vicenda, rendendo estremamente difficilela pianificazione dei movimenti.

Si delinea quindi un secondo approccio. L’idea e che la definizione di ren-dezvous come convergenza a un punto e troppo restrittiva per veicoli di Dubins.Si propone una definizione pratica di rendezvous come convergenza a un intorno

85

di un punto dimensioni abbastanza grandi da non fare emergere fenomeni di ciclilimite. Non si vuole dunque che tutti i veicoli si raccolgano entro un cerchio diraggio infinitesimo, ma ci si limita a richiedere che convergano entro un cerchiodi raggio finito. Alla luce delle considerazioni precedenti, si potrebbe ritenereraggiunto il rendezvous pratico quando la massima distanza tra i veicoli sia nonsuperiore ad una quantita attorno a 4rmin. L’algoritmo proposto pare, in questosenso, una buona soluzione.

0 5 10 15 20 25 30 35 40 45 500

0.5

1

1.5

2

2.5Convergence of 10 robots: min, mean and max of 10 experiments

time [s]

Max

. dis

tanc

e be

twee

n ro

bots

[m]

Method 2Method 1

Figura 3.10. Dieci robot sono stati disposti in maniera casuale, con orientazione casuale inun’area quadrata di 2 m di lato, garantendo pero la connettivita del grafo di prossimita. Per10 volte e stato applicato il primo metodo e per altrettante il secondo; la durata di ciascunesperimento e stata fissata a 50 secondi. In ogni caso si e registrata l’evoluzione della massimadistanza tra i robot del gruppo. In rosso sono riportati i risultati ottenuti con il primo metodo,in blu quelli relativi al secondo. Il valore medio e evidenziato con tratto grosso, mentre contratto fine sono riportati i valori massimi e minimi registrati. Le linee orizzontali tratteggiateindicano rmin e 4rmin.

Dalla figura 3.10 si evince come il secondo metodo, pur non risolvendo il pro-blema del rendezvous in senso stretto, sia, dal punto di vista pratico, preferibileal primo metodo, che invece garantisce la convergenza a un punto. Sono statecondotte dieci prove con ciascun metodo: ogni prova consiste nel disporre inmaniera casuale dieci robot, garantendo la connettivita del grafo di prossimita,lasciare evolvere il sistema per 50 secondi sotto l’azione dell’algoritmo di ren-dezvous e registrare l’andamento della massima distanza tra i robot. Il graficoriporta i valori minimi, massimi e medi ottenuti con i due algoritmi. Appare inmaniera evidente la maggiore velocita del secondo metodo: il primo metodo, in-fatti, puo mantenere i robot con massima distanza fermi finche si spostano altri.Pertanto la massima distanza puo mantenersi costante per degli intervalli primadi diminuire. Cio invece non accade in maniera sistematica per il secondo meto-do. Dopo 50 secondi il primo metodo e ancora lontano dal rendezvous, mentre ilsecondo porta tutti i veicoli a una distanza mutua inferiore a 4rmin, in media, inmeno di 12 secondi.

86

0 5 10 15 20 25 30 35 40 45 500

0.5

1

1.5

2

2.5

time [s]

Max

imum

dis

tanc

e be

twee

n ro

bots

[m]

10 robots20 robots40 robots

Convergence of a group of robots: average results of 10 experiments

0 5 10 15 20 25 30 35 40 45 500

0.5

1

1.5

2

2.5

3Convergence of a group of robots: min and max of 10 experiments

time [s]

Max

imum

dis

tanc

e be

twee

n ro

bots

[m]

10 robots20 robots40 robots

Figura 3.11. Un gruppo di robot e stato disposto in maniera casuale, con orientazione casualein un’area quadrata di 2 m di lato, garantendo pero la connettivita del grafo di prossimita.Per 10 volte e stato applicato il secondo metodo per il rendezvous. In ogni caso si e registratal’evoluzione della massima distanza tra i robot; la durata di ciascun esperimento e stata fis-sata a 50 secondi. A sinistra sono riportati i valori medi ottenuti con gruppi di 10, 20 e 40robot; a destra sono invece raffigurati i valori minimi e massimi registrati. Le linee orizzontalitratteggiate indicano rmin e 4rmin.

5 10 15 20 25 30 35 4010

0

101

102

103

Robot number

Tim

e fo

r pr

actic

al r

ende

zvou

s [s

]

Scalability analysis

Method 1Method 2

Figura 3.12. Il grafico riporta sull’asse delle ascisse il numero di robot e sull’asse delle ordinate,in scala logaritmica il tempo medio richiesto dagli algoritmi di rendezvous per portare tutti iveicoli a una distanza mutua inferiore a 4rmin. Per ciascuno dei due metodi si sono condotte10 prove con 5, 10, 20, 30 e 40 robot e si calcolati i valori medi. Le croci indicano i valoriottenuti, in rosso per il primo metodo, in blu per il secondo. Le curve sono state poi ottenuteper interpolazione.

Si era osservato in precedenza che il primo metodo soffre di scarsa scalabilita.Il tempo richiesto per il raggiungimento del rendezvous cresce infatti in manieraben piu che lineare con il numero degli agenti coinvolti. I grafici delle figure3.11 e 3.12 mostrano che questo problema e stato risolto dal secondo metodo, seovviamente ci si limita a considerare un rendezvous pratico. Se dieci veicoli si

87

0 5 10 15 20 25 30 35 40 45 500

0.5

1

1.5

2

2.5

time [s]

Max

imum

dis

tanc

e be

twee

n ro

bots

[m]

No errorRelative error 5 %Relative error 10 %Relative error 25 %

Convergence of 20 robots with sensor errors

Figura 3.13. Evoluzione temporale, mediata su 10 esperimenti, della massima distanza traventi robot che si muovono per 50 secondi sotto l’azione dell’algoritmo proposto. Si sonocondotte quattro prove: nella prima (blu) si sono assunti sensori di posizione accurati, nellealtre si e assunto che i sensori dei robot fossero affetti da un errore gaussiano di media nulla edeviazione standard pari al 5%, al 10% e al 25% della distanza effettiva. Le linee tratteggiateorizzontali indicano rmin e 4rmin.

trovano a una distanza mutua inferiore a 4rmin, in media, in meno di 12 secondi,con venti robot si raggiunge lo stesso risultato in 15 secondi e con 40 robot in 16secondi. L’aumento e dovuto anche al fatto che, tanto maggiore e il numero diveicoli in un quadrato, tanto piu cresce in media la massima distanza mutua ini-ziale. Si verifica che la velocita di convergenza media dalla configurazione inizialead una di rendezvous pratico e attorno ai 12.5 cm/s in tutti e tre i casi. In realtainizialmente e possibile un allontanamento, che porta un contributo negativo, poiinizia una fase di avvicinamento rapido e in prossimita del rendezvous praticosi registra un rallentamento tanto piu evidente tanto maggiore e il numero degliagenti. In prima approssimazione, comunque, la velocita media di convergenzaal rendezvous pratico e indipendente dal numero di agenti. Al contrario il primometodo soffre di una crescita esponenziale dei tempi richiesti per il raggiungi-mento del rendezvous, come messo in luce dal grafico riportato in figura 3.12. Sivede dunque che l’algoritmo proposto risulta essere rapido e scalabile.

Ripetendo, poi, gli esperimenti ipotizzando sensori non ideali, si e osservato unbuon grado di robustezza dell’algoritmo. In figura 3.13 e riportato l’andamentotemporale della massima distanza tra venti robot, mediata su dieci esperimenti,in movimento sotto l’azione del secondo metodo proposto. Si e pero assunto che isensori dei robot fossero affetti da un errore gaussiano di media nulla e deviazionestandard pari al 5% (curva rossa), al 10% (curva nera) e al 25% (curva viola) delladistanza reale. Confrontando i grafici ottenuti con quello registrato in assenzadi errori (curva blu) non si rileva quasi alcuna differenza nel caso di un errorerelativo del 5%, mentre si ravvisa un leggero rallentamento della convergenza, ma

88

non un sostanziale peggioramento delle prestazioni, nei casi di un errore relativodel 10% e del 25%. Il secondo metodo proposto per il rendezvous pratico diveicoli mobili, appare quindi robusto alla presenza di errori di localizzazione nontrascurabili a carico dei sensori di bordo dei robot.

In conclusione, seppure rigorosamente l’algoritmo non offra una soluzione delproblema del rendezvous, inteso come convergenza a un punto, si nota che sitratta di una tecnica soddisfacente sul piano pratico, veloce e robusta rispettoagli errori di localizzazione dei sensori.

89

90

Capitolo 4

Conclusioni

4.1 Risultati ottenuti

Nella prima parte della tesi si e affrontato il problema della progettazione diun controllore digitale per un sistema descrivibile con equazioni differenziali atempo continuo, anche non lineari, in cui si abbia la compresenza di sensoripropriocettivi, che consentano misurazioni con frequenza di campionamento ele-vata, e di sensori esterocettivi, che operano a frequenze inferiori e possibilmentenon uniformi. Un esempio di tale sistema e costituito da un veicolo di Dubinssu ruote che si muova in un ambiente monitorato da un sistema di telecamere,facente funzione di GPS, con il quale il veicolo ha la possibilita di comunicare; isensori on-board potrebbero essere invece costituiti da dei trasduttori di posizioneangolare delle ruote.

L’approccio proposto al problema della pianificazione del movimento fonde iprincipi fondamentali della pianificazione ottima di traiettorie per un veicolo diDubins, quelli della quantizzazione del controllo e del model predictive control.Questa tecnica presenta i seguenti vantaggi:

1. Non richiede che l’informazione dei sensori esterocettivi sia ricevuta adistanti equidistanti nel tempo e nel caso di sistemi drift-less si possonoottenere buone prestazioni anche per frequenze di acquisizione dell’infor-mazione sensoriale basse.

2. L’approccio proposto e sub-ottimo, rispetto ad un qualche criterio (ad.esempio: tempo minimo), per sistemi generici, poiche, per scelta proget-tuale, si limitano le traiettorie ammissibili ad una famiglia finita, che ingenerale non contiene tutte le possibili traiettorie ottime. Nel caso par-ticolare di veicoli di Dubins, pero, i risultati ricavati in [19] garantisconol’ottimalita delle traiettorie generate dal controllore proposto nel primocapitolo. Questa proprieta si ottiene senza che il processore a bordo delveicolo debba risolvere alcun problema di minimizzazione per via numeri-ca, riducendo cosı notevolmente il carico computazionale. Cio e dovuto alfatto che l’originario problema di ottimo differenziale viene trasformato in

91

un problema algebrico di cinematica inversa; dall’originario spazio infinito-dimensionale delle soluzioni ci si restringe, per scelta progettuale, ad unopportuno sotto-spazio di dimensione finita in cui la ricerca dell’ottimo epiu semplice.

3. La traiettoria viene pianificata con un orizzonte ristretto: dalla configura-zione corrente fino al prossimo punto solamente. Questo garantisce che l’al-goritmo funzioni in tempo reale anche per traiettorie molto lunghe. Inoltrela maggiore quantita dei calcoli viene eseguita in fase di pianificazione dellatraiettoria, quindi relativamente di rado. Per la maggior parte del tempoil processore puo gestire altri task. La traiettoria da seguire puo poi essereaggiornata con veicolo gia in movimento.

4. Nel caso a tempo continuo, gli algoritmi proposti in letteratura per il track-ing e per il posteggio sono molto diversi: nel caso a tempo discreto, in-vece, l’algoritmo presentato risolve entrambi i problemi. Inoltre l’algoritmoproposto e applicabile a una qualsiasi sequenza di punti isolati in R2 × S1.

5. In simulazione si sono ottenuti risultati buoni anche in presenza di unleggero drift. In tal caso pero le prestazioni sono tanto migliori tanto piualta e la frequenza media di ricezione dell’informazione da parte del GPS.

Nel caso dei veicoli di Dubins il sistema di controllo proposto puo poi essereintegrato con una routine di alto livello per la pianificazione di traiettorie privedi collisioni in ambienti con presenza di ostacoli. Nel secondo capitolo si e for-nito un esempio di algoritmo deterministico per la pianificazione del movimentotra ostacoli poligonali. La tecnica proposta e una rivisitazione dell’algoritmopubblicato da Bicchi et al. in [9]. La versione originale non e adatta ad essereapplicata a veicoli di Dubins, poiche non garantisce la generazione di camminiprivi di cuspidi, quindi richiede che il veicolo possa muoversi avanti e indietro.Inoltre, l’algoritmo di Bicchi et al. non assicura che la configurazione finale ven-ga raggiunta con l’orientazione voluta: non si esclude dunque la necessita diuna manovra correttiva d’inversione. La tecnica qui proposta risolve entram-bi i problemi, grazie ad un’esplorazione ad albero delle possibili traiettorie. Ilmetodo presentato in questa tesi, poi, fornisce la traiettoria di lunghezza minimase il cammino ottimo non richiede manovre di inversione. Se, invece, il percor-so di lunghezza minima contiene delle inversioni, allora l’algoritmo fornisce unasoluzione sub-ottima, oppure potrebbe non individuare soluzione alcuna.

La progettazione di algoritmi di controllo per una molteplicita di robot mo-bili e radicalmente diversa da quella per singoli agenti. Se per un unico veicolo epensabile l’esistenza di un controllore centralizzato che guidi il veicolo verso unobiettivo desiderato, possibilmente attraverso campi di ostacoli, facendo uso disensori esterocettivi in grado di rilevare completamente lo stato del sistema, alcrescere del numero dei veicoli la complessita computazionale richiesta aumentapiu che linearmente. Anche in ambienti privi di ostacoli, infatti, le traiettorie dei

92

diversi veicoli non possono essere pianificate separatamente, indipendentementel’una dall’altra, bensı assieme, per garantire l’assenza di collisione mutue. Ciorende la pianificazione distribuita delle traiettorie preferibile all’approccio cen-tralizzato. I vantaggi del paradigma distribuito non risiedono solamente nellapossibilita di sfruttare in parallelo le risorse computazionali degli agenti, ma an-che nella possibilita di progettare sistemi capaci di auto-organizzarsi e robustirispetto al malfunzionamento o alla completa rottura di una parte dei robot.Cio si paga, pero, con una maggiore difficolta di controllare l’evoluzione globaledel sistema, che non e codificata esplicitamente in alcun punto, ma e una con-seguenza delle interazioni locali tra gli agenti; in particolare risulta piu complessogarantire l’assenza di comportamenti indesiderabili.

In un paradigma distribuito il problema di far convergere tutti gli agenti inun unico punto e non banale, specialmente se i robot mobili coinvolti hannouna ridotta controllabilita, come nel caso delle macchine di Dubins. Allo statoattuale non sono note soluzioni al problema pubblicate nella letteratura tecnica.In effetti, se il range dei sensori di localizzazione a bordo di ciascun agente e dialmeno un ordine di grandezza superiore al raggio minimo di curvatura dei veicoli,si osserva sperimentalmente che gli algoritmi sviluppati per robot onnidirezionalisi applicano con successo anche alle macchine di Dubins con elevata probabilita: illoro fallimento si verifica solamente per condizioni iniziali patologiche particolari.Inoltre, al crescere della densita degli agenti, le condizioni di errore possonopassare inosservate, dato il buon grado di robustezza delle tecniche di rendezvousproposte in letteratura per robot onnidirezionali: se il vincolo sul minimo raggiodi curvatura viene trascurato e possibile che un veicolo perda il contatto conun vicino, ma se la densita degli agenti e elevata, e improbabile che tale veicoloperda il contatto con tutti i vicini o che comunque non entri piu in contatto conun altro robot, rimanendo definitivamente isolato.

L’algoritmo, che si e detto “secondo metodo”, per il rendezvous di veicoli diDubins proposto in questa tesi tiene conto di questo fatto. L’idea sostanzialee di verificare la possibile evenienza di situazioni che potrebbero determinare laperdita di connettivita. Qualora non si presenti tale rischio l’algoritmo opera inmaniera del tutto analoga all’algoritmo proposto da Ando et al. in [3]. Se invecee possibile una perdita di connettivita il metodo presentato prova a portare ilsistema in una situazione di assenza di tale rischio. L’algoritmo proposto nonva applicato solamente quando il raggio di curvatura dei veicoli di Dubins econfrontabile con il range dei sensori di localizzazione a bordo di ciascun agente,bensı si puo applicare a veicoli di Dubins generici. E l’algoritmo ad individuare inmaniera dinamica e flessibile quando non c’e il rischio di perdita di connettivita edunque e applicabile una tecnica di rendezvous piu veloce, improntata sul metododi Ando et al. per robot onnidirezionali, e quando, invece, si e in presenza disituazioni patologiche che richiedono una diversa gestione, necessariamente menorapida. L’algoritmo si applica in maniera del tutto generale a veicoli di Dubins,assicurando il mantenimento della connettivita in qualunque caso.

93

Cio che, invece, l’algoritmo non garantisce e la convergenza di tutti i veicolidi una componente connessa del grafo di prossimita a un punto. Le simulazionicondotte hanno messo in evidenza che la successione temporale dei gusci convessicontenenti le posizioni dei veicoli non e convergente. Si e osservato, pero, che, seraggiungere una distanza massima tra i veicoli attorno a 4rmin puo considerarsisufficiente, l’algoritmo offre prestazioni soddisfacenti dal punto di vista pratico.Le prove condotte al simulatore hanno, anzi, evidenziato una buona velocita diconvergenza della norma infinito dell’insieme delle distanze mutue tra robot entro4rmin, pressoche indipendente dal numero di robot, e un considerevole grado dirobustezza agli errori di localizzazione che affliggono i sensori di bordo dei robot.

Garantire la convergenza in intorni piu piccoli di 4rmin pare un obiettivo nonsemplicemente raggiungibile. La difficolta non risiede infatti nelle caratteristi-che dell’algoritmo proposto, ma nel fatto che i robot non sono controllabili intempo breve e si muovono simultaneamente, in maniera asincrona e senza mutuacomunicazione locale dell’informazione sensoriale propriocettiva. Tutti questifatti, assieme, rendono il problema complicato. Rimuovendo uno solo dei vincoliil problema diviene invece risolvibile. Se i robot fossero controllabili in tempobreve, si potrebbe pensare di applicare un algoritmo analogo a quello proposto daAndo et al.; se i robot non si muovessero simultaneamente si perverrebbe al ren-dezvous applicando il primo metodo presentato; se, infine, si potesse scambiareinformazione si potrebbe, prima, ottenere il consenso sul punto di rendezvous,poi condurvi i vari agenti. Senza rimuovere alcuna delle assunzioni non apparechiaro quale strategia possa condurre al rendezvous.

4.2 Sviluppi ulteriori

Si suggeriscono due vie per migliorare le proprieta di convergenza dell’algoritmoentro intorni piu piccoli di 4rmin.

Una prima possibilita potrebbe essere di passare al primo metodo, qualora siabbiano tutti i veicoli ad una distanza mutua inferiore a 4rmin. Cio garantirebbeil raggiungimento del rendezvous e sarebbe certamente piu rapido che applicareil primo metodo dall’inizio, poiche nella prima fase di avvicinamento si avrebbeil moto simultaneo dei robot. Il raggiungimento definitivo del rendezvous, comegia rilevato per il primo metodo, potrebbe pero richiedere relativamente moltotempo.

Un’altra opzione per tentare di ridurre la distanza massima tra i robot,ottenibile al raggiungimento del rendezvous pratico, potrebbe consistere nel-lo sfruttare la memoria dei processi a bordo dei veicoli. Si potrebbe teneretraccia, ad esempio, nel generico robot ri degli ultimi m obiettivi calcolati:ci(ti,k), ci(ti,k−1), . . . , ci(ti,k−m+1). Se questi risultassero “vicini” l’uno all’altrosi potrebbe rilevare il fatto che il robot ri si sta muovendo attorno ad uno stes-so punto. Un’euristica possibile, a questo punto, potrebbe consistere nel farmuovere l’agente ri verso il punto medio degli ultimi m centri calcolati e quin-

94

di fermarlo, anziche seguire normalmente l’algoritmo originale che porterebbead un ciclo limite senza fine. L’idea e che il punto medio degli ultimi centricalcolati sara prossimo per tutti i robot, che ruotano in una regione quasi cir-colare, come e evidente dall’ultimo grafico in figura 3.8. Ovviamente, e difficiledare una dimostrazione dell’efficacia di questo approccio e darne una stima delleprestazioni. La taratura di m e la scelta del criterio con il quale si stabilisce checi(ti,k), ci(ti,k−1), . . . , ci(ti,k−m+1) sono sufficientemente “vicini” dovrebbe esserecondotta su base empirica.

Le precedenti considerazioni mostrano che il problema del rendezvous di ve-icoli di Dubins e ancora aperto. La soluzione proposta puo essere soddisfacentese l’intorno in cui i veicoli devono pervenire ha raggio maggiore di 2rmin e lesue prestazioni possono essere ulteriormente migliorate facendo ricorso al primometodo o a delle euristiche che sfruttino la memorizzazione degli ultimi obiettivicalcolati. Il suo difetto e forse quello di non offrire una soluzione unitaria alproblema, ma di richiedere invece il cambiamento della strategia del rendezvous.D’altro canto ogni algoritmo di rendezvous per macchine di Dubins non puo nonscontrarsi con l’aumentare della difficolta di manovra dei veicoli mano a manoche gli spazi si restringono.

Il difetto principale dell’algoritmo proposto, derivante dall’aver seguito l’ap-proccio adottato in [3], consiste nel non considerare esplicitamente le collisionimutue tra veicoli, delegandole a routine locali da chiamare solamente quando iveicoli si trovino troppo vicini. Le collisioni non vengono considerate al momen-to della pianificazione della traiettoria, come invece accade per tecniche basatesui potenziali artificiali [33] [18]. Queste tecniche, seppure si prestano al coordi-namento di molteplici veicoli mobili considerando esplicitamente la necessita dievitare le collisioni, sono difficilmente adattabili a macchine di Dubins, a causadel limite sul minimo raggio di curvatura.

Il coordinamento di molteplici veicoli mobili non controllabili in tempo brevee di macchine di Dubins, in particolare, e dunque un problema aperto. Lasua soluzione e un primo passo verso applicazioni che prevedano una strettacooperazione di gruppi di robot autonomi.

95

96

Appendice A

Cenni sui gruppi e le algebre diLie

Quest’appendice si propone di definire i concetti di gruppo di Lie e di algebra diLie, fornendo alcuni esempi richiamati nella tesi. Per una trattazione approfondi-ta degli argomenti, qui solo accennati, si rimanda a testi di matematica specifici,come [1].

Si comincia col richiamare il concetto generale di gruppo.

Definizione A.1. Sia G un insieme sul quale e definita una legge di compo-sizione interna ′′·′′:

G × G → G(a, b) 7→ a · b.

Si dice che G e un gruppo rispetto a ′′·′′ se tale legge verifica le seguenti proprieta:

1. e associativa: (a · b) · c = a · (b · c) ∀a, b, c ∈ G;

2. ammette elemento neutro: ∃ e ∈ G : a · e = e · a = a ∀a ∈ G;

3. ogni elemento ammette simmetrico: ∀a ∈ G ∃ a′ ∈ G : a · a′ = a′ ·a = e.

Si usa indicare l’elemento simmetrico di a con a−1.

Definizione A.2. Un gruppo G si dice di Lie, se G e munito della strutturadi varieta differenziabile compatibile con la legge di composizione interna delgruppo, cioe se applicazioni

G × G → G; (a, b) 7→ a · bG → G; a 7→ a−1

sono differenziabili.

97

Si chiarisce la definizione precedente con alcuni esempi di gruppi di Lie di par-ticolare interesse per la teoria del controllo di veicoli mobili. Sono gruppi do Lie:lo spazio euclideo Rn munito di addizione, lo spazio dei numeri reali R munito dimoltiplicazione, il gruppo del cerchio S1, ovvero l’insieme dei numeri complessi dimodulo unitario, munito di moltiplicazione, il gruppo lineare generale GL(n,R),cioe l’insieme delle matrici reali di dimensione n× n invertibili, munito del con-sueto prodotto matriciale e il gruppo lineare speciale SL(n,R), ovvero l’insiemedelle matrici reali con determinante uguale a uno, anch’esso munito del consuetoprodotto matriciale.

Ad ogni gruppo di Lie si puo associare, in grado di esprimere interamente lastruttura locale del gruppo.

Definizione A.3. Un’algebra di Lie e una struttura costituita da uno spaziovettoriale g su un certo campo F e da un operatore binario [·, ·] : g × g → g

detto parentesi di Lie (in inglese, Lie bracket) che soddisfa le seguenti proprieta:

1. e bilineare, cioe [ax + by, z] = a[x, z] + b[y, z] e [z, ax + by] = a[z, x] +b[z, y] ∀a, b ∈ F, ∀x, y, z ∈ g

2. soddisfa l’identita di Jacobi: [[x, y], z]+ [[y, z], x]+ [[z, x], y] = 0 ∀x, y, z ∈g

3. e nilpotente, cioe [x, x] = 0 ∀x ∈ g.

Si noti che la prima e la terza proprieta assieme implicano l’antisimmetria delleparentesi di Lie, cioe [x, y] = −[y, x] ∀x, y ∈ g. In generale, invece, l’operazionedi parentesi di Lie non e associativa, cioe [[x, y], z] non e necessariamente ugualea [x, [y, z]].

Ad esempio, ogni spazio vettoriale dotato di parentesi di Lie identicamentenulle e, banalmente, un’algebra di Lie. Lo spazio euclideo tridimensionale R3,con parentesi di Lie data dal prodotto vettoriale, e un’algebra di Lie. L’algebradi Lie del gruppo lineare generale GL(n,R) e lo spazio vettoriale delle matriciquadrate Mn(R) con parentesi di Lie data da [A,B] = AB −BA.

I concetti gruppo e di algebra di Lie sono intimamente legati. I gruppi di Liepossono essere pensati come famiglie di simmetrie che variano in maniera regolare(in inglese, smooth). Esempi di simmetrie sono le traslazioni e le rotazioni at-torno ad un asse. Poiche i gruppi di Lie sono delle varieta, possono essere studiatiutilizzando il calcolo differenziale. Una delle idee di base nello studio dei gruppidi Lie, e quella di sostituire l’oggetto globale, il gruppo, con la sua contropartelocale o linearizzata, che lo stesso Sophus Lie chiamo gruppo infinitesimale, eche dopo di lui divenne nota con il nome di algebra di Lie. L’algebra di Lie ecostituita dallo spazio vettoriale tangente G nell’elemento identita. In manieraeuristica si puo pensare all’algebra di Lie come all’insieme di elementi del grup-po infinitesimalmente vicini all’identita e dotato di un’operazione binaria, dettaparentesi di Lie.

98

Ciascun gruppo di Lie definisce un’algebra di Lie g = Lie(G) associata. Ladefinizione generale e piuttosto tecnica e sara qui omessa. Nel caso di gruppi dimatrici, puo essere formulata utilizzando l’esponenziale matriciale.

Definizione A.4. L’algebra di Lie g associata al gruppo di Lie matriciale G el’insieme di tutte le matrici X tali per cui exp(tX) ∈ G ∀t ∈ R, con parentesi diLie date dal commutatore [X, Y ] = XY − Y X.

Ad esempio, si prenda il gruppo lineare speciale SL(n,R), che contiene lematrici ad elementi reali con determinante pari a uno. Si e gia detto che questoe un gruppo di Lie matriciale; l’algebra di Lie associata e data dall’insieme dellematrici reali n × n con traccia nulla. In particolare si consideri l’insieme dellematrici di traccia nulla g = {ξ(ϕ, θ)|ϕ, θ ∈ S1}, dove

ξ(ϕ, θ) =

0 −ϕ v cos θϕ 0 v sin θ0 0 0

,

l’applicazione esponenziale t 7→ exp(tξ(ϕ, θ)) associa a ξ(ϕ, θ) la matrice

g(t) = exp(ξt) =

cos ϕt − sin ϕt 2vϕ

cos(θ + ϕt2) sin( ϕt

2)

sin ϕt cos ϕt 2vϕ

sin(θ + ϕt2) sin( ϕt

2)

0 0 1

.

Si vede dunque che l’applicazione esponenziale associa all’algebra di Lie g ilgruppo di Lie G = {g(t) = exp(tξ)| ξ ∈ g, t ∈ R}. G e un sottogruppo diSL(n,R) e puo scriversi anche come

G =

{(R p0 1

)∣∣∣∣ R ∈ SO(2), p ∈ R2

}

dove SO(2) e l’insieme delle matrici di rotazione sul piano. G e omeomorfo allospazio euclideo speciale SE(2): si puo dunque identificare G = SE(2) e g = se(2).Il gruppo di Lie SE(2) e l’algebra di Lie associata se(2) sono di particolare utilitaper lo studio delle simmetrie nel caso di veicoli mobili sul piano e sono piu volteutilizzate in questa tesi. Al di la di quest’esempio particolare, il formalismo deigruppi e delle algebre di Lie fornisce lo strumento matematico piu potente egenerale per lo studio delle simmetrie di sistemi differenziali arbitrari.

99

100

Bibliografia

[1] E. Abbena, S. Console, and S. Garbiero. Gruppi diLie. Dipartimento di Matematica, Universita di Torino,www.dm.unito.it/personalpages/fino/gruppidilie-04-05.html edition, 1990.

[2] Y. Altshuler, A.M. Bruckstein, and I.A. Wagner. Swarm robotics for adynamic cleaning problem. IEEE Swarm Intelligence Symposium, June2005.

[3] H. Ando, Y. Oasa, I. Suzuki, and M. Yamashita. Distributed memorylesspoint convergence algorithm for mobile robots with limited visibility. IEEETrans. on Robotics and Automation, 15(5):818 – 828, Oct. 1999.

[4] H. Ando, I. Suzuki, and M. Yamashita. Formation and agreement problemsfor synchronous mobile robots with limited visibility. IEEE Int. Symp. onIntelligent Control, 1995.

[5] A. Balluchi, A. Bicchi, A. Balestrino, and G.Casalino. Path tracking con-trol for dubin’s cars. IEEE International Conference on Robotics andAutomation.

[6] A. Balluchi, A. Bicchi, and P. Soueres. Path-following with a bounded-curvature vehicle: a hybrid control approach. Roma, Italy, Mar. 2001. 4thInternational Workshop HSCC.

[7] A. Balluchi, P. Soueres, and A. Bicchi. Hybrid feedback control for pathtracking with a bounded-curvature vehicle. Roma, Italy, Mar. 2001. 4thInternational Workshop HSCC.

[8] F. Belkhouche and B. Belkhouche. A control strategy for tracking-interception of moving objects using wheeled mobile robots. Atlantis, Par-adise Island, Bahamas, Dec. 2004. 43rd IEEE Conference on Decision andControl.

[9] A. Bicchi, G. Casalino, and C. Santilli. Planning shortest bounded-curvaturepaths for a class of nonholonomic vehicles among obstacles. volume 2, pages1349 – 1354. IEEE Int. Conference on Robotics and Automation, May 1995.

101

[10] A. Bicchi and L. Pallottino. Optimal planning for coordinated vehicleswith bounded curvature. In Algorithmic and Computational Robotics: NewDirections, pages 181 – 189, Hanover, NH, 2000.

[11] R.W. Brockett. Asymptotic stability and feedback stabilization. InDifferential Geometric Control Theory, 1983.

[12] X.-N. Bui, P. Soueres, J.-D. Boissonnat, and J.-P. Laumond. The shortestpath synthesis for non-holonomic robots moving forwards. Technical Re-port 2153, INRIA, Domaine de Voluceau, Rocquencourt, 78153 Le ChesnayCedex, France, Dec. 1993.

[13] E.F. Camacho and C.Bordons. Model Predictive Control. Springer, 1998.

[14] S. Capkun, M. Hamdi, and J.P. Hubaux. Gps-free positioning in mobilead hoc networks. In Proceedings of the 34th Annual Hawaii InternationalConference on System Sciences. IEEE, Jan. 2001.

[15] R. Cassinis, G. Bianco, A. Cavagnini, and P. Ransenigo. Strategies for navi-gation of robot swarms to be used in landmines detection. In Advanced Mo-bile Robots, 1999. (Eurobot ’99) 1999 Third European Workshop on, pages211–218, Zurich, Switzerland, Sep. 1999. IEEE.

[16] N. Correll, C. Cianci, X. Raemy, and A. Martinoli. Self-organized em-bedded sensor/actuator networks for “smart” turbines. Beijing, China,Oct. 2006. IEEE/RSJ International Conference on Intelligent Robots andSystems Workshop on Network Robot System: Toward intelligent roboticsystems integrated with environments.

[17] N. Correll, S. Rutishauser, and A. Martinoli. Comparing CoordinationSchemes for Miniature Robotic Swarms: A Case Study in Boundary Cover-age of Regular Structures. In The 10th International Symposium on Exper-imental Robotics (ISER), Springer Tracts in Advanced Robotics, to appear,2006.

[18] D.V. Dimarogonas and K.J. Kyriakopoulos. On the rendezvous problemfor multiple nonholonomic agents. IEEE Trans. On Automatic Control,52(5):916 – 922, May 2007.

[19] L. E. Dubins. On curves of minimal length with a constraint on averagecurvature, and with prescribed initial and terminal positions and tangents.American Journal of Mathematics, (3), July 1957.

[20] M. Fischietti. Lezioni di Ricerca Operativa. Libreria Progetto, Padova, iiedition, 1999.

102

[21] E. Frazzoli, M.A. Dahleh, and E. Feron. Robust hybrid control for au-tonomous vehicle motion planning. Sydney, Australia, Dec. 2000. 39th IEEEConference on Decision and Control.

[22] E. Frazzoli, M.A. Dahleh, and E. Feron. Real-time motion planning foragile autonomous vehicles. Journal of Guidance, Control, and Dynamics,25(1):116–129, 2002.

[23] E. Frazzoli, M.A. Dahleh, and E. Feron. Maneuver-based motion plan-ning for nonlinear systems with symmetries. IEEE Trans. on Robotics,21(6):1077–1091, Dec. 2005.

[24] J. Fredslund and M.J. Mataric. A general algorithm for robot formationsusing local sensing and minimal communication. IEEE Trans. on Roboticsand Automation, 18(5):837– 846, Oct. 2002.

[25] B.P. Gerkey and M.J. Mataric. Pusher-watcher: An approach to fault-tolerant tightly-coupled robot coordination. IEEE Intl. Conference onRobotics and Automation, May 2002.

[26] A.T. Hayes, A. Martinoli, and R.M. Goodman. Swarm robotic odor localiza-tion. In Proceedings on IEEE/RSJ International Conference on IntelligentRobots and Systems, volume 2, pages 1073–1078, Maui, HI, USA, Nov. 2001.

[27] S. Hettiarachchi and W. Spears. Moving swarm formations through obstaclefields. IEEE International Conference on Artificial Intelligence, 2005.

[28] A. Howard, M.J. Mataric, and G.S. Sukhatme. An incremental self-deployment algorithm for mobile sensor networks. In Autonomous Robots,Special Issue on Intelligent Embedded Systems, volume 13 of 2, pages 113 –126. Kluwer Academic Publishers, Sept. 2002.

[29] P. Jacobs and J. Canny. Planning smooth paths for mobile robots. Scotts-dale, AZ, USA, May 1989. IEEE International Conference on Robotics andAutomation.

[30] P. Jacobs and J. Canny. Robust motion planning. Cincinnati, OH, USA,May 1990. IEEE International Conference on Robotics and Automation.

[31] F. Lamiraux and J.P. Laumond. Smooth motion planning for car-like ve-hicles. IEEE Trans. on Robotics and Automation, 17(4):498–501, Aug.2001.

[32] Z. Lin, B. Francis, and M. Maggiore. Necessary and sufficient graphical con-ditions for formation control of unicycles. IEEE Transactions on AutomaticControl, 50(1):121– 127, Jan. 2005.

103

[33] Z. Lin, B. Francis, and M. Maggiore. Getting mobile autonomous robots torendezvous. Conference on Control of uncertain systems, 2006.

[34] T. Lozano-Perez and M.A. Wesley. An algorithm for planning collision-freepaths among polyhedral obstacles. Communications of the ACM, 22(10):560– 570, Oct. 1979.

[35] J. McLurkin and J. Smith. Distributed algorithms for dispersion in indoorenvironments using a swarm of autonomous mobile robots. 7th InternationalSymposium on Distributed Autonomous Robotic Systems, 2004.

[36] B. Mirtich and J. Canny. Using skeletons for nonholonomic path planningamong obstacles. Nice, France, May 1992. IEEE International Conferenceon Robotics and Automation.

[37] P. Morin and C. Samson. Practical stabilization of drifless systems onlie groups: The transverse function approach. IEEE Trans. on AutomaticControl, 48(9):1496–1508, Sept 2003.

[38] P. Morin and C. Samson. Trajectory tracking for non-holonomic vehicles:Overview and case study. Fourth International Workshop on Robot Motionand Control, June 2004.

[39] M. Caregaro Negrin, A. Nicolettis, P. Pucci, and L. Schenato. Very-low sam-pling rate control of wheeled mobile robots using circles. Technical report,Department of Information Engineering, University of Padova, 2006.

[40] R. Olfati-Saber. Flocking of multi-agent dynamic systems: Algorithms andtheory. IEEE Trans. on Automatic Control, 51(3):401 – 420, Mar. 2006.

[41] J. Oomen. An efficient geometric solution to the minimum spanning circleproblem. Operation Research, 35(1):80–86, Jan. - Feb. 1987.

[42] A. Panousopoulou, E. Kolyvas, Y. Koveos, A. Tzes, and J. Lygeros. Robot-assisted target localization using a cooperative scheme relying on wirelesssensor networks. In Proceedings of the 45th IEEE Conference on Decisionand Control, pages 1031 – 1036, San Diego, CA, USA, Dec. 2006.

[43] L.E. Parker. Current state of the art in distributed autonomous mobilerobotics. In G. Bekey L. E. Parker and J. Barhen, editors, DistributedAutonomous Robotic Systems 4, pages 3–12, Tokyo, 2000. Springer-Verlag.

[44] Y.-Q. Qin, D.-B. Sun, N. Li, and Y.-G. Cen. Path planning for mobilerobot using the particle swarm optimization with mutation operator. Shang-hai, China, Aug. 2004. Proceedings of the 3rd International Conference ofMachine Learning and Cybernetics.

104

[45] J. A. Reeds and L. A. Shepp. Optimal paths for a car that goes bothforwards and backwards. Pacific Journal of Mathematics, (145):367–393,1990.

[46] R.Gross, M. Bonani, F. Mondada, and M. Dorigo. Autonomous self-assembly in swarm-bots. Technical Report TR/IRIDIA/2005-002, IRIDIA,Bruxelles, Luxemburg, May 2006.

[47] C. Samson and K. Ait-Abderrahim. Mobile robot control part 1: Feedbackcontrol of a nonholonomic wheeled car in cartesian space. Technical Re-port 1288, INRIA, Domaine de Voluceau, Rocquencourt, 78153 Le ChesnayCedex, France, Oct. 1990.

[48] S. Samuel and S. Sathiya Keerthi. Numerical determination of optimal non-holonomic paths in the presence of obstacles. IEEE International Conferenceon Robotics and Automation, 1993.

[49] K. Savla, E. Frazzoli, and F. Bullo. On the point-to-point and travelingsalesperson problems for dubins’ vehicle. Portland, OR, USA, June 2005.American Control Conference.

[50] A. Scheuer and C. Laugier. Planning sub-optimal and continuous-curvaturepaths for car-like robots. Victoria, B. C., Canada, Oct. 1998. IEEE/RSJIntl. Conference on Intelligent Robots and Systems.

[51] H. J. Sussmann and G. Tang. Shortest paths for the reeds-shepp car: Aworked out example of the use of geometric techniques in nonlinear opti-mal control. Technical Report SYCON-91-10, Department of Mathematics,Rutgers University, New Brunswick, NJ 08903, Sept. 1991.

[52] V. Trianni, E. Tuci, and M. Dorigo. Evolving functional self-assemblingin a swarm of autonomous robots. Technical Report TR/IRIDIA/2004-21,IRIDIA, Bruxelles, Luxemburg, July 2004.

[53] M. Vendittelli, J.-P. Laumond, and C. Nissoux. Obstacle distance for car-like robots. IEEE Trans. on Robotics and Automation, 15(4):678–691, Aug.1999.

[54] A.F.T. Winfield, C.J. Harper, and J. Nembrini. Towards dependable swarmsand a new discipline of swarm engineering. In E. Sahin and W.M. Spears,editors, Swarm Robotic WS 2004, number LNCS 3342, pages 126 – 142.Springer - Verlag, Berlin Heidelberg, 2005.

[55] A.F.T. Winfield, C.J. Harper, and J. Nembrini. Towards the applicationof swarm intelligence in safety critical systems. www.ias.uwe.ac.uk/ a-winfie/WinHarNemISSC06.pdf, 2006.

105

[56] S. Xu, R.M. Freund, and J. Sun. Solution methodologies for the smallestenclosing circle problem. Computational Optimization and Applications,25(1-3):283–292, Apr. 2003.

106