BOW: Bayesian Optimization over Windows for Motion Planning in Complex Environments

1. Probleemstelling

Bewegingsplanning voor mobiele robots in complexe, rommelige en hoogdimensionale omgevingen is een uitdagend geconstrueerd optimalisatieprobleem. De kernmoeilijkheden omvatten:

• Kinodynamische beperkingen: Robots moeten voldoen aan fysieke limieten (snelheid, versnelling, draaisnelheid) terwijl ze obstakels vermijden.
• Rekenkosten: Het evalueren van objectief functies (bijv. tijd, energie) en veiligheidsbeperkingen over lange planningshorizons is rekenkundig duur, vooral voor systemen met complexe dynamica.
• Afwegingen: Bestaande methoden worstelen vaak met het vinden van een balans tussen optimaliteit, veiligheid en rekenkundige efficiëntie. Traditionele op steekproeven gebaseerde methoden (zoals RRT) kunnen traag zijn, terwijl op roosters gebaseerde of heuristische methoden (zoals DWA) mogelijk geen steekproefficiëntie hebben of vastlopen in lokale minima.
• Eisen voor real-time: Online planning vereist het vinden van haalbare, bijna-optimale besturingssignalen binnen strikte tijdsbudgetten (milliseconden) bij elke tijdstap.

2. Methodologie: De BOW-planner

De auteurs stellen BOW (Bayesian Optimization over Windows) voor, een schaalbaar bewegingsplanningsalgoritme dat de Dynamic Window Approach (DWA) integreert met Constrained Bayesian Optimization (CBO).

Kernconcept

In plaats van de volledige bestuursruimte te doorzoeken of vaste roosters te gebruiken, beperkt BOW de zoektocht tot een dynamisch planningsvenster ($V_d$) dat wordt gedefinieerd door de huidige kinodynamische limieten van de robot (bereikbare snelheden en versnellingen). Binnen dit venster gebruikt het Bayesiaanse optimalisatie om besturingssignalen efficiënt te bemonsteren.

Belangrijke technische componenten

1. Receding Horizon Control (RHC):

   • De planner werkt over een korte voorspellingshorizon ($\Delta$).
   • Er wordt aangenomen dat een constante besturing $u_t$ over de horizon wordt toegepast om de kosten-naar-go-berekening te vereenvoudigen.
   • Het doel is om een kostenfunctie $J$ (afstand tot doel) te minimaliseren, onderworpen aan veiligheidsbeperkingen $c_k$ (obstakelvermijding).

2. Gaussian Process (GP) Surrogaatmodellen:

   • Omdat het evalueren van de werkelijke kosten en beperkingen via simulatie duur is, modelleert BOW de objectief functie $J(u)$ en beperkingsfuncties $c_k(u)$ als Gaussische Processen.
   • De GPs worden getraind op een kleine set initiële steekproeven ($p$) binnen het dynamische venster.

3. Constrained Expected Improvement (CEI):

   • Om de volgende besturing te selecteren, gebruikt BOW een gewijzigde acquisitiefunctie genaamd Constrained Expected Improvement (CEI).
   • Formule: $CEI(u) = EI(u) \times P(\text{haalbaar} | u)$
   • $EI(u)$ balanceert exploratie en exploitatie voor het doel.
   • $P(\text{haalbaar} | u)$ is de kans dat de besturing voldoet aan alle veiligheidsbeperkingen (afgeleid van de GP-posterior van de beperkingen).
   • Hierdoor kan de planner gelijktijdig optimaliseren voor prestaties en veiligheid, waarbij beperkingen tijdens de zoektocht effectief worden behandeld als zachte kansbeperkingen.

4. Algoritme-afloop:

   • Steekproeven $p$ besturingskandidaten uit het dynamische venster.
   • Evalueren van kosten en beperkingen via simulatie.
   • Trainen van GPs op de data.
   • Maximaliseren van CEI om de optimale besturing $u^*_t$ te vinden.
   • Genereren van een traject met het bewegingsmodel (RK4-integratie) en valideren tegen de volledige horizon.
   • Toepassen van de besturing voor een stap $\ell$ (waarbij $\ell \le \Delta$) en herhalen.

3. Belangrijkste bijdragen

