A.I. PLANNING
Planning as Heuristic Search
Copyright By PowCoder代写加微信 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, let’s 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 doesn’t overestimate distance from I to (S); h(S) doesn’t 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 hasn’t 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: Don’t 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]
Reviews
There are no reviews yet.