To see the other types of publications on this topic, follow the link: Pursuit-evasion.
Dissertations / Theses on the topic 'Pursuit-evasion'
Create a spot-on reference in APA, MLA, Chicago, Harvard, and other styles
Consult the top 31 dissertations / theses for your research on the topic 'Pursuit-evasion.'
Next to every source in the list of references, there is an 'Add to bibliography' button. Press on it, and we will generate automatically the bibliographic reference to the chosen work in the citation style you need: APA, MLA, Harvard, Chicago, Vancouver, etc.
You can also download the full text of the academic publication as pdf and read online its abstract whenever available in the metadata.
Browse dissertations / theses on a wide variety of disciplines and organise your bibliography correctly.
1
Li, Dongxu. "Multi-player pursuit-evasion differential games." Columbus, Ohio : Ohio State University, 2006. http://rave.ohiolink.edu/etdc/view?acc%5Fnum=osu1164738831.
Full text
2
Prasad, Deepika. "Pursuit Evasion From Multiple Pursuers Using Speed Fluctuation." University of Cincinnati / OhioLINK, 2013. http://rave.ohiolink.edu/etdc/view?acc_num=ucin1367928486.
Full text
3
Soares, Ronan Pardo. "Pursuit-evasion games, decompositions and convexity on graphs." Universidade Federal do CearÃ, 2013. http://www.teses.ufc.br/tde_busca/arquivo.php?codArquivo=11105.
Full textAbstract:
CoordenaÃÃo de AperfeiÃoamento de NÃvel Superior<br>Esta tese à centrada no estudo de propriedades estruturais de grafos cujas compressÃes permitem a concepÃÃo de algoritmos eficientes para resolver problemas de otimizaÃÃo.
Estamos particularmente interessados em decomposiÃÃes, em jogos de perseguiÃÃo-evasÃo e em convexidade.
O jogo de Processo foi definido como um modelo para a reconfiguraÃÃo de roteamento em redes WDM. Muitas vezes, jogos de perseguiÃÃo-evasÃo, em que uma equipe de agentes
tem como objetivo limpar um grafo nÃo direcionado, estÃo intimamente relacionados com decomposiÃÃes em grafos. No caso de grafos direcionados, mostramos que o jogo de Processo à monotÃnico e definimos uma nova decomposiÃÃo em grafos equivalente a tal jogo. A partir de entÃo, investigamos outras decomposiÃÃes em grafos. Propomos um algoritmo FPT para calcular vÃrios parÃmetros de largura em grafos. Em particular, este à o primeiro algoritmo FPT para calcular a largura em Ãrvore especial e a largura em Ãrvore q-ramificada de um grafo.
Em seguida, estudamos um outro jogo perseguiÃÃo-evasÃo que modela problemas de prÃ-obtenÃÃo. NÃs introduzimos uma versÃo mais realista do jogo de VigilÃncia a versÃo on-line. Estudamos a diferenÃa entre o jogo de VigilÃncia clÃssico e suas versÃes conectadas e on-line, fornecendo novos limites para essa diferenÃa. NÃs, entÃo, definimos um modelo geral para o estudo de jogos perseguiÃÃo-evasÃo, com base em tÃcnicas de programaÃÃo linear. Este mÃtodo permite-nos dar os primeiros resultados de aproximaÃÃo para alguns desses jogos.
Finalmente, estudamos outro parÃmetro relacionado com a convexidade e a propagaÃÃo da infecÃÃo em redes, o âhull numberâ. NÃs fornecemos vÃrios resultados de complexidade computacional, dependendo das propriedades estruturais do grafo de entrada e usando decomposiÃÃes em grafos. Alguns destes resultados respondem problemas em aberto na literatura.<br>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 FPTalgorithm
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.
4
Thunberg, Johan. "Consensus and Pursuit-Evasion in Nonlinear Multi-Agent Systems." Doctoral thesis, KTH, Optimeringslära och systemteori, 2014. http://urn.kb.se/resolve?urn=urn:nbn:se:kth:diva-143658.
Full textAbstract:
Within the field of multi-agent systems theory, we study the problems of consensus and pursuit-evasion. In our study of the consensus problem, we first provide some theoretical results and then consider the problem of consensus on SO(3) or attitude synchronization. In Chapter 2, for agents with states in R^m, we present two theorems along the lines of Lyapunov’s second method that, under different conditions, guarantee asymptotic state consensus in multi-agent systems where the interconnection topologies are switching. The first theorem is formulated by using the states of the agents in the multi-agent system, whereas the second theorem is formulated by using the pairwise states for pairs of agents in the multi-agent system. In Chapter 3, the problem of consensus on SO(3) for a multi-agent system with directed and switching interconnection topologies is addressed. We provide two different types of kinematic control laws for a broad class of local representations of SO(3). The first control law consists of a weighted sum of pairwise differences between positions of neighboring agents, expressed as coordinates in a local representation. The structure of the control law is well known in the consensus community for being used in systems of agents in the Euclidean space, and here we show that the same type of control law can be used in the context of consensus on SO(3). In a later part of this chapter, based on the kinematic control laws, we introduce torque control laws for a system of rigid bodies in space and show that the system reaches consensus when these control laws are used. Chapter 4 addresses the problem of consensus on SO(3) for networks of uncalibrated cameras. Under the assumption that each agent uses a camera in order to measure its rotation, we prove convergence to the consensus set for two types of kinematic control laws, where only conjugate rotation matrices are available for the agents. In these conjugate rotations, the rotation matrix can be seen as distorted by the (unknown) intrinsic parameters of the camera. For the conjugate rotations we introduce distorted versions of well known local parameterizations of SO(3) and show consensus by using control laws that are similar to the ones in Chapter 3, with the difference that the distorted local representations are used instead. In Chapter 5, we study the output consensus problem for homogeneous systems of agents with linear continuous time-invariant dynamics. We derive control laws that solve the problem, while minimizing a cost functional of the control signal. Instead of considering a fixed communication topology for the system, we derive the optimal control law without any restrictions on the topology. We show that for all linear output controllable homogeneous systems, the optimal control law uses only relative information but requires the connectivity graph to be complete and in general requires measurements of the state errors. We identify cases where the optimal control law is only based on output errors. In Chapter 6, we address the multi-pursuer version of the visibility pursuit-evasion problem in polygonal environments. By discretizing the problem and applying a Mixed Integer Linear Programming (MILP) framework, we are able to address problems requiring so called recontamination and also impose additional constraints, such as connectivity between the pursuers. The proposed MILP formulation is less conservative than solutions based on graph discretizations of the environment, but still somewhat more conservative than the original underlying problem. It is well known that MILPs, as well as multi-pursuer pursuit-evasion problems, are NP-hard. Therefore we apply an iterative Receding Horizon Control (RHC) scheme, where a number of smaller MILPs are solved over shorter planning horizons. The proposed approach is illustrated by a number of solved examples.<br><p>QC 20140327</p>
5
Gren, Olaf, and Dennis Magnusson. "A Method for Finding Strategies in Pursuit-Evasion Games." Thesis, KTH, Skolan för elektroteknik och datavetenskap (EECS), 2020. http://urn.kb.se/resolve?urn=urn:nbn:se:kth:diva-280341.
Full textAbstract:
Many real-world situations can be described as games over finite graphs, con- sisting of a set of agents performing joint actions affecting the state of the game. One class of games over finite graphs are the so called pursuit-evasion games, where a set of pursuers try to capture an evader on a finite map. In some pursuit-evasion games where the position of the evader is unknown finding an optimal strategy to ensure victory for the pursuers can be difficult. One way to simplify this process is by using the multiplayer knowledge-based subset construction (MKBSC) to transform the game graph to an expanded graph where the pursuers’ knowledge is included in the construction. In this report we investigate the usefulness of MKBSC for finding knowledge-based strate- gies for pursuit-evasion games by analyzing the generated graph by hand and extracting useful information from it. It was found that in general it is difficult to find the best knowledge-based strategies for pursuit-evasion games by hand with a non-symbolic representation of the game. This is mainly due to the fact that the sizes of the expanded graphs tended to be very large. It is pos- sible that MKBSC can be useful for finding knowledge-based strategies for pursuit-evasion games with the use of symbolic representations of the game or by algorithmically finding the strategies based on the generated graphs.<br>Många situationer kan beskrivas som spel på ändliga grafer bestående av en mängd agenter som utför sammansatta handlingar som påverkar spelets till- stånd. En klass sådana spel är de så kallade jaktflyktspelen, där en mängd jägare försöker fånga en flykting på en ändlig spelplan. I vissa jaktflyktspel där flyktingens position är okänd för jägarna kan det vara svårt att hitta en strategi som försäkrar vinst för jägarna. En metod för att förenkla detta är genom att använda sig av multiplayer knowledge-based subset construction (MKBSC) för att expandera spelgrafen till en expanderad graf som innehåller jägarnas kunskap. I denna rapport undersöker vi användbarheten av MKBSC för att hitta kunskapsbaserade strategier för jaktflyktspel genom att analysera de expanderade graferna för hand och extrahera användbar information från dem. Resultatet var att det generellt sett är svårt att hitta användbara kunskapsbaserade strategier för jaktflyktspel genom att för hand analysera den expanderade grafen med en icke-symbolisk representation av spelet. Detta är huvudsakligen på grund av att storleken på det expanderade spelet tenderar att vara mycket stor. Det är möjligt att MKBSC kan vara användbart för att hitta kunskapsbaserade strategier för jaktflyktspel genom att använda en symbolisk representation av spelet eller genom att söka genom den expanderade grafen med hjälp av algoritmer.
6
Pang, Jing-En. "Pursuit-evasion with acceleration, sensing limitation, and electronic counter measures." Connect to this title online, 2007. http://etd.lib.clemson.edu/documents/1193079487/.
Full text
7
Jiao, Yue, and Ivan Skvortsov. "An optimization approach to the multi-player pursuit-evasion problem." Thesis, KTH, Skolan för teknikvetenskap (SCI), 2017. http://urn.kb.se/resolve?urn=urn:nbn:se:kth:diva-210825.
Full textAbstract:
In this paper a scenario of one evader being chased by multiple pursuers in two specific simulation environments is studied. The simulation environments are divided into an open area without obstacles and a closed area with obstacles. In the open area a fairly accurate system of dynamics are implemented for both pursuers and evader. The Virtual Vehicle Approach is used to provide a reference trajectory for the pursuers to follow in order to catch the evader. The main purpose of this thesis is to find a decentralized robust control method for the dynamics of the pursuers. In the closed area, the line of sight and field of view are introduced and the solution to the Minimum time UGV surveillance problem and the Centroidal Voronoi partitions. Different capturing strategies, encirclement and one-on-one chase, are both studied and compared. The numerical implementation and the resulting simulation are presented and analyzed. Conclusion on the optimal formation for the multiple pursuers is made.
8
Hermansson, Richard, and Eric Peldan. "Pursuit and Evasion in Polygonal Environments - A Mixed Integer Linear Programming Approach." Thesis, KTH, Optimeringslära och systemteori, 2011. http://urn.kb.se/resolve?urn=urn:nbn:se:kth:diva-105763.
Full textAbstract:
This report addresses improvements to an already existent model of a Pursuit-and-Evasion problem. The model is formulated using Mixed Integer Linear Programming (MILP). The computation time of the original model is first thoroughly examined by solving for increasingly large areas, and with a varying number of pursuers. Some improvements to the model are suggested for shortening the computation time. Finally, a new model is suggested with the aims of being more realistic and to address an issue in the original model that meant that pursuers must not share tiles (i.e they must stay separated at all times).<br>Denna rapport introducerar förbättringar till en existerande modell av ett Pursuit-And- Evasion problem. Modellen är formulerad med hjälp av Mixed Integer Linear Programming (MILP). Först testas lösningstiden för originalmodellen utförligt på större och större områden, och med olika antal sökare. Några förbättringar föreslås för att förkorta beräkningstiden, och sedan föreslås även en helt ny modell. Syftet med den nya modellen är att den ska vara mer realistisk, och dessutom så försöker den åtgärda ett problem i originalmodellen som gör att sökare inte får stå för nära varandra.
9
Grimm, Christopher Lee Jr. "A tensor-train-decomposition-based algorithm for high-dimensional pursuit-evasion games." Thesis, Massachusetts Institute of Technology, 2016. http://hdl.handle.net/1721.1/105615.
Full textAbstract:
Thesis: S.M., Massachusetts Institute of Technology, Department of Aeronautics and Astronautics, 2016.<br>Cataloged from PDF version of thesis.<br>Includes bibliographical references (pages 99-100).<br>The research presented in this thesis was inspired by an interest in determining feedback strategies for high-dimensional pursuit-evasion games. When a problem is high-dimensional or involves a state space that is defined by several variables, various methods used to solve pursuit-evasion games often require unrealistic computation time. This problem, called the curse of dimensionality, can be mitigated under certain circumstances by utilizing tensor-train (TT) decomposition. By using this intuition, a new algorithm for solving high dimensional pursuit-evasion problems called Best-Response Tensor-Train-decomposition-based Value Iteration (BR-TT-VI) was developed. BR-TT-VI builds on concepts from game theory, dynamic programming (DP), and tensor-train decomposition. By using TT decomposition, BR-TT-VI greatly reduces the effects of the curse of dimensionality. This work culminates in the application of BR-TT-VI to two different pursuit-evasion problems. First, a four-dimensional problem capable of being solved by traditional value iteration(VI) is tackled by the BR-TT-VI algorithm. This problem allows a direct comparison between VI and BR-TT-VI to demonstrate the reduced computational time of the new algorithm. Finally, BR-TT-VI is used to solve a six-dimensional problem involving two Dubins vehicles that is impractical to solve with VI.<br>by Christopher Lee Grimm Jr.<br>S.M.
10
Phillpot, John. "Line-of-Sight Pursuit and Evasion Games on Polytopes in R^n." Scholarship @ Claremont, 2016. https://scholarship.claremont.edu/hmc_theses/80.
Full textAbstract:
We study single-pursuer, line-of-sight Pursuit and Evasion games in polytopes in $\mathbb{R}^n$. We develop winning Pursuer strategies for simple classes of polytopes (monotone prisms) in Rn, using proven algorithms for polygons as inspiration and as subroutines. More generally, we show that any Pursuer-win polytope can be extended to a new Pursuer-win polytope in more dimensions. We also show that some more general classes of polytopes (monotone products) do not admit a deterministic winning Pursuer strategy. Though we provide bounds on which polytopes are Pursuer-win, these bounds are not tight. Closing the gap between those polytopes known to be Pursuer-win and those known not to be remains an problem for future researchers.
11
Goode, Brian Joseph. "A State Space Partitioning Scheme for Vehicle Control in Pursuit-Evasion Scenarios." Diss., Virginia Tech, 2011. http://hdl.handle.net/10919/40266.
Full textAbstract:
Pursuit-evasion games are the subject of a variety of research initiatives seeking to provide some level of autonomy to mobile, robotic vehicles with on-board controllers. Applications of these controllers include defense topics such as unmanned aerial vehicle (UAV) and unmanned underwater vehicle (UUV) navigation for threat surveillance, assessment, or engagement. Controllers implementing pursuit-evasion algorithms are also used for improving everyday tasks such as driving in traffic when used for collision avoidance maneuvers.
Currently, pursuit-evasion tactics are incorporated into the control by solving the Hamilton-Jacobi-Isaacs (HJI) equation explicitly, simplifying the solution using approximate dynamic programming, or using a purely finite-horizon approach. Unfortunately, these methods are either subject to difficulties of long computational times or having no guarantees of succeeding in the pursuit-evasion game. This leads to more difficulties of implementing these tactics on-line in a real robotic scenario where the opposing agent may not be known before the maneuver is required.
This dissertation presents a novel method of solving the HJI equation by partitioning the state space into regions of local, finite horizon control laws. As a result, the HJI equation can be reduced to solving the Hamilton-Jacobi-Bellman equation recursively as information is received about an opposing agent. Adding complexity to the problem structure results in a decreased calculation time to allow pursuit-evasion tactics to be calculated on-board an agent during a scenario. The algorithms and implementation methods are given explicitly and illustrated with an example of two robotic vehicles in a collision avoidance maneuver.<br>Ph. D.
12
Blumenberg, Felix, Mats Malmberg, and Fredrik Båberg. "A Heuristic Approach to the Multiagent Pursuit and Evasion Problem in Polygonal Enviroments." Thesis, KTH, Optimeringslära och systemteori, 2011. http://urn.kb.se/resolve?urn=urn:nbn:se:kth:diva-105488.
Full textAbstract:
In this paper heursitic algorithms are developed for the pursuit evasion problem in polygonal enviroments. In this problem, continuous trajectories shall be constructed for a group of pursuers, searching for an evader, in such a way that the evader is guaranteed to be seen at some time during the search. Three fundamentaly dierent heuristic methods are considered: tabu search, genetic algorithms and greedy methods. The result is three heuristic algorithms. Two algorithms are readily implemented in ANSI C, yielding solutions of high quality compared to previous work. The report attains and evaluates statistics on runtime of the algorithms. The algorithms are compared considering the quality and e-ciency for a vast amount of randomly generated enviroments. Key-words : Pursuit and Evasion, Heuristic algorithms, tabu search, greedy methods, genetic algorithms.<br>I detta arbete utvecklas heuristiska algoritmer för ett avsökningsproblem i polygonmiljöer med mobila robotar. Problemet består i att konstruera kontinuerliga banor för en grupp av robotar, sökande efter en inkräktare, så att inkräktaren garanterat blir sedd vid någon tidpunkt under sökningen. Tre i grunden olika heuristiska metoder behandlas för att skapa algoritmer: tabusökning, genetiska algoritmer och giriga metoder. Resultatet är tre algoritmer, varav två har implementerats i ANSI C, som snabbt ger lösningar av hög kvalitet jämfört med tidigare arbete. Statistik på körtider och lösningskvalitet för ett stort antal slumpmässigt genererade områden har tagits fram och utvärderats. Nyckelord : Pursuit and evasion, sökalgoritmer, Heuristiska algoritmer, tabu, giriga metoder, genetiska algoritmer.
13
Shedied, Samy Aly. "Optimal Control for a Two Player Dynamic Pursuit Evasion Game; The Herding Problem." Diss., Virginia Tech, 2002. http://hdl.handle.net/10919/26110.
Full textAbstract:
In this dissertation we introduce a new class of pursuit-evasion games; the herding problem. Unlike regular pursuit evasion games where the pursuer aims to hunt the evader the objective of the pursuer in this game is to drive the evader to a certain location on the x-y grid. The dissertation deals with this problem using two different methodologies. In the first, the problem is introduced in the continuous-time, continuous-space domain. The continuous time model of the problem is proposed, analyzed and we came up with an optimal control law for the pursuer is obtained so that the evader is driven to the desired destination position in the x-y grid following the local shortest path in the Euler Lagrange sense. Then, a non-holonomic realization of the two agents is proposed. In this and we show that the optimal control policy is in the form of a feedback control law that enables the pursuer to achieve the same objective using the shortest path.
The second methodology deals with the discrete model representation of the problem. In this formulation, the system is represented by a finite di-graph. In this di-graph, each state of the system is represented by a node in the graph. Applying dynamic programming technique and shortest path algorithms over the finite graph representing the system, we come up with the optimal control policy that the pursuer should follow to achieve the desired goal. To study the robustness, we formulate the problem in a stochastic setting also. We analyze the stochastic model and derive an optimal control law in this setting. Finally, the case with active evader is considered, the optimal control law for this case is obtained through the application of dynamic programming technique.<br>Ph. D.
14
Reimann, Johan Michael. "Using Multiplayer Differential Game Theory to Derive Efficient Pursuit-Evasion Strategies for Unmanned Aerial Vehicles." Diss., Georgia Institute of Technology, 2007. http://hdl.handle.net/1853/16151.
Full textAbstract:
In recent years, Unmanned Aerial Vehicles (UAVs) have been used extensively in military conflict situations to execute intelligence, surveillance and reconnaissance missions. However, most of the current UAV platforms have limited collaborative capabilities, and consequently they must be controlled individually by operators on the ground. The purpose of the research presented in this thesis is to derive algorithms that can enable multiple UAVs to reason about the movements of multiple ground targets and autonomously coordinate their efforts in real-time to ensure that the targets do not escape. By improving the autonomy of multivehicle systems, the workload placed on the command and control operators is reduced significantly.
To derive effective adversarial control algorithms, the adversarial scenario is modeled as a multiplayer differential game. However, due to the inherent computational complexity of multiplayer differential games, three less computationally demanding differential pursuit-evasion game-based algorithms are presented. The purpose of the algorithms is to quickly derive interception strategies for a team of autonomous vehicles. The algorithms are applicable to scenarios with different base assumptions, that is, the three algorithms are meant to complement one another by addressing different types of adversarial problems.
15
Swanson, Brian A. "Solving a Single-Pursuer, Dual-Evader Pursuit-Evasion Differential Game and Analogous Optimal Control Problems." University of Cincinnati / OhioLINK, 2020. http://rave.ohiolink.edu/etdc/view?acc_num=ucin1595247361709163.
Full text
16
Fredriksson, Bastian, and Edvin Lundberg. "The Monk Problem : Verifier, heuristics and graph decompositions for a pursuit-evasion problem with a node-located evader." Thesis, KTH, Skolan för datavetenskap och kommunikation (CSC), 2015. http://urn.kb.se/resolve?urn=urn:nbn:se:kth:diva-166442.
Full textAbstract:
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.<br>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.
17
Theodorakopoulos, Panagiotis. "Suivi de cibles terrestres par des drones." Phd thesis, Université Paul Sabatier - Toulouse III, 2009. http://tel.archives-ouvertes.fr/tel-00392776.
Full textAbstract:
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.
18
Park, Jaeyong. "Safe Controller Design for Intelligent Transportation System Applications using Reachability Analysis." The Ohio State University, 2013. http://rave.ohiolink.edu/etdc/view?acc_num=osu1366201401.
Full text
19
Gonçalves, Antônio Renato Cruz. "Problema de perseguição-evasão baseado em random walk." Universidade Federal de Sergipe, 2016. https://ri.ufs.br/handle/riufs/5023.
Full textAbstract:
Coordenação de Aperfeiçoamento de Pessoal de Nível Superior - CAPES<br>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.<br>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.
20
Pardo, Soares Ronan. "Jeux de poursuite-évasion, décompositions et convexité dans les graphes." Phd thesis, Université Nice Sophia Antipolis, 2013. http://tel.archives-ouvertes.fr/tel-00908227.
Full textAbstract:
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.
21
Cheung, Warren A. "Constrained pursuit-evasion problems in the plane." Thesis, 2005. http://hdl.handle.net/2429/16494.
Full textAbstract:
In pursuit-evasion problems, we are presented with one or more pursuers attempting
to capture one or more evaders. We consider pursuers and evaders limited by
a maximum speed moving in the two-dimensional plane with obstacles. We then
investigate two problems in this domain. In the first, where we are given the starting
configuration of pursuers and evaders, we identify all possible paths by the evaders
that are not intercepted by pursuers, and the points reachable by the evaders before
the pursuers by following these paths. In the second problem, we consider a
pursuer forced to maintain visibility with an evader. We construct an example that
demonstrates there exists, in addition to the two standard outcomes of the pursuer
capturing the evader and the evader losing sight of the pursuer, a third tie outcome,
where the pursuer never loses sight of the evader, but the evader can also avoid capture
indefinitely. We give the conditions under which each of these three outcomes
occur for our specific situation.<br>Science, Faculty of<br>Computer Science, Department of<br>Graduate
22
Chu, Hung-Jen, and 朱弘仁. "Variational Approach to Pursuit-Evasion Game with Curvature Constraint." Thesis, 2000. http://ndltd.ncl.edu.tw/handle/14808079096316850024.
Full textAbstract:
博士<br>國立中山大學<br>電機工程學系研究所<br>88<br>In this thesis, a pursuit-evasion game, in which the pursuer moves with simple motion whereas the evader moves at a fixed speed but with a curvature constraint, is investigated. The game is the inverse of the usual homicidal chauffeur game. Square of the distance between the pursuer and the evader when the game is terminated is selected as the cost function. To solve such a zero-sum game, the variational approach will be employed to solve the problem. An algorithm will be proposed to determine a saddle point and the value of the game under consideration
23
Parish, III Allen S. "Pursuit and evasion games: semi-direct and cooperative control methods." 2008. http://hdl.handle.net/1969.1/ETD-TAMU-2668.
Full textAbstract:
Pursuit and evasion games have garnered much research attention since the
class of problems was first posed over a half century ago. With wide applicability to
both civilian and military problems, the study of pursuit and evasion games showed
much early promise. Early work generally focused on analytical solutions to games
involving a single pursuer and a single evader. These solutions generally assumed simple system dynamics to facilitate convergence to a solution. More recently, numerical
techniques have been utilized to solve more difficult problems. While many sophisticated numerical tools exist for standard optimization and optimal control problems,
developing a more complete set of numerical tools for pursuit and evasion games is
still a developing topic of research.
This thesis extends the current body of numeric solution tools in two ways.
First, an existing approach that modifies sophisticated optimization tools to solve
two player pursuer and evasion games is extended to incorporate a class of state
inequality constraints. Several classical problems are solved to illustrate the e±cacy
of the new approach. Second, a new cooperation metric is introduced into the system
objective function for multi-player pursuit and evasion games. This new cooperation
metric encourages multiple pursuers to surround and then proceed to capture an
evader. Several examples are provided to demonstrate this new cooperation metric.
24
Lee, Fang-Wen, and 李方雯. "Using Cognitive Behavioral Learning in Multi-Agent Pursuit-Evasion Game." Thesis, 2014. http://ndltd.ncl.edu.tw/handle/32rmqn.
Full textAbstract:
碩士<br>國立臺北科技大學<br>資訊工程系研究所<br>102<br>Multi-Agent system use learning to make the best response action is a challenging problem in a dynamic environment. This study use probabilistic formulation and Piaget‘s schema theory to develop Cognitive Behavioral Learning in a dynamic environment of pursuit-evasion game. We divide Piaget''s original schema into two parts; one is a perceptional schema and the other is an intentional schema. According to the agent’s state(search evader、individual learning、cooperative learning), Intentional schema proposes three strategy and uses probabilistic formulation to guess the evader’s position in next time steps; Perceptional schema use case base to save the agent’s state before action、action、state after action. When an agent faces a new situation, it might use assimilation to address the situation. If the current cognitive structure cannot explain the environment, Accommodation refers to the realization that the current structure is insufficient for ad-equate understanding of the world and that they must be changed until it can be assimilated. This study used the Recursive Porous Agent Simulation Toolkit (Repast) as the agent platform for implementing a multiagent system to demonstrate the proposed approach for the pursuit-evasion game.
25
Hsu, Chien-Feng, and 徐健峰. "Applying Assimilation and Accommodation for Cooperative Learning of Multi-Agent Pursuit-Evasion Strategies." Thesis, 2010. http://ndltd.ncl.edu.tw/handle/tx2xe8.
Full textAbstract:
碩士<br>國立臺北科技大學<br>資訊工程系研究所<br>98<br>This paper examines the problem of coordinating multiple robotic pursuers in locating and tracking a non-adversarial mobile evader in a dynamic environment. We have proposed two kinds of pursue strategies. One is for agents cooperate with one another. The other is for agents do not cooperate with each other. We consider the uncertain state information of the pursuers and the evaders, and we use a probabilistic formulation of the pursuit-evasion problem. We apply Case-based Reasoning to equip agents with memory and learning ability, and then we use the methods of positive-angle strategy and bevel-angle strategy based on the concept of Piaget’s assimilation and accommodation to let agents be able to adapt to environment easily and effectively.
We demonstrate our approach by a pursuit-evasion game, and then we use Repast (The Recursive Porous Agent Simulation Toolkit) as the agent platform to implement our multi-agent system.
26
Hsu, Jia-Lin, and 許嘉麟. "Using Reinforcement Learning and Case-Based Reasoning in Multi-Agent Pursuit-Evasion Game." Thesis, 2011. http://ndltd.ncl.edu.tw/handle/22asfc.
Full textAbstract:
碩士<br>國立臺北科技大學<br>資訊工程系研究所<br>99<br>In multi-agent pursuit-evasion game, pursuers need to coordinate the behavior of each other to achieve a common goal, catching the evader. In this paper, we propose a learning mechanism of capture in a dynamic environment of pursuit-evasion game. We deal with uncertainty in environment by using training and divide into two different ways of learning by cooperation or not. One is individual learning and the other is case-based reasoning. Therefore, agents can have memory and learning ability, so can catch evader more quickly. We demonstrate our approach by a pursuit-evasion game, and then we use Repast (The Recursive Porous Agent Simulation Toolkit) as the agent platform to implement our multi-agent system.
27
Rodriguez, Samuel Oscar. "Roadmap-Based Techniques for Modeling Group Behaviors in Multi-Agent Systems." Thesis, 2012. http://hdl.handle.net/1969.1/ETD-TAMU-2012-05-10796.
Full textAbstract:
Simulating large numbers of agents, performing complex behaviors in realistic environments is a difficult problem with applications in robotics, computer graphics and animation. A multi-agent system can be a useful tool for studying a range of situations in simulation in order to plan and train for actual events. Systems supporting such simulations can be used to study and train for emergency or disaster scenarios including search and rescue, civilian crowd control, evacuation of a building, and many other training situations.
This work describes our approach to multi-agent systems which integrates a roadmap-based approach with agent-based systems for groups of agents performing a wide range of behaviors. The system that we have developed is highly customizable and allows us to study a variety of behaviors and scenarios. The system is tunable in the kinds of agents that can exist and parameters that describe the agents. The agents can have any number of behaviors which dictate how they react throughout a simulation. Aspects that are unique to our approach to multi-agent group behavior are the environmental encoding that the agents use when navigating and the extensive usage of the roadmap in our behavioral framework. Our roadmap-based approach can be utilized to encode both basic and very complex environments which include multi- level buildings, terrains and stadiums.
In this work, we develop techniques to improve the simulation of multi-agent systems. The movement strategies we have developed can be used to validate agent movement in a simulated environment and evaluate building designs by varying portions of the environment to see the effect on pedestrian flow. The strategies we develop for searching and tracking improve the ability of agents within our roadmap-based framework to clear areas and track agents in realistic environments.
The application focus of this work is on pursuit-evasion and evacuation planning. In pursuit-evasion, one group of agents, the pursuers, attempts to find and capture another set of agents, the evaders. The evaders have a goal of avoiding the pursuers. In evacuation planning, the evacuating agents attempt to find valid paths through potentially complex environments to a safe goal location determined by their environmental knowledge. Another group of agents, the directors may attempt to guide the evacuating agents. These applications require the behaviors created to be tunable to a range of scenarios so they can reflect real-world reactions by agents. They also potentially require interaction and coordination between agents in order to improve the realism of the scenario being studied. These applications illustrate the scalability of our system in terms of the number of agents that can be supported, the kinds of realistic environments that can be handled, and behaviors that can be simulated.
28
Mehrabian, Abbas. "Cops and Robber Game with a Fast Robber." Thesis, 2011. http://hdl.handle.net/10012/5821.
Full textAbstract:
Graph searching problems are described as games played on graphs, between a set of searchers and a fugitive. Variants of the game restrict the abilities of the searchers and the fugitive and the corresponding search number (the least number of searchers that have a winning strategy) is related to several well-known parameters in graph theory. One popular variant is called the Cops and Robber game, where the searchers (cops) and the fugitive (robber) move in rounds, and in each round they move to an adjacent vertex. This game, defined in late 1970's, has been studied intensively. The most famous open problem is Meyniel's conjecture, which states that the cop number
(the minimum number of cops that can always capture the robber) of a connected graph
on n vertices is O(sqrt n).
We consider a version of the Cops and Robber game, where the robber is faster than the cops, but is not allowed to jump over the cops. This version was first studied in 2008.
We show that when the robber has speed s,
the cop number of a connected n-vertex graph can be as large as Omega(n^(s/s+1)). This improves the Omega(n^(s-3/s-2)) lower bound of Frieze, Krivelevich, and Loh (Variations on Cops and Robbers, J. Graph Theory, to appear). We also conjecture a general upper bound O(n^(s/s+1)) for the cop number,
generalizing Meyniel's conjecture.
Then we focus on the version where the robber is infinitely fast, but is again not allowed to jump over the cops. We give a mathematical characterization for graphs with cop number one. For a graph with treewidth tw and maximum degree Delta,
we prove the cop number is between (tw+1)/(Delta+1) and tw+1. Using this we show that the cop number of the m-dimensional hypercube is
between c1 n / m sqrt(m) and c2 n / m for some constants c1 and c2. If G is a connected interval graph on n vertices, then we give a polynomial time 3-approximation algorithm for finding the cop number of G, and prove that the cop number is O(sqrt(n)).
We prove that given n, there exists a connected chordal graph on n vertices
with cop number Omega(n/log n). We show a lower bound for the cop numbers of expander graphs, and use this to prove that the random G(n,p) that is not very sparse,
asymptotically almost surely has cop number between d1 / p and d2 log (np) / p for suitable constants d1 and d2. Moreover, we prove that a fixed-degree regular random graph with n vertices asymptotically almost surely has cop number Theta(n).
29
Lau, George Tin Lam. "Path Planning Algorithms for Autonomous Border Patrol Vehicles." Thesis, 2012. http://hdl.handle.net/1807/33303.
Full textAbstract:
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.
30
Sun, Andrew. "Cooperative UAV Search and Intercept." Thesis, 2009. http://hdl.handle.net/1807/17716.
Full textAbstract:
In this thesis, a solution to the multi-Unmanned Aerial Vehicle (UAV) search and intercept problem for a moving target is presented. For the search phase, an adapted diffusion-based algorithm is used to manage the target uncertainty while individual UAVs are controlled with a hybrid receding horizon / potential method. The coordinated search is made possible by an uncertainty weighting process. The team intercept phase algorithm is a behavioural approach based on the analytical solution of Isaac's Single-Pursuer/Single-Evader (SPSE) homicidal chau ffeur problem. In this formulation, the intercepting control is taken to be a linear combination of the individual SPSE controls that would exist for each of the evader/pursuer pairs. A particle swarm optimizer is applied to find approximate optimal weighting coefficients for discretized intervals of the game time. Simulations for the team search, team intercept and combined search and intercept problem are presented.
31
Chung, Chern Ferng Mechanical & Manufacturing Engineering Faculty of Engineering UNSW. "Reachable sets analysis in the cooperative control of pursuer vehicles." 2008. http://handle.unsw.edu.au/1959.4/41525.
Full textAbstract:
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.