Collision-Free Velocity Scheduling for Multi-Agent Systems on Predefined Routes via Inexact-Projection ADMM

Titel

Kollisie-vrije snelheidsplanning voor multi-agent systemen op vooraf gedefinieerde routes via Inexact-Projection ADMM.

1. Probleemstelling

In gestructureerde multi-agent transportsystemen (zoals stedelijke luchtmobiliteit, geautomatiseerde magazijnen en robotcorridors) moeten agenten vaak vaste routes volgen die door de infrastructuur worden opgelegd. In deze scenario's is ruimtelijk herplannen (het wijzigen van het pad) ongewenst of onmogelijk.

• De uitdaging: Kollisievrijheid moet worden bereikt door de timing van de beweging langs de vaste routes te coördineren, in plaats van door de routes zelf aan te passen.
• Beperkingen van bestaande methoden:
  • Reactive methods: Lopen vaak vast in dichte omgevingen of zijn te conservatief.
  • Global planning methods: Gebruiken vaak ruimtelijke padmodificaties of combineren discrete volgordevariabelen (mixed-integer programming), wat leidt tot schaalbaarheidsproblemen en numerieke gevoeligheid bij hoge congestie.

Het doel van dit onderzoek is het optimaliseren van de tijdstippen waarop agenten waypoints passeren, zodat de missie zo snel mogelijk wordt voltooid zonder dat er kollities optreden, terwijl de volgorde van de waypoints en de toegewezen routes strikt worden behouden.

2. Methodologie

De auteurs stellen een raamwerk voor dat het probleem formuleert als een niet-lineaire, niet-convexe optimalisatieprobleem, opgelost met een aangepast ADMM-algoritme.

A. Differentieerbaar Surrogaat Trajectmodel

Om de niet-gladde aard van stuksgewijs constante snelheidsmodellen te omzeilen (wat gradientenberekening bemoeilijkt), wordt een differentieerbaar surrogaatmodel ontwikkeld:

• In plaats van harde overgangen tussen segmenten, worden gladde sigmoid-overgangen gebruikt.
• Het model houdt rekening met tracking-lag (vertraging) door een tijdsbias ($b$) toe te voegen.
• Dit zorgt ervoor dat de positie van een agent een gladde functie is van de waypoint-tijdstippen, wat essentiële is voor gradient-based optimalisatie.

B. Formulering van het Optimalisatieprobleem

• Beslissingsvariabelen: De tijdstippen waarop elke agent de waypoints passeert ($t^{(i)}$).
• Doelfunctie: Minimaliseren van de som van de voltooiingstijden van agenten zonder vaste aankomsttijden.
• Beperkingen:
  • Vaste vertrek- en aankomsttijden (indien van toepassing).
  • Snelheidsgrenzen (lineair in segmentduur).
  • Continue kollisievrijheid: De afstand tussen elke paar agenten moet op elk moment $\tau$ binnen de missiehorizon groter zijn dan een veilige afstand ($d_{safe}$).

C. Oplossing: Inexact-Projection ADMM

Het probleem wordt opgelost met de Alternating Direction Method of Multipliers (ADMM), waarbij het probleem wordt opgesplitst in beheersbare subproblemen:

1. Tijdsupdate (t-update): Lost een lineair stelsel op voor de timingvariabelen, waarbij de structuur van de routes en snelheidslimieten wordt gerespecteerd.
2. Snelheidsupdate (x-update): Projecteert de segmentduur op de convexe set van toegestane snelheden (closed-form oplossing).
3. Kollisie-update (z-update - Inexact Projection): Dit is de kerninnovatie. Omdat de verzameling kollisievrije trajecten niet-convex is, is een exacte projectie onberekenbaar. In plaats daarvan wordt een inexacte projectie uitgevoerd:
   • Er wordt een straffunctie ($f(z)$) gedefinieerd die de schending van de veiligheidsafstand meet op een dichte tijdsgrid.
   • Een Polyak-type gradient stap met adaptieve momentum wordt gebruikt om de tijdsvariabelen aan te passen en de straffunctie te minimaliseren.
   • Dit vermijdt het gebruik van expliciete gehele getallen (integer variables) voor het bepalen van de voorrangsorde, wat de schaalbaarheid verbetert.

3. Belangrijkste Bijdragen

1. Formulering: Het probleem van route-beperkte multi-agent coördinatie wordt geformuleerd als een optimalisatie van waypoint-tijdstippen met veiligheidsbeperkingen over de volledige missiehorizon.
2. Model: Ontwikkeling van een differentieerbaar surrogaatmodel dat waypoint-timing koppelt aan gladde posities, inclusief tracking-dynamica.
3. Solver: Een nieuw ADMM-algoritme met inexacte projectie dat niet-convexe kollisiebeperkingen oplost via gradient-based correctie, zonder discrete volgordevariabelen.
4. Validatie: Uitgebreide validatie in diverse scenario's (willekeurige kruisingen, bottlenecks, grafische netwerken) en vergelijking met een hiërarchische baseline.

4. Resultaten en Experimenten

De methode werd getest in drie scenario's met variërende agentaantallen ($K=3, 7, 11$) en bezettingsdichtheden ($\phi = 1\%, 5\%, 10\%$).

• Willekeurige Kruisingen (Random Crossing):
  • De methode lost zowel inhaakconflicten (co-directional) als kop-staartconflicten (counter-directional) succesvol op.
  • Convergentie is snel (meestal < 400 iteraties).
  • Bij hoge dichtheid ($K=11, \phi=10\%$) daalt het succespercentage licht door fysieke onmogelijkheid (niet door het algoritme), maar blijft het zeer robuust voor haalbare gevallen.
• Bottleneck Scenario:
  • Alle agenten moeten door een smalle corridor. De methode creëert een natuurlijke rij-volgorde door tijdsverschillen.
  • Zelfs in de meest dichte gevallen wordt een oplossing gevonden met een tijdsverlies van slechts ~27% ten opzichte van de theoretische minimumtijd.
• Grafische Netwerken (Graph-Based):
  • Getest op netwerken die lijken op UAM-corridors.
  • De methode is succesvol zolang de veiligheidsafstand kleiner is dan een geometrische limiet bepaald door de netwerktopologie.
• Vergelijking met Baseline:
  • Vergelijking met een hiërarchische MIP-SOCP methode [15].
  • De voorgestelde methode levert kortere missietijden op.
  • Bij hoge dichtheid ($\phi=10\%$) faalt de baseline (geen haalbare oplossing in SOCP-stadium), terwijl de voorgestelde methode wel een oplossing vindt.

5. Betekenis en Conclusie

Dit artikel presenteert een schaalbare en efficiënte aanpak voor multi-agent coördinatie in omgevingen waar ruimtelijk herplannen niet mogelijk is.

• Significantie: Door het vermijden van discrete volgordevariabelen en het gebruik van een gladde, differentieerbare benadering, kan het algoritme complexe, dichte scenario's oplossen die traditionele methoden niet aankunnen.
• Toepassing: De methode is direct toepasbaar op systemen zoals geautomatiseerde magazijnen, drone-distributie en stedelijke luchtvaart, waar agenten gebonden zijn aan vaste corridors of routes.
• Toekomst: Verdere verbetering van het theoretische karakter van het surrogaatmodel en uitbreiding naar systemen met onzekerheid en online herplanning.

Kortom, de auteurs bewijzen dat directe optimalisatie van tijdstippen via een geavanceerd ADMM-raamwerk superieur is aan hiërarchische benaderingen voor route-beperkte kollisievrije planning.