Let D be a Jordan domain in the plane. We consider a pursuit-evasion, contamination clearing, or sensor sweep problem in which the pursuer at each point in time is modeled by a continuous curve, called the sensor curve. Both time and space are continuous, and the intruders are invisible to the pursuer. Given D, what is the shortest length of a sensor curve necessary to provide a sweep of domain D, so that no continuously-moving intruder in D can avoid being hit by the curve? We define this length to be the sweeping cost of D. We provide an analytic formula for the sweeping cost of any Jordan domain in terms of the geodesic Frechet distance between two curves on the boundary of D with non-equal winding numbers. As a consequence, we show that the sweeping cost of any convex domain is equal to its width, and that a convex domain of unit area with maximal sweeping cost is the equilateral triangle.
In a pursuit-evasion game, a team of pursuers attempt to capture an evader. The players alternate turns, move with equal speed, and have full information about the state of the game. We consider the most restrictive capture condition: a pursuer must become colocated with the evader to win the game. We prove two general results about this adversarial motion planning problem in geometric spaces. First, we show that one pursuer has a winning strategy in any compact CAT(0) space. This complements a result of Alexander, Bishop and Ghrist, who provide a winning strategy for a game with positive capture radius. Second, we consider the game played in a compact domain in Euclidean two-space with piecewise analytic boundary and arbitrary Euler characteristic. We show that three pursuers always have a winning strategy by extending recent work of Bhadauria, Klein, Isler and Suri from polygonal environments to our more general setting. This paper describes decentralized control laws for the coordination of multiple vehicles performing spatially distributed tasks. The control laws are based on a gradient descent scheme applied to a class of decentralized utility functions that encode optimal coverage and sensing policies. These utility functions are studied in geographical optimization problems and they arise naturally in vector quantization and in sensor allocation tasks. The approach exploits the computational geometry of spatial structures such as Voronoi diagrams. Previous work on the coverage of mobile sensor networks focuses on algorithms to reposition sensors in order to achieve a static configuration with an enlarged covered area. In this paper, we study the dynamic aspects of the coverage of a mobile sensor network that depend on the process of sensor movement. As time goes by, a position is more likely to be covered; targets that might never be detected in a stationary sensor network can now be detected by moving sensors. We characterize the area coverage at specific time instants and during time intervals, as well as the time it takes to detect a randomly located stationary target. Our results show that sensor mobility can be exploited to compensate for the lack of sensors and improve network coverage. For mobile targets, we take a game theoretic approach and derive optimal mobility strategies for sensors and targets from their own perspectives. We study the problem of a mobile target (the mouse) trying to evade detection by one or more mobile sensors (we call such a sensor a cat) in a closed network area. We view our problem as a game between two players: the mouse, and the collection of cats forming a single (meta-)player. The game ends when the mouse falls within the sensing range of one or more cats. A cat tries to determine its optimal strategy to minimize the worst case expected detection time of the mouse. The mouse tries to determine an optimal counter movement strategy to maximize the expected detection time. We divide the problem into two cases based on the relative sensing capabilities of the cats and the mouse. When the mouse has a sensing range smaller than or equal to the cats', we develop a dynamic programming solution for the mouse's optimal strategy, assuming high level information about the cats' movement model. We discuss how the cats' chosen movement model will affect its presence matrix in the network, and hence its payoff in the game. When the mouse has a larger sensing range than the cats, we show how the mouse can determine its optimal movement strategy based on local observations of the cats' movements. We further present a coordination protocol for the cats to collaboratively catch the mouse by: 1) forming opportunistically a cohort to limit the mouse's degree of freedom in escaping detection; and 2) minimizing the overlap in the spatial coverage of the cohort's members. Extensive experimental results verify and illustrate the analytical results, and evaluate the game's payoffs as a function of several important system parameters. This papers surveys some of the work done on trying to capture an intruder in a graph. If the intruder may be located only at vertices, the term searching is employed. If the intruder may be located at vertices or along edges, the term sweeping is employed. There are a wide variety of applications for searching and sweeping. Old results, new results and active research directions are discussed.   Given a lion and a man, their initial positions, and restrictions on their ranges and speeds, how quickly can the lion get within a given distance from the man? We consider the case in which the lion and man are restricted to the interior of a circle and each is limited to the same speed. INFORMS Journal on Computing , ISSN 1091-9856, was published as ORSA Journal on Computing from 1989 to 1995 under ISSN 0899-1499. This paper surveys recent results in pursuit-evasion and autonomous search relevant to applications in mobile robotics. We provide a taxonomy of search problems that highlights the differences resulting from varying assumptions on the searchers, targets, and the environment. We then list a number of fundamental results in the areas of pursuit-evasion and probabilistic search, and we discuss field implementations on mobile robotic systems. In addition, we highlight current open problems in the area and explore avenues for future work.