[SOLVED] SOCS 2010: https://aaai.org/ocs/index.php/SOCS/SOCS10/paper/view/2073/2500

A.I. PLANNING

Planning as Heuristic Search

Copyright By Assignmentchef assignmentchef

Heuristic Search
A Heuristic is a function that takes a state and returns an estimate of its distance from the goal.
Smaller = better, as nearer to a goal state

Heuristics are (usually) not perfect, or there is no search

For now, lets assume we have some function h(S) that gives us a distance to go from the state S to the goal:
For goal states, h(S) = 0
For other states, h(S) > 0

Best-First Search
Open list: priority queue with stable insertion

An ideal world

load-truck
walk driver

walk driver

board-truck

load-truck
drive-truck

drive-truck

unload-truck
Decreasing

What about plan length?
The heuristic took us to the left goal state (4 plan steps)
The other goal state has just 3 plan steps

What is best?
Priority = smallest h(S) = ignore plan so far
How about priority = f(S), where

f(S) = g(S) + h(S)

Intuition: distance so far + distance to goal estimates eventual distance for that option

Heuristic value
Length of plan to S

Open list: priority queue on f(S) = g(S) + h(S)

Awesome proof (i)
Q: What if h(S) is admissible and consistent?
admissible: never overestimates the distance to a goal state.
consistent (monotonic): h(S) <= h(S) + d(S, S)A: at any point, the smallest f(S) on the open list under estimates (<=) the shortest possible plan that can solve the problemProof: g(S) is perfect, so doesnt overestimate distance from I to (S); h(S) doesnt overestimate; so adding them together will never produce an overestimate.Interesting reading: Common Misconceptions Concerning Heuristic Search. SOCS 2010: https://aaai.org/ocs/index.php/SOCS/SOCS10/paper/view/2073/2500Awesome proof (ii)Q: What if we find a goal state, but put it on the open list, and wait until it is expanded?A: we have found the shortest possible planProof by contradiction: search expands a state with smallest f(S); if there was a shorter path to a goal state S, f(S) would be less than f(S), and it would have been expanded first.Consistency guarantees that there is no node that has not yet been put on the openlist that might have a shorter path than one that is there.What if the best node just hasnt been added to the open list yet?Every node has an ancestor that is (or has been) on the open list (e.g. Initial State) so if the cost of getting from any ancestor to the goal is guaranteed to be greater than the cost of getting from the ancestor to s + the cost of getting from s to the goal, no node below one that has ever been on the openlist can be better.This is the definition of consistent heuristics.Weighted A* Search (WA*)Q: What if we want a plan that is good quality but not necessarily optimal?A: we can use weighted A*f(S) = g(s) + W*h(s);W is a constant that gives an optimality bound.Now the solution we find will be within a factor W of optimal.Find a solution faster by biasing search towards nodes closer to the goal.Advantages: Dont have to explore as much of the search space to find a solution;Still have some guarantee of the solution being a reasonable one.W=2 means that the cost of the solution found can be at least 2* that of the optimal solutionWA* Search (W=2)Open list: priority queue on f(S) = g(S) + W*h(S) What is a good plan?Which plan is better?(fly-helicopter strand barbican)(walk strand temple)(tube temple barbican) CS: assignmentchef QQ: 1823890830 Email: [email protected]