Temporal landmark graphs for solving overconstrained planning problems

Abstract

This paper presents TempLM, a novel approach for handling temporal planning problems with deadlines. The proposal revolves around the concept of temporal landmark, a proposition that must be necessarily true in all solution plans to achieve the problem goals within their deadlines. The temporal landmarks extracted from the problem form a landmarks graph where nodes are landmarks and edges represent temporal as well as causal relationships between landmarks. The graph comprises information about which propositions and when these propositions must be achieved in a solution plan, information that is later used to guide the search process as well as reduce the search space. Thus, the partial plans of the search tree that are not compliant with the information comprised in this graph are pruned. We present an exhaustive experimentation evaluation in overconstrained and unsolvable problems and we compare the performance of TempLM with other state-of-the-art planners. The results will show the efficiency of TempLM in the detection of unsolvable problems. (C) 2016 Elsevier B.V. All rights reserved: