Politecnico di Milano · Alcuni dei piu` recenti lavori relativi ai racing games `e stato svolto da...

Politecnico di Milano

Facolta di Ingegneria dell’Informazione

Corso di Laurea Specialistica in Ingegneria Informatica

Dipartimento di Elettronica e Informazione

Evoluzione della traiettoria ottimale

in un simulatore di guida

Relatore: Ing. Daniele LOIACONO

Correlatori: Prof. Pier Luca LANZI

Ing. Luigi CARDAMONE

Tesi di laurea di: Matteo Botta matr. 739397

Vincenzo Gautieri matr. 739391

Anno Accademico 2010-2011

Indice

Elenco delle figure iii

Elenco delle tabelle vii

1 Introduzione 1

1.1 Organizzazione della tesi . . . . . . . . . . . . . . . . . . . . . . 2

1.2 Contributi Originali . . . . . . . . . . . . . . . . . . . . . . . . . 2

2 Stato dell’arte 5

2.1 L’intelligenza artificiale nei racing games . . . . . . . . . . . . . 6

2.1.1 TORCS . . . . . . . . . . . . . . . . . . . . . . . . . . . 6

2.2 Il problema della racing line . . . . . . . . . . . . . . . . . . . . 8

2.2.1 Studi correlati . . . . . . . . . . . . . . . . . . . . . . . . 9

3 Rappresentazione della racing line 13

3.1 Le curve di Bezier . . . . . . . . . . . . . . . . . . . . . . . . . . 13

3.1.1 Definizione matematica della curva . . . . . . . . . . . . 14

3.1.2 Proprieta . . . . . . . . . . . . . . . . . . . . . . . . . . 15

3.1.3 Costruzione delle curve di Bezier . . . . . . . . . . . . . 16

3.2 Rappresentazione della racing line con curve di Bezier . . . . . . 18

3.2.1 Divisione del circuito in sezioni . . . . . . . . . . . . . . 18

3.2.2 Definizione della rappresentazione come curva di Bezier . 19

3.2.3 Identificazione del numero di punti di controllo necessari 22

3.2.4 Calcolo della curva di Bezier e conversione della rappre-

sentazione . . . . . . . . . . . . . . . . . . . . . . . . . . 24

INDICE

4 Ottimizzazione della traiettoria 27

4.1 Metodi di ottimizzazione . . . . . . . . . . . . . . . . . . . . . . 27

4.2 Codifica della soluzione . . . . . . . . . . . . . . . . . . . . . . . 28

4.3 Inizializzazione della popolazione . . . . . . . . . . . . . . . . . 30

4.4 Valutazione della bonta della Racing Line, il calcolo della fitness 30

4.4.1 Crossover delle traiettorie . . . . . . . . . . . . . . . . . 32

5 Analisi sperimentale 35

5.1 Validazione della rappresentazione del tracciato . . . . . . . . . 36

5.2 Scelte sperimentali . . . . . . . . . . . . . . . . . . . . . . . . . 37

5.2.1 Tracciati analizzati . . . . . . . . . . . . . . . . . . . . . 37

5.2.2 Scelta dei parametri della rappresentazione . . . . . . . . 38

5.2.3 Scelta dei parametri dell’algoritmo genetico . . . . . . . 40

5.3 Risultati sperimentali con fitness function simulata . . . . . . . 41

5.3.1 Evoluzione senza seeding . . . . . . . . . . . . . . . . . . 42

5.3.2 Evoluzione con seeding . . . . . . . . . . . . . . . . . . . 50

5.4 Risultati sperimentali con fitness function stimata . . . . . . . . 54

5.4.1 Studio delle inversioni . . . . . . . . . . . . . . . . . . . 54

5.4.2 Evoluzione con fitness stimata . . . . . . . . . . . . . . . 57

6 Conclusioni e sviluppi futuri 65

6.1 Risultati . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 65

6.2 Sviluppi Futuri . . . . . . . . . . . . . . . . . . . . . . . . . . . 67

Bibliografia 69

A Configurazione del tool 75

ii

Elenco delle figure

2.1 Evoluzione dei racing game . . . . . . . . . . . . . . . . . . . . . 5

2.2 TORCS: schermata di gioco . . . . . . . . . . . . . . . . . . . . 7

2.3 Esempio di racing line . . . . . . . . . . . . . . . . . . . . . . . 8

2.4 Un esempio di come viene decomposto un tracciato basandosi

sulle intersezioni tra il cammino minimo (SP) e il cammino a

minima curvatura (MCP) . . . . . . . . . . . . . . . . . . . . . 11

3.1 Esempio di una curva di Bezier . . . . . . . . . . . . . . . . . . 14

3.2 Costruzione di una Bezier di secondo grado . . . . . . . . . . . . 16

3.3 Curve di Bezier di ordine superiore al secondo . . . . . . . . . . 17

3.4 Esempio di movimento di un punto di controllo (1) . . . . . . . 19

3.5 Esempio di movimento di un punto di controllo (2) . . . . . . . 20

3.6 Esempio di posizione dei punti di controllo . . . . . . . . . . . . 22

3.7 Tracciati calcolati con diversi valori dei punti di controllo . . . . 25

4.1 Sezione di un individuo, corrispondente al genoma in tabella 4.2 29

4.2 Diagramma rappresentante il calcolo della funzione di fitness . . 31

4.3 Due generiche traiettorie . . . . . . . . . . . . . . . . . . . . . . 32

4.4 Primo risultato Crossover . . . . . . . . . . . . . . . . . . . . . 33

4.5 Secondo risultato Crossover . . . . . . . . . . . . . . . . . . . . 33

5.1 Esempio di copia di una traiettoria . . . . . . . . . . . . . . . . 37

5.2 Ottimizzazione di racing line su A-speedway senza seeding, con

fitness function simulata. La curva riporta l’andamento di 5 run

evolutive . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 42

ELENCO DELLE FIGURE

5.3 Ottimizzazione di racing line su Alpine-2 senza seeding, con

fitness function simulata. La curva riporta l’andamento di 5

run evolutive . . . . . . . . . . . . . . . . . . . . . . . . . . . . 43

5.4 Ottimizzazione di racing line su CG-speedway senza seeding,

con fitness function simulata. La curva riporta l’andamento di

5 run evolutive . . . . . . . . . . . . . . . . . . . . . . . . . . . 43

5.5 Ottimizzazione di racing line su Ruudskogen senza seeding, con


evolutive . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 44

5.6 Ottimizzazione di racing line su Wheel-1 senza seeding, con fit-

ness function simulata. La curva riporta l’andamento di 5 run

evolutive . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 44

5.7 Traiettorie a confronto su particolari di pista. In rosso e rappre-

sentanta la racing line di Simplix, mentre in verde quella trovata

con la nostra rappresentazione . . . . . . . . . . . . . . . . . . . 45

5.8 Evoluzione delle traiettorie. Particolare di A-speedway . . . . . 46

5.9 Evoluzione delle traiettorie. Particolare di Alpine-2 . . . . . . . 47

5.10 Evoluzione delle traiettorie. Particolare di CG-speedway . . . . 47

5.11 Evoluzione delle traiettorie. Particolare di Ruudskogen . . . . . 48

5.12 Andamento di 10 punti di controllo durante l’evoluzoine . . . . 48

5.13 Posizione di 4 punti di controllo all’interno del tracciato e

relative deviazioni standard . . . . . . . . . . . . . . . . . . . . 49

5.14 Ottimizzazione di racing line su A-speedway con seeding, con


evolutive . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 51

5.15 Ottimizzazione di racing line su Alpine-2 con seeding, con fitness

function simulata. La curva riporta l’andamento di 3 run evolutive 51

5.16 Ottimizzazione di racing line su CG-speedway con seeding, con


evolutive . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 52

iv

ELENCO DELLE FIGURE

5.17 Ottimizzazione di racing line su Ruudskogen con seeding, con


evolutive . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 52

5.18 Ottimizzazione di racing line su Wheel-1 con seeding, con fitness

function simulata. La curva riporta l’andamento di 3 run evolutive 53

5.19 Schema per l’identificazione di un’inversione. . . . . . . . . . . . 55

5.20 Percentuale di inversioni per generazione . . . . . . . . . . . . . 56

5.21 Delta assoluto tra tempo stimato e tempo simulato su 100

generazioni . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 57

5.22 Ottimizzazione di racing line su A-speedway senza seeding, con

fitness function stimata. La curva riporta l’andamento di 5 run

evolutive . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 58

5.23 Ottimizzazione di racing line su Alpine-2 senza seeding, con


evolutive . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 58

5.24 Ottimizzazione di racing line su CG-speedway senza seeding,

con fitness function stimata. La curva riporta l’andamento di 5

run evolutive . . . . . . . . . . . . . . . . . . . . . . . . . . . . 59

5.25 Ottimizzazione di racing line su Ruudskogen senza seeding, con


evolutive . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 59

5.26 Ottimizzazione di racing line su Wheel-1 senza seeding, con fit-

ness function stimata. La curva riporta l’andamento di 5 run

evolutive . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 60

v

Elenco delle tabelle

4.1 Caratteristiche dei metodi di ottimizzazione . . . . . . . . . . . 28

4.2 Esempio di codifica di un genoma . . . . . . . . . . . . . . . . . 29

5.1 Tracciati utilizzati nella nostra analisi . . . . . . . . . . . . . . . 38

5.2 Variazione del numero di punti di controllo al variare dei parametri 39

5.3 Tabella riassuntiva dei tempi ottenuti su 5 run, senza seeding . . 42

5.4 Tabella riassuntiva contenente i migliori tempi ottenuti in 3 run,

utilizzando il seeding . . . . . . . . . . . . . . . . . . . . . . . . 50

5.5 Confronto tra tempi di lap stimati ed effettivi . . . . . . . . . . 61

5.6 Differenza tra i tempi computazionali medi di ogni run nelle due

tipologie di fitness. . . . . . . . . . . . . . . . . . . . . . . . . . 62

5.7 Tabella di confronto tra i tempi ottenuti tra le due tipologie di

analisi (funzione obiettivo simulata e stimata) . . . . . . . . . . 62

6.1 Risultati a confronto (i tempi sono misurati in secondi) . . . . . 66

Capitolo 1

Introduzione

Nel corso degli anni la tecnologia applicata ai videogame e sempre andata

migliorando. La possibilita di avere potenza di calcolo sempre maggiore, di

grafiche migliori, e di realizzare sfide multiplayer offline ed online, ha portato

ad avere videogiochi sempre piu complessi e coinvolgenti. Ultimamente l’enfasi

si e spostata sulla realizzazione di contenuti personalizzati, ossia permettere

all’utente di generare autonomamente feature specifiche per il gioco in questio-

ne. Nei racing game, per esempio, si e partiti dando la possibilita all’utente

di realizzare auto con livree personalizzate, fino ad arrivare alla creazione di

veri e propri tracciati. Ad oggi, la vera sfida consiste nel permettere all’utente

di sfidare, su questi nuovi tracciati, non solo se stessi o altri utenti, ma anche

intelligenze artificiali con vari livelli di difficolta. Questo e un problema di non

poco conto, poiche una volta creato il tracciato, non si ha automaticamente

una racing line buona da seguire, ma andrebbe calcolata analizzando le ca-

ratteristiche del tracciato e le peculiarita della macchina (aerodinamica, grip

etc.). Per la maggiore le case produttrici si avvalgono di esperti del settore i

quali si occupano di disegnare una traiettoria ottimale per ogni circuito [21].

Il nostro lavoro si inserisce proprio in questo ambito, in quanto l’obiettivo

finale e quello di riuscire a generare una racing line ottima automaticamente

partendo solamente dalle caratteristiche della pista e della macchina interes-

sata. Il simulatore scelto per gli esperimenti riportati in questa tesi e TORCS,

“The Open Racing Car Simulator”, un complesso simulatore di guida auto-

Introduzione

mobilistica open source. Le ragioni che hanno determinato questa scelta sono

la versatilita del gioco, la presenza di alcuni utili strumenti per la gestione dei

BOT e la possibilita di usare del codice open source. In particolare quest’ul-

tima caratteristica e stata molto importante per l’implementazione di alcune

modifiche che hanno permesso di adattare il simulatore al tipo di esperimen-

