AAAI Publications, Eighth Annual Symposium on Combinatorial Search

Font Size: 
Metareasoning in Real-Time Heuristic Search
Dylan O'Ceallaigh, Wheeler Ruml

Last modified: 2015-05-13


Real-time heuristic search addresses the setting in which planning andacting can proceed concurrently. We explore the use of metareasoning at two decision points within a real-time heuristic search. First, if the domain has an `identity action' that allows the agent to remain in the same state and deliberate further, when should this action be taken? Second, given a partial plan that extends to the lookahead frontier, to how many actions should the agent commit? We show that considering these decisions carefully can reduce the agent's total time taken to arrive at a goal in several benchmark domains, relative to the current state-of-the-art. The resulting algorithm can dynamically adjust the way it interleaves planning and acting, between greedy hill-climbing and A*, depending on the problem instance.


heuristic search, metareasoning, real-time

Full Text: PDF