# Maximiser l'Informativité et la Connectivité pour une Planification Optimale des Trajectoires Multi-Agents : Application à la Surveillance des Panaches de Pollution

Mohamed Sami Assenine, Walid Bechkit, Hervé Rivano

► To cite this version:

Mohamed Sami Assenine, Walid Bechkit, Hervé Rivano. Maximiser l'Informativité et la Connectivité pour une Planification Optimale des Trajectoires Multi-Agents : Application à la Surveillance des Panaches de Pollution. ALGOTEL 2025 - 27èmes Rencontres Francophones sur les Aspects Algorithmiques des Télécommunications, Jun 2025, Saint Valery-sur-Somme, France. hal-04995802

HAL Id: hal-04995802

https://hal.science/hal-04995802v1

Submitted on 18 Mar 2025

HAL is a multi-disciplinary open access
archive for the deposit and dissemination of sci-
entific research documents, whether they are pub-
lished or not. The documents may come from
teaching and research institutions in France or
abroad, or from public or private research centers.

L'archive ouverte pluridisciplinaire HAL, est
destinée au dépôt et à la diffusion de documents
scientifiques de niveau recherche, publiés ou non,
émanant des établissements d'enseignement et de
recherche français ou étrangers, des laboratoires
publics ou privés.

<figure><img src="image_1.png" /></figure>

Distributed under a Creative Commons Attribution 4.0 International License
# Maximiser l'Informativité et la Connectivité pour une Planification Optimale des Trajectoires Multi-Agents : Application à la Surveillance des Panaches de Pollution

Mohamed Sami Assenine¹ et Walid Bechkit¹ et Hervé Rivano¹

¹INSA Lyon, Inria, CITI, UR3720, 69621 Villeurbanne, France

Ce travail propose une approche optimisée pour la surveillance des panaches de pollution à l'aide de drones équipés de capteurs environnementaux. En exploitant la puissance de l'apprentissage par renforcement, la solution proposée optimise stratégiquement les trajectoires des drones afin de maximiser la qualité des données collectées tout en garantissant la connectivité. Un schéma d'apprentissage indépendant Q-Learning multi-agents est utilisé, où chaque drone agit de manière autonome tout en partageant une récompense d'équipe basée sur l'amélioration de l'estimation du panache et la maximisation d'une métrique de connectivité. Les tests démontrent l'efficacité de notre approche, qui offre un équilibre entre la précision de l'estimation des panaches et l'efficacité des communications. Elle surpasse une stratégie de mobilité aléatoire jusqu'à 32,88% et une heuristique génétique jusqu'à 4,2%, tout en maintenant un faible temps d'exécution.

**Mots-clefs** : Surveillance des panaches de pollution, Information mutuelle, Coûts de communication, Processus Gaus- sien, Planification informative de trajectoire, Système multi-agents, Apprentissage par renforcement.

## 1 Introduction

Les préoccupations croissantes concernant la pollution environnementale suscitent un vif intérêt pour le développement de systèmes avancés de surveillance. La détection et le suivi des panaches de pollution de l'air, caractérisés par une dispersion complexe dans l'atmosphère, nécessitent des méthodes précises et efficaces. Les approches classiques, telles que les capteurs au sol et les stations de mesures, sont sou- vent limitées en termes de couverture, de mobilité et d'acquisition de données en temps réel, en particulier lorsqu'il s'agit de phénomènes dynamiques. Pour pallier ces limitations, l'utilisation de drones autonomes apparaît comme une solution prometteuse, améliorant l'efficacité du suivi de la pollution grâce à leur flexi- bilité et leur capacité d'adaptation, notamment dans des contextes d'urgence où l'intervention humaine est limitée [GZL+23]. Dans ce contexte, un défi majeur réside dans l'optimisation des trajectoires des drones afin de collecter uniquement les données pertinentes pour l'estimation des panaches.

