We saw that Planning can be modeled as a search problem--where the state involves
state variables, and actions are "STRIPS" actions with preconditions and effects.
We had also seen that CSP too can be posed as a search problem, but unlike normal search problems,
which can have *any* complexity (recall that theorem proving can be cast as a search--and it is only semi-decidable),
CSP is *only* NP-complete.
What is the complexity of action planning? Is it NP-complete? More?
Before answering this, consider the tower of hanoi problem. Can you write the legal moves for
the tower of hanoi problem as STRIPS actions? If you can, what does it tell you about the complexity of planning?
Consider the "Bounded-length planning" problem, which takes a planning problem and a length bound "b" and attempts to find if there is a plan of length "b" or less that can solve the problem. How might the complexity of bounded length planning be related to the complexity of normal STRIPS planning?
6 comments:
I guess the main factor is whether there is exists a plan or it's actually impossible.
If there exists a plan, we can verify it in polynomial time. Thus it's at worst NP-Complete.
On the other hand non-existence of the plan seems undecidable.
Re: Sukru's comment
The intuition is reasonable, but not quite right.
If the plan exists, are you sure you can verify it in polynominal time? (In particular, how it the length of the Tower of Hanoi problem related to its input spec?)
if the plan doesn't exist, will you really be undecidable? In particular, consider that STRIPS planning is essentially looking for paths between states. Given that we are considering finite state spaces, why would you need to look for infinitely long paths?
rao
I see, the plan itself can be exponentially long, thus the algorithm is not even in p-space.
However, can't we have infinitely long plans due to Father-Of(Father-Of(...)) like recursive predicates? ... On the second thought, the number "actions" is limited, and since actions cannot trigger infinitely recursive predicates, the answer is no.
Thanks
As for the possibility of infinite-length plans: It is possible to formulate planning problems in which there are infinitely many states, but then they cannot be formulated to have finitely many state variables with finite ranges. In that case, specifying STRIPS actions becomes impossible (as their lists of modifications must in general be infinitely long). If we require an action only have finite effects then it seems that only a subset of all actions on any infinite domain can be STRIPS actions.
I just wonder whether we can define an action plan problem in which the state changing may depend on the outputs of actions. For example, when we are looking for the largest prime number smaller than 1000, we can do the action PrimeTest(x) for all numbers from 1000 to 2. If PrimeTest(x) returns true, we will add the state prime(x) to the current state set; otherwise, the state ~prime(x) is added. Could we formulate this plan problem?
For "Bounded-length planning" problem, the complexity depends on the 'b' value.
Since we have "STRIPS" actions, given any state and an action, we can compute the resulting state in polynomial time.
Hence the question is, how large 'b' can be so that we are still polynomial with respect to the number of actions and fluents 'n'? Lets assume 'b' is polynomial with respect to n. Also lets assume we have a given initial state. In that case, since we can apply any combination of actions, there may be exponential number of possible sequences of length 'b'. Hence it looks like this is at least NP(Actually, it really looks like a 'classic' NP-complete problem).
Hence cutting 'b' to 'log n' or less would yield a polynomial time planning, since then we have n total possible sequences, so we can just check all of them.
When 'b' is more than polynomial to 'n', the complexity keeps rising appropriately, and will be similar to action planning after 'b' passes a certain boundary.
Btw if we allow incomplete /too many initial states, the complexity jumps one level higher in all cases.
Post a Comment