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

1. Problemstellung

Das Paper adressiert das kritische Problem der Dimensionierung von Ersatzdrohnen-Flotten für Multi-UAV-Inspektionsmissionen mit endlichem Zeithorizont. In solchen Szenarien (z. B. Infrastrukturinspektion, Präzisionslandwirtschaft) müssen Drohnen nach dem Erschöpfen ihrer Batterien zur Basis zurückkehren, um aufgeladen zu werden, und werden sofort durch Ersatzdrohnen aus einem gemeinsamen Pool ersetzt.

Das zentrale Problem besteht darin, dass bestehende Ansätze zwei fehlerhafte Annahmen treffen:

• Stationärer Betrieb: Viele Modelle gehen von einem unendlichen, zyklischen Betrieb aus, was für einmalige Inspektionsmissionen nicht zutrifft.
• Statistische Unabhängigkeit: Herkömmliche Warteschlangenmodelle (wie Erlang-B) behandeln Ersatzanfragen als unabhängige, zufällige Ereignisse.

Der Autor identifiziert jedoch einen strukturellen Fehlermodus: Durch energiebewusstes Routing erhalten Drohnen ähnliche Arbeitslasten und Flugstrecken. Dies führt zu einer synchronisierten Batterieentleerung. Die Ersatzanfragen treten daher nicht gleichmäßig verteilt auf, sondern in zeitlich gebündelten Wellen (Bursts). Selbst wenn die durchschnittliche Kapazität ausreicht, kann der Ersatzpool während dieser synchronisierten Spitzen erschöpft werden, was zum Missionsversagen führt.

2. Methodik und Herleitung der Lösung

Die Autoren entwickeln einen deterministischen Ansatz, der auf einer Worst-Case-Analyse der Synchronisation basiert, anstatt auf probabilistischen Annahmen.

• Systemmodell:
  • $m$: Anzahl der aktiven Drohnen.
  • $R$: Verhältnis der Erholungszeit zur aktiven Flugzeit ($R = T_{recovery} / T_{active}$).
  • $k$: Anzahl der benötigten Ersatzdrohnen.
• Analyse der Worst-Case-Synchronisation:
  • Unter Worst-Case-Bedingungen (perfekte Phasenausrichtung) können alle $m$ Drohnen gleichzeitig ihre Batterien entleeren.
  • Da die Erholungszeit $R$ oft größer als 1 ist, befinden sich mehrere Wellen von Drohnen gleichzeitig im Erholungsprozess.
  • Proposition 1: Unter Worst-Case-Bedingungen können bis zu $m \cdot \lceil R \rceil$ Drohnen gleichzeitig in der Erholung sein.
• Der „Boundary-Burst"-Mechanismus:
  • Ein kritischer Fehler tritt genau am Ende des Erholungszyklus auf: Wenn die $m \cdot \lceil R \rceil$ Ersatzdrohnen bereits in der Erholung sind und gleichzeitig die nächste Welle von $m$ aktiven Drohnen einen Ersatz benötigt, ist der Pool leer.
  • Das System benötigt also nicht nur die Drohnen für den Erholungsprozess, sondern einen zusätzlichen Puffer für die ankommende Welle.
• Die abgeleitete Regel:
  Die Autoren leiten eine geschlossene Formel für die ausreichende Flottengröße ab:
  $$k = m(\lceil R \rceil + 1)$$
  Diese Regel fügt einen Puffer von $m$ zusätzlichen Drohnen hinzu, um die Worst-Case-Synchronisation an den Grenzen der Erholungszyklen zu absorbieren.

3. Hauptbeiträge

1. Identifikation des strukturellen Versagens: Nachweis, dass energiebewusstes Routing in endlichen Missionen zu synchronisierten Ersatzanfragen führt, was herkömmliche stochastische Modelle untergräbt.
2. Geschlossene Formel: Entwicklung der Regel $k = m(\lceil R \rceil + 1)$, die keine Simulationen, Verteilungsannahmen oder iterative Berechnungen erfordert. Sie garantiert die Missionszuverlässigkeit auch bei gleichzeitiger Entleerung aller Drohnen.
3. Validierung: Umfassende Monte-Carlo-Simulationen über fünf Szenarien, die die Überlegenheit der neuen Regel gegenüber etablierten Methoden (Naive, Duty-Cycle, Erlang-B) belegen.

4. Experimentelle Ergebnisse

Die Validierung erfolgte in fünf Szenarien mit variierenden Parametern ($m \in [2, 10]$, $R \in [0.87, 3.39]$) und 1000 Trials pro Szenario.

• Vergleich der Methoden:
  • Naive ($k=m$) und Duty-Cycle ($k=m\lceil R \rceil$): Versagen bei höheren $R$-Werten (z. B. $R > 1$) aufgrund fehlender Puffer für synchronisierte Wellen.
  • Erlang-B (Standard-Warteschlangenmodell): Bietet zwar eine Blockierwahrscheinlichkeit von $\epsilon = 0.01$ pro Anfrage, führt aber bei vielen Handovers zu einem drastischen Abfall der Missionszuverlässigkeit. Im schwierigsten Szenario ($R=3.39$) sank der Erfolg auf 69,9 %.
  • Vorgeschlagene Regel: Erreichte in allen Szenarien eine Erfolgsrate von 99,8 % (untere 95%-Konfidenzgrenze 99,3 %).
• Kosten-Nutzen-Analyse:
  • Im anspruchsvollsten Szenario benötigte die vorgeschlagene Regel nur 4 zusätzliche Drohnen (von 46 auf 50) im Vergleich zur Erlang-B-Methode, um die Zuverlässigkeit von ~70 % auf ~99,8 % zu steigern.
• Robustheit: Die Regel bleibt auch bei variierenden Windbedingungen (Variationskoeffizient bis $CV=0.30$) stabil, da sie auf Worst-Case-Annahmen und nicht auf spezifischen Varianzmodellen basiert.
• Fehlerkonzentration: 95 % der Ausfälle bei der Erlang-B-Methode traten in den Top-10 %-Zeitfenstern mit der höchsten Nachfrage auf, was die Hypothese der synchronisierten „Bursts" bestätigt.

5. Bedeutung und Schlussfolgerung

Das Paper liefert einen paradigmatischen Wechsel in der Planung von Multi-UAV-Systemen:

• Von Stochastisch zu Deterministisch: Es zeigt, dass für endliche Missionen mit bekannten Flugprofilen deterministische Worst-Case-Garantien robuster sind als stochastische Modelle, die Unabhängigkeit voraussetzen.
• Missionszuverlässigkeit vs. Einzelanfrage: Es wird demonstriert, dass eine hohe Zuverlässigkeit pro Einzelanfrage (per-request) nicht automatisch zu einer hohen Missionszuverlässigkeit führt, wenn die Anzahl der Handovers groß ist und Fehler sich kumulieren.
• Praktische Anwendbarkeit: Die Regel ist einfach berechenbar, benötigt keine komplexe Simulation und bietet einen klaren „Preis der Robustheit" (Price of Robustness): Ein geringer Zusatz an Ressourcen (ca. 7 % mehr Drohnen) verhindert katastrophales Missionsversagen.

Zusammenfassend bietet das Paper eine notwendige und hinreichende Regel zur Dimensionierung von Ersatzflotten, die die inhärente Synchronisation in Multi-UAV-Inspektionsmissionen berücksichtigt und damit die Lücke zwischen theoretischer Planung und praktischer Zuverlässigkeit schließt.