Hoe vaak gebeurt het niet dat je bij een kruispunt staat en het stoplicht op rood? En hoe vaak gebeurt het niet dat je staat te wachten terwijl er helemaal geen verkeer aankomt? Hoewel verkeerslichten over het algemeen het verkeer veilig regelen, zijn de gebruikte methoden zeker niet optimaal. Resultaten van onderzoek naar machinaal leren, een vakgebied binnen de kunstmatige intelligentie (ki), tonen aan dat het gebruik van zelflerende verkeerslichten grote voordelen kan bieden boven de huidige statische methoden. Hiervoor is het nodig eerst iets dieper in te gaan op het gebruik van netwerken binnen de kunstmatige intelligentie.

Netwerken in kunstmatige intelligentie

Kunstmatige intelligentie houdt zich bezig met het maken van programma’s die zelf handelingen uitvoeren op een zo optimaal mogelijke manier. Een voorbeeld daarvan is een medisch diagnosesysteem, dat na het verkrijgen van gegevens over een patiënt een goede diagnose van het ziektebeeld kan geven. Veel kunstmatig intelligente systemen maken gebruik van wiskundige functies om een bepaalde invoer om te zetten naar een gewenste uitkomst. Het kunstmatige neurale netwerk bijvoorbeeld, simuleert een abstract model van het brein, waarin het vooral gaat om het leren van verbindingssterktes (synapsen) tussen neuronen. Elke synaps krijgt een bepaalde waarde, die toeneemt naarmate de neuronen sterker met elkaar in verbinding staan. In plaats van informatie op een voorgeprogrammeerde manier te verwerken kan een neuraal netwerk dus leren, omdat de structuur van het netwerk (de verbindingen tussen de neuronen) verandert op basis van de informatie die het verwerkt.

Voor een geslaagd leerproces moet het netwerk van een leeralgoritme en correcte leervoorbeelden met ‘invoer; gewenste uitvoer’ paren wordt voorzien. Als het neurale netwerk genoeg is getraind, zijn de gewichten tussen de neuronen zo veranderd dat het in staat is om voor elke invoer de gewenste uitvoer terug te geven. Het netwerk heeft dan geleerd te generaliseren, zodat het na een bepaald aantal voorbeelden zelfstandig met nieuwe invoer om kan gaan.

Lerende netwerken

Toch zijn de hiervoor besproken neurale netwerken nogal statisch: de invoer wordt meteen omgezet naar een bepaalde uitvoer. Het wordt interessanter als er gedurende een tijdsinterval continu invoer wordt gegeven die een geheel vormt in het betreffende tijdsinterval. Een voorbeeld van dit soort tijdsafhankelijke invoer vind je terug in spraakherkenningsystemen. Op een bepaald tijdstip komen er bepaalde geluidsgolven een microfoon binnen, maar dat is niet genoeg om te herkennen welk woord er gezegd is. Kunstmatige neurale netwerken zijn daarom uitgebreid met wederkerende verbindingen waarin de informatie terug het netwerk instroomt, zodat ze in staat zijn om een kortetermijngeheugen te modelleren in de activiteit van de neuronen. Zulke recurrente neurale netwerken kunnen chaotisch en onvoorspelbaar gedrag vertonen en allerlei niet-lineaire tijdsafhankelijke functies benaderen.

Aangezien kunstmatige intelligentie zich bezighoudt met het modelleren van gedrag, zijn er allerlei verbanden met de neurobiologie, theoretische biologie, controletheorie, psychologie, economie, etc. Bepaalde recurrente neurale netwerken, genaamd liquid state machines, blijken het best presteren als de neuronen een topologie hebben die vergelijkbaar is met de menselijke visuele cortex. Kunstmatig leven, een deelgebied van de ki, bekijkt emergente (spontaan optredende) processen, waarbij de uitkomst van te voren niet te voorspellen is. Computersimulaties laten bijvoorbeeld zien dat er een grotere populatie van een soort tegelijkertijd kan leven in bepaalde omstandigheden als de individuen minder oud worden. Het spontane gedrag van elementen binnen een ruimtelijke representatie wordt zo als netwerk gemodelleerd.

Verkeerslichten

