Equilibrio di Nash

In teoria dei giochi, gli elementi tipici di un gioco sono:

1. un numero di giocatori (o agenti): 1,…,N

2. un insieme di strategie Qi per l’i-esimo giocatore (una strategia è un qualsiasi tipo di grandezza)

3. una funzione di utilità da ottimizzare, per ciascun giocatore, Ji (α1, …, αn), che associa al giocatore i il guadagno derivante da ogni combinazione di strategie (il guadagno dipende non solo dalla strategia del giocatore, ma anche dalle

strategie degli avversari).

La nozione di equilibrio venne introdotta da J.Nash nel 1949, in cui si afferma che un insieme di strategie è un equilibrio se nessun giocatore ha interesse a cambiare la sua strategia a meno che non la cambi anche qualcun altro, quindi, tenendo ferme le strategie degli altri, nessuno cambierebbe la sua. Quindi:

𝐽𝑖(𝛼1, . . . , 𝛼𝑖, . . . , 𝛼𝑛) ≥ 𝐽𝑖(𝛼1, . . . , 𝛽, . . . , 𝛼𝑛) ∀𝛽 ∈ 𝑄𝑖, ∀𝑖 = 1, . . . , 𝑁 Ovvero, se un gioco ammette un equilibrio di Nash, ogni giocatore può avere una strategia αi che vorrà portare a termine se tutti gli altri giocatori hanno giocato la propria strategia αj. Infatti, se il giocatore i deciderà di giocare una strategia diversa da αi, mentre tutti gli altri hanno giocato la propria strategia αj, può solo peggiorare il suo guadagno o lasciarlo invariato. E’ evidente che se ogni giocatore vuole migliorare il proprio guadagno, deve modificare la sua strategia ed è vincolato dalle scelte degli altri.

L’equilibrio di Nash rappresenta una situazione in cui ogni giocatore o agente fa ciò che è meglio per sé, mirando a massimizzare il proprio profitto a prescindere dalle scelte degli avversari. Questo tipo di risultato ottenuto, non è detto che rappresenti la soluzione migliore per tutti. Si distingue, infatti, dall’equilibrio di Nash, l’ottimo di Pareto (o ottimo paretiano), in cui un insieme di strategie possono condurre al miglioramento del guadagno di alcuni giocatori senza ridurre il guadagno di nessuno, oppure ad aumentare il guadagno di tutti. Analogamente, il risultato migliore per tutti non può essere un equilibrio. In termini matematici avremo:

27

𝐽𝑖(𝛼^𝑜1, . . . , 𝛼^𝑜𝑖, . . . , 𝛼^𝑜𝑛) > 𝐽𝑖(𝛼1, . . . , 𝛼𝑖, . . . , 𝛼𝑛)

dove il primo membro della disequazione indica un insieme di strategie ottimali, che però non sono strategie dominanti o che portano ad un equilibrio. Di conseguenza, ogni giocatore seguirà sempre la strategia αi che gli permetterà di migliorare il proprio guadagno:

𝐽𝑖(𝛼^𝑜1, . . . , 𝛼𝑖, . . . , 𝛼^𝑜𝑛) > 𝐽𝑖(𝛼1, . . . , 𝛼^𝑜𝑖. . . , 𝛼𝑛)

Inoltre, un miglioramento del risultato derivante da α^oi dipende dalla situazione in cui tutti i giocatori abbiano scelto la stessa strategia α^oj (Ottimo di Pareto), poiché il guadagno del giocatore i dipende dalle scelte degli altri giocatori: se uno qualsiasi dei giocatori sceglie di non seguire una strategia ottimale, gli altri subiscono una riduzione del loro guadagno. In conclusione, ogni giocatore sceglierà di non rischiare e giocare la propria strategia dominante, portando ad un possibile risultato non ottimale. E’

