Last time: Problem-SolvingSlide 2Slide 3Last time: Finding a solutionSlide 5Slide 6A Clean Robust AlgorithmSlide 8Last time: search strategiesEvaluation of search strategiesLast time: uninformed search strategiesThis time: informed searchBest-first searchRomania with step costs in kmGreedy searchPowerPoint PresentationSlide 17Slide 18Slide 19Properties of Greedy SearchSlide 21A* searchSlide 23Slide 24Slide 25Slide 26Slide 27Slide 28Optimality of A* (standard proof)Optimality of A* (more useful proof)Properties of A*Slide 32Proof of lemma: pathmaxAdmissible heuristicsSlide 35Relaxed ProblemNext timeCS 561, Session 61Last time: Problem-Solving•Problem solving: •Goal formulation •Problem formulation (states, operators) •Search for solution•Problem formulation:•Initial state•?•?•?•Problem types: •single state: accessible and deterministic environment•multiple state: ?•contingency: ?•exploration: ?CS 561, Session 62Last time: Problem-Solving•Problem solving: •Goal formulation •Problem formulation (states, operators) •Search for solution•Problem formulation:•Initial state•Operators•Goal test•Path cost•Problem types: •single state: accessible and deterministic environment•multiple state: ?•contingency: ?•exploration: ?CS 561, Session 63Last time: Problem-Solving•Problem solving: •Goal formulation •Problem formulation (states, operators) •Search for solution•Problem formulation:•Initial state•Operators•Goal test•Path cost•Problem types: •single state: accessible and deterministic environment•multiple state: inaccessible and deterministic environment•contingency: inaccessible and nondeterministic environment•exploration: unknown state-spaceCS 561, Session 64Last time: Finding a solutionFunction General-Search(problem, strategy) returns a solution, or failureinitialize the search tree using the initial state problemloop doif there are no candidates for expansion then return failurechoose a leaf node for expansion according to strategyif the node contains a goal state then return the corresponding solutionelse expand the node and add resulting nodes to the search treeendSolution: is ???Basic idea: offline, systematic exploration of simulated state-space by generating successors of explored states (expanding)CS 561, Session 65Last time: Finding a solutionFunction General-Search(problem, strategy) returns a solution, or failureinitialize the search tree using the initial state problemloop doif there are no candidates for expansion then return failurechoose a leaf node for expansion according to strategyif the node contains a goal state then return the corresponding solutionelse expand the node and add resulting nodes to the search treeendSolution: is a sequence of operators that bring you from current state to the goal state.Basic idea: offline, systematic exploration of simulated state-space by generating successors of explored states (expanding).Strategy: The search strategy is determined by ???CS 561, Session 66Last time: Finding a solutionFunction General-Search(problem, strategy) returns a solution, or failureinitialize the search tree using the initial state problemloop doif there are no candidates for expansion then return failurechoose a leaf node for expansion according to strategyif the node contains a goal state then return the corresponding solutionelse expand the node and add resulting nodes to the search treeendSolution: is a sequence of operators that bring you from current state to the goal stateBasic idea: offline, systematic exploration of simulated state-space by generating successors of explored states (expanding)Strategy: The search strategy is determined by the order in which the nodes are expanded.CS 561, Session 67A Clean Robust Algorithm Function UniformCost-Search(problem, Queuing-Fn) returns a solution, or failureopen make-queue(make-node(initial-state[problem]))closed [empty]loop doif open is empty then return failurecurrnode Remove-Front(open)if Goal-Test[problem] applied to State(currnode) then return currnodechildren Expand(currnode, Operators[problem])while children not empty[… see next slide …]endclosed Insert(closed, currnode)open Sort-By-PathCost(open)endCS 561, Session 68A Clean Robust Algorithm [… see previous slide …]children Expand(currnode, Operators[problem])while children not emptychild Remove-Front(children)if no node in open or closed has child’s stateopen Queuing-Fn(open, child)else if there exists node in open that has child’s stateif PathCost(child) < PathCost(node)open Delete-Node(open, node)open Queuing-Fn(open, child)else if there exists node in closed that has child’s stateif PathCost(child) < PathCost(node)closed Delete-Node(closed, node)open Queuing-Fn(open, child)end[… see previous slide …]CS 561, Session 69Last time: search strategiesUninformed: Use only information available in the problem formulation•Breadth-first•Uniform-cost•Depth-first•Depth-limited•Iterative deepeningInformed: Use heuristics to guide the search•Best first•A*CS 561, Session 610Evaluation of search strategies•Search algorithms are commonly evaluated according to the following four criteria:•Completeness: does it always find a solution if one exists?•Time complexity: how long does it take as a function of number of nodes?•Space complexity: how much memory does it require?•Optimality: does it guarantee the least-cost solution?•Time and space complexity are measured in terms of:•b – max branching factor of the search tree•d – depth of the least-cost solution•m – max depth of the search tree (may be infinity)CS 561, Session 611Last time: uninformed search strategiesUninformed search:Use only information available in the problem formulation•Breadth-first•Uniform-cost•Depth-first•Depth-limited•Iterative deepeningCS 561, Session 612This time: informed searchInformed search:Use heuristics to guide the search•Best first•A*•Heuristics•Hill-climbing•Simulated annealingCS 561, Session 613Best-first search•Idea:use an evaluation function for each node; estimate of “desirability”expand most desirable unexpanded node.•Implementation:QueueingFn = insert successors in decreasing order of desirability•Special cases:greedy searchA* searchCS 561, Session 614Romania with step costs in kmCS 561, Session 615Greedy search•Estimation function:h(n) =
View Full Document