Optimized graph topologies for probabilistic search
Chung, Timothy H.
MetadataShow full item record
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 the graph we change the search environment's model. 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 a graph by means of the algebraic connectivity of the graph and its associated (Fiedler) eigenvector. The relationship between the graph topology and the performance of the search is highlighted, including a comparative evaluation of different search strategies employed by the mobile searcher. 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.
2011 50th IEEE Conference on Decision and Control and European Control Conference (CDC-ECC) Orlando, Florida, USA, December 12-15, 2011.
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.
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 ...
Hasting, Matthew D. (Monterey, California. Naval Postgraduate School, 2009-06);This thesis investigates the visual search process and the effect of contextual information on the search process in an urban combat environment. High resolution combat simulation models implement a parallel sweeping or ...