Van iVRI naar AiVRI: Onderzoek naar kunstmatige intelligentie in verkeerslichten

Wie kan betere verkeerslichtenregelingen maken: een computer of een mens? Het onderzoeksteam van DTV Consultants heeft in een R&D-project getoetst of het mogelijk is om een computer een verkeerslichtenregeling te laten maken. In een eerste stap is daarbij vooral gekeken naar doorstroming met in het achterhoofd dat een straatwaardige regeling uiteindelijk ook geloofwaardig en veilig moet zijn.

Ondanks de standaardspecificaties van veel wegbeheerders is elk kruispunt uniek. Ontwerpers en programmeurs hebben er hun handen vol aan. De manier waarop verkeerslichten geprogrammeerd worden blijkt daarnaast toch nog een zekere onvoorspelbaarheid met zich mee te brengen, waardoor ook het testen van de regelingen behoorlijk wat aandacht vergt. Tegelijkertijd is het regelen van verkeer voor een groot deel een wiskundig optimalisatieproces. De gedachte is dan dat verkeerslichtenregelingen aan zulke bijzondere eisen moeten voldoen dat het al deze menselijke inspanning rechtvaardigt. Op de achtergrond speelt daarbij de heilige drie-eenheid: doorstroming, veiligheid en geloofwaardigheid. Doorstroming optimaliseren is iets dat computers beter kunnen dan mensen, maar hoe garandeer je binnen die randvoorwaarden ook dat de regeling veilig en geloofwaardig blijft?

DTV Consultants heeft in het onderzoeksproject twee concepten van kunstmatige intelligentie/machine learning uitgeprobeerd: genetisch programmeren en reïnforcement learning.

Genetisch programmeren

Bij genetisch programmeren is er een hoofdprogramma waarmee heel veel random programmaatjes worden gegenereerd. Deze random programmaatjes beschrijven de regels waarmee richtingen naar groen of rood moeten worden gestuurd. De eerste generatie van programmaatjes presteert slecht. Sommige programma’s doen niks, andere verwerken in meer of mindere mate het verkeer. Alle programmaatjes worden na simulatie in SUMO automatisch geëvalueerd op het criterium verliestijd. De beste programmaatjes krijgen een grotere mogelijkheid om hun eigenschappen, de “genen”, door te geven aan een volgende generatie, ze mogen zich als het ware voortplanten.

Best passende verkeerslichtenprogramma blijft over

In de tweede generatie ontstaan er programmaatjes met gekruiste eigenschappen van “ouders” die bij de eerste generatie zijn geselecteerd voor voortplanting. Die tweede generatie presteert iets beter dan de vorige. Dat gaat zo meerdere generaties door en na verloop van tijd neemt de verliestijd in elke nieuwe generatie steeds minder af. Het proces kan dan stoppen: er is een nieuw verkeersregelprogramma. Om te voorkomen dat elke generatie het moet doen met de eigenschappen die al in de eerste generatie bestonden, treden er tijdens het proces ook in beperkte mate mutaties op: eigenschappen die nieuw geïntroduceerd worden tijdens het ontstaan van elke nieuwe generatie. De naam genetisch programmeren is dan ook afgeleid van hetzelfde proces in de evolutie van het leven en Darwin’s survival of the fittest. De oorspronkelijke betekenis van “fittest” wordt vaak uitgelegd als “sterkste” maar het betekent letterlijk “best passend”.

Reinforcement learning

Reïnforcement learning werkt heel anders. Er start een simulatie. De simulatie beloont zichzelf als de cumulatieve wachtrij (aantal voertuigen dat staat te wachten) minder wordt en onthoudt wat de omstandigheden waren die tot deze beloning leidden. Na een tijdje neemt het programma steeds betere beslissingen om de wachtrij weggewerkt te krijgen en na verloop van tijd nemen de prestaties van het programma niet verder toe. Er kunnen ook straffen aan worden toegevoegd als er zaken gebeuren die onwenselijk zijn: bijvoorbeeld een zijrichting die te lang staat te wachten.

Reinforcement learning verkeerslichtenregeling

Langer wachten of black box

Het voornaamste nadeel van genetisch programmeren is dat het lang duurt voordat er een programma is. Zou je dit op één individuele computer draaien, dan duurt het weken voordat er een programma is. Reïnforcement learning leidt snel tot een programma, al binnen één of twee dagen, wederom gerekend met één enkele computer. Een nadeel van deze methode is dat het resulterende programma een black-box is terwijl het product van genetisch programmeren in principe een leesbaar programma oplevert. Het programma onthoudt alleen welke beslissingen de beste resultaten opleveren maar niet waarom dat zo is. Dat leesbare programma van genetisch programmeren kan overigens overbodige code bevatten.

Snelheid maakt reinforcement learning meest kansrijk

Vanwege de snelheid denken we desondanks dat reïnforcement learning kansrijker is. Dat betekent wel dat je met allerlei randvoorwaarden moet garanderen dat het programma geen dingen doet die je niet wil. Die randvoorwaarden kun je op verschillende manieren aanpassen. Je kunt het “speelveld aanpassen” zodat bepaalde faseovergangen altijd volgens dezelfde regels verlopen. Van een voorstart van een voetganger in deelconflict wil je zeker weten dat aan die randvoorwaarde voldaan wordt. Als een bepaalde actie gewenst is maar niet in honderd procent van de gevallen hoeft plaats te vinden, dan is een andere mogelijkheid om de beloningen en straffen te veranderen. Op die manier kan het programma bijvoorbeeld bijna altijd OV-prioriteit geven, maar niet ten koste van alles.

Tijdens de Studiedag Verkeerslichten 2020 is hierover een presentatie gegeven die hier te downloaden is.

Advies en informatie
Carl Stolz

Carl Stolz

Teamleider Data & Development
Bart Veroude

Bart Veroude

Datawetenschapper