1990 RealTimeHeuristicSearch
- (Korf, 1990) ⇒ Richard E. Korf. (1990). "Real-time Heuristic Search".; In: Artificial Intelligence Journal, 42(2-3). doi:10.1016/0004-3702(90)90054-4
Subject Headings: Heuristic Search Algorithm, Minimax Lookahead Search Algorithm, Alpha-Beta Pruning Algorithm, Real-Time-A Algorithm.
Notes
- Related Publications:
- (Korf, 1987) ⇒ Richard E. Korf. (1987). “Real-time Heuristic Search: First Results.” In: Proceedings of the sixth National conference on Artificial intelligence - Volume 1. ISBN:0-934613-42-7
- Copyright: 1990 Published by Elsevier B.V.
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
;
Author | volume | Date Value | title | type | journal | titleUrl | doi | note | year | |
---|---|---|---|---|---|---|---|---|---|---|
1990 RealTimeHeuristicSearch | Richard E. Korf | Real-time Heuristic Search | 10.1016/0004-3702(90)90054-4 | 1987 1990 |