Introduction to Artificial Intelligence: cs580Dr. Zoran DuricOffice: Nguyen Engineering Building 4443email: [email protected] Hours: Mon. & Tue. 3:00-4:00pm, or by app.URL: http://www.cs.gmu.edu/∼zduric/Course: http://www.cs.gmu.edu/∼zduric/cs580.htmlAugust 28, 2012Dr. Zoran Duric Introduction to Artificial Intelligence: cs580OutlineICourse overviewIWhat is AI?IA brief historyIThe state of the artDr. Zoran Duric Introduction to Artificial Intelligence: cs580Course overviewIlispIintelligent agentsIsearch and game-playingIlogical systemsIlearningIlanguageIperceptionIroboticsIphilosophical issuesDr. Zoran Duric Introduction to Artificial Intelligence: cs580What is AI?“[The automation of] activi-ties that we associate with hu-man thinking, activities such asdecision-making, problem solving,learning . . .” (Bellman, 1978)“The study of mental facultiesthrough the use of computationalmodels” (Charniak+McDermott,1985)“The study of how to make com-puters do things at which, atthe moment, people are better”(Rich+Knight, 1991)“The branch of computer sciencethat is concerned with the au-tomation of intelligent behavior”(Luger+Stubblefield, 1993)Views of AI fall into four categories:Thinking humanly Thinking rationallyActing humanly Acting rationallyExamining these, we will plump for acting rationally (sort of)Dr. Zoran Duric Introduction to Artificial Intelligence: cs580Acting humanly: The Turing testTuring (1950) “Computing machinery and intelligence”:♦ “Can machines think?” → “Can machines behaveintelligently?”♦ Operational test for intelligent behavior: the Imitation Game♦ Predicted that by 2000, a machine might have a 30% chance offooling a lay person for 5 minutes♦ Anticipated all major arguments against AI in following 50 years♦ Suggested major components of AI: knowledge, reasoning,language understanding, learningProblem: Turing test is not reproducible, constructive, oramenable to mathematical analysisDr. Zoran Duric Introduction to Artificial Intelligence: cs580Thinking humanly: Cognitive Science1960s “cognitive revolution”: information-processing psychologyreplaced prevailing orthodoxy of behaviorismRequires scientific theories of internal activities of the brainIWhat level of abstraction? “Knowledge” or “circuits”?IHow to validate? Requires1) Predicting and testing behavior of human subjects (top-down)or2) Direct identification from neurological data (bottom-up)Both approaches (roughly, Cognitive Science and CognitiveNeuroscience) are now distinct from AIDr. Zoran Duric Introduction to Artificial Intelligence: cs580Thinking rationally: Laws of ThoughtNormative (or prescriptive) rather than descriptiveAristotle: what are correct arguments/thought processes?Several Greek schools developed various forms of logic:notation and rules of derivation for thoughts; may or may nothave proceeded to the idea of mechanizationDirect line through mathematics and philosophy to modern AIProblems:1) Not all intelligent behavior is mediated by logical deliberation2) What is the purpose of thinking? What thoughts should Ihave?Dr. Zoran Duric Introduction to Artificial Intelligence: cs580Acting rationallyRational behavior: doing the right thingThe right thing: that which is expected to maximize goalachievement, given the available informationDoesn’t necessarily involve thinking—e.g., blinking reflex—butthinking should be in the service of rational actionAristotle (Nicomachean Ethics):Every art and every inquiry, and similarly every action andpursuit, is thought to aim at some goodDr. Zoran Duric Introduction to Artificial Intelligence: cs580Rational agentsAn agent is an entity that perceives and actsThis course is about designing rational agentsAbstractly, an agent is a function from percept histories toactions:f : P∗→ AFor any given class of environments and tasks, we seek theagent (or class of agents) with the best performanceCaveat: computational limitations make perfect rationalityunachievable → design best program for given machineresourcesDr. Zoran Duric Introduction to Artificial Intelligence: cs580AI prehistoryPhilosophy logic, methods of reasoning, mind as physical systemfoundations of learning, language, rationalityMathematics formal representation and proof, algorithmscomputation, (un)decidability, (in)tractabilityprobabilityPsychology adaptation, phenomena of perception andmotor control, experimental techniques(psychophysics, etc.)Linguistics knowledge representation, grammarNeuroscience physical substrate for mental activityControl theory homeostatic systems, stabilitysimple optimal agent designsDr. Zoran Duric Introduction to Artificial Intelligence: cs580Potted history of AI1943 McCulloch & Pitts: Boolean circuit model of brain1950 Turing’s “Computing Machinery and Intelligence”1952–69 Look, Ma, no hands!1950s Early AI programs, including Samuel’s checkers program,Newell & Simon’s Logic Theorist,Gelernter’s Geometry Engine1956 Dartmouth meeting: “Artificial Intelligence” adopted1965 Robinson’s complete algorithm for logical reasoning1966–74 AI discovers computational complexityNeural network research almost disappears1969–79 Early development of knowledge-based systemsDr. Zoran Duric Introduction to Artificial Intelligence: cs580Potted history of AI1980–88 Expert systems industry booms1988–93 Expert systems industry busts: “AI Winter”1985–95 Neural networks return to popularity1988– Resurgence of probabilistic and decision-theoreticmethodsRapid increase in technical depth of mainstream AI“Nouvelle AI”: ALife, GAs, soft computingDr. Zoran Duric Introduction to Artificial Intelligence: cs580State of the artWhich of the following can be done at present?♦ Play a decent game of table tennis♦ Drive along a curving mountain road♦ Drive in the center of Cairo♦ Play a decent game of bridge♦ Discover and prove a new mathematical theorem♦ Write an intentionally funny story♦ Give competent legal advice in a specialized area of law♦ Translate spoken English into spoken Swedish in real timeDr. Zoran Duric Introduction to Artificial Intelligence: