Distance-Constrained Unlabeled Multi-Agent Pathfinding

Stel je een bruisende stad voor waar duizenden kleine, identieke leveringsrobots van hun oplaadstations naar een stapel pakketjes moeten zoemen. In de wereld van de robotica wordt dit Multi-Agent Pathfinding (MAPF) genoemd. Meestal vertellen we deze bots gewoon: "Bots niet tegen elkaar op." Maar in de echte wereld is het rommeliger. De propellers van een drone kunnen stof op een buurman blazen, of een grote magazijnrobot heeft een veiligheidsbuffer nodig zodat hij geen schap raakt. Dit betekent dat robots niet alleen niet "dichtbij" elkaar mogen zijn; ze moeten op elk moment een specifieke afstand tot elkaar bewaren.

De uitdaging die dit artikel aanpakt, is als het choreograferen van een dans voor honderden identieke dansers die nooit dichter dan een bepaald aantal stappen bij elkaar mogen komen. Als ze te dicht bij elkaar komen, is dat een "botsing". De twist? De dansers zijn anoniem; het maakt niet uit welke specifieke danser op welke specifieke plek terechtkomt, zolang iedereen er maar veilig komt. Dit klinkt eenvoudig, maar wanneer je de regel toevoegt dat ze ver van elkaar af moeten blijven, wordt de wiskunde ongelooflijk moeilijk. Het is als het proberen op te lossen van een puzzel waarbij de stukjes constant van vorm veranderen, en soms is de enige manier om het op te lossen misschien wel langer dan de leeftijd van het universum.

Dit artikel introduceert een nieuwe manier om over dit probleem na te denken, die de auteurs Distance-r Independent Unlabeled Multi-Agent Pathfinding (of kortweg rIUMAPF) noemen. Ze ontdekten dat terwijl de standaardversie van dit probleem gemakkelijk op te lossen is, het toevoegen van de "houd afstand"-regel een nachtmerrie maakt voor computers om zelfs maar te bepalen of er een oplossing bestaat. De auteurs hebben echter niet de handen in onwetendheid gestoken. Ze hebben twee verschillende instrumenten gebouwd om dit beest aan te pakken.

Het eerste instrument is als een superprecieze architect. Het gebruikt een methode genaamd Integer Linear Programming (ILP) om de absoluut beste, meest efficiënte route te vinden. Om dit werkbaar te maken op een computer, hebben ze een slimme "compressie"-truc uitgevonden. Stel je voor dat je een gigantisch doolhof hebt met veel lege, nutteloze gangen. De architect kan die lege delen inkrimpen tot kleine, magische zwarte gaten die elke robot die erdoorheen passeert absorberen, waardoor het doolhof veel kleiner en sneller op te lossen wordt. Dit werkt geweldig voor kleine groepen robots, maar als je er honderden hebt, wordt de wiskunde te zwaar en loopt de architect vast.

Het tweede instrument is een snelle, intuïtieve improvisator. In plaats van het perfecte pad van begin tot eind te berekenen, gebruikt het een "configuratiegenerator" genaamd IU-PIBT. Denk aan dit als een verkeersregelaar die naar de huidige scène kijkt en elke robot vertelt: "Oké, jij beweeg daarheen, jij beweeg hierheen," stap voor stap. Het is ongelooflijk snel en kan enorme zwermen robots aan. Soms raakt de verkeersregelaar echter in de war en beginnen de robots in cirkels te draaien (een "livelock") zonder ooit hun bestemming te bereiken. Om dit op te lossen, hebben de auteurs een "zoeklaag" toegevoegd genaamd IU-LaCAM. Dit fungeert als een slimme supervisor die de verkeersregelaar in de gaten houdt. Als de robots in cirkels beginnen te draaien, grijpt de supervisor in, wijst de doelen opnieuw toe en doorbreekt de impasse.

De resultaten zijn indrukwekkend. Hoewel het probleem theoretisch zo moeilijk is dat het in de slechtste gevallen eeuwig kan duren, werken de methoden van de auteurs verrassend goed in de praktijk. Hun "improvisator" (IU-LaCAM) kan honderden agenten op grote kaarten in enkele seconden afhandelen en lost problemen op die andere methoden zouden overrompelen. Ze ontdekten dat terwijl de "architect" (ILP) goed is voor kleine, hoogwaardige plannen, de "improvisator" de held is voor grootschalige chaos. Interessant genoeg ontdekten ze ook dat het hebben van een grotere veiligheidsafstand (een grotere "r") de problemen soms zelfs makkelijker maakt, omdat het voorkomt dat robots vast komen te zitten in smalle, drukke gangen.

Kortom, dit artikel bewijst dat we zelfs met strikte veiligheidsregels en identieke robots nog steeds paden kunnen vinden voor enorme groepen van hen. Ze hebben niet elke mogelijke versie van het probleem opgelost (sommige zijn nog steeds te moeilijk voor elke computer), maar ze hebben een gereedschapskist gebouwd waarmee we kunnen bewegen van "theoretisch onmogelijk" naar "praktisch uitvoerbaar" voor echte robotzwermen.