Planning as Heuristic Forward search Brian c。 Willams March31. 2004 16412J6834J Slides with help from: Prof maria Fox Readings in Planning as Forward Heuristic Search The ff planning system Fast Plan Generation Through Heuristic Search, by Jorg Hoffmann and Bernhard Nebel Journalof Artificial Intelligence Research 2001 “" Planning as heuristic search,” by blai Bonet and Hector Geffner. Artificial Intelligence Journal, 2001
Planning as Heuristic Forward Search Brian C. Williams March31, 2004 16.412J/6.834J Slides with help from: Prof. Maria Fox Readings in Planning as Forward Heuristic Search “The FF Planning System: Fast Plan Generation Through Heuristic Search,” by Jorg Hoffmann and Bernhard Nebel, Journal of Artificial Intelligence Research, 2001. “Planning as Heuristic Search,” by Blai Bonet and Hector Geffner, Artificial Intelligence Journal, 2001
Outline Introduction to ff FF Search Algorithm FF Heuristic Fn FF Example Appendix: HSP Example: Polish Move from room x to room y Polish from room x to room y pre: robot is in x, door open pre: door open add: robot is in y add: floor polished del: robot is in x Initial State Open door n In(a) pre: door is closed Closed add door is open del: door is closed Final State (B) Close door Closed door is open Polished add: door is closed del: door is open
Outline Introduction to FF FF Search Algorithm FF Heuristic Fn FF Example Appendix: HSP Example: Polish Move from room x to room y pre: robot is in x, door open add: robot is in y del: robot is in x Open door pre: door is closed add: door is open del: door is closed Close door pre: door is open add: door is closed del: door is open Polish from room x to room y pre: door open add: floor polished Initial State In(A) Closed Final State In(B) Closed Polished
Planning as Forward heuristic search Planning can be seen as a state space search for a path from the initial state to a goal state Planning research has largely not been concerned with finding optimal solutions Although heuristic preference to shorter plans Planning research has largely used incomplete or uninformed search methods Breadth first search Meta search rules >The size of most state spaces requires informative heuristics to guide the search Review: Search Strategies Breadth first search (Uninformed) systematic search of state space in layers A* search (Informed) Expands search node with best estimated cost Estimated cost =cost-so-far optimistic-cost-to-go Greedy search Expands search node closest to the goal according to a heuristic function Hill-climbing search Move towards goal by random selection from the best children To apply informed search to planning need heuristic fn
Planning as Forward Heuristic Search Planning can be seen as a state space search, for a path from the initial state to a goal state. Planning research has largely not been concerned with finding optimal solutions. Although heuristic preference to shorter plans. Planning research has largely used incomplete or uninformed search methods. Breadth first search Meta search rules ÎThe size of most state spaces requires informative heuristics to guide the search. Review: Search Strategies Breadth first search (Uninformed) systematic search of state space in layers. A* search (Informed) Expands search node with best estimated cost. Estimated cost = cost-so-far + optimistic-cost-to-go Greedy search Expands search node closest to the goal according to a heuristic function. Hill-climbing search Move towards goal by random selection from the best children. Î To apply informed search to planning need heuristic fn
Fast Forward (FF) Forward-chaining heuristic search planner Basic principle: Hill-climb through the space of problem states, starting at the initial state Each child state results from apply a single plan operator Always moves to the first child state found that is closer to the goal Records the operators applied along the path E The operators leading to the goal constitute a plan Outline Introduction to ff FF Search Algorithm FF Heuristic Fn FF Example AppendiX: HSP
Fast Forward (FF) Forward-chaining heuristic search planner Basic principle: Hill-climb through the space of problem states, starting at the initial state. Each child state results from apply a single plan operator. Always moves to the first child state found that is closer to the goal. Records the operators applied along the path. ÖThe operators leading to the goal constitute a plan. Outline Introduction to FF FF Search Algorithm FF Heuristic Fn FF Example Appendix: HSP
Planning Problem and State Space A planning problem is a tuple <P, A, I, G> Propositions P Ground actions A are instantiated operators Initial state I is a subset of P, and Goal state G is a subset of P The state space of a problem consists of all subsets of propositions P a transition between two states is any valid application of an action, that is, its preconditions are satisfied FF Search Strategy FF uses a strategy called enforced hill-climbing Obtain heuristic estimate of the value of the current state Find action(s)transitioning to a better state Move to the better state Append actions to plan head E Never backtrack over any choice
Planning Problem and State Space A planning problem is a tuple <P, A, I, G>: Propositions P Ground actions A are instantiated operators Initial state I is a subset of P, and Goal state G is a subset of P. The state space of a problem consists of all subsets of propositions P. A transition between two states is any valid application of an action, that is, its preconditions are satisfied. FF Search Strategy FF uses a strategy called enforced hill-climbing: Obtain heuristic estimate of the value of the current state. Find action(s) transitioning to a better state. Move to the better state. Append actions to plan head. Ö Never backtrack over any choice