A Polynomial Time Optimal Algorithm for Robot-Human Search under Uncertainty
Proceedings of the Twenty-Fifth International Joint Conference on Artificial Intelligence. Pages 819-824.
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.
@inproceedings{ijcai2016p121,
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 = {Proceedings of the Twenty-Fifth International Joint Conference on
Artificial Intelligence, {IJCAI-16}},
publisher = {AAAI Press / International Joint Conferences on Artificial Intelligence},
editor = {Subbarao Kambhampati},
pages = {819--824},
year = {2016},
month = {7},
url = {https://ijcai.org/proceedings/2016/121},
}
TY - CPAPER TI - A Polynomial Time Optimal Algorithm for Robot-Human Search under Uncertainty AU - Chen, Shaofei AU - Baarslag, Tim AU - Zhao, Dengji AU - Chen, Jing AU - Shen, Lincheng T2 - Proceedings of the Twenty-Fifth International Joint Conference on Artificial Intelligence, IJCAI-16 PB - AAAI Press / International Joint Conferences on Artificial Intelligence PY - 2016 SP - 819 EP - 824 UR - https://ijcai.org/proceedings/2016/121 ER -Copied
Machine-readable versions of this paper, for tools and AI agents:
