Near-optimal probabilistic search using spatial Fourier sparse set

Kuo Shih Tseng, Bérénice Mettler

Research output: Contribution to journalArticlepeer-review

10 Scopus citations


Autonomous search is an essential research topic for rescue and other robotic applications. However, searching for targets efficiently is still an unsolved problem. To achieve this objective, a robot needs to simultaneously maximize environmental coverage, maximize probability of detection (PD) and minimize motion cost. The problems associated with these objectives are NP-hard. This research reformulates the three objective functions as a maximum cumulative PD problem with motion cost. Since the PD function depends on the environment, the robot needs to both learn the PD function and the cost-to-go (CTG) function. This research proposes a reinforcement learning algorithm to learn the PD and CTG functions simultaneously. Since the PD function is sparse in the Fourier domain under certain subgoal patterns, spatial Fourier sparse set is proposed to learn PD functions based on the compressed sensing technique. The learned PD and CTG functions can then be used to generate subgoals that achieve (1 - 1 / e) of the optimum due to the submodularity. Experiments conducted with this algorithm demonstrate that the robot can search for the target faster than prior learning approaches (e.g., PMAC and FSS) and the benchmark model (e.g., PD).

Original languageEnglish
Pages (from-to)329-351
Number of pages23
JournalAutonomous Robots
Issue number2
StatePublished - 1 Feb 2018


  • Compressed sensing
  • Probabilistic search
  • Q-learning
  • Sparse learning
  • Submodularity


Dive into the research topics of 'Near-optimal probabilistic search using spatial Fourier sparse set'. Together they form a unique fingerprint.

Cite this