An efficient hybrid strategy for temporal planning

Temporal planning (TP) is notoriously difficult because it requires to solve a prepositional STRIPS planning problem with temporal constraints. In this paper, we propose an efficient strategy for solving TP, which combines, in an innovative way, several well established and studied techniques in AI, OR and constraint programming. Our approach integrates graph planning (a well studied planning paradigm), max-SAT (a constraint optimization technique), and the Program Evaluation and Review Technique (PERT), a well established technique in OR. Our method first separates the logical and temporal constraints of a TP problem and solves it in two phases. In the first phase, we apply our new STRIPS planner to generate a parallel STRIPS plan with a minimum number of parallel steps. Our new STRIPS planner is based on a new max-SAT formulation, which leads to an effective incremental learning scheme and a goal-oriented variable selection heuristic. The new STRIPS planner can generate optimal parallel plans more efficiently than the well-known SATPLAN approach. In the second phase, we apply PERT to schedule the activities in a parallel plan to create a shortest temporal plan given the STRIPS plan. When applied to the first optimal parallel STRIPS plan, this simple strategy produces optimal temporal plans on most benchmarks we have tested. This strategy can also be applied to optimal STRIPS plans of different parallel steps in an anytime fashion to find an optimal temporal plan. Our experimental results show that the new strategy is effective and the resulting algorithm outperforms many existing temporal planners.