Optimal search in structured environments

Lau, Haye

Optimal search in structured environments

Lau, Haye

Permalink

Publication Type:: Thesis
Issue Date:: 2007

Closed Access

	Filename	Description	Size
	01Front.pdf	contents and abstract	619.47 kB	Adobe PDF	View/Open
	02Whole.pdf	thesis	93.18 MB	Adobe PDF	View/Open

Copyright Clearance Process

Recently Added
In Progress
Closed Access

This item is closed access and not available.

Full metadata record

Field	Value	Language
dc.contributor.author	Lau, Haye
dc.date.accessioned	2016-11-07T22:21:20Z
dc.date.available	2016-11-07T22:21:20Z
dc.date.issued	2007
dc.identifier.uri	http://hdl.handle.net/10453/60357
dc.description	University of Technology, Sydney. Faculty of Engineering.	en_AU
dc.description	NO FULL TEXT AVAILABLE. Access is restricted indefinitely. The hardcopy may be available for consultation at the UTS Library.
dc.description.abstract	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.	en_AU
dc.format	Thesis (PhD)
dc.language.iso	en_AU	en_AU
dc.rights	The author owns the copyright in this thesis including all reproduction and reuse rights for the work. The work may not be altered without the permission of the copyright owner. Attribution is essential when quoting or paraphrasing from this thesis.
dc.rights	info:eu-repo/semantics/closedAccess
dc.title	Optimal search in structured environments	en_AU
dc.type	Thesis	en_AU
utslib.copyright.status	closed_access

Abstract:

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:

http://hdl.handle.net/10453/60357