Real-Time Heuristic Search: First Results

Richard E. Korf

Existing heuristic search algorithms are not applicable to real-time applications because they cannot commit to a move before an entire solution is found. We present a special case of minimax lookahead 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.

This page is copyrighted by AAAI. All rights reserved. Your use of this site constitutes acceptance of all of AAAI's terms and conditions and privacy policy.