Agenti di intersezione e agenti dei semafori

1. Stato del problema

1.3 MAS e Traffico

1.3.1 Agenti di intersezione e agenti dei semafori

L’obiettivo che si pongono le tecniche e i modelli basati sull’intelligenza artificiale sul controllo del traffico è sempre quello di ridurre al minimo le congestioni, proponendo richieste che si concentrano sull’approvvigionamento di dati reali. Si utilizza un sistema MAS per la gestione del controllo del traffico.

Se si prende in considerazione un incrocio stradale, ogni semaforo sarà gestito dal suo agente (agente del semaforo) che si occuperà della regolazione dei tempi da assegnare ad esso, quindi ci sarà una regolazione del tempo rosso e verde. Ci sarà, inoltre, un ulteriore agente, cioè un agente di intersezione costituito da uno specifico software, il quale si occuperà di gestire gli agenti dei semafori che fanno parte dell’intersezione presa in considerazione in modo intelligente: esso riceverà una distribuzione ottimale dei tempi da assegnare ai suoi agenti, calcolati da un ulteriore componente (un server), ogni volta che si verifica un cambiamento significativo nel flusso del traffico. Sono questi i dati reali su cui bisogna basarsi: fonti che rilevano la situazione di traffico interessata nell’area attraverso strumenti specifici che vanno dai sensori a telecamere installate nell’incrocio. Il server è la componente principale utilizzata in questa

struttura che elaborerà le informazioni principali, in seguito comunicate agli agenti di intersezione. I principali parametri che si occuperà di gestire sono illustrati nella sezione 2.3.5 di questa tesi.

Figura 1: riassume la struttura del coordinamento tra agenti del semaforo, agente di intersezione e server.

Questo sistema prevederà anche un’assistenza umana con l’installazione di appositi centri di controllo, in cui si monitorerà la situazione generale e si interverrà in casi di emergenza, inviando appositi segnali al server che calcolerà la giusta soluzione in base a ciò che è stato ricevuto.

CAPITOLO 2- CONTROLLO DEL TRAFFICO TECNICHE MARKET-BASED E MECCANISMI INTELLIGENTI

2.1 Introduzione

Questo capitolo spiegherà i vari approcci che possono essere utilizzati per il controllo del traffico, utilizzando sistemi multi- agente. In particolare, vengono descritti i metodi utilizzati per la gestione del traffico a livello di intersezione: tecniche “market-based”, in cui si parlerà anche di un eventuale approccio pratico al problema e tecniche basate su meccanismi intelligenti, in cui si terrà conto anche delle esigenze dei conducenti.

Alla fine del capitolo, vengono brevemente discussi i problemi esistenti per la realizzazione di questi sistemi, legati a normative etiche e legali.

2.2 Parametri di controllo del traffico

Le tecniche che si utilizzano per rendere il flusso di traffico, più fluido, tengono conto di diversi parametri ritenuti molto importanti per il controllo del traffico. Un’adeguata regolazione di questi parametri permetterà una migliore gestione del funzionamento degli incroci ed un eventuale coordinamento tra più incroci. I metodi illustrati in questo capitolo regoleranno i seguenti parametri:

• Offset: questo parametro è la componente fondamentale nella formazione del fenomeno delle onde verdi, il quale si verifica quando un gruppo di veicoli attraversa una serie di incroci effettuando pochissime fermate. L’offset consiste nella differenza tra il tempo di inizio dell’intervallo verde tra due incroci

adiacenti. Più precisamente se la luce verde di un’intersezione si verifica all’istante t, la luce verde dell’intersezione successiva inizierà all’istante t+z, dove z è l’offset;

• Ciclo: il ciclo semaforico è un insieme di fasi e quindi una sequenza completa di segnali che regola i movimenti dei veicoli in un determinato incrocio. La durata del ciclo rappresenta il tempo necessario al completamento delle fasi che lo compongono;

• Split: lo split rappresenta la divisione del tempo verde tra le fasi che compongono un ciclo. Infatti, l’intervallo verde di una fase è indicato come split.

2.3 Metodi market-based

La gestione del traffico è stata affrontata utilizzando diversi metodi. Alcuni di questi metodi usano tecniche “market-based”, ovvero basate sul “Market mechanisms”.

2.3.1 Market mechanism

Letteralmente questo termine viene tradotto come “meccanismo di mercato”, viene impiegato come struttura sia per l’allocazione delle risorse (tempo, spazio, mezzi di comunicazione), sia come modello per un’interazione tra agenti in un MAS.

