CS361 (Artificial Intelligence) Lecture 4 Problem Solving as Search (Blind/Uninformed vs. Heuristic/Informed Strategies) 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 Resources for this lecture 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: Basic idea 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:Search: Basic idea start Recap:Search: