Progettazione e realizzazione di un sistema di rilevamento del traffico urbano basato su crowd sensing e stigmergia e caratterizzazione dei problemi basata su social sensing

UNIVERSITÀ DEGLI STUDI DI PISA

Scuola di Ingegneria

Corso di Laurea Magistrale in Ingegneria Informatica

Tesi di Laurea Magistrale

Progettazione e realizzazione di un Sistema di rilevamento del

traffico urbano, basato su Crowd Sensing e Stigmergia, e

caratterizzazione dei problemi basata su Social Sensing

Relatori :

Prof.ssa Gigliola Vaglini

Prof. Mario G. C. A. Cimino

Dott. Alessandro Lazzeri

Candidato:

Riccardo Paoli

2

Riassunto

Il Sistema che è stato progettato affronta il problema del rilevamento e della caratterizzazione del traffico urbano. Il rilevamento è fatto attraverso tecniche di crowd sensing e stigmergia applicate alle tracce GPS dei veicoli che attraversano la rete urbana. In particolare, le tracce sono analizzate da un modulo che rilascia delle impronte nell’ambiente in cui si trova l’utente; queste, aggregandosi fra loro, saranno utilizzate come indice della presenza di traffico. A causa dell’eventualità di non rilevare correttamente gli eventi frutto di un’impostazione manuale dei parametri stigmergici su cui si basa il modulo di rilevamento del traffico, i parametri del sistema sono ottimizzati per adattarsi alla variabilità del traffico e della topologia della rete stradale: dopo aver analizzato tre algoritmi di ottimizzazione ,Algoritmi Genetici, Evoluzione Differenziale e Ottimizzazione con Sciame di Particelle, è stato scelto come candidato l’algoritmo di Evoluzione Differenziale. Gli eventi di traffico individuati sono caratterizzati con tecniche di Social Sensing. La descrizione dell’evento è fatta con un Tag Cloud generato da un insieme di testi raccolti dal social network Twitter e opportunamente manipolati. Infatti, i tweet catturati dal modulo di Traffic Assessment sono soggetti a molte forme di rumore e prima di concorrere alla generazione del Tag Cloud vengono filtrati sia per quanto riguarda l’eliminazione dei campi ritenuti non essenziali dal punto di vista del guadagno di informazione sia per quanto riguarda l’eliminazione dal testo dei tweet di tutta una serie di elementi anch’essi poco influenti per il contenuto informativo. Il Tag Cloud generato supporta sia la modalità di funzionamento utilizzando soltanto uni-grammi che quella che include anche bi-grammi, tri-grammi e più in generale N-grammi.

3

Indice

1

Introduzione ... 8

1.1 Il problema del Traffico ... 8

1.2 Applicazioni per il monitoraggio stradale ... 10

1.3 Metodologie di caratterizzazione del Traffico... 12

2

Concetti Base ... 13

2.1 Sistemi Multi-Agente ... 13

2.2 Swarm Intelligence ... 16

2.3 Stigmergia ... 17

2.4 Studi e Applicazioni della Swarm Intelligence ... 20

2.5 Social Media e nuovi paradigmi di comunicazione ... 21

2.6 Social Sensing ... 23

2.7 Uso di Twitter per applicazioni di Social Sensing ... 24

3

Progettazione e Realizzazione del Sistema ... 26

3.1 Progettazione del Modulo di Traffic Detection ... 27

3.1.1 Rappresentazione del Modello di Traffico... 28

3.1.2 Ottimizzazione del Modello di Traffico ... 32

3.1.3 Simulatore ... 44

3.2 Realizzazione del Modulo di Traffic Detection... 45

3.2.1 Repast Simphony ... 46

3.2.2 MATLAB... 48

3.2.3 Implementazione del Modulo Traffic Jam Detector ... 49

3.2.4 Implementazione dell’Ottimizzatore ... 52

3.3 Progettazione del Modulo di Traffic Assessment ... 62

3.3.1 Schema completo dei componenti... 64

3.3.2 Data Capturing ... 65

3.3.3 Data Filtering ... 65

3.3.4 Data Selection ... 67

3.3.5 Event Assessment ... 68

3.4 Realizzazione del Modulo di Traffic Assessment ... 69

3.4.1 Descrizione delle Classi ... 71

4

Testing del Sistema ... 83

4

4.1.1 Impostazione manuale dei Parametri del Modello ... 84

4.1.2 Prima Serie di Test ... 86

4.1.3 Seconda Serie di Test ... 91

4.1.4 Terza Serie di Test ... 94

4.2 Testing del Modulo di Traffic Assessment ... 99

4.2.1 Dimostrazione di utilizzo con i dati riguardanti la piena dell’Arno ... 101

5

Conclusioni ... 106

Ringraziamenti ... 107

5

Indice delle Figure

Figura 1 – Volume di Passeggeri e Merci nei Sistemi di Trasporto ... 9

Figura 2 - Intelligent Transport Systems ... 10

Figura 3 - Comportamento di un Agente Riflesso ... 14

Figura 4 - Comportamento di un Agente Teleonomico ... 15

Figura 5 - Scelta del percorso più breve da parte delle formiche ... 19

Figura 6 - Raccolta dei cadaveri da parte della formiche ... 20

Figura 7 - Panorama dei Social Media ... 22

Figura 8 - Esempio di Tweet ... 25

Figura 9 - Confronto tra la vita di un tweet e di un post ... 25

Figura 10 - Rappresentazione generale del Sistema ... 26

Figura 11 - Rappresentazione della Rete Stradale ... 27

Figura 12 - Livello virtuale del Modello di Traffico ... 29

Figura 13 - Livello Globale del Modello di Traffico ... 30

Figura 14 - Sovrapposizione delle impronte sul Modello ... 31

Figura 15 - Schema di Funzionamento dell'Ottimizzatore ... 32

Figura 16 - Esempio di Cross - Over ... 38

Figura 17 - Esempio di Mutazione ... 38

Figura 18 - Inizializzazione della popolazione con DE ... 40

Figura 19 - Generazione di un nuovo Agente ... 40

Figura 20 - Esempio di esecuzione di PSO ... 42

Figura 21 - Simulatore di Traffico ... 45

Figura 22 - Contesto, proiezioni e agenti in Repast Simphony ... 47

Figura 23 - Diagramma delle Classi di Traffic Jam Detector ... 49

Figura 24 - Funzione Sigmoide con soglia per il Traffico ... 52

Figura 25 - Esempio di Tag Cloud ... 63

Figura 26 - Architettura Generale del modulo di Social Sensing ... 64

Figura 27 - Esempio di Tweet per Data Filtering ... 66

Figura 28 - Esempio di Tweet Rumoroso ... 67

Figura 29 - Esempio di Tweet non Rumoroso ... 67

Figura 30 - Diagramma delle Classi del modulo di Traffic Assessment ... 70

Figura 31 - Schema di Funzionamento della classe Config ... 74

Figura 32 - Funzionamento del componente di Capturing in modalità tempo reale ... 77

Figura 33 - Funzionamento del componente di Selection ... 79

Figura 34 - Percorsi delle rete stradale di Pisa monitorati nei Test ... 84

Figura 35 - Fitness dell'Ottimizzazione della prima Serie, Caso 1 ... 88

6

Figura 37 - Fitness dell'Ottimizzazione della seconda Serie di Test ... 94

Figura 38 - Mappa del Percorso 1 ... 95

Figura 39 - Mappa del Percorso 2 ... 95

Figura 40 - Fitness dell'Ottimizzazione della terza Serie di Test ... 98

Figura 41 - Console del Modulo di Capturing-Filtering ... 100

Figura 42 - Aggiornamento della Console di Capturing-Filtering ... 100

Figura 43 - Aggiornamento della Console di Selection Assessment ... 101

Figura 44 - Generazione in tempo reale del Tag Cloud ... 101

Figura 45 - Test sui tweet delle Piena dell'Arno con unigrammi non filtrati ... 102

Figura 46 - Test sui tweet delle Piena dell'Arno con N-grammi non filtrati ... 102

Figura 47 - Test sui tweet delle Piena dell'Arno con uni-grammi senza retweet ... 104

Figura 48 - Test sui tweet delle Piena dell'Arno con uni-grammi con retweet ... 104

7

Indice delle Tabelle

