Online path planning for kinematic-constrained UAVs in a dynamic environment based on a Differential Evolution algorithm

Technische Samenvatting: Online Padplanning voor Kinematisch Beperkte UAV's in Dynamische Omgevingen

Probleemstelling
Dit onderzoek behandelt de uitdaging van online padplanning voor vaste vleugel Unmanned Aerial Vehicles (UAV's) die opereren in dynamische omgevingen. In tegenstelling tot quadrotors worden vaste vleugel UAV's geconfronteerd met unieke kinematische beperkingen, waaronder maximale kromming, minimale draaicirkel en specifieke oriëntatie-eisen (yaw- en pitchhoeken). De kern van het probleem is het genereren van een haalbaar, botsingsvrij pad in real-time dat aan deze bewegingsbeperkingen voldoet, terwijl er genavigeerd wordt door omgevingen met zowel statische als dynamische obstakels. Het systeem moet opereren binnen een beperkt detectiebereik ($R_{view}$), waarbij de posities en snelheidsvectoren van obstakels op discrete herplanningsintervallen ($t_s$) worden gedetecteerd, en moet waarborgen dat de UAV binnen de vrije ruimte ($\Omega_{free}$) blijft en no-fly zones en potentiële botsingen vermijdt.

Methodologie
De voorgestelde oplossing integreert een Non-Uniform Rational B-Spline (NURBS) padrepresentatie met een Differential Evolution (DE) optimalisatiealgoritme, versterkt door concepten uit de Velocity Obstacle (VO) benadering.

• Padrepresentatie: Het pad wordt gemodelleerd als een NURBS-curve gedefinieerd door controlepunten ($P$) en gewichten ($w$). Om aan de oriëntatiebeperkingen aan het begin en einde van het pad te voldoen, worden drie collinear punten toegevoegd aan de eerste en laatste controlepunten, geschaald door factoren $\lambda_1$ en $\lambda_2$.
• Optimalisatiestrategie: In tegenstelling tot eerdere offline benaderingen die de curveparameters direct optimaliseerden, optimaliseert deze online methode de variatie van deze parameters ($\Delta\chi = [\Delta P, \Delta w, \lambda_1, \lambda_2]$ ten opzichte van een initieel haalbaar pad. Deze strategie beoogt de convergentie te versnellen.
• Doelfunctie: De optimalisatie minimaliseert de vluchtenergiekosten, gedefinieerd als de padlengte (uitgaande van een constante snelheid en het negeren van wind), onderhevig aan:
  1. Kinematische beperkingen: De kromming $\kappa(s)$ mag de maximale toegestane kromming ($\kappa_{max}$) niet overschrijden.
  2. Obstakelvermijding: De positie van de UAV $p_u$ mag niet in beperkte zones ($\Omega_{obs}$) komen.
  3. Dynamische botsingsvermijding: De relatieve snelheid van de UAV ten opzichte van obstakels mag niet binnen de Velocity Obstacle-kegel ($VO^{\tau}_{o_i/u}$) vallen voor een voorspellingshorizon $\tau$. Deze beperking wordt toegepast op alle gedetecteerde obstakels ($N_{obs}$) binnen het detectiebereik.
• Algoritme: LSHADE-COP (Linear-Success-History Based Adaptive Differential Evolution for Constrained Optimization Problems) wordt ingezet om het beperkte optimalisatieprobleem op elk herplanningsinterval op te lossen.
• Controle-implementatie: Zodra een haalbare NURBS-curve is gegenereerd, wordt deze gekoppeld aan een vectorveld-controleswet (gebaseerd op eerder werk [10]) om de UAV langs het pad te leiden.

Belangrijkste Bijdragen

1. Online Deliberatieve Planning: De auteurs hebben hun eerdere offline DE-NURBS framework getransformeerd naar een online planner die in staat is om dynamische obstakels te verwerken en te herplannen met intervallen van ongeveer $t_s \approx 0,1$ seconden.
2. Integratie van Velocity Obstacles: Een nieuwe beperkingsfunctie die de Velocity Obstacle-benadering incorporeert, is direct in het DE-optimalisatieproces ingebed. Dit stelt het algoritme in staat om toekomstige botsingen met bewegende obstakels te bestraffen tijdens de padgeneratiefase, in plaats van uitsluitend te vertrouwen op een reactieve lokale planner.
3. Optimalisatie van Parameter-variatie: Door de variatie van NURBS-parameters te optimaliseren in plaats van de parameters zelf, bereikt de methode een snellere convergentie die geschikt is voor real-time toepassingen.
4. Haalbaarheid in 2D: Het systeem genereert succesvol paden voor vaste vleugel UAV's in 2D dynamische omgevingen, waarbij een constante hoogte wordt behouden en aan de kinematische limieten wordt voldaan.

Resultaten
Simulatieresultaten laten zien dat de voorgestelde planner UAV's succesvol door drukke omgevingen met bewegende obstakels navigeert.

• Prestaties: De online planner wordt gerapporteerd ongeveer 12.000 keer sneller is dan de eerdere offline planner [5] van de auteurs.
• Veiligheid: De inclusie van de Velocity Obstacle-beperking maakt veilige navigatie mogelijk in scenario's waar een herplanningsbenadering zonder deze beperking zou falen of tot botsingen zou leiden.
• Efficiëntie: Het systeem kan alleen de noodzakelijke secties van een initiële NURBS-curve wijzigen om dynamische obstakels te vermijden, in plaats van het gehele missiepad vanaf nul opnieuw te plannen.
• Visuele Validatie: Momentopnames van het deliberatieve planningsproces (Fig. 1) en aanvullend videomateriaal bevestigen het vermogen van de planner om vloeiende, haalbare curven te genereren die dynamische dreigingen vermijden.

Betekenis en Claims
Het artikel beweert een haalbare basis te bieden voor online padplanning voor kinematisch beperkte UAV's in dynamische settings. De auteurs benadrukken dat hun aanpak het overtollige gebruik van extra smoothing-stappen voorkomt die vaak nodig zijn bij andere fixed-wing planners. Hoewel de huidige studie beperkt is tot 2D-scenario's met een constante hoogte, geven de auteurs aan dat de methode ontworpen is om uitbreidbaar te zijn naar driedimensionale (3D) omgevingen. Het werk wordt gepresenteerd als een stap richting het oplossen van het uitdagende openstaande probleem van het plannen van beweging om dynamische obstakels te vermijden zonder de UAV in lokale minima of onhaalbare situaties te leiden, een beperking die bij eenvoudigere lokale planner-benaderingen wordt opgemerkt.