Publications about 'search problems'
Articles in journal or book chapters
  1. B. DasGupta, J.P. Hespanha, J. Riehl, and E.D. Sontag. Honey-pot constrained searching with local sensory information. Nonlinear Analysis, 65:1773-1793, 2006. [PDF] Keyword(s): search problems, algorithms, computational complexity.
    This paper investigates the problem of searching for a hidden target in a bounded region of the plane by an autonomous robot which is only able to use limited local sensory information. It proposes an aggregation-based approach to solve this problem, in which the continuous search space is partitioned into a finite collection of regions on which we define a discrete search problem and a solution to the original problem is obtained through a refinement procedure that lifts the discrete path into a continuous one. The resulting solution is in general not optimal but one can construct bounds to gauge the cost penalty incurred. The discrete version is formalized and an optimization problem is stated as a `reward-collecting' bounded-length path problem. NP-completeness and efficient approximation algorithms for various cases of this problem are discussed.



This material is presented to ensure timely dissemination of scholarly and technical work. Copyright and all rights therein are retained by authors or by other copyright holders.

Last modified: Thu Nov 23 10:40:57 2017
Author: sontag.

This document was translated from BibTEX by bibtex2html