|
Pursuit-evasion with teams of robots
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!
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$](img1.png) -searcher, which can be readily instantiated
as a physical mobile robot. We present a detailed analysis of the
pursuit-evasion problem using ![$\phi$](img1.png) -searchers. We show that computing
the minimum number of ![$\phi$](img1.png) -searchers required to search a given
environment is NP-hard, and present the first complete search algorithm
for a single ![$\phi$](img1.png) -searcher. We show how this algorithm can be extended
to handle multiple searchers, and give examples of computed trajectories.
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 -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 pursuit-evasion 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 NP-hard, 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 existing body of analytical work on visibility-based pursuit-evasion
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 1-searcher and those of a 2-searcher.
Shown in Figure 1 is an example of a -searcher,
for .
Given a connected polygonal free space , the pursuit-evasion 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 NP-hard.
For the visibility-based version, establishing the minimum number of
-searchers required to search a given polygonal free space
is also
NP-hard. We have a similar
result for -searchers:
Theorem 1
Computing the minimum number of -searchers required to search a
given polygonal free space is NP-hard.
Since, 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.
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 . 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 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.
-
"Visibility-based pursuit-evasion with limited field of view".
Brian P. Gerkey,
Sebastian Thrun, and
Geoff Gordon.
To appear in the Intl. J. of Robotics
Research, 2006.
-
"Visibility-based pursuit-evasion with limited field of view".
Brian P. Gerkey,
Sebastian Thrun, and
Geoff Gordon.
In
Proceedings of the National Conference on Artificial Intelligence
(AAAI 2004), pages 20-27,
San Jose, California, July 25 - 29, 2004.
[gzipped PS: 147k]
[PDF: 179k]
|