Real-Time Heuristic Search: New Results

AAAI 1988

TL;DR

This paper introduces Real-Time A (RTA), an algorithm that adapts heuristic search techniques, traditionally used for problems where the entire solution can be pre-computed, to scenarios with strict time constraints. RTA* makes locally optimal decisions in real-time, proving to be complete and capable of learning for repeated problem-solving, effectively tackling larger problems than previously possible.

What Problem Does This Paper Address?

Traditional heuristic search algorithms like A and IDA excel at finding optimal solutions but require significant computation to explore the entire search space. This makes them impractical for real-time applications where decisions must be made quickly, and only a limited amount of computation is available before the next action must be taken. Think of a robot navigating a complex environment or a game AI needing to make a move within milliseconds. The core challenge is to balance the need for good decisions with severe computational and temporal limitations, a problem this paper tackles by adapting game-tree search techniques to single-agent problems.

Methods

The paper builds upon two key ideas:

  • Minimin Search with Alpha Pruning: This is a specialized version of minimax search for single agents. Instead of finding the maximum value (as in two-player games), it finds the minimum. Alpha pruning, a technique from game AI, is adapted to efficiently search a limited depth horizon. Crucially, the paper shows that this pruning becomes more effective as the branching factor of the problem increases, a counter-intuitive but powerful finding.
  • Real-Time A (RTA): This algorithm uses the minimin search with alpha pruning to generate a heuristic evaluation for neighboring states. It then selects the neighbor that minimizes the combined cost of reaching it (g) and its heuristic evaluation (h). RTA makes locally optimal decisions based on the visible search horizon. The paper also addresses how RTA can be modified to work on graphs (which contain cycles) and proves its completeness (guaranteed to find a solution if one exists) under certain conditions.
  • Learning-RTA (LRTA): To improve performance over multiple problem-solving trials, LRTA is introduced. It learns by storing and reusing heuristic values from previous searches. The paper proves that LRTA converges to exact heuristic values along optimal paths, making it more efficient over time.

Datasets

The paper evaluates its algorithms on sliding tile puzzles:

  • 3x3 (8 Puzzle)
  • 4x4 (15 Puzzle)
  • 5x5 (24 Puzzle)
  • 10x10 (99 Puzzle)

These puzzles involve rearranging tiles in a square frame to reach a goal configuration. The authors used averages of 1000 random solvable initial states for evaluation.

Key Insights and Ideas

  • Alpha Pruning Benefits from Higher Branching Factors: This is perhaps the most surprising result. Counter-intuitively, increasing the branching factor of a search problem can lead to deeper search horizons with the same amount of computation when using alpha pruning. This is because a larger branching factor increases the number of frontier nodes, which tends to lower the alpha value, leading to more aggressive pruning.
  • Real-Time Decisions Can Be Optimal (Locally): RTA* proves to make locally optimal decisions relative to the part of the search space it can see. This is a significant step towards applying sophisticated search techniques to time-constrained problems.
  • Completeness in Finite Spaces: RTA* is guaranteed to find a solution in finite problem spaces with positive edge costs, even with cycles, as long as a goal is reachable. This is a crucial theoretical guarantee.
  • Learning for Efficiency: LRTA* demonstrates that heuristic search algorithms can learn and improve over time, converging to exact values and making subsequent problem-solving much faster.

Key Results

  • Increased Search Horizon: For the 99 puzzle, fixing computation to 100,000 nodes per move, alpha pruning increased the search horizon from 10 to 50 moves.
  • Solving Larger Problems: The paper reports the first successful solutions to the 24-puzzle using heuristic search techniques.
  • Empirical Performance: Figure 1 shows that alpha pruning significantly reduces the number of nodes generated compared to brute-force search. Figure 2 illustrates that increasing the search horizon generally leads to shorter solution lengths for RTA*, with diminishing returns. For instance, for the 15-puzzle, finding solutions twice the optimal length (106 vs. 53) required a search depth of 22 moves.

Limitations and Future Work

  • Infinite Problem Spaces: RTA* may not find a solution in infinite problem spaces if heuristic values can lead it down an infinitely wrong path.
  • One-Way Edges and Dead-Ends: In finite problem spaces, RTA* might get stuck in parts of the graph from which the goal is unreachable due to one-way edges.
  • Non-Overestimating Heuristics for Learning: LRTA*'s convergence proof relies on initial heuristic values not overestimating the distance to the goal.
  • Future Work: The paper suggests further exploration of learning mechanisms and the application of these algorithms to more complex, real-world problems. The authors also note that space limitations prevented a full proof of RTA*'s optimality on general graphs.

Summary updated

BibTeX
@inproceedings{1988real,
  title = {{Real-Time Heuristic Search: New Results}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {1988},
}
Figure