On the Use of Temporal Landmarks for Planning with Deadlines

Abstract

In this paper we present a temporal planning approach for handling problems with deadlines. The model relies on the extraction of temporal landmarks from the problem and the construction of a landmarks graph as a skeleton of the solution plan. A temporal landmark is a proposition that must be achieved in a solution plan to satisfy the problem deadline constraints. Each temporal landmark is associated to three temporal intervals, which are updated and propagated according to the landmarks orders and the deadline constraints. Then, the partial plans in the search tree that are not compliant with the information comprised in this graph are pruned. The experimental results will show that this approach is helpful to quickly detect unsolvable problems and it is also very effective to solve problems with deadlines in comparison to other state-of-the-art planners.