ti eseguiti in questa tesi. Inoltre TORCS, ad oggi, e lo standard in ambito

accademico per la ricerca e lo sviluppo dell’inteligenza artificiale applicata ai

racing game.

1.1 Organizzazione della tesi

Nel Capitolo 2 vengono presentati gli studi effettuati fino ad oggi nell’ambito

della generazione di racing line e TORCS, il simulatore usato per lo scopo di

questa tesi.

Nel Capitolo 3 vengono introdotti gli strumenti matematici utilizzati e le

assunzioni formulate per la creazione della rappresentazione da noi introdotta.

Nel Capitolo 4 viene descritto il processo evolutivo, esaminando in dettaglio i

principali componenti che permettono l’esecuzione dell’algoritmo genetico.

Nel Capitolo 5 vengono illustrati gli esperimenti effettuati e i risultati ottenuti

al variare dei parametri in gioco.

Nel Capitolo 6 vengono mostrate le conclusioni estrapolate ad esperimenti

terminati e vengono inoltre presentati alcuni interessanti sviluppi futuri.

1.2 Contributi Originali

• Abbiamo creato una nuova rappresentazione per la generazione di una

racing line basata interamente su curve di Bezier, integrandola in TORCS

e mostrando come sia possibile, ottimizzandola tramite un processo evo-

lutivo, ottenere dei lap time anche inferiori a quelli del miglior BOT

presente in TORCS.

2

1.2 Contributi Originali

• Abbiamo valutato le prestazioni dell’algoritmo genetico in base all’uti-

lizzo di diverse strategie per l’inizializzazione della popolazione.

• Abbiamo valutato la bonta dello stimatore interno al BOT Simplix,

utilizzandolo come funzione di fitness alternativa.

3

Capitolo 2

Stato dell’arte

All’interno dei racing games il livello di realismo e decisamente aumentato

nell’arco degli ultimi 40 anni, passando da semplici giochi in cui l’obiettivo

era rimanere all’interno di un tracciato, a sfide sempre piu avvincenti contro

player umani e virtuali (fig. 2.1). Per far sı che l’utente possa giocare contro

player virtuali pero, e necessario che a questi venga fornita una traiettoria (o

racing line) da seguire durante la gara.

(a) Gran Track 10. (b) F1 2011.

Figura 2.1: Evoluzione dei racing game

In questo capitolo descriveremo innanzi tutto come l’intelligenza artificiale

e utilizzata all’interno dei racing games, in seguito TORCS, il simulatore usato

per lo scopo di questa tesi, ed infine illustreremo gli studi piu rilevanti effettuati

nell’ambito della generazione automatica di racing line.

Stato dell’arte

2.1 L’intelligenza artificiale nei racing games

All’interno dei racing games e necessario l’utilizzo di un’intelligenza artificiale

affinche il player abbia dei rivali virtuali che si comportino nel modo piu rea-

listico possibile, rendendo cosı l’esperienza di gioco dell’utente appassionante.

Alcuni dei piu recenti lavori relativi ai racing games e stato svolto da Togelius

et al. utilizzando un semplice car racing game 2D realizzato in java. In [34, 35],

Togelius et al. investigano su vari schemi di informazioni sensoriali (in prima

persona, in terza persona, etc.) studiando la capacita di generalizzazione dei

controllori evoluti. Piu recentemente, Cardamone et al. [7, 6] hanno applicato

la neuroevoluzione per addestrare un comportamento di guida e di sorpasso,

nell’ambito di un sofisticato simulatore di gare automobilistiche (TORCS ).

Il problema del sorpasso e stato inoltre considerato in [29] usando un’ar-

chitettura fuzzy modulare, e in [23] sfruttando un approccio di apprendimento

per rinforzo. Diversi lavori, come [26] [8] [36], applicano l’apprendimento per

imitazione partendo da dati relativi ad esseri umani in modo da generare stili

di guida piu realistici. In [37] e all’interno di [9], gli algoritmi genetici sono

stati applicati per ottimizzare il setup di un macchina da corsa, utilizzando

rispettivamente i giochi Formula One Challenge e TORCS.

Alcuni dei piu recenti lavori [31, 5, 28] riguardanti i racing game hanno

origine dalla partecipazione alla Simulated Car Racing Championship [22], una

competizione internazionale organizzata da Loiacono et al. dove l’obiettivo e

quello di sviluppare il miglior guidatore per TORCS capace di gareggiare da

solo e contro altri sfidanti.

2.1.1 TORCS

TORCS, The Open Racing Car Simulator, e un videogioco di corse 3D open

source basato su tecnologie OpenGL. Il progetto TORCS nacque nel 1997

grazie al lavoro di due programmatori francesi: Eric Espie e Christophe Guion-

neau. Scritto in C++, TORCS e stato sviluppato principalmente con l’idea di

permettere delle sfide tra programmatori nello sviluppo di robot. Il software

6

2.1 L’intelligenza artificiale nei racing games

simula un ambiente tridimensionale completo e implementa un motore molto

complesso per la gestione della fisica, che considera tutti gli aspetti di una

vera auto da corsa, come l’entita dei danni, il consumo di carburante, l’uti-

lizzo della frizione, l’aerodinamica e molto altro. In questo aspetto, il gioco e

molto completo ed e in grado di competere allo stesso livello con molti giochi

commerciali attualmente sul mercato. Inoltre il software e ben strutturato per

semplificare eventuali apporti di modifiche [1].

Figura 2.2: TORCS: schermata di gioco

In Figura 2.2 e rappresentata un’immagine di TORCS in azione. TORCS

presenta un ambiente molto interessante per esperimenti sull’intelligenza com-

putazionale. Il suo codice e open source: questa caratteristica e cruciale per

adattare TORCS allo sviluppo di esperimenti di questo tipo.

7

Stato dell’arte

2.2 Il problema della racing line

Affinche una macchina possa girare all’interno di una pista in maniera com-

petitiva, deve poter sostenere alte velocita in ogni punto del tracciato. Date

le caratteristiche della macchina, guidare ad alte velocita e facilitato prin-

cipalmente dall’inseguire la linea che consente la miglior prestazione possibile

all’interno dei limiti del tracciato. Questa linea e spesso chiamata “racing line”

o “traiettoria” (fig. 2.3). La realizzazione di una buona racing line comporta

la necessita di trovare un giusto trade-off tra due problemi contrapposti. Il

primo e quello di riuscire a percorrere il percorso piu breve possibile, mentre

il secondo richiede di seguire il percorso che garantisce la massima velocita.

Chiaramente i due non coincidono, basti pensare a una semplice curva, in cui

il percorso piu breve si trova percorrendo la pista in prossimita del lato interno,

mentre per affrontarla con velocita elevata e necessario compiere un percorso

con raggio di curvatura elevato.

Figura 2.3: Esempio di racing line

8


La necessita di creare una racing line nasce dal fatto che all’interno di un

racing game, i player virtuali hanno bisogno di conoscere la traiettoria da se-

guire durante una gara. La racing line puo essere ben identificata da un pilota

esperto. Un modo ovvio per farlo e provare piu volte la pista in questione

e determinarla. Ci sono diversi scenari in cui il designer deve calcolare varie

racing line ottime in base alle caratteristiche del videogioco, dell’ambiente in

cui sono inserite (asfalto, sterrato...) e in base ai tipi di mezzi che partecipe-

ranno alla competizione. Una racing line puo essere precalcolata o calcolata

dinamicamente, ma in entrambi i modi e necessario basarsi sulle caratteristi-

che del tracciato. Progettare diverse racing line e chiaramente un processo

lungo, laborioso e potenzialmente non privo di errori. Ad oggi, all’interno del-

la comunita che si occupa di ricerca nei videogiochi, vi sono solamente pochi

lavori riguardanti la generazione automatica di una racing line usando semplici

euristiche [3] [11] [14].

2.2.1 Studi correlati

Trovare la miglior traiettoria di gara possibile, per una determinata macchina,

dato un tracciato, e uno dei problemi che gli sviluppatori di racing game devono

risolvere. I giochi in commercio tipicamente si basano su traiettorie disegnate

da un esperto [21]. Le poche eccezioni a questo approccio umano includono

Colin McRae Rally1 (Codemaster), dove la racing line e calcolata tramite una

rete neurale addestrata da un esperto di dominio, e Forza Motorsport2 series

(Microsoft) dove le tecniche di supervised learning sono sfruttate per istruire

le AIs e la computazione evolutiva e applicata per ottimizzare le loro traiet-

torie. I racing gamen Open-source solitamente fanno affidamento su approcci

di tipo euristico. Gli esempi di maggior successo che utilizzano questo tipo di

approccio comprendono: l’algoritmo K1999 [11], sviluppato da Remi Coulom;

Simplix [3] sviluppato da Wolf-Dieter Beelitz per “The Open Car Racing Simu-

lator” (TORCS ) [1], basato su una semplice euristica; il BOT di Jussi Pajala

1http://en.wikipedia.org/wiki/Colin_McRae_Rally2http://en.wikipedia.org/wiki/Forza_Motorsport

9

Stato dell’arte

per “the Robot Auto Racing Simulator” (RARS) [2] che applica A*; DougE1

BOT per RARS di Doug Elenveld che utilizza gli algoritmi genetici, Nono-

stante si basino su tecniche differenti, tutti gli approcci precedenti sfruttano

un’euristica simile che cerca di ridurre il piu possibile la curvatura della racing

line. Infatti, minore e la curvatura della traiettoria, maggiore sara la velocita

raggiungibile senza perdere grip. Dall’altro lato, Casanova [12] mostra che

per trovare la miglior racing line e necessario tenere in considerazione diversi

aspetti dinamici della macchina quali il punto di frenata rispetto al tracciato,

la capacita di accelerazione della macchina, i cambi di direzione, etc. Benche

molto forte, l’approccio mostrato al’interno di [12] richiede un modello formale

del veicolo e delle sue interazioni con l’ambiente di gara molto dettagliato, che

solitamente non e disponibile nei racing game. Piu recentemente, Braghin

et al. [4] suggeriscono di calcolare la racing line come trade-off tra la mini-

mizzazione della distanza di gara e la minimizzazione della curvatura nella

traiettoria da seguire. In particolare, Braghin et al. [4] definisce il problema di

trovare la racing line ottima come un problema di programmazione quadratica.

Infine, il problema di calcolare una buona traiettoria e correlato al path e al

trajectory planning, un problema che e stato ampliamente studiato nel campo

della robotica mobile e dei veicoli autonomi [17, 32, 18, 19, 20, 13, 30, 27, 10].

Inoltre nel febbraio 2011 Microsoft ha registrato un brevetto riguardante un

nuovo approccio per l’ottimizzazione di una racing line [25]. Normalmente,

una “buona racing line” e essenzialmente una linea con una bassa curvatura

geometrica, che rimanga all’interno del tracciato. Questo perche la bassa cur-

vatura e d’aiuto alla velocita, dal momento che in un angolo, supponendo che

la macchina abbia un limite di trazione laterale, la massima velocita sostenibile

e inversamente proporzionale alla curvatura della traiettoria che si appresta a

seguire. I ricercatori di Microsoft [25] basandosi su questo principio, ed uti-

lizzando un adeguato livello di approssimazione, hanno ricavato un algoritmo

che calcola la racing line minimizzando la curvatura della traiettoria utilizzan-

do un processo di ottimizzazione gradient-based. Questa linea ricavata non e

necessariamente la migliore, ma e molto vicina a quella che puo esser giudicata

la miglior traiettoria possibile.

10


Figura 2.4: Un esempio di come viene decomposto un tracciato basandosi sulle

intersezioni tra il cammino minimo (SP) e il cammino a minima curvatura (MCP)

Un ulteriore approccio a questo problema e quello applicato da Cardamone

et al. in [24]. In questo lavoro, date due traiettorie precalcolate, una valutando

il cammino minimo (SP), ed una cercando la minima curvatura (MCP), viene

utilizzato un algoritmo genetico per generare una racing line come trade-off

tra le due. In [24] la racing line e definita come una sequenza ~P1, . . . , ~Pn di

punti nel tracciato, dove l’ultimo punto ~Pn e connesso al primo ~P1. Un modo

conveniente per rappresentare ogni punto ~Pi della racing line e quello di utiliz-

zare la tupla 〈δi, αi〉, dove αi e la distanza laterale del punto da uno dei bordi

del tracciato (per esempio dal bordo destro), normalizzato per la larghezza

del tracciato W mentre, δ e la distanza del punto dalla linea di partenza del

tracciato, calcolata facendo riferimento agli assi della pista. Questo lavoro se-

gue l’approccio presentato in [4], inoltre viene assunto che i punti della racing

line siano equalmente distanti, qundi per ogni i ∈ {1, . . . , n − 1}, δi+1 − δi e

costante. Per applicare l’algoritmo genetico alla ricerca di una racing line, e

stata decomposta la pista in varie sezioni t1, · · · , tm. Il punto iniziale e finale

di ogni sezione del tracciato sono identificati dalle interseziono fra lo shortest

11

Stato dell’arte

path e il cammino a minima curvatura. Percio, la sezione tj della pista, e

definita come la parte compresa tra le intersezioni j − th e (j + 1) − th tra

il cammino minimo e il cammino a curvatura minima. La figura 2.4 mostra

un esempio di come viene decomposta un tracciato. Sulla base delle decom-

posizione del tracciato illustrata precedentemente, ogni soluzione candidata e

semplicemente codificata come un vettore di pesi εt1 , · · · , εtm , dove εtj regola

la combinazione convessa tra i due cammini nella sezione tj del tracciato. Af-

finche si possa valutare una soluzione e necessario un procedimento diviso in

due passi. Innanzitutto viene decodificato il genoma, in modo che si trasformi

in una traiettoria. Quindi per ogni sezione tj del tracciato il cammino minimo

e la minima curvatura sono combinati in accordo al peso εtj come segue:

αi = αSP,i · εtj + αMCP,i · (1− εtj ) ∀~Pi ∈ tj (2.1)

dove αi e la deviazione laterale del i−esimo punto ~Pi della racing line calcolata;

mentre αMCP,i e αSP,i sono le deviazioni laterali degli i− esimi punti apparte-

nenti al cammino minimo e al cammino a minima curvatura. Successivamente

per valutare la racing line ottenuta viene effettuata una simulazione. La fun-

zione di fitness viene calcolata in base al lap time restituito dalla simulazione.

Il lavoro di Cardamone et al. [24] e stato ampiamente illustrato perche anche

nel nostro elaborato utilizzeremo una rappresentazione simile della racing line,

e poiche anche noi sfrutteremo un meccanismo di ottimizzazione evolutiva per

la ricerca della traiettoria ottima.

12

Capitolo 3

Rappresentazione della racing

line

Una racing line e definita come una sequenza ~P1, . . . , ~Pn di punti nel tracciato,

dove l’ultimo punto ~Pn e connesso al primo ~P1. Il problema principale risiede

nel definire una rappresentazione compatta per la realizzazione di quest’ulti-

ma, ossia un rappresentazione che riesca a generare curve diverse modificando

il minor numero di parametri possibile. La nostra scelta e ricaduta sull’utilizzo

delle curve di Bezier, poiche quest’ultime sono facilmente realizzabili e modi-

ficabili. Infatti le forme che esse possono assumere dipendono esclusivamente

dalla posizione dei loro punti di controllo. Nel paragrafo successivo daremo

una visione generica di cosa sia una curva di Bezier e come viene realizzata la

nostra rappresentazione.

3.1 Le curve di Bezier

Una curva di Bezier e una curva parametrica usata frequentemente nel cam-

po della computer graphics e in campi collegati. Le curve di Bezier furono

largamente pubblicizzate nel 1962 dall’ingegnere francese Pierre Bezier che le

uso per disegnare le carrozzerie delle automobili. Le curve furono realizzate

nel 1959 da Paul de Casteljau usando l’algoritmo di De Casteljau, un metodo

Rappresentazione della racing line

numerico stabile per la valutazione di queste curve. Gli utilizzi principali di

queste curve sono nel campo della computer grafica, dell’animazione e della

creazione di fonts.

3.1.1 Definizione matematica della curva

Una curva di Bezier (fig. 3.1) e definita dal suo ordine e da un insieme di

punti di controllo da P0 a Pn. Il numero n dei punti di controllo dipende

dall’ordine della curva. Il primo e l’ultimo sono sempre i punti estremi della

curva; comunque, i punti di controllo intermedi (se esistono) generalmente non

giacciono sulla curva.

Figura 3.1: Esempio di una curva di Bezier

Curve lineari Dati i punti P0 e P1, una Bezier lineare e semplicemente una

linea retta condotta tra quei punti. La curva e data da:

B(t) = (1− t)P0 + tP1, t ǫ [0, 1] (3.1)

ed e equivalente ad un’interpolazione lineare.

14


Curve quadratiche Una Bezier quadratica rappresenta il cammino tracciato

dalla funzione B(t), dati i punti P0, P1 e P2:

B(t) = (1− t)2P0 + 2t(1− t)P1 + t2P2, t ǫ [0, 1] (3.2)

Una Bezier quadratica e un segmento parabolico. Dato che una parabola

e una sezione conica, alcune fonti riferiscono la Bezier quadratica come

“arco di cono”.

Generalizzazione Una curva di Bezier puo essere definita per ogni grado n.

• Una definizione ricorsiva la esprime come un’interpolazione lineare

tra due curve di Bezier di grado n − 1. Sia BP0,P1,...,Pnla curva

determinata dai punti P0, P1, ..., Pn, allora dato BP0(t) = P0 come

punto iniziale, si ha

B(t) = BP0,P1,...,Pn(t) = (1−t)BP0,P1,...,Pn−1

(t)+tBP1,P2,...,Pn(t) (3.3)

• Altrimenti puo essere generalizzata come segue. Dati i punti

P0, P1, ..., Pn, la curva e definita da:

B(t) =n

∑

i=0

(

n

i

)

Pi(1− t)n−iti, t ǫ [0, 1] (3.4)

Il poligono formato connettendo i punti attraverso linee rette, iniziando

da P0 e finendo con Pn e l’insieme convesso contenente i punti Pi. Questo

poligono e chiamato poligono di Bezier, ed esso contiene la curva di

Bezier.

3.1.2 Proprieta

• Interpolazione dei punti estremi: la curva comincia a P0 e finisce a Pn;

• La curva e una linea retta se e solo se i punti di controllo sono collineari.

• L’inizio (fine) della curva e tangente alla prima (ultima) sezione del

poligono di Bezier.

15


• Una curva puo essere divisa in ogni punto in due sottocurve, o in un

numero arbitrario di sottocurve, ognuna delle quali e essa stessa una

curva di Bezier.

• Molte curve che sembrano semplici, come un cerchio, non possono es-

sere descritte esattamente tramite una Bezier o segmenti di Bezier, ma

quest’ultime possono essere considerate una loro buona approssimazione.

3.1.3 Costruzione delle curve di Bezier

Curve lineari: Il t nella funzione di una curva di Bezier lineare puo essere

pensato come la descrizione del tragitto di B(t) da P0 a P1. Per esempio

quando t = 0.25, B(t) e un quarto del percorso da P0 a P1. Al variare di

t da 0 a 1, B(t) descrive l’intero segmento compreso tra P0 e P1.

Curve quadratiche: Per le curve quadratiche di Bezier (fig. 3.2) si possono

costruire punti intermedi Q0 e Q1 al variare di t da 0 a 1:

• Il punto Q0 varia da P0 a P1 e descrive una curva lineare di Bezier.

• Il punto Q1 varia da P1 a P2 e descrive una curva lineare di Bezier.

• Il punto B(t) varia da Q0 a Q1 e descrive una curva quadratica di

Bezier.

Figura 3.2: Costruzione di una Bezier di secondo grado

16


Curve di ordine superiore: per queste curve e necessario un maggior nu-

mero di punti intermedi. Per una curva cubica (fig. 3.3(a)) si possono

costruire i punti Q0, Q1 e Q2 che descrivono una curva di Bezier lineare,

e i punti R0 e R1 che descrivono una curva di Bezier quadratica. Sup-

poniamo invece di avere una curva di quarto ordine (fig. 3.3(b)). Sara

necessario costruire dei punti intermedi Q0, Q1, Q2 e Q3 che descrivono

curve di Bezier lineari, i punti R0, R1 e R2 che descrivono curve qua-

dratiche di Bezier, e i punti S0 e S1 che descrivono una curva di Bezier

cubica. Ora, il punto B(t) descrivera la nostra curva di Bezier.

(a) Costruzione di una Bezier cubica (b) Costruzione di una Bezier di qarto

grado

Figura 3.3: Curve di Bezier di ordine superiore al secondo

17


3.2 Rappresentazione della racing line con

curve di Bezier

Una volta determinato il tipo di curva, e necessario stabilire come implemen-

tare la rappresentazione, e quali saranno i parametri che ci permetteranno di

creare curve sempre diverse. Date le caratteristiche della curva di Bezier, ci

sembra naturale far ricadere tale scelta sui punti di controllo, dato che grazie

ad essi possiamo manovrare l’intera curva. Per far cio, sara necessario seguire

alcuni semplici passi.

• Divisione del circuito in sezioni, per rendere il calcolo piu agile.

• Definizione della traiettoria come curva di Bezier.

• Calcolo del numero di punti di controllo necessari al fine di poter

rappresentare una traiettoria plausibile ed efficace.

• Calcolo della curva di Bezier rappresentata dai punti precedentemente

elaborati, e conversione della rappresentazione.

Nei prossimi paragrafi descriveremo piu nel dettaglio i vari passi.

3.2.1 Divisione del circuito in sezioni

Supponiamo di sapere il numero di punti di controllo utilizzati nella rappre-

sentazione. Se questo numero e troppo elevato, il calcolo della curva risultera

decisamente oneroso. Per questo motivo, puo essere una buona scelta dividere

il circuito in sezioni, ognuna con la propria curva di Bezier rappresentativa.

Il tutto si trasforma quindi in n sottoproblemi parzialmente indipendenti, i

quali semplificano notevolmente i processi di elaborazione e creazione della

rappresentazione. La motivazione per cui le sottocurve rimangono parzial-

mente dipendenti tra loro risiede nella necessita di rendere continui tra loro i

vari segmenti di racing line. Per far cio, definiamo a priori il numero massimo

di punti di controllo presenti all’interno di una sezione, esclusa l’ultima che

conterra un numero di punti variabile.

18

3.2 Rappresentazione della racing line con curve di Bezier

3.2.2 Definizione della rappresentazione come curva di

Bezier

Affinche la rappresentazione non gravi ulteriormente sul costo computazionale,

bisogna trovare il modo di far dipendere la curva dal minor numero di para-

metri possibile. Visto che la curva di Bezier dipende solo dalla posizione dei

suoi punti di controllo, abbiamo realizzato la rappresentazione in modo da far

dipendere la posizione di un punto di controllo da un solo parametro. Questo

ci permettera, in fase di ottimizzazione, di avere un numero di incognite uguale

al numero di punti di controllo. Dato che la posizione di un punto nel piano

dipende dalle sue coordinate (x, y), abbiamo optato, col fine di diminuire i

gradi di liberta, per vincolare la posizione di quest’ultimo lungo una retta che

unisce due punti dei bordi del tracciato in corrispondenza della stessa distanza,

lungo il tracciato, dal punto di partenza (Figura 3.4).

Figura 3.4: Esempio di movimento di un punto di controllo. In rosso e rappre-

sentato il punto di controllo, mentre in verde la retta di riferimento su cui puo

muoversi

Una volta ottenute le sezioni, si puo partire con l’algoritmo 1. La prima

sezione non presenta particolari problemi, si tratta di calcolare la posizione

dei punti di controllo. Questi punti si muoveranno in percentuale in base al

valore del relativo parametro dato in input, sulla retta di riferimento. Nelle

19


sezioni intermedie, oltre a calcolare la posizione dei punti, bisogna imporre la

continuita tra una sezione e l’altra, in modo che il tracciato risultante sia privo

di punti angolosi, difficilmente seguibili con una macchina. Al fine di ottenere

questo risultato e necessario che il primo segmento del poligono di Bezier della

i−esima e l’ultimo segmento del poligono della (i−1)−esima siano collineari.

Il secondo punto della sezione in analisi, che e quello interessato dal problema

della continuita, non si muovera sulla solita retta, ma sul segmento collineare

