Improving the Learning Efficiencies of Realtime Search

AAAI 1996

TL;DR

This paper tackles the instability and inefficiency of realtime search algorithms like LRTA* during repeated problem-solving. The authors introduce two novel algorithms, ε-search and δ-search, which allow for suboptimal solutions and utilize upper bounds, respectively, to achieve more stable and efficient learning convergence.

What Problem Does This Paper Address?

Realtime search algorithms, unlike their offline counterparts (like A), make decisions in constant time and interleave planning with execution. This makes them suitable for dynamic environments where immediate action is required. However, algorithms like Learning Real-Time A (LRTA*) face two key challenges during repeated problem-solving (learning):

  1. Searching for All Optimal Solutions: Even after finding a good solution, LRTA continues searching for all* optimal solutions. This is inefficient, especially since it can't definitively identify optimality without knowing the true cost.
  2. Instability of Solution Quality: LRTA* tends to explore new, potentially more expensive paths, leading to fluctuations in solution quality during the learning process. It can even revisit previously found, better solutions.

The paper aims to improve the learning efficiency of these algorithms, focusing on how they converge to optimal solutions over multiple trials, rather than just the performance of the first trial.

Methods

The paper proposes two new algorithms that build upon LRTA*:

  • ε-search (Weighted Realtime Search): This algorithm introduces the concept of "ε-lower bounds." Instead of strictly adhering to the lowest estimated cost, it allows for solutions with an error of up to ε times the actual optimal cost. This is achieved by modifying the action selection to choose the neighbor with the minimum fε(x') value, where fε(x') = k(x,x') + hε(x'). The core idea is to reduce search effort by accepting slightly suboptimal solutions, thereby limiting exploration of less promising areas.
  • δ-search (Realtime Search with Upper Bounds): This algorithm introduces "upper bounds" on estimated costs. These upper bounds are initialized to infinity and are updated as the problem is solved. The key innovation is the action selection criterion: a neighbor x' is chosen only if c(j) + f_u(x') ≤ (1 + δ)h₀, where c(j) is the cost incurred so far in the current trial, f_u(x') is the estimated cost using the upper bound, and h₀ is the upper bound of the initial state at the start of the trial. This condition helps balance exploration and exploitation by limiting how far the search can deviate from a bound related to the previous trial's performance.

The authors also suggest that these two ideas can be combined into an "εδ-search" algorithm.

Datasets

The evaluation uses a custom-generated "rectangle problem space" with 10,000 states, modeled as a 100x100 grid with randomly placed obstacles. This setup is used to create mazes of varying difficulty (e.g., 35% obstacle ratio). The authors note that mazes are used for ease of visualization of search behavior, but the algorithms are applicable to any problem space. No standard benchmark datasets are mentioned.

Key Insights and Ideas

  • Suboptimality as a Tool for Efficiency: Allowing algorithms to accept suboptimal solutions (ε-search) can significantly reduce the computational cost (fewer expanded states) and speed up convergence.
  • Upper Bounds for Stability: Introducing upper bounds (δ-search) provides a mechanism to stabilize solution quality during learning. By bounding the search's deviation from previous performance, it prevents erratic increases in solution length.
  • Trade-off Management: The paper highlights the inherent trade-off between solution optimality and search efficiency. ε-search prioritizes efficiency by allowing ε-error, while δ-search prioritizes stability by bounding the search path.
  • Learning Process Matters: The core contribution is shifting focus from the first-trial performance to the learning process itself, identifying and addressing issues that arise from repeated problem-solving.

Key Results

  • ε-search:
    • Significantly reduces the number of expanded states (memory usage) as ε increases (Figure 4).
  • Leads to faster convergence in terms of solution length reduction over trials (Figure 3).
  • However, higher ε values can prevent convergence to an optimal solution and can still exhibit some instability in solution length during convergence.
  • δ-search:
    • Dramatically stabilizes solution length as δ decreases (Figure 5).
  • Reduces the number of expanded states as δ decreases (Figure 6), indicating more focused exploration.
  • When an appropriate δ is chosen (e.g., δ=2), it can converge to an optimal solution.
  • Smaller δ values (e.g., δ=1.0) can lead to suboptimal solutions and slower convergence than δ=0 (which essentially stops learning after the first trial).

Limitations and Future Work

  • ε-search Limitations: While ε-search improves learning efficiency, it can make it harder to find optimal solutions and may not fully stabilize solution quality, as seen by the occasional increases in solution length. The paper notes that completeness in infinite problem spaces cannot be guaranteed.
  • δ-search Limitations: To achieve its benefits, δ-search requires the upper bound of the initial state to be updated based on previous trials. For optimal solutions, δ needs to be sufficiently large (e.g., ≥ 2), which can slow down convergence compared to less restrictive settings.
  • Future Work: The paper suggests combining ε-search and δ-search into "εδ-search" to leverage the benefits of both: reducing learning amount (like ε-search) and stabilizing solution quality (like δ-search). The results for εδ-search are briefly shown in Figure 2(b), indicating a smoother learning curve.

Summary updated

BibTeX
@inproceedings{1996improving,
  title = {{Improving the Learning Efficiencies of Realtime Search}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {1996},
}
Figure