L’Ecole doctorale : Ecole Doctorale de l’Institut Polytechnique de Paris

et le Laboratoire de recherche SAMOVAR – Services répartis, Architectures, Modélisation, Validation, Administration des Réseaux

présentent

l’AVIS DE SOUTENANCE de Madame Najoua BENALAYA

Autorisée à présenter ses travaux en vue de l’obtention du Doctorat de l’Institut Polytechnique de Paris, préparé à Télécom SudParis en :

Mathématiques et Informatique

« planification des trajectoires de recherche par drone pour la surveillance du bétail : de la programmation linéaire aux approches basées sur l’apprentissage »

le LUNDI 1 DéCEMBRE 2025 à 9h30

à

Amphithéâtre Sophie Germain, Bâtiment Turing
Centre Inria Saclay 1 Rue Honoré d’Estienne d’Orves, 91120 Palaiseau

Membres du jury :

M. Anis LAOUITI, Professeur, Télécom SudParis, FRANCE – CoDirecteur de these
M. Omar sami  OUBATTI, Maître de conférences, Université Gustave Eiffel Paris, FRANCE – Rapporteur
M. Amine DHRAIEF, Professeur, Ecole Supérieure d’Économie Numérique, Tunisie, TUNISIE – Rapporteur
M. Sami SOUIHI, Maître de conférences, Université Paris-Est Creteil, FRANCE – Examinateur
Mme Leila NASRAOUI, Professeure, Ecole nationale des sciences de l’informatique, Tunisie, TUNISIE – Examinateur
M. Nadjib ACHIR, Maître de conférences, Université Sorbonne Paris Nord, FRANCE – Examinateur
M. Paul MüHLETHALER, Directeur de recherche, Inria Saclay, FRANCE – Examinateur
Mme Leila AZOUZ SAIDANE, Professeur émérite, Ecole nationale des sciences de l’informatique, Tunisie, TUNISIE – CoDirecteur de these

« planification des trajectoires de recherche par drone pour la surveillance du bétail : de la programmation linéaire aux approches basées sur l’apprentissage »

présenté par Madame Najoua BENALAYA

Résumé :

UAV ou drones sont des systèmes aériens qui peuvent être pilotés à distance ou fonctionner de manière entièrement autonome. Leur polyvalence permet leur déploiement dans de nombreux secteurs. Dans l’élevage de précision, les UAV autonomes peuvent faciliter la surveillance en temps réel en collectant des données sur la santé du bétail. Pour collecter ces mesures, les UAV doivent localiser le bétail et se déplacer à proximité. Cependant, il est difficile de localiser des animaux sur des terrains vastes et encombrés, et les méthodes de localisation traditionnelles (par exemple, colliers GPS et RFID) sont coûteuses et consomment beaucoup d’énergie. Cette thèse aborde donc le problème de la recherche de bétail par drone (UCS) : concevoir des trajectoires de recherche qui minimisent le temps de recherche prévu (EST) pour localiser le bétail dans le cadre de contraintes opérationnelles. Sur la base d’une analyse approfondie de la littérature, nous définissons l’UCS comme un problème d’optimisation combinatoire de trajectoire. L’UCS est un problème probabiliste dépendant du temps qui présente des similitudes avec des problèmes d’optimisation de trajectoire bien connus tels que le problème du voyageur de commerce (TSP), mais qui diffère en termes d’objectif principal. Nous sommes donc les premiers à introduire et à résoudre le problème de l’UCS. Nous résolvons ce problème en suivant trois axes principaux: i) Formulations exactes. Tout d’abord, nous développons des modèles de programmation linéaire pour trois instances UCS avec cible stationnaire (UCS-ST), avec cible mobile unique (UCS-SMT) et avec deux cibles mobiles (UCS-TMT). Ces modèles fournissent des solutions optimales prouvées et constituent des références. Cependant, leur évolutivité est limitée aux petites instances. ii) Deuxièmement, nous étudions les approches basées sur l’apprentissage, car elles sont plus adaptées aux environnements dynamiques et ne nécessitent pas de conception experte. De plus, elles améliorent l’évolutivité. Nous concevons un cadre d’apprentissage profond par renforcement à l’aide de l’algorithme d’optimisation de politique proximale (PPO) pour UCS-ST, démontrant ainsi la viabilité de la recherche basée sur les politiques. iii) Troisièmement, nous introduisons un Transformer supervisé et uniquement basé sur un encodeur qui traite l’UCS-ST comme une prédiction du nœud suivant et peut générer efficacement des trajectoires à partir de parcours optimaux. Globalement, la thèse contribue aux domaines des formulations exactes et des modèles évolutifs basés sur l’apprentissage pour la recherche de bétail par drone, tout en délimitant les compromis entre l’optimalité et l’efficacité computationnelle. Les méthodes sont également applicables au-delà de la surveillance du bétail et s’étendent à d’autres problèmes dans de larges classes de CPOP sous incertitude.

Abstract :

Unmanned Aerial Vehicles (UAVs, or drones) are aircraft systems that can be remotely piloted or operate fully autonomously. Their versatility enables deployment across many sectors. In precision livestock farming, autonomous UAVs can support real-time monitoring by collecting health data about the cattle. To collect these measures, UAVs need to locate the cattle and travel near them. However, locating animals over vast, cluttered lands is difficult, and traditional localization methods (e.g., GPS collars, RFID, camera traps) are costly and energy-intensive. This dissertation therefore, addresses the UAV Cattle Search (UCS) problem: designing search paths that minimize the Expected Search Time (EST) to localize cattle under operational constraints. Based on an extensive literature review, we frame UCS as a Combinatorial Path Optimization Problem (CPOP). UCS is a probabilistic time-dependent problem that shares similarities with well-known path optimization problems like the Traveling Salesman Problem (TSP), but it differs in terms of the major objective. Thus, we are the first to introduce and solve the UCS problem. We solve this problem following three main axes: i) First, we develop exact Linear Programming formulations for three UCS instances: Stationary Target (UCS-ST), Single Moving Target (UCS-SMT), and Two Moving Targets (UCS-TMT). These models deliver provably optimal solutions and provide benchmarks. However, their scalability is limited to small instances. ii) Second, we investigate learning-based approaches as it is more suitable for dynamic environments and do not require expert design. In addition, it improves scalability. We design a Deep Reinforcement Learning framework using the Proximal Policy Optimization algorithm (PPO) for UCS-ST, demonstrating the viability of policy-based search. iii) Third, we introduce a supervised and encoder-only Transformer framework that treats UCS-ST as next-node prediction and can efficiently generate trajectories from optimal tours. Overall, the thesis contributes to the areas of exact formulations and scalable learning-based models for UAV cattle searching, while delineating the trade-offs in optimality and computational efficiency. The methods are applicable beyond livestock monitoring as well, and extend to other problems within broad classes of CPOP under uncertainty.