Envelope-Based Approaches to Real-Time Heuristic Search

2020-06-02

Proceedings of the AAAI Conference on Artificial Intelligence, 34

Volume

Vol. 34 No. 03: AAAI-20 Technical Tracks 3

AAAI Technical Track: Heuristic Search and Optimization

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.

10.1609/aaai.v34i03.5614