[Thinking topic]: Completeness and minimality..

["Subbarao Kambhampati" <rao@asu.edu>]

[Part of the required participation in the class involves taking part
in the blog discussions--and giving answers to thinking topics. Here
is one]

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?
exponential? etc)