No description available.

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

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.

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).

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).

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. / Ph. D.

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. / Ph. D.

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. / <p>QC 20140327</p>

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.

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.