Tabella 1 - Classificazione di un Agente ... 15

Tabella 2 - Caratteristiche principali degli operatori genetici ... 38

Tabella 3 - Comparazione tra le prestazione degli algoritmi di Ottimizzazione ... 44

Tabella 4 - Confronto tra Prototipo originale e Output del modulo di Traffic Detection 85 Tabella 5 - Riepilogo del Caso di Test con inizializzazione manuale dei parametri ... 86

Tabella 6 - Risultati dell'Ottimizzazione della prima Serie, Caso 1 ... 87

Tabella 7 - Riepilogo del Caso 1 di Test della prima serie di Test ... 89

Tabella 8 - Riepilogo del Caso 2 di Test della prima serie di Test ... 91

Tabella 9 - Prototipi utilizzati nella seconda serie di Test ... 92

Tabella 10 - Riepilogo degli eventi della seconda serie di Test ... 93

Tabella 11 - Riepilogo della seconda serie di test ... 94

Tabella 12 - Prototipi utilizzati nella quarta serie di Test nel Percorso 1 ... 96

Tabella 13 - Prototipi utilizzati nella quarta serie di Test nel Percorso 2 ... 96

Tabella 14 - Riepilogo del percorso 1 della quarta serie di test ... 97

Tabella 15 - Riepilogo del percorso 2 della quarta serie di test ... 98

8

1 Introduzione

Il Sistema che è stato progettato affronta il problema del rilevamento e della caratterizzazione del traffico urbano. Il rilevamento è fatto attraverso tecniche di crowd sensing e stigmergia applicate alle tracce GPS dei veicoli che attraversano la rete urbana. I parametri del sistema di rilevamento sono ottimizzati per adattarsi alla variabilità del traffico e della topologia della rete stradale attraverso l’algoritmo di Evoluzione Differenziale. Gli eventi di traffico individuati sono caratterizzati con tecniche di Social Sensing. La descrizione dell’evento è fatta con un Tag Cloud generato da un insieme di testi raccolti dal social network Twitter e opportunamente manipolati.

La presente tesi si articola in 5 capitoli; nei primi due capitoli è stata effettuata una descrizione dello stato dell’arte, delle tecniche e teorie di Swarm Intelligence e degli approcci all’utilizzo di tecniche di Social Sensing; nel capitolo 3 è presente la descrizione della progettazione e della realizzazione del Sistema; prima viene affrontato l’argomento dal punto di vista del modulo di rilevazione del traffico ed in seguito da quello della caratterizzazione. Il capitolo 4 è dedicato al Testing del sistema; sono proposti infatti scenari di test per entrambi i moduli del sistema. La tesi conclude nel capitolo 5 con l’illustrazione dei risultati raggiunti e dei possibili sviluppi futuri.

1.1 Il problema del Traffico

Nel secondo dopoguerra abbiamo assistito a una graduale e costante crescita di volumi per i sistemi di trasporto stradale; in particolare come possiamo notare in Figura 1, negli ultimi venti anni il volume di merci e persone è aumentato a dismisura provocando spesso situazioni di disagio dovute alla saturazione della capacità delle infrastrutture di smaltire i flussi di veicoli.

Il problema del traffico è ancora più evidente e complesso se consideriamo i centri urbani (le grandi aree metropolitane più in generale) in cui da un lato è talvolta impossibile intervenire modificando la struttura fisica della rete stradale perché storicamente e\o geomorfologicamente consolidata e dall’altro sono maggiori gli interessi, i disagi e i costi prodotti che vanno a ripercuotersi sui cittadini dal punto di vista economico, della qualità della vita e della salute a causa di tali disagi.

9

Figura 1 – Volume di Passeggeri e Merci nei Sistemi di Trasporto

Finora le soluzioni adottate sono state quelle di estendere la rete esistente facendo ricorso alla costruzione di nuove strade, circonvallazioni e viadotti; queste nuove arterie della rete però non sempre hanno un agevolato percorso di realizzazione in termini temporali e burocratici. È evidente che, laddove non si riesca a ovviare al problema nella maniera classica, è necessario affrontare la situazione facendo ricorso a nuovi strumenti di gestione e monitoraggio del traffico.

E’ in questo contesto che s’inserisce la direttiva 2010/40/EU del Parlamento e del Consiglio Europeo, che cerca di definire i nuovi strumenti da utilizzare per la risoluzione del problema del Traffico. Vengono infatti introdotti i sistemi di trasporto intelligenti (Figura 2); questi sistemi sono applicazioni avanzate che, senza essere dotate di intelligenza in senso proprio, mirano a fornire servizi innovativi relativamente ai diversi modi di trasporto e alla gestione del traffico e consentono a vari utenti di essere meglio informati e di fare un uso più sicuro, maggiormente coordinato e più intelligente delle reti di trasporto.

10

Figura 2 - Intelligent Transport Systems

Nella direttiva si specifica che “gli ITS integrano le telecomunicazioni, l'elettronica e le tecnologie dell'informazione con l'ingegneria dei trasporti al fine di pianificare, progettare, rendere operativi, sottoporre a manutenzione e gestire i sistemi di trasporto. L'applicazione delle tecnologie dell'informazione e della comunicazione al settore del trasporto stradale e alle interfacce con altri modi di trasporto darà un contributo significativo al miglioramento delle prestazioni ambientali, dell'efficienza, compresa l'efficienza energetica, della sicurezza del trasporto stradale, compreso il trasporto di merci pericolose, della sicurezza pubblica e della mobilità dei passeggeri e delle merci, assicurando al tempo stesso il funzionamento del mercato interno nonché accresciuti livelli di competitività e di occupazione.”.[1]

1.2 Applicazioni per il monitoraggio stradale

Nell’affrontare i problemi sopra introdotti, una parte cruciale la giocano le applicazioni per smartphone e dispositivi mobili; uno dei principali ruoli assunti da questo tipo di dispositivi è quello di operare come “recomender”, cioè suggerire servizi e mostrare informazioni in base alle caratteristiche dell’utente e del contesto in cui si trova.[2] La capacità di adattare il proprio comportamento in relazione al contesto in cui si trova immerso l’utente, fornendo a esso servizi e informazioni altamente correlate con l’ambiente in cui si trova; quanto detto rientra nei concetti attinenti al settore della

context-awarness e le applicazioni di questa tipologia devono essere sviluppate nel modo meno invasivo possibile. Infatti, fatta eccezione per l’utilizzo attivo

11

dell’applicazione da parte dell’utente, il dispositivo deve essere in grado di percepire l’ambiente circostante e adattarsi a esso in modo reattivo e proattivo. A riguardo, diversi esempi di applicazioni per smartphone sono stati sviluppati, sia da pubblici sia privati e a diversi livelli amministrativi, per assistere i cittadini nei problemi di viabilità in ambito.

Il sistema che è stato realizzato nell’ambito di questa Tesi intende affrontare questo problema utilizzando un approccio “emergente”, in altre parole i dati raccolti dalle applicazioni installate sui singoli dispositivi mobili si aggregano tra loro andando a produrre informazioni che sono diffuse agli utenti che si trovano in situazione da poterne godere. Il dato raccolto, come detto in precedenza, è la posizione GPS del dispositivo mentre l’informazione che viene restituita agli utenti è la presenza eventi di traffico nelle zone d’interesse per l’utente.

L’utilizzo dei sensori tradizionali “on-road” sono uno strumento necessario ma non sufficiente per raccogliere dati per il monitoraggio stradale. Tali sensori, per quanto ormai abbiano raggiunto un elevato livello di affidabilità, sono limitati da un basso livello di copertura e comportano comunque elevati costi d’implementazione e mantenimento.[3]

Negli ultimi anni si sono affiancati a questi, metodi di rilevamento basati su sensori installati direttamente sul veicolo detti appunto “in-vehicle”. I dati sono quindi raccolti direttamente dal veicolo stesso (Floating Car Data, FCD) attraverso l’utilizzo di dispositivi GPS e telefoni cellulari. Diverse applicazioni sono già state sviluppate per integrare informazioni prodotte dai FCD con risorse tradizionali di monitoraggio del traffico. [4]