• Verbeterde steekproefficiëntie: BOW vindt optimale besturingsstrategieën met aanzienlijk minder evaluaties (bijv. 5–15 steekproeven) in vergelijking met roosterzoektochten of willekeurige steekproeven, wat de rekentijd drastisch verlaagt.
• Veiligheid geïntegreerde optimalisatie: In tegenstelling tot methoden die eerst optimaliseren en later beperkingen controleren, integreert BOW veiligheidsbeperkingen direct in de acquisitiefunctie, waardoor geselecteerde besturingen probabilistisch haalbaar zijn.
• Schaalbaarheid: De methode schaalt effectief naar hoogdimensionale problemen (getest op 6-DOF UAV's) en complexe omgevingen zonder een lineaire explosie in rekentijd.
• Theoretische garanties: Het artikel levert een bewijs van asymptotische convergentie, waarbij wordt aangetoond dat naarmate het aantal steekproeven toeneemt, de geselecteerde besturing convergeert naar de werkelijke optimale oplossing binnen het haalbare gebied.
• Open source: De planner is uitgebracht als een open-source pakket met video's van experimenten in de echte wereld en in simulatie.

4. Experimentele resultaten

De BOW-planner werd geëvalueerd op zowel onbemande grondvoertuigen (UGV's) als onbemande luchtvaartuigen (UAV's) in simulatie en in de echte wereld.

• Benchmarks: Vergelijken met RRT, DWA, MPPI, HRVO en CBF over zes verschillende 2D-omgevingen (inclusief "Bugtrap" en Poisson-bossen) en vijf 3D-UAV-scenario's.
• Prestatiemetingen:
  • Rekentijd: BOW behaalde de snelste plannings tijden, variërend van 10 ms tot 30 ms per horizon, met uitvoeringstijden per stap zo laag als 0,10–0,15 ms. Competitors zoals CBF en MPPI deden er daarentegen honderden tot duizenden milliseconden over.
  • Volledigheid: BOW behield een succespercentage van 100% (perfecte volledigheid) in alle omgevingen, terwijl concurrenten zoals DWA, HRVO en CBF faalden om oplossingen te vinden in specifieke complexe scenario's (bijv. smalle doorgangen of obstakels met hoge dichtheid).
  • Trajectkwaliteit: BOW produceerde concurrerende trajectlengtes en gladheid (matige jerk), en presteerde beter dan RRT op het gebied van gladheid en beter dan MPPI op consistentie.
  • Steekproefficiëntie: In visuele vergelijkingen identificeerde BOW optimale besturingen met slechts ongeveer 15 steekproeven, terwijl DWA een volledige roosterzoektocht vereiste en MPPI uniforme steekproeven vereiste van zowel haalbare als onhaalbare ruimtes.
• Implementatie in de echte wereld: Succesvol ingezet op een differentieelaandrijving UGV en een quadrotor UAV, waarbij robuuste obstakelvermijding met aan boord LiDAR en real-time navigatie in rommelige 3D-ruimtes werd aangetoond.

5. Betekenis en impact

• Praktische toepasbaarheid: BOW overbrugt de kloof tussen theoretische optimaliteit en real-time haalbaarheid, waardoor het geschikt is voor randapparatuur met beperkte middelen (bijv. Raspberry Pi, Jetson Nano) en hoogwaardige robottoepassingen.
• Robuustheid bij onzekerheid: Door probabilistische modellen (GPs) te gebruiken, gaat de planner beter om met onzekerheid in dynamica en omgevingsperceptie dan deterministische heuristieken.
• Toekomstige richtingen: Hoewel BOW uitblinkt als lokale planner, erkennen de auteurs beperkingen in globale planning (bijv. vastlopen in lokale minima in smalle doorgangen). Toekomstig werk richt zich op het integreren van BOW met op bomen gebaseerde zoekalgoritmen om problemen met globale bewegingsplanning op te lossen.

Kortom, vertegenwoordigt de BOW-planner een aanzienlijke vooruitgang in lokale bewegingsplanning door gebruik te maken van geconstrueerde Bayesiaanse optimalisatie om snelle, veilige en steekproefficiënte navigatie te bereiken in complexe, dynamische omgevingen.