### 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 language | English (US) |
---|---|

Pages (from-to) | 329-351 |

Number of pages | 23 |

Journal | Autonomous Robots |

Volume | 42 |

Issue number | 2 |

DOIs | |

State | Published - Feb 1 2018 |

### Fingerprint

### Keywords

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

### Cite this

*Autonomous Robots*,

*42*(2), 329-351. https://doi.org/10.1007/s10514-017-9616-2

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

Research output: Contribution to journal › Article

*Autonomous Robots*, vol. 42, no. 2, pp. 329-351. https://doi.org/10.1007/s10514-017-9616-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 -