⚡ electrical engineering

Motion planning for hundreds of floating robots

Dit artikel presenteert een schaalbare bewegingsplanningspipeline die botsingsvermijding voor grote vloten van zwevende robots deelt in parallelle interactieclusters, wat de snelle generatie van botsingsvrije trajecten mogelijk maakt die gevalideerd zijn in simulaties van tot wel 500 robots en in real-world implementaties.

Oorspronkelijke auteurs: Jan Kamm, Antonio Terpin, Raffaello D'Andrea, Aswin Ramachandran

Gepubliceerd 2026-06-09

📖 4 min leestijd☕ Koffiepauze-leesvoer

CC BY 4.0

Oorspronkelijke auteurs: Jan Kamm, Antonio Terpin, Raffaello D'Andrea, Aswin Ramachandran

Oorspronkelijk artikel gelicentieerd onder CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ Dit is een AI-gegenereerde uitleg van het onderstaande artikel. Het is niet geschreven of goedgekeurd door de auteurs. Raadpleeg het oorspronkelijke artikel voor technische nauwkeurigheid. Lees de volledige disclaimer

Stel je voor dat je de regisseur bent van een enorme, drijvende dansshow op een meer. Je hebt honderden kleine, autonome bootjes (robots) die van de ene formatie naar de andere moeten bewegen, zoals het veranderen van een hartvorm in het woord "Water".

Het probleem? Als je probeert om alle 500 bootjes tegelijkertijd te vertellen waar ze heen moeten, wordt de wiskunde heel snel erg ingewikkeld. Elk bootje moet immers botsingen met elk ander bootje voorkomen. Naarmate het aantal bootjes groeit, explodeert het aantal "vermijdingsregels", waardoor de computer er eeuwig over doet om een veilig pad te berekenen.

Dit artikel presenteert een nieuwe, supersnelle manier om deze dansen te plannen, zodat een menselijke ontwerper de bewegingen kan aanpassen en het resultaat binnen enkele seconden kan zien, zelfs voor enorme vloten.

Zo hebben ze het aangepakt, onderverdeeld in eenvoudige stappen:

1. Het "Verkeersopstopping"-probleem

Het plannen van een vloot is normaal gesproken als het oplossen van een gigantische puzzel waarbij elk stukje met elk ander stukje verbonden is. Als je 500 robots hebt, moet de computer miljoenen potentiële botsingen controleren. Het is als het dirigeren van het verkeer in een stad waar elke auto tegelijkertijd met elke andere auto praat. Dat gaat te langzaam voor een mens om op te wachten.

2. De "Groepsapp"-strategie (Hiërarchische planning)

In plaats van één gigantische lijst met regels voor iedereen te maken, werkt het systeem van de auteurs als een slimme organisator die de menigte opdeelt in kleinere groepen.

Stap 1: De ruwe schets. Eerst tekent de computer een snelle, ruwe lijn voor elke robot van begin tot eind. Deze lijn bevat misschien crashes, maar het geeft een startpunt.
Stap 2: Clusters vinden. De computer kijkt naar deze ruwe schets en vraagt: "Wie botst er eigenlijk met wie?" Het bouwt een kaart (een graaf) die alleen de robots laat zien die dicht bij elkaar zijn.
Stap 3: Het opdelen. Het groepeert deze "botsende" robots in kleine clusters. Robots die ver uit elkaar liggen, hoeven niet met elkaar te communiceren.
Stap 4: Parallel oplossen. Nu, in plaats van één supercomputer die het hele meer probeert op te lossen, stuurt het systeem elke kleine groep naar een andere processor om tegelijkertijd hun eigen mini-puzzel op te lossen. Het is alsof je 50 verschillende mensen hebt die tegelijkertijd 50 verschillende verkeersopstoppingen oplossen, in plaats van één persoon die ze allemaal één voor één oplost.

3. De "Veiligheidsbuffer"

Soms, wanneer je een crash in één groep oplost, kun je per ongeluk een crash veroorzaken in een naburige groep. Om dit op te lossen, voegt het systeem een "veiligheidsbuffer" (een beetje extra tijd en ruimte) rond de groepen toe. Als twee groepen te veel overlappen, voegt het systeem ze voor dat specifieke moment slim samen, lost het grotere probleem op, en splitst ze daarna weer uit elkaar. Dit voorkomt dat het systeem vastloedt in een eindeloze lus van het steeds opnieuw oplossen van dezelfde fouten.

4. De "Slimme Wiskunde"-truc

Binnen elke kleine groep gebruikt de computer een specif kind wiskunde (genaamd Sequential Convex Programming) om de paden vloeiender te maken. De auteurs hebben deze wiskunde verbeterd door de manier waarop de vergelijkingen worden opgeschreven te veranderen. Denk aan het overstappen van een slordig, handgeschreven briefje naar een schoon, georganiseerd spreadsheet. Deze verandering zorgt ervoor dat de computer de wiskunde veel sneller en betrouwbaarder oplost, vooral wanneer de robots dicht op elkaar gepakt zitten.

Bewijs uit de praktijk

Het team heeft dit niet alleen gesimuleerd op een computer; ze hebben het ook echt in de buitenwereld getest:

Zürichmeer: Ze hebben met succes 24 drijvende robots choreografieën laten uitvoeren.
Venetië Biënnale (2025): Ze gebruikten het voor een kunstinstallatie met 8 robots.
Simulatie: Ze bewezen dat het werkt voor wel 500 robots in een computersimulatie.

De kern van het verhaal

De belangrijkste prestatie is snelheid en betrouwbaarheid. Voorheen kon het plannen van een show voor honderden robots uren duren of volledig mislukken. Met deze nieuwe pijplijn kan een ontwerper een paar "keyframes" (de begin- en eindposities van de dans) verplaatsen en binnen seconden een veilig, botsingsvrij plan terugkrijgen. Dit maakt het mogelijk om complexe, interactieve robotshows te creëren waarbij mensen de choreografie ter plekke kunnen aanpassen zonder te hoeven wachten tot de computer bij is.

Technische Samenvatting: Bewegingsplanning voor honderden zwevende robots

Probleemstelling
Het artikel behandelt de uitdaging van het plannen van botsingsvrije, dynamisch haalbare trajecten voor grote vloten omnidirectionele zwevende robots (oppervlakterobots) die opereren op een planaire manifold. In tegenstelling tot luchtvaartdrones, die verticale manoeuvres kunnen gebruiken om drukke overgangen te ontwijken, zijn oppervlakterobots beperkt tot 2D, wat coördinatie en botsingsvermijding inherent moeilijker maakt. De planningscontext is interactief showontwerp, waarbij een ontwerper schaarse keyframes (start- en eindconfiguraties) specificeert en snelle feedback vereist (seconden) om trajecten te genereren die minuten en duizenden tijdstappen kunnen beslaan.

De kern van de moeilijkheid ligt in de schaalbaarheid van botsingsvermijding. Naarmate de vlootgrootte ( $N$ ) toeneemt, groeit de onderlinge koppeling tussen agenten snel (vaak kwadratisch), wat leidt tot een aantal paargewijze botsingsbeperkingen dat schaalt als $\binom{N}{2}K$ (waarbij $K$ het aantal tijdstappen is). Voor grote $N$ (bijv. 500) en $K$ (bijv. 1000), resulteren standaard Sequential Convex Programming (SCP) formuleringen in Kwadratische Programma's (QP) met honderden miljoenen niet-nul elementen, wat ze computationeel onuitvoerbaar maakt voor iteratieve ontwerplussen.

Methodologie
De auteurs stellen een schaalbare, hiërarchische planningspipeline voor die het globaal gekoppelde probleem deelt op in kleinere, onafhankelijke subproblemen. De pipeline bestaat uit vier hoofdfasen:

Initialisatie en Toewijzing:
- Het proces begint met een kostenminimaliserend toewijzingsprobleem om robots aan doelposities te koppelen. Voor "gelabelde" robots (die vaste door de gebruiker gedefinieerde doelen hebben), is de kosten nul of oneindig om specifieke matches af te dwingen. Voor "ongelabelde" robots is de kosten de Euclidische afstand, wat de totale verplaatsing minimaliseert om onnodige wissels te verminderen.
- Een initieel traject wordt gegenereerd via lineaire interpolatie tussen start- en eindposities. Deze initialisatie is over het algemeen niet botsingsvrij.
Constructie van de Botsingsgraaf:
- Een spatio-temporele graaf wordt gebouwd waarbij knopen robot-tijd paren vertegenwoordigen.
- Ruimtelijke randen verbinden robots op hetzelfde tijdstip als ze zich binnen een veiligheidsstraal $R$ bevinden.
- Temporele randen verbinden een robot met zichzelf over opeenvolgende tijdstappen als er een botsing optreedt in één van beide.
- Verbonden componenten van deze graaf definiëren "botsingsclusters". De auteurs maken gebruik van een KD-tree datastructuur om paargewijze schendingen efficiënt te detecteren, wat een versnelling van bijna 2000× oplevert ten opzichte van naïeve paargewijze controle.
Clustering en Decompositie:
- Om de optimizer de vrijheid te geven om omwegen te plannen, wordt het temporele venster van elk cluster uitgebreid (gebufferd) met een hyperparameter $B$ (gesteld op 3 seconden).
- Overlappende gebufferde clusters worden samengevoegd met behulp van een union-find procedure. Om de creatie van subproblemen te voorkomen die te groot zijn (wat de voordelen van parallellisatie tenietdoet), wordt een complexiteitslimiet afgedwongen. Als het samenvoegen een drempel van niet-nul elementen in de QP-matrices overschrijdt, wordt de groep gesplitst met behulp van een scoringmechanisme dat de maximale complexiteit van de resulterende subproblemen minimaliseert.
Subprobleem Oplossen en Samenvoegen:
- Elk cluster wordt onafhankelijk en parallel opgelost met behulp van een SCP-framework.
- Formulering Verbetering: Het artikel introduceert een "directe transcriptie" formulering waarbij de beslissingsvector zowel posities als snelheden bevat ( $\chi = [p, v]$ ). Dit zet dynamica om in lokale gelijkheidsbeperkingen en verbetert de periodiciteit van de beperkingsmatrix aanzienlijk (het vermindert de complexiteit van $O(N^2K^2)$ naar $O(N^2K)$ ) vergeleken met de "directe schietmethode" (direct shooting) die in eerder werk werd gebruikt.
- Robuustheid: Mechanismen omvatten het verstoren van initialisatie voor symmetrische configuraties, het adaptief vergroven van discretisatie als een oplossing onhaalbaar is, en een lichtgewicht polijststap.
- Cyclusdetectie: De pipeline detecteert cyclische afhankelijkheden waarbij het samenvoegen van clusters leidt tot oscillerende botsingspatronen. Bij detectie worden conflicterende subproblemen vastgezet in één gezamenlijk subprobleem voor volgende iteraties.
- Ten slotte worden lokale oplossingen samengevoegd tot een globaal traject, en de lus wordt herhaald totdat een botsingsvrije oplossing wordt gevonden.

Belangrijkste Bijdragen

Schaalbare Hiërarchische Pipeline: Een methode die een botsingsgraaf bouwt, het probleem deelt in interactieclusters en deze parallel oplost, wat het plannen voor honderden robots in seconden mogelijk maakt.
Robuuste Decompositiemechanismen: Technieken voor het afhandelen van veelvoorkomende pathologieën, inclusief snelle graafupdates, bufferingsstrategieën, complexiteitslimieten om subprobleemexplosie te voorkomen, en cyclusdetectie om oscillatie te voorkomen.
Optimalisatieherformulering: Een verschuiving naar een directe transcriptie formulering voor cluster-niveau trajectoptimalisatie, wat de QP-periodiciteit en solver-robuustheid verbetert, met name voor configuraties met een hoog percentage gelabelde robots.

Resultaten en Validatie
Het systeem werd gevalideerd in simulaties en twee real-world implementaties:

Simulatie: De pipeline genereerde succesvol botsingsvrije trajecten voor vloten van tot 500 robots over 1000 tijdstappen. In een casestudy met 500 robots bereikte de solver een convergentiepercentage van 100% voor tot 30% gelabelde robots en 99% voor hogere percentages, waarbij de rekentijden doorgaans onder de enkele seconden bleven.
Real-World Implementatie 1 (Meer van Zürich): Een vloot van 24 robots werd gechoreografeerd voor overgangen die 1–2 minuten beslaan (400+ tijdstappen). Ontwerpers konden iteratief keyframes aanpassen en trajecten binnen enkele seconden regenereren.
Real-World Implementatie 2 (Venetië Biënnale 2025): Een vloot van 8 robots voerde overgangen uit die meer dan 2000 tijdstappen beslaan. Een traject van 2491 stappen werd berekend in 1,23 seconde.

Betekenis
Het artikel beweert dat deze op engineering gerichte pipeline de kern van de schaalbaarheidsproblematiek bij multi-robot bewegingsplanning op oppervlakken aanpakt. Door het probleem te deconstrueren en de solver-formulering te optimaliseren, is deze aanpak orders van grootte sneller dan traditionele monolithische SCP-pipelines. Deze snelheid maakt een soepele, interactieve gebruikerservaring voor choreografieontwerp mogelijk, waardoor ontwerpers iteratief schaarse keyframes kunnen aanpassen en onmiddellijke feedback kunnen krijgen op botsingsvrije, dynamisch haalbare trajecten, een capaciteit die voorheen beperkt werd door computationele restricties in 2D-oppervlaktemilieus.