Tecnica di Guida innovativa in ambiente con ostacoli

Corso di Laurea Magistrale in Robotica e dell’Automazione

Tesi di laurea magistrale

Guida innovativa in ambiente con ostacoli

Relatore: Lorenzo Pollini Correlatore: Mario Innocenti Candidato: Matteo Mammoliti Matricola 411915 Anno Accademico 2013–2014

1. Descrizione del problema . . . 4

2. Guida con Visibilità . . . 5

2.1 Descrizione della Visibilità . . . 5

2.2 Legge di Guida . . . 8

2.2.1 PNG . . . 8

2.2.2 Contributo di Visibilità . . . 13

3. Implementazione . . . 14

3.1 Calcolo della Variazione di Visibilità . . . 14

3.1.1 Regione di Valutazione . . . 14

3.1.2 Inversione del campo . . . 15

3.2 Raggio . . . 18 3.3 Diametro . . . 20 3.4 Raggio incrementale . . . 21 3.5 Composizione accelerazioni . . . 22 3.6 Correzione di O Heading . . . 24 4. Simulazioni . . . 35

4.1 Descrizione dello scenario . . . 35

4.2 Target . . . 37

4.3 Scenari . . . 39

4.3.1 Intercettazione . . . 39

4.3.2 Ricerca del target . . . 44

4.3.3 Due target . . . 46

4.3.4 Due Pursuer . . . 49

5. Giochi dierenziali . . . 52

5.1 Pursuit-Evasion Game . . . 53

5.2 PNG come pursuit-evasion game . . . 57

5.2.1 Stato del gioco ZEM . . . 57

5.2.2 Stato del gioco posizioni e velocità . . . 67

Appendice 87 A. Algoritmo di ricerca delle intersezioni . . . 88

L'obiettivo di questo testo è di sviluppare una guida intercept capace di agi-re in ambiente con ostacoli senza aver bisogno di pianicaagi-re a priori delle traiettorie per evitare le insidie dello scenario. L'idea di base utilizzata per raggiungere quanto richiesto è quella di comporre insieme due guide, una che realizzi il task di intercettazione ed un'altra che operi per evitare le collisioni con gli ostacoli avendo conoscenza solo della posizione degli agenti in gioco e della posizione degli ostacoli. Come guida intercept è stata scelta la Pro-portional Navigation Guidance (PNG); questa guida è nota in letteratura e molto usata per la sua semplicità di implementazione e per la grande quanti-tà di varianti esistente. La versione che andremo ad utilizzare è quella in cui le accelerazioni vengono fornite perpendicolari al vettore velocità del veicolo (PNG Pure) non producendo cosi modiche al modulo di tale quantità. Per svolgere il compito di evitare gli ostacoli e mantenere il target in line of sight (LOS) viene costruita una guida basata sulla visibilità ovvero, denito un livello di tale visibilità in base a delle caratterizzazioni che spiegheremo in seguito, viene stabilità una stima della probabilità di migliorare o meno tale livello in base alle traiettorie possibili da intraprendere. Una volta scelta la traiettoria che mi permette di rendere massimo il valore della visibilità atteso al prossimo istante di valutazione questa viene tradotta in una accelerazione perpendicolare al vettore velocità del vicolo e verrà composta con quella che viene data in uscita dalla PNG. Se le due componenti sono state bilancia-te correttamenbilancia-te tale guida raggiunge l'inbilancia-tercettazione evitando gli ostacoli nello scenario.

Una volta denito il metodo per ricercare i massimi livelli di visibilità ad ogni passo con piccole modiche la guida può essere applicata per compiere una ricerca del target avendo solo una informazione sommaria sulla zona di scenario in cui è locato. Tale informazione può essere fornita da un agente terzo oppure può essere stimata tramite posizioni passate del target e la conoscenza delle sue capacità di manovra.

In aggiunta si è provato a dare una formalizzazione matematica all pro-blema sfruttando la teoria dei giochi dierenziali applicata al propro-blema di Pursuit-Evasion come fatto da Bryson ed Ho per dimostrare l'ottimalità della PNG [2].

In letteratura sono presenti molte guide di tipo intercept ovvero guide utili per comandare i movimenti di un veicolo all'inseguimento di un target che può essere sso, mobile più o meno intelligente. La maggior parte di queste guide però è denita per ambienti privi di ostacoli in cui non sono presenti vincoli sulle posizioni raggiungibili dai veicoli in gioco. Il nostro obiettivo è di modicare una di queste guide in modo da renderla funzionante anche in questo tipo di ambienti. Il metodo che si vuole utilizzare non sfrutta metodi di pianicazione a priori o altri artici come inserimento di forze ttizie respingenti in prossimità degli ostacoli. Il concetto che viene denito in questo testo, e che si andrà a sfruttare per denire una componente di guida da sommare alle guide intercept classiche, è quello della visibilità.

2.1 Descrizione della Visibilità

La visibilità può essere vista come una misura di quanto lo spazio tra l'os-servatore e l'osservato è libero da ostacoli; tale valore non sarà lo stesso se scambio i compiti dei due agenti in quanto lo sazio di stato libero da ostacoli visto dal target è diverso da quello del pursuer per errori di parallasse. Oc-corre però denire un metodo matematico per calcolare tale valore; il modo più semplice ed intuitivo di cercarne una formalizzazione è quello di fornirne una caratterizzazione booleana ovvero considerando tale livello pari ad 1 se la LOS tra chi guarda e l'oggetto è libera oppure 0 se intercetta ostacoli. Questa scelta non è però particolarmente interessante al ne di costruire la guida che ci siamo preposti, infatti, la quantità di informazione che ne deriva è scarsa a causa del passaggio tra 0 ed 1 in maniera discontinua.

Fig. 2.1: Mappa di visibilità booleana

In gura 2.1 viene mostrato un possibile scenario in cui viene denita la posizione dell'oggetto da osservare e vengono tracciate in verde le possibi-li LOS in cui l'osservatore avrebbe vista possibi-libera sull'oggetto mentre in rosso quelle in cui l'oggetto è oscurato da un ostacolo; viene anche riportata una visione tridimensionale della mappa generata dalla quale è evidente come questo tipo di denizione produca una funzione di visibilità fortemente di-scontinua e quindi di dicile utilizzo per denire gradienti di crescita di tale quantità. Per riuscire a limitare i problemi descritti in precedenza, in parti-colare per rendere la funzione che caratterizzi il livello di visibilità continua e permettergli di fornire una descrizione più ricca del suo andamento risulta utile delimitare una regione intorno al target nel quale viene denita la pro-babilità di avere il target in vista come se fosse presente un'incertezza sulla sua eettiva posizione. Tale incertezza può essere eettivamente presente, in uno scenario reale, oppure delimitata arbitrariamente su informazioni note in modo perfetto. Per scenari particolarmente complessi la probabilità di cui stiamo parlando potrebbe essere modicata in base al problema che stiamo cercando di risolvere o in base alle eettive descrizioni che abbiamo della posizione del target. In questo testo, per semplicità, essa viene descritta in ogni caso possibile come una gaussiana bi-variabile con valore nominale la posizione del target.

fT(x, y) = 1 σXσY2π e− (x−xT )2 2σ2 X −(y−yT )2 2σ2 Y (2.1)

dove σX e σY sono le deviazioni standard lungo gli assi rispettivamente delle

ascisse e delle ordinate mentre xT ed yT descrivono la posizione nominale del

target che se le informazioni in possesso sono corrette è anche quella esatta. Utilizzando la densità di probabilità fT è possibile costruire una funzione che

dipenda dalla porzione della regione di incertezza sulla quale il pursuer è in grado di avere una LOS priva di ostacoli. Considerando il caso planare si può scrivere la probabilità di avere il target in vista come

pT ν(¯x,y) =¯

Z Z

D

fT(x, y)fLOS(¯x,y, x, y¯ )dxdy (2.2)

con D dominio della funzione, ¯x ed ¯y coordinate del veicolo osservatore tali che (¯x, ¯y) ∈ D ed fLOS denita come funzione binaria che ritorna un valore

1 se la LOS tra il punto di coordinate (x, y) e quello di coordinate (¯x, ¯y) è priva di ostacoli 0 se invece tale retta ha punti di contatto con gli ostacoli dello scenario. Questa è la formulazione continua di tale elemento che in simulazione e quindi in un ambiente digitale viene discretizzata in

pT ν(¯x,y) =¯

X

(x,y)∈I

fT(x, y)fLOS(¯x,y, x, y)¯ (2.3)

dove I è un intorno circolare centrato nella posizione del target (xT, yT), in

particolare I = I((xT, yT), 3σ) = {(x, y) : dist((x, y), (xT, yT)) ≤ 3σ}.

Fig. 2.2: Mappa di visibilità con incertezza

