Envelope-Based Approaches to Real-Time Heuristic Search


  • Kevin Gall University of New Hampshire
  • Bence Cserna University of New Hampshire
  • Wheeler Ruml University of New Hampshire




In real-time heuristic search, the planner must return the next action for the agent within a pre-specified time bound. Many algorithms for this setting are ‘agent-centered’ in that, at every iteration, they only expand states near the agent's current state, discarding the search frontier afterwards. In this paper, we investigate the alternative paradigm in which the search expands a single ever-growing envelope of states. Previous work on envelope-based methods restricts the agent to move along the generated search tree. We propose a more flexible approach in which an auxiliary search is performed within the envelope to guide the agent toward a promising frontier node. Experimental results indicate that intra-envelope search is beneficial in state spaces that are highly interconnected, such as those for grid pathfinding.




How to Cite

Gall, K., Cserna, B., & Ruml, W. (2020). Envelope-Based Approaches to Real-Time Heuristic Search. Proceedings of the AAAI Conference on Artificial Intelligence, 34(03), 2351-2358. https://doi.org/10.1609/aaai.v34i03.5614



AAAI Technical Track: Heuristic Search and Optimization