all’ultima parte del poligono di Bezier della sezione precedente che arriva ad

intersecarsi con l’usuale retta di riferimento (figura 3.5), della percentuale data

dal parametro in input.

Figura 3.5: Esempio di movimento di un punto di controllo. In rosso sono rappre-

sentati i punti di controllo collineari, in marrone le due usuali rette di riferimento,

in ciano la fine di una sezione e in verde il segmento su cui il secondo punto di

controllo della sezione puo muoversi

Il ragionamento e identico per l’ultima sezione della pista, con l’aggiunta

dell’imposizione della continuita anche con la prima sezione del tracciato in

modo che anche alla fine la traiettoria sia priva di discontinuita di primo e

secondo ordine.

20


Algorithm 1 Calcolo della posizione dei punti di controllo

1: for (Sezioni) do

2: if (Prima Sezione) then

3: for (Punti di controllo nella sezione) do

4: Calcolo la posizione;

5: end for

6: else if (Sezione Intermedia) then

7: for (Punti di controllo nella sezione ) do

8: if (Primo Punto) then

9: Impongo la continuita con la sezione precedente;


11: else(Altri Punti)


13: end if

14: end for

15: else if (Ultima Sezione) then

16: for (Punti di controllo nella sezione) do

17: if (Primo Punto) then

18: Impongo la continuita con la sezione precedente;


20: else if (Punti Intermedi) then


22: else if (Ultimo Punto) then

23: Impongo la continuita con la prima sezione;


25: end if

26: end for

27: end if

28: end for

Nella figura 3.6 seguente e possibile vedere uno scorcio di traiettoria

riassuntivo di quanto illustrato fino ad ora.

21


510 520 530 540 550 560 570 580 590

560

570

580

590

600

610

620

630

Figura 3.6: Esempio di posizione dei punti di controllo; in verde e rappresentata

la racing line, definita dai punti di controllo in rosso, i quali si possono muovere

lungo le linee tratteggiate in blu; la linea in ciano rappresenta la fine di una sezione

3.2.3 Identificazione del numero di punti di controllo

necessari

Il numero di punti di controllo da utilizzare in una rappresentazione e un

parametro delicato, in quanto un numero troppo esiguo porta a non realizzare

una curva efficace e valida per una traiettoria, mentre un numero troppo elevato

appesantisce in maniera notevole la rappresentazione rendendo la successiva

fase di ottimizzazione computazionalmente onerosa.

Per far cio bisogna quindi definire alcuni parametri che ci permettano di

trovare il giusto compromesso tra le due situazioni sopra citate. Vediamo quali

sono questi parametri.

• SogliaCurvatura (SC): questo parametro definisce la massima curvatura

cumulabile all’interno di una sezione compresa tra due punti di controllo;

22


• FinestraCampionamento (FC): rappresenta la finestra di campionamen-

to, ossia ogni quanto controlliamo il livello di curvatura;

• MaxSpazio (MS): in caso la soglia non sia raggiunta prima di questo

numero di confronti, inseriamo comunque un punto di controllo (serve

soprattutto all’interno di rettilinei per permettere di seguire traiettorie

che non siano esclusivamente lineari).

Una volta definiti i parametri dobbiamo calcolare la curvatura per ogni

punto del tracciato. Per fare cio applichiamo la formula per il calcolo del

raggio di una circonferenza circoscritta ad un triangolo:

R =abc

4A(3.5)

dove a, b e c rappresentano i lati del triangolo inscritto, e A e l’area calcolata

con al formula di Erone. Dato che la curvatura e l’inverso del raggio, ci basta

invertire il risultato ottenuto dall’equazione (3.5) per ricavare il valore cercato.

Fissiamo il primo e l’ultimo punto di controllo in concomintanza dell’inizio del

tracciato, in modo che la traiettoria inizi e finisca nello stesso punto. Succes-

sivamente sommiamo la curvatura di ogni punto analizzato in base al valore

di FC e, nel caso in cui questa superi la SC, salviamo l’indice che identifichera

la posizione relativa all’interno del tracciato del punto di controllo. Inoltre

abbiamo fatto in modo che non intercorra troppo spazio tra due punti di con-

trollo poiche non e detto che la traiettoria migliore all’interno di una zona della

pista con un basso livello di curvatura sia una retta. Cosi facendo otteniamo il

numero e la posizione relativa alla totalita del tracciato dei punti di controllo

(algoritmo 2).

23


Algorithm 2 Identificazione del numero e posizione relativa all’interno del

tracciato dei punti di controllo

1: Carica la pista;

2: for (Dimensione della pista) do

3: Calcolo della curvatura di ogni punto;

4: end for

5: Fisso l’indice del primo punto di controllo all’inizio del traccaito

6: for (i=0: FinestraCampionamento: Dimensione della pista) do

7: Sommo il valore delle curvature dei punti;

8: if (SogliaCurvatura superata) || (MaxSpazio tra due punti superato)

then

9: Fisso l’indice del punto di controllo;

10: end if

11: end for

12: Fisso l’indice dell’ultimo punto di controllo uguale al primo;

3.2.4 Calcolo della curva di Bezier e conversione della

rappresentazione

Calcolate le coordinate dei punti di controllo, abbiamo tutti gli elementi per

identificare i punti che comporranno la nostra traiettoria vera e propria (fig.

3.7). A tal fine utilizziamo la formula generica (3.4). Ai fini implemen-

tativi abbiamo utilizzato per il calcolo del coefficiente binomiale la formula

moltiplicativa (3.6), evitando cosi di incorrere in errori di overflow.

(

n

i

)

=

k∏

i=1

n− (k − i)

i(3.6)

Ottenuta la curva di Bezier, il modello va ampliato affinche l’inseguitore sia

in grado di leggere la traiettoria. Per fare cio e necesserio passare, per ogni

punto della racing line, dalla rappresentzione cartesiana (xi,yi) a quella basata

sulle ascisse curvilinee (δi,αi). δi identifica la distanza del punto i− esimo dal

punto di partenza, mentre αi rappresenta la distanza dal centro del tracciato

con valori compresi tra (-1.1,1.1).

24


(a) Punti di controllo scalati con valore 0.1

(b) Punti di controllo scalati con valore 0.8

Figura 3.7: Tracciati calcolati con diversi valori dei punti di controllo

25

Capitolo 4

Ottimizzazione della traiettoria

All’interno di questo capitolo illustreremo il processo utilizzato per ottimizzare

una racing line rappresentata col metodo mostrato in precedenza. Ci dedi-

cheremo innanzi tutto a una definizione del metodo che utilizzeremo, ossia un

algoritmo genetico, soffermandoci sui caratteri fondamentali che caratterizzano

il nostro approccio. Inizieremo percio con introdurre la codifica della soluzio-

ne al problema, illustrando successivamente come verra calcolata la funzione

obiettivo nella nostra evoluzione.

4.1 Metodi di ottimizzazione

Definita la rappresentazione da utilizzare, si deve scegliere come ricercare una

soluzione ottima. Per fare cio esistono principalmente due approcci. I metodi

locali, i quali convergono in maniera deterministica ad un massimo (minimo)

locale della funzione obiettivo, fissato un valore dei parametri iniziali, e i me-

todi globali, i quali convergono in maniera stocastica ad un valore prossimo al

massimo (minimo) assoluto della funzione obiettivo, sempre dopo aver fissato

il valore iniziale dei parametri.

Dato che, come mostrato nel capitolo precedente, la nostra rappresentazio-

ne dipende potenzialmente da un numero elevato di parametri e la funzione

obiettivo e difficilmente esprimibile matematicamente, in questo elaborato e

stato scelto un approccio di tipo globale, ed in particolare verra utilizzato un


Metodi locali Metodi globali

sono rapidi sono di lenta convergenza

sono fortemente influenzati dalla scel-

ta dei parametri iniziali

dipendono molto poco dalla soluzione

iniziale

richiedono che la funzione obiettivo

abbia opportune proprieta matemati-

che

non richiedono particolari proprieta

della funzione obiettivo

problemi con un alto numero di

parametri diventano intrattabili

permettono di studiare problemi con

un elevato numero di parametri

producono un insieme di soluzioni

sub-ottimali (oltre quella ottimale)

richiedono la taratura (in base alla

esperienza) di parecchi parametri di

simulazione

Tabella 4.1: Caratteristiche dei metodi di ottimizzazione

metodo evolutivo. In particolare per il nostro studio abbiamo utilizzato un

tool gia esistente. Questo tool, che noi denomineremo per semplicita GAtool-

box [33], offre diversi tipi di selection, ricombinazione, mutazione, niching, e

gestione dei vincoli, dando la possibilita di risolvere problemi mono e multi

obiettivo. Inoltre il tool e facilmente estendibile e modificabile per permettere

l’inserimento di altri operatori e per risolvere problemi ad-hoc.

4.2 Codifica della soluzione

La creazione di una traiettoria casuale tramite curve di Bezier e relativamente

semplice. Dato che la curva di Bezier si basa su dei punti di controllo, basta

modificare la posizione di questi punti per ottenere traiettorie sempre diverse.

Naturalmente viene impedita la creazione di traiettorie che escano dai limiti

del circuito oltre una certa soglia, e per far cio, dato che la posizione dei punti

28

4.2 Codifica della soluzione

di controllo si puo muovere tramite un parametro α su una retta che collega due

punti corrispondenti dei bordi della pista, il valore di questa α sara vincolato

all’interno del range [-0.1,1.1]. Il genoma sara quindi composto da un numero

di geni uguale al numero di punti di controllo che definiscono la traiettoria in

questione, ed ognuno di questi conterra il valore dell’α corrispondente.

0.8 0.5 0.6 0.33 0.45 0.92 1.1 0.79 0.2 0.57

0.92 0.71 0.48 0.21 -0.03

Tabella 4.2: Esempio di codifica di un genoma

350 400 450 500 550 600 650 700

−10

0

10

20

30

40

50

60

70

Figura 4.1: Sezione di un individuo, corrispondente al genoma in tabella 4.2

Una volta ottenuto il miglior genoma (tabella 4.2) questo viene trasforma-

to nella traiettoria corrispondente (fig. 4.1). Per far cio utilizziamo i valori

contenuti nel genoma e li passiamo come dati di input al calcolo della posi-

zione dei punti di controllo, come spiegato nella sezione 3.2, dove ogni gene

rappresentera di quanto il corrispettivo punto di controllo scalera sulla propria

retta di riferimento.

29


4.3 Inizializzazione della popolazione

Il GAtoolbox [33] offre la possibilita di scegliere se fornire o meno in input una

determinata popolazione iniziale. Sfruttando questa caratteristica abbiamo

quindi la possibilita di generare test di vario genere.

Popolazione iniziale casuale: la popolazione iniziale sara generata e valu-

tata direttamente dal tool.

Popolazione iniziale precalcolata:

• un primo scenario prevede come input il passaggio di traiettorie

casuali ma vicine a traiettorie di riferimento, ad esempio racing line

tutte sul bordo esterno, interno o al centro della pista.

• un secondo scenario invece prevede come input le miglior N

traiettorie di un run precedente del tool.

In entrambi i casi si puo scegliere se far valutare gli elementi della po-

polazione iniziale al tool oppure, in caso si sia in possesso delle relative

fitness, inserirne il valore nel file contenente la popolazione iniziale 1.

4.4 Valutazione della bonta della Racing Line,

il calcolo della fitness

La valutazione di quanto una racing line possa essere performante e fonda-

mentale all’interno del processo evolutivo, influenzandone il risultato finale.

La qualita di una racing line viene stimata attraverso il valore di un attributo

chiamato fitness. Maggiore sara il valore della fitness, migliore sara la perfor-

mance su quella particolare racing line. Preso in analisi il genoma interessato

questo viene decodificato, in modo da essere trasformato in una traiettoria.

La decodifica viene effettuata utilizzando gli indici relativi ai punti del bordo

che identificano la retta sul quale possono muoversi i punti di controllo,

1Per la configurazione del tool rimandiamo all’appendice A.

30

4.4 Valutazione della bonta della Racing Line, il calcolo della fitness

precedentemente calcolati. In questo lavoro la valutazione della fitness si basa

sull’utilizza di un BOT, ossia un’automobile dotata di una propria intelligenza

artificiale in grado di seguire una racing line datagli in input, e nello specifico il