Alcuni esempi sono:

 TomTom : il servizio High Definition Traffic offre informazioni che integrano i dati raccolti attraverso una collaborazione con provider telefonico Vodafone.

 Cellint: ha sviluppato il sistema TrafficSense che utilizza i telefoni cellulari per monitorare in tempo reale la situazione del traffico stradale; il servizio stima i tempi di percorrenza e consiglia il percorso migliore.

 Airsage: opera per le agenzie federali, statali e locali negli Stati Uniti in collaborazione con Sprint Nextel; offre un servizio di route planning per i servizi di emergenza.

12

L’utilizzo del dato GPS è appropriato poiché l’obiettivo di questo lavoro riguarda il monitoraggio di traffico urbano e un errore elevato nei dati può comportare una difficile identificazione del segmento stradale in cui è in corso un evento d’interesse.

1.3 Metodologie di caratterizzazione del Traffico

I sistemi ITS, ed in particolare i FCD, possono essere utilizzati per fornire agli utenti informazioni sullo stato del Traffico sottoforma di preavviso. E’ possibile quindi utilizzare queste informazioni per cercare ad esempio di calcolare percorsi alternativi o mettere in atto tutte una serie di procedure che permettano di evitare eventuali zone congestionate e soggette a ritardo di percorrenza. Inoltre questi dati possono anche essere utilizzati da enti pubblici per fornire una risposta migliore all’eventuale situazione di emergenza che si è venuta a creare.

Allo stato attuale le tecniche più utilizzate per la caratterizzazione degli eventi di traffico sono quelle che sfruttano il video recording del tratto stradale. In questi sistemi il flusso video del segmento stradale viene analizzato da un software dedicato che è in grado di individuare eventuali anomalie. Uno dei principali limiti di questi sistemi risiede nel fatto che è comunque necessaria un’elaborazione centralizzata per l’identificazione della sorgente del problema e degli eventuali effetti collaterali collegati.

Un approccio alternativo, come quello sviluppato in questo lavoro di Tesi, può essere quello di coinvolgere direttamente gli utenti stessi nel processo di caratterizzazione dell’evento di traffico; in questo modo l’individuazione delle criticità è di tipo distribuito e non soffre dei problemi menzionati precedentemente. Nel caso particolare del sistema che è stato realizzato è possibile sfruttare, anche grazie anche al fatto di avere a disposizione la posizione GPS dell’evento, un social network istantaneo come Twitter utilizzando delle parole chiavi altamente correlate con tale evento come il nome della città, della via o del quartiere per inferire informazioni circa lo stato del traffico e la sorgente del problema esaminando n tempo reale i commenti degli automobilisti.

13

2 Concetti Base

In questo capitolo verranno affrontati introdotti alcuni concetti che stanno alla base del successivo lavoro di progettazione; in particolare saranno introdotti i Sistemi Multi-Agente evidenziandone gli aspetti più caratteristici grazie ad una classificazione in base al comportamento che essi assumono nei confronti dell’ambiente in cui sono immersi. Successivamente verranno trattate le tecniche di Stigmergia e Swarm Intelligence, analizzando nel dettaglio le profonde connessioni che queste tecniche hanno con il mondo della Biologia; infine saranno affrontate le tematiche riguardanti il mondo dei Social Media ed in particolare come questi possano diventare degli strumenti in grado di monitorare il mondo che ci circonda grazie alle caratteristiche di pervasività proprie di questi sistemi.

2.1 Sistemi Multi-Agente

I sistemi multi-agente, detti anche sistemi ad agenti multipli, sono un paradigma di progettazione e sviluppo del software emerso negli ultimi anni, particolarmente efficace in ambienti distribuiti; in particolare i sistemi multi-agente si sono rivelati molto utili alcuni specifici ambiti di utilizzo di un ambiente distribuito quali la simulazione di fenomeni complessi, la risoluzione di problemi, e la progettazione di programmi. Un sistema multi-agente è sistema costituito da un insieme di agenti, entità indipendenti e autonome, capaci di interagire con l’ambiente circostante (detto contesto). Un sistema di questo tipo è quindi utilizzato in tutti quei casi in cui un problema è difficilmente risolvibile da sistemi monolitici o a thread (agente) singolo, sia in termini di complessità intrinseca della risoluzione del problema che in termini di risorse da utilizzare [5].

Utilizzando un sistema multi-agente, il problema complesso viene scomposto in sotto problemi più semplici che vengono affidati ad uno o più agenti; questi, eseguendo le operazioni per i quali sono stati progettati e interagendo tra loro, porteranno alla risoluzione del problema finale. Ogni agente è un oggetto software con un suo flusso privato di esecuzione, che compie operazioni in relazione al suo compito che gli è stato assegnato.

14

È possibile introdurre anche una classificazione degli agenti secondo due criteri:

 Agenti Cognitivi o Reattivi

 Comportamento Teleonomico o Riflesso

La distinzione tra cognitivo e reattivo attiene essenzialmente alla rappresentazione del mondo di cui dispone l'agente. Se il singolo agente è dotato d'una rappresentazione simbolica del mondo a partire dalla quale è in grado di formulare ragionamenti, si parlerà di agente cognitivo; in caso contrario, se l’agente non dispone che di una rappresentazione subsimbolica, vale a dire soltanto limitata alle percezioni, si parlerà di agente reattivo. Tale distinzione corrisponde a due scuole di pensiero relative ai sistemi multi-agente: la prima sostiene un approccio basato su insiemi di agenti "intelligenti" collaborativi, da una prospettiva più sociologica; la seconda studia la possibilità dell'emergenza di un comportamento "intelligente" di un insieme d'agenti non intelligenti, come avviene ad esempio in alcune colonie di insetti come quelle delle formiche.

La seconda distinzione tra comportamento teleonomico o riflesso divide i comportamenti intenzionali (perseguire scopi espliciti) dai comportamenti legati a delle percezioni. Le tendenze degli agenti possono essere anche espresse esplicitamente all'interno degli agenti o al contrario provenire dall'ambiente.

Nelle successiva Figura 3 e Figura 4, è possibile apprezzare le principali differenze tra il comportamento di un Agente Riflesso ed uno Teleonomico.

15

Figura 4 - Comportamento di un Agente Teleonomico

E’ quindi possibile compilare una tabella che riassuma le tipologie di comportamento in base alla tassonomia illustrata in precedenza.

Agenti Cognitivi Agenti Reattivi

Comportamento Riflesso Agenti Intenzionali Agenti Impulsivi

Comportamento Teleonomico Agenti Modulari Agenti Tropici

Tabella 1 - Classificazione di un Agente

Gli agenti cognitivi sono il più delle volte intenzionali, cioè hanno scopi prefissati che tentano di realizzare. In certi casi si possono pure trovare degli agenti detti modulari, i quali, anche se possiedono una rappresentazione del loro universo, non hanno tuttavia degli scopi precisi. Tali agenti potrebbero servire ad esempio a rispondere alle interrogazioni avanzate da altri agenti all’interno di un universo.

Gli agenti reattivi possono a loro volta essere suddivisi in agenti impulsivi e tropici. Un agente impulsivo avrà una missione ben determinata e si comporterà di conseguenza qualora percepisca che l'ambiente non risponde più allo scopo che gli è stato. L'agente tropico, dal canto suo, reagisce solo allo stato locale dell'ambiente. La fonte della motivazione è nel primo caso interna e nel secondo caso è legata esclusivamente all'ambiente.

16

Gli agenti che operano in sistemi di questo tipo devono inoltre possedere alcune caratteristiche specifiche fondamentali:

 Autonomia

Gli agenti, infatti, devono essere parzialmente indipendenti, coscienti del proprio stato e dell’ambiente in cui si trovano ed essere autonomi rispetto alle interazioni con esso.

 Visione Locale

Nessun agente ha una visione globale del sistema. L’utilizzo di un sistema multi-agente infatti presuppone che il sistema stesso sia troppo complesso perché venga affidato ad un solo agente dotato di visione globale. I vari agenti hanno a disposizione soltanto una visione parziale del sistema e sfruttano la presenza degli altri agenti per concorrere alla risoluzione del problema.

 Decentralizzazione

Non esiste infatti nessun agente che ha il compito di controllare le altre singole entità del sistema.

Un agente inoltre può implementare diversi tipi di meccanismi:

 Collaborazione

In questo caso diversi agenti collaborano e condividono tra loro risorse al fine di raggiungere uno scopo comune.

 Competizione

Gli agenti competono in situazioni in cui si trovano a condividere risorse essenziali allo scopo finale.

 Coordinamento

In questo meccanismo avvengono sia negoziazione di risorse che coordinamento di azioni specifiche.

2.2 Swarm Intelligence

La swarm intelligence trae spunto dall’osservazione di sistemi naturali come colonie di insetti (come formiche, api o termiti), branchi di pesci, stormi di uccelli oppure da sistemi biologici come ad esempio il sistema immunitario del corpo umano. Esso

17

prende in considerazione lo studio dei sistemi auto-organizzati, nei quali un'azione complessa deriva da un'intelligenza collettiva. Secondo la definizione di Beni e Watt la swarm intelligence può essere definita come: “Proprietà di un sistema in cui il comportamento collettivo di agenti (non sofisticati) che interagiscono localmente con l’ambiente produce l’emergere di pattern funzionali globali nel sistema”.[6]

Uno sciame (swarm) è definito come l’insieme di entità autonome (agenti), distribuite nello spazio, che interagiscono tra loro e che agiscono sul loro ambiente locale. Lo sciame presenta delle caratteristiche specifiche, valide per ogni individuo che ne fa parte:

 Ogni individuo del sistema dispone di “capacità limitate”.

 Ogni individuo del sistema non conosce lo stato globale del sistema.

 Assenza di un ente coordinatore (ad esempio in uno sciame di api, la regina non coordina l’attività delle altre api).

Le interazioni fra i vari agenti, come è già stato descritto, fa emergere un comportamento globale “intelligente”; ci si riferisce ad un comportamento di questo tipo con il termine di “comportamento emergente”.[7]

2.3 Stigmergia

Il termine stigmergia fu introdotto dallo zoologo Pierre-Paul Grassè, al fine di spiegare il comportamento delle termiti durante la costruzione dei nidi; esso deriva dalle parole greche “stigma” ed “ergon”, cioè “segno” e “lavoro”, il che significa "lavoro guidato da stimoli". La stigmergia fornisce una visione ad alto livello in cui N agenti cooperano per raggiungere un qualche obiettivo, si ottiene quindi un meccanismo generale che relaziona il comportamento individuale con quello della colonia. La stigmergia può essere attiva o passiva e in genere presenta le seguenti caratteristiche:

 Scalabilità  Tolleranza ai guasti;  Adattabilità  Velocità  Modularità  Autonomia  Parallelismo

18

La struttura fortemente parallela degli sciami, permette di sfruttare il numero degli individui, effettivamente disponibili ad ogni istante di tempo, capaci di percepire l'ambiente ed interagire con esso.

Il principio che vi è alla base, dunque, consiste nel lasciare una traccia iniziale nel sistema in modo da stimolare altri individui a fare lo stesso e rafforzare questa, innescando un meccanismo di feedback positivo che porterà alla comparsa di attività coerenti apparentemente sistematiche. Si evince dunque che la stigmergia è una forma di auto-organizzazione, producendo strutture anche complesse senza il bisogno di una pianificazione o di entità di coordinamento.

Un tipico esempio di auto-organizzazione e stigmergia è quello della ricerca di alimenti di una colonia di formiche; ogni formica, dopo aver individuato del cibo, rilascia nell’ambiente una traccia di feromoni (la cui intensità decade nel tempo) lungo il tragitto che segue nel ritornare verso il formicaio. Le altre formiche, anch’esse alla ricerca di cibo, non seguiranno più un percorso casuale nella loro ricerca, ma saranno guidate dalla traccia lasciata in precedenza. La scelta del percorso da seguire è guidata dall’intensità della scia: più essa è intensa più è probabile che venga scelta come percorso.

Se quindi quel percorso è utilizzato da molte formiche (si hanno quindi molti feedback positivi) l’intensità si rinforzerà a ogni passaggio e questo sarà, molto probabilmente, scelto come percorso preferenziale anche dal resto della colonia. Quando si sarà esaurita la fonte di cibo, l’intensità del percorso, considerando la scarsa percorrenza di questo, andrà a decadere con il passare del tempo.

In questo esempio, illustrato in Figura 5, si vede chiaramente come non sia presente alcuna forma di controllo centralizzato che vada a coordinare le formiche (agenti del sistema) nell’attuazione del processo “ricerca cibo” ma siano le formiche stesse a coordinarsi le une con le altre per giungere, in modo organizzato, alla soluzione del problema.

19

Figura 5 - Scelta del percorso più breve da parte delle formiche

In ogni applicazione swarm, il “comportamento della colonia” dipende dalle interazioni fra i singoli individui che la compongono. Losmart agent (la formica nel caso del formicaio)è in grado di percepire l'ambiente circostante e di prendere decisioni in merito al quantitativo di informazioni da trasferire nell’ambiente. Il carico di lavoro è distribuito in modo che il maggior numero possibile di agenti disponibili possa essere coinvolto nel processo. Questo fa sì che ad ogni istante si sfrutti al massimo la capacità computazionale disponibile. I comportamenti collettivi permettono inoltre di ottenere una discreta tolleranza ai guasti.

A seconda delle caratteristiche dell’agente e dello stimolo è possibile identificare una tassonomia valida per la stigmergia.

In particolare, sono quattro le tipologie di stigmergia che possiamo distinguere :

• Attenzione dell’agente:

- marker-based: l’agente utilizza gli stimoli che percepisce

- sematectonic: gli agenti hanno un proprio obiettivo interno da conseguire.

• Tipologia del segnale:

20

- qualitativo: basato sulla combinazione di diversi segnali, ad esempio diversi feromoni.

La ricerca dei percorsi delle formiche è ad esempio, nella tassonomia così descritta, un modello di comunicazione stigmergica marker-based/quantitativo.

2.4 Studi e Applicazioni della Swarm Intelligence

MECCANISMI DI RAGGRUPPAMENTO DELLE FORMICHE

Uno dei primi studi in campo naturale, cioè quando lo studio riguarda i sistemi biologici, è quello a cui hanno contribuito Jean Louis Deneubourg e il suo gruppo di ricerca che in cui è stato dimostrato che quando a una colonia di formiche viene data la possibilità di scelta tra due diversi percorsi, uno più lungo dell’altro, di raggiungere un punto ricco di vettovaglie, inizialmente la scelta è casuale e distribuita uniformemente tra le due vie, ma col passare del tempo le singole formiche (e quindi l’intera colonia) sceglieranno con una probabilità sempre maggiore il percorso più breve. Tale esperimento è stato illustrato nel dettaglio nella sezione precedente.

Sulla base dell’esperimento di Deneubourg e delle successive pubblicazioni, nel 1994 Ralph Becker propose uno dei primi studi in campo artificiale, cioè quando invece si analizza il comportamento di agenti che sono frutto della mente, programmando un gruppo di piccoli robot per comportarsi in modo similare a quello di una colonia di formiche nell’atto di organizzare zone di raccolta dei corpi per i propri simili (Figura 6).

21

COSTRUZIONE DEL NIDO DA PARTE DELLE TERMITI

Le termiti sono in grado di costruire nidi di dimensioni enormi proporzionalmente alla loro dimensione (che è dell’ordine di pochi millimetri); i nidi possono infatti superare il metro di diametro e i due metri di altezza.

Negli anni ’50 sono stati svolti i primi studi tesi a determinare i meccanismi di coordinamento che portano le termiti a costruire tali nidi; tali studi hanno portato a formulare modelli sull’attività di comunicazione stigmergica di tali insetti in grado di giustificare tale comportamento globale. Alcuni di questi studi sono riproposti in campo informatico per la simulazione di strutture che richiamano la morfologia dei nidi di termiti.

COORDINAMENTO DEGLI UCCELLI E DEI BRANCHI DI PESCI

Un esempio evidente di altissimo livello di coordinamento è riscontrabile nel movimento degli stormi di uccelli nel cielo o dei branchi di piccoli pesci in mare; in questi esempi, l’elevato livello di coordinamento è raggiunto attraverso meccanismi di collaborazione di numerosi individui in assenza di un meccanismo di comunicazione diretta.

