COMPLEXITY RESULTS FOR SAS⁺ PLANNING 论文

摘要

We have previously reported a number of tractable planning problems defined in the SAS + formalism. This article complements these results by providing a complete map over the complexity of SAS + planning under all combinations of the previously considered restrictions. We analyze the complexity of both finding a minimal plan and finding any plan. In contrast to other complexity surveys of planning, we study not only the complexity of the decision problems but also the complexity of the generation problems. We prove that the SAS + ‐PUS problem is the maximal tractable problem under the restrictions we have considered if we want to generate minimal plans. If we are satisfied with any plan, then we can generalize further to the SAS + ‐US problem, which we prove to be the maximal tractable problem in this case.