Joseph C. Pemberton and Richard E. Korf
We propose incremental, real-time search as a general approach to real-time decision making. We model real-time decision making as incremental tree search with a limited number of node expansions between decisions. We show that the decision policy of moving toward the best frontier node is not optimal, but nevertheless performs nearly as well as an expected-value-based decision policy. We also show that the real-time constraint causes difficulties for traditional best-first search algorithms. We then present a new approach that uses a separate heuristic function for choosing where to explore and which decision to make. Empirical results for random trees show that our new algorithm outperforms the traditional best-first search approach to real-time decision making, and that depth-first branch-and-bound performs nearly as well as the more complicated best-first variation.