possibile raggiungere una situazione che porta ad ottenere un risultato migliore per tutti se tutti i giocatori collaborano tra loro, anche istituendo un accordo vincolante tra loro, che porta ad una penalità nei confronti di chi non lo rispetta.

3.5 Perchè equilibrio di Wardrop ed equilibrio di Nash?

Per ottimizzare il traffico in una rete stradale è necessario assegnare determinati percorsi ai veicoli. C’è da dire, però, che non è detto che i veicoli seguono il percorso che gli è stato assegnato.

Nello studio dell’assegnazione dei percorsi sono stati, quindi, distinti due tipi di valori ideali:

• un valore ottimo per l’utente: tiene conto del percorso per una generica coppia OD (Origine- Destinazione) che deve essere intrapreso dall’utente, non

garantendo risultati ideali per coppie OD differenti;

• un valore ottimo per il sistema: tiene conto dell’efficienza del sistema, il che può produrre assegnazioni non ottimali per qualsiasi coppia OD.

Wardrop riconosce che le strade scelte dagli utenti sono quelle che essi scelgono come

“più corte” per raggiungere la loro destinazione, basandosi anche sulle condizioni di traffico. Questa situazione definisce, pertanto, l’equilibrio ottimo dell’utente

(ovviamente si considera che l’utente abbia un’ampia conoscenza della rete stradale, di tutti i percorsi possibili e dei flussi di traffico che possono generarsi).

28

L'equilibrio di Wardrop corrisponde all'equilibrio di Nash in una partita con un gran numero di giocatori [10].

L’ottimo di sistema si basa sul fatto che tutti i percorsi utilizzati per una coppia OD hanno lo stesso tempo di spostamento o costo marginale: infatti, se questi fossero diversi, si dovrebbero instradare i veicoli verso i percorsi con costi minori, riducendo il tempo di percorrenza. Questi due problemi, generalmente, non coincidono, in quanto l’equilibrio dell’utente non minimizza il tempo totale di viaggio nella rete. Inoltre, l’ottimo di sistema fornisce un inconveniente che si verifica quando viene calcolato il costo totale minimo della rete, poiché fornisce assegnazioni di percorsi non ottimali ai veicoli.

L’obiettivo è quello è quello di ridurre al minimo il tempo di viaggio totale.

Si intende colmare la differenza tra ottimizzazione di sistema e ottimizzazione

dell’utente: si utilizza una formulazione che si basa sul principio di Nash per produrre un “benessere egualitario” [11].

3.6 Modello di assegnazione del traffico

Di seguito viene riportato il modello di assegnazione del traffico utilizzato per la gestione del traffico all’interno di una rete stradale, in cui vengono presi in considerazione diversi parametri.

3.6.1 Assunzioni generali e sviluppo iniziale

Nel modello di ottimizzazione risultante si assume che ogni conducente abbia a disposizione tutte le conoscenze della rete, sui relativi percorsi e determinati tempi di viaggio; non solo, si suppone che ogni conducente conosca anche i tempi di

percorrenza che si potrebbero verificare nel momento in cui non si rispettasse il percorso assegnato dal sistema. Questa ipotesi può portare uno svantaggio nella sua considerazione a causa dell’imprevedibilità di eventuali congestioni di traffico. Inoltre, si presuppone che tutti gli utenti seguano le indicazioni del sistema e il percorso da esso assegnato. Si considera un sistema basato su prenotazione, in cui si rende noto lo slot spazio-tempo che intende utilizzare un veicolo per attraversare un segmento stradale, in cui ogni veicolo riserva la sua coppia OD e l'intervallo di tempo che utilizzerà per intraprendere il viaggio dalla sua origine. Se sono disponibili le

informazioni sul traffico in tempo reale, diventa possibile fornire un percorso ai veicoli considerando un’ottimizzazione del traffico globale. Per monitorare l’andamento del

29

veicolo si possono utilizzare telecamere appositamente installate per verificare l’accettazione del percorso proposto.

Sia G = (N, A) un grafo connesso che rappresenta la rete stradale, dove N è l’insieme dei nodi che rappresentano gli incroci stradali e A l’insieme degli archi che

congiungono due nodi differenti e quindi due intersezioni diverse. Assumiamo che ci sia un solo arco per ogni coppia di nodi.

3.6.2 Modello di ottimizzazione

Nella pubblicazione [11] è stato formulato un modello di ottimizzazione per

l’assegnazione del traffico, in cui si è individuata una soluzione ottimale del sistema. Il modello è il seguente:

30

dove l’equazione (5) rappresenta la funzione obiettivo del problema e le altre i vincoli che si devono rispettare.

Spiegazione: per sviluppare il problema di ottimizzazione si devono considerare diverse metriche.

Bisogna tenere conto dei fattori che soddisfano un principio “egualitario” e

“utilitaristico” secondo cui si assegnano i veicoli ai percorsi disponibili sia per la stessa coppia OD, sia per coppie OD differenti. Sia w una generica coppia OD e W l’insieme di tutte le coppie OD, tali che w ϵ W. Inoltre, con i termini ψwk e R si indicano

rispettivamente, una matrice che descrive i flussi dei veicoli sull’intera rete stradale e le richieste OD (Rw è la domanda dei veicoli che richiedono un nodo origine no per andare ad un nodo destinazione nd).

L’equazione (6) rappresenta il vincolo di capacità della rete e limita il flusso totale attraverso tutte le coppie OD su ciascun arco a ϵ A. Nel calcolo vengono considerati i valori della matrice φak (matrice di incidenza percorso- arco), x^k indica il flusso di traffico lungo k e Pw è l’insieme dei percorsi disponibili e accettabili.

Si parla di criteri di equità e di “no-envy”, letteralmente “senza invidia”: ovvero, non deve esserci nessuna coppia OD che “invidia” un’altra coppia OD in termini di costo della durata del percorso (poiché ci saranno percorsi di costo inferiore). E’ per questo motivo che è stato introdotto il vincolo (7), in cui con α si indica un fattore massimo di tolleranza con valore compreso nell’intervallo (0,1]. Per il calcolo di questo parametro si rimanda alla pubblicazione [11].

Ovviamente si deve cercare di minimizzare i costi totali, infatti nella funzione obiettivo è stata espressa questa condizione. Viene introdotto anche il concetto di latenza: il problema di latenza massima consiste nel minimizzare il costo dell’espressione associato al prodotto di costo massimo in termini di durata del percorso, cioè il flusso che minimizza il costo di durata del percorso medio, massimo tra tutte le coppie OD, e quindi ottimizza il benessere utilitaristico.

Minimizzando il valore di latenza media di un flusso Xw ci si avvicina al problema di ottimizzazione del benessere egualitario.

L’equazione (8) rappresenta il vincolo sul soddisfacimento della domanda OD tra i flussi di percorso, che impone che la somma dei flussi di percorso di ciascuna coppia w sia uguale alla richiesta OD. L'obiettivo di (5) è, quindi, ottenere un flusso di percorso normalizzato del veicolo richiesto sugli archi a ∈ A di costo minimo tale che ogni veicolo percorra un percorso dalla sua origine e termini nella posizione di destinazione con i vincoli precedentemente descritti, e percorsi ammissibili in PW soddisfatti.

31

3.6.3 Prodotto di Nash

La soluzione precedentemente proposta è di tipo utilitaristico.

L'equilibrio tra benessere sociale egualitario e utilitaristico è dato dalla

massimizzazione del prodotto di Nash che è il prodotto delle utilità individuali degli agenti: cioè le soluzioni di allocazione con un alto valore di Nash sono buone soluzioni sia a livello locale che globale. Tuttavia, l'ottimizzazione del prodotto di Nash non funziona quando definita attraverso la minimizzazione del costo complessivo poiché è sufficiente che solo uno degli agenti realizzi il costo vicino allo zero per avere il valore complessivo vicino allo zero: questo è il motivo per cui si massimizzano i costi e quindi, moltiplicati insieme, porteranno a valori elevati del prodotto di Nash.

