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 fnPlanning 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