L’obiettivo è quello di coordinare gli agenti per consentire loro di funzionare nel modo più efficiente possibile in ambienti con risorse limitate realizzando, in questo modo, una sorta di collaborazione e comportamenti cooperativi in sistemi distribuiti.

Il “meccanismo di mercato” più diffuso è quello basato su aste. Un’asta è un protocollo che determina l’assegnazione delle risorse in sistema costituito da diverse entità. In molti sistemi multi- agente è comunemente usato nel modo seguente:

1. Annunciazione di una risorsa disponibile: nel sistema è presente un

“banditore” che dà inizio all’asta e annuncia una possibile assegnazione di una risorsa;

2. Raccolta delle offerte: il banditore raccoglie tutte le offerte proposte dagli agenti che hanno risposto al suo annuncio;

3. Determinazione del vincitore: il banditore seleziona l’agente al quale assegnare la risorsa.

2.3.1.1 Similitudine con il funzionamento del Contract Net Protcol Un funzionamento analogo si può trovare nel Contract Net Protocol (CNP), un

protocollo di negoziazione e condivisione di task introdotto nel 1980 da Reid G.Smith.

È stato progettato per allocare diverse attività tra agenti autonomi. Anche qui è presente un agente manager che, nel nostro caso, funge da “banditore” e agenti secondari che saranno coloro che si proporranno per accettare la risorsa proposta dal banditore. La comunicazione avviene in diversi modi:

• Peer-to-peer: l’agente manager si mette in contatto con un solo agente;

• Multicast: l’agente manager comunica con più agenti;

• Broadcast: l’agente manager comunica con tutti gli agenti.

L’agente manager dichiara la disponibilità di un’attività tramite multicast, esattamente proprio come nell’asta in cui il banditore dichiara la disponibilità di una risorsa ai vari offerenti. Successivamente, si procederà in questo modo:

1. Gli agenti valutano ciò che propone il banditore e quelli interessati faranno le loro offerte;

2. L’agente manager raccoglierà le varie offerte e selezionerà l’agente vincitore;

3. L’agente manager e l’agente vincitore comunicheranno privatamente.

È evidente come questo meccanismo di negoziazione è molto simile al “market mechanism” basato su aste.

2.3.2 Problematiche generali

Le tecniche “market-based” sono state impiegate anche in molti sistemi di controllo e gestione del traffico [4], tuttavia la maggior parte di esse presenta un approccio poco pratico senza un’effettiva implementazione. Il motivo di questa problematica potrebbe essere relativo al fatto che per elaborare una certa soluzione c’è bisogno di molti parametri su cui basarsi, tra cui la disponibilità di dati affidabili in tempo reale che forniscano una rappresentazione accurata delle condizioni del traffico, come la lunghezza delle code dei veicoli, i tempi di percorrenza medi o altri tipi di misurazione che verranno passati ai vari processi decisionali dei sistemi di controllo adottati. La realtà è che esistono molte limitazioni nel modo in cui vengono prodotti questi dati sul traffico nonostante i progressi nei software, nei dispositivi di comunicazione e

geolocalizzazione. Al momento, la tecnologia aiuta a fornire dati precisi sul flusso di traffico, ad esempio i tempi di viaggio, come nel caso dei dati GPS dei telefoni cellulari che possono fornire informazioni più accurate sul flusso del traffico.

Si è provato a sviluppare un approccio ai sistemi di controllo del traffico più pratico, per tentare di iniziare a sviluppare nuovi metodi “market based” nel controllo del traffico [5]. In questo tipo di approccio si fa riferimento all'uso delle aste per consentire il coordinamento e l’allocazione delle risorse o l'assegnazione dei compiti/obiettivi.

2.3.3 Struttura basata su asta

Per l’elaborazione di queste teorie è stata presa in considerazione una generica intersezione che simula un incrocio stradale in cui sono previsti due tipi di agenti:

agenti di intersezione e agenti dei semafori. C’è un singolo agente di intersezione e più

agenti di semafori, interpretati rispettivamente come banditore e agenti secondari sul modello basato su aste, precedentemente descritto. Quindi, l’agente di intersezione si occupa della regolazione degli orari dei semafori (di conseguenza, la gestione delle relative fasi), ed è visto come banditore che dà inizio alle varie aste in cui sceglierà un opportuno agente del semaforo al quale assegnerà un numero di movimenti da gestire, ovvero si stabilirà il movimento dei veicoli per il tratto di strada segnalato dal semaforo corrente (si suppone che i veicoli dovranno rispettare la condizione imposta dal semaforo per quel tratto di strada). Si può notare che questi agenti lavoreranno in maniera del tutto indipendente, ma interagiranno gli uni con gli altri per gestire e migliorare l’efficienza dell’incrocio per cui operano, e di mantenerne la sicurezza.

