---
title: "A Polynomial Time Optimal Algorithm for Robot-Human Search under Uncertainty"
authors:
  - "Shaofei Chen"
  - "Tim Baarslag"
  - "Dengji Zhao"
  - "Jing Chen"
  - "Lincheng Shen"
doi: ""
url: "https://ijcai.org/proceedings/2016/121"
pdf: "https://ijcai.org/proceedings/2016/0121.pdf"
venue: "Proceedings of the Twenty-Fifth International Joint Conference on Artificial Intelligence"
year: 2016
pages: "819-824"
track: ""
keywords:
---

# A Polynomial Time Optimal Algorithm for Robot-Human Search under Uncertainty

Shaofei Chen, Tim Baarslag, Dengji Zhao, Jing Chen, Lincheng Shen

*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.