Regnier, Pierre
Tractable Monotone Temporal Planning
Cooper, Martin C. (University of Toulouse) | Maris, Frederic (University of Toulouse) | Regnier, Pierre (University of Toulouse)
This paper describes a polynomially-solvable sub-problem of temporal planning. Polynomiality follows from two assumptions. Firstly, by supposing that each sub-goal fluent can be established by at most one action, we can quickly determine which actions are necessary in any plan. Secondly, the monotonicity of sub-goal fluents allows us to express planning as an instance of STP≠ (Simple Temporal Problem, difference constraints). Our class includes temporally-expressive problems, which we illustrate with an example of chemical process planning.