Robust Fleet Sizing for Multi-UAV Inspection Missions under Synchronized Replacement Demand

Titel: Robuste Vlootgroottebepaling voor Multi-UAV Inspectiemissies onder Gesynchroniseerde Vervangingsvraag

Auteurs: Vishal Ramesh en Antony Thomas (Robotics Research Center, IIIT Hyderabad)

1. Probleemstelling

Bij inspectiemissies met meerdere onbemande luchtvaartuigen (UAV's) is de eindige batterijduur een fundamentele beperking. Om een continue inspectie van een reeks locaties te garanderen, moeten actieve UAV's worden vervangen door reservevliegtuigen tijdens hun oplaadcycli.

Het bestaande probleem ligt in de onjuiste aannames van huidige methoden voor het bepalen van de benodigde vlootgrootte (aantal reserve UAV's):

• Steady-state aannames: Veel modellen gaan uit van oneindig lopende cycli, wat niet geldt voor eindige missies waarbij elke locatie slechts één keer wordt bezocht.
• Statistische onafhankelijkheid: Andere modellen behandelen vervangingsverzoeken als onafhankelijke gebeurtenissen (vaak gebaseerd op de Erlang-B formule). Dit leidt tot garanties op het niveau van per verzoek (bijv. 99% kans dat een verzoek wordt gehonoreerd), maar faalt op het niveau van de hele missie.

Kerninzicht: De auteurs identificeren een structureel falingsmechanisme. Energiebewuste routing wijst UAV's vergelijkbare routes toe, wat leidt tot gesynchroniseerde batterijuitputting. Hierdoor ontstaan er tijdelijke pieken (bursts) in vervangingsvraag, waarbij meerdere UAV's tegelijkertijd reserve nodig hebben. Zelfs als de gemiddelde capaciteit toereikend is, kan deze gesynchroniseerde vraag de voorraad reserves tijdelijk volledig opraken, wat de missie faalt.

2. Methodologie

De paper introduceert een deterministische, op worst-case analyse gebaseerde aanpak in plaats van probabilistische modellen.

• Systeemmodel:

  • $m$: Aantal actieve UAV's.
  • $R$: Verhouding tussen hersteltijd ($T_{recovery}$) en actieve tijd ($T_{active}$), dus $R = T_{recovery} / T_{active}$.
  • $k$: Aantal reserve UAV's.
  • Doel: Bepaal de minimale $k$ zodat er gedurende de hele missie geen enkel vervangingsverzoek wordt geweigerd.

• Analyse van Gesynchroniseerde Vraag:

  • De auteurs analyseren het "worst-case" scenario waarbij alle $m$ UAV's tegelijkertijd hun batterij leegmaken (perfecte fase-alignatie).
  • Ze tonen aan dat tijdens zo'n cyclus maximaal $m \cdot \lceil R \rceil$ UAV's tegelijkertijd in het herstelproces kunnen zijn.
  • Een kritiek moment treedt op aan de grens van de herstelpijplijn: op het moment dat een nieuwe golf van $m$ UAV's vervanging vraagt, zijn de bestaande reserves al bezet met de vorige golf. Zonder extra buffer ontstaat er een tekort.

• Afgeleide Regel:
  De auteurs leiden een gesloten-formule af voor de voldoende vlootgrootte:
  $$k = m(\lceil R \rceil + 1)$$
  Deze formule voegt een buffer toe van $m$ extra UAV's bovenop de capaciteit die nodig is voor de herstelpijplijn ($m \cdot \lceil R \rceil$). Deze buffer absorbeert de nieuwe golf van vervangingsverzoeken terwijl de pijplijn vol is.

3. Belangrijkste Bijdragen

1. Identificatie van een structureel falingsmechanisme: Het aantonen dat gesynchroniseerde vervangingsgolven (door energiebewuste routing) leiden tot tijdelijke uitputting van reserves, zelfs bij voldoende gemiddelde capaciteit.
2. Gesloten-formule regel: De introductie van de regel $k = m(\lceil R \rceil + 1)$. Deze vereist geen simulatie, geen aannames over kansverdelingen en geen iteratieve berekening. Het is een deterministische garantie voor missie-betrouwbaarheid.
3. Validatie: Uitgebreide Monte Carlo-simulaties over vijf scenario's die aantonen dat traditionele methoden (zoals Erlang-B) falen bij gesynchroniseerde vraag, terwijl de voorgestelde regel 99%+ betrouwbaarheid garandeert.

4. Resultaten

De auteurs hebben de methode getest in 5 scenario's met variërende aantallen UAV's ($m \in [2, 10]$) en hersteltijdverhoudingen ($R \in [0.87, 3.39]$), elk met 1000 simulaties.

• Vergelijking met Erlang-B:
  • De Erlang-B methode (standaard in telecommunicatie, met een doel van 1% blokkering per verzoek) faalt bij complexe scenario's. In het meest veeleisende scenario (S5, $R=3.39$) daalt het succespercentage van de missie naar 69,9%.
  • De voorgestelde regel behaalt 99,8% succes (met een Wilson 95% ondergrens van 99,3%).
• Kosten-effectiviteit:
  • Om de betrouwbaarheid van 69,9% naar 99,8% te tillen, zijn slechts 4 extra UAV's nodig (van 46 naar 50 in scenario S5). Dit is een relatief kleine toename (ongeveer 7% van de vloot) voor een enorme sprong in betrouwbaarheid.
• Falenpatroon:
  • Bij de traditionele methoden treden falen niet willekeurig op, maar geconcentreerd in de top 10% van de tijdsvensters met de hoogste vraag (gesynchroniseerde golven).
  • De voorgestelde regel elimineert deze uitputtingsgebeurtenissen volledig.
• Robuustheid: De regel blijft robuust bij variaties in windsnelheid (tot een variatiecoëfficiënt van 0,30), aangezien deze gebaseerd is op worst-case analyse in plaats van gemiddelden.

5. Betekenis en Conclusie

Deze paper biedt een cruciale oplossing voor de planning van Multi-UAV inspectiemissies.

• Verschuiving in paradigma: Het verlegt de focus van "per-verzoek betrouwbaarheid" naar "missie-betrouwbaarheid". Een lage kans op falen per verzoek is onvoldoende bij een reeks handover-acties; de kans op geen enkel falen over de hele missie is wat telt.
• Praktische toepasbaarheid: De regel is eenvoudig te berekenen op basis van bekende parameters ($m$ en $R$) en vereist geen complexe simulaties tijdens de planning.
• Robuuste optimalisatie: Door te plannen voor het ergste geval (gesynchroniseerde uitputting) in plaats van gemiddelden, wordt een garantie gegeven dat de missie voltooid kan worden, ongeacht de timing van de batterijuitputting.

Concluderend stelt de paper dat voor eindige inspectiemissies met energiebewuste routing, de traditionele statistische modellen ontoereikend zijn. De voorgestelde bufferregel ($m(\lceil R \rceil + 1)$) is een noodzakelijke en efficiënte maatregel om mission-critical betrouwbaarheid te garanderen tegen een minimale meerkost.