La funzione Nash Social Welfare (Benessere sociale di Nash) è espressa come:

𝑚𝑎𝑥 𝑁(𝑋𝑤) = ∏ 1

𝛾_𝑤 = − ∑ 𝑙𝑜𝑔 𝛾_𝑤

𝑤∈𝑊 𝑤∈𝑊

Basterà sostituire il valore della funzione obiettivo con la nuova soluzione proposta per un modello di programmazione matematica con i nuovi parametri di correttezza.

Si sfrutta anche l’efficienza di Pareto, secondo cui un’allocazione di percorsi θ è

“Pareto superiore” ad un’altra allocazione θ’ se, e solo se, per ogni coppia OD (w) i cui costi dei percorsi utilizzati sono 𝑓_𝑤^𝜃(𝑥_𝑤) = ∑ _𝑘 𝑓^𝑘(𝑥^𝑘), è soddisfatto il seguente criterio: 𝑓_𝑤^𝜃(𝑥_𝑤) ≤ 𝑓_𝑤^𝜃′(𝑥_𝑤), dove 𝑥_𝑤 > 0. In altre parole, possiamo migliorare un’allocazione di percorsi se ne esiste un’altra tale che in essa almeno un agente “sia migliore e nessuno è peggio”. Un’allocazione si dice “Pareto efficiente” se non è possibile alcun miglioramento, ovvero non esiste un’allocazione che è “Pareto

superiore” rispetto ad un’altra. Nello stesso modo, un'allocazione è Pareto- inefficiente se è possibile rendere migliore un agente senza peggiorare altri agenti.

3.7 Utilizzo della struttura MAS

L’architettura multi- agente utilizzata consiste principalmente di tre agenti: veicoli, origini del percorso di viaggio e agenti di intersezione. Questi agenti comunicano tra loro scambiandosi informazioni tra componenti adiacenti. I veicoli comunicano con l’agente di intersezione a loro più vicino. In questo modo è possibile visualizzare e ricalcolare i percorsi dei veicoli in base alle condizioni di traffico e alla loro posizione.

Nella pubblicazione [11] è stato sviluppato il modello decisionale, in termini matematici, per l’assegnazione dinamica dei veicoli ai percorsi della rete stradale.

32

I veicoli negoziano aste con agenti OD per l’assegnazione del percorso, mentre questi cercano il percorso più breve con agenti di intersezione. Questi ultimi assegnano i percorsi in base alla massimizzazione del flusso di traffico di rete tenendo conto dei vincoli della capacità stradale. Per un numero minimo di origini e per queste coppie O-D, sono necessari incentivi monetari affinché i veicoli si comportino in linea con le prestazioni di sistema desiderate. Le metodologie di pedaggio all'avanguardia possono essere applicate anche nella soluzione proposta per incentivare l'accettazione da parte degli utenti dei percorsi assegnati.

33

CAPITOLO 4- GESTIONE DEL TRAFFICO E IA 4.1 Introduzione

I sistemi di gestione del traffico possono trarre grandi vantaggi dall'intelligenza artificiale (IA) e da molti altri sottocampi dell'informatica. Le modifiche strutturali alle reti stradali sono molto più problematiche del potenziamento dei sistemi che

gestiscono il flusso del traffico e, a volte, potrebbero risultare troppo costose o poco pratiche nelle aree urbane. Questi eventuali interventi, come ad esempio la

costruzione di nuove strade, possono, inoltre, compromettere le prestazioni del traffico.

Sono state impiegate molte tecniche per il controllo del traffico, come le reti neurali e gli algoritmi genetici. Ogni tecnica ha i suoi vantaggi e svantaggi.

4.2 Effetto sulle congestioni

