💻 computer science

Diffusion for Long-Horizon Multi-Robot Path Planning in Human-Shared Environments

Dit artikel introduceert Multi-Robot Rolling Diffusion (MRRD), een nieuw framework dat realtijdige, lange-termijn padplanning mogelijk maakt voor grote robotteams in drukke, door mensen gedeelde omgevingen door rolling-horizon schema's, geparallelliseerde diffusie-inferentie en conflictresolutie te combineren om bestaande baselines op het gebied van veiligheid en missiesucces aanzienlijk te overtreffen.

Oorspronkelijke auteurs: Vaibhav Sanjay, Yorai Shaoul, Jiaoyang Li

Gepubliceerd 2026-07-14

📖 4 min leestijd☕ Koffiepauze-leesvoer

CC BY 4.0

Oorspronkelijke auteurs: Vaibhav Sanjay, Yorai Shaoul, Jiaoyang Li

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 een druk stadsplein voor waar een team van 15 robotvrienden van de ene naar de andere kant moet steken, maar het plein staat vol met echte mensen die rondlopen. De robots moeten samen bewegen zonder tegen elkaar op te botsen of tegen de mensen aan te lopen, en ze moeten er natuurlijk uitzien terwijl ze dat doen. Dit is de uitdaging die het artikel aanpakt met een nieuw systeem genaamd Multi-Robot Rolling Diffusion (MRRD).

Denk aan de oude manier waarop robots hun paden planten, als een rigide marsband. Ze bepaalden de hele route van begin tot eind voordat ze ook maar één stap zetten, en ze waren gedwongen om te marcheren op een snelheid die paste bij een vooraf ingestelde liedjeslengte, ongeacht hoe ver ze moesten gaan. Als het doel ver weg was, moesten ze gevaarlijk snel sprinten; als het dichtbij was, moesten ze onhandig traag schuifelen. Het artikel betoogt dat deze "fixed-time" benadering een grote tekortkoming is, omdat het leidt tot grillige, onveilige bewegingen en faalt wanneer de menigte te dik wordt.

MRRD verandert de regels door te fungeren als een groep vrienden die door een drukke markt loopt. In plaats van de hele route van de dag in één keer te plannen, nemen ze korte, rollende stappen. Ze kijken ongeveer 3,2 seconden vooruit in de simulatie, beslissen waar ze als volgende heen gaan, zetten een paar stappen (ongeveer 1,6 seconden) en kijken dan direct weer vooruit om bij te sturen. Deze "rollende" benadering laat hen op een natuurlijke manier versnellen of vertragen op basis van hoe ver het doel is en hoe druk het pad op dit moment is.

Om ervoor te zorgen dat de 15 robots niet over elkaar struikelen, gebruikt MRRD een slim "verkeersregelaar"-systeem genaamd Conflict-Based Search. Stel je voor dat de robots een spel spelen waarbij ze allemaal tegelijkertijd proberen hun paden te tekenen. Als twee robots tegelijkertijd dezelfde plek willen bezetten, pauzeert het systeem, tekent een tijdelijke "niet betreden"-bubbel rond die plek en vraagt de robots om hun paden opnieuw te tekenen om de plek te vermijden. Het artikel laat zien dat deze methode de robots in staat stelt om deze conflicten in realtime op te lossen, zelfs met 15 van hen op het scherm.

De robots leren ook te bewegen als mensen door een enorme dataset van 20.000 echte menselijke wandelpaden te bestuderen. Ze gebruiken een "diffusie"-model, wat lijkt op een creatieve kunstenaar die begint met een wazige, ruizige schets en deze langzaam opschoont totdat het een perfecte, vloeiende wandeling wordt. Het artikel suggereert dat door een speciaal "urgentie"-signaal aan deze kunstenaar toe te voegen, de robots kunnen leren om stevig door te lopen wanneer ze ver van hun doel zijn en af te remmen wanneer ze dichtbij zijn, waarmee het "fixed-time" probleem wordt opgelgeslagen.

In de simulaties van het artikel bleek MRRD een uitmuntende prestatie te leveren. Bij tests met maximaal 15 robots in lege ruimtes bereikte MRRD een robot-robot botsingspercentage van 0,00, wat betekent dat de robots in die specifieke scenario's nooit tegen elkaar aan botsten. In contrast hiermee hadden andere methoden moeite, waarbij de botsingspercentages voor sommige concurrenten in soortgelijke tests opliepen tot wel 0,98 (bijna elke test mislukte). MRRD hield ook de robot-mens botsingen extreem laag, op 0,08 in de 15-robot lege kaart test, terwijl andere methoden in specifieke scenario's zoals de 12-robot lege kaart percentages van 1,00 lieten zien.

Het systeem was ook ongelooflijk snel. In de drukste test met 15 robots in een lege kaart was de totale plannings-tijd van MRRD (de som van alle rollende stappen) slechts 8,8 seconden. Dit is ongeveer 7 keer sneller dan de op diffusie gebaseerde methode die het dichtst in de buurt kwam, die 60,2 seconden nodig had. De robots bewogen ook veel vloeiender, met acceleratieprofielen die 5 tot 8 keer lager waren dan de schokkerige bewegingen van de andere methoden.

Het artikel concludeert dat hoewel deze methode briljant werkt in deze gesimuleerde omgevingen, het een specifieke oplossing is voor dit type probleem. Het suggereert dat toekomstig werk kan inhouden dat het systeem nog robuuster wordt gemaakt door menselijke voorspelling direct in het tekenproces te integreren, maar voor nu is MRRD een zeer effectieve manier om grote teams van robots veilig en sociaal door menselijke menigten te laten bewegen.

Technische Samenvatting: Multi-Robot Rolling Diffusion (MRRD)

Probleemdefinitie

Het artikel behandelt de uitdaging van multi-robot padplanning in door mensen gedeelde omgevingen. Het kerndoel is om een team van robots ( $N$ ) te coördineren bij het navigeren door een 2D-werkruimte die statische obstakels, andere robots en dynamische mensen ( $M$ ) bevat. Het systeem moet drie gelijktijdige doelen bereiken:

Botsingsvermijding: Het voorkomen van robot-robot, robot-mens en robot-obstakel botsingen.
Sociale Bewustwording: Het genereren van paden die voorspelbaar en sociaal acceptabel zijn, waarbij menselijke bewegingspatronen worden nagebootst in plaats van louter geometrische kortste paden.
Schaalbaarheid en Real-time Prestaties: Efficiënt opereren voor grote robotteams (tot 15) in real-time, waarbij wordt geadapteerd aan variërende afstanden en crowd-densiteiten.

De auteurs identificeren een kritieke beperking in bestaande generatieve planners (bijv. CoBL-Diffusion): het "fixed-time probleem." Traditionele diffusiemodellen genereren paden met een rigide, vaste duur, ongeacht de afstand tot het doel. Dit dwingt tot grillige snelheden (gevaarlijk hoog voor verre doelen of onnatuurlijk traag voor nabije doelen) en belemmert de adaptiviteit in dynamische scenario's met een lange horizon.

Methodologie: Multi-Robot Rolling Diffusion (MRRD)

Het voorgestelde framework, MRRD, is een drielagen-architectuur die een rolling-horizon schema, Conflict-Based Search (CBS) en een diffusie-gebaseerde single-robot planner integreert.

1. Rolling-Horizon Planning (Bovenste niveau)

In plaats van één enkel, globaal pad van begin tot eind te genereren, gebruikt MRRD een rolling-horizon benadering (Algoritme 1).

Iteratief Proces: Het systeem plant korte padsegmenten van lengte $H$ (planning horizon) en voert slechts $K$ stappen uit (execution horizon, waarbij $K < H$ ).
Adaptiviteit: Na het uitvoeren van $K$ stappen wordt de nieuwe positie van de robot het startpunt voor de volgende iteratie. Dit stelt de planner in staat om continu te reageren op veranderende menselijke voorspellingen en robotposities.
Menselijke Voorspelling: Het systeem maakt gebruik van een perfecte voorspellingsfunctie voor menselijke paden over de horizon $H$ , waardoor de noodzaak voor langetermijnvoorspelling van menselijke trajecten wordt vermeden.

2. Multi-Robot Coördinatie (Middelste niveau)

Om robot-robot botsingen binnen de rolling horizon op te lossen, past MRRD Conflict-Based Search (CBS) aan (Algoritme 2).

Parallelle Generatie: In tegen tegenstelling tot sequentiële planners, genereert MRRD initiële padsegmenten voor alle $N$ robots parallel met behulp van het diffusiemodel.
Constraint Tree: Als er botsingen tussen robots worden gedetecteerd, splitst het algoritme het probleem op in kindnodes. Het legt sferische restricties op aan specifieke robots op specifieke tijdstippen en plant hun paden opnieuw om deze beperkte regio's te vermijden.
Scheiding van Zorgen: Robot-mens interacties worden afgehandeld door de geleerde priors van het diffusiemodel, terwijl robot-robot interacties expliciet worden opgelost via de CBS-constraint tree.

3. Single-Robot Diffusion Planner (Onderste niveau)

De kerninnovatie ligt in de architectuur van het diffusiemodel en het conditioneringsmechanisme (Fig. 1).