Verkeersnetwerken vertonen allerlei interessante gedragingen, zoals filegolven die zich tegen de richting van het verkeer in bewegen met een snelheid van ongeveer 30 km/u, zodat de file zich over langere termijn steeds naar achteren verplaatst. Verkeerslichtnetwerken hebben meestal een simpele topologie, die in rustige verkeerssituaties voldoet. Als er echter meer verkeer zo’n netwerk binnenkomt, kan dat leiden tot exponentieel groeiende wachttijden, wat veel mensen dagelijks in de spits ervaren.

De meest gebruikte methode om verkeerslichten te regelen maakt gebruik van een optimalisatie van tijdsintervallen: de totale cyclustijd met splitsingstijdsintervallen waarin bepaalde lichtconfiguraties op groen gezet worden. De cyclustijd kan bijvoorbeeld een minuut zijn, waarbij verschillende wegen voor het kruispunt hun licht 10 seconden op groen hebben staan. Deze lichtconfiguraties worden dan steeds herhaald. Onderzoek heeft uitgewezen dat als er weinig verkeer is, korte tijdsintervallen veel beter werken, omdat met lange tijdsintervallen soms al het verkeer al van bepaalde wegen is weggereden en het overige verkeer onnodig moet wachten. Als het echter heel druk is, zijn lange tijdsintervallen nodig, omdat de auto’s eerst op gang moeten komen en daarna pas op snelheid het kruispunt kunnen passeren.

Deze technieken maken echter geen gebruik van actieve waarneming van het verkeer. Omdat de tijdsintervallen zich niet aanpassen wordt er geen rekening gehouden met dynamische factoren zoals een weg die onlangs is afgesloten. Met camera’s en verkeerslussen die meten of er verkeer over een bepaalde lijn rijdt, is het mogelijk om te detecteren of er veel onverwacht verkeer is, bijvoorbeeld omdat er net een voetbalwedstrijd is afgelopen. Een voordeel van deze aanpak is dat in een verkeersader series verkeerslichten in fase geschakeld kunnen worden, wat leidt tot zogenaamde ‘groene golven’. Dit werkt vooral goed als het meeste verkeer op hoofdwegen rijdt.

Zelflerende verkeerslichten

In 1996 maakten Thorpe en Anderson verkeerslichten adaptief aan het verkeer door ze zelf te laten leren hoe de wachttijden van weggebruikers te minimaliseren. Ze trainden neurale netwerken met reinforcement learning algoritmen om lichten op rood en groen te zetten. Reinforcement learning algoritmen trainen een controller door die te laten interacteren met een omgeving. Acties worden beloond of bestraft zodat de controller gaandeweg leert om actiesequenties te genereren die op lange termijn de meeste beloningen of de minste strafpunten opleveren.

Bij verkeerslichtcontrole wordt er meestal gebruik gemaakt van een strafpunt voor elke tijdstap die een auto moet wachten. De straf per tijdseenheid is gelijk aan het gemiddelde aantal auto’s dat staat te wachten voor een rood licht. De controller probeert allerlei verschillende actiesequenties uit en bepaalt de gemiddelde straf die daaruit volgt. Na een lang leerproces is de controller dan in staat om de optimale actiesequentie te selecteren.

Deze methode werd gebruikt in een simulatie waarin het doel was om een aantal auto’s zo snel mogelijk een kruispunt te laten passeren. Een nadeel van deze techniek is het grote aantal patronen dat veroorzaakt wordt door verschillende hoeveelheden auto’s op alle wegen.

De techniek die mijn collega’s en ik hebben voorgesteld maakt gebruik van reinforcement learning algoritmen en stemmechanismes geleend van de speltheorie. In plaats van rekening te houden met de gecombineerde patronen van autolocaties voor een kruispunt, gebruiken wij een techniek waarbij de individuele auto centraal staat. Daardoor hebben onze verkeerslichtalgoritmen geen neurale netwerken nodig maar kunnen we gebruik maken van veel sneller lerende opzoektabellen. Hiernaast onderscheidt onze techniek zich door het gebruik van stemmechanismen.

Stemmen

