Clear the building: Pursuit-evasion with limited field of view

Brian Gerkey

http://robotics.stanford.edu/~gerkey/

Stanford Robotics Laboratory

(with Sebastian Thrun)

Note: most of the notes are copied from the bullets on the presentation slides as the presentation was going very quickly.

Problem: coordinate the motions of a team of searchers through a given

environment so as to locate one or more evaders

Application: building security, search and rescue, hazardous spill

cleanup

Many variables:

* Environment:

- discrete graph

- continuous polygonal tree space

* Searcher visibility:

- immediate location

- k flashlights

- omni-directional vision

- limited field of view **

* Evader motion

- bounded velocity

- known policy (brownian motion, move away from pursuers)

- infinite velocity (worst case) **

* Performance metric

- minimize time to capture

- minimize travel distance to capture

- maximize likelihood of capture

- guarantee capture **

(** chosen for this study)

#### Parson's problem:

- a spelunker (target) is lost in a nework of caves. how should a search party find her

- she moves continiuously, but arbitrarily fast, and no model of her motion is available

- discrete graph formulation

- graph is initially contaminated

- goal is to clear all edges

- if an edge that was clear is now contaminated, it is called recontam

- finding the min number of searchers required is NP-hard (Meggido)

- recontamination is unnecessary (Lapaugh)

- a hard problem, where coordination matters

#### The polygon search problem: (Suzuki and Yamashita)

- with one searcher, search a given polygonal free space for a target the moves contiunously, but arbitrarily fast

- the k-sarcher has k flashlights (rays) that can be independently rotated at bounded speed about the searcher

#### Analysis of k-searcher:

- polynomial time algorithms exist for constructing a tour for the 1-searcher and the 2-searcher - any searachable polyugon is searchable by a 2-searcher, i.e. 2-searcher is equivalent to an infinity-searcher (omni-directional)#### The infinity-searcher:(Guibas)

- computing min number of searchers, H(F), for a given pologyn f is NP-hard - complete algorithm for one searcher when H(F) = 1#### Limited field of view

- many robots have limited-FOV sensors. limited-FOV sensors are cheaper ($60 camera versus $5000 laser) - algorithms for the k-searcher and infinity-searcher will not suffice - introducning a new class of searcher: the phi-searcher#### The phi-searcher:

- omni-directional mobile base - has a sensor with OFV of phi radians and unlimited range - when phi=2pi, it's an inifnity searcher - as phi->1, it's a 1-searcher - one phi-searcher can search an environment only if it is simply-connected (no holes/loops) - in general, it's between a 1-searcher and a 2-searcher#### Problem definition:

- given a connected polygonal free space F and N phi-searchers (same FOV) - let T(t) denote pos of target - let Si(t) denote pos of ith searcher - for all points q in F, let Vphi(p) denote set of points visible from p#### Complexity of general problem:

- min number of phi-searchers is NP-hard#### Critical boundaries

- need to identify places where critical changes occur in the topology of the contaminated space - simple ray-casting from infinity-searcher finds boundaries - occurs when set of corners in view changesPartition space along critical boundaries, not taking into account limitied FOV

#### Visibility curve:

- arc along with two verticies can remain in view to a phi-searcher

- as phi->pi, arcs flatten into straight line

#### Approach:

Refine partition space using visibility curvesBorders are good: can only gain visibility at borders

Intersections are good as well

For planning path, move along borders/intersections

Construct graph encoding the transitions in the information state

- search graph for goal state using favorite graph search

CGAL - good geometric computation library

When phi=pi, roadmap consists of linear objects, can use rational

instead of real numbers for more efficient implementation.

Greedy algorithms don't work, sometimes have to given up space

Can extend to multiple robots

- naive approach makes search exponential in number of searchers

- completeness is lost

- Single robot cannot clear a loop