Complexity Results for SAS+ Planning

Abstract

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