Stel je voor dat je zou weten hoe lang een weggebruiker, die een bepaald verkeerslicht nadert, nodig heeft om bij zijn of haar bestemming te komen. Als het licht voor deze weggebruiker nu op rood wordt gezet, is deze verwachte tijd natuurlijk langer dan als het licht op groen wordt gezet. Dit komt niet alleen omdat de weggebruiker op dit moment moet wachten, maar wellicht ook nog op volgende kruispunten waar misschien wel net een hoop andere weggebruikers naartoe gereden zijn. We nemen aan dat we deze totale wachttijd voor het huidige verkeerslicht weten. Elke weggebruiker heeft natuurlijk voordeel bij groen licht. Maar dit voordeel, gedefinieerd door het verschil in verwachte wachttijd voor rood en groen, is niet voor iedere weggebruiker gelijk.

Als er nu een hele groep weggebruikers voor een kruispunt staat, worden de weggebruikers in staat gesteld te stemmen en de configuratie die het meeste voordeel oplevert wordt gekozen. De verkeerslichtcontroller in ons systeem neemt hierin het initiatief en berekent de totale voordelen van verschillende configuraties, door te kijken waar de auto’s voornamelijk aanwezig zijn. De bestuurders van de auto’s stemmen hierbij niet zelf, maar seinen slechts hun bestemming aan de controller door. Ze kunnen dus geen onrechtmatig voordeel behalen door verkeerde informatie te communiceren.

In ons systeem worden lichtconfiguraties bepaald met enkel lokaal aanwezige informatie, maar er is onlangs onderzoek gedaan waarin controllers van verschillende kruispunten ook met elkaar communiceren om zo een heel verkeerslichtnetwerk globaal te optimaliseren.

Interactieve infrastructuur

Hoe kunnen we de verwachte wachttijd nu schatten? Dit gebeurt met reinforcement learning algoritmen, waarbij weggebruikers over het wegennet worden gevolgd en hun verwachte wachttijden op een statistische wijze worden bepaald. Hiervoor is het trouwens niet nodig elke individuele weggebruiker de hele tijd te volgen, het is enkel nodig dat een verkeerslicht waarneemt hoeveel auto’s hoe lang staan te wachten voor een kruispunt. Deze aanpak vergt weliswaar een verandering van de infrastructuur en is daarom redelijk kostbaar, maar kan ook veel voordelen bieden voor weggebruikers. Een mogelijkheid is om breedbandcommunicatie tussen weggebruikers en verkeerslichten te bewerkstelligen, zodat weggebruikers kunnen weten hoe ze het beste moeten rijden om files, drukte, en botsingen te ontwijken.

Mijn collega’s en ik hebben deze zelflerende verkeerslichten op virtuele verkeersnetwerken gesimuleerd. Het grootste verkeersnetwerk dat wij hebben getest telde 15 kruispunten. In dit experiment hebben we de lerende methode vergeleken met een aantal niet-lerende systemen. De resultaten toonden aan dat de lerende methoden de totale wachttijden minstens 25 % konden verminderen vergeleken met de beste niet-lerende controllers. Verder vertoonden de lerende verkeerslichtnetwerken bepaald interessant beslissingsgedrag. Zo blijkt het voordelig te zijn om prioriteit te geven aan weggebruikers die de stad uit rijden, voordat er meer verkeer de stad binnengelaten wordt. Dit zorgt voor gemiddeld minder verkeer, wat de doorstroom ten goede komt.

Conclusie

We hebben in dit artikel kort de mogelijkheden van zelflerende verkeerslichten besproken. Bij de voorgestelde methoden zal het verkeer waargenomen moeten worden, maar dat zal met verbeteringen in de communicatietechniek in de nabije toekomst zeker mogelijk zijn. De experimenteel aangetoonde vermindering van wachttijden is niet alleen belangrijk om tijd te besparen, maar leidt ook tot minder brandstofgebruik en daarmee een reductie in kosten en vervuiling. Een ander voordeel van deze aanpak is dat stemmen van weggebruikers ook een prioriteitsgewicht kunnen meekrijgen, hetgeen het mogelijk maakt om het openbaar vervoer sneller door het verkeersnetwerk te loodsen dan gewone weggebruikers. Hierdoor zouden meer mensen gebruik kunnen gaan maken van het openbaar vervoer, wat leidt tot minder drukte en dus de mogelijkheid voor iedereen om sneller zijn of haar bestemming te bereiken.