This thesis presents an online path planning algorithm developed for unmanned vehicles in charge of autonomous border patrol. In this Pursuit-Evasion game, the unmanned vehicle is required to capture multiple trespassers on its own before any of them reach a target safe house where they are safe from capture. The problem formulation is based on Isaacs’ Target Guarding problem, but extended to the case of multiple evaders. The proposed path planning method is based on Rapidly-exploring random trees (RRT) and is capable of producing trajectories within several seconds to capture 2 or 3 evaders. Simulations are carried out to demonstrate that the resulting trajectories approach the optimal solution produced by a nonlinear programming-based numerical optimal control solver. Experiments are also conducted on unmanned ground vehicles to show the feasibility of implementing the proposed online path planning algorithm on physical applications.

University, Diss., 2004--Saarbrücken.

No description available.

No description available.

This thesis is concerned with the Pursuit-and-Evasion (PE) problem where the pursuer aims to minimize the time to capture the evader while the evader tries to prevent capture. In the problem, the evader has two advantages: a higher manoeuvrability and that the pursuer is uncertain about the evader??s state. Cooperation among multiple pursuer vehicles can thus be used to overcome the evader??s advantages. The focus here is on the formulation and development of frameworks and algorithms for cooperation amongst pursuers, aiming at feasible implementation on real and autonomous vehicles. The thesis is split into Parts I and II. Part I considers the problem of capturing an evader of higher manoeuvrability in a deterministic PE game. The approach is the employment of Forward Reachable Set (FRS) analysis in the pursuers?? control. The analysis considers the coverage of the evader??s FRS, which is the set of reachable states at a future time, with the pursuer??s FRS and assumes that the chance of capturing the evader is dependent on the degree of the coverage. Using the union of multiple pursuers?? FRSs intuitively leads to more evader FRS coverage and this forms the mechanism of cooperation. A framework for cooperative control based on the FRS coverage, or FRS-based control, is proposed. Two control algorithms were developed within this framework. Part II additionally introduces the problem of evader state uncertainty due to noise and limited field-of-view of the pursuers?? sensors. A search-and-capture (SAC) problem is the result and a hybrid architecture, which includes multi-sensor estimation using the Particle Filter as well as FRS-based control, is proposed to accomplish the SAC task. The two control algorithms in Part I were tested in simulations against an optimal guidance algorithm. The results show that both algorithms yield a better performance in terms of time and miss distance. The results in Part II demonstrate the effectiveness of the hybrid architecture for the SAC task. The proposed frameworks and algorithms provide insights for the development of effective and more efficient control of pursuer vehicles and can be useful in the practical applications such as defence systems and civil law enforcement.

This thesis is concerned with the Pursuit-and-Evasion (PE) problem where the pursuer aims to minimize the time to capture the evader while the evader tries to prevent capture. In the problem, the evader has two advantages: a higher manoeuvrability and that the pursuer is uncertain about the evader??s state. Cooperation among multiple pursuer vehicles can thus be used to overcome the evader??s advantages. The focus here is on the formulation and development of frameworks and algorithms for cooperation amongst pursuers, aiming at feasible implementation on real and autonomous vehicles. The thesis is split into Parts I and II. Part I considers the problem of capturing an evader of higher manoeuvrability in a deterministic PE game. The approach is the employment of Forward Reachable Set (FRS) analysis in the pursuers?? control. The analysis considers the coverage of the evader??s FRS, which is the set of reachable states at a future time, with the pursuer??s FRS and assumes that the chance of capturing the evader is dependent on the degree of the coverage. Using the union of multiple pursuers?? FRSs intuitively leads to more evader FRS coverage and this forms the mechanism of cooperation. A framework for cooperative control based on the FRS coverage, or FRS-based control, is proposed. Two control algorithms were developed within this framework. Part II additionally introduces the problem of evader state uncertainty due to noise and limited field-of-view of the pursuers?? sensors. A search-and-capture (SAC) problem is the result and a hybrid architecture, which includes multi-sensor estimation using the Particle Filter as well as FRS-based control, is proposed to accomplish the SAC task. The two control algorithms in Part I were tested in simulations against an optimal guidance algorithm. The results show that both algorithms yield a better performance in terms of time and miss distance. The results in Part II demonstrate the effectiveness of the hybrid architecture for the SAC task. The proposed frameworks and algorithms provide insights for the development of effective and more efficient control of pursuer vehicles and can be useful in the practical applications such as defence systems and civil law enforcement.

This paper concerns a specific pursuit-evasion problem with a node-located evader which we call the monk problem. First, we propose a way of verifying a strategy using a new kind of recursive systems, called EL-systems. We show how an EL-system representing a graph-instance of the problem can be represented using matrices, and we give an example of how this can be used to efficiently implement a verifier. In the later parts we propose heuristics to construct a strategy, based on a greedy algorithm. Our main focus is to minimise the number of pursuers needed, called the search number. The heuristics rely on properties of minimal stable components. We show that the minimal stable components are equivalent to the strongly connected components of a graph, and prove that the search number is equal to the maximum search number of its strongly connected components. We also establish lower and upper bounds for the search number to narrow the search space. / Denna rapport avhandlar ett specifikt pursuit-evasion problem med en hörnplacerad flykting, som vi kallar för munkproblemet. Först föreslår vi ett sätt att verifiera en strategi med en ny typ av rekursivt system, kallat EL-system. Vi visar hur ett EL-system som representerar en grafinstans av munkproblemet kan representeras med matriser, och vi ger ett exempel på hur detta kan användas för att effektivt implementera en verifikator. I de senare delarna föreslår vi heuristiker för att konstruera en strategi, baserad på giriga algoritmer. Vårt huvudfokus är att minimera antalet förföljare som krävs för att dekontaminera grafen, det så kallade söktalet. Vår heuristik förlitar sig på egenskaper för minimala stabila komponenter. Vi visar att minimala stabila komponenter är ekvivalenta med de starka komponenterna i en graf, och härleder att söktalet är lika med det maximala söktalet för grafens starka komponenter. Vi etablerar också undre och övre gränser för söktalet i syfte att minska sökintervallet.

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.

ABSTRACT Usually, real game problems encountered in our daily lives are so complicated that the existing methods are no longer sufficient to deal with them. This motivates us to investigate several kinds of differential game problems, which have not been considered or solved yet, including a pursuit-evasion game with n pursuers and one evader, a problem of guarding a territory with two guarders and two invaders, and a payoff-switching differential game. In this thesis, firstly the geometric method is used to consider the pursuit-evasion game with n pursuers and one evader. Two criteria used to find the solutions of the game in some cases are given. It will be shown that the one-on-one pursuit-evasion game is a special case of this game. Secondly, the problem of guarding a territory with two guarders and two invaders is considered both qualitatively and quantitatively. The investigation of this problem reveals a variety of situations never occurring in the case with one guarder and one invader. An interesting thing found in this investigation is that some invader may play the role as a pursuer for achieving a more favorable payoff in some cases. This will make the problem more complicated and more difficult to be solved. The payoff-switching differential game, first proposed by us, is a kind of differential game with incomplete information. The main difference between this problem and traditional differential games is that in a payoff-switching differential game, any one player at any time may have several choices of payoffs for the future. The optimality in such a problem becomes questionable. Some reasoning mechanisms based on different methods will be provided to determine a reasoning strategy for some player in a payoff-switching differential game. A practical payoff-switching differential game problem, i.e., the guarding three territories with one guarder against one invader, is presented to illustrate the situations of such a game problem. Many computer simulations of this example are given to show the performances of different reasoning strategies. The proposition of the payoff-switching differential game is an important breakthrough in dealing with some kinds of differential games with incomplete information.

Coordenação de Aperfeiçoamento de Pessoal de Nível Superior - CAPES / One of the greatest reasons to use robotics rather than human beings is to avoid hazardous situations such as activities related to search, surveillance and rescue. The pursuit-evasion problem is a fundamental theoretical base to apply robotics on these cases. This dissertation presents an approach to solve the pursuit-evasion problem with no previous knowledge of the map, which must be simply connected, using multi-robots systems with limited sensing. The approach is based on the random walk, since it is a mathematical formalization probabilistically complete, considering plane and obstacle free environments that shall be treated discretely through a regular occupation grid. This dissertation also presents a variation of this approach, though it considers random walk probabilities, to enhance the previous approach, decreasing the amount of iterations needed to solve the problem. In order to validate what is proposed, a discrete multi-robot simulation environment was developed. Finally, the results obtained on the tests that were performed and possible future works that could improve this approach are discussed. / Uma das principais motivações do uso de sistemas robóticos em detrimento de seres humanos é evitar situações de risco, como as encontradas em atividades de busca, vigilância e resgate. O problema de perseguição-evasão é uma base teórica fundamental para a aplicação da robótica nestes casos. Esta dissertação apresenta uma abordagem para solução do problema de perseguição-evasão sem um conhecimento a priori do mapa, que deverá ser simplesmente conectado, através da coordenação de múltiplos robôs com visão limitada. A abordagem aqui proposta é baseada na random walk, por esta ser uma formalização matemática probabilisticamente completa, sendo contemplados ambientes planos e sem obstáculos, que serão tratados discretamente por meio de uma grade de ocupação regular. Ainda nesta dissertação, foi proposta uma variação dessa abordagem, porém com a ponderação de probabilidades da random walk, com o objetivo de aprimorar a anterior, diminuindo número de iterações necessárias para solução do problema. Para a validação da abordagem proposta, foi desenvolvido um ambiente de simulações para abordagens discretas de múltiplos robôs. Finalmente, são discutidos os resultados obtidos nos testes realizados e propostos trabalhos futuros para melhoria desta abordagem.