Brian P. Gerkey
Home
CV
Publications
Research
Player/Stage
Tools/Resources
Photo gallery
Adbusting

Pursuit-evasion with teams of robots

Overview

 ----

Introduction

 ----

The $\phi$-searcher

 ----

Algorithm

 ----

Animations

 ----

Publications

Latest results

These videos demonstrate the application of the Conscription algorithm to pursuit-evasion, 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 videos

Here are some videos of teams of robots cooperatively searching indoor environments. These tests were done in simulation using the Stage multi-robot 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 pursuit-evasion 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 $\phi$-searcher, which can be readily instantiated as a physical mobile robot. We present a detailed analysis of the pursuit-evasion problem using $\phi$-searchers. We show that computing the minimum number of $\phi$-searchers required to search a given environment is NP-hard, and present the first complete search algorithm for a single $\phi$-searcher. We show how this algorithm can be extended to handle multiple searchers, and give examples of computed trajectories.

Introduction

In this project we address a form of the problem known as pursuit-evasion. 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 $\phi$-searcher, which is a robot equipped with a $\phi$-radian field of view (FOV) sensor for detecting evaders. The $\phi$-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 $\phi$-searcher is a qualitatively different kind of searcher from those previously studied in pursuit-evasion scenarios, and so warrants the fresh analysis that we present here.

After proving that computing the minimum number of $\phi$-searchers required to search an environment is NP-hard, we present the first complete search algorithm for the case of one $\phi$-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 $\phi$-searcher

The existing body of analytical work on visibility-based pursuit-evasion is concerned with some form of the $k$-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 $\phi$-searcher. The $\phi$-searcher is a holonomic (i.e., omnidirectional drive) mobile robot with a limited FOV sensor having angular aperture $\phi \in (0,2\pi]$. The sensor has unlimited range, but cannot penetrate obstacles. This robot can move (i.e., rotate and/or translate) at bounded speed. When $\phi = 2\pi$, we have an $\infty$-searcher. For $\phi < 2\pi$, 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 $\phi$-searcher lie somewhere between those of a 1-searcher and those of a 2-searcher. Shown in Figure 1 is an example of a $\phi$-searcher, for $\phi = \pi$.

Given a connected polygonal free space $F$, the pursuit-evasion problem is to find a trajectory through $F$ (called a search schedule) for $\phi$-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 $F$ where the evader can be hiding is called contaminated and any part of $F$ 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 $F$ 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 NP-hard. For the visibility-based version, establishing the minimum number of $\infty$-searchers required to search a given polygonal free space is also NP-hard. We have a similar result for $\phi$-searchers:

Theorem 1   Computing the minimum number of $\phi$-searchers required to search a given polygonal free space $F$ is NP-hard.

A complete algorithm

Since, by Theorem 1, we cannot easily determine the minimum number of $\phi$-searchers required to search a given environment, we focus initially on the case of controlling a single $\phi$-searcher. In this section, we present a complete search algorithm for the case of a single $\phi$-searcher. That is, we are interested in finding a trajectory for a single $\phi$-searcher that will search a given polygonal free space $F$, 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 $\infty$-searcher. Their algorithm does not suffice for a $\phi$-searcher with $\phi < 2\pi$, 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 examples

We 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 $\phi = \pi$. In this case, the roadmap consists only of linear objects, and so the underlying geometric computation can be done with rational numbers. For $\phi != \pi$, 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 $\phi = \pi$ is of particular interest and value to roboticists, because a sensor that is commonly found on robots today is a scanning laser range-finder with a 180-degree 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


Last updated $Date: 2004/12/08 16:16:39 $