Monday, January 21, 2008

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


Subbarao Kambhampati said...

[[Comment from Anupam]]
I don't seem to be able to post my comments on the blog. The verification image for posting is not visible, and I'm not sure if anybody else facing the same issue.

Here are my comments on the blog topic:

0. There can be infinite non-minimal solutions for a problem.

1. yes, progression tree can reach every solution(node).

2. Regression planner would be complete only for minimal plans.

3. No, conditions on regressing over a state imply that only a minimal plan would be found.

4. Yes, if progression is performed in depth-first manner.

5. Could not understand the question.

6. Minimizing would be exponentially complex in the length of non-minimal plan.


Oleg Bakun said...

If next action is chosen in some weird way (alternating “put on” and “take of” on every iteration and always prefer block C) then the plan may not be created at all. For example: repeat first two steps infinite number of times.
Minimization of non-minimal plan will take O(n log n). Not any non-minimal plan will consist of actions and their “antipodes”. In the worst-case scenario, we will need to know complete description of all n+1 (world) states that were created (which make it pseudo-polynomial). After that we can sort the states and compare them.


Kartik said...

0. Clearly, the number of non-minimal solutions could be infinite because we can keep tacking on actions that preserve soundness but aren't really *useful* in the sense of a regression planner (must give some useful literal).

The number of minimal solutions could be more than 1, and I think it would depend on the branching factor wrt actions: if there is more than one action that will achieve the exact same sub-goals, then clearly 2 plans that incorporate one or the other will be different yet minimal.

1. Progression planning: if we look at all possible actions, and those support all required literals (i.e. there exists a solution to the problem) then yes, prog. planner should find *a* solution. Will it find all possible solutions (including minimal ones)?- Not necessarily, depending on the approach it takes: graphplan vs. strips (sussman anomaly).

2. Given enough time and space, yes, regression planner should be complete for all kinds of plans.

3. It doesn't seem like regression planner should find non-minimal plans, because we use an incremental approach (commandment 1 of reg. planning: thou shalt not disturb that which is not thine). Also, every step gives something productive (thou shalt contribute something).

4. Progression planner could find non-minimal plans, because given a stage at which it has to choose between 2 actions, it could choose one, go into a cycle, come back to the same junction and choose the other and go on to a solution. This would be non-minimal.

5. Actually it seems like if you could produce non-minimal plans, sussman anomaly *should* be serializable (wrt a non-minimal plan; if you aren't in the race for minimality).

Here are some good notes on serializability: Spring 2003

6. Possibly non-minimal? Just confirming that fact should take exp. time, leave alone minimizing it.

Tuan A. Nguyen said...

1 & 2. Progression is a generic model with a nondeterministic choice of actions. Depending on what strategy used to choose action (deterministic), it's may be complete or not. Breath-first search or A* with admissible heuristic ensures completeness, for instance; but simply depth-first search in state space may be stuck in loop (e.g, put_a_on_b, then put_b_on_table, then put_a_on_b, then put_b_on_table, ...). The same for regression search.

3. Also, regression planner with some action/subgoal selection strategy may find non-minimal plans. For instance, if action a1, which is chosen to support p1 (its only effect), has pre p2. And p2 now is supported by a2 whose effects are p1 and p2. Then the sequence a2 -- a1 can be replace by only a2.

4. Depth-first search (progression search approach) may cause cycle in solution path, which is non-minimal solution.

ravi said...

0. Infinite.

Yes(it has to run forever).

Yes. Any plan obtained by a progression planner can be obtained by a regression planner.

Depends on the order in which the states are processed.
If the states are processed in breadth first manner, then the planner will never find non-minimal plans.
If the states are processed in depth first manner, then the planner can find non-minimal plans.

No. We can achieve on(B,C) first by using the non-minimal plan unstack(C,A), putdown(C), stack(B,C).
We can then achieve on(A,B) by stack(A,B).

It would be exponential in the length of the original non-minimal plan.

Brandon said...

Here's my attempt, expressed in gibberish:

0. I guess it depends on the actions the planner has at its disposal. If for at least one action/sequence, there is a symmetric action/sequence that "undoes" the other (such as taking a block off another block, but not undoing a nuclear explosion), or if there exists an irrelevant action that doesn't affect the goal or preconditions of actions that do affect the goal (which you could throw in for fun), then there are infinite.

1. Yes. It can generate any possible sequence of actions.

2. Yes, same.

3. It would depend on how you explore the space. If you do a complete, uninformed breadth-first search, for example, you're going to only find a minimal plan. If you do IDDF/something else informed by heuristics, you could possibly miss a minimal solution. Regression planner only considers the properties of the current state and previous state--nothing after the current state--so you could at least get into the same kind of loops with symmetric/irrelevant actions.

4. Same thing, swapping "previous" for "next."

5. I wouldn't think so. A non-minimal solution to a subgoal could miraculously fall upon a step that is necessary for a later goal/action leading to said goal.

6. It certainly seems hard. It'd be easy enough to remove irrelevant actions by comparing their effects with the preconditions of every following action and the goal, but the only way I can think to minimize the rest would be to search the entire space up to the size of the possibly non-minimal plan, which would be exponential.