Stel je een wereld voor waarin robots, zelfrijdende auto's en drones niet alleen een script volgen, maar ook echt een hoogwaardig schaakspel met elkaar spelen om uit te vogelen hoe ze kunnen bewegen zonder tegen elkaar op te botsen. Dit is het domein van multi-agent robotica, waar elke robot een speler is die probeert zijn eigen race te winnen terwijl hij botsingen met al het andere probeert te vermijden. Om deze beslissingen in realtime te nemen, gebruiken ingenieurs een wiskundig hulpmiddel genaamd een "Mixed Complementarity Problem" (MCP). Denk aan een MCP als een gigantisch, complex regelboek dat precies beschrijft hoe elke speler moet handelen om een perfect evenwicht te bereiken waarbij niemand zijn situatie kan verbeteren door alleen zijn eigen zet te veranderen. Jarenlang was de enige manier om dit regelboek te lezen het gebruik van een zeer krachtige, maar gesloten stuk software genaamd PATH. Het was alsocht het hebben van een meesterkok die een perfect maaltijd kon koken, maar je mocht het recept niet zien, de ingrediënten niet veranderen en je moest wachten tot de kok één enkel gerecht had bereid voordat je met het volgende kon beginnen.

Maak kennis met een nieuw team van onderzoekers dat een gloednieuwe, open-source keuken heeft gebouwd: MixedComplementarityProblems.jl. In plaats van één gerecht tegelijk te koken, hebben zij ontdekt hoe ze honderden gerechten tegelijkertijd kunnen bereiden, of ze nu een standaard fornuis (een computer-CPU) of een supersnelle industriële oven (een videokaart of GPU) gebruiken. Hun grote ontdekking? Door in batches te koken, kunnen ze deze complexe robotspellen ongeveer 100 keer sneller oplossen dan de oude methode, en kunnen ze dit op gewone computers doen zonder speciale, dure hardware nodig te hebben. Ze hebben het ook mogelijk gemaakt om het recept onderweg aan te passen, wat cruciaal is voor het leren van robots van hun fouten.

Het Probleem: De Robotverkeersopstopping

In de wereld van robotica wordt het ingewikkeld wanneer meerdere agenten — zoals auto's op een snelweg of drones in een magazijn — tegelijkertijd moeten bewegen. Elke agent wil zo snel mogelijk op zijn bestemming aankomen, maar ze moeten zich aan de verkeersregels houden en botsingen met anderen vermijden. Wiskundig gezien is dit een "niet-coöperatief spel". De oplossing voor dit spel is een specifieke reeks zetten waarbij iedereen tevreden is met zijn pad, gegeven wat iedereen anders doet.

Om deze oplossing te vinden, moeten de robots een Mixed Complementarity Problem (MCP) oplossen. Je kunt een MCP zien als een enorme, verstrengelde knoop van vergelijkingen. Sommige delen van de knoop zeggen: "Als je in het midden van de rijstrook rijdt, moet je snelheid nul zijn." Andere delen zeggen: "Als je tegen de muur botst, moet je stoppen." De knoop wordt nog ingewikkelder wanneer je een "parameter" toevoegt, zoals het veranderen van de startpositie van een auto of de maximumsnelheid. In de robotica moet je vaak duizenden van deze knopen tegelijk oplossen om te plannen voor verschillende scenario's (bijv. "Wat als de auto hier begint? Wat als hij daar begint?").

Lamaag was de industriestandaard voor het ontwarren van deze knopen een programma genaamd PATH. Het is betrouwbaar en sterk, maar het heeft drie grote gebreken:

1. Het is closed-source, wat betekent dat ontwikkelaars niet onder de motorkap kunnen kijken om het te repareren of aan te passen voor hun specifieke robot.
2. Het lost problemen één voor één op. Als je 1.000 scenario's wilt controleren, doet het ze sequentieel, wat veel tijd kost.
3. Het werkt niet goed samen met machine learning. Moderne AI heeft vaak nodig om te weten hoe de oplossing verandert als je de input licht aanpast (een proces dat differentiatie wordt genoemd), maar PATH maakt dit erg moeilijk.

De Oplossing: De Batch-Keuken

De auteur van dit artikel, die MixedComplementarityProblems.jl heeft gebouwd, heeft een nieuw solver geschreven in de programmeertaal Julia. Hun aanpak is als de upgrade van een enkele chef die één gerecht tegelijk bereidt naar een enorme keukenbrigade die een heel banket gelijktijdig kan bereiden.

Zo hebben ze het gedaan:

1. De "Batch"-Magie
In plaats van één robotspel op te lossen, dan weer een ander, dan weer een ander, neemt de nieuwe solver een hele "batch" van spellen — zeg, 1.024 verschillende verkeersscenario's — en lost ze allemaal tegelijk op.

• Op een CPU (Computerprocessor): Ze gebruiken de meerdere kernen van de computer (zoals het hebben van 32 chefs die parallel werken).
• Op een GPU (Videokaart): Ze gebruiken de duizenden kleine kernen van de videokaart (zoals een super-snelle assemblageband).

