Premium
COMPLEXITY RESULTS FOR SAS + PLANNING
Author(s) -
Bäckström Christer,
Nebel Bernhard
Publication year - 1995
Publication title -
computational intelligence
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.353
H-Index - 52
eISSN - 1467-8640
pISSN - 0824-7935
DOI - 10.1111/j.1467-8640.1995.tb00052.x
Subject(s) - computational complexity theory , formalism (music) , plan (archaeology) , computer science , mathematics , decision problem , theoretical computer science , algorithm , art , musical , archaeology , visual arts , history
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.