Real-Time Heuristic Search: First Results

Richard E. KorfAAAI 1987

Abstract: Traditional heuristic search algorithms like A require complete path planning before the first move can be executed, making them unsuitable for real-time applications where time is limited or the environment is partially unknown. This paper introduces Real-Time-A (RTA), an algorithm that allows agents to make high-quality moves within a fixed time budget. By combining limited lookahead search with a learning mechanism that updates state values based on experience, RTA bridges the gap between planning and action. Experimental results on the Fifteen Puzzle demonstrate that RTA* can achieve near-optimal performance with constant time per move.

Introduction

In classical artificial intelligence, search algorithms such as A and IDA are designed to find the shortest path to a goal state. While effective for offline planning, these methods suffer from a significant drawback in real-time scenarios: they exhibit exponential time complexity and require the entire plan to be finalized before execution begins. In dynamic or large-scale environments—such as robotics or complex navigation—waiting for a complete plan is often impossible.

Richard Korf's 1987 paper addresses this challenge by proposing a "real-time" approach. The goal is to commit to an immediate move based on incomplete information while ensuring the agent eventually reaches its destination without falling into infinite loops.

The RTA* Algorithm

The paper introduces three primary mechanisms to enable real-time decision-making:

  1. Minimin Lookahead Search: Adapted from the minimax algorithm used in adversarial games, minimin search explores the state space to a fixed depth (the search horizon). It then applies a heuristic function to the frontier nodes and propagates the minimum value back to the current state to identify the most promising immediate move.
  2. Alpha Pruning: To optimize the search, Korf adapts alpha-beta pruning for single-agent contexts. If the cost function is monotonic, branches can be pruned as soon as their estimated cost exceeds the best value found on the current frontier.
  3. Real-Time-A (RTA): The core contribution is the RTA algorithm. Unlike standard A, which measures cost from a fixed start point, RTA* calculates cost relative to the agent's current position. Crucially, when an agent leaves a state, it records the heuristic value of the second-best path. This "learning" allows the agent to backtrack rationally if a chosen path proves more difficult than expected.

Experimental Evaluation

Korf evaluated these algorithms using standard AI benchmarks, primarily the Fifteen Puzzle and the Eight Puzzle. For the Fifteen Puzzle, 1,000 randomly generated solvable states were used to measure solution length and search depth. The Eight Puzzle was utilized for 10,000 trials to assess "decision quality"—the probability that the algorithm selects the mathematically optimal move.

Key Results and Insights

The experiments revealed several critical properties of real-time search. One of the most significant findings is the "L-curve" of diminishing returns. As shown in Figure 2, there is a sharp initial drop in solution length as the search horizon increases. However, this benefit quickly plateaus; beyond a certain point, additional computation yields only marginal improvements in the total path length.

Solution length as a function of search horizon, demonstrating the 'L-curve' of diminishing returns.

Another key observation is the relationship between search depth and decision quality. While deeper search generally leads to better individual moves (reducing the error percentage, as seen in Figure 3), it does not always result in a shorter overall solution. Korf identified "search pathology," where specific search depths actually increased the total path length due to the high cost of recovering from a single deep-level error.

Error percentage in move selection decreases as the search horizon increases.

Furthermore, alpha pruning proved highly effective, reducing the effective branching factor in the Fifteen Puzzle from 2.13 to 1.41. This efficiency allowed the agent to search significantly deeper within the same computational budget. At a search depth of 25 moves, RTA* produced solutions approximately twice the length of the optimal path while searching only a tiny fraction of the nodes required by an offline solver.

Conclusion

RTA* represents a fundamental shift toward "anytime" algorithms in AI. By prioritizing immediate action and learning from the environment, it provides a robust framework for agents operating under real-world constraints. While the algorithm can occasionally exhibit repetitive backtracking behavior, its ability to provide constant-time decision-making makes it a cornerstone of modern real-time heuristic search. Future work suggested by Korf includes improving tie-breaking strategies and exploring more complex cost models for computation versus execution.

Summary updated

BibTeX
@inproceedings{korf1987real,
  author = {Richard E. Korf},
  title = {{Real-Time Heuristic Search: First Results}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {1987},
}
Figure