able to answer these questions (add your answers to the blog)
1. If you grew the planning graph (without mutexes) to level-off and
found that a particular literal p never entered the proposition
list at any level. WHat is the length of the plan needed to achieve
p from the init state?
2. In the example above, suppose an action A never entered any action
layer. Can you lose any plans by refusing to consider A as an
option in the regression search (i.e., you never branch on A)? What
about partial order planning?
3. In level 5 of the planning graph propositions p1 and p2 are not
mutex. Is it possible for the propositions to be mutex at level 3?
How about level 9?
4. Suppose a planning graph with mutexes has been grown to level off
(i.e., until two consecutive proposition levels have the same
propositions and binary mutexes).
4.1. If propositions p, q, r appear first in level 17 with no pair of
them marked mutex. Are we guaranteed to have a plan of length 17 for
achieving p,q,r? If not, how long could the plan for p,q,r be?
4.2. If propositions p,q appear first in level 12 without mutex. Are
we guaranteed to have a plan of length 12 for them? If not, how long
can the plan be?
4.3. If proposition p appears first in level 7. Are we guaranteed to
have a plan of length 7 for achieving p? If not how long can the plan
be?
Rao
2 comments:
Ok. I'll take a shot at these. If you notice that my logic is flawed, please post a correction.
1. Since p never appeared it is not reachable and the plan length to reach p is infinite.
2. I think this means that none of the preconditions for A were ever met. If this is the case then action A can be ingnored for regression search. I'm not sure if it can be ignored for partial order planning.
3. Yes at level 3 since a subsequent set of actions can make them not mutex at level 5. No at level 9 since one or more actions makes them not mutex in level 5 and those actions are propogated forward.
4.1. No. We can only estimate the minimum plan if all the binary and ternary mutexes for p,q,r have been cleared. The length of the plan for p,q,r could be infinite.
4.2. No. We only know that it will take at least 12 steps to achieve p,q. The actual plan length could be infinite.
4.3. No. We only know that the plan length will be at least 7. The actual plan length could be infinite.
Kirk
Awesome, Kirk!
Just a couple of clarifications.
(part 3) There is no point in using A in the Partial order planning either.
Notice that irrespective of how the plan is made, in the end it is executed in the forward direction. So, for A to be present anywhere in the plan there must be some state, reachable from initial state, where A 's preconditions must hold. Since A is in the PG at level-off level, this is clearly not true.{see quote at the end}
For 4.1
It is not that you need to check ternary mutexes--but that have to check for *all* n-ary mutexes before you can be sure that h_lev
= h* (i.e., there will be a plan of length h_lev for the goals).
The *number* of goals is actually a complete red-herring here. In trying to achieve a single goal g, I may need to use an action which has n preconditions {p1..pn}. Thus, you will need to do n-ary mutex detection even if you are only trying to guarantee that a single goal, p, will definitely be reachable by the level where it is present.
[Another way of seeing the point above is to notice that if your real problem is to ensure that n subgoals {p1...pn}
will be achievable by the level they are reachable in the PG, then
I can convert it into a problem involving achievability of just one goal p* as follows:
Makeup a dummy action A* which has
preconditions {p1..pn} and has
a single effect p*. Now checking that p* is really achievable involves checking {p1...pn} are really achievable.
Cheers
Rao
Quote (made for order):
"Life can only be understood backwards, but it must be lived forward."
Soren Kierkegaard
Post a Comment