Temporal planning through mixed integer programming: A preliminary report

Abstract

Temporal planning is an important problem, as in many real world planning domains actions have different durations and the goals should be achieved by a specified deadline, or as soon as possible. This paper presents a novel approach to temporal planning that is based on Mixed Integer Programming. In the new framework, a temporal planning domain is modeled by two sets of linear inequalities. The first set involves integer variables and is a Graphplan-like encoding of a simplification of the original problem where the duration of the actions is ignored. The second set involves both integer and real valued variables, and models the temporal aspects of the problem. The two sets interact through the common integer variables, and their combination can be solved by using available Mixed Integer Programming software. The new method aims at generating good solutions quickly, under different minimization objectives.Preliminary experimental results illustrate the effectiveness of our approach. © Springer-Verlag Berlin Heidelberg 2002.