follower Simplix [3] opportunamente modificato. In particolare questo follower

ci permette di seguire due strade per la valutazione della funzione obiettivo. La

prima consiste nel valutare il lap time effettivo che il follower impiega per com-

piere un giro di pista. Per far cio lanciamo TORCS simulando una breve gara

sul tracciato in analisi seguendo la traiettoria da valutare e registrando il tempo

ottenuto al secondo giro. Prendendo il tempo risultante e negandolo, otteniamo

la fitness cercata. Maggiore sara quest’ultima, migliore sara la traiettoria cor-

rispondente. Un’altra possibilita consiste nel semplificare il tutto utilizzando

come tempo di giro una stima generata automaticamente da Simplix, dato che

al suo interno ha una funzione che calcola a priori, data la racing line da seguire,

una stima del tempo di percorrenza di un giro. Questo secondo approccio ha un

impatto notevole sui tempi di calcolo dato che permette di interrompere l’esecu-

zione di una run di TORCS prima della simulazione di una gara vera e propria,

che rappresenta il bottleneck dell’intera procedura. Naturalmente i valori otte-

nuti saranno delle stime del valore reale e quindi non saranno precise. Di segui-

to in figura 4.2 riportiamo lo schema di come il GAtollbox esegue una chiamata

di TORCS per ricavare funzione obiettivo relativa a un genoma in analisi.

Figura 4.2: Diagramma rappresentante il calcolo della funzione di fitness

31


4.4.1 Crossover delle traiettorie

Il nostro problema soddisfa la “Building Block Hypotesis” (BBH) [16], infatti

noi cerchiamo di trovare una racing line ottima combinando fra loro buone

sezioni di traiettorie nel complesso non ottime, senza mischiare quindi tutte

le possibili combinazioni, riducendo cosı la complessita del problema. Nelle

figure successive e possibile vedere due traiettorie prima (fig.4.3) e dopo il

crossover (fig.4.4(a) e fig.4.5(a)). Possiamo notare come nonostante si siano

prese due traiettorie completamente differenti, una volta effettuato il crossover,

le caratteristiche di continuita e permanenza all’interno del tracciato vengano

mantenute.

Figura 4.3: Due generiche traiettorie

32

4.4 Valutazione della bonta della Racing Line, il calcolo della fitness

(a) Primo figlio generato mischiando le traiettorie della fig. 4.3

(b) Punto di interesse: inizio pista (c) Punto di interesse: punto di taglio

Figura 4.4: Primo risultato Crossover

(a) Secondo figlio generato mischiando le traiettorie della fig. 4.3

(b) Punto di interesse: inizio pista (c) Punto di interesse: punto di taglio

Figura 4.5: Secondo risultato Crossover

33

Capitolo 5

Analisi sperimentale

In questo capitolo illustreremo tutte le analisi effettuate per valutare l’efficacia

e il funzionamanto della nostra rappresentazione. In particolare prenderemo in

analisi alcuni tracciati gia utilizzati in lavori precedenti [24] in modo da avere

dei termini di paragone. Studieremo il nostro modello con diverse variabili

quali la presenza o meno di una popolazione iniziale e l’utilizzo di due diverse

tipologie di funzione obiettivo, simulata o stimata. Come prima analisi ab-

biamo verificato l’efficienza della nostra rappresentazione, in modo da essere

sicuri che i risultati pratici rispecchino gli studi teorici. In seguito illustreremo

le scelte preliminari adottate in sede di analisi, ossia quali tracciati all’interno

dei possibili circuiti forniti da TORCS verranno utilizzati per gli esperimenti

e quali saranno i valori dei parametri utilizzati per la definizione dei punti

di controllo. Inoltre verrano identificati i parametri chiave per l’evoluzione

dell’algoritmo genetico. A questo punto analizzeremo la nostra rappresenta-

zione tramite due diverse funzioni obiettivo, la prima simulando una breve

gara mentre la seconda stimando un tempo plausibile di percorrenza della

traiettoria.


5.1 Validazione della rappresentazione del

tracciato

La prima analisi da effettuare riguarda l’efficacia della rappresentazione nel

raffigurare delle traiettorie. Per verificarne la validita abbiamo cercato di rea-

lizzare delle semplici curve casuali all’interno del tracciato, tentando di copiare

delle buone traiettorie gia esistenti (fig 5.1) e calcolando le traiettorie a mini-

ma distanza (SP) e minima curvatura (MCP). A tal scopo abbiamo utilizzato

degli script in Matlab e la funzione fminsearch presente nel tool come funzione

ottimizzatrice. In particolare abbiamo creato una funzione di costo usata dal

metodo fminsearch per stimare la bonta della soluzione (algoritmo 3).

Algorithm 3 Funzione di costo per la copiatura di una traiettoria gia esistente.

1: for (Sezione) do

2: Trova la sezione corrispondete di Simplix ;

3: Calcola Bezier;

4: for (Punti della curva di Bezier nella sezione) do

5: Trovo il punto piu vicino di Simplix ;

6: Calcola la distanza;

7: end for

8: end for

I risultati ottenuti possono essere considerati validi, infatti siamo riusci-

ti a dimostrare che una racing line gia esistente puo essere ottenuta con la

nostra rappresentazione, con un errore poco significativo, come si puo notare

graficamente in figura 5.1.

36

5.2 Scelte sperimentali

Figura 5.1: Esempio di copia di una traiettoria. In rosso e rappresentata la racing

line di Simplix, in verde la nostra “copiata”


Prima di iniziare la fase di analisi vera e propria, e necessario stabilire alcuni

punti cardine fondamentali per l’evoluzione del lavoro. Vanno infatti definiti

quali circuiti verranno presi in considerazione durante i test, quali siano i valori

ottimali per i parametri che definiscono le caratteristiche dei punti di controllo

relativi alle curve di Bezier (SC, FC e MS), la dimensione della popolazione e

il numero di generazioni dell’algoritmo genetico.

5.2.1 Tracciati analizzati

TORCS possiede al suo interno una vasta gamma di circuiti, quindi per validare

il nostro studio abbiamo deciso di analizzare una serie di tracciati con caratte-

ristiche diverse fra loro. L’analisi di partenza e stata effettuata su A-Speedway,

un tracciato semplice e veloce, il quale non richiede particolari traiettorie dato

37


che non contiene chicane e curve a gomito. Questo ci ha permesso di identifi-

care inizialmente dei valori validi per i parametri di interesse da cui partire. In

tabella 5.1 vengono mostrate le caratteristiche principali1 e la conformazione

delle piste da noi utilizzate.

A-speedway Length: 1908.32 m Alpine-2 Length: 3775.57 m

Width: 25 m Width: 10 m

Lap Time: 27.558 s Lap Time: 94.334 s

Track Points: 19087 Track Points: 37723

CG-speedway Length: 2057.56 m Ruudskogen Length: 3274.20 m

Width: 15 m Width: 11

Lap Time: 40.120 s Lap Time: 69.208s

Track Points: 20580 Track Points: 32734

Wheel-1 Length: 4257.62 m

Width: 16 m

Lap Time: 73.924 s

Track Points: 42559

Tabella 5.1: Tracciati utilizzati nella nostra analisi

5.2.2 Scelta dei parametri della rappresentazione

Per effettuare i vari test abbiamo innanzi tutto identificato i valori dei parame-

tri SC, FC e MS, gia illustrati nella sezione 3.2.3, da utilizzare per la selezione

dei punti di controllo. Di seguito riportiamo una tabella contenente il numero

di punti di controllo al variare di questi parametri.

1Il lap time indicato e ottenuto tramite il BOT Simplix

38


Tracciato SC FC MS N

A-speedway

0.025 25 375 115

0.025 50 750 58

0.05 25 375 75

0.05 50 750 38

0.075 25 375 62

0.075 50 750 31

Alpine-2

0.025 25 375 365

0.025 50 750 177

0.05 25 375 234

0.05 50 750 113

0.075 25 375 181

0.075 50 750 86

CG-Speedway

0.025 25 375 175

0.025 50 750 86

0.05 25 375 100

0.05 50 750 49

0.075 25 375 76

0.075 50 750 37

Ruudskogen

0.025 25 375 258

0.025 50 750 127

0.05 25 375 159

0.05 50 750 79

0.075 25 375 126

0.075 50 750 62

Wheel-1

0.025 25 375 380

0.025 50 750 186

0.05 25 375 237

0.05 50 750 115

0.075 25 375 182

0.075 50 750 88

Tabella 5.2: Variazione del numero di punti di controllo al variare dei parametri

39


Al fine di ottenere una rappresentazione valida, che ci permetta di trovare

una traiettoria efficace in tutte le situazioni, abbiamo deciso come analisi inizia-

le di sovrastimare il numero di punti di controllo, cercando una configurazione

adatta a tutte le conformazioni di tracciati analizzati. Questo ci garantisce

un piu vasto campo di rappresentazione delle traiettorie; infatti, maggiore e il

numero di punti di controllo piu ampia sara la famiglia di curve generabile da

quel numero di punti di controllo. Per coerenza tra le varie analisi abbiamo

mantenuto gli stessi parametri per tutte le piste. In tabella 5.2 sono evidenziati

i parametri scelti per il nostro studio. L’utilizzo di un alto numero di variabili

garantisce una potenza rappresentativa maggiore ma cio viene pagato da un

costo computazionale elevato.

5.2.3 Scelta dei parametri dell’algoritmo genetico

Prima di iniziare a valutare le racing line abbiamo dovuto configurare i due

parametri fondamentali dell’algoritmo genetico:

• Dimensione della popolazione.

• Numero massimo di generazioni.

Per quando riguarda le dimensioni della popolazione abbiamo tenuto in

considerazione il numero di punti di controllo necessari per la rappresentazio-

ne dei tracciati illustrati nella tabella 5.1. Guardando invece la tabella 5.2

possiamo notare che i punti di controllo sono compresi in un intervallo che va

da un minimo di 75 punti necessari per A-speedway a un massimo di 237 per

rapprestare Wheel-1. Quindi si e deciso di utilizzare una popolazione uguale

per tutti i test, di dimensione maggiore al numero di punti di controllo. A tal

proposito nei nostri esperimenti utilizzeremo sempre un popolazione composta

da 300 elementi.

Il valore del numero massimo di generazioni e stato fissato a 300. Questo

valore e stato scelto empiricamantene dopo un’analisi sperimentale volta ad

individuarne il dimensionamento piu appropriato. Dopo aver condotto 5 run

per ogni tracciato con inizializzazione della popolazione casuale si e notato che

40

5.3 Risultati sperimentali con fitness function simulata

intorno alla generazione 300 si ha un’appiattimento dell’andamento, il quale,

da quel punto in poi non portera vantaggi significativi alla soluzione finale.

5.3 Risultati sperimentali con fitness function

simulata

Il primo obiettivo dell’analisi e generare una traiettoria in grado di essere se-

guita dal follower con il minor lap time possibile. Per valutare il lap time, viene

lanciata una breve simulazione di gara in TORCS lunga tre giri, considerando

il tempo ottenuto durante il secondo giro. La gara simulata e impostata con

benzina infinita e follower che non subisce danni. Questo in alcune situazioni

puo portare a risultati non ottimali, ma semplifica decisamente il processo nella

maggior parte dei casi, e quindi per coerenza e stato mantenuto in ogni analisi.

Oltre a scegliere quale tempo utilizzare per l’analisi e necessario stabilire un

follower univoco per tutti i test in modo da mantenere coerenza rappresenta-

tiva. TORCS fornisce un numero elevato di follower tra cui scegliere. Il BOT

da noi utilizzato e una versione leggermente modificata di Simplix [3], che e in

grado di seguire una traiettoria datagli in input.

La funzione di fitness dunque sara proprio il tempo necessario al BOT

per compiere un giro lanciato. Nelle nostre analisi utilizzaremo due diversi

approcci:

• Senza seeding iniziale

• Con seeding iniziale

dove con seeding si intende la presenza di una popolazione iniziale fornita

in input all’algoritmo.

41


5.3.1 Evoluzione senza seeding

Per questa tipologia di esperimento abbiamo effettuato cinque run per ogni

tracciato, con dimensione della popolazione e numero di generazioni in accordo

