in the blog discussions--and giving answers to thinking topics. Here
An interesting issue about planner completeness is whether or not the
planner is capable of finding *every plan* for the problem.
Let us get some terminology straight.
A sequence of actions a1...an is considered a solution to a problem
[I,G] if we can
execute the sequence starting in state I and G will hold in the final
state after executing an.
A solution plan P: a1...an is said to be minimal if it is not
possible to remove any subset of actions from P
without violating its solution-ness.
An example of a non-minimal plan for achieving On(A,B) when A, B and C
are all on table is:
put A on C, take A of C, put A on B.
Cleraly, we can cut the first two actions out and it will still be a
solution (so it is a non-minimal solution).
Consider the following questions:
0. Given a planning problem that is solvable, how many solutions
(minimal as well as non-minimal) are there?
1. Is progression planner complete for all plans (including minimal
and non-minimal plans)?
2. Is regression planner complete for all plans (including non-minimal)?
3. Will regression planner ever find any non-minimal plans?
4. Will progression planner ever find any non-minimal plans?
5. If a planner is capable of producing non-minimal plans, then will
sussman anomaly be non-serializable for such a planner?
6. Given a possibly non-minimal plan, how costly would it be to
"minimize" it (i.e., remove redundant actions from it)?
(Complexity-wise... is it polynomial?