Near-optimal probabilistic search via submodularity and sparse regression

Kuo Shih Tseng, Bérénice Mettler

Research output: Contribution to journalArticlepeer-review

12 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 (US)
Pages (from-to)205-229
Number of pages25
JournalAutonomous Robots
Issue number1
StatePublished - Jan 1 2017

Bibliographical note

Funding Information:
This research was completed thanks to the financial support from ONR Grant 1361538 and NSF CAREER CMMI 1254906. Kuo-Shih would like to thank his daughter, Chin-Chun Tseng. The hide-and-seek game they played inspires this research. The authors would also like to thank Alessandro Renzaglia for discussing the details about his PhD thesis, the CAO algorithm.

Publisher Copyright:
© 2015, Springer Science+Business Media New York.


  • 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