[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]

[Thinking topic]: Completeness and minimality..

[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)