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

• Google Scholar: 1183 Citations
• ACM DL: 241 Citations
• Semantic Scholar: 648 Citations

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