Graph Abstraction in Real-time Heuristic Search

Vadim Bulitko, Nathan R. Sturtevant, Jieshan Lu, Timothy YauJAIR 2007 · DOI · OpenReview

TL;DR

This paper introduces Path Refinement Learning Real-time Search (PR LRTS), a novel algorithm that combines graph abstraction with real-time heuristic search to improve efficiency and learning speed. By performing search on a simplified abstract graph and then refining the path to the ground level, PR LRTS significantly outperforms existing methods on complex pathfinding tasks, offering a better trade-off between planning time and learning.

What Problem Does This Paper Address?

Situated agents in real-time environments, like those in video games or robotics, need to make decisions quickly, often within milliseconds, regardless of the complexity of their environment. This requires planning algorithms that can operate within a constant time bound per action. Traditional real-time heuristic search algorithms, such as LRTA*, can achieve this but often suffer from slow learning and poor solution quality during convergence. Conversely, full search algorithms can find optimal solutions but cannot guarantee constant planning time. This paper addresses the challenge of achieving both fast response times and efficient learning in complex environments by leveraging graph abstraction to create a more manageable search space for real-time agents.

Methods

The core contribution is the Path Refinement Learning Real-time Search (PR LRTS) algorithm. PR LRTS operates on a hierarchy of abstract graphs, where higher levels represent simplified versions of the environment. The algorithm first plans a path on the most abstract graph using a real-time search algorithm (like LRTS). This abstract path is then "refined" into a ground-level path by using a corridor-restricted A search. The abstraction mechanism used is clique abstraction*, which groups connected states in the original graph into single abstract states. This approach allows for:

  • Accelerated Learning: Learning occurs on the smaller abstract graph, speeding up heuristic function updates.
  • Constant Planning Time: The real-time property is maintained by performing planning on the abstract graph.
  • Path Refinement: The abstract path is translated into a detailed ground-level path.

The paper also formalizes abstraction properties and proves theoretical guarantees for PR LRTS, including real-time operation, completeness, and convergence.

Datasets

The experiments were conducted on 3000 randomly generated problems across six maps. Three maps were modeled after environments from the role-playing game "Baldur's Gate" and three from the real-time strategy game "Age of Empires II." These maps varied in size, from 5672 to 18841 states. The problems were distributed into five buckets based on optimal solution costs, ranging from [50, 60) to [90, 100).

Key Insights and Ideas

  • Abstraction as a Trade-off Enabler: The most significant insight is that graph abstraction is not just about simplifying problems but is a powerful tool for efficiently trading off antagonistic performance measures (e.g., convergence travel vs. first-move lag). PR LRTS demonstrates that abstraction allows for better performance on multiple fronts simultaneously.
  • Hierarchical Search for Real-time Agents: Applying hierarchical search, common in full search, to real-time agents is a novel and effective approach. PR LRTS shows that planning on abstract levels can significantly reduce the computational burden without sacrificing the real-time constraint.
  • Clique Abstraction's Suitability: The paper highlights that clique abstraction, which focuses on fully connected components, is particularly well-suited for grid-based pathfinding due to its ability to maintain a relatively constant branching factor across abstraction levels.
  • Suboptimality is Manageable: While abstraction can introduce suboptimality, the empirical results show that this is not a severe issue in practice, especially with deeper lookahead. The paper also suggests methods to mitigate this, such as pre-computing optimal paths within abstract regions.

Key Results

  • Dominance over Non-Abstracted Algorithms: PR LRTS configurations consistently dominated most tested algorithms that did not use abstraction, particularly when considering pairs of antagonistic performance measures.
  • Improved Efficiency: Abstraction significantly reduced convergence travel, convergence planning, and convergence memory. For example, PR LRTS achieved convergence speeds orders of magnitude faster than LRTA* in some cases.
  • Better Trade-offs: PR LRTS offered superior trade-offs between performance measures. For instance, it achieved lower convergence travel and first-move lag compared to non-abstracted algorithms.
  • Scalability: The paper demonstrates that PR LRTS scales well to larger problems, with abstraction dampening the increase in convergence travel, planning, and memory.
  • Theoretical Guarantees: PR LRTS was proven to be complete, to have real-time operation, and to converge in a finite number of trials.

Limitations and Future Work

  • Abstraction Mechanism Specificity: The paper acknowledges that the effectiveness of clique abstraction might be domain-specific. Future work could investigate the extent to which these results are specific to clique abstraction and pathfinding, and explore other homomorphic abstraction techniques for different domains (e.g., sliding tile puzzles).
  • Heuristic Propagation: Combining abstract path planning with propagating heuristic values from higher to lower levels of the abstraction hierarchy is suggested as a future research direction.
  • Function Approximation: Integrating function approximation for heuristic functions with state aggregation is proposed for large-scale reinforcement learning applications.
  • Dynamic Environments: Investigating PR LRTS in dynamic environments and for moving target search is a promising avenue.
  • Stochastic Environments: Extending the graph abstraction method to stochastic environments formulated as Markov Decision Processes is also a future research goal.

Summary updated

BibTeX
@article{bulitko2007graph,
  author = {Vadim Bulitko and Nathan R. Sturtevant and Jieshan Lu and Timothy Yau},
  title = {{Graph Abstraction in Real-time Heuristic Search}},
  journal = {J. Artif. Intell. Res.},
  year = {2007},
  doi = {10.1613/jair.2293},
}
Figure