1Optimal searchingBest-first search review• Advantages– Takes advantage of domain information to guide search– Greedy advance to the goal • Disadvantages– Considers cost to the goal from the current state– Some path can continue to look good according to the heuristic function321x111 xAt this point the path is morecostly than the alternate path2Branch & Bound• Use current cost (past cost) to a node• Pick best (lowest) cost.• If f is our evaluation function for node n, f(n)= g(n) [g= cost ‘gone so far’g ≥ 0• B&B: sort queue in order of lowest f, & make sure not to pursue identical paths with higher costs than known costsThe A* Algorithm:combining past with future• Now Consider the overall cost of the solution.f(n) = g(n) + h(n) where g(n) is the path cost to node g= distance gone so far h= future estimated costthink of f(n) as an estimate of the cost of the best solution going through the node n332x345 x321x111 x3UCS, BFS, Best-First, and A*• f = g + h ¨ A* Search• h = 0 ¨ Uniform cost search• g = 1, h = 0 ¨ Breadth-First search• g = 0 ¨ Best-First searchAdmissible Heuristics• This is not quite enough, we also require h be admissible: – a heuristic h is admissible if h(n) < h*(n) for all nodes n, – where h* is the actual cost of the optimal path from n to the goal • Examples: – travel distance straight line distance must be shorter than actual travel path – tiles out of place each move can reorder at most one tile distance of each out of place tile from the correct place each move moves a tile at most one place toward correct place4Heuristic Functions• Tic-tac-toexxxoxxxxxooooxxxooo8 Puzzle• Exhaustive Search : 3 20 = 3 * 10 9states• Remove repeated state : 9! = 362,880• Use of heuristics – h1 : # of tiles that are in the wrong position– h2 : sum of Manhattan distanceh1 = 3h2 = 1+2+2=547658321567483215Heuristics : 8 Puzzle4765832145768321476583215674832147658321Tic-tac-toe• Most-Win Heuristicsxxx3 win4 win2 win6Road Map Problemsgh(s)nh(n)n’h(n’)g(n’)Effect of Heuristic Accuracy on Performance• Well-designed heuristic have its branch close to 1•h2dominates h1iff h2(n) ≥ h1(n), ∀ n• It is always better to use a heuristic function with higher values, as long as it does not overestimate• Inventing heuristic functions– Cost of an exact solution to a relaxed problem is a good heuristic for the original problem– collection of admissible heuristicsh*(n) = max(h1(n), h2(n), …, hk(n))7Optimality of A*• Let us assume that f is non-decreasing along each path – if not, simply use parent’s value – if that’s the case, we can think of A* as expanding f contours toward the goal; better heuristics make this contour more “eccentric”• Let G be an optimal goal state with path cost f*• Let G2be a suboptimal goal state with path cost g(G2) > f*. – suppose A* picks G2before G (A* is not optimal) – suppose n is a leaf node on the path to G when G2is chosen – if h is admissible, then f* >= f(n) – since n was not chosen, it must be the case that f(n) >= G2– therefore f* >= f(G2), but since G2is a goal, f* >= g(G2) – But this is a contradiction --- G2is a better goal node than G – Thus, our supposition is false and A* is optimal. Completeness of A*• Suppose there is a goal state G with path cost f*– Intuitively: since A* expands nodes in order of increasing f, it must eventually expand node G• If A* stops and fails– Prove by contradiction that this is impossible.– There exists a path from the initial state to the node state – Let n be the last node expanded along the solution path– n has at least one child, that child should be in the open nodes– A* does not stop until there are open list is empty (unless it finds a goal state). Contradiction.• A* is on an infinite path – Recall that cost(s1,s2) > δ– Let n be the last node expanded along the solution path– After f(n)/δ the cumulative cost of the path becomes large enough that A* will expand n. Contradiction.8Properties of A*Properties of A*• Suppose C* is the cost of the optimal solution path– A* expands all nodes with f(n) < C*– A* might expand some of nodes with f(n) = C* on the “goal contour”– A* will expand no nodes with f(n) > C*, which are pruned!– Pruning: eliminating possibilities from consideration without examination•A* is optimally efficient for any given heuristic function–noother optimal algorithm is guaranteed to expand fewer nodes than A*– an algorithm might miss the optimal solution if it does notexpand all nodes with f(n) < C*• A* is complete9A* summary• Completeness – provided finite branching factor and finite cost per operator • Optimality– provided we use an admissible heuristic • Time complexity – worst case is still O(bd) in some special cases we can do better for a given heuristic • Space complexity – worst case is still O(bd)Finding heuristics: Relax Optimality (note: this is not required material)• Goals:– Minimizing search cost– Satisficing solution, i.e. bounded error in the solutionf(s) = (1-w) g(s) + w h(s)– g can be thought of as the breadth first component– w = 1 => Best-First search– w = .5 => A* search– w = 0 => Uniform search10Iterative Deepening A*• Goals– A storage efficient algorithm that we can use in practice– Still complete and optimal• Modification of A*– use f-cost limit as depth bound– increase threshold as minimum of f(.) of previous cycle• Each iteration expands all nodes inside the contour for current f-cost• same order of node expansionGames• Why games?– Games provide an environment of pure competition with objective goals between agents. – Game playing is considered an intelligent human activity.– The environment is deterministic and accessible.– The set of operators is small and defined.– Large state space– Fun!11Games• Consider Games– Two player games– Perfect Information: not involving chance or hidden information (not back-gammon, poker)– Zero-sum games: games where our gain is our opponents loss– Examples: tic-tac-toe, checkers, chess, go • Games of perfect information are really just search problems– initial state– operators to generate new states– goal test– utility function (win/lose/draw)Game Trees• Tic-tac-toexxxoxxxxxooooxxxooo1 ply 1 move12Game Trees
View Full Document
Unlocking...