Probabilistic search on optimized graph topologies

Download
Author
Klaus, Christian.
Date
2011-09Second Reader
Chung, Timothy H.
Rasmussen, Craig
Dimitrov, Nedialko
Gera, Ralucca
Metadata
Show full item recordAbstract
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.
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.Related items
Showing items related by title, author, creator and subject.
-
Optimized graph topologies for probabilistic search
Klaus, Christian; Chung, Timothy H. (IEEE, 2011-12);This paper investigates the effect on the performance of a mobile sensor search caused by the search environment. We model the search environment as a simple connected undirected graph. By adding non-existing edges to ... -
A capability-based approach to analyzing the effectiveness and robustness of an offshore patrol vessel in the search and rescue mission
Ashpari, Mohammad (Monterey, California. Naval Postgraduate School, 2012-12);In this thesis, a model of effectiveness for an offshore patrol vessel conducting search and rescue missions is developed and described. Beginning with a brief overview of work done by colleagues from the University of ... -
Modeling and Analysis of Exhaustive Probabilistic Search
Chung, Timothy H.; Silvestrini, Rachel T. (2014);This article explores a probabilistic formulation for exhaustive search of a bounded area by a single searcher for a single static target. The searcher maintains an aggregate belief of the target’s presence or absence in ...