Urgentie-gebaseerde Temporele Conditionering: Om het "fixed-time probleem" op te lossen, is het model geconditioneerd op een urgentie-term ( $u_i$ $u_{i}$ ) die het aantal waypoints naar het doel vertegenwoordigt, in plaats van een vaste tijdsduur.
- Het model is getraind op menselijke loopdata waarbij de doelpositie en urgentie worden gesampled om het model te leren de snelheid aan te passen op basis van afstand.
- Tijdens inferentie genereert het model een batch paden met variërende urgentiewaarden. Het systeem selecteert het pad dat haalbaar is (geen botsingen) en de hoogste snelheid (laagste $u_i$ ) heeft die passend is voor de huidige context.
Guidance Termen: Het denoising proces wordt gestuurd door gradiënten van drie kostenfuncties:
1. Constraint Kosten: Het bestraffen van schendingen van door CBS opgelegde sferische restricties.
2. Menselijke Afstandskosten: Het bestraffen van nabijheid tot mensen met behulp van een persoonlijke ruimte-model (core en close radii) met rank-gewogen straffen voor dichte menigten.
3. Obstakel Kosten: Het bestraffen van penetratie in statische obstakels met behulp van Signed Distance Fields (SDF).
Architectuur: Een temporele U-Net verwerkt het ruisige pad, de doel-embedding en de urgentie-embedding om het pad iteratief te denoisen.

Belangrijkste Bijdragen

MRRD Framework: Een nieuw 3-lagen planner die rolling-horizon executie, CBS-gebaseerde botsingsresolutie en diffusie-gebaseerde padgeneratie combineert.
Urgentie Conditionering: Een mechanisme om diffusiemodellen te conditioneren op "tijd-tot-doel" (urgentie) in plaats van een vaste duur, wat adaptieve snelheidsprofielen mogelijk maakt en het fixed-time probleem oplost.
Schaalbare Parallelle Inferentie: Implementatie van geparalleleerde diffusie-inferentie binnen een CBS-framework, waardoor het systeem kan schalen naar grote robotteams (15 robots) in real-time.
Gedifferentieerde Guidance: Een strategie voor guidance die sociale bewustwording (behandeld door de diffusie prior en de menselijke kosten) scheidt van inter-robot coördinatie (behandeld door CBS-restricties).

Experimentele Resultaten

De auteurs evalueerden MRRD in gesimuleerde omgevingen met variërende robotaantallen (6–15), menselijke menigten en statische obstakels, waarbij het werd vergeleken met CoBL-Diffusion (diffusie-gebaseerd) en Navi-STAR (RL-gebaseerd).

Veiligheid en Succesratio's:
- MRRD behaalde een robot-robot botsingspercentage van 0% in alle scenario's, terwijl baselines percentages tot 0,98 (Navi-STAR) en 0,28 (CoBL-Diffusion) vertoonden in scenario's met 15 robots.
- MRRD behield een succespercentage van 92% met 15 robots, terwijl CoBL-Diffusion daalde naar 32% en Navi-STAR naar 0%.
- De robot-mens botsingspercentages waren aanzienlijk lager voor MRRD (0,08) vergeleken met de baselines (0,22–1,00).
Efficiëntie:
- MRRD demonstreerde superieure planningstijd. Voor 15 robots duurde MRRD 8,8 seconden om te plannen, vergeleken met 60,2 seconden voor CoBL-Diffusion en 17,3 seconden voor Navi-STAR.
- De geparallelliseerde aanpak was 4x sneller dan een niet-geparallelliseerde versie van MRRD.
Trajectkwaliteit:
- MRRD produceerde gladdere trajecten met gemiddelde acceleratieprofielen die 5 tot 8 keer lager waren dan die van CoBL-Diffusion, wat wijst op meer mensachtige, vloeiende bewegingen.
- De nauwkeurigheid bij het bereiken van het doel was aanzienlijk beter (0,37m fout vs. 1,46m voor CoBL-Diffusion).
Obstakel Navigatie:
- In complexe kaarten met statische obstakels behield MRRD een robot-robot botsingspercentage van 0,00 en een succespercentage van 56% in het dichtste scenario, terwijl CoBL-Diffusion volledig faalde (0% succes).

Betekenis en Claims

Het artikel claimt dat MRRD erin slaagt de kloof te overbruggen tussen sociaal bewuste navigatie en schaalbare multi-robot coördinatie. Door af te stappen van rigide, vastgestelde duur-padgeneratie, stelt de methode robots in staat hun snelheid dynamisch aan de omgeving aan te passen, een cruciale factor voor veiligheid in door mensen gedeelde ruimtes.

De auteurs benadrukken dat hun aanpak:

Effectief schaalt naar grote teams (tot 15 robots) in real-time, een capaciteit die ontbreekt bij eerdere learning-gebaseerde benchmarks.
Interactietypes ontkoppelt, waarbij diffusie wordt gebruikt voor sociale normen en CBS voor harde botsingsrestricties, wat resulteert in robuuste prestaties zonder veiligheid op te offeren.
Bestaande baselines overtreft in zowel veiligheidsmetrieken (botsingspercentages) als missiesucces, terwijl het kwalitatief gladdere en meer mensachtige trajecten genereert.

Het werk concludeert dat hoewel toekomstige verbeteringen onder meer invariantie in het denoisingproces en geïntegreerde menselijke voorspellingsmodules kunnen omvatten, MRRD momenteel een significante stap voorwaarts vertegenwoordigt bij het inzetten van grote robotteams in dynamische, door mensen bevolkte omgevingen.