E’ stato dimostrato da numerose ricerche come questi eleganti comportamenti avvengano in assenza di un leader che gestisca il coordinamento del gruppo ma siano basati esclusivamente sulla percezione che il singolo individuo ha dell’ambiente circostante; questa percezione è generata da diversi fattori quali ad esempio la distanza, la velocità, la direzione e il numero dei propri vicini di viaggio.

2.5 Social Media e nuovi paradigmi di comunicazione

La condivisione di informazioni, contenuti e opinioni in rete è ormai una realtà quotidiana e consolidata. Nel corso degli ultimi anni i Social Media , ovvero quelle piattaforme web che consentono la creazione e lo scambio di contenuti generati dagli, hanno rappresentato un fondamentale cambiamento nel modo di comunicare delle persone e delle aziende, diventando a tutti gli effetti nuovi vettori per la diffusione dell’informazione e ampliando le possibilità di interazione tra soggetti.

In questo senso nei Social Media ha avuto luogo una vera e propria democratizzazione dell’informazione e le persone si sono trasformate da fruitori di contenuti ad editori. I Social Media sono ad oggi il mezzo attraverso cui milioni di utenti interagiscono

22

secondo nuovi paradigmi di comunicazione e partecipazione; essi costituiscono il terreno ideale per lo studio della diffusione di nuovi temi di discussione e nuove dinamiche di comunicazione. Nei fatti ogni persona che inserisce contenuti nel web aumenta di fatto le informazioni che si possono ricavare dai Social Media, arricchendoli con le proprie esperienze.

Figura 7 - Panorama dei Social Media

Le principali piattaforme sociali quali Facebook, Twitter, YouTube, Wikipedia, ecc. che oggi raccolgono milioni di utenti, permettono non solo la condivisione di messaggi di testo e recensioni, ma anche di contenuti multimediali quali foto, video, links e molto altro.

Il primo Social Media al mondo per numero di iscritti è Facebook: a Luglio 2014 gli utenti iscritti hanno infatti raggiunto quota 1,3 miliardi che, se paragonati al numero di abitanti che popolano i vari stati mondiali, di fatto lo rendono la seconda nazione dietro alla Cina. Secondo statistiche di Luglio 2014 ,Twitter ha più di 500 milioni di iscrizioni, con 288 milioni di utenti attivi ogni mese e 400 milioni di tweet inviati ogni giorno. La maggior parte degli iscritti sono teenegers, ma Twitter grazie alla sua enorme facilità d'uso ha raccolto migliaia di utenti “senior” (55-65 anni) che si sono iscritti e twittano ogni giorno.

Ogni utente di queste applicazioni lascia quindi una traccia delle proprie attività e delle proprie esperienze, ed è proprio per questo motivo che negli ultimi anni i Social Media sono diventati un argomento di ricerca sempre più popolare; i numerosi ricercatori che studiano le dinamiche dei Social Media infatti sono interessati ad usufruire dell’enorme mole di informazioni fresche che ogni giorno vengono pubblicate e condivise online per

23

compiere analisi con gli scopi più disparati: da quelle sociologiche, a quelle di marketing, a quelle più a carattere partecipativo e sociale, come l’alerting in particolari situazioni di disagio o emergenza.[11]

2.6 Social Sensing

Per via dello scenario appena descritto queste piattaforme costituiscono la base ideale per tutte le analisi incentrate sull’utilizzo dell’individuo come generatore di informazioni.

Questa branca di studi prende il nome di Social Sensing e si basa sul concetto che comunità o gruppi di persone possano fornire ognuna un insieme di informazioni, simili a quelle ricavabili da un singolo sensore, tali da generare nel complesso un’adeguata conoscenza su uno o più temi specifici.

Gli utenti dei Social Media possono quindi essere visti come veri e propri sensori in grado di fornire tempestive informazioni riguardo a particolari tematiche. La centralità assunta dalla rete nella comunicazione tra persone, unitamente al nuovo ruolo di piattaforma di Sensing dei Social Media, sollecita sul fronte della ricerca empirica, l’adozione di nuove forme sperimentali di analisi. La mole di dati coinvolti, la moltiplicazione dei soggetti da analizzare e delle piattaforme utilizzate impongono la costruzione di un disegno di ricerca e l’adozione di metodologie di raccolta, archiviazione e trattamento dei dati.

Tra i vari ambiti di studio relativi al Social Sensing vi è quello relativo all’Emergency Management. Questo tema è di chiaro interesse per una molteplicità di soggetti: enti pubblici, operatori del settore dell’informazione, semplici cittadini. Tali soggetti hanno infatti la possibilità di raccogliere informazioni aggiornate su emergenti situazioni di pericolo, con lo scopo di acquisire una maggiore consapevolezza dello scenario creatosi, la possibilità di allertare gli interessati tempestivamente o verificare informazioni ottenute attraverso altri canali.

Un sistema in grado di assolvere a queste funzioni potrebbe rappresentare un valido strumento di supporto decisionale per chi opera nel settore.

Le informazioni su un evento in corso sono tanto più importanti quanto più tempestivamente vengono raccolte. Acquisire informazioni rapidamente lascia più tempo per prendere decisioni corrette riguardo la situazione da affrontare e consente

24

di allertare in anticipo la popolazione interessata contribuendo ad una migliore gestione dell’emergenza stessa.

Nell’ambito di questo lavoro di tesi ci si prefigge di raccogliere ed analizzare segnalazioni spontanee di utenti riguardanti fenomeni generati dall’eccessivo traffico urbano.

L’idea nasce dall’intuizione che le prime persone a rendersi conto di questi fenomeni siano proprio i diretti interessati; questo, unitamente al ruolo centrale dei Social Media nei moderni paradigmi di comunicazione, può consentire di individuare e raccogliere importanti informazioni sui suddetti eventi a partire dalle testimonianze di chi ne è coinvolto in prima persona.

Per questo motivo l’analisi si concentra su una famiglia specifica dei Social Media: i Social Network. Un Social Network (o Rete Sociale) è una piattaforma che consente l’instaurarsi di relazioni virtuali tra gli utenti, in modo similare a quello che succede nella società reale.

Su queste piattaforme gli utenti si scambiano e condividono messaggi parlando dei propri interessi e delle loro attività giornaliere. I Social Network si prestano in modo particolare a questo tipo di analisi per via dell’elevato numero di utenti che raccolgono e grazie alla loro elevata interattività. Oltre a Facebook e Twitter vi sono numerosi altri Social Network con un bacino di utenza di diversi milioni di iscritti ed ogni Social Network ha le sue caratteristiche tipiche che lo distinguono dagli altri.

2.7 Uso di Twitter per applicazioni di Social Sensing

Analizzando le caratteristiche e le principali differenze tra i maggiori Social Network si può notare come Twitter presenti delle peculiarità che lo rendono particolarmente indicato come fonte di dati per piattaforme di Social Sensing.[8]

Un’importante caratteristica di Twitter, che lo distingue dal suo principale competitor, risiede nel tipo di messaggi che gli utenti tendono a scambiarsi. Mentre su Facebook le persone sono invitate a parlare dei loro pensieri e opinioni, su Twitter generalmente gli utenti parlano delle proprie attività e quindi di quello che succede intorno a loro. Raccogliendo i messaggi degli utenti di Twitter è quindi più facile acquisire una buona context awarness, cioè capire cosa sta succedendo e dove.

25

Figura 8 - Esempio di Tweet

In aggiunta Twitter risulta più interattivo e responsive rispetto agli altri principali SN: anche per via della limitazione imposta alla lunghezza massima di un messaggio pubblico (massimo 140 caratteri), il tempo di vita dei tweet (così si chiamano i messaggi scambiati su Twitter) è piuttosto breve e gli utenti tendono a twittare con maggiore frequenza.

Figura 9 - Confronto tra la vita di un tweet e di un post

La figura precedente mostra i risultati di uno studio sul tempo di vita di tweet e post tramite boxplot; il tempo di vita di un contenuto è il tempo che trascorre dal momento della sua creazione al momento dell’ultima interazione con lo stesso (ad esempio attraverso like, commenti, retweet,ecc).

Lo studio è stato effettuato analizzando le interazioni con un campione di 10.000 post e 10.000 tweet ed ha evidenziato una netta differenza di longevità tra i contenuti pubblicati sui due SN: in particolare su tutto il campione analizzato il post più longevo ha avuto un tempo di vita di 21 giorni, mentre il tweet più longevo solo di 31 ore.

