See if you can crack some of these...
[0.][Don't ask why something is bad. Ask why it is not worse?] We said that regression searches in the space of partial states or "sets" of real world states. We also said that there are
3^n such partial states (where n is the number of state variables). However, given that there are actually 2^n complete states,
there should be 2^{2^n} distinct sets of states. How come regression is searching in only 3^n of them? (Notice 3^n is hugely better
than 2^2^n).
[1] One thing that I left unsaid w.r.t. planning graph based heuristic computation is how many layers the planning graph should be expanded. Can you see a natural place to stop expanding?
Also, if you are too lazy to go all that far, can you think of how the heuristic will change if you expanded it a little less farther than is needed?
[2]Suppose the actions have differing costs (i.e., they are not all equally costly). Can you think of how planning graph based heuristics will behave in that case? (how does your answer to 1 above change?)
[3] In all the actions we looked at, we assumed that the effects are unconditional. That is, the action will give all its effects once it executed. Consider modeling the action of driving a bus from tempe to LA
The requirements for the driving are that the bus is originally in Tempe (and that there is a driver). The "unconditional" effects of the action are that the bus will be in LA, and the driver also will be in LA.
Now how about anyone else who is in the bus? Suppose Tom is in the bus when it is in Tempe--Tom will be in LA after the action. And yet, Tom being in the bus is not a requirement of the bus taking off. In
these cases, the effect of tom being in LA is a "conditional effect" ---if Tom is in the bus before the action, then Tom will be in LA after the action. How do you see progression and regression changing
in the presence of conditional effects?
Rao
ps: if you are curious about planning graph heuristics, check out
http://rakaposhi.eas.asu.edu/pgSurvey.pdf
and
http://rakaposhi.eas.asu.edu/pg-tutorial
Subscribe to:
Post Comments (Atom)
Re question 0- when you say there are 2^{2^n} distinct sets of states, are you saying (when n=2 for example) that it's (4 choose 0) + (4 choose 1) + ... + (4 choose 4) = 1 + 4 + 6 + 4 + 1 = 16 different "sets of states"? So that creates a kind of overlap where the sets of 3 states contain the sets of two states as subsets.
ReplyDeleteThat confuses me.
For n=2, I see 4 distinct states and 9 partial states. I also see that each distinct state has n^2 = 4 of the partial states that potentially "map" to it. For example, the state TF can map to {--, -F,T-, TF}. And TT can map to {--, -T, T-, TT}. So the "-" creates that "overlap" where the same partial state can map to multiple distinct states.
So even though there are 16 distinct sets of states, I can't see how to "map" these sets to actual states.
Q0: Possibly because we are going from a state that has a high branching factor down to states with a lower branching factor.
ReplyDeleteQ1: Wouldn't you just keep expanding till a valid state is found? I assume if you stopped too early you would have a partial solution with some of the conditions satisfied but not all.
Q2: It should expand the states with the least cost first like A* search. One could set a upper cost limit and once a branch reaches that limit it is cut and the search moves onto the next branch
0. My guess for this would be because we are only considering three values for each term, something like {T/F/Undefined}. This would give 3^n total partial states whereas 2^2^n can be seen to assign each complete state a {complete/partial} tag. This second method is inefficient because it considers both values {T/F} for terms that are not specified. In regression we do not specify these variables at all and so do not consider all complete states with both values for unspecified variables. We just assume that they can have any value, or are undefined, reducing the space to 3^n.
ReplyDelete1. The most natural place to stop expanding would be when all possible states have been reached in a level, when two consecutive levels are the same. The states that this is when the graph has "leveled off". This makes sense because each level after would be the same as no no actions would be possible to introduce new states.
If you expanded a little less than needed to acheive a state it could be a huge problem in the evaluation because the cost associated with reaching that state would then be set to infinity. This would also make the heuristic inadmissible because the true cost of the state is < infinity.
2. The planning graph heuristic could be made to accommodate the varying costs by making each level a certain specific cost increase and grabbing the associated actions that have a cost less than the cumulative step costs of each level from the initial level where the action first applies. If the heuristic was kept the same though, it would not be a very good heuristic as very high cost actions would be evaluated the same as low cost actions. I believe it would still be admissible. Not sure how it would change my answer to 1 though.
3. I imagine that progression and regression would change by increased branching factor as the conditions would need to be accounted for, both if Tom was on the bus or not for every action. Plus, the derived plan wouldn't be guaranteed to work unless there was a way to check the state of the conditions while traversing the space and choosing the appropriate action.
0. I agree with Alex here, that the 3^n comes from T,F,Undefined
ReplyDelete1. Just going to add to what others have said. From Russell & Norvig p396-7
"We continue in this way ... until we reach a level where two consecutive levels are identical. At this point, we say that the graph has leveled off. Every subsequent level will be identical, so further expansion is unnecessary."
If a graph has leveled off, the cost for items not in the graph would be infinity. However, if we stop expanding before the graph leveled off, we wouldn't be able to say that the cost is infinity for items not yet in the graph, but rather that it is d+1 where d is the depth to which we expanded.
2. If the heuristic takes into account the cost of actions to reach that particular state, then the h-value would be affected.
This changes my answer in 1 because we wouldn't be able to say the cost is d+1, but instead would have to say a cost larger than d.
3. What Shawn wrote makes the most sense to me for this problem, but if we are considering the conditional effects for progression, at what point should we assign their values? The beginning (ie the root node), or the end (after a solution has already been found)?
None of you got the answers to 0 and 3 right..they are actually related--you can get 2^2^n states with actions with conditional effects...
ReplyDeletesee if you can figure this by the class
rao