Lecture slides for Automated Planning: Theory and Practice Chapter 3 Complexity of Classical Planning Dana S. Nau University of Maryland 06:22 AM February 11, 2020 Dana Nau: Lecture slides for Automated Planning Licensed under the Creative Commons Attribution-NonCommercial-ShareAlike License: http://creativecommons.org/licenses/by-nc-sa/2.0/ 1 Motivation

Recall that in classical planning, even simple s0 problems can have huge search spaces Example: DWR with five locations, three piles, three robots, 100 containers location 1 location 2 277 10 states About 10190 times as many states as there are particles in universe How difficult is it to solve classical planning problems? The answer depends on which representation scheme we use Classical, set-theoretic, state-variable Dana Nau: Lecture slides for Automated Planning Licensed under the Creative Commons Attribution-NonCommercial-ShareAlike License: http://creativecommons.org/licenses/by-nc-sa/2.0/ 2 Outline

Background on complexity analysis Restrictions (and a few generalizations) of classical planning Decidability and undecidability Tables of complexity results Classical representation Set-theoretic representation State-variable representation Dana Nau: Lecture slides for Automated Planning Licensed under the Creative Commons Attribution-NonCommercial-ShareAlike License: http://creativecommons.org/licenses/by-nc-sa/2.0/ 3 Complexity Analysis Complexity analyses are done on decision problems or languagerecognition problems Problems that have yes-or-no answers

A language is a set L of strings over some alphabet A Recognition procedure for L A procedure R(x) that returns yes iff the string x is in L If x is not in L, then R(x) may return no or may fail to terminate Translate classical planning into a language-recognition problem Examine the language-recognition problems complexity Dana Nau: Lecture slides for Automated Planning Licensed under the Creative Commons Attribution-NonCommercial-ShareAlike License: http://creativecommons.org/licenses/by-nc-sa/2.0/ 4 Planning as a Language-Recognition Problem

Consider the following two languages: PLAN-EXISTENCE = {P : P is the statement of a planning problem that has a solution} PLAN-LENGTH = {(P,n) : P is the statement of a planning problem that has a solution of length n} Look at complexity of recognizing PLAN-EXISTENCE and PLAN-LENGTH under different conditions Classical, set-theoretic, and state-variable representations Various restrictions and extensions on the kinds of operators we allow Dana Nau: Lecture slides for Automated Planning Licensed under the Creative Commons Attribution-NonCommercial-ShareAlike License: http://creativecommons.org/licenses/by-nc-sa/2.0/ 5 Complexity of Language-Recognition Problems

Suppose R is a recognition procedure for a language L Complexity of R TR(n) = Rs worst-case time complexity on strings in L of length n SR(n) = Rs worst-case space complexity on strings in L of length n Complexity of recognizing L TL = best time complexity of any recognition procedure for L SL = best space complexity of any recognition procedure for L Dana Nau: Lecture slides for Automated Planning Licensed under the Creative Commons Attribution-NonCommercial-ShareAlike License: http://creativecommons.org/licenses/by-nc-sa/2.0/ 6

Complexity Classes Complexity classes: NLOGSPACE (nondeterministic procedure, logarithmic space) P (deterministic procedure, polynomial time) NP (nondeterministic procedure, polynomial time) PSPACE (deterministic procedure, polynomial space) EXPTIME (deterministic procedure, exponential time) NEXPTIME (nondeterministic procedure, exponential time) EXPSPACE (deterministic procedure, exponential space) Let C be a complexity class and L be a language

L is C-hard if for every language L' C, L' can be reduced to L in a polynomial amount of time NP-hard, PSPACE-hard, etc. L is C-complete if L is C-hard and L C NP-complete, PSPACE-complete, etc. Dana Nau: Lecture slides for Automated Planning Licensed under the Creative Commons Attribution-NonCommercial-ShareAlike License: http://creativecommons.org/licenses/by-nc-sa/2.0/ 7 Possible Conditions Do we give the operators as input to the planning algorithm, or fix them in advance?

These take us Do we allow infinite initial states? outside classical Do we allow function symbols? planning Do we allow negative effects? Do we allow negative preconditions? Do we allow more than one precondition? Do we allow operators to have conditional effects?* i.e., effects that only occur when additional preconditions are true Dana Nau: Lecture slides for Automated Planning Licensed under the Creative Commons Attribution-NonCommercial-ShareAlike License: http://creativecommons.org/licenses/by-nc-sa/2.0/ 8 Decidability of Planning Halting problem Can cut off the search at every path of length n

Next: analyze complexity for the decidable cases Dana Nau: Lecture slides for Automated Planning Licensed under the Creative Commons Attribution-NonCommercial-ShareAlike License: http://creativecommons.org/licenses/by-nc-sa/2.0/ 9 In this case, can write domain-specific algorithms e.g., DWR and Blocks World: PLAN-EXISTENCE is in P and PLAN-LENGTH is NP-complete no operator has PSPACE-complete or NP-complete Dana Nau: Lecture slides for Automated Planning >1 precondition some sets of operators Licensed under the Creative Commons Attribution-NonCommercial-ShareAlike License:for http://creativecommons.org/licenses/by-nc-sa/2.0/

10 PLAN-LENGTH is never worse than NEXPTIME-complete We can cut off every search path at depth n Here , PLAN-LENGTH is harder than PLAN-EXISTENCE Dana Nau: Lecture slides for Automated Planning Licensed under the Creative Commons Attribution-NonCommercial-ShareAlike License: http://creativecommons.org/licenses/by-nc-sa/2.0/ 11 Set-Theoretic and Ground Classical Set-theoretic representation and ground classical representation are basically identical For both, exponential blowup in the size of the input Thus complexity looks smaller as a function of the input size

every operator with >1 precondition Licensed under the Creative Commons Attribution-NonCommercial-ShareAlike License: is thehttp://creativecommons.org/licenses/by-nc-sa/2.0/ composition of other operators no operator has >1 precondition Dana Nau: Lecture slides for Automated Planning 12 State-Variable Representation Classical and state-variable representations are equivalent, except that some of the restrictions arent possible in state-variable representations e.g., classical translation of pos(a) b precondition on(a,x) two effects, one is negative on(a,x), on(a,b)

Like classical rep, but fewer lines in the table Dana Nau: Lecture slides for Automated Planning Licensed under the Creative Commons Attribution-NonCommercial-ShareAlike License: http://creativecommons.org/licenses/by-nc-sa/2.0/ 13 Summary If classical planning is extended to allow function symbols Then we can encode arbitrary computations as planning problems Plan existence is semidecidable Plan length is decidable Ordinary classical planning is quite complex

Plan existence is EXPSPACE-complete Plan length is NEXPTIME-complete But those are worst case results If we can write domain-specific algorithms, most well-known planning problems are much easier Dana Nau: Lecture slides for Automated Planning Licensed under the Creative Commons Attribution-NonCommercial-ShareAlike License: http://creativecommons.org/licenses/by-nc-sa/2.0/ 14