Dans cette contribution, nous supposons que le panache de pollution est modélisable par un processus gaussien (GP) [DZ07], une hypothèse largement utilisée pour étudier la pollution atmosphérique [HDWG19]. Cette modélisation permet d'obtenir des estimations fiables et d'intégrer une mesure d'incertitude essen- tielle dans des contextes où les observations sont limitées. Ainsi, notre solution exploite cette métrique d'incertitude basée sur l'information mutuelle (MI) [GKS05] pour l'optimisation des trajectoires à l'aide de l'apprentissage par renforcement (RL) [SB18] pour offrir une approche robuste et scalable au suivi des panaches de pollution [ABR24].

## 2 Problématique

Nous considérons une flotte de drones équipés de capteurs environnementaux, de capacités de calcul em- barquées et de systèmes de communication sans fil. Lorsqu'un panache de pollution accidentel est détecté,
ces drones sont déployés afin de surveiller sa propagation en temps réel et de générer des cartes de concentration de polluants précises. Le phénomène étudié est modélisé par un GP, et notre objectif est d'estimer rapidement ses paramètres, en trouvant les trajectoires optimales passant par les points de mesures les plus informatifs sur le panache, tout en minimisant les coûts de communication entre drones et la station de base au sol. Cette station de base coordonne les drones à chaque itération.

À chaque étape, les drones transmettent leurs mesures à la station de base, qui met à jour la régression GP et détermine les prochaines positions des drones. La communication suit un modèle multi-sauts, permettant d'acheminer les données via d'autres drones avant d'atteindre la station. Le coût de communication entre deux nœuds est défini comme le nombre attendu de transmissions, incluant les retransmissions.

L'espace d'étude est discrétisé sous forme d'une grille régulière où chaque sommet représente un point de mesure potentiel. La qualité de l'information collectée en un ensemble de points est mesurée par l'information mutuelle. L'objectif est de déterminer un ensemble de trajectoires optimales maximisant la qualité des mesures et la métrique de connectivité, tout en respectant les contraintes énergétiques des drones, assurées à un budget. Ainsi, le problème étudié consiste à optimiser conjointement la couverture spatiale du panache et la robustesse des communications pour une surveillance autonome et adaptative.

## 3 Travaux Connexes

Plusieurs travaux se sont intéressés à la planification de trajectoires basée sur l'information mutuelle, permettant de sélectionner les points de mesures les plus informatifs. Les auteurs de [GKS05] ont introduit l'usage de l'information mutuelle pour le placement optimal de capteurs dans les réseaux sans fil, tandis que [DXL¹⁵] a exploré l'optimisation du placement de capteurs de vent en milieu urbain pour améliorer la précision des prédictions météorologiques. Dans le domaine de la robotique mobile, [BKS10] a proposé une heuristique simple pour la planification de trajectoires pour véhicules sous-marins autonomes en s'appuyant sur une modélisation sous GP et une métrique définie par l'information mutuelle, alors que [WZ21] a employé un modèle d'apprentissage par renforcement profond (DQN) couplé à l'information mutuelle pour planifier les déplacements de robots collectant des données de signal Wi-Fi en intérieur. Cependant, ces approches, principalement conçues pour des phénomènes statiques ou des environnements contrôlés, sont plus difficiles à appliquer aux panaches de pollution dynamiques.

Par ailleurs, la modélisation de la qualité des liens de communication est cruciale pour garantir la fiabilité des transmissions et par conséquent réduire les retransmissions. Des travaux, comme [KGGK11], ont utilisé un modèle probabiliste basé sur les GP pour estimer la qualité des liens de communication sans fil. Ces modèles permettent d'estimer le nombre moyen de transmissions nécessaires entre deux nœuds, en tenant compte des pertes potentielles de paquets [DCABM03].

## 4 Méthodologie

Pour adresser notre problématique, nous proposons une solution basée sur le RL pour une planification informative à l'aide d'une métrique issue de l'information mutuelle. Dans ce qui suit, nous détaillons le schéma général de la solution ainsi que la fonction de récompense employée [ABR24].

### 4.1 Schéma Global de la Solution