La congestione del traffico è uno dei problemi più importanti del sistema del trasporto stradale. L’applicazione di tecniche di intelligenza artificiale si sono dimostrate efficaci per la gestione di tale problema. Alcune di queste tecniche riguardano le reti neurali artificiali, algoritmi genetici e modelli di logica fuzzy. Questi meccanismi sono stati sfruttati al fine di gestire i vari flussi di traffico e si è arrivati persino al punto di

prevedere i vari tempi di flussi di traffico e quando i vari veicoli si approssimano ad un incrocio stradale, poiché ritenuti parametri rilevanti per una gestione ottimale. Ci sono molti problemi che il settore dei trasporti deve affrontare e che l’intelligenza artificiale contribuisce a migliorare, tra cui l’aumento della domanda di viaggio, le emissioni ci CO2 e la sicurezza stradale.

4.3 Reti neurali artificiali

Le reti neurali artificiali sono una classe di tecniche di apprendimento automatico ispirate ai cervelli biologici: l’idea è quella di simulare il funzionamento del cervello umano e animale per ottenere comportamenti intelligenti. Il modello di neurone più diffuso è chiamato neurone sigmoidale ed è costituito da un’unità con n ingressi numerici e un’uscita numerica.

34

4.3.1 Cenni sulle reti neurali artificiali

Una rete neurale artificiale (ANN, Artificial Neural Network) è un modello di

computazione composto da “neuroni” artificiali, che hanno il compito di riprodurre un comportamento intelligente nei sistemi su cui sono state impiegate: l’idea è quella di simulare un cervello umano, cioè capace di prendere decisioni autonome attraverso un processo di apprendimento che aiuta a rispondere a determinati input (che essa

riceve) con determinati output. La capacità che ha la rete di rispondere a questi input è data dal numero dei neuroni di cui è composta e dalle connessioni che li collegano e che definiscono, quindi, la modalità di avviamento del loro funzionamento. Le principali caratteristiche che le contraddistinguono sono:

• Resistenza al rumore: la rete è in grado di produrre una risposta corretta anche se gli vengono forniti dei segnali di ingresso (input) “disturbati”, quindi la capacità del sistema rimane intatta (o quasi completamente).

• Flessibilità d’uso: le ANN possono essere impiegate in molti sistemi, anche se non conoscono i relativi domini su cui sono applicate, poiché il loro processo automatico di apprendimento le rende capaci di adattarsi facilmente a qualsiasi contesto;

• Generalizzazione: anche se la rete riceve una quantità limitata di input o di informazioni a lei sconosciute, è in grado di produrre lo stesso un output attraverso un processo di “somiglianza” che associa gli input ricevuti a risultati già elaborati precedentemente;

• Recupero di memoria: partendo da dati di input incompleti, è possibile fornire comunque una risposta poiché basta un suggerimento per dirigere il processo di elaborazione dell’output e l’intera attivazione del sistema nella direzione giusta.

4.3.2 Struttura di una rete neurale artificiale

Le reti neurali sono strutture semplici costituite da elementi connessi tra loro. Può essere vista come un grafo G = (V, A), i cui nodi V rappresentano gli elementi di processo e gli archi A rappresentano le connessioni tra i vari elementi.

I nodi sono collegati tra loro tramite gli archi, possono ricevere più connessioni e inviare tramite essi dei segnali identici per tutte le connessioni che si intendono utilizzare. Ogni elemento è costituito da una memoria locale, che viene usata da una specifica funzione dell’elemento stesso, in grado di produrre un segnale di output.

Alcuni nodi che hanno le stesse caratteristiche possono essere raggruppati tra loro,

35

andando così a formare lo strato della rete: ad esempio, solitamente, si ha uno strato di ingresso, i cui nodi hanno lo scopo di passare i segnali agli altri elementi del grafo.

Una rete neurale artificiale viene anche chiamata solo “rete neurale”, è un modello matematico e/o informatico di calcolo basato su reti neurali biologiche.

