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

Shaofei Chen, Tim Baarslag, Dengji Zhao, Jing Chen, Lincheng ShenIJCAI 2016

Introduction

In many robotic exploration scenarios, such as a lunar rover searching for mineral deposits, robots must operate under significant uncertainty regarding the value of potential targets. While a robot can "reveal" the true value of a target through costly physical action (e.g., digging), it also has the option to "ask" for human assistance (e.g., remote expert analysis). However, human help is often constrained by availability and communication costs. This paper addresses the Robot-Human Search (RHS) problem: determining the optimal sequence of actions—reveal, ask, or collect—to maximize the expected reward while minimizing costs.

The interaction model between the robot, human, and environment.

The Robot-Human Search (RHS) Model

The RHS problem involves $n$ potential items, each with an unknown reward $X_i$ following a known distribution. The robot can perform two types of information-gathering actions:

  1. Reveal: The robot directly observes $X_i$ at a cost $c_i^{reveal}$.
  2. Ask: The robot requests human help at a cost $c_i^{ask}$. With probability $p$, the human is available and provides the exact value of $X_i$. With probability $1-p$, the human is unavailable, and the state of the item remains unchanged.

The state of each item transitions through various levels of knowledge and availability, as illustrated in the state transition diagram below.

State transition diagram for an item in the RHS model.

The Index-Based Optimal Strategy

Solving the RHS problem using standard dynamic programming typically leads to an exponential state-space explosion ($O(n^2 2^n)$). The authors overcome this by mapping RHS to a variant of "Pandora’s Rule," a classic economic search problem. They prove that the optimal policy is an index-based strategy with a complexity of only $O(n \log n)$.

The algorithm calculates two numerical indices for each location:

  • Reveal Index ($z_i^{reveal}$): The "reservation price" for revealing the item.
  • Ask Index ($z_i^{ask}$): The "reservation price" for asking for human help.

The robot follows a simple, optimal rule: always perform the action (reveal or ask) that has the highest current index. The search terminates when the highest reward already found exceeds the indices of all remaining possible actions.

Key Insights and Results

  • Computational Efficiency: By reducing the problem to an $O(n \log n)$ index-based search, the authors make optimal decision-making feasible for real-time robotic applications with many targets.
  • Dominance Property: A critical finding is that if $c_i^{reveal} < c_i^{ask}/p$, the robot should never ask for help for that specific item, as direct revelation is more cost-effective.
  • Human Availability: The value of human intervention is highly sensitive to the availability probability $p$. As $p$ increases, the "ask index" rises, making human help more attractive.
  • Performance: Simulations demonstrate that this optimal strategy consistently outperforms common heuristics, such as picking items based solely on expected value or ignoring human help entirely.

Conclusion and Future Work

This work provides a mathematically rigorous and computationally efficient framework for robot-human collaboration in uncertain environments. While the current model assumes independent search costs and immediate feedback on human availability, it lays the groundwork for more complex scenarios. Future research will explore "wait-costs" for delayed human responses and multi-item collection goals.

Summary updated

BibTeX
@inproceedings{chen2016polynomial,
  author = {Shaofei Chen and Tim Baarslag and Dengji Zhao and Jing Chen and Lincheng Shen},
  title = {{A Polynomial Time Optimal Algorithm for Robot-Human Search under Uncertainty}},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year = {2016},
}
Figure