Publication:
Probabilistic search on optimized graph topologies

Loading...
Thumbnail Image
Authors
Klaus, Christian.
Subjects
Advisors
Date of Issue
2011-09
Date
Publisher
Monterey, California. Naval Postgraduate School
Language
Abstract
This thesis investigates how the performance of a mobile searcher is affected by altering the search environment. We model the search environment as a simple connected, undirected graph. By adding new edges to the graph, we change the search environment. Our objective is to optimize search performance, that is, to minimize the (expected) time needed to find the target, in the context of probabilistic search. We first analyze two different methods to generate random connected graphs, then evaluate a number of methods to augment the graph, typically by considering the algebraic connectivity of the graph and its associated (Fiedler) eigenvector. Extensive simulation studies and resulting statistical and theoretical models show that adding a few wisely chosen edges to a sparse graph is sufficient to dramatically increase search performance. Further, we propose a novel method for incorporating prior information about the target's likely location by defining a subgraph on which the presented approach is performed, resulting in even greater improvements in search performance.
Type
Thesis
Description
Department
Applied Mathematics
Organization
Naval Postgraduate School (U.S.)
Identifiers
NPS Report Number
Sponsors
Funder
Format
xviii, 61 p. ;
Citation
Distribution Statement
Approved for public release; distribution is unlimited.
Rights
This publication is a work of the U.S. Government as defined in Title 17, United States Code, Section 101. Copyright protection is not available for this work in the United States.
Collections