Notre solution repose sur un schéma d'apprentissage indépendant Q-Learning (IQL) [Tan93], dans lequel chaque drone apprend une politique de déplacement individuellement tout en partageant un état d'entrée partiel. La solution globale s'articule autour des points suivants :

- **Acquisition des mesures** : chaque drone collecte des données environnementales en vol stationnaire.

- **Mise à jour de la modélisation à base de GP** : une régression GP, implémentée au niveau de la station de base, ajuste l'estimation de la carte du panache en fonction des nouvelles mesures reçues.

- **Sélection des prochains déplacements** : le modèle RL, centralisé au niveau de la station de base au sol et reposant sur une architecture de type Rainbow DQN [HMVH¹⁸] avec plusieurs couches de neurones entièrement connectées, génère des actions de déplacement optimales pour chaque drone afin de maximiser la fonction de récompense.
— **Calcul des récompenses** : la station de base calcule une récompense après chaque étape de déplacement et la répartit entre les drones selon une approche méritocratique (Difference Rewards) [NKL18].

— **Itération du processus** : ce processus se répète jusqu'à l'épuisement des batteries des drones.

L'état d'entrée du modèle RL est défini par un quadruple composé de la carte actuelle estimée du panache, de ses coordonnées, de son budget énergétique restant et des positions des autres drones [ABR24]. À chaque étape, le drone peut soit se déplacer vers un sommet voisin, soit rester sur place.

## 4.2 Fonction de Récompense

La prise de décision repose sur une fonction de récompense qui équilibre l'acquisition d'information et les coûts de communication. La récompense attribuée à un drone i à l'instant t est définie par :

$$R_T(v_t^i) = \alpha \cdot \tanh(R_{MI}(v_t^i)) + (1 - \alpha) \cdot R_{CC}(v_t^i), \quad (1)$$

où :

— $R_{MI}(v_t^i)$ quantifie la **réduction de l'incertitude** sur l'état du panache. Il est calculé comme la dimension en entropie ($H(\cdot)$) après l'ajout des mesures prises par le drone i :

$$R_{MI}(v_t^i) = H(y_V|y_{P_t^{-i}}) - H(y_V|y_{P_t}). \quad (2)$$

Ici : $y_V$ représente les mesures effectuées sur l'ensemble des points de la grille V, $P_t$ désigne l'ensemble des points mesurés par les drones jusqu'à l'instant t, et $P_t^{-i}$ correspond au même ensemble précédent après exclusion des points explorés par le drone i.

— $R_{CC}(v_t^i)$ représente le **coût de communication**. Il est défini comme l'inverse du coût de transmission multi-sauts entre un drone et la station de base. Calculer ce coût revient à déterminer le chemin de communication optimal reliant un drone i à la station de base. Cette connexion peut être directe ou s'effectuer via plusieurs sauts en passant par d'autres drones. À chaque étape, ces chemins optimaux sont déterminés à l'aide de l'algorithme de Dijkstra, implémenté au niveau de la station de base, qui centralise la gestion des déplacements des drones. L'algorithme prend en compte l'opposé du logarithme des probabilités de transmission réussie entre une paire de points $v_1$ et $v_2$, soit $-\log(p(\theta_{v_1,v_2}))$ [ABR24]. Ainsi, si le chemin optimal entre le drone i et la station de base $v_{bs}$ est représenté par $(v_t^i = v_1, v_2, \dots, v_k = v_{bs})$, alors le coût de communication du drone i s'exprime comme suit :

$$R_{CC}(v_t^i) = \frac{1}{CC(v_t^i)} \quad \text{où} \quad CC(v_t^i) = \sum_{j=1}^{j=k-1} \log(1/p(\theta_{v_j,v_{j+1}})). \quad (3)$$

— $\alpha \le 1$ est le paramètre d'agrégation permettant d'ajuster le compromis informativité-connectivité.

## 5 Validation et Évaluation des Performances

