
Pursuitevasion with teams of robots
Latest resultsThese videos demonstrate the application of the Conscription algorithm to pursuitevasion, both in simulation and with physical robots. The three panels in each video are: the world (either simulated or physical), the robots' current plans, and the state of the problem.
New videosHere are some videos of teams of robots cooperatively searching indoor environments. These tests were done in simulation using the Stage multirobot simulator, using the Conscription distributed planning algorithm. Details of the algorithm are forthcoming.
We give only a brief summary of the project here. For details and proofs, consult the paper(s). Also, please try the Animations! Overview
We study a form of the pursuitevasion problem, in which one or
more searchers must move through a given environment so as to guarantee
detection of any and all evaders, which can move arbitrarily fast.
Our goal is to develop techniques for coordinating teams of robots to
execute this task in application domains such as clearing a building,
for reasons of security or safety. To this end, we introduce a new
class of searcher, the searcher, which can be readily instantiated
as a physical mobile robot. We present a detailed analysis of the
pursuitevasion problem using searchers. We show that computing
the minimum number of searchers required to search a given
environment is NPhard, and present the first complete search algorithm
for a single searcher. We show how this algorithm can be extended
to handle multiple searchers, and give examples of computed trajectories.
IntroductionIn this project we address a form of the problem known as pursuitevasion. The goal of this problem is to direct the actions of one or more searchers through a given environment in such a way as to guarantee that any evaders present in the environment will be found. As an example, consider the problem of closing a museum for the night. In order to be sure that no thieves or other malcontents remain inside after closing, the guards must perform a thorough search of the building. They must keep in mind that any intruders may try to avoid the guards. For example, if a guard is checking each room along a hall, an intruder might sneak behind the guard while he is checking one room and hide in a room that was already checked. In this case, one solution might be to use two guards, with one always keeping watch on the hall.Our goal is to derive strategies for robots that allow them to play the role of guard. In particular, we are interested in scalable techniques for coordinating the actions of teams of robots to clear entire buildings. We first establish an analytical foundation for studying this problem by introducing the concept of a searcher, which is a robot equipped with a radian field of view (FOV) sensor for detecting evaders. The searcher reflects the realities of physical robots, most of which have limited FOV sensors, and thus the techniques we develop can be applied to robots. Furthermore, the searcher is a qualitatively different kind of searcher from those previously studied in pursuitevasion scenarios, and so warrants the fresh analysis that we present here. After proving that computing the minimum number of searchers required to search an environment is NPhard, we present the first complete search algorithm for the case of one searcher in a known environment. We show how this algorithm can be extended to handle multiple robots (albeit at a loss of completeness). We have implemented and tested this algorithm in a variety of environments and present example solution trajectories. The searcherThe existing body of analytical work on visibilitybased pursuitevasion is concerned with some form of the searcher, and is not readily applicable to physical robots, few of which are equipped with movable flashlights or omnidirectional sensing. Since our target domain is teams of physical robots, we introduce a new class of searcher, which to our knowledge has not yet been studied, and which we call the searcher. The searcher is a holonomic (i.e., omnidirectional drive) mobile robot with a limited FOV sensor having angular aperture . The sensor has unlimited range, but cannot penetrate obstacles. This robot can move (i.e., rotate and/or translate) at bounded speed. When , we have an searcher. For , however, we have a different kind of searcher, with significantly diminished capabilities. Since the sensor's FOV can be freely rotated about the searcher at bounded speed and independently of the searcher's motion (this follows from the holomonicity of the robot), the capabilities of the searcher lie somewhere between those of a 1searcher and those of a 2searcher. Shown in Figure 1 is an example of a searcher, for . Given a connected polygonal free space , the pursuitevasion problem is to find a trajectory through (called a search schedule) for searchers that guarantees detection of an arbitrarily fast evader, whose trajectory and initial location are unknown. Analogously to the graph search problem, any part of where the evader can be hiding is called contaminated and any part of where the evader cannot be hiding is called clear. Whenever there exists a path between contaminated space and clear space, that clear space is said to be recontaminated. The space is initially contaminated and the goal is to clear it. It is known that for the discrete graph search problem, establishing the minimum number of searchers required to search a given graph, known as the search number of the graph, is NPhard. For the visibilitybased version, establishing the minimum number of searchers required to search a given polygonal free space is also NPhard. We have a similar result for searchers:
Theorem 1
Computing the minimum number of searchers required to search a
given polygonal free space is NPhard.
A complete algorithmSince, by Theorem 1, we cannot easily determine the minimum number of searchers required to search a given environment, we focus initially on the case of controlling a single searcher. In this section, we present a complete search algorithm for the case of a single searcher. That is, we are interested in finding a trajectory for a single searcher that will search a given polygonal free space , under the assumption that such a trajectory exists. We address the extension to multiple searchers later.We take inspiration in the design of our algorithm from the work of Guibas et al., who have previously given a complete algorithm for the case of a single searcher. Their algorithm does not suffice for a searcher with , because it does not account for the searcher's limited FOV. However, we borrow from their work in several ways. The basic steps of our algorithm are: (i) by a series of partitions, retract the given free space into a network of curves that represent the visibility constraints induced by the environment and the searcher's FOV; (ii) construct an information graph that encodes the possible information states of the problem as the searcher moves, using the network of intersecting curves as a roadmap; then (iii) search this graph for a goal state, and read the desired trajectory out from the resulting path. The key to this algorithm is identifying the critical points in the environment; it is only by moving through these points that the searcher will change the information state of the problem. Implementation and examplesWe have implemented the algorithm summarized above, using the excellent CGAL computational geometry library. For reasons of efficiency and convenience, our implementation thus far computes trajectories only for the special case of . In this case, the roadmap consists only of linear objects, and so the underlying geometric computation can be done with rational numbers. For , circular arcs are introduced, and the exact computation of their intersections requires the use of arbitrary precision real numbers, which are far slower to work with than rationals. Efficiency concerns aside, the case of is of particular interest and value to roboticists, because a sensor that is commonly found on robots today is a scanning laser rangefinder with a 180degree FOV (e.g., the SICK LMS). So trajectories computed by our implementation can be executed directly on holonomic robots that are equipped with such sensors. Below are some computed examples (click on an image for an animated trajectory), for one and two searchers. In all the figures, yellow areas are currently in view (and thus clear), white areas are clear (but not in view), and gray areas are contaminated. Relevant Publications
