CIT 478 Artificial Intelligence Course Guide PDF

NATIONAL OPEN UNIVERSITY OF NIGERIA FACULTY OF SCIENCE DEPARTMENT OF COMPUTER SCIENCE COURSE CODE: CIT478 COURSE TITLE: ARTIFICIAL INTELLIGENCE CIT478 COURSE GUIDE COURSE GUIDE CIT478 ARTIFICIAL INTELLIGENCE Course Team Dr. J.N. Ndunagu (Developer/Writer) - NOUN Dr. J.N. Ndunagu (Coordinator) - NOUN ii CIT478 COURSE GUIDE NATIONAL OPEN UNIVERSITY OF NIGERIA iii CIT478 COURSE GUIDE National Open University of Nigeria Headquarters 14/16 Ahmadu Bello Way Victoria Island Lagos Abuja Office No. 5 Dar es Salaam Street Off Aminu Kano Crescent Wuse II, Abuja Nigeria e-mail: [email protected] URL: www.nou.edu.ng Published By: National Open University of Nigeria First Printed 2012 Reviewed and Reprinted 2021 ISBN: 978-058-826-4 All Rights Reserved iv CIT478 COURSE GUIDE CONTENTS PAGE Introduction…....................................................................................... 1 What You Will Learn in This Course…............................................... 1 Course Aim............................................................................................ 2 Course Objectives….............................................................................. 2 Working through This Course…........................................................... 3 Course Materials…............................................................................... 3 Study Units…....................................................................................... 4 Textbooks and References.................................................................... 4 Assignment File…................................................................................ 9 Presentation Schedule…....................................................................... 9 Assessment…........................................................................................ 9 Tutor Marked Assignments (TMAs)…............................................... 10 Final Examination and Grading…........................................................ 10 Course Marking Scheme...................................................................... 10 Course Overview….............................................................................. 11 How to Get the Most from This Course............................................... 12 Facilitators/Tutors and Tutorials…...................................................... 13 v Introduction Welcome to CIT478 Artificial Intelligence which is a two credit unit course offered in the fourth year to students of the undergraduate degree programme in Communication Technology and Computer Science. There are eleven study Units in this course. There are no prerequisites for studying this course. It has been developed with appropriate local and foreign examples suitable for audience. This course guide is for distance learners enrolled in the B.Sc. Communication Technology and Computer Science programmes of the National Open University of Nigeria. This guide is one of the several resource tools available to you to help you successfully complete this course and ultimately your programme. In this guide you will find very useful information about this course, aims and objectives, what the course is about, what course materials you will be used, available services to support your learning, information on assignments and examination. It also offers you guidelines on how to plan your time for study the amount of time you are likely to spend on each study unit as well as your tutor-marked assignments. I strongly recommend that you go through this course guide and complete the feedback form at the end before you begin studying the course. The feedback form must be submitted to your tutorial facilitator along with your first assignment. I wish you all the best in your learning experience and successful completion of this course. What You Will Learn in This Course The overall aim of this course, CIT478 is to introduce you to artificial Intelligence and the different faculties involved in it. It also examines different ways of approaching AI. It starts with the basics and then moves on to the more advanced concepts. The Search in artificial Intelligence - State Space Search, uninformed Search, informed Search Strategies and tree Search are also treated. You will also learn about Knowledge Representation and programming languages for AI. Finally, CIT478 ARTIFICIAL INTELLIGENCE you will be introduced to Artificial Intelligence and its applications – Expert System and Robotics. Course Aim This course aims at introducing you to Artificial Intelligent (AI), different types of intelligent agents (IA) and types of AI search. You are not expected to have experience in Artificial Intelligent before using this course material. It is hoped that the knowledge would help you solve some real world problems. Course Objectives In order to achieve this aim, the course has a set of objectives. Each unit has specific objectives which are included at the beginning of the unit. You are expected to read these objectives before you study the unit. You may wish to refer to them during your study to check on your progress. You should always look at the unit objectives after completion of each unit. By doing so, you would have followed the instructions in the unit. Below are the comprehensive objectives of the course as a whole. By meeting these objectives, you should have achieved the aim of the course. Therefore, after going through this course you should be able to:  State the definition of Artificial Intelligence  List the different faculties involved with intelligent behavior  Explain the different ways of approaching AI  Look at some example systems that use AI  Describe the history of AI  Explain what an agent is and how it interacts with the environment.  Identify the percepts available to the agent and the actions that the agent can execute, if given a problem situation  Measure the performance used to evaluate an agent  State based agents  Identify the characteristics of the environment  Describe the state space representation.  Describe Some algorithms ii CIT478 ARTIFICIAL INTELLIGENCE  Formulate, when given a problem description, the terms of a state space search problem  Analyze the properties of Some algorithms  Analyze a given problem and identify the most suitable search strategy for the problem.  Solve Some Simple problems  Explain Uninformed Search  List two types of Uninformed Search  Describe Depth First and Breadth First Search  Solve simple problems on Uninformed Search  Explain informed Search  Mention other names of informed Search  Describe Best-first Search  Describe Greedy Search  Solve simple problems on informed Search  Describe a Game tree  Describe Some Two-Player Games Search Algorithms  Explain Intelligent Backtracking  Solve Some Simple problems on tree search.  Explain the meaning of Knowledge Representation  Describe the history of History of knowledge representation and reasoning  List some Characteristics of KR  List 4 main features of KR language  Describe the History of IPL  Discuss the similarities between Lisp and Prolog Programming  list the areas where Lisp can be used  Describe the history of natural language processing  List major tasks in NLP  Mention different types of evaluation of NPL  Explain an Expert System  Distinction between expert systems and traditional problem solving programs  Explain the term ―Knowledge Base‖  Explain the word Robotics  List 4 types of Robotics you know  Describe the history of Robotics Working through This Course iii CIT478 ARTIFICIAL INTELLIGENCE To complete this course, you are required to read each study unit, read the textbooks and read other materials which may be provided by the National Open University of Nigeria. Each unit contains tutor marked assignments and at certain points in the course you would be required to submit assignment for assessment purposes. At the end of the course there is a final examination. The course should take you about a total of eleven (11) weeks to complete. Below is the list of all the components of the course, what you have to do and how you should allocate your time to each unit in order to complete the course on time and successfully. This course entails that you spend a lot of time to read and practice. For easy understanding of this course, I will advise that you avail yourself the opportunity of attending the tutorials sessions where you would have the opportunity to compare your knowledge with that of other people, and also have your questions answered. The Course Material The main components of this course are: 1. The Course Guide 2. Study Units 3. Further Reading/References 4. Assignments 5. Presentation Schedule Study Units There are 11 study units and 4 modules in this course. They are: Module 1 Introduction to AI Unit 1 What is Artificial Intelligent (AI)? Unit 2 Introduction to Intelligent Agent (IA) Module 2 Search in Artificial Intelligence Unit 1 Introduction to State Space Search Unit 2 Uninformed Search iv CIT478 ARTIFICIAL INTELLIGENCE Unit 3 Informed Search Strategies Unit 4 Tree Search Module 3 Artificial Intelligence Techniques in Programming and Natural Languages Unit 1 Knowledge Representation Unit 2 Programming Languages for Artificial Intelligence Unit 3 Natural Language Processing Module 4 Artificial Intelligence and Its Applications Unit 1 Expert System Unit 2 Robotics Textbooks and References These texts will be of enormous benefit to you in learning this course: Adrian Walker; Michael McCord; John F. Sowa and Walter G. Wilson (1990). Knowledge Systems and Prolog (Second Edition). Addison-Wesley. Argumentation in Artificial Intelligence by Iyad Rahwan, Guillermo R. Simari Arthur B. Markman (1998). Knowledge Representation. Lawrence Erlbaum Associates. Asimov, Isaac (1996). "The Robot Chronicles". Gold. London: Voyager. pp. 224–225. ISBN 0-00-648202-3. Bates, M. (1995). Models of Natural Language Understanding. Proceedings of the National Academy of Sciences of the United States of America, Vol. 92, No. 22 (Oct. 24, 1995), pp. 9977– 9982. v CIT478 ARTIFICIAL INTELLIGENCE Bowling, M. and Veloso, M. (2002). Multiagent Learning Using a Variable Learning Rate Artificial Intelligence, 136(2): 215-250. Chein, M. & Mugnier, M.-L. (2009). Graph-based Knowledge Representation: Computational Foundations of Conceptual Graphs, Springer, 2009,ISBN 978-1-84800-285-2. Christopher D. Manning, Hinrich Schütze (1999). Foundations of Statistical Natural Language Processing, MIT Press, ISBN 978-0- 262-13360-9, p. Xxxi. Crane, Carl D.; Joseph Duffy (1998-03). Kinematic Analysis of Robot Manipulators. Cambridge University Press. ISBN 0521570638. http://www.cambridge.org/us/catalogue/catalogue.asp?isbn=0521 570638. Crevier, Daniel (1993). AI: The Tumultuous Search for Artificial Intelligence. New York, NY: Basic Books, ISBN 0-465-02997-3. Davis, R. Shrobe, H.E. Representing Structure and Behavior of Digital Hardware, IEEE Computer, Special Issue on Knowledge Representation, 16(10):75-82. Dechter, Rina; Judea Pearl (1985). "Generalized best-first search strategies and the optimality of A*". Journal of the ACM 32 (3): 505–536. doi:10.1145/3828.3830. Dowe, D.L. and Hajek, A. R. (1997). "A Computational Extension to the Turing Test". Proceedings of the 4th Conference of the Australasian Cognitive Science jSociety. http://www.csse.monash.edu.au/publications/1997/tr-cs97-322- abs.html. Hermann Helbig: Knowledge Representation and the Semantics of Natural Language. Springer, Berlin, Heidelberg, New York 2006 Jean-Luc Hainaut, Jean-Marc Hick, Vincent Englebert, Jean Henrard, Didier Roland: Understanding Implementations of IS-A Relations. ER 1996: 42-57 vi CIT478 ARTIFICIAL INTELLIGENCE Jeen Broekstraa, Michel Klein, Stefan Deckerc, Dieter Fenselb, Frank van Harmelenb and Ian Horrocks Enabling knowledge representation on the Web by extending RDF Schema, , April 16 2002. John F. Sowa (2000). Knowledge Representation: Logical, Philosophical, and Computational Foundations. New York: Brooks/Cole. John McCarthy (1979). History of Lisp "LISP prehistory - Summer 1956 through Summer 1958." Jose H. (2000). "Beyond the Turing Test". Journal of Logic, Language and Information 9 (4): 447–466. doi:10.1023/A:1008367325700. http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.44.894 3. Koenig, Sven; Maxim Likhachev, Yaxin Liu, David Furcy (2004). "Incremental heuristic search in AI". AI Magazine 25 (2): 99– 112. http://portal.acm.org/citation.cfm?id=1017140. Lowerre, Bruce (1976). "The Harpy Speech Recognition System", Ph.D. thesis, Carnegie Mellon University. Marakas, George. Decision Support Systems in the 21st Century. Prentice Hall, 1999, p.29. McCarthy, John (November 12, 2007). "What Is Artificial Intelligence?". http://www-formal.stanford.edu/jmc/whatisai/ whatisai.html Michael Wooldridge, An Introduction to Multiagent Systems, John Wiley & Sons, Ltd. Nilsson, N. J. (1980). Principles of Artificial Intelligence. Palo Alto, California: Tioga Publishing Company. ISBN 0-935382-01-1. Nilsson, Nils (1998). Artificial Intelligence: A New Synthesis, Morgan Kaufmann Publishers, ISBN 978-1-55860-467-4. vii CIT478 ARTIFICIAL INTELLIGENCE Nishibori; et al. (2003). Robot Hand with Fingers Using Vibration-Type Ultrasonic Motors (Driving Characteristics). Journal of Robotics and Mechatronics. http://www.fujipress.jp/finder/xslt.php?mode= present&inputfile=ROBOT001500060002.xml. OWL DL Semantics. http://www.obitko.com/tutorials/ontologies- semantic-web/owl-dl-semantics.html. Park; et al. (2005). Synthetic Personality in Robots and Its Effect on Human-Robot Relationship. Pearl, Judea (1984). Heuristics: Intelligent Search Strategies for Computer Problem Solving. Addison-Wesley Longman Publishing Co., Inc.. ISBN 0-201-05594-5. Philippe Martin "Knowledge representation in RDF/XML, KIF, Frame- CG and Formalized-English", , Distributed System Technology Centre, QLD, Australia, July 15-19, 2002 Poole, David; Mackworth, Alan; Goebel, Randy (1998). Computational Intelligence: A Logical Approach. New York: Oxford University Press, ISBN 0195102703, http://www.cs.ubc.ca/spider/poole/ ci.html Pople H, Heuristic Methods for Imposing Structure on Ill-Structured Problems, in AI in Medicine, Szolovits (ed.). AAAS Symposium 51, Boulder: Westview Press. Randall Davis, Howard Shrobe, and Peter Szolovits; What Is a Knowledge Representation? AI Magazine, 14(1):17-33,1993 Ronald Fagin, Joseph Y. Halpern, Yoram Moses, Moshe Y. Vardi Reasoning About Knowledge. MIT Press, 1995, ISBN 0-262- 06162-7. Ronald J. Brachman, Hector J. Levesque (eds) Readings in Knowledge Representation, Morgan Kaufmann, 1985, ISBN 0-934613-01-X viii CIT478 ARTIFICIAL INTELLIGENCE Ronald J. Brachman, Hector J. Levesque Knowledge Representation and Reasoning, Morgan Kaufmann, 2004 ISBN 978-1-55860-932-7 Ronald J. Brachman; What IS-A is and Isn't. An Analysis of Taxonomic Links in Semantic Networks; IEEE Computer, 16 (10); October 1983. Rosheim, Mark E. (1994). Robot Evolution: The Development of Anthrobotics. Wiley-IEEE. pp. 9–10. ISBN 0471026220. Russell, S. J.; Norvig, P. (2003). Artificial Intelligence: A Modern Approach. Upper Saddle River, N.J.: Prentice Hall. pp. 97–104. ISBN 0-13-790395-2. Russell, Stuart J.; Norvig, Peter (2003). Artificial Intelligence: A Modern Approach (2nd ed.), Upper Saddle River, New Jersey: Prentice Hall, ISBN 0-13-790395-2, http://aima.cs.berkeley.edu/ Russell, Stuart J.; Norvig, Peter (2003). Artificial Intelligence: A Modern Approach (2nd ed.), Upper Saddle River, New Jersey: Prentice Hall, pp. 111–114, ISBN 0-13-790395-2 Russell, Stuart J.; Norvig, Peter (2003). Artificial Intelligence: A Modern Approach (2nd ed.). Upper Saddle River, New Jersey: Prentice Hall, ISBN 0-13-790395-2, http://aima.cs.berkeley.edu/ Russell, Stuart J.; Norvig, Peter (2010). Artificial Intelligence: A Modern Approach (3rd ed.), Upper Saddle River, New Jersey: Prentice Hall, ISBN 0-13-604259-7, p. 437-439. Sebesta, Robert W. (1996). Concepts of Programming Languages, (Third Edition). Addison-Wesley Publishing Company, Menlo Park, California. Serenko, Alexander; Detlor, Brian (2004). "Intelligent agents as innovations". AI and Society 18 (4): 364–381. doi:10.1007/s00146-004-0310-5. http://foba.lakeheadu.ca/ serenko/papers/Serenko_Detlor_AI_and_Society.pdf ix CIT478 ARTIFICIAL INTELLIGENCE Serenko, Alexander; Ruhi, Umar; Cocosila, Mihail (2007). "Unplanned effects of intelligent agents on Internet use: Social Informatics approach". AI and Society 21 (1–2): 141–166. doi:10.1007/s00146-006-0051-8. http://foba.lakeheadu.ca/serenko/papers/AI_Society_Serenko_So cial_Impacts_of_Agents.pdf Shapiro, Stuart C. (1992). "Artificial Intelligence". In Shapiro, Stuart C.. Encyclopedia of Artificial Intelligence (2nd ed.). New York: John Wiley. pp. 54–57. ISBN 0471503061. http://www.cse.buffalo.edu/~shapiro/Papers/ai.pdf. Skillings, J. (2006). "Getting Machines to Think Like Us". cnet. http://news.cnet.com/Getting-machines-to-think-like-us/2008- 11394_3-6090207.html. Stuart Russell; Peter Norvig (2010). Artificial Intelligence: A Modern Approach (3 ed.). Prentice Hall. ISBN 978-0-13-6042594 Turing, Alan (1950), "Computing Machinery and Intelligence", Mind LIX (236): 433–460, doi:10.1093/mind/LIX.236.433, ISSN 0026-4423, http://loebner.net/Prizef/TuringArticle.html. Yucong Duan, Christophe Cruz (2011). Formalizing Semantic of Natural Language through Conceptualization from Existence. International Journal of Innovation, Management and Technology (2011) 2 (1), pp. 37-42. Zhou, Rong. Hansen, Eric (2005). "Beam-Stack Search: Integrating Backtracking with Beam Search". http://www.aaai.org/Library/ICAPS/2005/icaps05-010.php Assignment File The assignment file will be given to you in due course. In this file, you will find all the details of the work you must submit to your tutor for marking. The marks you obtain for these assignments will count towards the final mark for the course. Altogether, there are 11 tutor marked assignments for this course. x CIT478 ARTIFICIAL INTELLIGENCE Presentation Schedule The presentation schedule included in this course guide provides you with important dates for completion of each tutor marked assignment. You should therefore endeavor to meet the deadlines. Assessment There are two aspects to the assessment of this course. First, there are tutor marked assignments; and second, the written examination. Therefore, you are expected to take note of the facts, information and problem solving gathered during the course. The tutor marked assignments must be submitted to your tutor for formal assessment, in accordance to the deadline given. The work submitted will count for 40% of your total course mark. At the end of the course, you will need to sit for a final written examination. This examination will account for 60% of your total score. Tutor-Marked Assignments (TMAs) There are 11 TMAs in this course. You need to submit all the TMAs. The best 4 will therefore be counted. When you have completed each assignment, send them to your tutor as soon as possible and make certain that it gets to your tutor on or before the stipulated deadline. If for any reason you cannot complete your assignment on time, contact your tutor before the assignment is due to discuss the possibility of extension. Extension will not be granted after the deadline, unless on extraordinary cases. Final Examination and Grading The final examination for CIT478 will be of last for a period of 2 hours and have a value of 60% of the total course grade. The examination will consist of questions which reflect the tutor marked assignments that you have previously encountered. Furthermore, all areas of the course will be examined. It would be better to use the time between finishing the last unit and sitting for the examination, to revise the entire course. You might find it useful to review your TMAs and comment on them before the examination. The final examination covers information from all parts of the course. Course Marking Scheme xi CIT478 ARTIFICIAL INTELLIGENCE The following table includes the course marking scheme Table 1: Course Marking Scheme Assessment Marks Assignments 1-11 11 assignments, 40% for the best 4 Total = 10% X 4 = 40% Final Examination 60% of overall course marks Total 100% of Course Marks Course Overview This table indicates the units, the number of weeks required to complete them and the assignments. Table 2: Course Organizer Unit Title of the work Weeks Assessment Activity (End of Unit) Course Guide Week 1 Module 1 Introduction to AI 1 What Is AI? Week 1 Assessment 1 2 Introduction to Agent Week 2 Assessment 2 Module 2 Search in Artificial Intelligence 1 Introduction to State Space Search Week 3 Assessment 3 2 Uninformed Search Week 4 Assessment 4 3 - Informed Search Strategies Week 5 Assessment 5 4 Tree Search Week 6 Assessment 6 Module 3 Knowledge Representation and Programming Languages for AI 1 Knowledge Representation Week 7 Assessment 7 2 Programming Languages for Artificial Week 8 Assessment 8 Intelligence 3 – Natural Language Processing Week 9 Assessment 9 Module 4 Artificial Intelligence and the Future 1 Expert System Week 10 Assessment 10 2 Robotics Week 11 Assessment 11 How to Get the Best from This Course xii CIT478 ARTIFICIAL INTELLIGENCE In distance learning, the study units replace the university lecturer. This is one of the great advantages of distance learning; you can read and work through specially designed study materials at your own pace, and at a time and place that suit you best. Think of it as reading the lecture instead of listening to a lecturer. In the same way that a lecturer might set you some reading to do, the study units tell you when to read your set books or other material. Just as a lecturer might give you an in-class exercise, your study units provide exercises for you to do at appropriate points. Each of the study units follows a common format. The first item is an introduction to the subject matter of the unit and how a particular unit is integrated with the other units and the course as a whole. Next is a set of learning objectives. These objectives enable you know what you should be able to do by the time you have completed the unit. You should use these objectives to guide your study. When you have finished the units you must go back and check whether you have achieved the objectives. If you make a habit of doing this you will significantly improve your chances of passing the course. Remember that your tutor‘s job is to assist you. When you need help, don‘t hesitate to call and ask your tutor to provide it.  Read this Course Guide thoroughly.  Organize a study schedule. Refer to the ‗Course Overview‘ for more details. Note the time you are expected to spend on each unit and how the assignments relate to the units. Whatever method you chose to use, you should decide on it and write in your own dates for working on each unit.  Once you have created your own study schedule, do everything you can to stick to it. The major reason that students fail is that they lag behind in their course work.  Turn to Unit 1 and read the introduction and the objectives for the unit.  Assemble the study materials. Information about what you need for a unit is given in the ‗Overview‘ at the beginning of each unit. You will almost always need both the study unit you are working on and one of your set of books on your desk at the same time. xi ii CIT478 ARTIFICIAL INTELLIGENCE  Work through the unit. The content of the unit itself has been arranged to provide a sequence for you to follow. As you work through the unit you will be instructed to read sections from your set books or other articles. Use the unit to guide your reading.  Review the objectives for each study unit to confirm that you have achieved them. If you feel unsure about any of the objectives, review the study material or consult your tutor.  When you are confident that you have achieved a unit‘s objectives, you can then start on the next unit. Proceed unit by unit through the course and try to pace your study so that you keep yourself on schedule.  When you have submitted an assignment to your tutor for marking, do not wait for its return before starting on the next unit. Keep to your schedule. When the assignment is returned, pay particular attention to your tutor‘s comments on the tutor-marked assignment form. Consult your tutor as soon as possible if you have any questions or problems.  After completing the last unit, review the course and prepare yourself for the final examination. Check that you have achieved the unit objectives (listed at the beginning of each unit) and the course objectives (listed in this Course Guide). Facilitators/Tutors and Tutorials There are 11 hours of tutorials provided in support of this course. You will be notified of the dates, times and location of these tutorials, together with the name and phone number of your tutor, as soon as you are allocated a tutorial group.  Your tutor will mark and comment on your assignments, keep a close watch on your progress and on any difficulties you might encounter and provide assistance to you during the course. You must mail or submit your tutor-marked assignments to your tutor well before the due date (at least two working days are required). They will be marked by your tutor and returned to you as soon as possible.  Do not hesitate to contact your tutor by telephone, or e-mail if you need help. The following might be circumstances in which you would find help necessary. Contact your tutor if: xiv CIT478 ARTIFICIAL INTELLIGENCE  You do not understand any part of the study units or the assigned readings  You have a question or problem with an assignment, with your tutor‘s comments on an assignment or with the grading of an assignment. You should try your best to attend the tutorials. This is the only chance to have face to face contact with your tutor and to ask questions which are answered instantly. You can raise any problem encountered in the course of your study. To gain the maximum benefit from course tutorials, prepare a question list before attending them. You will learn a lot from participating in discussions actively. GOODLUCK! xv CIT478 ARTIFICIAL INTELLIGENCE Course Code CIT478 Course Title Artificial Intelligence Course Team Dr. J.N. Ndunagu (Developer/Writer) - NOUN Dr. J.N. Ndunagu (Coordinator) - NOUN NATIONAL OPEN UNIVERSITY OF NIGERIA xvi CIT478 ARTIFICIAL INTELLIGENCE National Open University of Nigeria Headquarters 14/16 Ahmadu Bello Way Victoria Island Lagos Abuja Office No. 5 Dar es Salaam Street Off Aminu Kano Crescent Wuse II, Abuja Nigeria e-mail: [email protected] URL: www.nou.edu.ng Published By: National Open University of Nigeria First Printed 2012 ISBN: 978-058-826-4 All Rights Reserved xv ii CIT478 ARTIFICIAL INTELLIGENCE CONTENTS PAGE Module 1 Introduction to AI.......................................................... 1 Unit 1 What is Artificial Intelligent (AI)?.................................. 1 Unit 2 Introduction to Intelligent Agent (IA)............................ 13 Module 2 Search in Artificial Intelligence.................................. 24 Unit 1 Introduction to State Space Search................................ 24 Unit 2 Uninformed Search........................................................ 42 Unit 3 Informed Search Strategies............................................ 53 Unit 4 Tree Search..................................................................... 72 Module 3 Artificial Intelligence Techniques in Programming and Natural Languages...................... 81 Unit 1 Knowledge Representation............................................ 81 Unit 2 Programming Languages for Artificial Intelligence.... 100 Unit 3 Natural Language Processing........................................115 Module 4 Artificial Intelligence and its Applications............... 128 Unit 1 Expert System............................................................... 128 Unit 2 Robotics..........................................................................142 xviii CIT478 ARTIFICIAL INTELLIGENCE MODULE 1 INTRODUCTION TO AI Unit 1 What Is Artificial Intelligent (AI)? Unit 2 Introduction to Intelligent Agent (IA) UNIT 1 WHAT IS ARTIFICIAL INTELLIGENT (AI)? CONTENTS 1.0 Introduction 2.0 Objectives 3.0 Main Content 3.1 Definition of AI 3.1.1 What is AI? 3.1.2 Typical AI problem 3.1.3 Practical Impact of AI 3.1.4 Approaches to AI 3.1.5 Limits of AI Today 3.2 AI History 4.0 Conclusion 5.0 Summary 6.0 Tutor-Marked Assignment 7.0 References/Further Reading 1.0 INTRODUCTION This unit introduces you to Artificial Intelligence and the different faculties involve in it. It also examines different ways of approaching AI. 2.0 OBJECTIVES At the end of this unit, you should be able to:  state the definition of Artificial Intelligence  list the different faculties involved with intelligent behavior  explain the different ways of approaching AI  look at some example systems that use AI  describe the history of AI. 1 CIT478 ARTIFICIAL INTELLIGENCE 3.0 MAIN CONTENT 3.1 Definition of AI What is AI? Artificial Intelligence is a branch of Science which deals with helping machines find solutions to complex problems in a more human-like fashion. This generally involves borrowing characteristics from human intelligence, and applying them as algorithms in a computer friendly way. A more or less flexible or efficient approach can be taken depending on the requirements established, which influences how artificial the intelligent behaviour appears. AI is generally associated with Computer Science, but it has many important links with other fields such as Mathematics, Psychology, Cognition, Biology and Philosophy, among many others. Our ability to combine knowledge from all these fields will ultimately benefit our progress in the quest of creating an intelligent artificial being It is also concerned with the design of intelligence in an artificial device. The term was coined by McCarthy in 1956. There are two ideas in the definition. 1. Intelligence 2. Artificial device What is intelligence? - Is it that which characterize humans? Or is there an absolute standard of judgment? - Accordingly there are two possibilities: - A system with intelligence is expected to behave as intelligently as a human - A system with intelligence is expected to behave in the best possible manner - Secondly what type of behavior are we talking about? - Are we looking at the thought process or reasoning ability of the system? - Or are we only interested in the final manifestations of the system in terms of its actions? Given this scenario different interpretations have been used by different researchers as defining the scope and view of Artificial Intelligence. 1. One view is that artificial intelligence is about designing systems that are as intelligent as humans. This view involves trying to 2 CIT478 ARTIFICIAL INTELLIGENCE understand human thought and an effort to build machines that emulate the human thought process. This view is the cognitive science approach to AI. 2. The second approach is best embodied by the concept of the Turing Test. Turing held that in future computers can be programmed to acquire abilities rivaling human intelligence. As part of his argument Turing put forward the idea of an 'imitation game', in which a human being and a computer would be interrogated under conditions where the interrogator would not know which was which, the communication being entirely by textual messages. Turing argued that if the interrogator could not distinguish them by questioning, then it would be unreasonable not to call the computer intelligent. Turing's 'imitation game' is now usually called 'the Turing test' for intelligence. Figure 1: Turing Test Turing Test Consider the following setting. There are two rooms, A and B. One of the rooms contains a computer. The other contains a human. The interrogator is outside and does not know which one is a computer. He can ask questions through a teletype and receives answers from both A 3 CIT478 ARTIFICIAL INTELLIGENCE and B. The interrogator needs to identify whether A or B are humans. To pass the Turing test, the machine has to fool the interrogator into believing that it is human. For more details on the Turing test visit the site http://cogsci.ucsd.edu/~asaygin/tt/ttest.html 3. Logic and laws of thought deals with studies of ideal or rational thought process and inference. The emphasis in this case is on the inferencing mechanism, and its properties. That is how the system arrives at a conclusion, or the reasoning behind its selection of actions is very important in this point of view. The soundness and completeness of the inference mechanisms are important here. 4. The fourth view of AI is that it is the study of rational agents. This view deals with building machines that act rationally. The focus is on how the system acts and performs, and not so much on the reasoning process. A rational agent is one that acts rationally, that is, is in the best possible manner. 3.1.2 Typical AI problems While studying the typical range of tasks that we might expect an ―intelligent entity‖ to perform, we need to consider both ―common- place‖ tasks as well as expert tasks. Examples of common-place tasks include - Recognizing people, objects. - Communicating (through natural language). - Navigating around obstacles on the streets These tasks are done matter of firstly and routinely by people and some other animals. Expert tasks include: Medical diagnosis. Mathematical problem solving Playing games like chess These tasks cannot be done by all people, and can only be performed by skilled specialists. Now, which of these tasks are easy and which ones are hard? Clearly tasks of the first type are easy for humans to perform, and almost all are able to master them. The second range of tasks requires skill 4 CIT478 ARTIFICIAL INTELLIGENCE development and/or intelligence and only some specialists can perform them well. However, when we look at what computer systems have been able to achieve to date, we see that their achievements include performing sophisticated tasks like medical diagnosis, performing symbolic integration, proving theorems and playing chess. On the other hand it has proved to be very hard to make computer systems perform many routine tasks that all humans and a lot of animals can do. Examples of such tasks include navigating our way without running into things, catching prey and avoiding predators. Humans and animals are also capable of interpreting complex sensory information. We are able to recognize objects and people from the visual image that we receive. We are also able to perform complex social functions. Intelligent behaviour. This discussion brings us back to the question of what constitutes intelligent behaviour. Some of these tasks and applications are:  Perception involving image recognition and computer vision  Reasoning  Learning  Understanding language involving natural language processing, speech processing  Solving problems  Robotics 3.1.3 Practical Impact of AI AI components are embedded in numerous devices e.g. in copy machines for automatic correction of operation for copy quality improvement. AI systems are in everyday use for identifying credit card fraud, for advising doctors, for recognizing speech and in helping complex planning tasks. Then there are intelligent tutoring systems that provide students with personalized attention Thus AI has increased understanding of the nature of intelligence and found many applications. It has helped in the understanding of human reasoning, and of the nature of intelligence. It will also help you understand the complexity of modeling human reasoning. You can now look at a few famous AI systems. 5 CIT478 ARTIFICIAL INTELLIGENCE 1. ALVINN Autonomous Land Vehicle in a Neural Network In 1989, Dean Pomerleau at CMU created ALVINN. This is a system which learns to control vehicles by watching a person drive. It contains a neural network whose input is a 30x32 unit two dimensional camera image. The output layer is a representation of the direction the vehicle should travel. The system drove a car from the East Coast of USA to the west coast, a total of about 2850 miles. Out of this about 50 miles were driven by a human being and the rest solely by the system. 2. Deep Blue In 1997, the Deep Blue chess program created by IBM, beat the current world chess champion, Gary Kasparov. 3. Machine translation A system capable of translations between people speaking different languages will be a remarkable achievement of enormous economic and cultural benefit. Machine translation is one of the important fields of endeavour in AI. While some translating systems have been developed, there is a lot of scope for improvement in translation quality. 4. Autonomous agents In space exploration, robotic space probes autonomously monitor their surroundings, make decisions and act to achieve their goals. NASA's Mars rovers successfully completed their primary three-month missions in April, 2004. The Spirit rover had been exploring a range of Martian hills that took two months to reach. It is finding curiously eroded rocks that may be new pieces to the puzzle of the region's past. Spirit's twin, Opportunity, had been examining exposed rock layers inside a crater. 5. Internet Agents The explosive growth of the internet has also led to growing interest in internet agents to monitor users' tasks, seek needed information, and to learn which information is most useful 6 CIT478 ARTIFICIAL INTELLIGENCE 3.1.4 Approaches to AI Strong AI aims to build machines that can truly reason and solve problems. These machines should be self aware and their overall intellectual ability needs to be indistinguishable from that of a human being. Excessive optimism in the 1950s and 1960s concerning strong AI has given way to an appreciation of the extreme difficulty of the problem. Strong AI maintains that suitably programmed machines are capable of cognitive mental states. Weak AI deals with the creation of some form of computer-based artificial intelligence that cannot truly reason and solve problems, but can act as if it were intelligent. Weak AI holds that suitably programmed machines can simulate human cognition. Applied AI aims to produce commercially viable "smart" systems such as, security system that is able to recognise the faces of people who are permitted to enter a particular building. Applied AI has already enjoyed considerable success. Cognitive AI: computers are used to test theories about how the human mind works--for example, theories about how we recognise faces and other objects, or about how we solve abstract problems. 3.1.5 Limits of AI Today Today‘s successful AI systems operate in well-defined domains and employ narrow, specialized knowledge. Common sense knowledge is needed to function in complex, open-ended worlds. Such a system also needs to understand unconstrained natural language. However these capabilities are not yet fully present in today‘s intelligent systems.  What can AI systems do? Today‘s AI systems have been able to achieve limited success in some of these tasks.  In Computer vision, the systems are capable of face recognition  In Robotics, we have been able to make vehicles that are mostly autonomous  In Natural language processing, we have systems that are capable of simple machine translation  Today‘s Expert systems can carry out medical diagnosis in a narrow domain 7 CIT478 ARTIFICIAL INTELLIGENCE  Speech understanding systems are capable of recognizing several thousand words continuous speech  Planning and scheduling systems had been employed in scheduling experiments with the Hubble Telescope  The Learning systems are capable of doing text categorization into about a 1000 topics  In Games, AI systems can play at the Grand Master level in chess (world champion), checkers, etc.  What can AI systems NOT do yet?  Understand natural language robustly (e.g., read and understand articles in a newspaper)  Surf the web  Interpret an arbitrary visual scene  Learn a natural language  Construct plans in dynamic real-time domains  Exhibit true autonomy and intelligence 3.2 AI History Intellectual roots of AI date back to the early studies of the nature of knowledge and reasoning. The dream of making a computer imitate humans also has a very early history. The concept of intelligent machines is found in Greek mythology. There th is a story in the 8 century A.D about Pygmalion Olio, the legendary king of Cyprus. He fell in love with an ivory statue he made to represent his ideal woman. The king prayed to the goddess Aphrodite, and the goddess miraculously brought the statue to life. Other myths involve human-like artifacts. As a present from Zeus to Europa, Hephaestus created Talos, a huge robot. Talos was made of bronze and his duty was to patrol the beaches of Crete. Aristotle (384-322 BC) developed an informal system of syllogistic logic, which is the basis of the first formal deductive reasoning system. th Early in the 17 century, Descartes proposed that bodies of animals are nothing more than complex machines. Pascal in 1642 made the first mechanical digital calculating machine. th In the 19 century, George Boole developed a binary algebra representing (some) "laws of thought." 8 CIT478 ARTIFICIAL INTELLIGENCE Charles Babbage & Ada Byron worked on programmable mechanical calculating machines. In the late 19th century and early 20th century, mathematical philosophers like Gottlob Frege, Bertram Russell, Alfred North Whitehead, and Kurt Gödel built on Boole's initial logic concepts to develop mathematical representations of logic problems. The advent of electronic computers provided a revolutionary advance in the ability to study intelligence. In 1943 McCulloch & Pitts developed a Boolean circuit model of brain. They wrote the paper ―A Logical Calculus of Ideas Immanent in Nervous Activity‖, which explained how it is possible for neural networks to compute. Marvin Minsky and Dean Edmonds built the SNARC in 1951, which is the first randomly wired neural network learning machine (SNARC stands for Stochastic Neural-Analog Reinforcement Computer).It was a neural network computer that used 3000 vacuum tubes and a network with 40 neurons. In 1950 Turing wrote an article on ―Computing Machinery and Intelligence‖ which articulated a complete vision of AI. For more on Alan Turing see the site http://www.turing.org.uk/turing/. Turing‘s paper talked of many things, of solving problems by searching through the space of possible solutions, guided by heuristics. He illustrated his ideas on machine intelligence by reference to chess. He even propounded the possibility of letting the machine alter its own instructions so that machines can learn from experience. In 1956 a famous conference took place in Dartmouth. The conference brought together the founding fathers of artificial intelligence for the first time. In this meeting the term ―Artificial Intelligence‖ was adopted. Between 1952 and 1956, Samuel had developed several programs for playing checkers. In 1956, Newell & Simon‘s Logic Theorist was published. It is considered by many to be the first AI program. In 1959, Gelernter developed a Geometry Engine. In 1961 James Slagle (PhD dissertation, MIT) wrote a symbolic integration program SAINT. It was written in LISP and solved calculus problems at the college freshman level. In 1963, Thomas Evan's program Analogy was developed which could solve IQ test type analogy problems. 9 CIT478 ARTIFICIAL INTELLIGENCE In 1963, Edward A. Feigenbaum & Julian Feldman published Computers and Thought, the first collection of articles about artificial intelligence. In 1965, J. Allen Robinson invented a mechanical proof procedure, the Resolution Method, which allowed programs to work efficiently with formal logic as a representation language. In 1967, the Dendral program (Feigenbaum, Lederberg, Buchanan, Sutherland at Stanford) was demonstrated which could interpret mass spectra on organic chemical compounds. This was the first successful knowledge-based program for scientific reasoning. In 1969 the SRI robot, Shakey, demonstrated combining locomotion, perception and problem solving. The years from 1969 to 1979 marked the early development of knowledge-based systems In 1974, MYCIN demonstrated the power of rule-based systems for knowledge representation and inference in medical diagnosis and therapy. Knowledge representation schemes were developed. These included frames developed by Minski. Logic based languages like Prolog and Planner were developed. We will now mention a few of the AI systems that were developed over the years. The Meta-Dendral learning program produced new results in chemistry (rules of mass spectrometry) In the 1980s, Lisp Machines developed and marketed. Around 1985, neural networks return to popularity. In 1988, there was a resurgence of probabilistic and decision-theoretic methods. The early AI systems used general systems, little knowledge. AI researchers realized that specialized knowledge is required for rich tasks to focus reasoning. The 1990's saw major advances in all areas of AI including the following:  Machine learning, data mining  Intelligent tutoring,  Case-based reasoning,  Multi-agent planning, scheduling, 10 CIT478 ARTIFICIAL INTELLIGENCE  Uncertain reasoning,  Natural language understanding and translation,  Vision, virtual reality, games, and other topics. Rod Brooks' COG Project at MIT, with numerous collaborators, made significant progress in building a humanoid robot. The first official Robo-Cup soccer match featuring table-top matches with 40 teams of interacting robots was held in 1997. For details, see the site http://murray.newcastle.edu.au/users/students/2002/c3012299/bg. html In the late 90s, Web crawlers and other AI-based information extraction programs become essential in widespread use of the world-wide-web. Interactive robot pets ("smart toys") become commercially available, realizing the vision of the 18th century novelty toy makers. In 2000, the Nomad robot explores remote regions of Antarctica looking for meteorite samples. AI in the news http://www.aaai.org/AITopics/html/current.html 4.0 CONCLUSION Artificial intelligence (AI) is the intelligence of machines and the branch of computer science that aims to create it. AI textbooks define the field as "the study and design of intelligent agents" where an intelligent agent is a system that perceives its environment and takes actions that maximize its chances of success. John McCarthy, who coined the term in 1956, defines it as "the science and engineering of making intelligent machines." The field was founded on the claim that a central property of humans, intelligence—the sapience of Homo sapiens—can be so precisely described that it can be simulated by a machine. This raises philosophical issues about the nature of the mind and the ethics of creating artificial beings, issues which have been addressed by myth, fiction and philosophy since antiquity. Artificial intelligence has been the subject of optimism, but has also suffered setbacks and, today, has become an essential part of the technology industry, providing the heavy lifting for many of the most difficult problems in computer science. 11 CIT478 ARTIFICIAL INTELLIGENCE 5.0 SUMMARY In this unit, you have learnt that:  Artificial Intelligence is a branch of Science which deals with helping machines find solutions to complex problems in a more human-like fashion  Typical AI problems  AI History  Limits of AI Today 6.0 TUTOR-MARKED ASSIGNMENT 1. Define intelligence. 2. What are the different approaches in defining artificial intelligence? 3. List five tasks that you will like a computer to be able to do within the next five years. 4. List five tasks that computers are unlikely to be able to do in the next five years. 7.0 REFERENCES/FURTHER READING Dowe D.L. & Hajek, A. R. (1997). "A Computational Extension to the Turning Test". Proceedings of the 4th Conference of the Australasian Cognitive Science Society. http://www.csse.monash. edu.au/publications/1997/tr-cs97-322-abs.html. Jose, H. (2000). "Beyond the Turing Test". Journal of Logic, Language and Information 9 (4): 447–466. doi:10.1023/A:1008367325700. http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.44.894 3. McCarthy, J. (November 12, 2007). "What Is Artificial Intelligence?. http://www-formal.stanford.edu/jmc/whatisai/whatisai.html Shapiro, S. C. (1992). "Artificial Intelligence". In Shapiro, Stuart, C.. Encyclopedia of Artificial Intelligence (2nd ed.). New York: John Wiley. pp. 54–57. ISBN 0471503061. http://www.cse.buffalo. edu/~shapiro/Papers/ai.pdf. Skillings, J. (2006). "Getting Machines to Think Like Us". cnet. http://news.cnet.com/Getting-machines-to-think-like-us/2008- 11394_3-6090207.html. Turing, Alan (1950), "Computing Machinery and Intelligence", Mind LIX (236): 433–460, doi:10.1093/mind/LIX.236.433, ISSN 0026-4423, http://loebner.net/Prizef/TuringArticle.html. 12 CIT478 ARTIFICIAL INTELLIGENCE UNIT 2 INTRODUCTION TO INTELLIGENT AGENTS CONTENTS 1.0 Introduction 2.0 Objectives 3.0 Main Content 3.1. Introduction to Agent 3.1.1 Agent Performance 3.1.2 Examples of Agents 3.1.3 Agent Faculties 3.1.4 Intelligent Agents 3.1.5 Rationality 3.1.6 Bound Rationality 3.2 Agent Environment 3.2.1 Observability 3.2.2 Determinism 3.2.3 Episodicity 3.2.4 Dynamism 3.2.5 Continuity 3.2.6 Presence of other Agents 3.3 Agent Architectures or Reflex Agent 3.3.1 Table Based Agent 3.3.2 Percept based 3.3.3 Subsumption Architecture 3.3.4 State-based Reflex Agent 4.0 Conclusion 5.0 Summary 6.0 Tutor-Marked Assignment 7.0 References/Further Reading 1.0 INTRODUCTION This unit introduces you to Intelligence Agents (IA), how it interacts with the environment and Agent architectures. IA is an autonomous entity which observes and acts upon an environment. It may use knowledge to achieve their goals. They may be very simple or very complex. 2.0 OBJECTIVES At the end of this unit, you should be able to:  explain what an agent is and how it interacts with the environment. 13 CIT478 ARTIFICIAL INTELLIGENCE  identify the percepts available to the agent and the actions that the agent can execute, if given a problem situation  measure the performance used to evaluate an agent  list based agents  identify the characteristics of the environment. 3.0 MAIN CONTENT 3.1 Introduction to Agent An agent perceives its environment through sensors. The complete set of inputs at a given time is called a percept. The current percept or a sequence of percepts can influence the actions of an agent. The agent can change the environment through actuators or effectors. An operation involving an Effector is called an action. Actions can be grouped into action sequences. The agent can have goals which it tries to achieve. Thus, an agent can be looked upon as a system that implements a mapping from percept sequences to actions. A performance measure has to be used in order to evaluate an agent. An autonomous agent decides autonomously which action to take in the current situation to maximize progress towards its goals. 3.1.1 Agent Performance An agent function implements a mapping from perception history to action. The behaviour and performance of intelligent agents have to be evaluated in terms of the agent function. The ideal mapping specifies which actions an agent ought to take at any point in time. The performance measure is a subjective measure to characterize how successful an agent is. The success can be measured in various ways. It can be measured in terms of speed or efficiency of the agent. It can be measured by the accuracy or the quality of the solutions achieved by the agent. It can also be measured by power usage, money, etc. 3.1.2 Examples of Agents 1. Humans can be looked upon as agents. They have eyes, ears, skin, taste buds, etc. for sensors; and hands, fingers, legs, mouth for effectors. 14 CIT478 ARTIFICIAL INTELLIGENCE 2. Robots are agents. Robots may have camera, sonar, infrared, bumper, etc. for sensors. They can have grippers, wheels, lights, speakers, etc. for actuators. Some examples of robots are Xavier from CMU, COG from MIT, etc. Figure 2: Xavier Robot (CMU) Then we have the AIBO entertainment robot from SONY. Figure 3: Aibo from SONY 3. We also have software agents or softbots that have some functions as sensors and some functions as actuators. Askjeeves.com is an example of a softbot. 4. Expert systems like the Cardiologist are an agent. 5. Autonomous spacecrafts. 6. Intelligent buildings. 15 CIT478 ARTIFICIAL INTELLIGENCE 3.1.3 Agent Faculties The fundamental faculties of intelligence are  Acting  Sensing  Understanding, reasoning, learning Blind action is not a characterization of intelligence. In order to act intelligently, one must sense. Understanding is essential to interpret the sensory percepts and decide on an action. Many robotic agents stress sensing and acting, and do not have understanding. 3.1.4 Intelligent Agents An Intelligent Agent must sense, must act, must be autonomous (to some extent). It also must be rational. AI is about building rational agents. An agent is something that perceives and acts. A rational agent always does the right thing. 1. What are the functionalities (goals)? 2. What are the components? 3. How do we build them? 3.1.5 Rationality Perfect Rationality assumes that the rational agent knows all and will take the action that maximizes her utility. Human beings do not satisfy this definition of rationality. Rational Action is the action that maximizes the expected value of the performance measure given the percept sequence to date. However, a rational agent is not omniscient. It does not know the actual outcome of its actions, and it may not know certain aspects of its environment. Therefore rationality must take into account the limitations of the agent. The agent has too select the best action to the best of its knowledge depending on its percept sequence, its background knowledge and its feasible actions. An agent also has to deal with the expected outcome of the actions where the action effects are not deterministic. 16 CIT478 ARTIFICIAL INTELLIGENCE 3.1.6 Bounded Rationality ―Because of the limitations of the human mind, humans must use approximate methods to handle many tasks.‖ Herbert Simon, 1972 Evolution did not give rise to optimal agents, but to agents which are in some senses locally optimal at best. In 1957, Simon proposed the notion of Bounded Rationality: that property of an agent that behaves in a manner that is nearly optimal with respect to its goals as its resources will allow. Under these promises an intelligent agent will be expected to act optimally to the best of its abilities and its resource constraints. 3.2 Agent Environment Environments in which agents operate can be defined in different ways. It is helpful to view the following definitions as referring to the way the environment appears from the point of view of the agent itself. 3.2.1 Observability In terms of observability, an environment can be characterized as fully observable or partially observable. In a fully observable environment, the entire environment relevant to the action being considered is observable. In such environments, the agent does not need to keep track of the changes in the environment. A chess playing system is an example of a system that operates in a fully observable environment. In a partially observable environment, the relevant features of the environment are only partially observable. A bridge playing program is an example of a system operating in a partially observable environment. 3.2.2 Determinism In deterministic environments, the next state of the environment is completely described by the current state and the agent‘s action. Image analysis If an element of interference or uncertainty occurs then the environment is stochastic. Note that a deterministic yet partially observable environment will appear to be stochastic to the agent. Ludo 17 CIT478 ARTIFICIAL INTELLIGENCE If the environment state is wholly determined by the preceding state and the actions of multiple agents, then the environment is said to be strategic. Example: Chess 3.2.3 Episodicity An episodic environment means that subsequent episodes do not depend on what actions occurred in previous episodes. In a sequential environment, the agent engages in a series of connected episodes. 3.2.4 Dynamism Static Environment: does not change from one state to the next while the agent is considering its course of action. The only changes to the environment are those caused by the agent itself.  A static environment does not change while the agent is thinking.  The passage of time as an agent deliberates is irrelevant.  The agent doesn‘t need to observe the world during deliberation. A Dynamic Environment changes over time independent of the actions of the agent -- and thus if an agent does not respond in a timely manner, this counts as a choice to do nothing 3.2.5 Continuity If the number of distinct percepts and actions is limited, the environment is discrete, otherwise it is continuous. 3.2.6 Presence of Other agents Single agent/ Multi-agent A multi-agent environment has other agents. If the environment contains other intelligent agents, the agent needs to be concerned about strategic, game-theoretic aspects of the environment (for either cooperative or competitive agents) Most engineering environments do not have multi-agent properties, whereas most social and economic systems get their complexity from the interactions of (more or less) rational agents. 18 CIT478 ARTIFICIAL INTELLIGENCE 3.3 Agent architectures 3.3.1 Table Based Agent In table based agent the action is looked up from a table based on information about the agent‘s percepts. A table is simple way to specify a mapping from percepts to actions. The mapping is implicitly defined by a program. The mapping may be implemented by a rule based system, by a neural network or by a procedure. There are several disadvantages to a table based system. The tables may become very large. Learning a table may take a very long time, especially if the table is large. Such systems usually have little autonomy, as all actions are pre-determined. 3.3.2 Percept based agent or reflex agent In percept based agents, 1. information comes from sensors - percepts 2. changes the agents current state of the world 3. triggers actions through the effectors Such agents are called reactive agents or stimulus-response agents. Reactive agents have no notion of history. The current state is as the sensors see it right now. The action is based on the current percepts only. The following are some of the characteristics of percept-based agents.  Efficient  No internal representation for reasoning, inference.  No strategic planning, learning.  Percept-based agents are not good for multiple, opposing, goals. 3.3.3 Subsumption Architecture We will now briefly describe the subsumption architecture (Rodney Brooks, 1986). This architecture is based on reactive systems. Brooks notes that in lower animals there is no deliberation and the actions are based on sensory inputs. But even lower animals are capable of many complex tasks. His argument is to follow the evolutionary path and build simple agents for complex worlds. 19 CIT478 ARTIFICIAL INTELLIGENCE The main features of Brooks‘ architecture are.  There is no explicit knowledge representation  Behaviour is distributed, not centralized  Response to stimuli is reflexive  The design is bottom up, and complex behaviours are fashioned from the combination of simpler underlying ones.  Individual agents are simple The Subsumption Architecture built in layers. There are different layers of behaviour. The higher layers can override lower layers. Each activity is modeled by a finite state machine. The subsumption architecture can be illustrated by Brooks‘ Mobile Robot example. Figure 4: Subsumption Architecture The system is built in three layers. 1. Layer 0: Avoid Obstacles 2. Layer1: Wander behaviour 3. Layer 2: Exploration behavior Layer 0 (Avoid Obstacles) has the following capabilities:  Sonar: generate sonar scan  Collide: send HALT message to forward  Feel force: signal sent to run-away, turn 20 CIT478 ARTIFICIAL INTELLIGENCE Layer1 (Wander behaviour)  Generates a random heading  Avoid reads repulsive force, generates new heading, feeds to turn and forward Layer 2 (Exploration behaviour)  Whenlook notices idle time and looks for an interesting place.  Pathplan sends new direction to avoid.  Integrate monitors path and sends them to the path plan. 3.3.4 State-Based Agent or Model-Based Reflex Agent State based agents differ from percept based agents in that such agents maintain some sort of state based on the percept sequence received so far. The state is updated regularly based on what the agent senses, and the agent‘s actions. Keeping track of the state requires that the agent has knowledge about how the world evolves, and how the agent‘s actions affect the world. Thus a state based agent works as follows:  information comes from sensors – percepts  based on this, the agent changes the current state of the world  based on state of the world and knowledge (memory), it triggers actions through the effectors 3.3.5 Goal-based Agent The goal based agent has some goal which forms a basis of its actions. Such agents work as follows:  information comes from sensors - percepts  changes the agents current state of the world  based on state of the world and knowledge (memory) and goals/intentions, it chooses actions and does them through the effectors. Goal formulation based on the current situation is a way of solving many problems and search is a universal problem solving mechanism in AI. The sequence of steps required to solve a problem is not known a priori and must be determined by a systematic exploration of the alternatives. 21 CIT478 ARTIFICIAL INTELLIGENCE 3.3.6 Utility-based Agent Utility based agents provide a more general agent framework. In case that the agent has multiple goals, this framework can accommodate different preferences for the different goals. Such systems are characterized by a utility function that maps a state or a sequence of states to a real valued utility. The agent acts so as to maximize expected utility. 3.3.7 Learning Agent Learning allows an agent to operate in initially unknown environments. The learning element modifies the performance element. Learning is required for true autonomy 4.0 CONCLUSION In conclusion, an intelligent agent (IA) is an autonomous entity which observes and acts upon an environment. Intelligent agents may also learn or use knowledge to achieve their goals. They may be very simple or very complex: a reflex machine such as a thermostat is an intelligent agent, as is a human being, as is a community of human beings working together towards a goal. 5.0 SUMMARY In this unit, you have learnt that:  AI is a truly fascinating field. It deals with exciting but hard problems. A goal of AI is to build intelligent agents that act so as to optimize performance.  An agent perceives and acts in an environment that has architecture, and is implemented by an agent program.  An ideal agent always chooses the action which maximizes its expected performance, given its percept sequence so far.  An autonomous agent uses its own experience rather than built-in knowledge of the environment by the designer.  An agent program maps from percept to action and updates its internal state.  Reflex agents respond immediately to percepts.  Goal-based agents act in order to achieve their goal(s).  Utility-based agents maximize their own utility function.  Representing knowledge is important for successful agent design. 22 CIT478 ARTIFICIAL INTELLIGENCE  The most challenging environments are partially observable, stochastic, sequential, dynamic, and continuous, and contain multiple intelligent agents. 6.0 TUTOR-MARKED ASSIGNMENT 1. Define an agent. 2. What is a rational agent? 3. What is bounded rationality? 4. What is an autonomous agent? 5. Describe the salient features of an agent. 7.0 REFERENCES/FURTHER READING Bowling, M. & Veloso, M. (2002). Multiagent Learning Using a Variable Learning Rate. Artificial Intelligence. 136(2): 215-250. Serenko, A.; Detlor, B. (2004). "Intelligent Agents as Innovations". AI and Society 18 (4): 364–381. doi:10.1007/s00146-004-0310-5. http://foba.lakeheadu.ca/serenko/papers/Serenko_Detlor_AI_and _Society.pdf Serenko, A.; Ruhi, U.; Cocosila, M. (2007). "Unplanned Effects of Intelligent Agents on Internet use: Social Informatics approach". AI and Society 21 (1–2): 141–166. doi:10.1007/s00146-006- 0051-8. http://foba.lakeheadu.ca/serenko/papers/AI_Society_ Serenko_Social_Impacts_of_Agents.pdf. 23 CIT478 ARTIFICIAL INTELLIGENCE MODULE 2 SEARCH IN ARTIFICIAL INTELLIGENCE Unit 1 Introduction to State Space Search Unit 2 Uninformed Search Unit 3 Informed Search Strategies-I Unit 4 Tree Search UNIT 1 INTRODUCTION TO STATE SPACE SEARCH CONTENTS 1.0 Introduction 2.0 Objectives 3.0 Main Content 3.1 State space search 3.1.1 Goal Directed Agent 3.1.2 State Space Search Notations 3.2 Problem Space 3.2.1 Search Problem 3.3 Examples 3.2.1 Illustration of a search process 3.2.2 Example problem: Pegs and Disks problem 3.2.3 Queens Problem 3.2.4 Problem Definition - Example, 8 puzzle 3.4 Types of AI Search Techniques 4.0 Conclusion 5.0 Summary 6.0 Tutor- Marked Assignment 7.0 References/Further Reading 1.0 INTRODUCTION In computer science, a search algorithm, broadly speaking, is an algorithm for finding an item with specified properties among a collection of items. The items may be stored individually as records in a database; or may be elements of a search space defined by a mathematical formula or procedure, such as the roots of an equation with integer variables; or a combination of the two, such as the Hamiltonian circuits of a graph. Specifically, Searching falls under Artificial Intelligence (AI). A major goal of AI is to give computers the ability to think, or in other words, mimic human behavior. The problem is, unfortunately, computers don't 24 CIT478 ARTIFICIAL INTELLIGENCE function in the same way our minds do. They require a series of well- reasoned out steps before finding a solution. Your goal, then, is to take a complicated task and convert it into simpler steps that your computer can handle. That conversion from something complex to something simple is what this unit is primarily about. Learning how to use two search algorithms is just a welcome side-effect. This unit will explain the background for AI search and some of the AI search techniques. 2.0 OBJECTIVES After the end of this unit, you should be able to:  describe the state space representation  describe some algorithms  formulate, when given a problem description, the terms of a state space search problem  analyse the properties of some algorithms  analyse a given problem and identify the most suitable search strategy for the problem  solve some simple problems. 3.0 MAIN CONTENT 3.1 State Space Search Let us begin by introducing certain terms. An initial state is the description of the starting configuration of the agent. An action or an operator takes the agent from one state to another state which is called a successor state. A state can have a number of successor states. A plan is a sequence of actions. The cost of a plan is referred to as the path cost. The path cost is a positive number, and a common path cost may be the sum of the costs of the steps in the path. The goal state is the partial description of the solution 25 CIT478 ARTIFICIAL INTELLIGENCE 3.1.1 Goal Directed Agent Figure 1: Goal Directed Agent We have earlier discussed about an intelligent agent. In this unit we will study a type of intelligent agent which we will call a goal directed agent. A goal directed agent needs to achieve certain goals. Such an agent selects its actions based on the goal it has. Many problems can be represented as a set of states and a set of rules of how one state is transformed to another. Each state is an abstract representation of the agent's environment. It is an abstraction that denotes a configuration of the agent. Let us look at a few examples of goal directed agents. 1. 15-puzzle: The goal of an agent working on a 15-puzzle problem may be to reach a configuration which satisfies the condition that the top row has the tiles 1, 2 and 3. The details of this problem will be described later. 2. The goal of an agent may be to navigate a maze and reach the HOME position. The agent must choose a sequence of actions to achieve the desired goal. 3.1.2 State Space Search Notations Now let us look at the concept of a search problem. 26 CIT478 ARTIFICIAL INTELLIGENCE Problem formulation means choosing a relevant set of states to consider, and a feasible set of operators for moving from one state to another. Search is the process of considering various possible sequences of operators applied to the initial state, and finding out a sequence which culminates in a goal state. 3.2 Problem Space What is problem space? A problem space is a set of states and a set of operators. The operators map from one state to another state. There will be one or more states that can be called initial states, one or more states which we need to reach what are known as goal states and there will be states in between initial states and goal states known as intermediate states. So what is the solution? The solution to the given problem is nothing but a sequence of operators that map an initial state to a goal state. This sequence forms a solution path. What is the best solution? Obviously the shortest path from the initial state to the goal state is the best one. Shortest path has only a few operations compared to all other possible solution paths. Solution path forms a tree structure where each node is a state. So searching is nothing but exploring the tree from the root node. 3.2.1 Search Problem We are now ready to formally describe a search problem. A search problem consists of the following:  S: the full set of states  s : the initial state 0  A:S→S is a set of operators  G is the set of final states. Note that G ⊆S These are schematically depicted in Figure 2. 27 CIT478 ARTIFICIAL INTELLIGENCE The search problem is to find a sequence of actions which transforms the agent from the initial state to a goal state g∈G. A search problem is represented by a 4-tuple {S, s , A, G}. 0 S: set of states s ∈ S: initial state 0 A: S? S operators/ actions that transform one state to another state G: goal, a set of states. G ⊆ S This sequence of actions is called a solution plan. It is a path from the initial state to a goal state. A plan P is a sequence of actions. P = {a , a , a } which leads to traversing a number of states {s , s , 0 1 N 0 1 Sn+ ∈G}. A sequence of states is called a path. The cost of a path is a 1 positive number. In many cases the path cost is computed by taking the sum of the costs of each action. Representation of search problems A search problem is represented using a directed graph.  The states are represented as nodes.  The allowed actions are represented as arcs. 28 CIT478 ARTIFICIAL INTELLIGENCE Searching process The generic searching process can be very simply described in terms of the following steps: Do until a solution is found or the state space is exhausted. 1. Check the current state 2. Execute allowable actions to find the successor states. 3. Pick one of the new states. 4. Check if the new state is a solution state If it is not, the new state becomes the current state and the process is repeated 3.3 Examples 3.3.1 Illustration of a search process We will now illustrate the searching process with the help of an example. Consider the problem depicted in Figure 3. s is the initial state. 0 The successor states are the adjacent states in the graph. 29 CIT478 ARTIFICIAL INTELLIGENCE There are three goal states. The two successor states of the initial state are generated. The successors of these states are picked and their successors are generated. 30 CIT478 ARTIFICIAL INTELLIGENCE Successors of all these states are generated. The successors are generated. A goal state has been found. The above example illustrates how we can start from a given state and follow the successors, and be able to find solution paths that lead to a goal state. The grey nodes define the search tree. Usually the search tree is extended one node at a time. The order in which the search tree is extended depends on the search strategy. 31 CIT478 ARTIFICIAL INTELLIGENCE We will now illustrate state space search with one more example – the pegs and disks problem. We will illustrate a solution sequence which when applied to the initial state takes us to a goal state. 3.3.2 Example problem: Pegs and Disks problem Consider the following problem. We have 3 pegs and 3 disks. Operators: one may move the topmost disk on any needle to the topmost position to any other needle. In the goal state all the pegs are in the needle B as shown in the figure below. The initial state is illustrated below. Now we will describe a sequence of actions that can be applied on the initial state. Step 1: Move A → C 32 CIT478 ARTIFICIAL INTELLIGENCE Step 2: Move A → B Step 3: Move A → C Step 4: Move B→ A 33 CIT478 ARTIFICIAL INTELLIGENCE Step 5: Move C → B Step 6: Move A → B Step 7: Move C→ B We will now look at another search problem – the 8-queens problem, which can be generalized to the N-queens problem. 3.3.3 Queens Problem The problem is to place 8 queens on a chessboard so that no two queens are in the same row, column or diagonal. The picture below on the left shows a solution of the 8-queens problem. The picture on the right is not a correct solution, because some of the queens are attacking each other. 34 CIT478 ARTIFICIAL INTELLIGENCE Figure 18: Queens Problem How do we formulate this in terms of a state space search problem? The problem formulation involves deciding the representation of the states, selecting the initial state representation, the description of the operators, and the successor states. We will now show that we can formulate the search problem in several different ways for this problem. N queens problem formulation 1  States: Any arrangement of 0 to 8 queens on the board  Initial state: 0 queens on the board  Successor function: Add a queen in any square  Goal test: 8 queens on the board, none are attacked The initial state has 64 successors. Each of the states at the next level has 63 successors, and so on. We can restrict the search tree somewhat by considering only those successors where no queen is attacking each other. To do that, we have to check the new queen against all existing queens on the board. The solutions are found at a depth of 8. 35 CIT478 ARTIFICIAL INTELLIGENCE N queens problem formulation 2  States: Any arrangement of 8 queens on the board  Initial state: All queens are at column 1  Successor function: Change the position of any one queen  Goal test: 8 queens on the board, none are attacked If we consider moving the queen at column 1, it may move to any of the seven remaining columns. N queens problem formulation 3 36 CIT478 ARTIFICIAL INTELLIGENCE  States: Any arrangement of k queens in the first k rows such that none are attacked  Initial state: 0 queens on the board  Successor function: Add a queen to the (k+1) th row so that none are attacked.  Goal test : 8 queens on the board, none are attacked We will now take up yet another search problem, the 8 puzzle. 3.3.4 Problem Definition - Example, 8 puzzle In the 8-puzzle problem we have a 3×3 square board and 8 numbered tiles. The board has one blank position. Bocks can be slid to adjacent blank positions. We can alternatively and equivalently look upon this as the movement of the blank position up, down, left or right. The objective of this puzzle is to move the tiles starting from an initial position and arrive at a given goal configuration. 37 CIT478 ARTIFICIAL INTELLIGENCE The 15-puzzle problems is similar to the 8-puzzle. It has a 4×4 square board and 15 numbered tiles The state space representation for this problem is summarized below: States: A state is a description of each of the eight tiles in each location that it can occupy. Operators/Action: The blank moves left, right, up or down Goal Test: The current state matches a certain state (e.g. one of the ones shown on previous slide) Path Cost: Each move of the blank costs 1 A small portion of the state space of 8-puzzle is shown below. Note that we do not need to generate all the states before the search begins. The states can be generated when required. 8-puzzle partial state space 3.4 Types of AI Search Techniques Solution can be found with less information or with more information. It all depends on the problem we need to solve. Usually when we have more information it will be easy to solve the problem. The following are the types of AI search namely: Uninformed Search, List search, Tree search , Graph search, SQL search, Tradeoff Based search, Informed search, Adversarial search. This module will only deal with uninformed search, informed search and Tree search. 38 CIT478 ARTIFICIAL INTELLIGENCE 4.0 CONCLUSION State space search is a process used in the field of computer science, including artificial intelligence (AI), in which successive configurations or states of an instance are considered, with the goal of finding a goal state with a desired property. Problems are often modelled as a state space, a set of states that a problem can be in. The set of states forms a graph where two states are connected if there is an operation that can be performed to transform the first state into the second. State space search often differs from traditional computer science search methods because the state space is implicit: the typical state space graph is much too large to generate and store in memory. Instead, nodes are generated as they are explored, and typically discarded thereafter. A solution to a combinatorial search instance may consist of the goal state itself, or of a path from some initial state to the goal state. 5.0 SUMMARY In this unit, you have learnt that:  State space search is a process used in the field of computer science, including artificial intelligence (AI), in which successive configurations or states of an instance are considered, with the goal of finding a goal state with a desired property  The search problem is to find a sequence of actions which transforms the agent from the initial state to a goal state g∈G. A search problem is represented by a 4-tuple {S, s , A, G}. 0  Solution can be found with less information or with more information. It all depends on the problem we need to solve 39 CIT478 ARTIFICIAL INTELLIGENCE 6.0 TUTOR-MARKED ASSIGNMENT 1. Find a path from a boxed node to the goal node (p). 2. Using the following AND/OR graph, where is fred? 7.0 REFERENCES/FURTHER READING Dechter, R. & Judea, P. (1985). "Generalized Best-First Search Strategies and the Optimality of A*". Journal of the ACM 32 (3): 505–536. doi:10.1145/3828.3830. Koenig, S.; Maxim, L.; Yaxin, L.; David, F. (2004). "Incremental Heuristic Search in AI". AI Magazine 25 (2): 99–112. http://portal.acm.org/citation.cfm?id=1017140. Nilsson, N. J. (1980). Principles of Artificial Intelligence. Palo Alto, California: Tioga Publishing Company. ISBN 0-935382-01-1. Pearl, J. (1984). Heuristics: Intelligent Search Strategies for Computer Problem Solving. Addison-Wesley Longman Publishing Co., Inc. ISBN 0-201-05594-5. 40 CIT478 ARTIFICIAL INTELLIGENCE Russell, S. J. & Norvig, P. (2003). Artificial Intelligence. A Modern Approach. Upper Saddle River, N.J.: Prentice Hall. pp. 97–104. ISBN 0-13-790395-2. 41 CIT478 ARTIFICIAL INTELLIGENCE UNIT 2 UNINFORMED SEARCH OR BRUTE FORCE SEARCH CONTENTS 1.0 Introduction 2.0 Objectives 3.0 Main Content 3.1 Uninformed Search 3.2 Depth First and Breadth First Search 3.2.1 Depth First Search 3.2.2 Breadth First Search 4.0 Conclusion 5.0 Summary 6.0 Tutor-Marked Assignment 7.0 References/Further Reading 1.0 INTRODUCTION In computer science, uninform-cost search (UCS) is a tree search algorithm used for traversing or searching a weighted tree, tree structure, or graph. The search begins at the root node. The search continues by visiting the next node which has the least total cost from the root. Nodes are visited in this manner until a goal state is reached. Typically, the search algorithm involves expanding nodes by adding all unexpanded neighbouring nodes that are connected by directed paths to a priority queue. In the queue, each node is associated with its total path cost from the root, where the least-cost paths are given highest priority. The node at the head of the queue is subsequently expanded, adding the next set of connected nodes with the total path cost from the root to the respective node. The uniform-cost search is complete and optimal if the cost of each step exceeds some positive bound ε. 2.0 OBJECTIVES At the end of this unit, you should be able to:  explain uninformed search  list two types of uninformed search  describe depth first and breadth first search  solve simple problems on uninformed search. 42 CIT478 ARTIFICIAL INTELLIGENCE 3.0 MAIN CONTENT 3.1 Uninformed Search Sometimes we may not get much relevant information to solve a problem. Suppose we lost our car key and we are not able to recall where we left, we have to search for the key with some information such as in which places we used to place it. It may be our pant pocket or may be the table drawer. If it is not there then we have to search the whole house to get it. The best solution would be to search in the places from the table to the wardrobe. Here we need to search blindly with fewer clues. This type of search is called uninformed search or blind search. There are two popular AI search techniques in this category: breadth first search and depth first search. 3.2 Depth First and Breadth First Search If you want to go from Point A to Point B, you are employing some kind of search. For a direction finder, going from Point A to Point B literally means finding a path between where you are now and your intended destination. For a chess game, Point A to Point B might be two points between its current position and its position 5 moves from now. For a genome sequence, Points A and B could be a link between two DNA sequences. As you can tell, going from Point A to Point B is different for every situation. If there is a vast amount of interconnected data, and you are trying to find a relation between few such pieces of data, you would use search. In this unit, you will learn about two forms of searching, depth first and breadth first. Our Search Representation Lets you learn how we humans could solve a search problem. First, we need a representation of how our search problem will exist. The following is an example of our search tree. It is a series of interconnected nodes that we will be searching through: 43 CIT478 ARTIFICIAL INTELLIGENCE In our above graph, the path connections are not two-way. All paths go only from top to bottom. In other words, A has a path to B and C, but B and C do not have a path to A. It is basically like a one-way street. Each lettered circle in our graph is a node. A node can be connected to other via our edge/path, and those nodes that are connected to be called neighbors. B and C are neighbors of A. E and D are neighbors of B, and B is not a neighbor of D or E because B cannot be reached using either D or E. Our search graph also contains depth: We now have a way of describing location in our graph. We know how the various nodes (the lettered circles) are related to each other 44 CIT478 ARTIFICIAL INTELLIGENCE (neighbors), and we have a way of characterizing the depth each belongs in. Knowing this information isn't directly relevant in creating our search algorithm, but they do help us to better understand the problem. 3.2.1 Depth First Search Depth first search works by taking a node, checking its neighbors, expanding the first node it finds among the neighbors, checking if that expanded node is our destination, and if not, continue exploring more nodes. The above explanation is probably confusing if this is your first exposure to depth first search. I hope the following demonstration will help you more. Using our same search tree, let's find a path between nodes A and F: Step 0 let‘s start with our root/goal node: I will be using two lists to keep track of what we are doing - an Open list and a Closed List. An Open list keeps track of what you need to do, and the Closed List keeps track of what you have already done. Right now, we only have our starting point, node A. We haven't done anything to it yet, so let's add it to our Open list. 45 CIT478 ARTIFICIAL INTELLIGENCE  Open List: A  Closed List: Step 1 Now, let's explore the neighbors of our A node. To put another way, let's take the first item from our Open list and explore its neighbors: Node A's neighbors are the B and C nodes. Because we are now done with our A node, we can remove it from our Open list and add it to our Closed List. You aren't done with this step though. You now have two new nodes B and C that need exploring. Add those two nodes to our Open list. Our current Open and Closed Lists contain the following data:  Open List: B, C  Closed List: A Step 2 Our Open list contains two items. For depth first search and breadth first search, you always explore the first item from our Open list. The first item in our Open list is the B node. B is not our destination, so let's explore its neighbors: Because I have now expanded B, I am going to remove it from the Open list and add it to the Closed List. Our new nodes are D and E, and we add these nodes to the beginning of our Open list:  Open List: D, E, C  Closed List: A, B Step 3 46 CIT478 ARTIFICIAL INTELLIGENCE You should start to see a pattern forming. Because D is at the beginning of our Open List, we expand it. D isn't our destination, and it does not contain any neighbors. All you do in this step is remove D from our Open List and add it to our Closed List:  Open List: E, C  Closed List: A, B, D Step 4 We now expand the E node from our Open l

CIT 478 Artificial Intelligence Course Guide PDF

Document Details

Tags

Related

Summary

Full Transcript

Upgrade to continue