In conclusione Twitter è più istantaneo degli altri principali Social Network e rappresenta una fotografia più aggiornata di quello che sta accadendo.

26

3 Progettazione

e

Realizzazione

del

Sistema

Il Sistema che è stato progettato affronta il problema del rilevamento e della caratterizzazione del traffico urbano. Il rilevamento è fatto attraverso tecniche di crowd sensing e stigmergia applicate alle tracce GPS dei veicoli che attraversano la rete urbana. I parametri del sistema di rilevamento sono ottimizzati per adattarsi alla variabilità del traffico e della topologia della rete stradale attraverso l’algoritmo di Evoluzione Differenziale. Gli eventi di traffico individuati sono caratterizzati con tecniche di Social Sensing. La descrizione dell’evento è fatta con un Tag Cloud generato da un insieme di testi raccolti dal social network Twitter e opportunamente manipolati.

Il sistema è composto di due sottosistemi (Figura 10) :

 Traffic Detection Subsystem

 Traffic Information Subsystem

Il primo sottosistema utilizza le coordinate GPS dei veicoli per valutare se nella zono in cui stanno transitando tali veicoli siano presenti condizioni di traffico più o meno intenso. Il secondo sottosistema invece viene attivato dal primo nel momento in cui viene rilevato un evento di traffico e si occupa di fornire una caratterizzazione di tale evento come individuarne la causa o segnalare eventuali eventi collaterali collegati.

27

3.1 Progettazione del Modulo di Traffic Detection

Prima di procedere alla progettazione del modulo, è stato innanzitutto affrontto il problema di rappresentare la rete stradale urbana in maniera coerente e comprensibile agli strumenti a disposizione (Figura 11) .

Possiamo quindi rappresentare la rete come un grafo, ossia un insieme di archi che rappresentano le strade della città e di nodi che invece rappresentano gli incroci e le terminazioni stradali come i vicoli ciechi e i punti di uscita dalla città.

Per ottenere una rappresentazione della rete corretta non solo concettualmente ma anche graficamente si posiziona il grafo in uno spazio geografico e si fanno corrispondere i nodi alle coordinate geografiche GPS degli elementi che essi rappresentano nella realtà.

Dettaglio della rete stradale urbana di Pisa Grafo della Rete Stradale

Figura 11 - Rappresentazione della Rete Stradale

L’uso di archi orientati permette di caratterizzare le strade a senso unico. Per quelle a doppio senso si utilizza una coppia di archi di direzione opposta. Graficamente una strada a senso unico è rappresentata con un arco che termina con una freccia nella direzione di marcia, le strade a doppio senso invece sono rappresentate con archi privi di terminazioni particolari.

In questa tesi è stata scelta come città di riferimento una sezione della rete stradale urbana della città di Pisa. La rete così costruita viene analizzata per individuare un insieme di percorsi che copra tutte le possibili strade e tutti i possibili sensi di marcia della rete.

28

Si può a questo punto considerare ogni singolo percorso come un grande segmento stradale nel quale le auto, che viaggiano tutte nella stessa direzione, posso immettersi (e eventualmente uscire) in diversi punti compresi gli estremi.

La scelta di utilizzare diversi percorsi invece dell’intera rete stradale ci permette di ridurre il problema da un problema in due dimensioni a un problema in un’unica dimensione. Il modello ad agenti che sarà applicato a ogni percorso sarà quindi di più semplice realizzazione intuitiva e pratica.

3.1.1

Rappresentazione del Modello di Traffico

Un veicolo che percorre un tratto stradale è rappresentato da un agente che si sposta lungo il percorso. Ad istanti campionati ad intervallo di tempo costante l’agente valuta se la propria velocità è al di sotto di una determinata soglia e se questa condizione è verificata viene rilasciata un’impronta sul percorso, o sui percorsi nel caso che il tratto corrisponda a più percorsi. L’impronta ha la forma di un triangolo isoscele la cui base poggia sul segmento e l’agente si trova al centro di essa. La posizione dell’agente sul segmento è pari alla distanza percorsa dal veicolo lungo il tratto stradale corrispondente.

Le impronte depositate dagli agenti nello stesso percorso si sommano lungo l’asse verticale formando una traccia che rispecchia la situazione di traffico sul tratto stradale corrispondente. Valutando la conformazione della traccia è possibile identificare gli eventi.

Livello Virtuale

Il livello virtuale è il modello che ogni agente-veicolo utilizza per valutare il rilascio o meno di impronte nell’ambiente. Il rilascio di impronte viene effettuato se la velocità del veicolo scende sotto una determinata soglia. Questa valutazione è delegata allo Stillness Agent che utilizza due posizioni GPS, la posizione p(t-1) e la posizione p(t), per valutare la velocità del veicolo.

A livello virtuale l’agente utilizza due impronte rilasciate nelle posizioni p(t-1) e p(t); queste impronte hanno la forma di un trapezio isoscele con centro della base maggiore nel punto in cui si trova l’agente e sono caratterizzate dai seguenti parametri:

• Altezza h

29

• Base superiore B

• Baricentro orizzontale p(t)

Ognuna di queste impronte può essere variata modificando i parametri sopra descritti, in particolare b e B permettono di definire l’intervallo di velocità sotto il quale gli agenti iniziano a rilasciare impronte.

Le impronte vengono infatti rilasciate nel momento in cui i due trapezi isosceli incominciano a sovrapporsi, ovvero quando:

𝑝(𝑡) − 𝑝(𝑡 − 1) ≤ 𝐵

L’impronta rilasciata avrà intensità proporzionale all’altezza dell’intersezione dei trapezi, ovvero finché:

𝑏 ≤ 𝑝(𝑡) − 𝑝(𝑡 − 1) ≤ 𝐵

L’intensità sarà massima quando:

𝑝(𝑡) − 𝑝(𝑡 − 1) ≤ 𝑏

Questo modello permette da un lato di avere rilascio d’impronte solamente quando la velocità del veicolo scende sotto una determinata soglia evitando quindi di avere un eccesso d’impronte nell’ambiente che comporterebbe solo la comparsa di rumore, dall’altro anche di parametrizzare le soglie di velocità per avere l’intensità delle impronte proporzionale al rallentamento dei veicoli. In Figura 12 è riportata una rappresentazione del livello virtuale.

30 Livello Globale

Al livello globale gli agenti rilasciano delle impronte sul segmento dove queste vanno ad aggregarsi le une con le altre. Le impronte rilasciate hanno la forma di un triangolo isoscele e l’agente si trova nel punto medio della base che poggia sull’arco corrispondente come si nota in Figura 13.

Figura 13 - Livello Globale del Modello di Traffico

L’impronta è descritta dei seguenti parametri:

• Baricentro: p(t) • Altezza: I(t)

• Ampiezza: a

L’ambiente, ovvero l’arco, è descritto dai seguenti parametri:

• Lunghezza: l, pari alla lunghezza del tratto stradale corrispondente

• Evaporazione: θ, coefficiente che determina il decadimento delle impronte presente sull’arco ad ogni istante successivo

All’istante t se il veicolo viaggia al di sotto di una soglia di velocità di v, che soddisfa la condizione descritta al livello virtuale, l’agente deposita a livello globale un’impronta di altezza I nella posizione p(t) in cui si trova. All’istante successivo t+1 l’impronta I(t) non avrà più altezza I ma sarà evaporata di un fattore θ e la su altezza sarà I*θ. Se la velocità v(t+1) è ancora sotto la soglia v l’agente depositerà una nuova impronta in posizione p(t+1) che si sommerà alle impronte presenti nell’ambiente.

Altezza massima dell’impronta

Ai fini del rilevamento del traffico ogni tratto stradale viene considerato come un segmento di pari lunghezza; questo accorgimento permette di ridurre il sistema da bidimensionale a monodimensionale in quanto la posizione di un veicolo nello spazio viene prima assegnata al segmento corrispondente al tratto di strada su cui sta

31

viaggiando mentre la posizione sul segmento è individuata dalla distanza percorsa dall’inizio del tratto stradale.

Un veicolo fermo deposita ad ogni istante nuove impronte nella medesima posizione che si vanno a sommare tra loro (Figura 14). In questo caso l’altezza massima raggiungibile dall’impronta di un singolo agente è data da:

𝐼𝑚𝑎𝑥 = 𝐼(𝑡) + 𝐼(𝑡 − 1) ∗ 𝜃 + 𝐼(𝑡 − 2) ∗ 𝜃2+ … + 𝐼(0) ∗ 𝜃𝑡 = 𝐼(𝑡) ∗ (𝜃0_{+ 𝜃}1_{+ 𝜃}𝑡_{) = 𝐼 (𝑡 ) ∗} 1

1 − 𝜃

Se nel segmento sono presenti più veicoli la somma delle impronte dipende dalla semiampiezza a dell’impronta e da quanti veicoli sono presenti nel sistema; supponendo che ogni veicolo occupi uno spazio s, che consideri le dimensioni e la distanza di sicurezza, il numero di veicoli n che contribuiscono all’altezza di un’impronta sarà dato dal veicolo che stiamo considerando più le impronte dei veicoli che si trovano nella semiampiezza dell’impronta a.

𝑛 = 1 + 𝑎 / 𝑠

In definitiva l’altezza massima dell’impronta sarà data da:

𝐼𝑚𝑎𝑥 = 𝐼 (𝑡 ) ∗

1

1 − 𝜃

∗ 𝑛

32

3.1.2

Ottimizzazione del Modello di Traffico

Il modello fin qui proposto è in grado di individuare situazioni di traffico di varia natura lungo il percorso che è stato scelto come campione, ma non è ancora esente da errori: è infatti necessaria una opportuna configurazione dei parametri fondamentali per fare in modo che le rilevazioni avvengano nel modo più corretto possibile; infatti con le configurazioni originali non c’è certezza del fatto che un evento di traffico sia rilevato correttamente sia dal punto di vista temporale che da quello spaziale.

Figura 15 - Schema di Funzionamento dell'Ottimizzatore

Per accuratezza spaziale si intente la capacità di identificare correttamente per ogni istante di tempo l’intervallo di spazio in cui avviene l’evento di traffico; per accuratezza temporale la capacità di individuare gli istanti di inizio e fine dell’evento.

E’ necessario quindi definire una metrica che permetta di quantificare l’accuratezza spaziale e temporale della rilevazione degli eventi e, sulla base di questa, cambiare i parametri del modello per ottimizzarne il funzionamento come illustrato in Figura 15.

33

A tal fine definiamo in primo luogo quella che per noi sarà l’ontologia di traffico, ovvero la condizione necessaria e sufficiente per poter distinguere una situazione patologica di disagio alla circolazione veicolare da una situazione fisiologica.

Ontologia di Traffico

Al fine di discriminare una situazione di traffico rilevante da una irrilevante per il nostro sistema consideriamo traffico una colonna di auto lunga almeno 100 metri e che perduri per almeno due minuti di tempo. La condizione spaziale indica la presenza di un numero consistente di veicoli che stazionano o si spostano a velocità ridotta influenzando negativamente il normale flusso veicolare; la condizione temporale individua il mantenimento dell’evento e quindi la presenza della situazione di disagio.

Per il singolo veicolo definiamo una soglia di velocità sopra la quale il modello è inattivo e non segnala in alcun modo eventi; la soglia in questione è posta a 20 km/h. Scendere al di sotto di questa velocità è quindi condizione necessaria ma non sufficiente per il rilevamento di eventi. Ricordiamo che il modello è pensato per rilevare eventi in ambito urbano dove il limite di velocità è per legge di 50 km/h e quindi una velocità di crociera pari a 20Km/h non è chiaramente sintomo di ingorgo stradale se elevata a unica misura degli eventi.

Responsività Spaziale e Temporale

La metrica individua un unico evento di traffico lungo il percorso e valuta l’accuratezza spaziale e temporale del modello. Nel nostro caso è sufficiente la classificazione di un evento di traffico in quanto possiamo ripetere la valutazione della metrica più volte per individuare eventi multipli.

La Responsiveness è, in Informatica, un concetto che si riferisce alla capacità specifica di un sistema o di una unità funzionale di completare compiti assegnati entro un dato vincolo temporale.

Per definire la metrica partiamo dalla Responsiveness temporale che valuta l’accuratezza, temporale appunto, di un classificatore in grado di riconoscere l’inizio e la fine di eventi.

Nella formula seguente vediamo come si calcola la Responsiveness di un insieme di eventi 𝑆𝑖 caratterizzati da 𝑁𝑖 coppie inizio e fine 𝑡𝑖,𝑝 rilevate dal classificatore al tempo

𝑡′_𝑖,𝑝 .

𝑅𝐸𝑆𝑃(𝑆

) =

∑

|𝑡

− 𝑡

|

𝑁

34

La metrica per il nostro modello dovrà quindi da un lato tener conto dell’accuratezza nell’identificare correttamente l’inizio e la fine dell’evento di traffico in modo analogo alla Responsiveness temporale sopra descritta, poi, nell’intervallo di tempo indicato, valutare l’accuratezza spaziale. Il funzionamento ottimale del modello si ottiene quando questo è in grado di rilevare l’evento nello stesso momento in cui esso si presenta nella realtà.

Definiamo quindi alcuni parametri :

 𝑡′_{𝑠𝑡𝑎𝑟𝑡} e 𝑡′_{𝑠𝑡𝑜𝑝}: tempo di inizio e fine durante i quali il modello riesce ad

individuare l’ingorgo

 𝑡_{𝑠𝑡𝑎𝑟𝑡} e 𝑡_{𝑠𝑡𝑜𝑝}: tempo di inizio e fine reali durante i quali ha luogo l’ingorgo

 𝑠′(𝑡)𝐼𝑁 e 𝑠′(𝑡)𝐹𝐼𝑁: punto di inizio e fine al tempo t lungo i quali il modello riesce ad

individuare l’ingorgo

 𝑠(𝑡)𝐼𝑁 e 𝑠(𝑡)𝐹𝐼𝑁: punto di inizio e fine reali al tempo t lungo i quali ha luogo

l’ingorgo

Dato un evento di traffico avente come caratteristiche un istante di inizio e uno di fine pari a 𝑡𝑠𝑡𝑎𝑟𝑡 e 𝑡𝑠𝑡𝑜𝑝 e una ampiezza spaziale per ogni istante temporale definita dai valori

𝑠(𝑡)_𝐼𝑁 e 𝑠(𝑡)_𝐹𝐼𝑁 la Responsiveness del sistema si può esprimere in questo modo:

𝑅𝐸𝑆𝑃(𝑆

) = 𝑅𝐸𝑆𝑃(𝑆

)

+ 𝑅𝐸𝑆𝑃(𝑆

)

𝑅𝐸𝑆𝑃(𝑆

)

=

|𝑡

− 𝑡

| + |𝑡

− 𝑡

|

|𝑡

− 𝑡

|

𝑅𝐸𝑆𝑃(𝑆

)

=

1

|𝑡

− 𝑡

|

∑

|𝑠

(𝑡) − 𝑠

(𝑡)| + |𝑠

(𝑡) − 𝑠

(𝑡)|

|𝑠

(𝑡) − 𝑠

(𝑡)|

Nella formula precedente possiamo notare come, per un singolo evento di traffico, il primo addendo stima l’accuratezza temporale del modello valutando lo scostamento tra l’inizio e la fine reali e rilevati. Il secondo addendo invece misura, durante l’intervallo di tempo precedente, l’accuratezza dell’intervallo spaziale.

Rispettando l’ontologia di traffico precedentemente definita, viene impedito alla formula della Responsiveness di divergere verso infinito in quanto la differenza tra

35

l’istante temporale di inizio e fine ingorgo è di almeno 2 minuti mentre la differenza tra la posizione spaziale finale e iniziale è di almeno 100m.

Inoltre, la presenza del denominatore in entrambi gli addendi della formula, consente di normalizzare il risultato.

Influenza dei Parametri del Modello sulla Responsività

Il rilascio delle impronte da parte del modello ad agenti avviene all’interno di una griglia di valori sulla base delle posizioni e delle velocità dei veicoli nel mondo reale; ad ogni istante temporale, più precisamente al termine della fase di raccolta delle posizioni dei veicoli, viene analizzata la griglia dei valori alla ricerca di eventuali criticità corrispondenti alla precedente definizione di traffico.

