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 paper evaluates three primary configurations:
- $h_b$ (Bellman Baseline): Traditional per-state lookup table updates.
- $h_r$ (Abstraction Refinement): Heuristic updates driven solely by CEGAR refinement.
- $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.
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