Optimized graph topologies for probabilistic search
Loading...
Authors
Klaus, Christian
Chung, Timothy H.
Subjects
Advisors
Date of Issue
2011-12
Date
Publisher
IEEE
Language
Abstract
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.
Type
Article
Description
2011 50th IEEE Conference on Decision and Control and European Control Conference (CDC-ECC) Orlando, Florida, USA, December 12-15, 2011.
Series/Report No
Department
Operations Research
Organization
Identifiers
NPS Report Number
Sponsors
Funder
Format
Citation
Distribution Statement
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.