1990 RealTimeHeuristicSearch

From GM-RKB
Jump to navigation Jump to search

Subject Headings: Heuristic Search Algorithm, Minimax Lookahead Search Algorithm, Alpha-Beta Pruning Algorithm, Real-Time-A Algorithm.

Notes

Cited By

Quotes

Abstract

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 variation of minimax lookahead search, and an analog to alpha-beta pruning that significantly improves the efficiency of the algorithm. Paradoxically, the search horizon reachable with this algorithm increases with increasing branching factor. In addition, we present a new algorithm, called Real-Time-A∗, for interleaving planning and execution. We prove that the algorithm makes locally optimal decisions and is guaranteed to find a solution. We also present a learning version of this algorithm that improves its performance over successive problem solving trials by learning more accurate heuristic values, and prove that the learned values converge to their exact values along every optimal path. These algorithms effectively solve significantly larger problems than have previously been solvable using heuristic evaluation functions.

References

;

 AuthorvolumeDate ValuetitletypejournaltitleUrldoinoteyear
1990 RealTimeHeuristicSearchRichard E. KorfReal-time Heuristic Search10.1016/0004-3702(90)90054-41987
1990