Abstract:
Current techniques for reasoning about search control knowledge in AI planning, such as those used in TLPlan, TALPlanner, or SHOP2, assume that search control knowledge is conditioned upon and interpreted with respect to a fixed set of goal states. Therefore, these techniques can deal with reachability goals but do not apply to temporally extended goals, such as goals of achieving a condition whenever a certain fact becomes true. Temporally extended goals convey several intermediate reachability goals to be achieved at different point of execution, sometimes with cyclic executions; that is, the notion of goal state becomes dynamic. In this paper, we describe a method for reasoning about search control knowledge in the presence of temporally extended goals. Given such a goal, we generate an equivalent Buchi automaton---an automaton recognising the language of the executions satisfying the goal---and interpret control knowledge over this automaton and the world state trajectories generated by a forward search planner. This method is implemented and experimented with as an extension of the TLPlan planner, which incidentally becomes capable of handling cyclic goals.