Near-optimal probabilistic search via submodularity and sparse regression

Kuo Shih Tseng, Bérénice Mettler

Research output: Contribution to journalArticlepeer-review

15 Scopus citations


The goal of search is to maximize the probability of target detection while covering most of the environment in minimum time. Existing approaches only consider one of these objectives at a time and most optimal search problems are NP-hard. In this research, a novel approach for search problems is proposed that considers three objectives: (1) coverage using the fewest sensors; (2) probabilistic search with the maximal probability of detection rate (PDR); and (3) minimum-time trajectory planning. Since two of three objective functions are submodular, the search problem is reformulated to take advantage of this property. The proposed sparse cognitive-based adaptive optimization and PDR algorithms are within (1 - 1 / e) of the optimum with high probability. Experiments show that the proposed approach is able to search for targets faster than the existing approaches.

Original languageEnglish
Pages (from-to)205-229
Number of pages25
JournalAutonomous Robots
Issue number1
StatePublished - 1 Jan 2017


  • Coverage problem
  • Overlapping group LASSO
  • Probabilistic search
  • Receding horizon control
  • Submodularity


Dive into the research topics of 'Near-optimal probabilistic search via submodularity and sparse regression'. Together they form a unique fingerprint.

Cite this