In gura 2.2 viene riportato lo stesso scenario precedente sul quale viene denita la regione di incertezza (la circonferenza formata da puntini rossi) è possibile disegnare come varia il livello di visibilità in funzione delle possibili posizioni nello spazio. I contorni disegnati rappresentano zone iso-potenziali ovvero zone in cui il livello di visibilità è lo stesso da cui risulta evidente come la maggior parte dello scenario rimanga caratterizzato da zone in cui il valore del livello di visibilità è nullo o massimo ma è altrettanto visibile come il passaggio tra queste due tipologie di zone, che in precedenza avveniva in modo discontinuo, avviene attraverso un scala di valori che si susseguono in

modo più veloce o lento a seconda della disposizione del target rispetto agli ostacoli. Questa dierenziazione dei valori, che viene enfatizzata anche nella visione 3D della stessa mappa, permette in anzi tutto di assicurare l'elimi-nazione delle discontinuità della funzione visibilità che erano presenti nella formalizzazione booleana ma soprattutto di denire delle zone con gradienti di variazione della visibilità che in seguito verranno utilizzati per denire le caratteristiche del contributo di visibilità della nostra guida.

2.2 Legge di Guida

Passiamo ora a denire in maniera pratica le parti che comporranno le leggi di guida che utilizzeremo. Come già detto in precedenza si utilizza come legge di guida base una PNG in particolare si sceglierà una Pure PNG ovvero una delle tante varianti presenti in letteratura in cui il comando di accelerazione è perpendicolare alla velocità eettiva del veicolo.

Fig. 2.3: Scenario PNG

Si è scelto di utilizzare questo tipo di guida per la sua semplicità di imple-mentazione infatti tale comando lascia costante il modulo della velocità del veicolo ed agisce solamente sulla direzione del vettore della velocità. In gura 2.3 è rappresentato lo scenario relativo al problema corrente con espressi gli angoli, le velocità e le accelerazioni del sistema. Il comando generato è pro-porzionale alla Los Rate ˙σ che è la variazione dell'angolo che la line of sight

(LOS, ovvero la retta congiungente il target al pursuer) forma con l'asse x del frame sso scelto, alla Closing Velocity Vc cioè la velocità relativa tra

i due veicoli, ed ad un parametro N che caratterizza la capacità di manovra del target rispetto a quella del pursuer e viene denito come

N = 3

1 − cp

ct

(2.4) con cp capacità di manovra del pursuer e ctcapacità di manovra del target. I

valori tipici di N sono compresi tra 3 e 5 in cui 3 rappresenta un target inca-pace di eettuare manovre mentre 5 esprime la presenza di un target cainca-pace di eettuare tentativi di evasione. La forma in cui appare tale accelerazione sarà dunque quella classica

Apng = N Vc˙σ (2.5)

Nella nostra interpretazioni la Closing Velocity viene calcolata a partire dalle componenti della velocità e della posizione degli agenti in gioco perciò de-nendo rped rt come le posizioni dei due agenti mentre vp e vt le loro velocità

posso denire

Vc= − ˙R= −

∆(x)∆(Vx) + ∆(y)∆(Vy)

R (2.6)

in cui ∆(x) = rpx− rex e ∆(y) = rpy− rey sono le componenti cartesiane della

distanza tra i due veicoli mentre ∆(Vx) = vpx− vex e ∆(Vy) = vpy− vey sono

le componenti della dierenza di velocità dei due veicoli.

Sempre utilizzando le componenti di velocità e posizione dei due veicoli si può denire anche la Los Rate in maniera semplice

˙σ = ∆(Vy)∆(x) − ∆(Vx)∆(y)

R2 (2.7)

Simulazioni

Vengono riportate di seguito alcune simulazioni per mostrare il comporta-mento dei due agenti quando su di essi è montata una guida Pure PNG. Nelle gure che seguono verranno riportate le traiettorie del pursuer in blu mentre quelle dell'evader in rosso

Fig. 2.4: Andamento dello scenario

La presenza della closing velocity nelle equazioni fa si che le accelerazioni siano molto più intense ad inizio simulazione piuttosto che al termine in cui vanno ad annullarsi. Nella gura seguente sono descritti gli andamenti delle accelerazioni dei due veicoli; il pursuer (a sinistra) ha una capacita di manovra più elevata rispetto al target (a destra) infatti l'intensità massima riporta queste dierenze.

Fig. 2.5: Accelerazione di pursuer e target

Il modulo delle velocità dei due veicoli non varia durante tutto lo scenario ma questo risultato è ovvio visto che l'accelerazione comandata è perpendi-colare al vettore velocità.

Fig. 2.6: Velocità di pursuer e target

Proviamo a far partire gli agenti da una condizione iniziale più sfavorevole per il pursuer per capire come si modica il comportamento al variare dello stato di partenza.

Fig. 2.7: Andamento dello scenario

Possiamo notare come la accelerazioni dei due veicoli si comportino in maniera molto simile al caso precedenti e che le intensità dei controlli risul-tano maggiori rispetto al caso precedente a causa dei maggiori valori della Los Rate necessari per raggiungere l'orientazione corretta per inseguire il target.

Fig. 2.8: Accelerazione di pursuer e target

Per completezza vengono riportate anche le variazioni delle delle velocità che ovviamente avvengono in quanto a direzione e non in quanto a modulo.

2.2.2 Contributo di Visibilità

Deniamo il contributo che sfrutta il concetto di visibilità precedentemente espresso per modicare il comportamento della legge di guida base in modo da poterla utilizzare in ambiente con ostacoli avendo due obiettivi paralleli:

1. Mantenere alto il livello di visibilità e di conseguenza evitare gli ostacoli 2. Inseguire il target ed eettuare l'intercettazione

Per riuscire a garantire i due risultati occorrerà dunque per prima cosa li-berare la LOS sul target da ostacoli ed in seguito procedere con la guida intercept in modo da essere sicuri di evitare le collisioni. Il contributo che stiamo denendo dovrà essere fornito al veicolo sotto forma di accelerazione perpendicolare al vettore della velocità del veicolo stesso in modo da non farne variare il modulo. L'accelerazione che viene fornita all'agente ha un va-lore massimo rappresentato dal parametro Kvis che viene scelto in modo da

rendere tale accelerazione di intensità paragonabile a quella della PNG così da non far prevalere un contributo sull'altro quando entrambi sono attivi. L'accelerazione completa che viene fornita al veicolo è

Avis= Kvissin(γvis− γv) (2.8)

il fattore sin(γvis− γv) è di fatto la proiezione sull'asse perpendicolare alla

velocità dell'accelerazione di visibilità totale in cui appaiono γv, ovvero

l'an-golo che il vettore velocità forma con l'asse delle ascisse, e l'anl'an-golo γvis che è

la direzione che massimizza l'aumento di visibilità del veicolo.

Questa misura non può essere conosciuta a priori perciò si dovrà for-malizzare un metodo di stima di tale variazione al tempo t + 1 in base ad informazioni che sono reperibili al tempo t. Diversi modi vengono presi in considerazione in seguito col ne di trovarne uno che permetta di avere un calcolo del gradiente di variazione il più preciso possibile e che gestisca al meglio le zone problematiche (come per esempio le zone in cui non vi sono variazioni nell'intorno della posizione del veicolo).

3.1 Calcolo della Variazione di Visibilità

La nostra guida si basa sul tentativo di massimizzare la variazione di visibi-lità che il pursuer ha sull'evader. Questa in un ambiente continuo è denita chiaramente dal gradiente della funzione di visibilità descritta in (2.2); in que-sto modo l'angolo γvis che massimizza la variazione che appare nella formula

(2.8) viene scelto in modo da rendere la velocità del veicolo v(t) = ∂pT ν ∂r¯    ¯ r=rp(t) (3.1) dove ¯r è la posizione generica che può assumere il veicolo mentre rp è

l'ef-fettiva posizione del veicolo all'istante di valutazione. Lavorando in ambiente digitale però occorre stimare tramite valori dello spazio scelti in base carat-teristiche favorevoli al nostro problema poiché non è pensabile valutare ogni punto dello spazio di stato (inniti) per trovare il gradiente reale della fun-zione. Quindi per prima cosa si sfrutterà la denizione del livello di visibilità descritta in modo discreto come nella (2.3) per poi ricavarsi la variazione di visibilità che ci si aspetta di avere al tempo successivo sfruttando e misure che posso ricavare nel momento in cui sto valutando. Le sezioni che seguono servono a descrivere degli algoritmi utili a stimare le variazioni di visibilità attese e di conseguenza la miglior traiettoria da scegliere per rendere massima tale quantità risolvendo un problema discreto del tipo

M ax

r [pT ν(r) − pT ν(rv)] r ∈ B(rv, d) (3.2)

con B(rv, d) intorno circolare di centro la posizione del veicolo e raggio d

3.1.1 Regione di Valutazione

Occorre dunque denire la regione di valutazione su cui vogliamo eettuare l'eettiva stima della variazione ovvero descrivere in maniera chiara B(rv, d).

Come detto si sceglie un intorno circolare centrato nella posizione del pur-suer di raggio d, dove come misura d viene preso il percorso che il veicolo è in

grado di compiere tra una valutazione della visibilità e quella seguente. Una circonferenza come quella appena descritta è comunque formata da inniti punti; è necessario dunque sceglierne una collezione sucientemente infor-mativa in modo da discretizzare la scelta eettuata. Raccogliamo quindi 36 punti equidistanti tra loro in B(rv, d)sui quali viene valutato il livello di

vi-sibilità salvandolo in un vettore circolare vis_CirP oints che verrà utilizzato per eettuare le stime.

Fig. 3.1: Schema della regione di valutazione 3.1.2 Inversione del campo

Utilizzando il modo descritto no ad ora di denire il campo di visibilità si ha una perfetta conoscenza dello spazio intorno al veicolo quando abbiamo almeno parte di informazioni sulla visibilità rispetto al target poiché la pre-senza di ostacoli inuisce su tali informazioni; quando però il pursuer si trova in zone dove il livello di visibilità è nullo perdo completamente il riferimento sulla posizione degli ostacoli, visto che per la nostra denizione i punti dentro gli ostacoli e quelli nascosti da questi ultimi hanno la stesso livello di visibili-tà, procurando problemi nella ricerca di una guida utilizzabile in qualunque scenario compresi quelli a condizioni iniziali con scarso livello di visibilità.

Per eliminare tale problema, in fase di scelta delle traiettoria, alla mappa globale di visibilità vengono apportate alcune modiche a livello locale ovve-ro nell'intorno di valutazione che si sta utilizzando. Tale modica consiste nel lasciare invariato il calcolo della visibilità, perciò sia il valore della visibilità che il vettore dei possibili futuri livelli di visibilità non subisce modiche ma, per utilizzare in maniera più ricca l'informazione sul posizionamento degli ostacoli, che è nota al veicolo inseguitore, prima di eettuare la stima sulle variazioni di visibilità viene eettuato un controllo sull'eettiva possibilità di inseguire o meno una determinata traiettoria; si verica infatti se la LOS tra il centro del cerchio ed il punto della circonferenza sul quale si sta cal-colando la variazione intercetti ostacoli oppure no. Se la linea di vista sul punto considerato è libera si continua ad utilizzare il valore calcolato dalla mappa globale altrimenti, prima di eettuare la stima delle variazioni opero un'inversione del valore futuro, ovvero prendo il livello di visibilità del punto futuro che sto considerando con il segno negativo e vi sottraggo 1. In questo modo a tutte le traiettorie che porterebbero a scontrarsi con ostacoli vengono assegnati valori inferiori a −1.

Per chiarire meglio il concetto viene mostrato lo pseudo-codice relativo a tale modica:

my_vis = livello di visibilità del veicolo

vis_CirPoints [36] = vettore futuri livelli di visibilità if ([pos_v,new_pos_v[i]] senza ostacoli)

vis_dif[i] = vis_CirPoints[i] - my_vis else

vis_dif[i] = - vis_CirPoints[i] - 1 - my_vis end

la sottrazione di un valore unitario occorre per eliminare l'ambiguità nelle zone in cui la visibilità è univocamente nulla descritta in precedenza; infatti con tale sottrazione le direzioni che portano ad avvicinarsi ad un ostacolo, quando sono in prossimità di esso, vengono penalizzate rispetto a tutte le altre; questo permette di evitare gli ostacoli nel tentativo di ricercare un livello di visibilità diverso da 0.

Questa tecnica permette di evitare gli ostacoli; se è necessario per ragioni si sicurezza riguardo alla distanza di superamento degli ostacoli, è possibile pensare di penalizzare, in maniera più lieve che nei casi di traiettoria con ostacoli, anche le traiettorie vicine a quelle penalizzate nel caso precedente. Il problema per cui con alcuni metodi il veicolo supera gli ostacoli passando a distanze inferiori al metro rispetto agli spigoli nella maggior parte dei casi

è dovuto al fatto che la visibilità futura viene valutata in punti vicini tra loro ma, a causa delle penalizzazioni incluse, con valori molto diversi tra loro. Con il ne di fornire un margine di sicurezza è possibile pensare, tramite un aumento di complessità del codice riportato in precedenza, di aggiungere delle penalizzazioni aggiuntive alle traiettorie più vicine a quelle che intercettano ostacoli come nell'esempio che segue.

my_vis = livello di visibilità del veicolo

vis_CirPoints [36] = vettore futuri livelli di visibilità if ([pos_v,new_pos_v[i]] senza ostacoli)

vis_dif[i] = vis_dif[i] + vis_CirPoints[i] - my_vis else

vis_dif[i] = vis_dif[i] - vis_CirPoints[i] - 1 - my_vis vis_dif[i+1] = vis_dif[i+1] - 0.2

vis_dif[i-1] = vis_dif[i-1] - 0.2 vis_dif[i+2] = vis_dif[i+2] - 0.1 vis_dif[i-2] = vis_dif[i-2] - 0.1

Per essere sicuri che il vettore circolare vis_dif sia usato in maniera coerente ad ogni passo del ciclo bisognerà far attenzione ai valori nelle quadre in modo da non fargli puntare a zone di memoria esterne al vettore (esempio se i = 35 si avrebbe i + 1 = 36 valido ed i + 2 = 37 non valido perciò sarà necessario sostituirlo con i + 2 − 36 = 1 che punta al primo valore del vettore circolare ovvero quello dopo l'ultimo). Utilizzando tali penalizzazioni aggiuntive anche le traiettorie vicino agli ostacoli vengono considerate in modo meno vantaggioso, anche se in minima parte rispetto a quelle nelle zone adiacenti, ed il veicolo passerà ad una distanza più accettabile dagli ostacoli.

Il campo di visibilità risulterà diverso quando applicato per ricercare la traiettoria ottimale rispetto a come era in gura 2.2; appariranno infatti zo-ne con un livello locale di visibilità inferiore a zero come si può notare zo-nella visione tridimensionale di gura 3.2 mentre nel graco delle zone isopoten-ziali di visibilità di gura non presenza dierenze sostanisopoten-ziali da quello del caso precedente nelle zone esterne agli ostacoli, l'unica dierenza è che la pendenza delle zone di salita risulta addolcita rispetto ai casi precedenti; le vere dierenze si hanno negli aloni di livello fortemente inferiore allo zero che si generano intorno agli ostacoli.

Anche se apporta beneci in alcuni scenari bisogna stare attenti al fatto che le traiettorie a cui viene inserita una penalizzazione aggiuntiva debbano essere molto vicine tra loro altrimenti l'unico risultato che viene raggiunto è quello di allungare il tempo che occorre a raggiungere la condizione di intercetto. Tale chiarimento che sembra banale risulterà molto importante in seguito quando verranno deniti i metodi di stima della variazione di visibilità e quindi della scelta delle traiettorie ottime per il contributo di visibilità.

3.2 Raggio

Il modo più semplice di esprimere la stima della variazione di visibilità è quello di denire un intorno di punti in cui il veicolo potrà trovarsi al prossimo istante di valutazione, quindi, sulla regione di valutazione circolare di raggio 3m denita come esplicitato in precedenza. Una volta impostata tale regione viene calcolato il livello di visibilità al centro della circonferenza (ovvero il livello di visibilità attuale del pursuer) e il vettore in cui memorizzo il livello di visibilità che avrei se mi trovassi esattamente sul punto della circonferenza di valutazione che sto analizzando; la dierenza tra il valore attuale e i possibili valori futuri sarà la stima della variazione di visibilità che avrò scegliendo la direzione che unisce il centro della circonferenza con il punto sotto analisi. Con il ne di limitare la memoria utilizzata per salvare i possibili valori futuri di visibilità ed il numero di conti e confronti da eettuare viene scelto di valutare la circonferenza in 36 punti equidistanti tra loro, ovvero traiettorie distanti 10 gradi l'una dall'altra (che, con un cerchio di ampiezza 3m, equivale punti distanti circa 27cm). Esistono delle zone in cui non è possibile denire una direzione migliore delle altre e si ha quindi una ambiguità di scelta.

Fig. 3.3: Schema di Funzionamento del Metodo del Raggio

Questa scelta multipla possibile deve essere risolta secondo un qualche criterio che risulti univoco; la scelta fatta, visto che il nostro obbiettivo è raggiungere un target, è stata quella che permette di avvicinarsi il più pos-sibile all'obbiettivo. In poche parole tra le possibili traiettorie con punteggio massimo viene scelta quella relativa al punto della supercie di controllo più vicino al target. Occorre ora cercare di denire la bontà della correzione fat-ta; l'ambiguità di scelta può avvenire in tre zone: zona di piena visibilità su tutte le traiettorie scelta, zona con livelli di visibilità variegati sulla super-cie di controllo, zona di visibilità nulla su tutta la supersuper-cie di controllo. Se l'ambiguità avviene nella zona di piena visibilità idealmente qualunque scelta andrà bene perché l'idea di base è di dover utilizzare la PNG in tale zona e quindi il contributo sarà molto basso, idealmente nullo. Se siamo in zona mista la scelta di avvicinarsi al target per risolvere l'ambiguità risulta buona in quanto sfrutto il gradiente di visibilità per allontanarmi dagli ostacoli ma contemporaneamente cerco di avvicinarmi all'obbiettivo nale di intercettare il target. Nell'ultimo caso, ovvero quello in cui il veicolo si trovi in zona di visibilità nulla, la scelta fatta è sicuramente sbagliata; se sono in una zona di visibilità nulla sulla congiungente tra pursuer ed evader è presente sicura-mente un ostacolo che impedisce la visibilità, avvicinandosi al target quindi si andrà sicuramente in direzione di un ostacolo che verrà colpito prima di avere un qualunque aumento di visibilità.

3.3 Diametro

Utilizzando la stessa regione di valutazione del caso precedente possiamo calcolare la variazione di visibilità in un modo diverso con l'obiettivo di avere un gradiente più preciso. In questo caso non viene considerata la visibilità attuale ma viene calcolata la dierenza tra uno dei punti del cerchio e quello all'opposto del diametro passando per lo stesso punto considerato.

vis_dif[i] = vis_CirPoints[i] - vis_CirPoints[i+18]

Anche in questo caso occorrerà fare attenzione ai valori assoluti all'interno delle parentesi in modo da rendere il vettore circolare coerente ad ogni passo del ciclo. Di fatto eettuando questa scelta si fa una media delle direzioni di due passi consecutivi. In questo modo il risultato permetterà di avere un gradiente denito per ogni punto a dierenza del caso precedente in cui può capitare di avere ampi settori circolari con lo stesso punteggio.

Fig. 3.4: Schema di Funzionamento del Metodo del Diametro

Questo restrizione sugli spazi dello scenario occorre per evitare errori di traiettorie libere e con ostacoli che risultano a pari potenziale; infatti supponiamo di avere due ostacoli messi a formare un corridoio largo meno del diametro del cerchio e più lungo di esso, quando andremo a fare i calcoli

avremo le le due estremità dei diametri che non toccano ostacoli entrambe con livello di visibilità 0 mentre quelle che toccano ostacoli con livello -1; facendo le dierenze 0 − 0 e −1 − (−1) risultano entrambe nulle e si ha dunque un ambiguità di scelta In questo caso le penalizzazioni aggiuntive non portano miglioramenti sensati; le traiettorie con il metodo del diametro hanno già una forte spinta ad allontanarsi dagli ostacoli perciò non verranno presi in considerazioni altri aiuti a fuggire da essi

3.4 Raggio incrementale

Una evoluzione utile ad evitare i problemi che si hanno nelle zone in cui il gradiente è identicamente nullo è quella di far aumentare le dimensioni della circonferenza utilizzata per analizzare lo spazio intorno al veicolo in caso di assenza di variazioni nell'intorno considerato. Questo permette di scegliere una direzioni dove eettivamente sarà presente un guadagno sul livello di visibilità a lungo termine nelle zone in cui a breve non si hanno variazioni eettive. Per far questo occorre fare attenzione alla presenza o meno di osta-coli all'interno della circonferenza di controllo che tende ad ingrandirsi anche di molto nei casi in cui il target è ben nascosto; per scegliere una dimensione utile del raggio occorre non considerare nella stima della visibilità le traiet-torie che attraversano un ostacolo. Per riuscire a fare tale modica il primo controllo che si fa è sulla visibilità attuale del veicolo; se diversa da zero non si fanno modiche all'algoritmo, se invece tale visibilità è nulla modico il raggio considerato aumentandolo per svolgere la ricerca di valori utili per poi comportarmi nello stesso modo del primo caso studiato.

Occorre mettere due condizioni di uscita dal loop di ricerca di un raggio valido; una sul raggiungimento di un valore di visibilità futuro diverso da zero ed una sulla dimensione massima di aumento del raggio che serve a non far diventare il ciclo innito nei casi in cui non è possibile trovare valori di visibilità diversi da zero.

curr_vis = somma delle visibilità future; curr_vis = vis_lev;

while curr_vis == 0 && Raggio < distanza * 3 for j = d_ang:d_ang:2*pi

new_pos(1) = pos_v(1) + Raggio * cos(j); new_pos(2) = pos_v(2) + Raggio * sin(j);

if ([new_pos,pos_v] senza ostacoli)

curr_vis = curr_vis + vis_lev(new_pos); end end if curr_vis == 0 modifico il raggio end end

Utilizzando questa modica di fatto si può compiere una ricerca della mi-glior zona di approccio per l'inizio dell'ingaggio quando non sono in possesso di informazioni reali sulla posizione del target. Una volta trovata e raggiunta la posizione desiderata cominciare il task di intercettazione può essere uti-lizzato indistintamente il metodo del raggio o quello di diametro; la nostra scelta ricade su utilizzare il diametro per migliori margini di sicurezza rispet-to agli ostacoli e per la miglior denizione del gradiente. Quando siamo in condizioni di circonferenza allargata non è vantaggioso invece utilizzare tale metodo a causa della forte repulsione che questa porta sugli ostacoli; infatti ogni volta che verrà incontrato un ostacolo da una delle traiettorie in esame la traiettoria opposta risulterà essere quella migliore portando a allontanarsi in maniera troppo eccessiva dalla zone in cui è presente il target prima di riuscire a trovare una zona di attacco utile.

3.5 Composizione accelerazioni

Una volta denite tutte le accelerazioni in gioco occorre trovare una legge di composizione per utilizzare tutte le parti descritte in maniera concreta. Una buona scelta risulta già essere quella di sommare le due componenti in modo da avere la PNG nella sua forma completa mentre la parte di corre-zione di visibilità viene pesata per la variacorre-zione di visibilità teorica che tale accelerazione comporterebbe. L'accelerazione totale che riceve il sistema sarà dunque

Atot = Apng+ Avisvisvar (3.3)

Come detto in precedenza quando l'angolo di heading relativo tra i due veicoli è troppo elevato al posto della PNG viene utilizzata la correzione di o heading.

Da qui in aventi faremo riferimento sempre alla versione con la PNG per alleggerire la trattazione anche se nelle zone in cui per denizione avremo l'O Heading ovviamente si utilizzerà una legge che presenta Aoh invece di

Apng. Una prima miglioria a quanto fatto che si può fornire non utilizzandoo

la PNG sempre allo stesso modo per qualunque condizione di visibilità, in particolare si vuole evitare che il veicolo la utilizzi quando la visibilità sul target è nulla. Per far questo l'accelerazione Apng verrà pesata per il livello

di visibilità dell'oggetto producendo la legge seguente

Atot = Apngvislev+ Avisvisvar (3.5)

La cosa ha senso in campo pratico infatti se non vedo ciò che sto inseguendo il mio obbiettivo dovrà essere cercarlo e non inseguirlo. In termini simulativi la scelta eettuata porterà a ricercare più velocemente un buon livello di visibilità rispetto all'avvicinamento al veicolo che, in caso di scarsezza di tale livello, porta solamente ad avvicinarsi agli ostacoli. Si può osservare che se vislev > 0.5 io ho la certezza di avere la LOS libera sul target anche

se ho una porzione della zona di incertezza coperta da almeno un ostacolo; si può perciò pensare di utilizza la (3.5) in caso di vislev ≤ 0.5 pesando

unitariamente il contributo di visibilità in modo da rendere il veicolo più reattivo alle variazioni di ma mantenere la (3.3) quando vislev >0.5.

Si può anche pensare di non utilizzare la porzione relativa alla visibilità e quindi servirsi di una PNG pura quando la distanza tra i due veicoli è inferiore ad un certo valore anche se visvar non è nullo in modo da garantirsi

l'intercetto in questi casi; senza questa accortezza può infatti non vericarsi se la zona in cui termina la simulazione è molto vicina ad un ostacolo. La legge di composizione nale risulta quindi essere:

png=      0 vislev <10−3

Accpng vislev vislev ≤ 0.5

Accpng vislev >0.5

(3.6)

vis= (

Accvis vislev ≤ 0.5

Accvis visvar vislev >0.5

(3.7)

acc= png + vis; (3.8)

Dove Accvis ed Accpng sono le accelerazioni comandate separatamente dei

due contributi di accelerazione mentre png e vis sono le eettive componenti usate quando le due parti vengono utilizzate congiuntamente; inne acc è l'accelerazione totale comandata al veicolo.

3.6 Correzione di O Heading

La Proportional Navigation Guidance deriva dalle equazioni descritte dal gio-co dierenziale ma, a dierenza di quanto accade utilizzando le accelerazioni che nascono dal formalismo completo, questa versione presenta degli errori quando le direzioni delle velocità dei due veicoli formano degli angoli relativi troppo elevati. Questo avviene perché per poter scrivere la legge di guida nel-la forma canonica vengono apportate delle linearizzazioni; a causa di queste se gli angoli relativi tra le velocità dei due veicoli sono troppo grandi il veicolo inseguitore si muove lungo la traiettoria corretta ma con verso opposto a do-ve si trova il target allontanandosi sempre di più dal do-veicolo da raggiungere. Per eliminare tale problema basta aggiungere una correzione che permetta al veicolo inseguitore di rientrare nella zona di corretto funzionamento quando le condizioni iniziali o, nel nostro caso, le manovre eettuate per portare il veicolo in zone di buona visibilità non sono coerenti con le limitazioni de-scritte. Tale correzione ha la forma di una accelerazione perpendicolare al vettore velocità da usare in alternativa alla Apng nelle zone problematiche.

Fig. 3.5: Scenario per la correzione di O Heading

Tale correzione prende il nome di O Heading ed è descritta da un valore massimo Koh che viene mutuato dal seno della dierenza tra l'angolo

della LOS e l'orientazione della velocità del veicolo ovvero

Aoh = Kohsin(σ − γp) (3.9)

Per delimitare le zone di comportamento si deniscono due angoli; il primo (γmid) denisce il valore ideale di angolo d'attacco il secondo (β) la massima

distanza angolare del vettore velocità del veicolo da γmid gestibile con la Png

pura; matematicamente tali angoli sono deniti come: γmid = σ + arcsin  vtsin(γt− σ) vp  (3.10) β = arcsin vt vp  (3.11) Da notare come tali angoli dipendano dal modulo della velocità dei due veicoli e non solo dalle loro direzioni; in particolare il settore in cui si utilizza la PNG sarà più ampio al diminuire della velocità vp del pursuer e al crescere della

velocità vt del target viceversa diminuirà di ampiezza all'aumentare della

velocità dell'inseguitore ed al diminuire di quella dell'evader. Nel caso limite in cui il target è fermo β risulterà nullo e la PNG verrà utilizzata solo se il vettore velocità del veicolo sarà perfettamente coincidente con la direzione descritta da γmid. Avendo denito queste quantità posso dividere lo spazio

intorno al pursuer in due settori: uno compreso tra γmid + β e γmid − β e

l'altro esterno al precedente. Se γp è compreso nel primo settore si utilizzerà

come legge di guida la Pure PNG mostrata in (2.5) se si trova nel settore esterno utilizzeremo la correzione di O Heading ovvero l'equazione (3.9).

Fig. 3.6: Denizione delle zone dello spazio per correzione di O Heading In gura (3.6) vengono mostrate le zone di funzionamento dello spazio; la zona 2 (in rosso nella gura) è quella in cui viene usata la PNG mentre la zona 1 e la zona 3 (insieme sono la zona esterna a quella di corretto funzionamento) sono quelle in cui viene utilizzata la correzione di O Heading.

Simulazioni

Nelle gure seguenti viene mostrato il comportamento della Pure PNG quan-do lo scenario inizia da una condizione esterna a quella di corretto funzio-namento. Risulta chiaro dal presente esempio come il pursuer compia una manovra per ricercare la traiettoria giusta per inseguire il target ma questa avvenga nel verso opposto a quello utile.

Fig. 3.7: Andamento dello scenario

Se facciamo riferimento ai graci delle accelerazioni vediamo come lo sce-nario debba essere ritenuto concluso intorno ai 10 sec poiché da li in poi le accelerazioni dei due veicoli risultano nulle.

Fig. 3.8: Accelerazione di pursuer e target

I due veicoli in da questo momento si trovano sul triangolo di intercetta-zione perciò la ˙σ è nulla anche se invece di avvicinarsi gli agenti si allontanano e creano una closing velocity negativa. Di seguito sono riportati i graci delle velocità.

Fig. 3.9: Velocità di pursuer e target

Vediamo cosa succede introducendo il fattore correttivo descritto in prece-denza; nella gura di sinistra possiamo vedere come in questo caso lo scenario vada a buon ne mentre a destra viene riportata una comparazione dei due comportamenti. Il tratto in verde è quello in cui il pursuer utilizza la correzio-ne di O Heading. In giallo mostriamo invece la variaziocorrezio-ne della traiettoria del target dovuta ai dierenti valori di ˙σ che si generano con il nuovo con-trollo del pursuer che dunque modicano l'andamento del veicolo inseguito anche se su di esso non vi è modica del sistema di controllo.

Fig. 3.10: Variazione delle traiettorie

Dai graci delle accelerazioni è facilmente intuibile il momento di transi-zione da una strategia di controllo alla successiva, infatti nel primo periodo (quello in cui utilizzo la correzione di O Heading) l'accelerazione coman-data è costante al valore massimo possibile per correggere in modo rapido l'orientazione del vicolo; in seguito sii ha un brusco decadimento dovuto al controllo generato dalla PNG di intensità minore. Anche il graco relativo al target presenta una discontinuità, anche se minore, dovuta al fatto che le accelerazioni del target dipendono di un veicolo dipendono da come si com-porta l'altro. E' chiaro che sarebbe preferibile andamenti delle accelerazioni di tale tipo prevedendo per esempio che la correzioni di o heading operi con un modulo dell'accelerazione uguale a quello che si avrà quando entra in funzione la PNG, ma questo non può essere conosciuto a priori; in più questa tipo di controllo può essere utilizzato anche quando il target presenta comandi diversi non noti al pursuer.

Visto che anche il contributo correttivo aggiunto in questa sezione vie-ne fornito sotto forma di acceleraziovie-ne perpendicolare al vettore velocità il modulo di quest'ultima non viene modicato durante lo scenario.

Fig. 3.12: Velocità di pursuer e target

Si propone un altro scenario in cui la PNG linearizzata non riesce a garan-tire la condizione di intercetto. In questo caso inizialmente si ha una corre-zione nel senso corretto che porterebbe all'intercetto ma la capacità di sterzo rispetto alle velocità in gioco lo porta a nire nella condizione precedente.

Fig. 3.13: Andamento dello scenario

Anche in questo caso da un certo momento in poi il sistema non porta nessuna forzante per uscire dalla situazione di stallo che si verica.

Fig. 3.14: Accelerazione di pursuer e target

L'andamento delle velocità rispecchia l'andamento delle accelerazioni; nel-la prima fase dello scenario sono presenti variazioni nel tentativo di raggiun-gere l'obiettivo mentre nella fase nale si crea una situazione di stallo in cui i due veicoli viaggiano secondo un moto rettilineo uniforme.

Fig. 3.15: Velocità di pursuer e target

La correzioni d o heading che viene generata da questa condizione ini-ziale agisce per un tempo molto breve ma suciente ad aiutare il veicolo a proseguire lungo la corretta direzione che viene presa inizialmente

Fig. 3.16: Variazione delle traiettorie

L'accelerazione che si genera ha però un modulo molto elevato rispetto al funzionamento del sistema a condizioni normali; questo può essere un proble-ma perché il veicolo potrebbe non essere in grado di sopportare accelerazioni di questo tipo.

Fig. 3.17: Accelerazione di pursuer e target

Per completezza vengono mostrati anche i graci delle velocità che mo-strano, ovviamente, come dove l'intensità de controlli è maggiore le variazioni delle componenti della velocità sono più signicative.

Fig. 3.18: Velocità di pursuer e target

Per ovviare al problema delle accelerazioni troppo forti generate nella fase correzione è possibile diminuire il valore di Koh oppure prevedere una

saturazione nel simulatore che modelli le capacità del veicolo. Il risultato che si ottiene è praticamente lo stesso ovvero l'utilizzo per un tempo superiore della correzione di o heading poiché per avere la stessa curvatura con minore forza centripeta occorre un tempo superiore.

Fig. 3.19: Variazione delle traiettorie

Le accelerazioni mantengono le stesse caratteristiche anche se partono da valori assoluti più bassi ed hanno un decadimento con pendenze me-no ripide rispetto al caso precedente che provocame-no meme-no sbalzi anche al comportamento del target.

Fig. 3.20: Accelerazione di pursuer e target

Anche le velocità subiscono variazioni meno signicative mantenendo un andamento più continuo nella fase di transizione da un comando all'altro.

Fig. 3.21: Velocità di pursuer e target

A livello simulativo è più eciente saturare esternamente il comando di accelerazione rispetto a limitare la costante Koh questo perché, anche se gli

andamenti sono molto simili, consente di utilizzare a pieno le capacità di ma-novra anche quando il fattore sin(σ − γv)presente nella guida farebbe calare

il valore assoluto dell'accelerazione. A livello pratico questo però vuol dire fare andare il veicolo sempre al limite delle sue possibilità che generalmente non è una scelta saggia per la durata della macchina.

Mostriamo alcune possibili applicazioni di questa legge di guida con il ne di spiegarne in modo più chiaro ed intuitivo il funzionamento dimostrando anche la validità del lavoro proposto. Occorrerà una mappa dello scenario su cui eettuate le simulazioni con disposizione degli ostacoli non troppo banale ma tale da non creare zone in cui è impossibile accedere o zone in cui gli ostacoli risultano troppo vicini tra loro per essere considerati separati. Ovviamente c'è la necessità di avere anche un veicolo evasore da inseguire che abbia un'intelligenza tale da rendere l'inseguimento il più complicato possibile al pursuer ma che non abbia capacità di manovra e velocità superiori a quelle dell'inseguitore per rendere possibile l'intercettazione.

4.1 Descrizione dello scenario

Lo scenario che prendiamo in esempio è composto da otto ostacoli concentrati nella zona centrale dello spazio in modo da creare una zona in cui dover eettuare un buon bilanciamento dei due contributi ed una zona esterna nella quale il veicoli compirà le operazioni di ricerca di punti di attacco favorevoli e sfrutterà la guida intercept una volta stanato il target dalle zone in cui si nasconderà. Gli ostacoli vengono scelti con dimensioni sucientemente grandi da non permettere alla regione di incertezza di presentarsi da ambo i lati di un ostacolo; per esempio se la regione di incertezza fosse distribuita su cerchio di raggio 3 metri e un ostacolo avesse lo spesso re di un metro se il target si nascondesse dietro quest'ultimo parte della regione di incertezza apparirebbe dalla parte opposta dell'ostacolo rispetto a quella del veicolo come viene mostrato in gura 4.1, questo tipo di condizione porterebbe il pursuer ad avere il target in parziale vista anche se questo è completamente nascosto facendo utilizzare la png e provocando una collisione con gli ostacoli.

Fig. 4.1: Problema sul dimensionamento dell'ostacolo

In campo reale questo non è un grane problema basta sovradimensionare, nelle informazioni utilizzate dal pursuer, la zona in cui è posizionato un osta-colo assegnando quindi una dimensione minima per ogni lato degli ostacoli pari alla grandezza della zona di incertezza scelta.

Se si vuole utilizzare il metodo di stima della variazione di visibilità del diametro sarebbe conveniente non avere ostacoli troppo vicini tra loro per evitare di avere due contributi negativi posizionati sui due estremi di un diametro che porterebbero ad annullare l'eetto delle penalizzazioni per l'e-vasione dagli ostacoli. Un ultimo aspetto di cui si è tenuto conto è quello di non avere più di due ostacoli con spigoli perfettamente allineati tra lo-ro; questo perché tale condizione provoca la generazione di massimi locali nella mappa di visibilità che, anche se non provocano collisioni con ostacoli, rendono le traiettorie generate dal sistema di guida piene di correzioni e di andamenti ondulatori. Anche questa condizione in campo reale non risulta essere un vero problema poiché è suciente che uno solo degli ostacoli allinea-te sia minimamenallinea-te sporgenallinea-te rispetto agli altri per annullare questi eetti. Lo scenario che verrà utilizzato in seguito tenendo conto delle limitazioni enunciate n precedenza viene mostrato nella gura seguente.

Fig. 4.2: Scenario utilizzato

4.2 Target

Per mostrare il comportamento del simulatore proposto si è scelto di utilizzare un target che non utilizza in tutto e per tutto una guida identica al pursuer. al target non è stata fornita la porzione di guida dovuta alla PNG ma gestisce i suoi movimenti solo in base alla componente che cerca di minimizzare il livello di visibilità che il pursuer possiede sul di lui. In particolare il target stima il gradiente di visibilità utilizzando il metodo del raggio. In caso che esistano più punti con uguale potenziale tra quelli possibili da scegliere è stata introdotta una diversicazione nella risoluzione dell'ambiguità; esistono due possibili scelte per fornire una maggior possibile gamma di comportamenti al target e renderlo meno prevedibile possibile. Può esser scelta la via di prendere la direzione che massimizza la distanza dal pursuer per permettere una fuga il più rapida possibile nelle zone dello scenario in cui il livello di visibilità è molto alto sperando di incontrare una nuova zona con molti ostacoli che possano far da nascondiglio. Un altra scelta è quella di prendere la direzione ammissibile più vicina possibile alla media della direzioni con pari potenziale. Questa seconda scelta tende generalmente a fornire un comportamento più

dicile intuizione guardando le traiettorie compiute dal target; tende però generalmente a far rimanere il veicolo che tenta la fuga nelle zone dove è più alta la concentrazione degli ostacoli. Un'ultima dierenza presente nel target rispetto al pursuer è quella di poter ridurre la propria velocità per permettere al veicolo di rimanere fermo quando si trova in una zona a visibilità nulla; questa modica è presente per rendere più complesso il compito al pursuer in quanto se si permettesse al target di muoversi in tali condizioni l'unico eetto che avrei sarebbe quello di fornire informazioni a chi mista inseguendo e peggiorare la propria condizione.

Simulazioni

Viene mostrato il comportamento del target del target durante l'evasione da un pursuer fermo per evidenziare le dierenza tra le due tipologie di risolu-zione delle ambiguità scelte. Nel primo caso si ha quella in cui il target si allontana il più possibile dal pursuer ovvero in caso di due direzioni ugual-mente valide prende quella a distanza maggiore dal pursuer. La gura a destra è uno zoom della parte interessante dello scenario.

Fig. 4.3: Target con ricerca della massima distanza

Nel secondo caso vengono fornite le stesse condizioni iniziali, la sola cosa che viene modicata è il modo di risolvere le ambiguità; questa volta viene scelta la traiettoria più vicina alla media delle traiettorie valide. Va notato come il comportamento sia completamente diverso nei due casi; viene scelto di andarsi a nascondersi dietro due ostacoli diversi raggiungendoli in un primo caso con una traiettoria rettilinea mentre nel secondo con una traiettoria fortemente oscillatoria.

Fig. 4.4: Target con miglior traiettoria media

4.3 Scenari

Il primo tipo di utilizzo che viene portato è quello relativo all'intercettazione; ai due veicoli vengono assegnate condizioni iniziali per le quali il pursuer ha un livello di visibilità sul target accettabile in modo da utilizzare la guida nella sua forma base senza bisogno di aggiunte per riuscire a compiere l'intercetto. Per prima cosa viene mostrato il funzionamento utilizzando il metodo di stima incentrato sul raggio della circonferenza di valutazione. In rosso viene riportata la traiettoria compiuta dal target mentre in blu quella eettuata dal pursuer. Le frecce verdi rappresentano le direzioni scelte dal contributo di visibilità come direzioni ottime mentre in giallo vengono riportate quelle scelte dalla PNG. Da notare come il pursuer evita l'ostacolo centrale grazie al contributo di visibilità prima di lanciarsi all'inseguimento vero e proprio del target.

Fig. 4.5: Scenario Intercept con Raggio

Vengono riportate l'accelerazione totale comandata al veicolo inseguitore e le due componenti che ne generano l'andamento. In questo caso le com-ponenti sono di modulo superiore al totale perché queste vengono fornite in verso opposto e quindi si sottraggono tra loro. Viene anche mostrato l'anda-mento del livello di visibilità che mostra un primo aul'anda-mento poi fatto calare dallo spostamento compiuto dal target come contromisura; quando però il target supera l'ostacolo il target non ha più la forza di compiere manovre sucientemente evasive.

I due contributi vengono utilizzati con percentuali variabili rispetto al-l'accelerazione totale applicata; le due componenti sono ovviamente comple-mentari perciò viene riportato solo l'utilizzo della componente di visibilità.

Fig. 4.7: Percentuale di utilizzo del contributo di visibilità

Mostriamo ora le modiche che subisce l'andamento dello scenario utiliz-zando l'altro metodo di stima del gradiente, ovvero quello del diametro; la prima cosa che salta all'occhio è quella della distanza molto superiore con cui il veicolo supera l'ostacolo che si frappone, parzialmente, tra lui ed il target. In questo modo si ha un margine di sicurezza maggiore utile sopratutto nel caso in cui i veicoli gure solide invece che descritti da punti materiali.

Fig. 4.8: Scenario Intercept con Diametro

Sempre a titolo di confronto vengono riportate accelerazione, con tanto di componenti, e percentuale di utilizzo del contributo di visibilità rispetto al totale dell'accelerazione. Si nota come le accelerazioni siano in norma più elevato ad inizio simulazione per poi tornare a valori accettabili durante lo scenario

Fig. 4.9: Accelerazioni comandate e percentuali di utilizzo

Il livello di visibilità cresce molto più rapidamente rispetto a quanto suc-cede con l'altro metodo per poi rimanere costante per tutto il resto dello scenario.

Fig. 4.10: Livello di visibilità

Le accelerazioni generate in questo tipo di scenario risultano troppo eleva-te, proviamo allora a svolgere la simulazione saturando l'accelerazione totale comandata al valore di 5 m

sec2. La traiettoria ad inizio simulazione risulta più

lenta a fare la virata necessaria per evitare l'ostacolo a causa dalla minor capacità di accelerare per poi comportarsi in maniera simile al precedente.

Fig. 4.11: Scenario Intercept con Diametro ed accelerazioni saturate Le componenti superano il valore dell'accelerazione totale comandata che

rimane molto contenuta rispetto a quanto avvenuto in precedenza ma i valori alti vengono mantenuti più a lungo a causa del maggior tempo che occorre per eettuare completamente la virata. Il livello di visibilità sale in maniera meno continua rispetto a prima a causa della minor capacità di manovra e quindi occorre più tempo per raggiungere la traiettoria ideale.

Fig. 4.12: Target con ricerca della massima distanza 4.3.2 Ricerca del target

Vediamo cosa succede facendo partire il pursuer da una posizione in cui il livello di visibilità sul target è nullo; ovviamente alla guida dovrà essere fornita la capacità di espandere il proprio raggio di ricerca in modo da trovare valori utili. La simbologia delle frecce sul risultato della simulazione è lo stesso del caso precedente con aggiunta di quelle magenta che rappresentano le scelte fatte dalla PNG in zone dello spazio in cui il sistema di controllo le esclude dal funzionamento a causa del valore nullo di visibilità.

Fig. 4.13: Scenario Intercept con Raggio

Le accelerazioni chiariscono come il veicolo ricerchi subito la traiettoria migliore per trovare valori di visibilità buoni e non compia più manovre no a quando il punto richiesto non viene raggiunto; da questo momento in poi il controllo evolve nello stesso modo in cui avrebbe fatto per gli scenari precedenti, in particolare per sviluppare la denitiva guida proposta viene adottato il metodo di stima del raggio incrementale per eettuare una ricerca del punto migliore per cominciare l'ingaggio per poi utilizzare il diametro per concluderlo.

Di seguito vengono aancati l'andamento del livello di visibilità e quello delle dimensioni del raggio utilizzato per la stima del gradiente. Va notato coma il cerchio di valutazione sia di dimensioni superiori a quella base no all'istante precedente a quello in cui si recupera un livello di visibilità diverso da zero.

Fig. 4.15: Composizione della accelerazioni e livello di visibilità 4.3.3 Due target

Vengono di seguito riportati degli scenari un cui vengono utilizzate strategie per utilizzare la guida proposta anche in scenari diversi dal classico uno contro uno. In questa sezione viene riportato un metodo per riuscire a compiere intercettazione su più target utilizzando un solo veicolo. Chiariamo subito che essendo in possesso di informazioni sulle zone di posizionamento dei target utilizzando il raggio incrementale sarebbe suciente, a livello di simulazione, assegnare un ordine di inseguimento ai vari target e compiere più intercetti in sequenza con condizioni iniziali le nali dell'intercetto precedente. In realtà si cerca una soluzione più elegante e gestibile con una minor quantità di informazioni. Verrà denito un target ttizio che avrà come caratteristiche la media media delle posizioni e delle velocità dei due target che sto realmente tenendo sotto controllo in modo da mantenere un buon livello di visibilità su entrambi gli agenti. Questa condizione verrà mantenuta no a quando non si vericherà una condizione che verrà utilizzata per forzare l'inizio vero e proprio delle intercettazioni. La condizione può essere fornita sotto diverse forme:

1. intercettazione del target ttizio

3. angolo formato dalle linee di vista sui due agenti più grande di un certo valore

4. ...

Nella simulazione presentata la condizione di sblocco è il superamento dei 90◦ _{da parte dell'angolo che siforma tra le due line of sight. Quando si}

verica tale condizione il pursuer intercetta il target più vicino per poi inse-guire il rimanente con le informazioni ricavate no a quel momento. Vengono riportati i graci di visibilità rispetto ai tre target ovvero i due target reali e quello costruito in modo ttizio per gestire la prima fase di approccio.

Le accelerazioni si mantengono su valori contenuti esclusi i momenti in cui il pursuer cambia obbiettivo in cui sono presenti dei picchi di energia nel controllo richiesti per reagire al bisogno di orientarsi in modo dierente a quanto fatto no a quel momento.

4.3.4 Due Pursuer

Un ultimo utilizzo che si vuole proporre è quello relativo alla cooperazione di due pursuer per riuscire ad intercettare in maniera più ecace un unico target. I due avranno dunque necessità di dividersi lo spazio a disposizione in due zone da cui dover partire per compiere il proprio obiettivo. Si sfrutterà ancora una volta il concetto di visibilità per suddividersi la zone di ingaggio. Verranno ricercate tutte le zone a massimo livello di visibilità e verranno pesate per la distanza dal target all'interno di cerchio massimo di distanza dal target entro un certo range. Tutte le posizioni con valori massimi vengono scelte come possibili zone di attacco. Vengono selezionate come attive quelle più vicine ai veicoli inseguitori che come primo obbiettivo raggiungeranno tali punti dello scenario per poi dirigersi verso il target.

Mostriamo una mappa di visibilità tridimensionale classica a cui aan-chiamo la sua versione pesata per la distanza

Fig. 4.16: Visibilità classica e pesata per la distanza

Dalle informazioni raccolte dal precedente graco vengono deniti i punti di migliori di approccio descritti dai cerchi nello scenario che segue in cui si mostra il comportamento del sistema. Fino a che non vengono raggiunti i punti designati per l'inizio dell'ingaggio i pursuer non si curano della presenza del target. Solo in seguito i due pursuer si gettano all'inseguimento anche senza attendere che l'altro pursuer raggiunga il proprio punto di attacco.

La visibilità dei pursuer viene attivata solo una volta raggiunta la zona designata per l'attacco per poi evolversi come nei casi classici.

Si vuole dare una caratterizzazione matematica al problema appena descritto in modo da dimostrare la correttezza delle idee proposte. Per fare questo ci si ada all'aiuto della teoria dei giochi dierenziali. I giochi dierenziali sono una tipologia di problemi che interessano la modellazione e l'analisi di una situazione di conitto nel contesto di un sistema dinamico; sono molto utilizzati in letteratura non solo per problemi ingegneristici ma anche in altri campi come ad esempio quello economico per prevedere l'andamento dei mercati ma anche in capo sociologico.

Per alcuni aspetti questa categoria di problemi risulta molto simile a quella del controllo ottimo e le equazioni che ne descrivono il funzionamento si ricavano in maniera analoga; la dierenza sta nel fatto che in un problema di controllo ottimo è presente un singolo giocatore, un singolo controllo ed un unico criterio da ottimizzare. Nella teoria dei giochi dierenziali, invece, su un unico funzionale di costo agiscono due giocatori con due controlli diversi e due diversi criteri di ottimizzazione. Ogni giocatore cercherà infatti di controllare lo stato del sistema per raggiungere i propri obiettivi ed il sistema risponderà agli input di entrambi i giocatori.

In un problema pursuit-evasion si avranno due agenti(nel nostro caso identici), il cui moto è modellato con equazioni dierenziali; uno (il pursuer) tenterà di minimizzare il valore del funzionale di costo che modella il com-portamento del sistema mentre l'altro (l'evader) cercherà di massimizzarlo in modo da rendere il compito del pursuer il più complicato possibile.

La soluzione del problema risulterà dunque quella di trovare un punto di sella per il funzionale J coerentemente coi vincoli del problema ovvero bisognerà trovare la coppia di strategie ottime ( ¯u,¯v) per le quali risulta

J(¯u, v) ≤ J(¯u,v) ≤ J(u, ¯¯ v) (5.1) La relazione deve valere per qualunque coppia di strategie (u, v) in cui u e v sono tutte le possibili accelerazioni assegnabili come controlli rispetti-vamente al pursuer ed evader. Il problema da risolvere sarà quindi denito nella seguente maniera:

Trovare il punto di sella del funzionale di costo J = β(x(T ), T ) + Z T t0 L(x, u, v, t)dt (5.2) soggetto ai vincoli ˙ x= f (x, u, v, t) x(t0) = x0 (5.3)

dove x è lo stato del sistema che deve tenere conto dei singoli stati di entram-bi gli agenti. Le strategie di controllo u e v scelte per comandare gli agenti dovranno essere coerenti con il problema scelto e quindi dovranno apparte-nere agli insiemi delle strategie ammissibili U(t) e V (t); anche le strategie ottime devono essere tali che

¯

u(t) ∈ U (t) v(t) ∈ V (t)¯ (5.4)

Se la precedente è vericata ¯u e ¯v vengono denite strategie ottime pure mentre J(¯u,v) = W (x¯ 0, t0) viene chiamato valore del gioco dierenziale e

può essere denito come segue

W(x0, t0) = M in

u∈U M axv∈V (J) (5.5)

5.1 Pursuit-Evasion Game

Per impostare correttamente il nostro problema occorre prima studiare be-ne quanto fatto in letteratura per dimostrare il comportamento ottimo della Proportional Navigation Guidance partendo dalla denizione di un qualun-que gioco dierenziale tra un pursuer ed un evader. Le equazioni del moto dei due agenti sono denite in forma ane nel controllo come segue

˙

xp(t) = Fp(t)xp(t) + ¯Gp(t)u(t) (5.6)

˙

xe(t) = Fe(t)xe(t) + ¯Ge(t)v(t) (5.7)

con xp e xe vettori di stato rispettivamente del pursuer e dell'evader Fp, Fe

sono le matrici che descrivono l'evoluzione libera dei due veicoli mentre ¯Gpe

¯

Ge descrivono l'evoluzione forzata dai controlli u e v. Il funzionale di costo

scelto avrà una parte che misura la dierenza degli stati dei due agenti al tempo T di ne ingaggio ed un'altra che tiene conto di quanto controllo è necessario per raggiungere tali caratteristica degli stati

J = a 2 2k(xp(T ) − xe(T ))k 2 AT_A+ 1 2 Z T t0 h ku(t)k2 Rp(t) − kv(t)k 2 Re(t) i dt (5.8)

Rp ed Re sono matrici che pesano i controlli nel funzionale di costo

ovve-ro indicano quando energia serve per eettuare i contovve-rolli richiesti; A pesa l'errore a ne ingaggio ed è denita come una matrice nella forma [Ik 0]

dove Ik è una matrice identica di dimensione k questo perché il mio errore a

tempo nale deve dipendere dalla distanza relativa tra i due agenti, se aves-simo voluto costruire un randez-vous tale contributo sarebbe dipeso anche dalle velocità al tempo nale; a è un peso aggiuntivo per controllare l'ener-gia di ne ingaggio. Il gioco dierenziale in questione viene impostato come un problema a tempo nito ovvero viene impostato a priori l'istante in cui voglio che avvenga l'ingaggio; grazie a questa informazione posso utilizzare una equazione al contorno per trovare il valore del costato al tempo nale T predeterminato.

Per facilitare i conti in letteratura viene trasformato il problema in uno equivalente eettuando un cambio di variabile dalle variabili spaziali x e y con le relative derivate che porta lo stato ad essere di ordine 2k ad un unico vettore di stato k-dimensionale; per riuscire nella costruzione di questo cambio di variabili vantaggioso si introducono le matrici di risposta impulsiva dei sue agenti Φp e Φe

Φp(T, t) = e RT t Fp(τ )dτ Φe(T, t) = e RT t Fe(τ )dτ (5.9)

Il nuovo stato verrà trovato applicando la seguente equazione

z(t) = A [Φp(T, t)xp(t) − Φe(T, t)xe(t)] (5.10)

Una volta applicata la modica allo stato del sistema anche il funzionale di costo apparirà in forma del nuovo stato

J = a 2 2kz(T )k 2₊ 1 2 Z T t0 h ku(t)k2 Rp(t) − kv(t)k 2 Re(t) i dt (5.11)

Derivando il nuovo stato si ottengono anche i nuovi vincoli del gioco die-renziale in forma di vettore unico

˙

z = Gp(T, t)u(t) − Ge(T, t)v(t) (5.12)

dove le matrici Gp(T, t) e Ge(T, t)sono denite come segue

Gp(t) = AΦp(T, t) ¯Gp(t) (5.13)

E' facile notare che né i vincoli e né il funzionale di costo risultano dipendere dai vecchi stati perciò il cambio di variabile risulta completo. Una volta denito tutto il problema con le nuove variabili di stato è possibile costruirsi l'Hamiltoniano del gioco dierenziale in maniera analoga a quanto avviene nel controllo ottimo

H(λ, z, u, v, t) = 1 2  ku(t)k2 Rp− kv(t)k 2 Re  + λT _(G p(t)u(t) − Ge(t)v(t)) (5.15) Anche le regole derivanti dal calcolo variazionale dell'Hamiltoniano per co-struire le equazioni di Eulero-Lagrange sono le stesse che vengono utilizzate nel controllo ottimo

∂H(λ, z, u, v, t) ∂u = 0 (5.16) ∂H(λ, z, u, v, t) ∂v = 0 (5.17) ˙ z(t) = ∂H(λ, z, u, v, t) ∂λ (5.18) ˙λT_{(t) = −}∂H(λ, z, u, v, t) ∂z (5.19)

Dalla 5.16 e 5.17 si ottengono le espressioni delle strategie ottime di controllo u(t) = −R−1p (t)G

T

p(T, t)λ(t) (5.20)

v(t) = −R_e−1(t)GT

e(T, t)λ(t) (5.21)

Invece dalla 5.19 otteniamo l'equazione dierenziale che gestisce l'andamento di λ(t) ma visto che l'Halitoniano non dipende da z(t) questa risulterà

˙λ(t) = 0 (5.22)

Conoscendo l'istante di ne ingaggio T , poiché il problema è a tempo ssato, si può ricavare la condizione di trasversalità

λ(T ) = ∂β(z(T ), T ) ∂z(T ) = a

2_{z(T ) (5.23)}

Nota la 5.23 si integra la 5.22 e si sostituisce in 5.20 ed 5.21 ottenendo u(t) = −R_p−1(t)GT

p(T, t)a

v(t) = −R−1_e (t)GT

e(T, t)a

2_{z(T ) (5.25)}

E' chiaro che risulta scomodo esprime i controlli in funzione dello stato del sistema a tempo nale. Per risolvere tale problema si utilizza il backward-sweep method per esprimere il risultato in funzione del tempo corrente; tale metodo consiste nello scrivere λ(t) in funzione dello stato

λ(t) = K−1(T, t)z(t) (5.26)

sappiamo che, per il problema che si sta studiando, ˙λ(t) = 0; è possibile sfruttare quindi questa informazione per derivare la precedente equazione trovando

˙λ(t) = 0 = ˙K−1(T, t)z(t) + K−1(T, t) ˙z(t) (5.27) Sostituendo a ˙z(t) la sua espressione denita in 5.12 posso riscrivere la precedente in forma esplicita

˙

K−1(T, t)z(t) = −K−1(T, t)[Gp(T, t)u(t) − Ge(T, t)v(t)] (5.28)

sostituendo l'espressione di u(t) e v(t) nella precedente posso semplicare le equazioni e, per come sono caratterizzate in questo problema, si riesce a semplicare l'equazione eliminando la dipendenza da z(t)

˙

K−1(T, t) = −K−1(T, t)[Gp(T, t)R−1p GTp(T, t) − Ge(T, t)R−1e GTe]K −1

(T, t) (5.29) Conoscendo le condizioni al contorno che determinano K(T, T )−1 _{= I posso}

ricavare il valore di K(T, t) integrando la precedente equazione dierenziale K(T, t) = IR

a2 + Mp(T, t) − Me(T, t)



(5.30) in cui Mp(T, t)ed Me(T, t) sono denite nel seguente modo

Mp(t, t0) = Z t t0 Gp(T, τ )R−1p G T p(T, τ )dτ (5.31) Me(t, t0) = Z t t0 Ge(T, τ )R−1e GTe(T, τ )dτ (5.32)

Sostituisco l'espressione trovata nelle equazioni delle strategie ottime tro-vando così le eettive accelerazioni da comandare agli agenti per risolvere il problema evasione-inseguimento espresso come gioco dierenziale

v(t) = −R−1 e G

T eK

−1_{(T, t)z(t) (5.34)}

Bisogna determinare la condizione suciente per l'esistenza del punto di sella; per questo svolgiamo la derivata seconda dell'Hamiltoniano rispetto ai controlli e verichiamo che tali valori siano positivi per il pursuer e negativi per l'evader.

∂2_{H(λ, z, u, v, t)}

∂u(t)2 = Rp(t) > 0

∂2_{H(λ, z, u, v, t)}

∂v(t)2 = −Re <0 (5.35)

Tale condizione risulta essere vericata visto che Rp(t)ed Re(t)sono matrici

denite positive.

5.2 PNG come pursuit-evasion game

Una volta denito in maniera generale il problema si può passare a svolgere i conti di un caso particolare al quale facciamo riferimento ovvero la Pro-portional Navigation Guidance. Faremo riferimento a moti che si svolgono su un piano orizzontale, quindi il sistema sarà descritto con due gradi di li-bertà, considerando i due veicoli identici a patto di avere velocità e capacita di controllo superiori per quanto riguarda il pursuer rispetto all'evader. Per descrivere la dinamica dei veicoli si utilizzano le equazioni riportate in 5.6 ed 5.7 scegliendo come vettore di stato le posizioni e le velocità dei due veicoli nel modo seguente

xp =  rp vp  xt =  rt vt  (5.36) le matrici che ne deniscono l'evoluzione del moto risulteranno semplicissime per a possibilità di elidere le componenti gravitazionali poiché i due veicoli sono considerati in una zona dello spazio ristretta e quindi con pari eetti gravitazionali Fp= Fe = 0 I 0 0  ¯ Gp= ¯Ge = 0 I  (5.37) In questo modo si riescono ad esprimere le equazioni come se tutte le quantità espresse siano di ordine uno semplicando i calcoli che verranno svolti in seguito. Per essere precisi posizioni e velocità andrebbero espresse in uno spazio di dimensione 2 o 3 per essere più simili a quando succede nella realtà; i risultati ottenuti con questa descrizione sono però perfettamente compatibili