To the goal state In(B) In the following we develop the tree of nodes visited in the state space search by the FF algorithm. We label each node with its relaxed distance estimate. For each node we demonstrate how the relaxed distance estimate is computed, including the plan grap generated from the node to the goal state, the relaxed plan that is extracted, and the resulting heuristic cost of that node FF starts with the initial state as the root of the tree Node 1 In(A) Estimate? Closed FF then computes the heuristic value of Node 1 by generating a relaxed plan graph, from Node I to the goal In(a) noop In(a) nooD In(a) Move(A B In(B) Closed noo Closed Closed Opened noop Opened Polish Each operator is relaxed by simply eliminating its delete list. The relaxed plan graph is similar to that produced by GraphPlan, except that it does not contain any mutual exclusion relations. The relaxed plan graph for Node 1 consists of three fact layers and two action layers. The three goal propositions appear in the third fact layer Note that, for simplicity, in our drawing we have drawn each action once, in the action layer in which it first appears. That action should also appear in all subsequent layers However, its consequences are also achieved through null operations(noops). For example, in the graph above, FF or Graph Plan would include an arc from Opened in layer 2 to Closed in layer 3, representing the Close action. When generating the relaxed plan, FF never selects these subsequent actions, since it al ways prefers noops to actions Hence, they serve no useful roleTo the goal state: In(B) Closed Polished In the following we develop the tree of nodes visited in the state space search by the FF algorithm. We Label each node with its relaxed distance estimate. For each node we demonstrate how the relaxed distance estimate is computed, including the plan graph generated from the node to the goal state, the relaxed plan that is extracted, and the resulting heuristic cost of that node. FF starts with the initial state as the root of the tree: FF then computes the heuristic value of Node 1 by generating a relaxed plan graph, from Node 1 to the goal: Each operator is relaxed by simply eliminating its delete list. The relaxed plan graph is similar to that produced by GraphPlan, except that it does not contain any mutual exclusion relations. The relaxed plan graph for Node 1 consists of three fact layers and two action layers. The three goal propositions appear in the third fact layer. Note that, for simplicity, in our drawing we have drawn each action once, in the action layer in which it first appears. That action should also appear in all subsequent layers. However, its consequences are also achieved through null operations (noops). For example, in the graph above, FF or GraphPlan would include an arc from Opened in layer 2 to Closed in layer 3, representing the Close action. When generating the relaxed plan, FF never selects these subsequent actions, since it always prefers noops to actions. Hence, they serve no useful role. In(A) Closed In(A) Closed Opened In(A) In(B) Closed Opened Polished noop noop Open noop noop noop Polish Move(A,B) Node 1 In(A) Estimate ? Closed Close