Het slimme deel is dat al deze spellen dezelfde basisstructuur delen (dezelfde vorm van de "knoop"), zelfs als de getallen erin verschillend zijn. De solver realiseert zich dit en hergebruikt het werk, waarbij alleen de specifieke getallen voor elk scenario worden aangepast.

2. Het "Open-Source" Recept
Omdat de code open-source is en in Julia is geschreven, kan iedereen de code bekijken, aanpassen of koppelen aan hun eigen robotsoftware. Het ondersteunt ook automatische differentiatie, wat betekent dat de solver je direct kan vertellen: "Als je de startpositie van de auto met één inch verplaatst, verandert het hele verkeerspatroon met deze hoeveelheid." Dit is een superkracht voor het trainen van AI-robots.

3. De "Slimme Pauze"
Een van de grootste uitdagingen bij het batch-oplossen is dat sommige problemen makkelijk zijn, sommige moeilijk en sommige onmogelijk. Als je wacht tot het moeilijkste probleem klaar is, zitten de makkelijke problemen gewoon te wachten.
De nieuwe solver is slim genoeg om te detecteren wanneer een specifiek scenario vastloopt of onmogelijk is. Hij "bevriest" dat probleem en stopt met het verspillen van tijd eraan, zodat de rest van de batch kan doorgaan. Dit voorkomt dat één hardnekkig probleem de hele groep vertraagt.

De Resultaten: Hoe snel is snel?

De onderzoekers hebben hun nieuwe solver getest tegen de oude standaard (PATH) met behulp van twee soorten problemen: willekeurige wiskundige puzzels (Quadratic Programs) en een realistisch "rijstrookwissel"-spel waarbij twee auto's proberen van rijstrook te wisselen zonder te botsen.

• Betrouwbaarheid: Eerst controleerden ze of de nieuwe solver net zo goed was als de oude. Dat was hij. Hij loste hetzelfde aantal problemen op als PATH, wat bewees dat hij niet alleen snel, maar ook accuraat was.
• Snelheid: Daarna maten ze de snelheid.
  • Voor het rijstrookwissel-spel rondde de nieuwe solver een batch van 1.024 scenario's af in ongeveer 0,44 seconden. De oude PATH-methode duurde 46,4 seconden. Dat is een versnelling van 105x.
  • Zelfs op de CPU van de computer (met 32 threads) was de nieuwe solver 100 keer sneller dan het een voor een draaien van PATH.
  • De GPU (videokaart) was ook ongelooflijk snel, maar opvallend genoeg was deze niet altijd de winnaar.

De Twist: Wanneer de GPU wint (en wanneer niet)

Het paper vond een verrassend detail over wanneer welke hardware te gebruiken.

• De CPU Koning: Voor het rijstrookwissel-spel was de CPU (met zijn 32 threads) daadwerkelijk sneller dan de GPU. Waarom? Omdat de wiskunde voor het rijstrookwissel-spel "sparse" (ijjl/leeg) is. De CPU is slim genoeg om de lege delen over te slaan en alleen aan de actieve problemen te werken. De GPU probeert echter de hele batch tegelijk te verwerken, zelfs de bevroren of voltooide delen, wat energie verspilt.
• De GPU Kampioen: De GPU nam pas de leiding wanneer de problemen zeer groot en "dense" (vol met getallen) werden. Bijvoorbeeld, toen ze de omvang van de willekeurige wiskundige puzzels vergrootten, was de GPU 3 keer sneller dan de CPU.

Dit leert ons dat er niet één "beste" machine is. Als je robotproblemen klein en sparse zijn, is een standaardcomputer met veel kernen de beste keuze. Als je problemen enorm en complex zijn, neemt een videokaart de leiding.

Waarom dit ertoe doet

Dit artikel biedt niet alleen een snellere rekenmachine; het biedt een nieuwe manier van denken. Door te laten zien dat we duizenden robotscenario's in een oogwenk kunnen oplossen met open-source tools, wordt een belangrijke flessenhals in de robotica weggenomen.

• Real-time Planning: Robots kunnen nu direct plannen voor veel "wat als"-scenario's, wat ze veiliger en aanpasbaarder maakt.
• Leren: Omdat de solver kan differentiëren, kunnen ingenieurs nu robots trainen om betere strategieën te leren direct vanuit deze spellen.
• Toegankelijkheid: Omdat het open-source is, kunnen onderzoekers overal ter wereld deze tools gebruiken zonder te betalen voor dure licenties of te wachten tot een enkel probleem is voltooid voordat ze met het volgende kunnen beginnen.

Kortom, de auteur heeft een brug gebouwd tussen complexe wiskunde en real-world robotica, en bewezen dat we met de juiste batch-verwerkingsstrategie de chaotische dans van multi-agent robots sneller dan ooit kunnen oplossen.