Near-optimal probabilistic search using spatial Fourier sparse set

Kuo Shih Tseng, Bérénice Mettler

Research output: Contribution to journalArticle

1 Citation (Scopus)

Abstract

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 (US)
Pages (from-to)329-351
Number of pages23
JournalAutonomous Robots
Volume42
Issue number2
DOIs
StatePublished - Feb 1 2018

Fingerprint

Costs
Robots
Compressed sensing
Reinforcement learning
Learning algorithms
Robotics
Experiments

Keywords

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

Cite this

Near-optimal probabilistic search using spatial Fourier sparse set. / Tseng, Kuo Shih; Mettler, Bérénice.

In: Autonomous Robots, Vol. 42, No. 2, 01.02.2018, p. 329-351.

Research output: Contribution to journalArticle

@article{8454f0935e4b45288bf35df62b211ff2,
title = "Near-optimal probabilistic search using spatial Fourier sparse set",
abstract = "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).",
keywords = "Compressed sensing, Probabilistic search, Q-learning, Sparse learning, Submodularity",
author = "Tseng, {Kuo Shih} and B{\'e}r{\'e}nice Mettler",
year = "2018",
month = "2",
day = "1",
doi = "10.1007/s10514-017-9616-2",
language = "English (US)",
volume = "42",
pages = "329--351",
journal = "Autonomous Robots",
issn = "0929-5593",
publisher = "Springer Netherlands",
number = "2",

}

TY - JOUR

T1 - Near-optimal probabilistic search using spatial Fourier sparse set

AU - Tseng, Kuo Shih

AU - Mettler, Bérénice

PY - 2018/2/1

Y1 - 2018/2/1

N2 - 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).

AB - 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).

KW - Compressed sensing

KW - Probabilistic search

KW - Q-learning

KW - Sparse learning

KW - Submodularity

UR - http://www.scopus.com/inward/record.url?scp=85011697958&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=85011697958&partnerID=8YFLogxK

U2 - 10.1007/s10514-017-9616-2

DO - 10.1007/s10514-017-9616-2

M3 - Article

VL - 42

SP - 329

EP - 351

JO - Autonomous Robots

JF - Autonomous Robots

SN - 0929-5593

IS - 2

ER -