Optimal search in structured environments
- Publication Type:
- Thesis
- Issue Date:
- 2007
Closed Access
Filename | Description | Size | |||
---|---|---|---|---|---|
01Front.pdf | contents and abstract | 619.47 kB | |||
02Whole.pdf | thesis | 93.18 MB |
Copyright Clearance Process
- Recently Added
- In Progress
- Closed Access
This item is closed access and not available.
NO FULL TEXT AVAILABLE. Access is restricted indefinitely. ----- This thesis is concerned with the development of optimal search techniques to
find a target in a structured environment. It is necessary in many rescue and security
applications for the responders to efficiently find and reach the phenomena of interest.
Although the target location is by definition not precisely known, it is nevertheless
imperative to make the best use of any available information.
Given a known area described as a set of connected regions, a prior belief on the
target location and a model of likely target motion, the underlying task addressed is to
determine the best paths for the one or more searchers to follow to maximise their
effectiveness. As the most related problem discussed in literature, the Optimal Searcher
Path (OSP) problem, assumes that the searcher can instantly relocate between regions,
one of the main contributions in this thesis is an extension to the OSP problem to deal
with the more realistic scenario where a searcher needs a finite time to physically travel
from one region to another.
This work first considers the search of an indoor environment for a stationary
target with the aim of minimising the expected time to detection. A dynamic
programming approach is used to find an optimal ordering of regions to inspect. The
proposed technique is also extended to the search for multiple targets.
Secondly, for maximising the probability of detecting a moving target in a
structured environment, the more general Optimal Searcher Path Problem with non-uniform
Travel times (OSPT) is formulated. A key contribution is a branch and bound
solution approach with a new bounding technique, the Discounted MEAN bound, which
also provides much tighter bounds for the OSP problem compared to existing methods.
As this improvement is gained with almost no increase in computational time, optimal
search paths can thus be feasibly derived for longer time horizons.
Finally, a multi-agent problem where the searchers are aided by scouts that can
help find but not rescue the target is considered. Envisaged applications include firefighters
(searchers) entering a building with a number of scouting robots. While the
process terminates as soon as a searcher finds the target, successful scout detections can
only improve on the knowledge available to guide future searches. The solution
framework must therefore plan not only to maximise the probability of the searchers
directly finding the target, but also put them in the best position to exploit any new
information obtained from detections by scouts. It is shown that the problem can be
partitioned into a series of modified OSP problems, through which the complete set of
paths necessitated by each possible scout detection (and non-detection) can be obtained.
Optimal and heuristic solutions to this problem are presented.
Please use this identifier to cite or link to this item: