Generating preview...
CS361(Artificial Intelligence) Lecture4 Problem Solving as Search (Blind/Uninformedvs.Heuristic/InformedStrategies) Dr. Hala Abdel-Galil & Dr. Amr S. Ghoneim (Computer Science Dept.) Helwan University Fall 2019 Lecture is based on its counterparts in the following courses: o Artificial Intelligence, University of Illinois at Urbana-Champaign
Resourcesforthislecture o This lecture covers the following chapters/sections: o Chapter 3 (Structures & Strategies for State Space Search; sections 3.2, and 3.3) and Chapter 4 (Heuristic Search) from George F. Luger, "Artificial Intelligence: Structures and strategies for complex problem solving, " Sixth edition (2009), Pearson Education Limited.
Outline o Search: Basic idea o Search tree o Tree Search Algorithm Outline o Heuristic Function o Handling repeated states o Robot Navigation o Backtracking Search o Examples of Evaluation function o Backtracking Algorithm o 8-Puzzle Data Structure o Reasoning Representation o Backtracking Algorithm o Propositional Calculus: Example (1) o Blind vs. Heuristic Strategies o And/ Or Graph o Blind Strategies o Propositional Calculus: Example (2) o Depth-First Strategy o Predicate Calculus Example o Depth-Limited Strategy o Comparison of Blind o More on Heuristic Search & Functions Search Strategies o Symmetry Reduction o Repeated States o Heuristic Reduction o Avoiding Repeated States o Hill Climbing Strategy o Uniform-Cost Strategy o Best-First Search o Best-First Search o 8-Puzzle Heuristics
Recap:Search Given: Initial state Actions Transition model Goal state Path cost How do we find the optimal solution?
Recap:Search:Basicidea o Let’s begin at the start state and expand it by making a list of all possible successor states. o Maintain a frontier or a list of unexpanded states. o At each step, pick a state from the frontier to expand. o Keep going until you reach a goal state. o Try to expand as few states as possible.
Recap:Searchtree Starting state “What if” tree of sequences of actions and outcomes ❖ When we are searching, we are not acting in the Action world, merely “thinking” about the possibilities Successor The root node corresponds to the starting state state The children of a node correspond to the successor states of that node’s state A path through the tree corresponds to a sequence of … actions ❖ A solution is a path ending in the goal state Nodes vs. states Frontier A state is a representation of the world, Goal while a node is a data structure that is state part of the search tree Node has to keep pointer to parent, path cost, possibly other info
Recap:TreeSearchAlgorithmOutline Initialize the frontier using the starting state. While the frontier is not empty: • Choose a frontier node according to search strategy and take it off the frontier. • If the node contains the goal state, return solution. • Else expand the node and add its children to the frontier.
Showing the first 19 pages. Download the document to see it all.
No comments yet. Be the first!
Comments (0)
No comments yet. Be the first!