Optimal temporal planning using the plangraph framework

The past few years have seen a rapid development in AI Planning and Scheduling. Many algorithms and techniques have been studied and improved to deal with more complex and difficult planning domains. One such innovation was Graphplan, first developed by Blum and Furst in 1995 and soon became one of the best approaches for optimal classical planning systems. Planning systems that use Graphplan’s plangraph framework can find optimal plans for temporal planning problems, in which actions have durations. However, these systems have had strict assumptions on the preconditions and effects of actions, for instance, effects happen only at the end of the execution. In addition, the algorithm used in the solution extraction phase of these plangraph-based systems does not take full advantage of the information provided by the expansion phase to prune irrelevant search branches early. With the ambition to make temporal planning problems more realistic, the thesis proposes an extension to the Planning Domain Definition Language (PDDL) 2.1 level 3, to allow actions to have intermediate effects. Our optimal temporal planning system, CPPlanner, is introduced as the first Graphplan-based optimal planner to handle the richer temporal domains (i.e. actions can have intermediate effects). Futhermore, the planner applies “critical paths” as a backbone for the search in the solution extraction phase, so that irrelevant search branches are pruned early. This improves the performance even in more restricted temporal planning domains. In our experimental evaluation, CPPlanner outperforms two leading plangraph-based optimal temporal planning systems, TGP and TPSYS, in almost all test cases. The state-of-theart optimal planner CPT and latest temporal planning domains in the international planning competition in 2004 and 2006 are also used in the experimental evaluation