Notre solution repose sur l'implémentation de trois composants : la simulation des panaches à l'aide d'un modèle de dispersion Gaussien [DZ07], la simulation des transmissions de paquets par un modèle de régression GP [KGGK11, BBCB14], et la mise en œuvre de l'approche Rainbow en utilisant RLlib†.

Les performances de notre approche Rainbow sont évaluées sur deux scénarios distincts. Dans le premier, la direction du vent est inclinée de 20° par rapport à l'axe des abscisses, et les drones décollent depuis la station de base située à (0, 4). Dans le second, le vent est aligné avec l'axe des abscisses et les drones partent du centre de la zone surveillée, une configuration inédite permettant d'évaluer la capacité de généralisation.

La Fig. 1 illustre l'évolution des récompenses totales au cours d'un épisode, mettant en évidence la supériorité de Rainbow sur deux approches de référence : un vol aléatoire (Random) et une heuristique génétique (GA). Vous trouverez les détails d'implémentation des approches et des simulations dans [ABR24]. Bien que GA et Rainbow affichent des performances proches, Rainbow la surpasse de 4, 2% et 1, 88% selon le scénario, pendant que l'écart avec Random varie entre 17, 24% et 32, 88%. Cette différence s'explique par l'analyse des composantes de la récompense totale où Rainbow maximise la récompense liée à l'informativité, atteignant des valeurs plus élevées que les autres méthodes, tout en maintenant un nombre raisonnable de retransmissions (un maximum de 3 paquets retransmis par étape).

<footnote>†. https://docs.ray.io/en/latest/rllib/index.html.</footnote>
<figure><img src="image_2.png" /><figcaption>**FIGURE 1 :** Comparaison des récompenses totales de l'équipe pour les trois approches étudiées.</figcaption></figure>

La Fig. 2 compare la précision de l'estimation des concentrations de polluants. Rainbow se distingue par une erreur absolue moyenne plus faible que ses concurrents, avec une précision supérieure de 0,05mg/m³ par rapport à la GA. Cette amélioration met en évidence la capacité de Rainbow à concilier exploration efficace et estimation robuste des concentrations de polluants, allant jusqu'à couvrir 60% de la zone à surveiller. De plus, Rainbow réduit significativement l'erreur d'estimation de la variance initiale de 16%-25% à 3%-5%, tandis que les autres approches présentent des erreurs finales comprises entre 6% et 12%.

<figure><img src="image_3.png" /><figcaption>**FIGURE 2 :** Évolution de l'erreur absolue moyenne (MAE) dans l'estimation de la concentration de polluants.</figcaption></figure>

L'un des avantages notables de notre solution réside dans son efficacité en termes de temps d'exécution, inférant une solution en quelques centaines de millisecondes, contre plus de 30 minutes par instance pour l'heuristique génétique [ABR24]. Les expériences menées démontrent également la scalabilité de notre approche, tant en fonction du nombre de drones que de la diversité des actions possibles à chaque étape et du nombre d'étapes par épisode [ABR24].

# 6 Conclusion

Cette étude présente une solution efficace pour la surveillance des panaches de pollution à l'aide d'une flotte de drones équipés de capteurs environnementaux. L'utilisation du RL couplé à la modélisation par régression GP se révèle être une approche prometteuse pour relever les défis de la surveillance environnementale via des systèmes multi-agents autonomes. Notre solution vise à planifier les trajectoires des drones afin de maximiser l'informativité des mesures tout en optimisant la connectivité. La modélisation des panaches et des probabilités de transmission réussie entre les points est réalisée à l'aide de modèles de régression GP. Ces modèles permettent de calculer l'informativité avec l'information mutuelle et d'estimer les coûts de communication. Les simulations démontrent que notre approche surpasse des méthodes de référence, telles que le vol aléatoire et une heuristique génétique. Grâce au RL, notre solution peut s'adapter efficacement à divers problèmes de surveillance de phénomènes physiques modélisables par des GP.
Références