a quanto analizzato nel paragrafo 5.2.3. Il GAtoolbox generera automatica-

mente la popolazione iniziale casuale rispettando i bound indicati nel file di

configurazione. Di seguito riportiamo i risultati ottenuti in questi primi test.

I tempi riportati fanno riferimento al miglior tempo di ogni run.

Tracciato Min Max Media SIMPLIX Lap Time

A-speedway 24.71 s 24.82 s 24.756 s 27.558 s

Alpine-2 94.06 s 94.32 s 94.15 s 94.334 s

CG-speedway 39.34 s 39.72 s 39.55 s 40.120 s

Ruudskogen 62.77 s 63.01 s 62.836 s 63.206 s

Wheel-1 77.71 s 77.86 s 78.01 s 73.924 s

Tabella 5.3: Tabella riassuntiva dei tempi ottenuti su 5 run, senza seeding

0 50 100 150 200 250 30024

25

26

27

28

29

30

31

32

33

34

Generazioni

Max

fitn

ess

func

tion

Run 1Run 2Run 3Run 4Run 5Media

Figura 5.2: Ottimizzazione di racing line su A-speedway senza seeding, con fitness

function simulata. La curva riporta l’andamento di 5 run evolutive

42


0 50 100 150 200 250 30094

96

98

100

102

104

106

Generazioni

Max

fitn

ess

func

tion


Figura 5.3: Ottimizzazione di racing line su Alpine-2 senza seeding, con fitness


0 50 100 150 200 250 30039

40

41

42

43

44

45

46

Generazioni

Max

fitn

ess

func

tion


Figura 5.4: Ottimizzazione di racing line su CG-speedway senza seeding, con fitness


43


0 50 100 150 200 250 30062

64

66

68

70

72

74

Generazioni

Max

fitn

ess

func

tion

Run 1Run 2Run 3Run 4Run5Media

Figura 5.5: Ottimizzazione di racing line su Ruudskogen senza seeding, con fitness


0 50 100 150 200 250 30076

78

80

82

84

86

88

90

92

94

96

Generazioni

Max

fitn

ess

func

tion


Figura 5.6: Ottimizzazione di racing line su Wheel-1 senza seeding, con fitness


44


La tabella 5.3 mostra come i risultati ottenuti siano tendenzialmente molto

buoni, infatti in quasi tutti i tracciati riusciamo a migliorare il tempo base

relizzato dal BOT Simplix. Dai grafici (da fig. 5.2 a 5.5) si puo notare come

l’andamento sia regolare, migliorando costantemente il risultato fino alla 200-

esima generazione, per poi raffinarlo nelle ultime 100.

(a) Alpine-2 (b) Cg-Speedway

(c) Ruudskogen (d) Wheel-1

Figura 5.7: Traiettorie a confronto su particolari di pista. In rosso e rappre-

sentanta la racing line di Simplix, mentre in verde quella trovata con la nostra

rappresentazione

Nella figura 5.7 e possibile visualizzare le differenze tra la traiettoria di

riferimento di Simplix e quella in analisi. Si puo notare come ad esempio in A-

speedway, nonostante la racing line di riferimento sia piu morbida, riusciamo

ad ottenere un risultato migliore. Questo ci permette di ritenere possibili

ulteriori raffinamenti e miglioramenti.

Alcuni risultati, data la caratteristica di non potersi danneggiare del follo-

wer, permettono di compiere traiettorie che urtano i guardrail, in caso questi

siano presenti, senza influenzare negativamente il risultato finale, impedendo

quindi di ottimizzare al meglio. Cio porta ad esempio ai risultati di Alpine,

che sono vicini, ma non molto inferiori, a quelli di Simplix.

45


Abbiamo inoltre effettuato un’analisi statistica dei dati ottenuti in tabella

5.3 utilizzando il test non parametrico Wilcoxon signed rank [15]. La nostra

analisi mostra come le differenze fra i risultati ottenuti con il nostro approccio

e i risultati ottenuti dal BOT Simplix sono statisticamente significative con

una confidenza del 90% ad eccezione dei risultati ottenti sulla pista Alpine-2.

In definitiva, quanto ottenuto puo essere ritenuto valido, e si potrebbero

ottenere dei risultati ancora migliori personalizzando i parametri relativi ai

punti di controllo per ogni pista, ma quest’analisi esula dagli obiettivi di questa

tesi.

Nelle figure dalla 5.8 alla 5.11 si possono vedere le evoluzioni delle traiettorie

durante un singolo run. Per chiarezza si e deciso di visualizzare dieci traiettorie

rappresentative, prese ad intervalli di miglioramento piu uniforme possibile.

Si puo notare come nei punti dove la differenza tra le traiettorie e parti-

colarmente significativa si ha l’intersezione tra sezioni diverse (nella legenda

sono indicati i tempi impiegati, in secondi, per compiere un giro utilizzando la

traiettoria di riferimento).

Aspeedway 25

Aspeedway 27

Aspeedway 29

Aspeedway 31

Aspeedway 33

Aspeedway 35

Aspeedway 37

Aspeedway 39

Aspeedway 41

Aspeedway 43

Figura 5.8: Evoluzione delle traiettorie. Particolare di A-speedway

46


alpine−2 110

alpine−2 108

alpine−2 106

alpine−2 104

alpine−2 102

alpine−2 100

alpine−2 98

alpine−2 96

alpine−2 94

alpine−2 92

Figura 5.9: Evoluzione delle traiettorie. Particolare di Alpine-2

CG−speedway 224

CG−speedway 84

CG−speedway 78

CG−speedway 72

CG−speedway 67

CG−speedway 62

CG−speedway 57

CG−speedway 52

CG−speedway 47

CG−speedway 42

CG−speedway 39

Figura 5.10: Evoluzione delle traiettorie. Particolare di CG-speedway

47


ruudskogen 128

ruudskogen 111

ruudskogen 101

ruudskogen 99

ruudskogen 93

ruudskogen 87

ruudskogen 81

ruudskogen 75

ruudskogen 69

ruudskogen 63

Figura 5.11: Evoluzione delle traiettorie. Particolare di Ruudskogen

E interessante osservare l’andamento dei valori dei punti di controllo du-

rante l’evoluzione della traiettoria. In figura 5.12 e possibile visualizzare la

media dei valori ottenuti per generazione di 10 punti di controllo, filtrati con

una moving average. Si puo notare, anche visualizzando un campione ristretto

di punti, che alcuni tendono ad assestarsi prima di altri durante l’evoluzione.

0 50 100 150 200 250 3000.1

0.2

0.3

0.4

0.5

0.6

0.7

0.8

0.9

1

Generazioni

Val

ore

Figura 5.12: Andamento di 10 punti di controllo durante l’evoluzoine

48


0 50 100 150 200 250 3000

0.05

0.1

0.15

0.2

0.25

0.3

Generazioni

Dev

iazi

one

stan

dard

(a) Punto di controllo A

0 50 100 150 200 250 3000

0.05

0.1

0.15

0.2

0.25

0.3

Generazioni

Dev

iazi

one

stan

dard

(b) Punto di controllo B

0 50 100 150 200 250 3000

0.05

0.1

0.15

0.2

0.25

0.3

Dev

iazi

one

stan

dard

Generazioni

(c) Punto di controllo C

0 50 100 150 200 250 3000

0.05

0.1

0.15

0.2

0.25

0.3

GenerazioniD

evia

zion

e st

anda

rd

(d) Punto di controllo D

A

B

C

D

(e) Tracciato: A-speedway

Figura 5.13: Posizione di 4 punti di controllo all’interno del tracciato e relative

deviazioni standard

Purtroppo non e possibile creare un collegamento tra tempo di assesta-

mento durante l’evoluzione, e posizione del punto nella pista all’interno della

sezione (inizio/fine sezione, interni, etc.). Dall’analisi effettuata comunque si

evince che alcuni punti di controllo posizonati in zone cruciali della traiettoria

(es. ingresso/uscita curva), siano i primi a stabilizzarsi e a mantenere una

49


variazione bassa durante l’evoluzione, questo perche ogni modifica apportata

a questi punti incide in maniera significativa sul tempo di giro. Per mostrare

cio, di seguito riportiamo l’andamento della deviazione standard per 4 punti

di controllo durante l’ottimizzazione e dove questi si collocano all’interno del

tracciato (fig. 5.13). I punti A e C, appartenenti ad un rettilineo e quindi

non fondamentali per la traiettoria variano molto di piu durante l’evoluzione

rispetto a B e D che si trovano in un punto delicato, quale la curva, all’interno

della racing line.

5.3.2 Evoluzione con seeding

Una volta ottenuti dei risultati, ci siamo domandati se quest’ultimi possano

essere migliorati tramite un’ulteriore run dell’algoritmo, questa volta pero con

una popololazione iniziale predefinita.

L’esperimento si svolge quindi in ulteriori due run, in cui entrambi avran-

no in input i migliori N genomi, dove N e la dimensione della popolazione,

ottenuti dalla run precedente. La dimensione della popolazione e il numero

massimo di generazioni rimane invariato durante l’intero esperimento.

La tabella 5.4 mostra i risultati ottenuti in questa tipologia di test, mentre

i grafici dalla fig. 5.14 alla 5.18 mostrano l’andamento delle 3 run per circuito.

Tracciato Run 1 Run 2 Run 3 SIMPLIX Time

A-speedway 24.8 s 24.66 s 24.62 s 27.558 s

Alpine-2 94.09 s 93.98 s 93.97 s 94.334 s

CG-speedway 39.72 s 39.44 s 39.18 s 40.120 s

Ruudskogen 62.78 s 62.46 s 62.45 s 63.206 s

Wheel-1 78.11 s 77.36 s 77.05 s 73.924 s

Tabella 5.4: Tabella riassuntiva contenente i migliori tempi ottenuti in 3 run,

utilizzando il seeding

50


0 50 100 150 200 250 30024

25

26

27

28

29

30

31

32

33

34

Generazione

Min

fitn

ess

func

tion

Run 1Run 2Run 3

Min: 24.62

Min: 24.8

Min: 24.66

Tempo mediorun: 13h03’

Figura 5.14: Ottimizzazione di racing line su A-speedway con seeding, con fitness


0 50 100 150 200 250 30092

94

96

98

100

102

104

Generazione

Max

fitn

ess

func

tion

Run 1Run 2Run 3

Tempo mediorun: 1G14h10’

Min: 93.98

Min: 94.09

Min: 93.97

Figura 5.15: Ottimizzazione di racing line su Alpine-2 con seeding, con fitness


51


0 50 100 150 200 250 30039

40

41

42

43

44

45

46

Generazione

Min

fitn

ess

func

tion

Run 1Run 2Run 3


Min: 39.72Min: 39.44

Min: 39.18

Figura 5.16: Ottimizzazione di racing line su CG-speedway con seeding, con fitness


0 50 100 150 200 250 30062

64

66

68

70

72

74

Generazione

Min

fitn

ess

func

tion

Run 1Run 2Run 3

Min: 62.78

Min: 62.46


Min: 62.45

Figura 5.17: Ottimizzazione di racing line su Ruudskogen con seeding, con fitness


52


0 50 100 150 200 250 30076

78

80

82

84

86

88

90

92

94

Generazione

Max

fite

nss

func

tion

Run 1Run 2Run3

Min: 78.11

Min: 77.36

Tempo Mediorun: 33h46’

Min: 77.05

Figura 5.18: Ottimizzazione di racing line su Wheel-1 con seeding, con fitness


In questa analisi e stato eseguito un solo esperimento per ogni pista per

motivi di costo computazionale. Sebbene i risultati siano quindi preliminari,

essi suggeriscono che sia possibile ottenere un miglioramento rispetto ai valori

della prima run. Questo e confutato dal fatto che lo stesso comportamento

si verifica per tutti i cinque tracciati in analisi. Si puo pero notare come il

secondo e il terzo run, ossia quelli interessati dal seeding, non siano altro che

dei tentativi di raffinamento locale. Infatti, osservando che il risultato della

prima run e gia di per se molto buono, il tool con le altre due run ottiene si

dei risultati migliori, ma senza allontanarsi significativamente da un intorno

del tempo ottenuto precedentemente.

53


5.4 Risultati sperimentali con fitness function

stimata

Gli esperimenti realizzati fino ad ora richiedono una vera simulazione di gara