2.3.4 Alcune tecniche per il controllo del traffico

Di seguito vengono illustrate alcune tecniche di controllo del traffico “market-based”.

SAT e SATQ

SAT e SATQ sono due sistemi di controllo del traffico “market-based”, e rappresentano due approcci pratici elaborati con l’obiettivo di evitare congestioni fornendo un

accesso equilibrato agli incroci stradali.

La loro implementazione è disponibile nella pubblicazione [5].

Descrizione e funzionamento

Entrambi questi metodi utilizzano la “Saturazione” per gestire la congestione, poiché quest’ultima è vista come una saturazione eccessiva; quindi il modo migliore per evitarla è assegnare più tempo verde ai semafori che individuano i collegamenti stradali in cui c’è maggiore flusso di traffico. Per saturazione, infatti, si intende la misura del flusso di traffico su un determinato tratto stradale.

Nel dettaglio, si parte da una condizione iniziale in cui gli agenti dei semafori lavorano in un certo modo. Le aste vengono eseguite dagli agenti di intersezione ogni 5 minuti aggiornando, quindi, i tempi dei semafori. Il meccanismo dell’asta prevede due parti.

Per prima cosa, gli agenti dei semafori presentano le loro offerte e, in seguito, l’agente di intersezione selezionerà l’agente con l’offerta più alta come il vincitore (in caso di pareggio, il vincitore viene scelto a caso). Il vincitore dell’asta guadagna 5 secondi aggiuntivi di tempo verde, mentre il tempo verde del perdente diminuisce della stessa quantità.

Ma in cosa consistono queste offerte? Semplice, con “offerta” si intende il livello di saturazione rilevata dagli agenti dei semafori su quel segmento stradale che servono. È per questo motivo che, assegnando più tempo verde nelle parti in cui è presente maggiore saturazione, si potrà liberare il tratto di strada interessato, evitando la congestione. Per trarre informazioni sul volume del traffico, vengono usati dei

rilevatori dei veicoli che forniscono dati utili agli agenti dei semafori per generare, sulla base di ciò, le proprie offerte.

In termini matematici, la saturazione è definita come il rapporto tra il volume del traffico su un tratto di strada e la sua capacità. Si deduce, quindi, che un flusso di traffico “vicino” alla capacità della strada è più suscettibile a inceppamenti. Data una fase p (si ricorda che per fase si intende l’insieme degli intervalli di tempo delle singole sequenze di luci di un semaforo), che serve k collegamenti (si fa riferimento ai quindi vari tratti di strada interessati da un determinato semaforo), sia dp la misura della sua saturazione:

𝑑𝑝 = ∑𝑣𝑘 𝑐𝑘

𝐾

𝑘=1

dove per vk e ck, si intendono rispettivamente il volume del traffico e la capacità sul collegamento.

Differenza tra SAT e SATQ

La differenza sostanziale di questi due approcci consiste in una diversa regolazione dell’offerta. In SAT, gli agenti dei semafori calcolano la loro saturazione (dp, nella formula) del loro segmento stradale da utilizzare come offerta.

Il metodo SATQ, invece, estende il metodo SAT. Ogni volta che si genere un’offerta viene considerata anche un‘altra misurazione che si aggiunge a quella della

saturazione: la “pienezza” dei collegamenti in entrata per quel tratto di strada servito, ovvero la percentuale della carreggiata occupata dai veicoli. Sarà sommata alla misura della saturazione e avrà valore compreso nell’intervallo [0,1], dove 0 significa che i collegamenti stradali sono vuoti e 1 significa che i collegamenti sono completamente pieni di veicoli. Ciò fornisce un quadro migliore delle condizioni stradali, rispetto al solo valore di saturazione. Si potrebbe utilizzare una telecamera per ottenere questi dati.

GRACE (GeneRal- purpose Auction- based Traffic ControllEr)

È stato sviluppato un altro sistema di controllo “market-based” che lavora in maniera diversa dagli altri: permette agli agenti di semafori di gestire i principali parametri di controllo del traffico.

11 Perché un sistema di controllo diverso?

Nella sezione 2.2 sono stati illustrati i diversi parametri di controllo del traffico, ed è stato dimostrato che questi rappresentano le componenti più importanti che influiscono sui tempi dei semafori come nei sistemi di controllo di traffico commerciale.

Con le tecniche descritte in precedenza, SAT e SATQ, viene gestito solo lo split: quando si dà inizio ad un’asta, l’agente dell’incrocio propone come risorsa una quantità di tempo verde da assegnare al vincitore. Gli altri parametri non vengono considerati.

L’obiettivo è, quindi, quello di cercare di gestire tutti questi parametri che influenzano le prestazioni del traffico: ad esempio l’offset, per avere un migliore coordinamento tra incroci stradali.

Descrizione e funzionamento

In GRACE, non si mettono più all’asta solo 5 secondi di tempo verde: il vincitore potrà decidere autonomamente i tempi del semaforo dell’incrocio interessato. Questo meccanismo permette agli agenti dei semafori di modificare tutti i parametri del controllo del traffico.

È possibile consultare l’implementazione dell’algoritmo in [5].

Anche qui, gli agenti dei semafori iniziano a lavorare con un tempo iniziale predefinito.

Successivamente, questi interagiscono per generare un nuovo insieme S, che racchiude tutte le possibili tempistiche da assegnare al semaforo che si vuole gestire. Nello specifico, questo insieme consiste in una raccolta di vettori in cui un vettore s è definito come una tripla:

𝑠 =< 𝛿𝑔, 𝛿𝑐, 𝛿𝑡 >

dove δg, δc, δt sono le variazioni delle componenti del controllo del traffico,

rispettivamente del tempo verde, della durata del ciclo e dell’offset. Considerare una tripla del tipo <5, -4, 2>, significa dire che il tempo verde è aumentato di 5 secondi, la durata del ciclo è stata ridotta di 4 secondi e l’offset aumentato di 2 secondi. Come in SAT/Q, le aste vengono eseguite periodicamente e gli agenti dei semafori faranno offerte per potersi guadagnare l’autorità di regolare i tempi del semaforo all’incrocio che servono. Il vincitore dell’asta sceglierà le modifiche da apportare all’orario del semaforo. Tuttavia, durante l’esecuzione dell’asta, in questo approccio, viene eseguita una serie aggiuntiva di passaggi per regolare le nuove misure di split, durata del ciclo e offset che ogni agente del semaforo vuole apportare. È in questo modo che si

costruiscono tutti i vettori s ∈ S, per questo anche denominati “adjustment vectors”,

ovvero “vettori di regolazione” o “vettori regolatori”. Gli agenti dei semafori valutano

“l’utilità” di ogni vettore, determinata da una funzione di utilità:

𝑈(𝑠) = 𝑆 → 𝑅

Ogni agente dei semafori presenta il proprio vettore e fa un’offerta al banditore. Il banditore selezionerà sempre l’offerta più alta.

Di seguito verranno presentate due varianti di GRACE con le loro funzioni di utilità e strategie di offerta.

MMDOS (Minimise Maximum Degree Of Saturation)

Questa variante prende il nome dalla sua funzione di utilità, utilizzata dagli agenti dei semafori. MMDOS regola tutti e tre i parametri del controllo del traffico: split, ciclo e offset. L’obiettivo che si pone questa strategia è di ridurre il grado di saturazione di un collegamento stradale all’incrocio preso in considerazione in cui è concentrato un maggiore flusso di traffico. Quindi, MMDOS si basa su un generico grado di saturazione Xi, calcolato nel modo seguente:

𝑋𝑖 = 𝑣𝑖 𝐿 𝑐𝑖 𝑔𝑖

(1) Questa equazione permette di quantificare il grado di saturazione verificato nell’i-esimo gruppo di collegamenti stradali in entrata ad un incrocio, dove: “vi” rappresenta il volume di traffico sul collegamento “critico” (che ha quindi una priorità maggiore rispetto agli altri del suo gruppo), “ci” indica la capacità massima di questo

collegamento, e “gi” e “L” sono, rispettivamente, la quantità di tempo verde assegnato alla fase e alla durata del ciclo. Xi sarà un valore compreso nell’intervallo [0,1].

L’utilità di una regolazione “s” è espressa come:

𝑈(𝑠) = −[𝑋(𝑠) + 𝐷(𝑠)]

(2) in cui,

𝑋(𝑠) = 𝑣𝑚𝑎𝑥 (𝐿 + δc) 𝑐𝑚𝑎𝑥 (𝑔 + δg)

(3)

Spiegazione: Xs rappresenta il grado di saturazione stimato in cui viene gestito il collegamento in entrata con volume di traffico più elevato (collegamento critico).

Questo parametro è indicato dal termine vmax ed è stato considerato tale durante il processo dell’asta; la sua capacità è espressa dal termine cmax. Come detto prima, g è la quantità di tempo verde assegnata all’agente del semaforo e L è la durata del ciclo all’incrocio. Il risultato avrà valore compreso nell’intervallo [0,1], proprio come

l’equazione (1). Nell’equazione (2), D(s) indica il numero dei veicoli fermi calcolato dai rilevatori dei veicoli.

