Temporal Landmarks for Overconstrained Planning Problems with Deadlines

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. Partial plans in the search tree that are not compliant with the information comprised in this graph are pruned. We introduce a novel search scheme that builds a landmarks graph in each tree node and which notably improves the rate of detection of unsolvable problems.