da parte di TORCS. Questo e computazionalmente pesante poiche impiega pa-

recchio tempo e risorse per simulare una gara, ed e influenzato negativamente

dalla lunghezza e complessita del tracciato. Ci siamo quindi posti il problema

di trovare una funzione di fitness valida che richiedesse prestazioni decisamente

inferiori. Il BOT Simplix e in grado di stimare a priori il tempo che impie-

ghera a percorrere una determinata traiettoria in un tracciato. Questa stima

viene ottenuta tramite l’euristica K1999 [11] per l’ottimizzazione di racing line.

Questa euristica si basa esclusivamente sui parametri fisici della macchina e

sulla minima curvatura ottenibile nel circuito in analisi, ricavando il tempo

di giro propagando indietro la massima velocita che consenta di non uscire

in ogni punto dal tracciato in base alle capacita di frenata del mezzo, ed in

seguito propagando in avanti le massime velocita raggiungibili tenendo conto

delle capacita di accelerazione del BOT. Vogliamo a questo punto valutare

quanto questo approccio sia affidabile, e che guadagno sotto il punto di vista

computazionale otteniamo.

5.4.1 Studio delle inversioni

Come primo passo, bisogna valutare l’affidabilita della stima. Per far cio,

prendiamo le prime 100 generazioni dell’algoritmo applicate ai 5 tracciati da

noi analizzati. Prese due coppie di tempi (simulato e stimato da Simplix ),

valutiamo se vi sono delle inversioni tra le due, ossia se, in caso il primo tempo

simulato sia inferiore al secondo, la stima di Simplix invece e superiore alla

stima della seconda coppia (fig 5.19).

54

5.4 Risultati sperimentali con fitness function stimata

Figura 5.19: Schema per l’identificazione di un’inversione.

Come si puo vedere dal grafico (fig. 5.20), su un totale di circa 90000

coppie per generazione, vi e un 4% circa di inversioni per circuito. Questo

ci porta a dire che la stima fatta da Simplix e abbastanza affidabile, infatti

questi dati ci dicono che ordinando i valori stimati siamo certi al 96% che lo

stesso ordinamento sia corretto anche nei corrispettivi dati simulati, rendendo

cosı valida la selezione dei genomi, ma purtroppo non possiamo essere ancora

certi che l’algoritmo genetico, alla fine dell’evoluzione, ci fornisca un risultato

ottimo.

55


0 10 20 30 40 50 60 70 80 90 1000 %

1 %

2 %

3 %

4 %

5 %

6 %

7 %

8 %

9 %

Generazioni

Per

cent

uale

num

ero

inve

rsio

ni

A−speedwayCG−speedwayRuudskogenAlpine−2Wheel−1

Figura 5.20: Percentuale di inversioni per generazione

Per avere un riscontro valido alle nostre supposizioni e necessario che non

ci sia un grosso scarto tra tempo simulato e tempo stimato, o per lo meno che

questo sia costante.

Come si puo vedere dai grafici (fig. 5.21), il delta assoluto tra la funzione

stimata e quella simulata si assesta, dopo una prima fase rumorosa, all’incirca

per ogni tracciato.

Dato che in questo approccio ottimizziamo la funzione stimata, se anche il

corrispettivo tempo reale della miglior stima non e il miglior tempo in assoluto

tra quelli generati, siamo sicuri di esserci abbastanza avvicinati.

56


0 0.5 1 1.5 2 2.5 3

x 104

0

0.2

0.4

0.6

0.8

1

1.2

1.4

Numero valutazione

Del

ta a

ssol

uto

(a) A-Speedway

0 0.5 1 1.5 2 2.5 3

x 104

0

1

2

3

4

5

6

7

8

Numero valutazione

Del

ta a

ssol

uto

(b) Alpine-2

0 0.5 1 1.5 2 2.5 3

x 104

0

0.5

1

1.5

2

2.5

3

3.5

4

4.5

5

Numero valutazione

Del

ta a

ssol

uto

(c) Cg-Speedway

0 0.5 1 1.5 2 2.5 3

x 104

0

1

2

3

4

5

6

7

Numero valutazione

Del

ta a

ssol

uto

(d) Ruudskogen

0 0.5 1 1.5 2 2.5 3

x 104

0

5

10

15

20

25

30

Numero valutazione

Del

ta a

ssol

uto

(e) Wheel-1

Figura 5.21: Delta assoluto tra tempo stimato e tempo simulato su 100 generazioni

5.4.2 Evoluzione con fitness stimata

I test sono stati eseguiti con le stesse modalita utilizzate per la funzione

obiettivo simulata.

Come si puo notare dai grafici seguenti (da fig. 5.22 a fig. 5.26), si ottiene

lo stesso andamento regolare osservato con l’utilizzo della fitness simulata, ed

in alcuni casi raggiunge risultati che sembrano nettamente migliori.

57


0 50 100 150 200 250 30022

24

26

28

30

32

34

36

Generazioni

Max

fitn

ess

func

tion


Figura 5.22: Ottimizzazione di racing line su A-speedway senza seeding, con fitness

function stimata. La curva riporta l’andamento di 5 run evolutive

0 50 100 150 200 250 30096

98

100

102

104

106

108

110

Generazioni

Max

fitn

ess

func

tion


Figura 5.23: Ottimizzazione di racing line su Alpine-2 senza seeding, con fitness


58


0 50 100 150 200 250 30038

39

40

41

42

43

44

45

46

47

48

Generazioni

Max

fitn

ess

func

tion


Figura 5.24: Ottimizzazione di racing line su CG-speedway senza seeding, con

fitness function stimata. La curva riporta l’andamento di 5 run evolutive

0 50 100 150 200 250 30064

66

68

70

72

74

76

78

Generazioni

Max

fitn

ess

func

tion


Figura 5.25: Ottimizzazione di racing line su Ruudskogen senza seeding, con fitness


59


0 50 100 150 200 250 30075

80

85

90

95

100

Generazioni

Max

fitn

ess

func

tion


Figura 5.26: Ottimizzazione di racing line su Wheel-1 senza seeding, con fitness


Nella tabella 5.5 possiamo visualizzare i risultati ottenuti. A parte Wheel,

che presenta alcune criticita legate alla rappresentazione, la differenza tra i due

tempi e quasi costante in ogni run.

60


Tracciato Run Tempo Stimato s Tempo Reale s |∆|

A-speedway

1 24.333600 25.070000 0.7364

2 23.802800 24.863999 1.061199

3 24.328300 25.232000 0.9037

4 24.444000 25.230000 0.786

5 24.090800 24.980000 0.8892

Alpine-2

1 96.383800 97.566002 1.182202

2 96.308300 97.365998 1.057698

3 96.610600 97.677998 1.067398

4 96.261100 96.873998 0.612898

5 96.354200 96.699999 0.345799

CG-Speedway

1 39.177600 40.932000 1.7544

2 39.175600 41.304002 2.128402

3 39.048800 39.951999 0.903199

4 38.741300 40.388001 1.646701

5 39.227200 41.714001 2.486801

Ruudskogen

1 64.999400 64.245999 0.753401

2 65.228700 64.120002 1.108698

3 64.937100 63.793997 1.143103

4 65.281200 63.795996 1.485204

5 65.161700 65.353997 0.192297

Wheel-1

1 77.267900 112.922001 35.654101

2 77.694900 80.907996 3.213096

3 77.518000 80.295999 2.777999

4 77.193700 114.651998 37.458298

5 77.316600 79.988000 2.6714

Tabella 5.5: Confronto tra tempi di lap stimati ed effettivi

61


Tutto cio comunque sarebbe inutile se i tempi computazionali non presen-

tassero miglioramenti. Come si puo notare nella tabella 5.6 successiva, pero,

le nostre aspettative sono state confermate, ed i tempi di calcolo si riducono

drasticamente di circa un fattore 6.

Tracciato Fitness simulata Fitness stimata

A-Speedway 13h 03’ 3h 24’

Alpine-2 1G 14h 10’ 5h 02’

Cg-Speedway 17h 41’ 3h 42’

Ruudskogen 1G 3h 17’ 4h 48’

Wheel-1 1G 9h 46’ 5h 20’

Tabella 5.6: Differenza tra i tempi computazionali medi di ogni run nelle due

tipologie di fitness.

Simulato Simulato Stimato Stimato

Tracciato Min Media Min Media SIMPLIX

A-speedway 24.71 s 24.756 s 24.863999 s 25.0751998 s 27.558 s

Alpine-2 94.06 s 94.32 s 96.699999 s 97.236799 s 94.334 s

CG-speedway 39.34 s 39.55 s 39.951999 s 40.8580026 s 40.120 s

Ruudskogen 62.77 s 62.836 s 64.120002 s 64.2619982 s 63.206 s

Wheel-1 77.71 s 77.86 s 79.988000 s 93.7531988 s 73.924 s

Tabella 5.7: Tabella di confronto tra i tempi ottenuti tra le due tipologie di analisi

(funzione obiettivo simulata e stimata)

Il bottleneck di tutto l’algoritmo era quindi la simulazione della gara. Co-

me mostrato in tabella 5.7 utilizzando la fitness stimata e possibile ottenere

risultati vicini a quelli simulati, ma con un costo decisamente inferiore. In-

fine, abbiamo effettuato un’analisi statistica dei dati ottenuti in tabella 5.7

utilizzando il test non parametrico Wilcoxon rank sum [15]. La nostra analisi

mostra come le differenze fra i risultati ottenuti utilizzando la fitness simulata

62


e quelli ottenuti con la fitness stimata sono statisticamente significative con

una confidenza del 95% ad eccezione dei risultati ottenti sulla pista Alpine-2.

63

Capitolo 6

Conclusioni e sviluppi futuri

6.1 Risultati

In questa tesi abbiamo affrontato il problema di realizzare una rappresenta-

zione per la creazione di una racing line che non necessitasse di informazioni

preliminari, a parte le informazioni di base del tracciato da seguire e del BOT

che seguira la traiettoria.

Abbiamo quindi introdotto una nuova rappresentazione basata su curve

di Bezier. Per valutare la bonta di questa rappresentazione, abbiamo con-

dotto diversi tipi di analisi, tenendo come obiettivo i risultati ottenuti dal

BOT di riferimento nella comunita di TORCS, Simplix, e quelli ottenuti in

[24]. Abbiamo studiato le prestazioni della traiettoria evolvendola tramite un

algoritmo genetico, inizialmente senza una popolazione iniziale, ed in seguito,

con l’obiettivo di migliorare ancora, provando a inizializzarla. Come funzione

di fitness abbiamo utilizzato, come primo approccio, una simulazione di gara

di TORCS, in cui viene registrato il tempo del secondo su tre giri, per poi

passare ad una stima del tempo sul giro.

I risultati ottenuti mostrano che il nostro approccio puo essere considera-

to valido, dato che siamo riusciti ad avvicinarci ai tempi riportati in [24], e

migliorare quelli di Simplix.

Si e visto inoltre come, inizializzando l’algoritmo genetico con una popo-

Conclusioni e sviluppi futuri

Tracciato Simplix Cardamone et al. [24] Simulata Simulata Stimata

senza seeding con seeding

A-Speedway 27.558 24.701 24.71 24.62 24.864

Alpine-2 94.334 92.527 94.06 93.97 96.700

Cg-Speedway 40.120 39.372 39.34 39.18 39.952

Ruudskogen 63.206 62.732 62.77 62.45 63.796

Wheel-1 73.924 74.887 77.71 77.05 79.988

Tabella 6.1: Risultati a confronto (i tempi sono misurati in secondi)

lazione di traiettorie gia buone, non si ha un miglioramento sostanziale della

soluzione, ma bensı una ricerca locale, che raffina leggermente il risultato finale,

impiegando pero lo stesso tempo di calcolo di una normale evoluzione senza

seeding. E emerso infatti come il difetto maggiore di questo metodo sia il tempo

e la potenza di calcolo necessaria per l’evoluzione delle traiettorie. Per ovvia-

re a questo problema, l’utilizzo della stima del tempo sul giro direttamente

tramite il BOT Simplix permette di ridurre drasticamente i tempi di calcolo,

a scapito pero di soluzioni meno accurate. E comunque interessante notare

come l’andamento evolutivo di quest’ultima analisi risulti pressoche identico

