A Polynomial Time Optimal Algorithm for Robot-Human Search Under Uncertainty
Abstract
This paper studies a search problem involving a robot that is searching for a certain item in an uncertain environment (e.g., searching minerals on Moon) that allows only limited interaction with humans. The uncertainty of the environment comes from the rewards of undiscovered items and the availability of costly human help. The goal of the robot is to maximize the reward of the items found while minimizing the search costs. We show that this search problem is polynomially solvable with a novel integration of the human help, which has not been studied in the literature before. Furthermore, we empirically evaluate our solution with simulations and show that it significantly outperforms several benchmark approaches. PDF
Cite
Text
Chen et al. "A Polynomial Time Optimal Algorithm for Robot-Human Search Under Uncertainty." International Joint Conference on Artificial Intelligence, 2016.Markdown
[Chen et al. "A Polynomial Time Optimal Algorithm for Robot-Human Search Under Uncertainty." International Joint Conference on Artificial Intelligence, 2016.](https://mlanthology.org/ijcai/2016/chen2016ijcai-polynomial/)BibTeX
@inproceedings{chen2016ijcai-polynomial,
title = {{A Polynomial Time Optimal Algorithm for Robot-Human Search Under Uncertainty}},
author = {Chen, Shaofei and Baarslag, Tim and Zhao, Dengji and Chen, Jing and Shen, Lincheng},
booktitle = {International Joint Conference on Artificial Intelligence},
year = {2016},
pages = {819-825},
url = {https://mlanthology.org/ijcai/2016/chen2016ijcai-polynomial/}
}