DOC PREVIEW
USC CSCI 561 - session06

This preview shows page 1-2-3-18-19-36-37-38 out of 38 pages.

Save
View full document
View full document
Premium Document
Do you want full access? Go Premium and unlock all 38 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 38 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 38 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 38 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 38 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 38 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 38 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 38 pages.
Access to all documents
Download any document
Ad free experience
Premium Document
Do you want full access? Go Premium and unlock all 38 pages.
Access to all documents
Download any document
Ad free experience

Unformatted text preview:

CS 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 AlgorithmFunction 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 km374329253CS 561, Session 615Greedy search• Estimation function:h(n)= estimate of cost from nto goal (heuristic)• For example:hSLD(n)= straight-line distance from nto Bucharest• Greedy search expands first the node that appears to be closest to the goal, according to h(n).CS 561, Session 616CS 561, Session 617CS 561, Session 618CS 561, Session 619CS 561, Session 620Properties of Greedy Search• Complete?•Time?•Space?•Optimal?CS 561, Session 621Properties of Greedy Search• Complete? No – can get stuck in loopse.g., Iasi > Neamt > Iasi > Neamt > …Complete in finite space with repeated-state checking.• Time? O(b^m) but a


View Full Document

USC CSCI 561 - session06

Download session06
Our administrator received your request to download this document. We will send you the file to your email shortly.
Loading Unlocking...
Login

Join to view session06 and access 3M+ class-specific study document.

or
We will never post anything without your permission.
Don't have an account?
Sign Up

Join to view session06 2 2 and access 3M+ class-specific study document.

or

By creating an account you agree to our Privacy Policy and Terms Of Use

Already a member?