all’andamento di una fitness function simulata. Le analisi da noi effettuate

sono state convalidate attraverso due test statistici non parametrici [15], che

hanno confermato che le differenze tra i risultati ottenuti con i nostri approcci

(i.e., fitness simulata e fitness stimata), i risultati ottenuti da Cardamone et al.

[24] e i risultati ottenuti dal BOT Simplix sono statisticamente significative

con una confidenza superiore al 90% (con l’eccezione di alcuni casi). Si puo

quindi concludere che il nostro approccio presenta dei notevoli vantaggi rispet-

to a quanto visto in altri studi, dato che non necessita di informazioni iniziali

particolari, ma paga questo vantaggio con un costo computazionale decisa-

mente elevato. L’utilizzo della stima potrebbe essere un buon compromesso,

permettendo di raggiungere buoni risultati in relativamente poco tempo.

66

6.2 Sviluppi Futuri

6.2 Sviluppi Futuri

L’analisi fin qui effettuata si e basata principalmente su parametri standard per

ogni esperimento e per ogni circuito. Trovare dei valori personalizzati per ogni

circuito puo sicuramente migliorare i risultati e le performance dell’algoritmo.

Inoltre, la racing line ottenuta e profondamente correlata al BOT utilizzato

per la valutazione. E quindi possibile far partire un’analisi su come la rappre-

sentazione viene influenzata da diversi BOT, e quanto i risultati differiscano

in base alle caratteristiche dei BOT.

Un’ulteriore possibilita e quella di effettuare ulteriori studi per ottimizzare

il processo evolutivo, ossia scegliere la miglior combinazione tra dimensione

della popolazione e numero di generazioni, oppure provare differenti metodi di

crossover o mutazione, studiandone le differenze sui risultati.

Infine, supponendo di aver ridotto drasticamente i tempi di evoluzione, il

tutto potrebbe essere integrato in un tool di generazione automatica di trac-

ciati (interno ad un videogioco, o esistente di per se), generando la relativa

traiettoria migliore, dando cosı all’utente la possibilita di sfidare AI sulla pista

da lui generata.

67

Bibliografia

[1] The open racing car simulator website. http://torcs.sourceforge.net/.

[2] Robot auto racing simulator. http://rars.sourceforge.net/.

[3] Wolf-Dieter Beelitz. The simply mixed best practice torcs robot.

http://www.wdbee.gotdns.org:8086/SIMPLIX/SimplixDefault.aspx.

[4] F. Braghin, F. Cheli, S. Melzi, and E. Sabbioni. Race driver model.

Comput. Struct., 86(13-14):1503–1516, 2008.

[5] Martin V. Butz and Thies D. Lonneker. Optimized sensory-motor cou-

plings plus strategy extensions for the torcs car racing challenge. In Com-

putational Intelligence and Games, 2009. CIG 2009. IEEE Symposium

on, pages 317–324, Sept. 2009.

[6] Luigi Cardamone. On-line and off-line learning of driving tasks for the

open racing car simulator (torcs) using neuroevolution. Master’s thesis,

Politecnico di Milano, 2008.

[7] Luigi Cardamone, Daniele Loiacono, and Pier Luca Lanzi. Evolving

competitive car controllers for racing games with neuroevolution. In

GECCO ’09: Proceedings of the 11th Annual conference on Genetic and

evolutionary computation, pages 1179–1186, New York, NY, USA, 2009.

ACM.

[8] Luigi Cardamone, Daniele Loiacono, and Pier Luca Lanzi. Learning dri-

vers for torcs through imitation using supervised methods. In Compu-

BIBLIOGRAFIA

tational Intelligence and Games, 2009. CIG 2009. IEEE Symposium on,

pages 148–155, Sept. 2009.

[9] Luigi Cardamone, Daniele Loiacono, and Pier Luca Lanzi. Applying coo-

perative coevolution to compete in the 2009 torcs endurance world cham-

pionship. In Evolutionary Computation (CEC), 2010 IEEE Congress on,

pages 1 –8, jul. 2010.

[10] T. A. de A Costa. Trajectory generation with curvature constraint based

on energy minimization. In ABCM Symposium Series in Mechatronics,

volume 3, pages 300–307, 2008.

[11] Remi Coulom. Reinforcement learning using neural networks, with appli-

cations to motor control. PhD thesis, Instituite National Polytechnique

de Grenoble, 2002.

[12] R.S. Sharp D. Casanova. On minimum time vehicle manoeuvring: the

theoretical optimal time. PhD thesis, Cranfield University, 2000.

[13] H. Delingette, Martial Hebert, and Katsushi Ikeuchi. Trajectory gene-

ration with curvature constraint based on energy minimization. In Pro-

ceedings 1991 IEEE/RSJ International Conference On Intelligent Robotic

Systems (IROS ’91), November 1991.

[14] Christos Dimitrackakis. Online statistical estimation for vehicle control.

IDIAP-RR 13, IDIAP, 2006.

[15] J. D. Gibbons. Nonparametric Statistical Inference. Marcel Dekker, 1985.

[16] David E. Goldberg. Genetic Algorithms in Search Optimization and

Machine Learning. 1989.

[17] Y. Kanayama and N. Miyake. Trajectory generation for mobile robots.

In In Proc. of the Int. Symp. on Robotics Research, 1985.

[18] Y. Kanayama, A. Nilipour, and C. Lelm. A locomotion control method

for autonomous vehicles. In ICRA, pages 1315–1317, 1988.

70

BIBLIOGRAFIA

[19] Yutaka J. Kanayama and Bruce I. Hartman. Smooth local-path planning

for autonomous vehicles. Int. J. Rob. Res., 16(3):263–284, 1997.

[20] K. Komoriya and K. Tanie. Trajectory design and control of a wheel-

type mobile robot using b-spline curve. In Intelligent Robots and Systems

’89. The Autonomous Mobile Robots and Its Applications. IROS ’89. Pro-

ceedings., IEEE/RSJ International Workshop on, pages 398 –405, sep

1989.

[21] Stefano Lecchi. Artificial intelligence in racing games. In CIG’09: Procee-

dings of the 5th international conference on Computational Intelligence

and Games, 2009.

[22] D. Loiacono, P.L. Lanzi, J. Togelius, E. Onieva, D.A. Pelta, M.V. Bu-

tz, T.D. Lonneker, L. Cardamone, D. Perez, Y. Saez, M. Preuss, and

J. Quadflieg. The 2009 simulated car racing championship. Computatio-

nal Intelligence and AI in Games, IEEE Transactions on, 2(2):131 –147,

jun. 2010.

[23] Daniele Loiacono, Alessandro Prete, Pier Luca Lanzi, and Luigi Carda-

mone. Learning to overtake in torcs using simple reinforcement learning.

In Evolutionary Computation (CEC), 2010 IEEE Congress on, pages 1

–8, jul. 2010.

[24] Pier Luca Lanzi e Alessandro Pietro Bardelli Luigi Cardamone, Danie-

le Loiacono. Searching for the optimal racing line using genetic algorithms.

IEEE Conference on Computational Intelligence and Games, 2010.

[25] Mark Andrew Hatton e Ralf Herbrich Michael E. Tipping. Racing line

optimization, 2011.

[26] Jorge Munoz, German Gutierrez, and Araceli Sanchis. Controller for torcs

created by imitation. In Computational Intelligence and Games, 2009.

CIG 2009. IEEE Symposium on, pages 271–278, Sept. 2009.

71

BIBLIOGRAFIA

[27] B. Nagy and A. Kelly. Trajectory generation for car-like robots using

cubic curvature polynomials. Field and Service Robots 2001, 2001.

[28] E. Onieva, D. A. Pelta, J. Alonso, V. Milanes, and J. Perez. A modular

parametric architecture for the torcs racing engine. In Computational

Intelligence and Games, 2009. CIG 2009. IEEE Symposium on, pages

256–262, Sept. 2009.

[29] Enrique Onieva, Luigi Cardamone, Daniele Loiacono, and Pier Luca Lan-

zi. Overtaking opponents with blocking strategies using fuzzy logic. In

Computational Intelligence and Games (CIG), 2010 IEEE Symposium on,

pages 123 –130, aug. 2010.

[30] F.G. Pin and H.A. Vaaseur. Autonomous trajectory generation for mobile

robots with non-holonomic and steering angle constraints. In Intelligent

Motion Control, 1990. Proceedings of the IEEE International Workshop

on, volume 1, pages 295 –299, aug 1990.

[31] J. Quadflieg, M. Preuss, O. Kramer, and G. Rudolph. Learning the track

and planning ahead in a car racing controller. In Computational Intelli-

gence and Games (CIG), 2010 IEEE Symposium on, pages 395 –402, aug.

2010.

[32] Alireza Sahraei, Mohammad Taghi Manzuri, Mohammad Reza Razvan,

Masoud Tajfard, and Saman Khoshbakht. Real-time trajectory generation

for mobile robots. In AI*IA ’07: Proceedings of the 10th Congress of

the Italian Association for Artificial Intelligence on AI*IA 2007, pages

459–470, Berlin, Heidelberg, 2007. Springer-Verlag.

[33] Kumara Sastry. Single and multiobjective genetic algorithm toolbox in

c++. 2007.

[34] J. Togelius and S.M. Lucas. Evolving robust and specialized car racing

skills. pages 1187–1194, 0-0 2006.

72

BIBLIOGRAFIA 73

[35] Julian Togelius and Simon M. Lucas. Evolving controllers for simulated

car racing. In Proceedings of the Congress on Evolutionary Computation,

2005.

[36] N. van Hoorn, J. Togelius, D. Wierstra, and J. Schmidhuber. Ro-

bust player imitation using multiobjective evolution. In Evolutionary

Computation, 2009. CEC ’09. IEEE Congress on, pages 652–659, May

2009.

[37] Krzysztof Wloch and Peter J. Bentley. Optimising the performance of

a formula one car using a genetic algorithm. In Proceedings of Eighth

International Conference on Parallel Problem Solving From Nature, pages

702–711, 2004.

Appendice A

Configurazione del tool

Per poter utilizzare il tool, e necessario impostare alcuni parametri all’interno

di due file di configurazione. Nel file params.txt sono presenti 22 parametri,

ma solamente 11 sono di nostro interesse:

alg: indica il tool da utilizzare per l’evoluzione genetica (nel nostro caso, il

GATbx).

popsize: indica la dimensione della popolazione (utilizzato per motivi di

debug).

maxgen: indica il massimo numero di generazioni realizzate dall’algoritmo

(utilizzato per motivi di debug).

statfile: indica il nome del file contenente le statistiche principali relative

all’esecuzione corrente (es. ruudskogen.stat).

popfile: indica il nome del file contenente tutti i dati relativi all’evoluzione

(es. ruudskogen.pop).

GATbx.paramFile: indica il path relativo al file di configurazione proprio

dell’algoritmo genetico (nel nostro caso, input sga).

problem: indica il tipo di problema che il tool dovra analizzare (nel nostro

caso BezierProblem).

76 BIBLIOGRAFIA

FitnessType: specifica se la funzione obiettivo da utilizzare e quella stimata

o quella simulata tramite un giro di pista lanciato (Simbolic o Real).

xmlFile: indica il path relativo al file xml che configura la gara in torcs (es.

race.xml).

objectiveTrack: indica il nome del tracciato preso in analisi (es. ruudskogen)

choose: indica la possibilita di valutare la Bezier interamente o dividendola

in sezioni (0 per la Bezier intera, 1 per dividere il tracciato in sezioni,

ognuna con la propria Bezier).

Per il file input sga, rimandiamo alla guida dedicata[33]. In caso si abbia

necessita di fornire all’algoritmo una popolazione iniziale, questa va inserita

all’interno di un file, contenente all’inizio il numero di elementi all’interno

della popolazione, in seguito il valore di ogni gene per ogni cromosoma della

popolazione, e in fine la bonta di quel genoma. Quest’ultimo elemento puo

non essere considerato, in caso si voglia far valutare al tool la bonta di quel

genoma, ma deve essere comunque presente all’interno del file.

Politecnico di Milano · Alcuni dei piu` recenti lavori relativi ai racing games `e stato svolto da...

Documents

Transcript of Politecnico di Milano · Alcuni dei piu` recenti lavori relativi ai racing games `e stato svolto da...