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

1. Problématique

L'article aborde le défi critique du dimensionnement de la flotte de drones de rechange (spares) nécessaire pour assurer la continuité des missions d'inspection multi-UAV à horizon fini.

• Contexte : Dans des applications comme l'inspection d'infrastructures ou l'agriculture de précision, une flotte de drones actifs doit visiter un ensemble fini de sites. En raison des limites de la batterie, les drones actifs doivent être retirés périodiquement pour se recharger et être remplacés instantanément par des drones de rechange.
• Le Défi : Si aucun drone de rechange n'est disponible au moment de la demande, la mission échoue. Le problème consiste à déterminer le nombre minimal de drones de rechange ($k$) pour garantir une fiabilité de mission élevée.
• Limites des approches existantes :
  • Les modèles d'état stationnaire supposent une opération cyclique infinie, ce qui ne s'applique pas aux missions à horizon fini où chaque tâche n'est effectuée qu'une seule fois.
  • Les modèles basés sur la statistique (Erlang-B) traitent les demandes de remplacement comme des événements indépendants. Ils garantissent une probabilité de blocage faible par demande ($\epsilon$), mais cette garantie ne se traduit pas par une fiabilité de mission globale, car les échecs s'accumulent sur la durée de la mission.
• Le Phénomène Clé : L'article identifie un mode de défaillance structurel : le routage économe en énergie attribue des charges de travail similaires aux drones, ce qui entraîne une dépletion synchronisée des batteries. Cela génère des "vagues" de demandes de remplacement simultanées (bursts) qui peuvent épuiser le stock de rechange, même si la capacité moyenne semble suffisante.

2. Méthodologie

Les auteurs proposent une approche déterministe basée sur l'analyse du pire des cas, plutôt que sur des hypothèses probabilistes.

A. Modélisation du Système

• Paramètres :
  • $m$ : Nombre de drones actifs.
  • $R$ : Ratio de récupération ($R = T_{recovery} / T_{active}$), où $T_{recovery}$ est le temps total de retour, recharge et préparation, et $T_{active}$ est le temps de vol utile.
  • $k$ : Nombre de drones de rechange.
• Hypothèse de synchronisation : Les drones lancés en même temps avec des itinéraires similaires s'épuisent simultanément, créant des vagues de demandes à des intervalles réguliers.

B. Analyse du Pire des Cas (Worst-Case Analysis)

L'article démontre que sous une "alignement de phase" défavorable (tous les drones s'épuisant en même temps) :

1. Le nombre de drones simultanément en phase de récupération peut atteindre $m \lceil R \rceil$.
2. Une faille structurelle survient à la frontière du cycle de récupération : lorsque le $m$-ième groupe de drones demande un remplacement, tous les $m \lceil R \rceil$ drones de rechange sont déjà occupés dans le pipeline de récupération.
3. Pour éviter l'épuisement, il faut non seulement remplir le pipeline, mais aussi avoir une réserve immédiate pour servir la vague entrante.

C. La Règle de Dimensionnement Proposée

Les auteurs dérivent une règle fermée (closed-form) suffisante pour garantir zéro épuisement de stock :
$$k = m(\lceil R \rceil + 1)$$

• Interprétation : Cette formule ajoute une "mémoire tampon" (buffer) de $m$ drones supplémentaires par rapport à la règle de cycle de service classique ($m \lceil R \rceil$). Ces $m$ drones supplémentaires absorbent la demande synchronisée maximale à la frontière du cycle.
• Avantages : La règle ne nécessite ni simulation, ni hypothèses sur la distribution des arrivées, ni calculs itératifs. Elle est calculable instantanément à partir des spécifications de la mission.

3. Contributions Clés

1. Identification du mode de défaillance structurel : Mise en évidence du fait que le routage efficace crée une demande synchronisée (et non aléatoire), rendant les modèles de files d'attente classiques (Erlang-B) inadéquats pour les missions à horizon fini.
2. Dérivation d'une règle suffisante : Proposition de la formule $k = m(\lceil R \rceil + 1)$, qui garantit la fiabilité au niveau de la mission en couvrant le pire des cas de synchronisation.
3. Validation empirique rigoureuse : Comparaison de la règle proposée contre quatre méthodes de référence (Naïve, Duty-Cycle, Erlang-B) via des simulations de Monte Carlo sur 1000 essais par scénario.

4. Résultats Expérimentaux

Les auteurs ont testé leurs méthodes sur cinq scénarios (S1 à S5) avec des nombres de drones actifs ($m$) allant de 2 à 10 et des ratios de récupération ($R$) allant de 0,87 à 3,39.

• Fiabilité de la Mission :
  • Méthode Erlang-B (Standard) : Dans le scénario le plus difficile (S5, $R=3.39$), la méthode Erlang-B (qui vise un taux de blocage de 1% par demande) n'atteint qu'un taux de réussite de mission de 69,9%. Cela illustre l'effet cumulatif des échecs : une probabilité de succès de 99% par demande devient catastrophique sur 50+ échanges.
  • Méthode Proposée : Maintient un taux de réussite de 99,8% (borne inférieure de confiance de Wilson à 99,3%) sur tous les scénarios, y compris avec une variabilité du vent jusqu'à un coefficient de variation (CV) de 0,30.
• Coût de la Robustesse :
  • Dans le scénario S5, la méthode proposée nécessite 50 drones de rechange, contre 46 pour la méthode Erlang-B.
  • L'ajout de seulement 4 drones (environ 7% de la flotte totale) permet de passer d'un taux d'échec de 30% à un taux d'échec négligeable (<0,2%).
• Concentration des Échecs : L'analyse montre que 95% des échecs de la méthode Erlang-B se produisent lors des fenêtres de demande synchronisée (les 10% des fenêtres de 5 minutes les plus chargées), confirmant que la défaillance est due à des vagues de demande et non à une variabilité aléatoire.

5. Signification et Implications

• Changement de Paradigme : L'article démontre que pour les missions d'inspection à horizon fini, la fiabilité ne doit pas être évaluée par la probabilité de blocage d'une demande individuelle, mais par la capacité à survivre aux vagues de demande synchronisées.
• Praticité Opérationnelle : La règle proposée est simple, déterministe et ne nécessite pas de modélisation complexe. Elle permet aux planificateurs de missions de calculer instantanément la flotte de rechange nécessaire pour garantir la réussite de la mission.
• Coût-Bénéfice : Le "prix de la robustesse" est faible (quelques drones supplémentaires) par rapport au gain massif de fiabilité, évitant ainsi l'échec coûteux de missions entières.
• Limites et Perspectives : L'étude suppose une flotte homogène et une capacité de charge illimitée. Des travaux futurs pourraient intégrer des flottes hétérogènes, des contraintes de bornes de charge limitées et des stratégies de réaffectation dynamique pour réduire la synchronisation.

En conclusion, cet article fournit une solution théorique et pratique robuste pour le dimensionnement de flottes de drones, comblant le vide entre les modèles de files d'attente stochastiques et les besoins réels des missions d'inspection synchronisées.