Temporally-Lifted Progression GraphPlan

TLP-GP Planner

We have developped an algorithm which solves temporally-expressive planning problems, that is problems for which all possible solutions require concurrency of actions. The planner TLP-GP which implements this algorithm constructs a simplified planning graph until the goals are attained, as in classic atemporal planners. It then establishes temporal constraints between actions and searches backward for a solution-plan in the planning graph using a disjunctive temporal constraint solver. If the search fails, the graph is extended to the next level and the search is restarted. This method can solve problems in a language whose expressivity is greater than PDDL 2.1. Preconditions can be required and effects can take place on any temporal interval relative to the start-time of an action. This algorithm can also take into account, in a very natural way, exogenous events as well as temporally extended goals. We also propose several different means of extending expressivity even further. TLP-GP is complete for the temporally-expressive sublanguages of PDDL 2.1.

We compared our planner with three state-of-the-art temporally-expressive planners such as LPGP, VHPOP and CRIKEY. These experimental trials not only show the efficiency of our approach but also demonstrate the practical possibility of solving temporally expressive problems which up until now were unsolvable by existing techniques.

In order to test and compare our system with LPGP, VHPOP and CRIKEY, we have developped new sets of problems :
Temporally-Expressive Planning Benchmarks
New Results on Temporally-Expressive Planning Benchmarks

TLP-GP Graphic Interface:
Example of solution-plan for problem "cooking01" (video)

Cours - Planification temporelle (Fr)


F. Maris, P. Régnier, "TLP-GP : Un planificateur pour la résolution de problèmes temporellement expressifs", dans Actes des 4èmes Journées Francophones de Planification, Décision et Apprentissage pour la conduite de systèmes (JFPDA-2009), Paris, Juin 2009. (pdf) (Fr)

F. Maris, P. Régnier, "TLP-GP: New Results on Temporally-Expressive Planning Benchmarks", in Proceedings of 20th IEEE International Conference on Tools with Artificial Intelligence (ICTAI-2008), Dayton OH, USA, November 2008. (pdf)

F. Maris, P. Régnier, "TLP-GP: Solving Temporally-Expressive Planning Problems", in Proceedings of 15th International Symposium on Temporal Representation and Reasoning (TIME-2008), pp 137-144, Montreal QC, Canada, June 2008. (pdf)

F. Maris, P. Régnier, "TLP-GP: a Planner to Solve Temporally-Expressive Problems", 6th International Planning Competition, Technical paper, 2008. (pdf)

F. Maris, P. Régnier, "A new set of temporally-expressive benchmarks", 6th International Planning Competition, Technical paper, 2008. (pdf)