I am reading the two articles below to try to figure out whether STRIPS are NP-complete or PSPACE-complete. Specifically, I am trying to figure out the complexity of finding optimal solutions using STRIPS.

Also, Bylander (1994) defines PLANMIN to find the shortest plan. This is tied to length directly where minimizing plan length is the objective. I'm not sure if I can apply his reasoning to my situation. I use a objective function other than length, for which I need to find the entire plan before calculating its utility, then find a plan that minimizes that utility. So I can't simply stop my search and backtrack if I find a plan longer than the shortest one I have found so far. Does this condition make this search NP-complete?

Thank you in advance.

Bylander, T. (1994). The computational complexity of propositional STRIPS planning. Artificial Intelligence, 69(1–2), 165–204. https://doi.org/10.1016/0004-3702(94)90081-7

Erol, K., Nau, D. S., & Subrahmanian, V. S. (1991). Complexity, Decidability and Undecidability Results for Domain-Independent Planning: A Detailed Analysis, 76(CS-TR-2797), 75–88.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.