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 changes

Partition 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 curves

Borders 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

Real-world issues:

- robots have extent (can't be perfectly against a wall), search assumes that robots are points. however, targets have extent as well, and as long as there extent is as great, not a problem. - robots cannot position themselves exactly, can increase tolerance by pretending phi is smaller - real robots usually have learned sensor-based maps - road maps can be more dense than necessary - solutions sometimes involve robots moving backwards; may not want robots to move outside FOV - holonomic constraints are not considered - road maps may involve difficult trajectories - planning in the joint space of multiple searchers is inelegant and intractable