Real-Time Heuristic Search: First
Richard E. Korf · 1987
Existing heuristic search algorithms are not ap-plicable to real-time applications because they can-not commit to a move before an entire solution is found. We present a special case of minimax looka-head search to handle this problem, and an analog of alpha-beta pruning that significantly improves the efficiency of the algorithm. In addition, we present a new algorithm, called Real-Time-A*, for searching when actions must actually be executed, as opposed to merely simulated. Finally, we examine the nature of the tradeoff between computation and execution cost. EIeuristic search is a fundamental problem-solving method in artificial intelligence. l?or most AI problems, the se-