CS361 (Artificial Intelligence) Lecture 2 Problem Solving as Search Dr. Hala Abdel-Galil & Dr. Amr S. Ghoneim (Computer Science Dept.) Helwan University Fall 2019 Lectures are based on their counterparts in the following courses: o Intelligent Systems, University of British Columbia (Dept. of Computer Science) o Introduction to Artificial Intelligence, University of Wisconsin-Madison o Artificial Intelligence, University of Illinois at Urbana-Champaign 1 o Artificial Intelligence, University of California, Berkeley Resources for this lecture o This lecture covers the following chapters: o Chapter 3 (Solving Problems by Searching; only sections 3.1, 3.2, & 3.3) from Stuart J. Russell and Peter Norvig, "Artificial Intelligence: A Modern Approach," Third Edition (2010), by Pearson Education Inc. … AND … o Part II (pages 41 to 45) and Chapter 3 (only sections 3.0, 3.1, and 3.2) from George F. Luger, "Artificial Intelligence: Structures and strategies for complex problem solving, " Sixth edition (2009), Pearson Education Limited. Outline o Solving problems by Searching o Types of agents o State Space Search o Example: Tic-Tac-Toe Game o Example: Mechanical Fault o State Space Search Strategies Diagnosing o State Space Search Strategies: o How human beings think? Selecting Search Strategy o Heuristic Search o Search: Basic idea o Search o Search tree o Search problem components o Tree Search Algorithm Outline o Example: Romania o Tree search example o State space o Handling repeated states o Example: Vacuum world o Backtracking Search o Vacuum world state space graph o Backtracking Algorithm Data o Example: The 8-puzzle Structure o Example: Robot motion o Backtracking Algorithm planning o Example: Tic- Tac-Toe o Example: Traveling Salesperson Solving Problems by SEARCHING Types of Agents Reflex agent Consider how the world IS Choose action based on current percept. Do not consider the future consequences of actions. Planning agent Consider how the world WO