Envelope-Based Approaches to Real-Time Heuristic Search

Kevin C. Gall, Bence Cserna, Wheeler RumlAAAI 2020 · DOI

Abstract

Real-time heuristic search algorithms often struggle with local minima in the heuristic function, leading to inefficient state re-visitation known as "scrubbing." This paper introduces Intra-Envelope Search (I-ES), a real-time search algorithm that maintains a persistent envelope of explored states. Unlike previous methods that strictly follow search tree branches, I-ES utilizes an auxiliary search within the envelope to identify shortcuts, allowing the agent to jump between branches. Experimental results in grid-based pathfinding and other domains show that I-ES significantly reduces path length and improves search efficiency in interconnected state spaces.

Introduction

Real-time planning is critical for agents operating under strict time constraints, such as robots in dynamic environments. Traditional agent-centered search methods often discard search data between moves, leading to "heuristic depressions" where the agent repeatedly visits states to update misleadingly low heuristic values. While envelope-based methods like Time-Bounded A (TBA) maintain a persistent search tree, they are often too rigid, forcing agents to backtrack significantly to switch between tree branches even when states are physically close in the environment.

Methods: Intra-Envelope Search (I-ES)

I-ES addresses these limitations by treating the set of explored states as a flexible graph rather than a rigid tree. The algorithm divides its per-step computation time into two distinct phases:

  1. Exploration: The search frontier is expanded toward the goal, similar to standard A*.
  2. Path Extraction: Instead of following parent pointers in a tree, I-ES performs a secondary search within the existing envelope. This "intra-envelope" search identifies the optimal shortcut from the agent's current position to the most promising node on the frontier.
Figure 1: Illustration of path extraction and envelope navigation in I-ES.

By searching the graph of the envelope rather than just following tree pointers, the agent gains immense flexibility. This approach allows the agent to "jump" between branches of the search tree if they are physically close in the state space, avoiding the massive backtracking required by previous methods.

Evaluation

The authors evaluated I-ES against several baselines, including LSS-LRTA and TBA variants, across four distinct domains: the 15-Puzzle, Racetrack, and two grid-based environments.

Figure 4: Grid pathfinding domains: "Minima" (left) and Starcraft "Cauldron" (right).

Key Results

  • Grid World Dominance: In the "Minima" and "Starcraft" grid maps, I-ES significantly outperformed all other algorithms at low time bounds. It found paths that were often 2-3 times shorter than those found by LSS-LRTA*.
  • The Connectivity Dividend: The benefits of I-ES are directly proportional to the "interconnectedness" of the domain. In dense grids where many paths exist between points, the ability to find shortcuts within the envelope provides a massive advantage. In more constrained domains like the Sliding Tile puzzle, the lead was less dramatic.
  • Efficiency at Scale: While I-ES spends some time searching within its envelope, this trade-off pays off. The shortcuts it finds are more valuable than the extra frontier nodes it would have reached otherwise.

Conclusion

I-ES represents a significant step forward in real-time heuristic search by leveraging the graph structure of explored states to eliminate inefficient scrubbing behavior. While highly effective in interconnected domains, the primary limitation is the computational overhead of the intra-envelope search in sparse environments. Future work will explore adapting I-ES for dynamic domains with changing edge costs and integrating bidirectional search techniques to further accelerate shortcut discovery.

Summary updated

BibTeX
@inproceedings{gall2020envelope,
  author = {Kevin C. Gall and Bence Cserna and Wheeler Ruml},
  title = {{Envelope-Based Approaches to Real-Time Heuristic Search}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {2020},
  doi = {10.1609/aaai.v34i03.5614},
}
Figure