Monday, September 25, 2006

About Relaxed Planning Graph

Some students are a little confusing about the relaxed planning graph construction. Here, I'll briefly explain how to construct it.

Please check the block world example on the slides 7 and 8 of week5-f06-1.ppt.

In progression or regression planning, each node is a state consisting multiple state variable values. However, in relaxed planning, each node is just a state variable value. Like in slide 8, at the initial level, there are 5 nodes, corresponding to the initial state( Ontable(A),Ontable(B), Clear(A), Clear(B), hand-empty)

In order to construct the next level, you apply all the possible actions to current level to generate possible state variable values. Like in the example, if you pick the action PICK-A, with precondition: hand-empty, clear(A) and ontable(A). The result would be holding(A), ~ontable(A), ~hand-empty, ~clear(A). So you can check the first level add some nodes like h-A(holding A), ~cl-A(clear (A)), ~he(hand~empty). However, you might notice that ~ontable(A) is not in the figure. But I guess the instructor omit some variables to make the figure readable. ~ontable(A) should be included in the first level.

Similarly, you can apply pick(B) to add more nodes. Note that all the nodes in previous level should be transferred to the next level by no-operation.

After you get the 1st level, you can apply the same strategy to generate more level.

You can construct the graph until it levels off, which means there's no change between two levels.

Please check slide 15 , 16 and 17 to find out how to obtain a relaxed plan.

Please correct me If I made anything wrong. Thanks!

-Lei

No comments: