Massachusetts Institute of Technology 16.412/6.834 Cognitive Robotics Distributed: Monday, 3/31/04 objective The purpose of the following handout is to walk you step by step through the execution of the ff planning algorithm, on a simple example. The ff algorithm is presented in the The FF Planning System: Fast Plan Generation Through Heuristic Search, by Jorg Hoffmann and Bernhard Nebel, Journal of Artificial Intelligence Research, 2001 Problem by a door), with the Polish operator added in move betveen rooms A and B, separated You are given operators for the door dome Door-2 Domain Operators Move(x, y) Pre: in(x) Add: in(y) Del Pre: closed Add: opened Del closed Close Pre Polish Pre: opened Add: polished Del: Consider the problem of generating a plan that moves from the initial state In(A) Closed
Massachusetts Institute of Technology 16.412/6.834 Cognitive Robotics Distributed: Monday, 3/31/04 Objective The purpose of the following handout is to walk you step by step through the execution of the FF planning algorithm, on a simple example. The FF algorithm is presented in the paper: The FF Planning System: Fast Plan Generation Through Heuristic Search,” by Jorg Hoffmann and Bernhard Nebel, Journal of Artificial Intelligence Research, 2001. Problem You are given operators for the door domain (move between rooms A and B, separated by a door), with the Polish operator added. Door-2 Domain Operators Move (x,y) Pre: in(x) opened Add: in(y) Del: in(x) Open Pre: closed Add: opened Del: closed Close Pre: opened Add: closed Del: opened Polish Pre: opened Add: polished Del: Consider the problem of generating a plan that moves from the initial state: In(A) Closed
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 role
To 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
To generate the relaxed plan, FF starts with the three goal propositions In(B), closed, Polished For each goal it selects a noop or action from action layer 2 that achieves it, preferring no-ops over actions. The selected actions/noops are highlighted in bold. In (B)is achieved by action Move(A, B), Closed is carried forward by a noop, and Polished is achieved using the Polish action. The corresponding subgoals for fact layer 2 are collected and consist of In(A), Closed, Open Next, actions and noops from action layer l are selected to achieve these subgoals. In(A) and Closed are achieved by noops, while Open is achieved with the Close action. The corresponding subgoals are all propositions in the initial state relaxed plan, shown in bold, consists of three actions--Open, Move(A, B)and polish, a The heuristic value of Node 1 is the number of actions in the relaxed plan. The comple lence. the heuristic value of node 1 is 3 FF expands Node 1 by considering the application of each action in the first layer of the relaxed plan. Note that FF only uses an action in this first layer if the effects of the action are used by an action in layer 2. ff stops evaluating actions as soon as it finds an action whose target state has a better heuristic value. If the heuristic value does not improve, it performs a breadth first search For Node 1, only one action, Closed, appears in the first layer of the relaxed plan, hence it is the only action expanded. The expanded graph is shown below, with Node 2 added Node 1 In(A) Estimate 3 Closed Node 2 In(A)Estimate? Opened lext we generate the relaxed plan graph and plan for Node 2, as shown below
To generate the relaxed plan, FF starts with the three goal propositions: In(B), Closed, Polished. For each goal it selects a noop or action from action layer 2 that achieves it, preferring no-ops over actions. The selected actions/noops are highlighted in bold. In(B) is achieved by action Move(A,B), Closed is carried forward by a noop, and Polished is achieved using the Polish action. The corresponding subgoals for fact layer 2 are collected, and consist of: In(A), Closed, Open Next, actions and noops from action layer 1 are selected to achieve these subgoals. In(A) and Closed are achieved by noops, while Open is achieved with the Close action. The corresponding subgoals are all propositions in the initial state. The heuristic value of Node 1 is the number of actions in the relaxed plan. The complete relaxed plan, shown in bold, consists of three actions -- Open, Move(A,B) and Polish – hence, the heuristic value of Node 1 is 3. FF expands Node 1 by considering the application of each action in the first layer of the relaxed plan. Note that FF only uses an action in this first layer if the effects of the action are used by an action in layer 2. FF stops evaluating actions as soon as it finds an action whose target state has a better heuristic value. If the heuristic value does not improve, it performs a breadth first search. For Node 1, only one action, Closed, appears in the first layer of the relaxed plan, hence it is the only action expanded. The expanded graph is shown below, with Node 2 added: Next we generate the relaxed plan graph and plan for Node 2, as shown below: Node 1 In(A) Estimate 3 Closed Estimate ? Open Node 2 In(A) Opened
In(a n(B) noop Opened Polish Polished The plan graph has one action layer, separating the current state and goal state fact layers The relaxed plan consists of three parallel actions: Move(A, B), Close, and Polish, resulting in a cost estimate of 3. The node value is the same as for Node 1 indicating a plateau. Hence, actions are explored in breadth first order until the first action is found with decreased heuristic cost. In this example, we evaluate each of the three concurrent actions of Node 2s plan, working in a top-down order, as they are written in the relaxed plan. However, no specific order for expanding the breadth first search is required First we expand the action Move(A, B) Node 1 In(a) Estimate 3 Closed Open Node 2 In(a) Estimate 3 Move(A, B) Node 3 In(B)Estimate? Opened Next we calculate the relaxed plan graph estimate for Node 3
In(A) Opened In(A) In(B) Closed Opened Polished noop noop Close Move(A,B) Polish The plan graph has one action layer, separating the current state and goal state fact layers. The relaxed plan consists of three parallel actions: Move(A,B), Close, and Polish, resulting in a cost estimate of 3. The node value is the same as for Node 1, indicating a plateau. Hence, actions are explored in breadth first order until the first action is found with decreased heuristic cost. In this example, we evaluate each of the three concurrent actions of Node 2’s plan, working in a top-down order, as they are written in the relaxed plan. However, no specific order for expanding the breadth first search is required. First we expand the action Move(A,B): Next we calculate the relaxed plan graph estimate for Node 3: Node 1 In(A) Estimate 3 Closed Estimate 3 Open Node 2 In(A) Opened Estimate ? Move(A,B) Node 3 In(B) Opened
In(B) n(B) ose Opened Once again the plan graph has a single action layer. The relaxed plan only contains two actions: Close and Polish, hence the cost of Node 3 is 2. This estimate is strictly better than that of Nodes l and 2; hence Node 3 moves FF off the plateau, and is chosen for further expansion. FF has two actions available to expand Node 3, either Close or Polish First choosing Close Node 4 is added to the search tree n(A) Estimate 3 n(A)Estimate Opened Move(A, B) In(B) Estimate 2 Opened Clos Polish Node 4 In(B) Estimate? The relaxed plan graph and plan for Node 4 is as follows
In(A) In(B) Closed Opened Polished In(B) Opened noop noop Close Move Polish Once again the plan graph has a single action layer. The relaxed plan only contains two actions: Close and Polish, hence the cost of Node 3 is 2. This estimate is strictly better than that of Nodes 1 and 2; hence Node 3 moves FF off the plateau, and is chosen for further expansion. FF has two actions available to expand Node 3, either Close or Polish. First, choosing Close, Node 4 is added to the search tree: Node 1 In(A) Estimate 3 Closed Open The relaxed plan graph and plan for Node 4 is as follows: Node 2 In(A) Estimate 3 Opened Move(A,B) Node 3 In(B) Estimate 2 Opened Estimate ? Close Polish Node 4 In(B) Closed