TLP-GP
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)
Slides:
Cours - Planification temporelle (Fr)
Publications:
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)