AI310 & CS361 Intro to Artificial Intelligence Lectures (Fall 2024) PDF

AI310 & CS361 Artificial Intelligence Mainstream – Medical Informatics – Computer Science Dept. Software Engineering Programmes Helwan University Lecture 0 Course Introduction & Plan  Course Details  Tentative Topics & Learning Objectives  Course L...

AI310 & CS361 Artificial Intelligence Mainstream – Medical Informatics – Computer Science Dept. Software Engineering Programmes Helwan University Lecture 0 Course Introduction & Plan  Course Details  Tentative Topics & Learning Objectives  Course Logistics & Grading Policy  Classroom Code of Conduct  Be an Effective Learner..? Faculty of  Academic Agenda Computers & Artificial Intelligence FALL 2023 Course Details Course Code(s) AI301 and CS361 Course Name Artificial Intelligence Coordinating Unit Department of Artificial Intelligence, and Department of Computer Science, Faculty of Computers & Artificial.... Intelligence, Helwan University Term Semester 1 [Fall] Level Undergraduate - Level 3 2 Tentative Topics & Learning Objectives.. of this course 3 Learning Objectives of this Course What you'll learn?  This course gives a basic introduction to Artificial Intelligence (AI) and Machine Learning (ML).  Students receive an introduction to philosophical fundamental problems and ethical questions related to ML/AI, as well as the field's history.  Then, We will study the core topics of knowledge representation, reasoning, and learning.  Later topics will include and introduction to machine learning, & probabilistic reasoning, in addition to applications such as robotics, computer vision, and natural language processing. 4 Learning Objectives of this Course.. Continued.. What you'll learn?  The course covers basic supervised classification (e.g., Artificial Neural Networks), as well as unsupervised learning (Clustering), optimization (Evolutionary Algorithms and other search methods), and tentatively regression and reinforcement learning.  Through an algorithmic approach, the students are given a practical understanding of the methods being taught, in particular through making their own implementations of several of the methods. 5 Topics Covered [ Tentative] The main contents of the course are:  Main approaches to Artificial Intelligence (AI) & Learning  Task environment  Performance measures  Intelligent Agents  Knowledge Representation  Problem solving by searching:  Uninformed Search  Informed Search  Adversarial Search  Beyond classical search: Evolutionary Algorithms  Machine learning (ML):  Supervised Learning versus Unsupervised Learning  Decision Trees  Artificial Neural Networks: Perceptrons, & Multi-Layer Perceptrons  Support Vector Machines  Clustering Algorithms  Ensemble Learning 6  Selected AI / ML Applications Recommended background o The only formal prerequisites for this course are an Introduction to Computer Science, Introduction to Programming Languages 1 & 2 (including Object-Oriented Programming), and Data Structures & Algorithms.. o We recommend that students have some experience with Python / Matlab, ideally some background in probability and statistics, and linear algebra. o If you don’t have background in these areas, you may still sign up, but be aware that you will probably need to learn some of these items as the class goes on (we will be providing pointers to references). 7 Course Logistics Announcements & Course Materials Additional Resources (per section) Assessment Summary (Grading Policy) Exercises.. What have we learned? Be an Effective Learner..? Classroom Code of Conduct Academic Integrity & Plagiarism 8 Announcements & Course Materials Video Lessons: All recorded lectures are on the following: Amr S. Ghoneim YouTube Channel : https://www.youtube.com/AmrSGhoneim/ CS361 Introduction to Artificial Intelligence YouTube Playlist : https://www.youtube.com/playlist?list=PLsnvpvHuTUbAZr0n65TgytB K6bHdT33A7 9 Announcements & Course Materials Downloads, Homework, & Announcements: All course material (lecture notes “slides", assignments, any supplemental notes or documentation), will be made available “posted” online on weekly basis, on: CS361 Introduction to Artificial Intelligence Google Drive Folder: https://drive.google.com/drive/folders/1idzWQqb_Fb-BPLBPABPRMYLE- Pr7AS8j?usp=drive_link All announcements will be made available “posted” online, on: Amr S. Ghoneim Facebook Page : https://www.facebook.com/amr.s.ghoneim/ 10 Announcements & Course Materials Required Resources: The prescribed textbooks for the course are: - Stuart J. Russell and Peter Norvig, "Artificial Intelligence: A Modern Approach," 3rd Edition (2010), by Pearson Education Inc. - George F. Luger, "Artificial Intelligence: Structures and strategies for complex problem solving," 5th Edition (2005), Pearson Education Limited. Additional Textbooks: - Wolfgang Ertel, "Introduction to Artificial Intelligence," 2nd Edition (2017) - Miroslav Kubat, "An Introduction to Machine Learning," 2nd Edition (2017) - Y. Abu-Mostafa, M. Magdon-Ismail, & H-T. Lin, "Learning from Data - A Short Course," (2012) - Max Bramer, "Principles of Data Mining," 3rd Edition (2016) 11  Additional Resources  At the end of each section, there will be a short list of additional resources.  The list will include articles, YouTube videos, online courses, books,.. etc. (in both Arabic and English).  These resources will provide more details on some of the topics discussed during the lectures. Assessment Summary (Grading Policy) The Assessment for this subject consists of five components with the following weightings (grading breakdown): 1) Final Written Exam: 50% 2) Group Project: 35% 3) Midterm Written Exam: 15% 4) Attendance and Participation during the Labs. (Sections) are obligatory. 13 Class Project o A major component of the class: Goal is to take a real-world domain that you are interested in and apply the taught methodologies to gain insight into the domain. o Work to be done in groups of (5 to 6) students, more details will be announced later. o Final report will include the presentation & analysis of your problem & data, the algorithms/approaches applied, and the outcomes, including code and visual results. o The students will be required to perform a ~15 mins demo of their project. o Class projects must be focused on some real data problem. 14  Exercises What have we learned? At the end of each section, there will be a set review activities (exercises), that would help you see the progress you've made in this lesson. The exercises would help you:  Highlight what you have learned today & emphasize key information.  Correct misunderstandings.  Summarize, review, & demonstrate your understanding of major points.  Transfer ideas to new situations. Be an Effective Learner.. o Have the desire to seek knowledge and acquire new skills (be inquisitive / curious) o Ask questions. o Be an avid (keen & passionate) reader. o Be an attentive / focused listener. o Find your preferred learning style.. &.. Learn in multiple ways. o Do NOT memorize. o Embrace Discomfort. o Practice, practice, practice (you must gain practical experience). o Teach what you’ve learned to another person. o Use testing to boost / improve learning. o Avoid multitasking. o Make use of Memory Improvement Basics. o Draw up a schedule. o Examine your lifestyle. o Create a study station. 16 Classroom Code of Conduct Be punctual & prepared to study: - Attend all classes including online and face-to-face classes. - Arrive to all classes on time. - Keep all handouts & work in a folder and make sure they are well organised. - Prepare yourself for your classes. Participate in the classroom: - Participate in class. - Respect yourself, your teachers, and your classmates. - Turn mobile phones off or put them on silent mode before entering the classroom. - Adopt a professional attitude - no eating, side-talk, etc. Study independently: - Study outside the classroom as part of your student effort (about 6 to 8 hours per week). - Complete all homework assignments and hand them in on time. - Use the University/Faculty facilities (e.g., the library) and online resources. Respect University regulations: - Follow (University, Faculty, Department, and Programme) regulations. - Know the due date of all assessments, submit them by that date & in the required format. - Understand what you need to successfully progress. - Maintain academic honesty (academic integrity & plagiarism). 17 Academic Integrity & Plagiarism o You can discuss ideas and methodology for the homework or the project with other students in the course, but you must write your solutions completely independently. o We will be code-checking to assess similar submissions or submissions that use code from other sources. o You may use snippets of code from other sources, as long as you cite these properly (put a comment above and below whatever portion of code is copied); but be reasonable. 18 Academic Agenda 19 Week: Starts: Tentative Academic Agenda (Topics) Wk. 1 Sept. 30 Course Introduction & Plan + an introduction to Artificial Intelligence [AI] Wk. 2 Oct. 07 an introduction to Artificial Intelligence [AI] Continued Wk. 3 Oct. 14 Intelligent Agents, & AI Related Disciplines Wk. 4 Oct. 21 Solving Problems by Searching, & State Space Search Strategies & Structures Wk. 5 Oct. 28 Knowledge Representation via Propositional & Predicate Calculi Wk. 6 Nov. 04 Problem Solving as Search (Blind/Uninformed vs. Heuristic/Informed Strategies) Wk. 7 Nov. 11 Midterm Written Exams (15%) – Schedule TBA by the Faculty Wk. 8 Nov. 18 Problem Solving as Search (More on Heuristic Search + Adversarial Search) Wk. 9 Nov. 25 Beyond Classical Search (Evolutionary Computation: Genetic Algorithms) An Intro. to Machine Learning + Supervised Machine Learning: Decision Trees via Wk. 10 Dec. 02 the ID3 Algo. + BI app. via Weka The Learning Problem, the Perceptron, & the Perceptron Learning Algo. [PLA], Wk. 11 Dec. 09 Multilayer Perceptron [MLP], & an intro. to Artificial Neural Networks [ANNs] Wk. 12 Dec. 16 Ensemble Learning + Selected AI Topics / Applications Final Practical Exams – Group Project (35%) – Schedule TBA by the Faculty Final Written Exams (50%) – Schedule TBA by the Faculty 20  Up Next.. Welcome to Lecture 1 AI310 & CS361 an Introduction to Artificial Intelligence Thank you! AI310 & CS361 Artificial Intelligence Mainstream – Medical Informatics – Computer Science Dept. Software Engineering Programmes Helwan University Lecture 1 An Introduction to Artificial Intelligence 1.1 What is Intelligence  Some Foundations of AI – What is Intelligence? – What is Artificial Intelligence? 1.2 Systems that Act Like Humans  Systems that Act Like Humans – Turing Test? – The Chinese Room Argument – Strong Vs. Weak AI – Where are we? 1.3 AI as the Study & Design of Intelligent Agents Faculty of  Systems that Think like Humans – Systems that – Think Computers & Rationally – Main Research Problems / Challenges – Artificial Intelligence Systems that Act Rationally – AI as the Study & Design of Intelligent Agents – Intelligent Agents in the World FALL 2023 Lecture 1: An introduction to Artificial Intelligence [AI] 1.1 What is Intelligence 1.3 AI as the Study & Design of Intelligent  Some Foundations of Artificial Agents Intelligence  Systems that Think like Humans  What is Intelligence?  Systems that Think Rationally  What is Artificial Intelligence?  Challenges to Systems that Think 1.2 Systems that Act Like Humans Rationally  Systems that Act Like Humans  Systems that Act Rationally  Turing Test (the Imitation Game)?  AI as the Study & Design of Intelligent  Total Turing Test? Agents  The Chinese Room Argument  Intelligent Agents in the World  Strong Vs. Weak AI  Sample of solutions offered by AI  Where are we?  History of the various AI areas  3 AnIntroduction to Artificial Intelligence  This lecture covers the following chapters: Chapter 1 (Introduction) from Stuart J. Russell and Peter Norvig, "Artificial Intelligence: A Modern Approach," Third Edition (2010), by Pearson Resources for Education Inc. this lecture.. AND.. Chapter 1 (AI: History and Applications) from George F. Luger, "Artificial Intelligence: Structures and strategies for complex problem solving, " Fifth Edition (2005), Pearson Education Limited. 4  SOME FOUNDATIONS OF ARTIFICIAL INTELLIGENCE Philosophy Economics Can formal rules be used to draw valid How should we make decisions so as conclusions? to maximize payoff? How does the mind arise from a How should we do this when others physical brain? may not go along? Where does knowledge come from? How should we do this when the How does knowledge lead to action? payoff may be far in the future? Mathematics Computer Engineering What are the formal rules to draw valid How can we build an efficient conclusions? computer? What can be computed? Control theory and cybernetics How do we reason with uncertain How can artefacts operate under their information? own control? Neuroscience Linguistics How do brains process information? How does language relate to thought? Psychology How do humans and animals think and act? 5  What is Intelligence? Intelligence: Judgment, otherwise called “good sense,” “practical sense,” “initiative,” the faculty of adapting one's self to circumstances.. auto-critique ~ Alfred Binet (July 8, 1857 – October 18, 1911) was a French psychologist who invented the first practical intelligence test (An intelligence quotient (IQ); a total score derived from one of several standardized tests designed to assess human intelligence) “.. the resultant of the process of acquiring, storing in memory, retrieving, combining, comparing, and using in new contexts information and conceptual skills.” ~Lloyd G. Humphreys (December 12, 1913 – September 7, 2003) was an American psychologist “.. the capacity to learn and solve problems..” (Webster’s dictionary) in particular, the ability to solve novel problems the ability to act rationally the ability to act like humans 6  What is Artificial Intelligence? John McCarthy*, Stanford University What is artificial intelligence? It is the science and engineering of making intelligent machines, especially intelligent computer programs. It is related to the similar task of using computers to understand human intelligence, but AI does not have to confine itself to methods that are biologically observable; “.. The goal of AI is to develop machines that behave as though they were intelligent...” Yes, but what is intelligence? Intelligence is the computational part of the ability to achieve goals in the world. Varying kinds and degrees of intelligence occur in people, many animals and some machines. Isn't there a solid definition of intelligence that doesn't depend on relating it to human intelligence? Not yet. The problem is that we cannot yet characterize in general what kinds of computational procedures we want to call intelligent. We understand some of the mechanisms of intelligence and not others. More in: http://www-formal.stanford.edu/jmc/whatisai/node1.html * John McCarthy (September 4, 1927 – October 24, 2011) was an American computer scientist & cognitive scientist. McCarthy was one of the founders of the discipline of artificial intelligence. He coined the term 7 "artificial intelligence" (AI) , and invented the programming language LISP.  What is Artificial Intelligence? More Definitions by Encyclopedia Britannica (1991) ".. AI is the ability of digital computers or computer-controlled robots to solve problems that are normally associated with the higher intellectual processing capabilities of humans.“ by Elaine Rich.. Artificial Intelligence. McGraw-Hill, 1983 ".. Artificial Intelligence is the study of how to make computers do things at which, at the moment, people are better." 8  What is Artificial Intelligence? Four Main Approaches that have been followed, each by different people with different methods. Thinking Acting Humanly Humanly Thinking Acting Rationally Rationally 9  What is Artificial Intelligence? Systems that act like humans Systems that think rationally “The study of how to make computers do “The study of mental faculties through the things at which, at the moment, people are use of computational models” (Charniack better” (Rich and Knight, 1991) and McDermott, 1985). “The art of creating machines that perform “The study of the computations that make it functions that require intelligence when possible to perceive, reason, and act.” performed by people.” (Kurzweil, 1990) (Winston, 1992) Systems that think like humans Systems that act rationally “The automation of activities that we associate with human thinking, such as “AI.. is concerned with intelligent behavior decision making, problem solving, learning” in artifacts (Nilsson, 1998) (Bellman, 1978) “Computational Intelligence is the study of “The exciting new effort to make computers the design of intelligent agents.” (Poole et think … machines with minds, in the full al., 1998) and literal sense.” (Haugeland, 1985) 10  Exercises What have we learned?  Read the following: [ Chapter 1 (Introduction) from Stuart J. Russell and Peter Norvig, "Artificial Intelligence: A Modern Approach." ] then describe briefly in a point or two how the following disciplines contribute/d to AI:  Psychology  Computer Engineering  Neuroscience  Economics  What are the four Approaches to AI according to Russell & Norvig?  Up Next.. Additional Section 1.2 Resources  How Far is Too Far? | The Age of A.I.: https://www.youtube.com/watch?v=UwsrzCVZAb8&t=1249s  Artificial Intelligence & the Future – Rise of AI (Elon Musk, Bill Gates, Sundar Pichai): https://www.youtube.com/watch?v=wTbrk0suwbg  What is Artificial Intelligence? In 5 minutes: https://www.youtube.com/watch?v=2ePf9rue1Ao  What is Artificial Intelligence Exactly? https://www.youtube.com/watch?v=kWmX3pd1f10 Lecture 1: An introduction to Artificial Intelligence [AI] 1.1 What is Intelligence 1.3 AI as the Study & Design of Intelligent  Some Foundations of Artificial Agents Intelligence  Systems that Think like Humans  What is Intelligence?  Systems that Think Rationally  What is Artificial Intelligence?  Challenges to Systems that Think 1.2 Systems that Act Like Humans Rationally  Systems that Act Like Humans  Systems that Act Rationally  Turing Test (the Imitation Game)?  AI as the Study & Design of Intelligent  Total Turing Test? Agents  The Chinese Room Argument  Intelligent Agents in the World  Strong Vs. Weak AI  Sample of solutions offered by AI  Where are we?  History of the various AI areas  What is Artificial Intelligence? Systems that act like humans Systems that think rationally “The study of how to make computers do “The study of mental faculties through the things at which, at the moment, people are use of computational models” (Charniack better” (Rich and Knight, 1991) and McDermott, 1985). “The art of creating machines that perform “The study of the computations that make it functions that require intelligence when possible to perceive, reason, and act.” performed by people.” (Kurzweil, 1990) (Winston, 1992) Systems that think like humans Systems that act rationally “The automation of activities that we associate with human thinking, such as “AI.. is concerned with intelligent behavior decision making, problem solving, learning” in artifacts (Nilsson, 1998) (Bellman, 1978) “Computational Intelligence is the study of “The exciting new effort to make computers the design of intelligent agents.” (Poole et think … machines with minds, in the full al., 1998) and literal sense.” (Haugeland, 1985) 14  Systems that Act Like Humans … ?! 15  Systems that Act Like Humans Turing Test; theImitation Game … In Turing’s (1950) paper “Computing machinery and intelligence”: ♦ Can machines think ? ≡ (identical to) Can machines behave intelligently? ♦ Operational test for intelligent behavior: the Imitation Game HUMAN HUMAN ? INTERROGATOR AI SYSTEM 16  Systems that Act Like Humans Turing Test; theImitation Game … Turing test (1950): Can a human interrogator tell whether (written) responses to her (written) questions come from a human or a machine? Natural Language Processing Knowledge Representation Automated Reasoning Machine Learning Total Turing Test (extended to include physical aspects of human behavior): Computer Vision 17 Robotics  Total Turing Test? But why do we want an intelligent system to act like a human? - Because for many tasks, humans are still the Gold Standard. 18  BabyX is a project (by Auckland's Bioengineering Institute BabyX! Laboratory for Animate Technologies) to make a virtual animated baby that learns and reacts like a human baby. It uses the computer's cameras for "seeing" and microphones Total Turing Test? to "listen" as the inputs. The computer uses AI algorithms for BabyX's "learning" and interpretation of the inputs (voice and image) to understand the situation. The result is a virtual toddler that can learn to read, recognize objects and "understand." The output is the baby's face that can "speak" and express its mood by facial expressions (such as smiling). 19  BabyX! Reinforcement learning..? It is a machine learning training method based on rewarding desired behaviors and/or punishing undesired ones. Total Turing Test? Affective Computing..? it describes computing that is in some way connected to emotion (a.k.a. emotional artificial intelligence). It is the study and development of systems and devices that can recognize, interpret, process, and simulate human affects (feelings, emotions, or mood). 20  Systems that Act Like Humans The Chinese Room Argument John Rogers Searle (born July 31, 1932) is an American philosopher “Searle's thought experiment begins with this hypothetical premise: suppose that artificial intelligence research has succeeded in constructing a computer that behaves as if it understands Chinese. It takes Chinese characters as input and, by following the instructions of a computer program, produces other Chinese characters, which it presents as output. Suppose, says Searle, that this computer performs its task so convincingly that it comfortably passes the Turing test: it convinces a human Chinese speaker that the program is itself a live Chinese speaker. To all of the questions that the person asks, it makes appropriate responses, such that any Chinese speaker would be convinced that they are talking to another Chinese-speaking human being.” The question Searle wants to answer is this: does the machine literally "understand" Chinese? Or is it merely simulating the ability to understand Chinese? Searle calls the first position "strong AI" and the latter "weak AI". 21  Systems that Act Like Humans The Chinese Room Argument (Continued) Searle then supposes that he is in a closed room and has a book with an English version of the computer program, along with sufficient paper, pencils, erasers, and filing cabinets. Searle could receive Chinese characters through a slot in the door, process them according to the program's instructions, and produce Chinese characters as output. If the computer had passed the Turing test this way, it follows, says Searle, that he would do so as well, simply by running the program manually. Searle asserts that there is no essential difference between the roles of the computer and himself in the experiment. Each simply follows a program, step-by- step, producing a behaviour which is then interpreted as demonstrating intelligent conversation. However, Searle would not be able to understand the conversation. Searle argues that without "understanding" (or "intentionality"), we cannot describe what the machine is doing as "thinking" and since it does not think, it does not have a "mind" in anything like the normal sense of the word. Therefore, he concludes that "strong AI" is false. 22  Systems that Act Like Humans The Chinese Room Argument (Continued) If person inside does a great job of answering questions, can we say s/he understands? Even if (s)he is only blindly following rules? (Obviously, the ‘person inside’ is acting like an AI program) 23  Systems that Act Like Humans The Chinese Room Argument (Continued) Strong vs. Weak AI Hypotheses? - WEAK AI Hypothesis; We can accurately simulate animal / human intelligence in a computer. - STRONG AI Hypothesis; We can create algorithms that are intelligent ( Consciousness ?.. Self-Awareness ?.. Free-will ? ) Do you remember Sonny, the robot from the 2004 science-fiction / action film "I, Robot"? 24  Systems that Act Like Humans Strong Vs. Weak AI.. Where are we? Artificial Super Intelligence (ASI) Artificial General Intelligence (AGI) Artificial Narrow Intelligence (ANI) Sources: https://www.scoro.com/blog/artificial-intelligence-everything-you-want-to-know/ 25 https://www.ubs.com/microsites/artificial-intelligence/en/new-dawn.html  Exercises What have we learned?  Describe briefly the Turing Test "imitation game". (Illustrate through drawing)  Describe briefly the Total Turing Test.  Describe briefly the “Weak AI Hypothesis” versus the “Strong AI Hypothesis”.  Criticize Turing's criteria for computer software being "intelligent"; What is Searle’s thought experiment (the Chinese Room Argument)?  Describe briefly Reinforcement Learning.  Describe briefly Affective Computing.  Up Next.. Additional Section 1.3 Resources  The Turing test: Can a computer pass for a human? - Alex Gendler https://www.youtube.com/watch?v=3wLqsRLvV-c  The Chinese Room Argument: https://www.youtube.com/watch?v=18SXA-G2peY  The Chinese Room - 60-Second Adventures in Thought: https://www.youtube.com/watch?v=TryOC83PH1g  We Talked To Sophia – The AI Robot That Once Said It Would ‘Destroy Humans’: https://www.youtube.com/watch?v=78-1MlkxyqI  This Freaky Baby Could Be the Future of AI. Watch It in Action: https://www.youtube.com/watch?v=yzFW4-dvFDA  Two robots debate the future of humanity: https://www.youtube.com/watch?v=1y3XdwTa1cA Lecture 1: An introduction to Artificial Intelligence [AI] 1.1 What is Intelligence 1.3 AI as the Study & Design of Intelligent  Some Foundations of Artificial Agents Intelligence  Systems that Think like Humans  What is Intelligence?  Systems that Think Rationally  What is Artificial Intelligence?  Challenges to Systems that Think 1.2 Systems that Act Like Humans Rationally  Systems that Act Like Humans  Systems that Act Rationally  Turing Test (the Imitation Game)?  AI as the Study & Design of Intelligent  Total Turing Test? Agents  The Chinese Room Argument  Intelligent Agents in the World  Strong Vs. Weak AI  Sample of solutions offered by AI  Where are we?  History of the various AI areas  What is Artificial Intelligence? Systems that act like humans Systems that think rationally “The study of how to make computers do “The study of mental faculties through the things at which, at the moment, people are use of computational models” (Charniack better” (Rich and Knight, 1991) and McDermott, 1985). “The art of creating machines that perform “The study of the computations that make it functions that require intelligence when possible to perceive, reason, and act.” performed by people.” (Kurzweil, 1990) (Winston, 1992) Systems that think like humans Systems that act rationally “The automation of activities that we associate with human thinking, such as “AI.. is concerned with intelligent behavior decision making, problem solving, learning” in artifacts (Nilsson, 1998) (Bellman, 1978) “Computational Intelligence is the study of “The exciting new effort to make computers the design of intelligent agents.” (Poole et think … machines with minds, in the full al., 1998) and literal sense.” (Haugeland, 1985) 29  Systems that Think Like Humans Need to study the brain as an information processing machine, … in other words … Use Computational Models to Understand the Actual Workings of Human Mind Devise/Choose a sufficiently precise theory of the mind. Express it as a computer program. Check match between program and human behavior (actions and timing) on similar tasks. Tight connections with Cognitive Science & Neuroscience. Also known as descriptive approaches to AI. 30  What is Artificial Intelligence? Systems that act like humans Systems that think rationally “The study of how to make computers do “The study of mental faculties through the things at which, at the moment, people are use of computational models” (Charniack better” (Rich and Knight, 1991) and McDermott, 1985). “The art of creating machines that perform “The study of the computations that make it functions that require intelligence when possible to perceive, reason, and act.” performed by people.” (Kurzweil, 1990) (Winston, 1992) Systems that think like humans Systems that act rationally “The automation of activities that we associate with human thinking, such as “AI.. is concerned with intelligent behavior decision making, problem solving, learning” in artifacts (Nilsson, 1998) (Bellman, 1978) “Computational Intelligence is the study of “The exciting new effort to make computers the design of intelligent agents.” (Poole et think … machines with minds, in the full al., 1998) and literal sense.” (Haugeland, 1985) 31  Systems that Think Rationally Logic: formalize idealized or right thinking, i.e. irrefutable reasoning processes. That is; patterns of argument that always yield correct conclusions when supplied with correct premises: “.. Socrates is a man; all men are mortal; therefore Socrates is mortal.” Logistic tradition in AI aims to build computational frameworks based on logic, that is, describe a problem in formal logical notation and apply general deduction procedures to solve it. Then use these frameworks to build intelligent systems. Some examples are (Propositional Logic) and (Logic Programming). More advanced logic-based representations: Semantic Networks. 32  Systems that Think Rationally Main Research Problems / Challenges: Describing real-world problems and knowledge in logical notation. Proving Soundness and Completeness of various formalisms. How to represent often informal and uncertain domain knowledge and formalize it in logic notation (i.e., dealing with Uncertainty). Computational Complexity of finding a solution. A lot of “rational” behavior has nothing to do with logic. 33  What is Artificial Intelligence? Systems that act like humans Systems that think rationally “The study of how to make computers do “The study of mental faculties through the things at which, at the moment, people are use of computational models” (Charniack better” (Rich and Knight, 1991) and McDermott, 1985). “The art of creating machines that perform “The study of the computations that make it functions that require intelligence when possible to perceive, reason, and act.” performed by people.” (Kurzweil, 1990) (Winston, 1992) Systems that think like humans Systems that act rationally “The automation of activities that we associate with human thinking, such as “AI.. is concerned with intelligent behavior decision making, problem solving, learning” in artifacts (Nilsson, 1998) (Bellman, 1978) “Computational Intelligence is the study of “The exciting new effort to make computers the design of intelligent agents.” (Poole et think … machines with minds, in the full al., 1998) and literal sense.” (Haugeland, 1985) 34  Systems that Act Rationally Why..? The “think rationally” approach focuses on correct inference. But more is needed for rational behavior, e.g. How to behave when there is no provably correct thing to do (i.e. reasoning under uncertainty). Fully reactive behavior (instinct vs. reason). 35  AI as the Study & Design of Intelligent Agents (Poole and Mackworth, 1999) An intelligent agent is such that: Its actions are appropriate for its goals and circumstances. It is flexible to changing environments and goals. It learns from experience. It makes appropriate choices given perceptual limitations and limited resources (bounded rationality or bounded optimality). This definition drops the constraint of cognitive plausibility; Same as building flying machines by understanding general principles of flying (aerodynamic) vs. by reproducing how birds fly. Thus, a rational agent acts to optimally achieve its goals (does the right thing). The right thing: that which is expected to maximize goal achievement, given the available information. 36  Intelligent Agents In AI, artificial agents that have a physical presence in the world are usually known as Robots. Robotics is the field primarily concerned with the implementation of the physical aspects of a robot (i.e. perception of the physical environment, actions on the environment). Another class of artificial agents include interface agents, for either stand alone or Web-based applications (e.g. intelligent desktop assistants, recommender systems, intelligent tutoring systems). Interface agents don’t have to worry about interaction with the physical environment but share all other fundamental components of intelligent behavior with robots. We will focus on these agents in this course. 37  Pac-Man.. as an..Intelligent Agent Agent Sensors Percepts ? Environment Actuators Actions 38 Samples of Intelligent Systems in our daily life: o The Web: Identifying your age, gender, location, from your Web surfing,.. etc. o Post Office: Automatic address recognition, automatic sorting of mail,.. o Banks: Automatic check readers, signature verification systems, loan application classification,.. o Customer Service: Automatic voice, speech, & language recognition,.. etc. o Digital Cameras: Automated face detection & recognition,.. etc. o Computer Games: Intelligent characters,.. etc. o Medical Centers: Automatic Detection, Prediction, & Grading of 39 Diseases,.. etc. "A small sample of solutions offered by AI." - Wolfgang Ertel, "Introduction to Artificial Intelligence," 2nd Edition (2017) 40 "History of the various AI areas.. The width of the bars indicates prevalence of the method's use.“ 41 - Wolfgang Ertel, "Introduction to Artificial Intelligence," 2nd Edition (2017)  Exercises What have we learned?  Compare briefly between Systems that “Act / Behave Rationally”, and Systems that “Act / Behave Humanly”.  Describe briefly Intelligent Agents.  Give the scientific term for each of the following statements: a) The branch of computer science that is concerned with the automation of intelligent behavior. b) A problem-solving technique that systematically explores a space of problem states. c) Systems that are constructed by obtaining knowledge from a human expert and coding it into a form that a computer may apply to similar problems. d) Models that parallel the structure of neurons in the human brain and used to build intelligent programs. e) Algorithms that evolve new problem solutions from components of previous solutions using specific operators such as crossover and mutation.  Read the following: [ Chapter 1 (AI: History and Applications) from George F. Luger, "Artificial Intelligence: Structures and strategies for complex problem solving." ] then Describe briefly the two most fundamental concerns of AI researchers.  Up Next.. Additional Lecture 2 Resources  Artificial Intelligence In 5 Minutes | What Is Artificial Intelligence? | AI Explained: https://www.youtube.com/watch?v=ad79nYk2keg  Types of Artificial Intelligence | Artificial Intelligence Explained | What is AI? https://www.youtube.com/watch?v=y5swZ2Q_lBw  Artificial Intelligence: Mankind’s Last Invention https://www.youtube.com/watch?v=Pls_q2aQzHg Thank you! AI310 & CS361 Artificial Intelligence Mainstream – Medical Informatics – Computer Science Dept. Software Engineering Programmes Helwan University Lecture 2 Intelligent Agents, & AI Related Disciplines 2.1 Intelligent “Rational” Agents?  Recap: AI as the Study & Design of Intelligent Agents – Intelligent Agents in the World – Specifying the Task Environment [ PEAS ] – Goad-based vs. Cost-based Agents 2.2 Specifying the Task Environment  Environment Types 2.3 AI: Related Disciplines Faculty of Computers &  Learning Agents – AI vs. Machine Learning vs. Deep Artificial Intelligence Learning – Machine Learning? – Datamining? – AI vs. Data Science – Why Data Science? – Why Big Data? FALL 2023 Lecture 2: Intelligent Agents, & AI Related Disciplines 2.1 Intelligent “Rational” Agents? 2.3 AI: Related Disciplines  Recap: AI as the Study & Design of  Learning Agents Intelligent Agents  AI vs. Machine Learning vs. Deep  Intelligent Agents in the World Learning  An Example: Vacuum_Agent  Machine Learning?  Specifying the Task Environment [  Datamining? PEAS ]  AI vs. Data Science  Goad-based vs. Cost-based Agents  Why Data Science?  Why Big Data? 2.2 Specifying the Task Environment  Environment Types Acting Rationally Intelligent Agents 3 MainResources for thisSection This lecture covers mainly the following chapter(s): Chapter 2 (Intelligent Agents) from Stuart J. Russell and Peter Norvig, "Artificial Intelligence: A Modern Approach," Third Edition (2010), by Pearson Education Inc. 4  Recap.. What is Artificial Intelligence? Four Main Approaches that have been followed, each by different people with different methods. the Cognitive the Turing Test Modelling approach approach Thinking Acting Humanly Humanly Thinking Acting Rationally Rationally the Rational Agent the Laws-of-Thought approach approach 5  Recap.. So.. It all started as.. Systems that Act Like Humans.. 6  Recap.. What is Artificial Intelligence? Systems that act like humans Systems that think rationally “The study of how to make computers do “The study of mental faculties through the things at which, at the moment, people are use of computational models” (Charniack better” (Rich and Knight, 1991) and McDermott, 1985). “The art of creating machines that perform “The study of the computations that make it functions that require intelligence when possible to perceive, reason, and act.” performed by people.” (Kurzweil, 1990) (Winston, 1992) Systems that think like humans Systems that act rationally “The automation of activities that we associate with human thinking, such as “AI.. is concerned with intelligent behavior decision making, problem solving, learning” in artifacts (Nilsson, 1998) (Bellman, 1978) “Computational Intelligence is the study of “The exciting new effort to make computers the design of intelligent agents.” (Poole et think … machines with minds, in the full al., 1998) and literal sense.” (Haugeland, 1985) 7  Recap.. AI as the Study & Design of Intelligent Agents (Poole and Mackworth, 1999) An intelligent agent is such that: Its actions are appropriate for its goals and circumstances. It is flexible to changing environments and goals. It learns from experience. It makes appropriate choices given perceptual limitations and limited resources (bounded rationality or bounded optimality). This definition drops the constraint of cognitive plausibility; Same as building flying machines by understanding general principles of flying (aerodynamic) vs. by reproducing how birds fly. Thus, a rational agent acts to optimally achieve its goals (does the right thing). The right thing: that which is expected to maximize goal achievement, given the available information. 8  Recap.. Intelligent Agents In AI, artificial agents that have a physical presence in the world are usually known as Robots. Robotics is the field primarily concerned with the implementation of the physical aspects of a robot (i.e., perception of the physical environment, actions on the environment). Another class of artificial agents include interface agents, for either stand alone or Web-based applications (e.g., intelligent desktop assistants, recommender systems, intelligent tutoring systems). Interface agents don’t have to worry about interaction with the physical environment but share all other fundamental components of intelligent behavior with robots. We will focus on these agents in this course (i.e., software agents not hardware agents “autonomous robots”). 9  Recap.. Pac-Man.. as an..Intelligent Agent Agent Sensors Percepts ? Environment Actuators Actions 10  BB-8 “the Star Intelligent “Rational” Agents? Wars franchise” Agent Smith in The Matrix (1999) Dr. Will Caster Arthur, an android bartender on the Avalon, Passengers David in Prometheus (2012) Sonny in I, Robot (2004)  Intelligent “Rational” Agents? ! Automata TARS and CASE Interstellar L3 (Star Wars – Vision Han Solo) (Marvel Comics) Ava, in Ex Machina Intelligent Agents An agent is anything that can be viewed as perceiving its environment through sensors and acting upon that environment through actuators. 13  Intelligent Agents in the World.... Learning?.. Feedback? 1: Sense 3: Act AI “Agent” Environment 2: Reason 5: Learn 4: Get Feedback 14  Intelligent Agents in the World.. Knowledge Representation Machine Learning.. Capacities / Fields? Reasoning + Decision Theory Natural Language Generation Natural Language + Understanding Robotics + + Computer Vision Human Computer Speech Recognition /Robot + Interaction Physiological Sensing 15 Mining of Interaction Logs  Example: Vacuum –Agent Percepts: Location and status, e.g., [A, Dirty] Actions: Left, Right, Suck, NoOp function Vacuum_Agent( [ location, status ] ) returns an action if status = Dirty then return Suck else if location = A then return Right else if location = B then return Left 16 Rational Agents For each possible percept sequence, a rational agent should select an action that is expected to maximize its performance measure, given the evidence provided by the percept sequence and the agent’s built-in knowledge. Performance measure (utility function): An objective criterion for success of an agent's behaviour. 17 Specifying the Task Environment [ PEAS ] PEAS: Performance measure, Environment, Actuators, Sensors P: a function the agent is maximizing (or minimizing); Assumed given.. In practice, needs to be computed somewhere. E: a formal representation for world states; For concreteness, a tuple (var1 = val1, var2 = val2, … , varn = valn). A: actions that change the state according to a transition model; Given a state and action, what is the successor state (or distribution over successor states)? S: observations that allow the agent to infer the world state; Often come in very different form than the state itself.. E.g., in tracking, observations may be pixels and state variables 3D coordinates. 18 PEAS Example 1:Autonomous Taxi o Performance measure Safe, fast, legal, comfortable trip, maximize profits o Environment Roads, other traffic, pedestrians, customers o Actuators Steering wheel, accelerator, brake, signal, horn o Sensors Cameras, LIDAR, speedometer, GPS, odometer, engine sensors, keyboard 19 PEAS Example 2:Spam Filter o Performance measure Minimizing false positives, false negatives o Environment A user’s email account, email server o Actuators Mark as spam, delete, etc. o Sensors Incoming messages, other information about user’s account 20 Goal-based Agents versus Cost-based Agents Goal-based agents: the actions depend on the goal; E.g., a mobile robot which should move from room 112 to room 179 in a building takes actions different from those of a robot that should move to room 105. 21 Goal-based Agents versus Cost-based Agents Cost-based agents: the goal is to minimize the cost of erroneous decisions in the long term; E.g., a spam filter is an agent that puts incoming emails into wanted or unwanted (spam) categories & deletes any unwanted emails. Its goal as a goal- based agent is to put all emails in the right category. In the course of this not-so- simple task, the agent can occasionally make mistakes. Because its goal is to classify all emails correctly, it will attempt to make as few errors as possible. However, that is not always what the user has in mind. Let us compare the following two agents. Out of 1,000 emails, Agent 1 makes only 12 errors. Agent 2 on the other hand makes 38 errors with the same 1,000 emails. Is it therefore worse than Agent 1? The errors of both agents are shown in more detail in the following confusion matrix: Agent 1 in fact makes fewer errors than Agent 2, but those few errors are severe because the user loses 11 potentially important emails. Because there are in this case two types of errors of differing severity, each error should be weighted with 22 the appropriate cost factor.  Exercises What have we learned?  Differentiate between Goal-based Agents & Cost-based Agents.  Discuss PEAS, and how is it employed to specify a task environment.  What are the basic capacities of an Intelligent Agent?.. illustrate using a diagram.  Up Next.. Additional Section 2.2 Resources  Understanding Artificially Intelligent Agents: https://www.youtube.com/watch?v=XO6SV0Mu p1E  Where AI is today and where it's going. | Richard Socher | TEDxSanFrancisco: https://www.youtube.com/watch?v=8cmx7V4oI R8 Lecture 2: Intelligent Agents, & AI Related Disciplines 2.1 Intelligent “Rational” Agents? 2.3 AI: Related Disciplines  Recap: AI as the Study & Design of  Learning Agents Intelligent Agents  AI vs. Machine Learning vs. Deep  Intelligent Agents in the World Learning  An Example: Vacuum_Agent  Machine Learning?  Specifying the Task Environment [  Datamining? PEAS ]  AI vs. Data Science  Goad-based vs. Cost-based Agents  Why Data Science?  Why Big Data? 2.2 Specifying the Task Environment  Environment Types Environment Fully Observable vs. Partially Types Observable Deterministic vs. Stochastic (vs. Strategic) Episodic vs. Sequential Static vs. Dynamic (vs. Semi-Dynamic) Discrete vs. Continuous Single-Agent vs. Multi-Agent Known vs. Unknown 26 Fully Observable vs. Partially Observable o Do the agent's sensors give it access to the complete state of the environment? o For any given world state, are the values of all the variables known to the agent? vs. 27 Source: L. Zettlemoyer Deterministic vs. Stochastic (vs. Strategic) o Is the next state of the environment completely determined by the current state and the agent’s action? o Is the transition model deterministic (unique successor state given current state and action) or stochastic (distribution over successor states given current state and action)? o Strategic: the environment is deterministic except for the actions of other agents. vs. 28 Episodic vs. Sequential o Is the agent’s experience divided into unconnected single decisions/actions, or is it a coherent sequence of observations and actions in which the world evolves according to the transition model? vs. 29 Static vs. Dynamic (vs. Semi-dynamic) o Is the world changing while the agent is thinking? o Semi-dynamic: the environment does not change with the passage of time, but the agent's performance score does. vs. 30 Discrete vs. Continuous o Does the environment provide a fixed number of distinct percepts, actions, and environment states? o Are the values of the state variables discrete or continuous? o Time can also evolve in a discrete or continuous fashion. vs. 31 Single–Agent vs. Multi–Agent o Is an agent operating by itself in the environment? o Is the environment of an autonomous taxi driver a competitive multiagent environment or a cooperative multiagent environment? vs. 32 Known vs. Unknown o Are the rules of the environment (transition model and rewards associated with states) known to the agent? o Strictly speaking, not a property of the environment, but of the agent’s state of knowledge. vs. 33  Examples of the different environments Word Jumble Chess with Scrabble Autonomous Solver a Clock Driving Observable Fully Fully Partially Partially Deterministic Deterministic Strategic Stochastic Stochastic Episodic Episodic Sequential Sequential Sequential Static Static Semi-dynamic Static Dynamic Discrete Discrete Discrete Discrete Continuous Single agent Single Multi Multi Multi 34  Exercises What have we learned?  Is the environment of an autonomous taxi driver a competitive multiagent environment or a cooperative multiagent environment?  Characterize the following Task Environments: Poker Game – Medical Diagnosis – Image Analysis – Interactive English Tutor.  Is the distinction between known and unknown environments the same as the one between fully observable and partially observable?  Describe briefly the following statements (while giving an example):  Episodic environments are much simpler than sequential environments because the agent does not need to think ahead.  Communication often emerges as a rational behavior in multiagent environments.  Up Next.. Additional Section 2.3 Resources  Intelligent Agents Intro https://www.youtube.com/watch?v=UjQ1AzSvC p8 Lecture 2: Intelligent Agents, & AI Related Disciplines 2.1 Intelligent “Rational” Agents? 2.3 AI: Related Disciplines  Recap: AI as the Study & Design of  Learning Agents Intelligent Agents  AI vs. Machine Learning vs. Deep  Intelligent Agents in the World Learning  An Example: Vacuum_Agent  Machine Learning?  Specifying the Task Environment [  Datamining? PEAS ]  AI vs. Data Science  Goad-based vs. Cost-based Agents  Why Data Science?  Why Big Data? 2.2 Specifying the Task Environment  Environment Types Artificial Intelligence Related Disciplines 38 Main Resources for this Section The following courses: o Data Science, Harvard University (School of Engineering & Applied Sciences) o Introduction to Data Science - Data Intensive Computing, University of Florida o Introduction to Data Science, University of California - Berkeley o Practical Data Science: Introduction, Carnegie Mellon University 39 Learning Agents? "Of particular interest in AI are Learning agents, which are capable of changing themselves given training examples or through positive or negative feedback, such that the average utility of their actions grows over time." - Wolfgang Ertel, "Introduction to Artificial Intelligence," 2nd Edition (2017) 40 Artificial Intelligence Vs. Machine Learning Vs. Deep Learning.. A formal short answer: Deep Learning is a part of Machine Learning, which is a part of AI. https://human-centered.ai/2017/11/11/difference-ai-ml/ 41 Artificial Intelligence Vs. Machine Learning Vs. Deep Learning.. Evolution of AI — Source: https://www.embedded-vision.com/ 42 Machine Learning Vs. Deep Learning.. https://www.upwork.com/hiring/for-clients/artificial-intelligence-and-natural-language-processing-in-big-data/ 43 Machine Learning? Generic Machine Learning Models 44 Machine Learning? {Artificial Intelligence} Machine Learning Map 45 Machine Learning Approaches & their corresponding Applications 46 What about Data-Mining? Machine learning and data mining often employ the same methods and overlap significantly. They can be roughly distinguished as follows: o Machine learning focuses on prediction, based on known properties learned from the training data. o Data mining focuses on the discovery of (previously) unknown properties in the data. This is the analysis step of Knowledge Discovery in Databases. Much of the confusion between these two research communities comes from the basic assumptions they work with: in machine learning, performance is usually evaluated with respect to the ability to reproduce known knowledge, while in Knowledge Discovery and Data Mining (KDD) the key task is the discovery of previously unknown knowledge. 47 Artificial Intelligence Vs. Data-Science DataScience-Some PossibleDefinitions: Data Science is the science which uses computer science, statistics and machine learning, visualization and human- computer interactions to collect, clean, integrate, analyse, visualize, interact with data to create data products. Data science = statistics + data processing + machine learning + scientific inquiry + visualization + business analytics + big data + … 48 WhyDataScience? in 20th Century Innovations.. Engineering and Computer Science played key role: o Cars o Airplanes o Power grid o Television o Air conditioning and central heating o Nuclear power o Digital computers o The internet 49 WhyDataScience? But how about these 20th Century questions? o Does fertilizer increase crop yields? o Does Streptomycin cure Tuberculosis? o Does smoking cause lung-cancer? 50 WhyDataScience? What is the difference?.. Data o Does fertilizer increase crop yields? Answer: Collect and analyse agricultural experimental data. o Does Streptomycin cure Tuberculosis? Answer: Collect and analyse randomized trials data. o Does smoking cause lung-‐cancer? Answer: Collect and analyse observational studies data.  Deductive versus empirical..  Solutions deduced mostly from theory versus solutions deduced from mostly from data.. 51 TheDawnofBigData To understand the phenomenon that is big data, it is often described using five Vs: Volume, Velocity, Variety, Veracity, and Value. Recently, Visualization, Virality, & Viscosity were added (thus, Eight Vs).. Source: https://www.intechopen.com/books/artificial-intelligence-scope-and-limitations/prediction- 52 of-cancer-patient-outcomes-based-on-artificial-intelligence TheDawnofBigData o Volume refers to the vast amounts of data generated every second. o Velocity refers to the speed at which new data is generated and the speed at which data moves around. o Variety refers to the different types of data we can now use. In fact, 80% of the world’s data is now unstructured, and therefore can’t easily be put into tables (think of photos, video sequences or social media updates). o Veracity refers to the messiness or trustworthiness of the data. With many forms of big data, quality and accuracy are less controllable. o Value; It is all well and good having access to big data but unless we can turn it into value it is useless. 53 Success Stories & a few data science examples … MoneyBall ?! 55 Success Stories & a few data science examples … MoneyBall ?! … the Data Scientist Actual Hollywood 56  Success Stories & a few data science examples … MoneyBall ?! Starting around 2001, the Oakland A’s picked players that scouts thought were no good but data said otherwise. 57 Success Stories & a few data science examples … Poverty Mapping Abelson, Varshney, and Sun. “Targeting Direct Cash Transfers to the Extremely Poor,” 2012 58  Exercises What have we learned?  Define the following terms: (1) Data Science, (2) Learning Agents, (3) Machine Learning.  What are the characteristics of Big data (the 5 Vs)? Describe briefly.  Compare between the following: (1) Machine Learning & Data-mining, (2) Machine Learning & Deep Learning.  Draw a block diagram that describes a generic Supervised Machine Learning model.  Which Machine Learning approach is employed when realizing each the following applications:  Estimating Life expectancy.  Customer Segmentation.  Robot Navigation.  Rcommender Systems.  Market or Weather Forecasting.  Medical Image Classification.  Up Next.. Additional Lecture 3 Resources  Data Science In 5 Minutes | Data Science For Beginners | What Is Data Science? https://www.youtube.com/watch?v=X3paOmcrTjQ  Learn Data Science Tutorial - Full Course for Beginners (~6 hours) https://www.youtube.com/watch?v=ua-CiDNNj30  Deep Learning in 5 Minutes | What Is Deep Learning? | Deep Learning Explained Simply: https://www.youtube.com/watch?v=6M5VXKLf4D4  MIT Introduction to Deep Learning | 6.S191: https://www.youtube.com/watch?v=njKP3FqW3Sk  The Rise of Artificial Intelligence through Deep Learning | TEDxMontreal https://www.youtube.com/watch?v=uawLjkSI7Mo  Big Data In 5 Minutes | What Is Big Data? | Introduction To Big Data | Big Data Explained: https://www.youtube.com/watch?v=bAyrObl7TYE Thank you! AI310 & CS361 Artificial Intelligence Mainstream – Medical Informatics – Computer Science Dept. Software Engineering Programmes Helwan University Lecture 3 Problem Solving as Search & State Space Search 3.1 Solving Problems by Searching  Types of Agents (Reflex vs. Planning) - State Space Search - Example: Tic-Tac-Toe Game - Example: Mechanical Fault Diagnosing - How human beings think? - Heuristic Search 3.2 State Space Search Graph & Strategies  Search Problem Components - State Space & State Space Graph - Examples: Vacuum World, The 8-Puzzle, Romania, etc. - State Space Search Strategies - Selecting Search Strategy Faculty of 3.3 Basic Idea of Search & the Backtracking Search Algorithm Computers &  Search: Basic idea - Search Tree - Tree Search Algorithm- Artificial Intelligence Outline & Example - Handling Repeated States - Backtracking Search Algorithm & Data Structures FALL 2023 Lecture 3: Solving Problem by Searching,.. &.. State Space Search Strategies and Structures 3.1 Solving problems by Searching  Solving Problems by Searching  Example: Tic-Tac-Toe  Types of Agents (Reflex vs. Planning)  Example: Traveling Salesperson  State Space Search  State Space Search Strategies  Example: Tic-Tac-Toe Game  Selecting Search Strategy  Example: Mechanical Fault Diagnosing 3.3 Basic Idea of Search & the Backtracking Search Algorithm  How human beings think?  Search: Basic idea  Heuristic Search  Search Tree 3.2 State Space Search Graph &  Tree Search Algorithm Outline Strategies  Tree Search Example  Search Problem Components  Handling Repeated States  Example: Romania  Backtracking Search  State Space & State Space Graph  Backtracking Algorithm Data Structures  Example: Vacuum World  Backtracking Algorithm  Example: The 8-Puzzle  Example: Robot Motion Planning 3.4 Practice Exercises (Solved Problems) Resources for this lecture This lecture covers the following chapters: 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.. Part II (pages 41 to 45) and Chapter 3 (Structures and Strategies for State Space Search; only sections 3.0, 3.1, and 3.2) from George F. Luger, "Artificial Intelligence: Structures and strategies for complex problem solving, " Fifth Edition (2005), Pearson Education Limited. 3 Solving Problems by SEARCHING  Types of Agents a Reflex Agent : a Planning agent : Considers how the world IS Considers how the world WOULD BE Choose action based on current Decisions based on (hypothesized) percept. consequences of actions. Do not consider the future Must have a model of how the world consequences of actions. evolves in response to actions. Must formulate a goal. Source: D. Klein, P. Abbeel State Space Search Problems are solved by searching among alternative choices. o Humans consider several alternative strategies on their way to solving a problem. o A Chess player considers a few alternative moves. o A mathematician chooses from a different strategies to find a proof for a theorem. o A physician evaluates several possible diagnoses. Example:Tic-Tac-Toe Game X X X X X X X X X O O O X X X O X X O X X X O O O Example:Mechanical Fault Diagnosing Start ask: What is the problem? Engine trouble ask: Transmission ask:……… breaks ask: …… … Does the car start? Yes No Engine starts Engine won’t start ask: ask:………. Will engine turn over? Yes No battery Yes ok Turn over Won’t turn over ask: No ask: …….. Do lights come on? battery dead How Human Beings Think..? Human beings do not search the entire state space (exhaustive search). Only alternatives that experience has shown to be effective are explored. Human problem solving is based on judgmental rules that limit the exploration of search space to those portions of state space that seem somehow promising. These judgmental rules are known as “heuristics”. Heuristic Search A heuristic is a strategy for selectively exploring the search space. It guides the search along lines that have a high probability of success. It employs knowledge about the nature of a problem to find a solution. It does not guarantee an optimal solution to the problem but can come close most of the time. Human beings use many heuristics in problem solving.  Exercises What have we learned?  Define the following terms:  State Space Graph,  Exhaustive Search, and..  Heuristics.  Describe briefly the difference between a Planning Agent & a Reflex Agent.  Give examples of Heuristics that human beings employ in any domain.  Up Next.. Additional Section 3.2 Resources  Searching: https://www.youtube.com/watch?v=t0yCDZe6Tnk  State Space Problems: https://www.youtube.com/watch?v=ngkXAcjeNWE Lecture 3: Solving Problem by Searching,.. &.. State Space Search Strategies and Structures 3.1 Solving problems by Searching  Solving Problems by Searching  Example: Tic-Tac-Toe  Types of Agents (Reflex vs. Planning)  Example: Traveling Salesperson  State Space Search  State Space Search Strategies  Example: Tic-Tac-Toe Game  Selecting Search Strategy  Example: Mechanical Fault Diagnosing 3.3 Basic Idea of Search & the Backtracking Search Algorithm  How Human Beings Think?  Search: Basic idea  Heuristic Search  Search Tree 3.2 State Space Search Graph &  Tree Search Algorithm Outline Strategies  Tree Search Example  Search Problem Components  Handling Repeated States  Example: Romania  Backtracking Search  State Space & State Space Graph  Backtracking Algorithm Data Structures  Example: Vacuum World  Backtracking Algorithm  Example: The 8-Puzzle  Example: Robot Motion Planning 3.4 Practice Exercises (Solved Problems) Search We will consider the problem of designing goal-based agents in fully observable, deterministic, discrete, known environments. Start State Goal State Search We will consider the problem of designing goal-based agents in fully observable, deterministic, discrete, known environments. The agent must find a sequence of actions that reaches the goal. The performance measure is defined by: (a) reaching the goal, and.. (b) how “expensive” the path to the goal is. Search Problem Components Initial Initial state State Actions Transition model What state results from performing a given action in each state? Goal state Solution Path Path cost Assume that it is a sum of Goal nonnegative step costs State The optimal solution is the sequence of actions that gives the lowest path cost for reaching the goal.  Example:Romania - On vacation in Romania; currently in Arad. - Flight leaves tomorrow from Bucharest. Initial state o Arad Actions o Go from one city to another Transition Model o If you go from city A to city B, you end up in city B Goal State o Bucharest Path Cost o Sum of edge costs (total distance traveled) State Space The initial state, actions, and transition model define the state space of the problem; The set of all states reachable from initial state by any sequence of actions. Can be represented as a directed graph where the nodes are states and links between nodes are actions. What is the state space for the Romania problem? State Space An AI problem can be represented as a state space graph. A graph is a set of nodes and links that connect them. Graph theory: o Labeled graph. ○ Parent. o Directed graph. ○ Child. o Path. ○ Sibling. o Rooted graph. ○ Ancestor. o Tree. ○ Descendant. State Space Graph Theory, Kônigsberg Bridges Problem, & Euler Tour.. Riverbank 1 4 River Island 1 1 Island 2 7 Riverbank 2 State Space A state space is represented by four-tuple [N, A, S, GD]. o N, is the set of nodes or states of the graph. These correspond to the states in the problem-solving process. o A, is the set of arcs between nodes. These correspond to the steps in a problem-solving process. o S, a nonempty subset of N, contains the start-state (s) of the problem. o GD, a nonempty subset of N, contains the goal-state(s) of the problem. The states in GD are described using either: o A measurable property of the states encountered in the search. o A property of the solution path developed in the search (a solution path is a path through this graph from a node in S to a node in GD).  Example: Vacuum World o States: o Agent location and dirt location o How many possible states? o What if there are n possible locations? o The size of the state space grows exponentially with the “size” of the world! o Actions: o Left, right, suck. o Transition Model.. ?  Example:Vacuum World State Space Graph o Transition Model: Example: the8-Puzzle o States o Locations of tiles o 8-puzzle: 181,440 states (9!/2) o 15-puzzle: ~10 trillion states o 24-puzzle: ~1025 states o Actions o Move blank left, right, up, down o Path Cost o 1 per move Example: Robot Motion Planning o States o Real-valued joint parameters (angles, displacements). o Actions o Continuous motions of robot joints. o Goal State o Configuration in which object is grasped. o Path Cost o Time to execute, smoothness of path, etc. Example: Tic-Tac-Toe Nodes(N): all the different configuration of Xs and Os that the game can have. Arcs (A): generated by legal moves by placing an X or an O in unused location. Start state (S): an empty board. Goal states (GD): a board state having three Xs in a row, column, or diagonal. The arcs are directed, then no cycles in the state space, directed acyclic graph (DAG). Complexity: 9! Different paths can be generated. Example: Traveling Salesperson A salesperson has five cites to visit and ten must return home. Nodes(N): represent 5 cites. Arcs(A): labeled with weight indicating the cost of traveling between connected cites. Start state(S): a home city. Goal states(GD): an entire path contains a complete circuit with minimum cost. Complexity: (n-1)! Different cost-weighted paths can be generated. State Space Search Strategies There are two distinct ways for searching a state space graph:  Data-Driven Search: (Forward chaining) Start searching from the given data of a problem instance toward a goal.  Goal-Driven Search: (Backward chaining) Start searching from a goal state to facts or data of the given problem. State Space Search Strategies.. Selecting Search Strategy Data-Driven Search is suggested if: o The data are given in the initial problem statement. o There are few ways to use the given facts. o There are large number of potential goals. o It is difficult to form a goal or hypothesis. Goal- Driven Search is appropriate if: o A goal is given in the problem statement or can easily formulated. o There are large number of rules to produce a new facts. o Problem data are not given but acquired by the problem solver.  Exercises What have we learned?  Define the following terms: Path, Rooted Graph, Tree.  Describe using drawing the Kongsberg problem "Euler Tour."  Determine whether goal-driven or data-driven search would be preferable for solving each of the following problems. Justify your answer.  You have met a person who claims to be your distant cousin, with a common ancestor named John Doe. You would like to verify her claim.  Another person claims to be your distant cousin. He doesn't know the common ancestor's name but knows that it was no more than eight generations back. You would like to either find this ancestor or determine that she didn't exist.  A theorem prover for plane geometry.  Up Next.. Additional Section 3.3 Resources  Backward & Forward Chaining: https://www.youtube.com/watch?v=ZhTt-GG7PiQ Lecture 3: Solving Problem by Searching,.. &.. State Space Search Strategies and Structures 3.1 Solving problems by Searching  Solving Problems by Searching  Example: Tic-Tac-Toe  Types of Agents (Reflex vs. Planning)  Example: Traveling Salesperson  State Space Search  State Space Search Strategies  Example: Tic-Tac-Toe Game  Selecting Search Strategy  Example: Mechanical Fault Diagnosing 3.3 Basic Idea of Search & the Backtracking Search Algorithm  How human beings think?  Search: Basic idea  Heuristic Search  Search Tree 3.2 State Space Search Graph &  Tree Search Algorithm Outline Strategies  Tree Search Example  Search Problem Components  Handling Repeated States  Example: Romania  Backtracking Search  State Space & State Space Graph  Backtracking Algorithm Data Structures  Example: Vacuum World  Backtracking Algorithm  Example: The 8-Puzzle  Example: Robot Motion Planning 3.4 Practice Exercises (Solved Problems) Search..? Given:  Initial state  Actions  Transition model  Goal state  Path cost How do we find the optimal solution? 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. Search: Basic idea Start Search: Basic idea Search: Basic idea Search: Basic idea Search: Basic idea Search: Basic idea Search: Basic idea Search: Basic idea Search: Basic idea Search: Basic idea Search: Basic idea Search: Basic idea  Starting Search Tree (theWhat-if tree) State “What if” tree of sequences of actions and Action outcomes; Successor  I.e., When we are searching, we are not acting State in the world, merely “thinking” about the possibilities.  The root node corresponds to the starting state.  The children of a node correspond to the … successor states of that node’s state. Frontier  A path through the tree corresponds to a Goal sequence of actions. State  A solution is a path ending in the goal state Nodes vs. States..? A state is a representation of the world, while a node is a data structure that is part of the search tree. Node must keep pointer to parent, path cost, possibly other info. Tree Search Algorithm Outline 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.  Tree Search Example Start: Arad Goal: Bucharest  Tree Search Example Start: Arad Goal: Bucharest  Tree Search Example Start: Arad Goal: Bucharest Handling Repeated States - 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. To handle repeated states: Every time you expand a node, add that state to the explored set; do not put explored states on the frontier again. Every time you add a node to the frontier, check whether it already exists with a higher path cost, and if yes, replace that node with the new one. Backtracking Search “Backtracking is a technique for systematically trying all paths through a state space” It begins at the start state and pursues a path until: Finding a goal, then quit and return the solution path. Finding a dead end, then backtrack to the most recent unexamined node and continue down one of its branches. Backtracking Search Start Node Dead Dead Dead Dead End End End End Backtracking Algorithm Data Structures o State List (SL): lists the states in the current path being tried. If the goal is found, then it contains the solution path. o New State List (NSL): contains nodes a waiting evaluation. o Dead Ends (DE): lists states whose descendants have failed to contain a goal node. o Current State (CS): a state currently under consideration.  theBacktracking Algorithm Function Backtrack; Begin SL := [Start]; NSL := [Start]; CS := Start; while NSL# [ ] do begin if CS = goal (or meets goal description) then return (SL); if CS has no children (excluding nodes already on DE, SL, and NSL) then begin while SL is not empty and CS = the first element of SL do begin add CS to DE; remove first element from SL; remove first element from NSL; CS := first element of NLS; end; add CS to SL; end else begin place children of CS on NSL; (except nodes on DE, SL, or NSL) CS := first element of NSL; add CS to SL; end; end; return FAIL; end;  theBacktracking Algorithm SL = [A]; NSL = [A]; DE = [ ]; CS = A; SL := [Start]; NSL := [Start]; CS := Start; while NSL# [ ] do if CS = goal (or meets goal description) then return (SL); if CS has no children (excluding nodes already on DE, SL, and NSL) then … … … else …  theBacktracking Algorithm SL = [A]; NSL = [A]; DE = [ ]; CS = A; … … else place children of CS on NSL; (except nodes on DE, SL, or NSL) CS := first element of NSL; add CS to SL; end; …..  theBacktracking Algorithm SL = [B A]; NSL = [B C D A]; DE = [ ]; CS = B; … … else place children of CS on NSL; (except nodes on DE, SL, or NSL) CS := first element of NSL; add CS to SL; end; …..  theBacktracking Algorithm SL = [E B A]; NSL = [E F B C D A]; DE = [ ]; CS = E; … … else place children of CS on NSL; (except nodes on DE, SL, or NSL) CS := first element of NSL; add CS to SL; end; …..  theBacktracking Algorithm SL = [H E B A]; NSL = [H I E F B C D A]; DE = [ ]; CS = H; …. if CS has no children (excluding nodes already on DE, SL, and NSL) then … while SL is not empty and CS = the first element of SL do begin add CS to DE; remove first element from SL; remove first element from NSL; CS := first element of NLS; end; add CS to SL; else …  theBacktracking Algorithm SL = [I E B A]; NSL = [I E F B C D A]; DE = [H]; CS = I; …. if CS has no children (excluding nodes already on DE, SL, and NSL) then … while SL is not empty and CS = the first element of SL do begin add CS to DE; remove first element from SL; remove first element from NSL; CS := first element of NLS; end; add CS to SL; else …  theBacktracking Algorithm SL = [E B A]; NSL = [E F B C D A]; DE = [I H]; CS = E; …. if CS has no children (excluding nodes already on DE, SL, and NSL) then … while SL is not empty and CS = the first element of SL do begin add CS to DE; remove first element from SL; remove first element from NSL; CS := first element of NLS; end; add CS to SL; else …  theBacktracking Algorithm SL = [F B A]; NSL = [F B C D A]; DE = [E I H]; CS = F;  theBacktracking Algorithm SL = [J F B A]; NSL = [J F B C D A]; DE = [E I H]; CS = J;  theBacktracking Algorithm SL = [C A]; NSL = [C D A]; DE = [B F J E I H]; CS = C;  theBacktracking Algorithm SL = [G C A]; NSL = [G C D A]; DE = [B F J E I H]; CS = G;  Exercises What have we learned?  The following are two problems that can be solved using state-space search techniques. You should:  Suggest a suitable representation for the problem state.  State what the initial and final states are in this representation.  State the available operators/rules for getting from one state to the next, giving any conditions on when they may be applied.  Draw the first two levels of the directed state- space graph for the given problem.  Exercises What have we learned?  [Problem # 1] The Cannibals and Missionaries problem: "Three cannibals and three missionaries come to a crocodile infested river. There is a boat on their side that can be used by either one or two persons. If cannibals outnumber the missionaries at any time, the cannibals eat the missionaries. How can they use the boat to cross the river so that all missionaries survive?" Formalize the problem in terms of state-space search.  [Problem # 2] A farmer with his dog, rabbit and lettuce come to the east side of a river they wish to cross. There is a boat at the river’s edge, but of course only the farmer can row. The boat can only hold two things (including the rower) at any one time. If the dog is ever left alone with the rabbit, the dog will eat it. Similarly, if the rabbit is ever left alone with the lettuce, the rabbit will eat it. How can the farmer get across the river so that all four characters arrive safely on the other side?  Up Next.. Additional Section 3.4 (video lesson) Resources  Backtracking (Solving a Maze – C++): https://www.youtube.com/watch?v=gBC_Fd8EE8A  N Queen Problem | Backtracking: https://www.youtube.com/watch?v=0DeznFqrgAI  Sudoku (Visualisation) | Backtracking: https://www.youtube.com/watch?v=_vWRZiDUGHU Thank you! AI310 & CS361 Artificial Intelligence Mainstream – Medical Informatics – Computer Science Dept. Software Engineering Programmes Helwan University Lecture 5 Problem Solving as Search Blind vs. Heuristic Search 5.1 Blind / Uninformed Search [ Part 1 ]  Blind vs. Heuristic Strategies – Blind / Exhaustive Strategies - Depth-First Strategy (DFS) – Breadth-First Strategy (BFS) 5.2 Blind / Uninformed Search [ Part 2 ]  Depth-Limited & Iterative-Deepening Strategies – Complexity / Comparison of Blind Search Strategies – Bidirectional Search – Avoiding Repeated States – Uniform-Cost Strategy 5.3 Heuristic Search & Functions [ Part 1 ] Faculty of Computers &  Best-First Search – Examples of Evaluation function Artificial Intelligence 5.4 Heuristic Search & Functions [ Part 2 ]  Symmetry / Heuristic Reductions – Hill Climbing Strategy FALL 2023 Resources for this lecture This lecture covers the following chapters: Ch