Abstract:

In domains where planning is slow compared to the evolution of the environment, it can be important to take into account the time taken by the planning process itself.  For one example, plans involving taking a certain bus are of no use if planning finishes after the bus departs.  For another, replanning how to repair a broken fuse box might need to finish while the currently-burning match still provides light. We call this setting situated temporal planning and we define it as a variant of temporal planning with timed initial literals. We present a forward state-space search approach to the problem, in which search nodes expire at possibly uncertain times. To guide search, we first formalize the underlying metareasoning problem as an MDP and then derive both optimal algorithms for special cases and general greedy schemes. Finally, we present a situated temporal planner that uses greedy metareasoning to guide its search. Our experimental evaluation suggests that using metareasoning significantly improves the performance of situated temporal planners. This work broadens the scope of planning to include situations in which the world refuses to wait.