Monotone Temporal Planning: Tractability, Extensions and Applications

摘要

We describe a polynomially-solvable class of temporal planning problems. Polynomiality follows from two assumptions. Firstly, by supposing that each fluent (fact) can be established by at most one action, we can quickly determine which actions are necessary in any plan. Secondly, the monotonicity of fluents allows us to express planning as an instance of STP~≠ (Simple Temporal Problem with difference constraints). This class includes temporally-expressive problems requiring the concurrent execution of actions, with potential applications in the chemical, pharmaceutical and construction industries. Any (temporal) planning problem has a monotone relaxation, which can lead to the polynomial-time detection of its unsolvability in certain cases. Indeed our relaxation is orthogonal to the relaxation based on ignoring deletes used in classical planning since it preserves deletes and can also exploit temporal information.