Tractable Monotone Temporal Planning

Vol. 22 (2012): Twenty-Second International Conference on Automated Planning and Scheduling

Volume

Vol. 22 (2012): Twenty-Second International Conference on Automated Planning and Scheduling

Full Technical Papers

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.

10.1609/icaps.v22i1.13501