Le offerte che verranno proposte durante il processo dell’asta sono rappresentate dal valore Xi, quindi viene comunicato il grado di saturazione dei collegamenti in entrata gestiti dall’agente interessato con il relativo collegamento critico. Alle componenti che rappresentano un generale vettore di regolazione, possono essere assegnati

determinati valori; nel dettaglio:

𝛿𝑔 ∈ {0, 1, 2, 3, 4, 5};

𝛿𝑐 ∈ {−32, −16, −8, −4, 0, 4, 8, 16, 32};

𝛿𝑡 ∈ {−4, −3, −2, −1, 0, 1, 2, 3,4}.

Varianti di MMDOS

Sono state sviluppate sei tipi di varianti diverse di MMDOS, ognuna delle quali rappresenta le diverse combinazioni tra i parametri di traffico, al fine di esaminare in che modo i singoli parametri del controllo del traffico (o coppie di questi, a seconda della combinazione desiderata) influiscono sul flusso di traffico in corrispondenza di un’intersezione. La funzione di offerta rimane la stessa di MMDOS, così come anche i possibili valori delle componenti dei vettori regolatori. La funzione di utilità è, invece, leggermente diversa e varia a seconda dell’offset.

In particolare, per l’implementazione e il funzionamento si rimanda alla pubblicazione [5].

DC2 (Dynamic Coalition Formation)

In SAT / Q e in GRACE, gli agenti dei semafori sono interessati solo ai rispettivi flussi di traffico. Cioè, vincere l'asta ha lo scopo di migliorare il flusso di traffico associato all'agente del semaforo vincente. DC2 è una variante di GRACE, il cui obiettivo è quello di costruire delle coalizioni dinamiche tra intersezioni, per poter permettere loro di regolare i tempi da assegnare ai loro segnali.

Ma in che modo? Si sfrutta il parametro dell’offset: le intersezioni collaboreranno tra loro e provvederanno ad un continuo aggiornamento sulla sua regolazione, in modo da garantire un migliore coordinamento tra incroci e quindi, un eventuale aggiornamento di offset da parte di un agente del semaforo di un’intersezione dipende dalle

condizioni di traffico che si verificano in un’altra intersezione della coalizione, la quale provvederà a comunicare tali dati.

Nella pubblicazione [6] è stato dimostrato come trovare una coalizione ottimale.

In DC2 le coalizioni si formano e si distruggono in maniera dinamica. Si differenzia, inoltre, da MMDOS, poiché l’offset adottato potrebbe non essere “ideale” per l’agente del semaforo che ha vinto l’asta.

L’utilità di una regolazione “s” è espressa come:

𝑈(𝑠) = −[𝑋(𝑠) + 𝐷^𝐼(𝑠)]

in cui, il termine D^I (s) indica il numero di veicoli fermi in relazione all’incrocio considerato e, se a quest’ultimo, è stato consentito di applicare l’offset scelto.

Le offerte proposte dai vari agenti saranno costituite dal valore Xi (grado di saturazione dei collegamenti sotto il controllo dell’agente). I termini Xs e Xi sono stati descritti precedentemente. Si può notare che la funzione di utilità e l’offerta sono simili a quelle di MMDOS.

Valori delle possibili componenti dei vettori in DC2:

𝛿𝑔 ∈ {0, 1, 2, 3, 4, 5};

𝛿𝑐 = 0;

𝛿𝑡 ∈ {−4, −3, −2, −1, 0, 1, 2, 3,4}.

Questo meccanismo permette, quindi, di formare onde verdi tra incroci adiacenti: è per questo motivo che δc = 0, in quanto non modificare la durata del ciclo è un requisito necessario al fine della formazione di questo fenomeno.

2.3.5 Distribuzione ottima e discussione dei risultati

SAT e SATQ assegnano una quantità di tempo verde ben definita ed equivalente ad un tempo di 5 secondi, con un aumento di questo tempistica all’agente del semaforo che ha vinto l’asta e una diminuzione di questa tempistica all’agente del semaforo che ha perso l’asta. Anche se queste tecniche sono molto simili, presentano risultati

abbastanza differenti. Nella pubblicazione [5] sono stati condotti degli esperimenti orientati alla simulazione del traffico su due mappe prestabilite, in cui vengono valutate le prestazioni del traffico utilizzando tre metriche principali: tempo di

Nel documento VERSO UN INFRASTRUTTURA INTELLIGENTE PER IL TRAFFICO VEICOLARE: RASSEGNA DELLA LETTERATURA E PROSPETTIVE DI SVILUPPO (pagine 8-0)