Risulta chiaro che la forma delle impronte e la loro durata di evaporazione influenzano la capacità di individuare temporalmente e spazialmente gli eventi di traffico. Una durata di evaporazione delle impronte eccessivamente prolungata nel tempo porterà il sistema a individuare con più facilità ingorghi anche se questi non si sono manifestati nella realtà, mentre una dimensione di base delle impronte molto piccola porterebbe a poche sovrapposizioni tra le impronte e il sistema si comporterebbe in maniera opposta, cioè eventualmente non riconoscendo eventi di traffico che invece sono presenti nella realtà.

Da questa breve analisi è possibile individuare nella dimensione dell’impronta e nel fattore di evaporazione dell’impronta i parametri che influenzano maggiormente la Responsiveness.

Risoluzione del problema di Ottimizzazione

Una volta stabilito che i parametri che influenzano il funzionamento del modello in termini di Responsiveness sono l’evaporazione delle impronte, la loro semiampiezza e la soglia di attivazione del traffico, si rende necessario studiare un meccanismo di ottimizzazione di tali parametri.

Poiché il problema di ottimizzazione che stiamo considerando è un problema non lineare, non è quindi facilmente risolvibile con algoritmi di ottimizzazione di tipo deterministico; per la sua risoluzione bisogna quindi sfruttare un approccio metaeuristico alla risoluzione del problema.

Una tecnica risolutiva di un problema è detta euristica se il suo procedimento non segue regole o percorsi precisi, ma per ogni scelta necessaria ci si affida all’analisi dello stato attuale, all’esperienza e all’intuito.

36

Ogni volta che si prende una decisione di questo tipo bisogna verificare se ci siamo avvicinati o meno a una soluzione possibile del problema. Anche nel caso in cui ci fossimo allontanati dall’ottimo del problema, le scelte precedentemente effettuate contribuiranno ad allargare la nostra conoscenza del problema.

La metaeuristica è un metodologia per l’appunto di tipo euristico di risoluzione di una classe molto ampia di problemi computazionali la quale prevede di applicare e combinare procedure in parte euristiche e in parte deterministiche con l’obiettivo di individuare procedure robuste ed efficienti.

Per la risoluzione del problema di ottimizzazione sono state prese in considerazione tre tecniche euristiche di valutazione e ottimizzazione di soluzioni: l’algoritmo genetico (GA), l’evoluzione differenziale (DE) e l’ottimizzazione con sciami di particelle (PSO).

L’idea che sta alla base di questi tre algoritmi è la stessa: si parte inizialmente da un gruppo casuale di possibili soluzioni di un problema e si combinano fra loro in modo che dopo una serie di tali combinazioni, scartando le soluzioni meno affini, si arrivi alla soluzione o alle soluzioni ottime o, in alternativa, a soluzioni che risultino qualitativamente migliori delle soluzioni di partenza.

Queste tecniche sono usate soprattutto per individuare soluzioni di problemi di cui non si conoscono algoritmi risolutivi di complessità lineare o polinomiale perché, nonostante non sia possibile stabilire con precisione il tempo necessario a individuare la o le soluzioni ottimali del problema, arrivano in tempi brevi a soluzioni più che accettabili.

Gli algoritmi prevedono tre fasi di esecuzione:

1. Inizializzazione casuale della popolazione di soluzioni.

2. Valutazione della popolazione dei suoi membri attraverso l’utilizzo di una funzione di fitness.

3. Generazione di una nuova popolazione attraverso meccanismi di ricombinazione. 4.

Esaminiamo brevemente le caratteristiche specifiche dei tre algoritmi elencati in precedenza.

ALGORITMO GENETICO

Un algoritmo genetico (GA) è un algoritmo euristico ispirato al principio della selezione naturale ed evoluzione biologica teorizzato nel 1859 da Charles Darwin. L'aggettivo "genetico" deriva dal fatto che il modello evolutivo darwiniano trova spiegazioni nella branca della biologia detta genetica e dal fatto che gli algoritmi genetici attuano dei

37

meccanismi concettualmente simili a quelli dei processi biochimici scoperti da questa scienza.

La vera prima creazione di un algoritmo genetico è tuttavia storicamente attribuita a John Henry Holland che, nel 1975, nel libro Adaptation in Natural and Artificial Systems pubblicò una serie di teorie e di tecniche tuttora di fondamentale importanza per lo studio e lo sviluppo della materia.

E’ necessario premettere che gli Algoritmi Genetici ereditano e riadattano dalla biologia alcune terminologie che vengono qui preventivamente presentate per una successiva maggiore chiarezza espositiva:

 Cromosoma: una delle soluzioni ad un problema considerato. Generalmente è codificata con un vettore di bit o di caratteri.

 Popolazione: insieme di soluzioni relative al problema considerato.

 Gene: parte di un cromosoma. Generalmente consiste in una o più parti del vettore di bit o caratteri che codificano il cromosoma.

 Fitness: grado di valutazione associato ad una soluzione. La valutazione avviene in base ad una funzione appositamente progettata detta funzione di fitness.

 Crossover: generazione di una nuova soluzione mescolando delle soluzioni esistenti.

 Mutazione: alterazione casuale di una soluzione.

Un tipico algoritmo genetico, nel corso della sua esecuzione, provvede a fare evolvere delle soluzioni secondo il seguente schema di base:

1. Generazione casuale della prima popolazione di cromosomi.

2. Applicazione della funzione di fitness ai cromosomi appartenenti all'attuale popolazione.

3. Selezione delle soluzioni considerate migliori in base al risultato della funzione di fitness e della logica di selezione scelta.

4. Applicazione degli operatori di mutazione e crossover per generare delle soluzioni ibride a partire dalle soluzioni scelte al punto 3.

5. Creazione di una nuova popolazione a partire dalle soluzioni identificate al punto 4.

6. Esecuzione della procedura a partire dal punto 2 ed utilizzando la nuova popolazione creata al punto 5.

38

Di seguito è riportata una tabella riassuntiva degli effetti degli operatori di Mutazione, Crossover e Selezione.

Cross–Over

Figura 16 - Esempio di Cross - Over Occorre scegliere due individui genitori e uno

o più punti di taglio. Nel caso di un solo punto di taglio (one-point cross-over), le porzioni di genotipo alla sua destra vengono scambiate tra di loro, generando così due nuovi discendenti il cui genoma deriva dal rimescolamento di quello dei genitori

Mutazione

Figura 17 - Esempio di Mutazione L’applicazione dell’operatore provoca invece

l’alterazione di singoli geni di un cromosoma, aggiungendo alle componenti del genitore, con una piccola probabilità pm, un rumore gaussiano a media nulla

Selezione

La selezione degli individui che parteciperanno ad una nuova riproduzione è subordinata al valore di fitness associata ad ogni individuo. Gli individui con fitness più alta sono quelli che risolvono meglio il problema di ricerca dato e dunque devono essere privilegiati in questa fase, andando a formare la matrice Pi relativa alla i−esima generazione.

Tabella 2 - Caratteristiche principali degli operatori genetici

L'iterazione dei passi presentati precedentemente permette l'evoluzione verso una soluzione ottimizzata del problema considerato.

Poiché questo algoritmo di base soffre del fatto che alcune soluzioni ottime potrebbero essere perse durante il corso dell'evoluzione e del fatto che l'evoluzione potrebbe ricadere e stagnare in "ottimi locali" spesso viene integrato con la tecniche dell'"elitarismo" e con quella delle mutazioni casuali. La prima consiste in un ulteriore passo precedente al punto 3 che copia nelle nuove popolazioni anche gli individui migliori della popolazione precedente, la seconda invece successiva al punto 4 introduce nelle soluzioni individuate delle occasionali mutazioni casuali in modo da permettere l'uscita da eventuali ricadute in ottimi locali.

In sintesi si può dire che gli algoritmi genetici consistono in algoritmi che permettono di valutare delle soluzioni di partenza e che ricombinandole ed introducendo elementi di disordine sono in grado di crearne di nuove nel tentativo di convergere a soluzioni ottime. Queste tecniche vengono di norma utilizzate per tentare di risolvere problemi di ottimizzazione per i quali non si conoscono altri algoritmi efficienti di complessità lineare o polinomiale. Nonostante questo utilizzo, data la natura intrinseca di un