Technische Samenvatting: Multi-UAV Padplanning in 3D gebaseerd op APF-MADDPG

1. Probleemstelling

Het artikel behandelt de uitdaging van multi-UAV padplanning in onbekende 3D-omgevingen. Dit probleem wordt gekenmerkt door een hoogdimensionale actieruimte, strikte botsingsvermijdingsbeperkingen (zowel tussen UAV's als met obstakels) en een computationeel karakter dat NP-hard is.

Specifieke geïdentificeerde uitdagingen zijn:

• Collaboratie versus Individualiteit: In tegenstelling tot single-UAV planning, die zich richt op individuele optimaliteit, vereist multi-UAV planning het balanceren van samenwerking, botsingsvermijding en simultane missievoltooiing (aggregatie).
• Beperkingen van Traditionele Methoden: Geometrische methoden (bijv. Voronoi) worstelen met dynamische veranderingen; Artificial Potential Field (APF) methoden lijden aan lokale minima; en heuristische algoritmen (bijv. Genetische Algoritmen, PSO) kampen vaak met trage convergentie of lokale optimalisatieproblemen in hoogdimensionale ruimtes.
• Beperkingen van Bestaande RL-benaderingen: Hoewel Deep Deterministic Policy Gradient (DDPG) werkt voor enkelvoudige agenten, negeert het de strategische verschillen tussen agenten, wat leidt tot botsingen. Multi-Agent DDPG (MADDPG) adresseert samenwerking, maar lijdt vaak aan sparse rewards (ijle beloningen), waardoor het ontwerp van de beloningsfunctie moeilijk is en de convergentie traag verloopt in complexe omgevingen.

2. Methodologie

De auteurs stellen een nieuw algoritme voor, APF-MADDPG, dat het Multi-Agent Deep Deterministic Policy Gradient (MADDPG) raamwerk integreert met een verbeterde beloningsmechanisme gebaseerd op het Artificial Potential Field (APF).

2.1 Probleemmodellering

• Missiemodel: Gedefinieerd als een aggregatiemissie waarbij $N$ UAV's vanuit verspreide locaties starten en tegelijkertijd een gemeenschappelijk doelgebied moeten bereiken terwijl ze dreigzones, no-fly zones en obstakels vermijden.
• Bewegingsmodel: Een 3D kinematisch model wordt gebruikt waarbij UAV's lineaire versnelling, pitch hoekversnelling en yaw hoekversnelling aansturen. Beperkingen worden toegepast op snelheid, versnelling en hoeken.
• Obstakelmodel: Obstakels worden gemodelleerd als convexe lichamen (sferen of cilinders) gedefinieerd door geometrische parameters.
• Speltheoretische Formulering: Het probleem wordt geformuleerd als een Partially Observable Markov Game (POMG).
  • Toestandsruimte ($S_i$): Omvat positie, snelheid, pitch en yaw hoeken.
  • Actieruimte ($A_i$): Lineaire versnelling, pitch hoekversnelling en yaw hoekversnelling.
  • Observatieruimte ($o_i$): Lokale observaties inclusief de eigen staat van de UAV, relatieve staten van andere UAV's en relatieve posities van obstakels.

2.2 Kernalgoritme: APF-MADDPG

Het algoritme maakt gebruik van een distributed execution and centralized training raamwerk.

1. Hiërarchisch Trainingsmechanisme: Er wordt een twee-laagse structuur geïntroduceerd:
   • Padplanningslaag: Elke UAV heeft een onafhankelijk actor-critic netwerk. De actor neemt lokale observaties en genereert acties met exploratie-ruis.
   • Actie-uitvoeringslaag: UAV's voeren acties uit in de omgeving, wat nieuwe observaties en beloningen genereert.
2. Dense Reward Function (Kerninnovatie): Om de problemen met sparse rewards te overwinnen, ontwerpen de auteurs een samengestelde beloningsfunctie ($R_{sum}$) gebaseerd op APF-principes:
   • Aantrekking ($R_{ut}$): Stimuleert beweging naar het doel met behulp van een exponentiële vervalfunctie gebaseerd op de Euclidische afstand.
   • Afstoting ($R_{uu}$): Bestraft nabijheid tussen UAV's om botsingen te voorkomen.
   • Obstakelafstoting ($R_{uo}$): Bestraft nabijheid tot obstakels met behulp van een exponentiële functie.
   • Departure Reward ($R_{depart}$): Beloont progressie richting het doel door het verschil te berekenen tussen de vorige afstand en de huidige afstand tot het doel ($d(p_{last}, p_{target}) - d(p_{now}, p_{target})$). Dit mechanisme is ontworpen om het probleem van onbereikbare doelen in APF op te lossen en te voorkomen dat de agent rond het doel blijft dwalen om maximale beloningen te accumuleren zonder het doel daadwerkelijk te bereiken.
   • Totale Beloning: $R_{sum} = w_1R_{ut} + w_2R_{uu} + w_3R_{uo} + w_4R_{depart}$.

2.3 Trainingsproces

Het algoritme gebruikt de standaard MADDPG update-regels met target netwerken voor stabiliteit.

• Critic Update: Minimaliseert de loss tussen de voorspelde Q-waarde en de target waarde ($y_i$), die de onmiddellijke beloning en de gedisconteerde toekomstige Q-waarde van de target netwerken bevat.
• Actor Update: Maximaliseert de verwachte return met behulp van de policy gradient.
• Soft Updates: De parameters van de target netwerken worden bijgewerkt via soft updates ($\tau \ll 1$) om de trainingsstabiliteit te waarborgen.

3. Belangrijkste Bijdragen

Het artikel claimt expliciet twee primaire bijdragen:

1. Dense Reward Function: De integratie van een op APF gebaseerde dense reward function in het MADDPG raamwerk. Dit adresseert de problemen van sparse rewards en trage convergentie die worden gevonden bij traditionele multi-agent reinforcement learning voor padplanning.
2. Hiërarchisch Trainingsmechanisme: De vestiging van een hiërarchische deep reinforcement learning structuur bestaande uit een padplanningslaag en een actie-uitvoeringslaag om optimale strategieën efficiënt te trainen.

4. Experimentele Resultaten

De voorgestelde methode werd geëvalueerd in een 3D-simulatieomgeving (10 km $\times$ 10 km $\times$ 10 km) met drie UAV's en drie obstakels (twee sferen, één cilinder). Het werd vergeleken met MADDPG (met gebruik van traditionele sparse rewards) en ILDDPG (Independent Learner DDPG).

• Convergentiesnelheid: De episode reward curves (Fig. 4) laten zien dat APF-MADDPG aanzienlijk sneller convergeert dan zowel MADDPG als ILDDPG.
• Kwaliteit van het Beleid:
  • ILDDPG: Faalde in het vermijden van obstakels in de simulatie (UAV 1 en 2 botsten), waardoor het ongeschikt is voor dit multi-agent scenario.
  • MADDPG: Vermeed obstakels succesvol, maar resulteerde in een langere totale padlengte.
  • APF-MADDPG: Vermeed alle obstakels succesvol en bereikte de kortste totale padlengte.
• Vergelijking Padlengte:
  • MADDPG Totale Lengte: 25.9426 km
  • APF-MADDPG Totale Lengte: 24.7056 km
  • Het APF-MADDPG algoritme reduceerde de totale padlengte vergeleken met de standaard MADDPG.

5. Betekenis en Claims

Het artikel concludeert dat het APF-MADDPG algoritme zowel ILDDPG als standaard MADDPG overtreft op het gebied van:

• Efficiëntie van Beleidsleren: Snellere convergentie naar een optimale strategie.
• Optimaliteit van Padplanning: Het genereren van kortere, efficiëntere paden.
• Veiligheid: Effectief het vermijden van botsingen met obstakels en andere UAV's in een 3D-omgeving.

De auteurs beweren dat de combinatie van de op APF gebaseerde dense reward en het hiërarchische trainingsmechanisme effectief de uitdagingen van sparse rewards en lokale minima in 3D multi-UAV padplanning oplost, en een robuuste oplossing biedt voor collaboratieve missies in onbekende omgevingen.