No description available.

La plupart des applications des avions drones sont liées à l'observation d'événements au sol. En particulier, les suivi de cibles terrestres mobiles, qu'elles soient statiques, lentes ou rapides, est une tâche essentielle pour un drone. L'objectif global de la thèse est de proposer des méthodes qui permettent à un drone de suivre une cible terrestre, dans les conditions suivantes: - Le drone est de type voilure fixe équipé d'une caméra monoculaire. - Présence d'obstacles qui occultent la visibilité de zones au sol. - Existence de zones d'exclusion aérienne qui limitent le mouvement aérien. - Restrictions sur le champ de vue du capteur qui assure le suivi (caméra) - Différents comportements de la cible : elle peut évoluer librement ou sous contraintes dynamiques (cas d'une voiture par exemple), et peut être neutre ou évasive~: dans ce dernier cas, elle peut exploiter la présence d'obstacles pour éviter d'être perçue par le drone. Trois approches pour aborder ce problème sont proposées dans la thèse : - Une méthode basée aux lois de contrôle et de la navigation, - Une méthode basée sur la prédiction des déplacements de la cible, - Et une approche basée sur la théorie des jeux. Des résultats obtenus par des simulations réalistes et avec un drone sont présentés, pour évaluer et comparer les avantages et inconvénients de chacune des approches. Des extensions au cas "multi-drones" sont aussi proposées.

Cette thèse porte sur l’étude des propriétés structurelles de graphes dont la compréhension permet de concevoir des algorithmes efficaces pour résoudre des problèmes d’optimisation. Nous nous intéressons plus particulièrement aux méthodes de décomposition des graphes, aux jeux de poursuites et à la notion de convexité. Le jeu de Processus a été défini comme un modèle de la reconfiguration de routage. Souvent, ces jeux où une équipe de chercheurs doit effacer un graphe non orienté sont reliés aux décompositions de graphes. Dans les digraphes, nous montrons que le jeu de Processus est monotone et nous définissons une nouvelle décomposition de graphes que lui est équivalente. Ensuite, nous étudions d’autres décompositions de graphes. Nous proposons un algorithme FPT-unifiée pour calculer plusieurs paramètres de largeur de graphes. En particulier, ceci est le premier FPT-algorithme pour la largeur arborescente q-branché et spéciale d’un graphe. Nous étudions ensuite un autre jeu qui modélise les problèmes de pré-chargement. Nous introduisons la variante en ligne du jeu de surveillance. Nous étudions l’écart entre le jeu de surveillance classique et ses versions connecté et en ligne, en fournissant de nouvelles bornes. Nous définissons ensuite un cadre général pour l’étude des jeux poursuite-évasion. Cette méthode nous permet de donner les premiers résultats d’approximation pour certains de ces jeux. Finalement, nous étudions un autre paramètre lié à la convexité des graphes et à la propagation d’infection dans les réseaux, le nombre enveloppe. Nous fournissons plusieurs résultats de complexité en fonction des structures des graphes et en utilisant des décompositions de graphes. / This thesis focuses on the study of structural properties of graphs whose understanding enables the design of efficient algorithms for solving optimization problems. We are particularly interested in methods of decomposition, pursuit-evasion games and the notion of convexity. The Process game has been defined as a model for the routing reconfiguration problem in WDM networks. Often, such games where a team of searchers have to clear an undirected graph are closely related to graph decompositions. In digraphs, we show that the Process game is monotone and we define a new equivalent digraph decomposition. Then, we further investigate graph decompositions. We propose a unified FPT-algorithm to compute several graph width parameters. This algorithm turns to be the first FPT-algorithm for the special and the q-branched tree-width of a graph. We then study another pursuit-evasion game which models prefetching problems. We introduce the more realistic online variant of the Surveillance game. We investigate the gap between the classical Surveillance Game and its connected and online versions by providing new bounds. We then define a general framework for studying pursuit-evasion games, based on linear programming techniques. This method allows us to give first approximation results for some of these games. Finally, we study another parameter related to graph convexity and to the spreading of infection in networks, namely the hull number. We provide several complexity results depending on the graph structures making use of graph decompositions. Some of these results answer open questions of the literature.

One group of games studied within game theory are grid-based pursuit evasion games of imperfect information. A pursuit evasion game is in essence a game where there exists a set of pursuers which have as their objective to capture a set of evaders. This thesis aims to develop a formalisation of this type of games as well as describing and integrating vital game theoretical concepts such as order of knowledge into this game. With the developed formalism at hand, the concept of knowledge-based strategies is then introduced, which is essential when searching for the way to play the game most efficiently. The formalisation of the game is then followed by a simulation, measuring the performance of some older and some newly developed knowledge-based strategies. The thesis concludes that the formalisation is applicable on a more general class of pursuit evasion games and enables a wider study of the game. The simulation results indicate that knowledge-based strategies of higher order do not always perform better compared to simpler strategies of lower order of knowledge. Furthermore, strategies which allow for communication between agents are found to be superior to communication-less strategies. / En typ av spel som studeras inom spelteori är rutnätsbaserade jakt-flykt-spel med ofullständig information. Ett jakt-flykt-spel går ut på att det existerar en samling jagande aktörer som försöker fånga en samling flyende aktörer. Denna uppsats söker utveckla en formalism för denna typ av spel såväl som att beskriva och integrera ett antal nyckelkoncept inom spelteori såsom kunskapsordning. Med hjälp av den utvecklade formalismen, framställs så kallade kunskapsbaserade strategier, vilka är av fundamental vikt i sökandet efter sätt att spela spelet på det effektivaste sättet. Kapitlet om formalismen följs sedan av simuleringar där några äldre och några nyare kunskapsbaserade strategier prövas. Slutsatsen dras att den nya formalismen kan vara applicerbar på en bredare samling jakt-flykt-spel än den initialt påtänkta. Vidare underlättar formalismen en generalisering till andra sätt att beskriva spel. Simulationsresultaten indikerar att kunskapsbaserade strategier av högre ordning inte alltid presterar bättre än enklare strategier av lägre ordning. Till yttermera visso visar sig kommunikationslösa strategier vara underlägsna strategier som tillåter kommunikation. / Kandidatexjobb i elektroteknik 2022, KTH, Stockholm

Imagine for a moment we are living in the distant future where autonomous robots are patrollingthe streets as police officers. Two such robots are chasing a robber through the city streets. Fearingthe thief might listen in to any potential transmission, both robots remain radio silent and are thuslimited to a strictly visual pursuit. Since the robots cannot see the robber the entire time, they haveto deduce the potential location of the robber. What would the best strategy be for these robots toachieve their objective? This bachelor's thesis investigated the above example by creating strategies through reinforcementlearning. The thesis also investigated the performance of the players when they have differentabilities of deduction. This was tested by creating a suitable game and corresponding reinforcementlearning algorithm and running the simulations for different degrees of knowledge. The study provedthat reinforcement learning is a viable method for strategy construction, reaching nearly guaranteedvictory for cases when the agent knows everything about the environment and a slightly lower winratio when there is uncertainty introduced. The implementation yielded only a small gain in win ratiowhen the agents could deduce even more about each other. / Föreställ dig för ett ögonblick att vi lever i en avlägsen framtid där autonoma robotar patrullerar pågatorna som poliser. Två sådana robotar jagar en rånare genom stadens gator. Eftersom de är räddaför att tjuven kan lyssna på alla möjliga sändningar, förblir båda robotarna radiotysta och är därförbegränsade till en strikt visuell strävan. Eftersom robotarna inte kan se rånaren hela tiden, måste dehärleda den potentiella platsen för rånaren. Vilken skulle den bästa strategin vara för dessa robotarför att uppnå sitt mål? Denna kandidatuppsats undersökte ovanstående exempel genomskapa strategier genomförstärkningsinlärning. Avhandlingen undersökte också spelarnas prestationer när de har olikaavdragsförmåga. Detta testades genom att skapa ett lämpligt spel och motsvarandeförstärkningsinlärningsalgoritm och köra simuleringarna för olika kunskapsgrader. Studien visade attförstärkningsinlärning är en användbar metod för strategikonstruktion, och når nästan garanteradseger i fall då agenten vet allt om miljön och en något lägre vinstkvot när det finns osäkerhet.Implementeringen gav bara en liten vinst i vinstförhållandet när agenterna kunde härleda ännu merom varandra. / Kandidatexjobb i elektroteknik 2023, KTH, Stockholm