Probabilistic search on optimized graph topologies
Chung, Timothy H.
MetadataShow full item record
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.
RightsThis 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.
Showing items related by title, author, creator and subject.
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 ...
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 ...