Refining Abstraction Heuristics during Real-Time Planning

Rebecca Eifler, Maximilian Fickert, Jörg Hoffmann, Wheeler RumlAAAI 2019 · DOI

Introduction

In real-time planning, agents must commit to actions within strict time constraints, often before a complete path to the goal is discovered. To ensure completeness and eventual success, these agents must learn from their environment by updating their heuristic—the estimate of the remaining distance to the goal.

Traditionally, algorithms like LSS-LRTA rely on Bellman updates, which adjust heuristic values for states on a case-by-case basis. This approach suffers from two primary limitations: a lack of generalization (learning about one state does not inform the agent about similar, unvisited states) and significant memory consumption in large state spaces. This paper proposes a shift toward online abstraction refinement*, using Cartesian abstractions to group similar states into blocks, thereby enabling simultaneous updates across multiple states and maintaining a compact memory footprint.

Methodology

The authors integrate Cartesian Abstraction into a real-time planning framework. The core mechanism is Counter-Example Guided Abstraction Refinement (CEGAR). Instead of using a static model, the planner begins with a coarse abstraction and dynamically "splits" abstract states (blocks) into smaller, more precise ones when flaws in the current plan are detected.

Refinement and Time Management

Because refinement is computationally more intensive than simple table updates, the authors introduce a lookahead ratio ($l$) to balance the time spent on search versus heuristic refinement within each decision cycle.

The lookahead ratio $l$ is used to manage the time budget between search and refinement phases across multiple planning steps.

The paper evaluates three primary configurations:

  1. $h_b$ (Bellman Baseline): Traditional per-state lookup table updates.
  2. $h_r$ (Abstraction Refinement): Heuristic updates driven solely by CEGAR refinement.
  3. $h_{r+b}$ (Hybrid): A combination of both methods to leverage the local precision of Bellman updates and the broad generalization of abstraction.

The Mechanism of Refinement

Refinement occurs by identifying inconsistencies within an abstract block. For instance, if an action $a'$ is applicable in some concrete states of a block but not others, the block is split to reflect this difference, improving the accuracy of the heuristic for all states within those new blocks.

Abstraction refinement involves splitting a block $A$ into $A_0$ and $A_1$ based on whether an action $a'$ is applicable, allowing for more precise heuristic estimates.

Key Insights and Results

The researchers tested their approach on 1,797 instances from the International Planning Competition (IPC) and various 15-Puzzle configurations.

  • Generalization: On average, 54% of newly visited states already possessed improved heuristic values due to previous abstraction refinements. This confirms that the agent learns the underlying structure of the problem rather than just specific state coordinates.
  • Memory Efficiency: Abstraction proved remarkably compact. In several domains, the number of abstract states required was three orders of magnitude smaller than the entries needed for a standard Bellman lookup table.
  • Coverage and Search Reduction: At 0.1s time intervals, the hybrid $h_{r+b}$ approach achieved the highest coverage, solving 1,067 instances compared to 1,022 for the Bellman baseline. In domains like Depots and Hiking, abstraction-based methods reduced state expansions by more than an order of magnitude.
  • Theoretical Strength: The authors provide a proof that abstraction refinement can simulate Bellman updates, positioning it as a strictly more powerful framework for heuristic learning.

Conclusion and Future Work

While online abstraction refinement offers superior generalization and memory efficiency, it introduces higher computational overhead per step. This makes it most effective at moderate time intervals (e.g., 0.1s) rather than extremely tight constraints (0.01s). Future research aims to integrate lookahead search more deeply into the refinement process to make heuristic updates even more targeted and efficient.

Summary updated

BibTeX
@inproceedings{eifler2019refining,
  author = {Rebecca Eifler and Maximilian Fickert and Jörg Hoffmann and Wheeler Ruml},
  title = {{Refining Abstraction Heuristics during Real-Time Planning}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {2019},
  doi = {10.1609/aaai.v33i01.33017578},
}
Figure