[ABR24] Mohamed Sami Assenine, Walid Bechkit, and Hervé Rivano. Informative and communication-efficient multi-agent path planning for pollution plume monitoring. In *2024 IEEE 25th International Symposium on a World of Wireless, Mobile and Multimedia Networks (WoWMoM)*, pages 329–338, 2024.

[BBCB14] Abdelmalik Bachir, Walid Bechkit, Yacine Challal, and Abdelmadjid Bouabdallah. Joint connectivity-coverage temperature-aware algorithms for wireless sensor networks. *IEEE Transactions on Parallel and Distributed Systems*, 26(7):1923–1936, 2014.

[BKS10] Jonathan Binney, Andreas Krause, and Gaurav S Sukhatme. Informative path planning for an autonomous underwater vehicle. In *2010 IEEE International Conference on Robotics and Automation (ICRA)*, pages 4791–4796. IEEE, 2010.

[DCABM03] Douglas SJ De Couto, Daniel Aguayo, John Bicket, and Robert Morris. A high-throughput path metric for multi-hop wireless routing. In *Proceedings of the 9th annual International Conference on Mobile Computing and Networking*, pages 134–146, 2003.

[DXL<sup>+</sup>15] Wan Du, Zikun Xing, Mo Li, Bingsheng He, Lloyd Hock Chye Chua, and Haiyan Miao. Sensor placement and measurement of wind for water quality studies in urban reservoirs. *ACM Transactions on Sensor Networks (TOSN)*, 11(3):1–27, 2015.

[DZ07] Aaron Daly and Paolo Zannetti. Air pollution modeling-an overview. *Ambient air pollution*, pages 15–28, 2007.

[GKS05] Carlos Guestrin, Andreas Krause, and Ajit Paul Singh. Near-optimal sensor placements in gaussian processes. In *Proceedings of the 22nd International Conference on Machine Learning (ICML)*, pages 265–272, 2005.

[GZL<sup>+</sup>23] Yue Guan, Sai Zou, Kai Li, Wei Ni, and Bochun Wu. Mappo-based cooperative uav trajec- tory design with long-range emergency communications in disaster areas. In *2023 IEEE 24th International Symposium on a World of Wireless, Mobile and Multimedia Networks (WoWMoM)*, pages 376–381. IEEE, 2023.

[HDWG19] Oliver Hamelijnck, Theodoros Damoulas, Kangrui Wang, and Mark Girolami. Multi- resolution multi-task gaussian processes. *Advances in Neural Information Processing Systems (NeurIPS)*, 2019.

[HMVH<sup>+</sup>18] Matteo Hessel, Joseph Modayil, Hado Van Hasselt, Tom Schaul, Georg Ostrovski, Will Dab- ney, Dan Horgan, Bilal Piot, Mohammad Azar, and David Silver. Rainbow: Combining improvements in deep reinforcement learning. In *Proceedings of the AAAI conference on artificial intelligence*, volume 32, 2018.

[KGGK11] Andreas Krause, Carlos Guestrin, Anupam Gupta, and Jon Kleinberg. Robust sensor place- ments at informative and communication-efficient locations. *ACM Transactions on Sensor Networks (TOSN)*, 7(4):1–33, 2011.

[NKL18] Duc Thien Nguyen, Akshat Kumar, and Hoong Chuin Lau. Credit assignment for collec- tive multiagent rl with global rewards. *Advances in Neural Information Processing Systems (NeurIPS)*, 31, 2018.

[SB18] Richard S Sutton and Andrew G Barto. *Reinforcement learning: An introduction*. MIT press, 2018.

[Tan93] Ming Tan. Multi-agent reinforcement learning: Independent vs. cooperative agents. In *Proceedings of the tenth International Conference on Machine Learning (ICML)*, pages 330–337, 1993.

[WZ21] Yongyong Wei and Rong Zheng. Multi-robot path planning for mobile sensing through deep reinforcement learning. In *IEEE INFOCOM 2021-IEEE International Conference on Computer Communications*, pages 1–10. IEEE, 2021.