A Complete State-Space Based Temporal Planner

Since that heuristic state space planners have been very successful in classical planning, this approach is currently the most popular strategy in dealing with temporal planning, too. However, all current state-space temporal planners use a search method known as decision epoch planning, which is not complete for problems with required concurrency. In theory, this flaw can be overcome by employing another search method, called temporally lifted progression planning. In this paper, we show that there are two major problems which, if not tackled properly, can cause the latter method to be very inefficient in practice. The first problem is dealing with the remarkably large state space of temporally lifted progression planning. We present a pruning method for solving this problem and prove it to be both complete and optimality preserving. The next troublesome issue is solving a simple temporal problem (STP) in each state for computing g-values. We exploit the properties of such STPs and introduce a new method that solves them more efficiently than the state of the art algorithms do. Our experiments show that the new search method can add completeness to a state-of-the-art incomplete planner, TFD, without considerably worsening its performance in most standard domains.