Incremental search algorithms for real-time decision making
Joseph C. Pemberton, Richard E. Korf · 1994
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-valuebased 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 depthfirst branch-and-bound performs nearly as well as the more complicated best-first variation. Introduction and Overview We are interested in the general problem of how to make real-time decisions. One example of...