Si tratta di un sistema adattivo, ovvero che cambia la propria struttura in base a informazioni interne o esterne che attraversano la rete stessa e che tramite algoritmi di apprendimento riesce a comprendere.

Ci sono tre principali metodi di apprendimento:

• Apprendimento supervisionato: dispone di un insieme di dati (training set) in cui si comprendono degli esempi riguardo specifici ingressi e relative uscite in modo che la rete possa imparare la relazione e il procedimento che portano ad avere un determinato output, dato il corrispondente input. La rete viene

“addestrata” tramite un opportuno algoritmo, di solito l’algoritmo di “back-propagation”: si tratta di un algoritmo di apprendimento usato nelle reti neurali, confronta il valore di uscita del sistema con il valore da raggiungere (obiettivo) calcolando, tramite una differenza tra i due valori, l’errore rilevato e, basandosi su esso, modifica i parametri della rete facendo convergere i risultati ottenuti verso l’obiettivo desiderato. Se l’apprendimento ha successo, la rete riesce ad individuare la corretta relazione tra gli input e output, ed è anche capace di fare previsioni sul risultato finale. Questo rappresenta l’obiettivo che si pone questa tecnica, cioè calcolare il valore di uscita partendo da determinati valori di ingresso e coppie di valori input- output da cui prendere esempio.

• Apprendimento non supervisionato: si basa su algoritmi che forniscono al sistema una serie di input che esso riorganizzerà sulla base delle caratteristiche in comune che si evidenziano tra loro, per cercare di effettuare ragionamenti e fare previsioni sugli input successivi utilizzando anche metodi probabilistici.

• Apprendimento per rinforzo: l’algoritmo utilizzato prende in considerazione l’ambiente esterno, poiché ogni azione ha un impatto sull’ambiente, il quale risponde in una certa maniera, indirizzando l’algoritmo verso il processo di apprendimento. Questa tecnica differisce dall’apprendimento supervisionato in quanto non vengono considerati degli esempi iniziali, ma si sfrutta una

conoscenza attuale per affrontare situazioni ancora sconosciute.

36

4.3.3 La rete neurale Feedforward

Le reti neurali si basano sulla simulazione di neuroni artificiali opportunamente collegati.

Ci sono molti tipi di reti neurali che si differenziano per la loro tipologia, ovvero il particolare modo di come le sue parti vengono organizzate e interconnesse. Quella più semplice ed utilizzata è la rete neurale Feedforward (Figura 3), costituita da più di due strati di neuroni: oltre lo strato di input e di output se ne aggiungono altri nascosti.

I neuroni ricevono degli stimoli e li elaborano: i valori di ingresso vengono moltiplicati per un certo parametro detto “peso” ed il risultato delle varie moltiplicazioni viene sommato. Se la somma supera un certo valore il neurone si attiva producendo un certo output. Il peso serve a quantificare l’importanza del corrispondente valore di ingresso, cioè un ingresso importante avrà un peso elevato e viceversa. Più neuroni possono connettersi tra loro tramite determinati percorsi che acquisteranno una maggiore importanza se maggiormente utilizzati, tuttavia anche altre combinazioni possono essere considerate con il relativo peso.

Figura 3: Illustrazione di una rete neurale artificiale Feedforward.

In questo tipo di rete ogni neurone è connesso con tutti i neuroni dello strato successivo ma non ha connessioni con i neuroni del suo stesso strato e il segnale si propaga dall’input all’output attraverso queste connessioni, sfruttando anche gli strati nascosti. In particolare, una rete è formata da tre strati principali: lo strato d’ingresso (I), lo strato nascosto (H) e lo strato d’uscita (O). Lo strato d’ingresso si occuperà di trattare gli ingressi calcolando le eventuali operazioni, lo strato nascosto si occupa

37

dell’elaborazione delle informazioni e lo strato di uscita si preoccupa di raccogliere i

dell’elaborazione delle informazioni e lo strato di uscita si preoccupa di raccogliere i