CS 475: Uncertainty and Multi-Agent Systems Prof. Bart Selman

CS 475: Uncertainty and Multi-Agent Systems Prof. Bart Selman [email protected] Introduction 1 Bart Selman CS 475

Overview of this Lecture Motivation behind new course Course administration Role of uncertainty and multi-agent systems in AI 2 Bart Selman CS 475

Motivation 3 Bart Selman CS 475

A new course The field of AI has grown tremendously over the last two decades, both in terms of range of topics and technical depth. A single introductory course no longer works. So, this course complements CS 472. CS 472: Search, Adversarial Search, Planning, Knowledge Represention and Reasoning, and Learning. (Parts I, II, III, IV, & VI R&N.) CS 475: Uncertainty (Part V, R&N) and Multi-Agent Systems (t.b.d.) 4 Bart Selman CS 475

Course Administration 5 Bart Selman CS 475

CS 475 Lectures: Wedns & Fridays – 2:55pm – 4:10pm Location: OH 216 Lecturer: Prof. Selman Office: 4148 Upson Hall Email: [email protected] Administrative Assistant: Beth Howard ([email protected]) 5136 Upson Hall, 255-4188 6 Bart Selman CS 475

Grading (tentative) Midterm (15%) Homework (40%) Participation (10%) Final (35%) Note: The lowest homework grade will be dropped before the final grade is computed. 7 Bart Selman CS 475

Textbook Artificial Intelligence: A Modern Approach (AIMA) (Second Edition) by Stuart Russell and Peter Norvig Probabilistic Reasoning in Intelligent Systems : Networks of Plausible Inference by Judea Pearl Learning Bayesian Networks by Richard Neapolitan Multi-Agent Systems: A Modern Approach to Distributed AI by Gerhard Weiss Bart Selman CS 475 8

Emergence of Uncertainty in AI Historical Perspective AI: Obtaining an understanding of the human mind is one of the final frontiers of modern science. Founders: Aristotle, George Boole, Gottlob Frege, and Alfred Tarski formalizing the laws of human thought Alan Turing, John von Neumann, and Claude Shannon thinking as computation John McCarthy, Marvin Minsky, Herbert Simon, and Allen Newell the start of the field of AI (1959) 9 Bart Selman CS 475

1959 – 1985 Logical representations and symbolic processing were at the core of AI. Precise. Models much of mathematical thought. Also, human artifacts such as circuits and complex machinery. Well-understood syntax and semantics. Computational principles well-understood (inference). Moreover: “symbolic processing and representations” were actually novel for computing. Handcrafted knowledge works well in specialized domains in e.g. expert systems and automated diagnosis systems. “knowledge driven” [Aside: probabilistic methods, such as Markov models, were quite familiar in the 50s and 60s from work in EE on information and signal processing.] 10 Bart Selman CS 475

1985 – 2005 emergence of probabilistic and statistical methods in AI. Can deal with noisy input (sensor) data, and many forms of uncertain information. Can exploit statistical regularities in large data-sets, leading to statistical machine learning (less need for hand-crafted encoding of knowledge). Computational techniques were developed. Probabilistic framework (e.g. Bayesian nets, Markov random fields) bridge different areas such as reasoning, nlp, vision, machine learning, and bio-info. “data-driven” [Aside: value of probabilistic models was also discovered “later” in the other fields --- e.g. statistical physics (1870 ) & quantum physics (1910 ) and in computation (randomized algorithms 1970 ).] 11 Bart Selman CS 475

2006 ? Possibly a merger of probabilistic information (“soft constraints / preferences”) and logical information (“hard constraints”). Consider a robot moving around: a probabilistic (continuous) model of its most likely location seems appropriate given noisy sensory inputs. However, in reasoning and making plans about its environment an appropriate discretization may be needed (e.g. “door is either closed or open”; “words” in language; component-wise designs). “Hierarchical models: lower-level statistical (from sensory input) & higherlevels symbolic (from cognition).” 12 Bart Selman CS 475

Emergence of Multi-Agent Systems 1959—1985 Mostly single agent, problem solving / task-oriented perspective Examples: medical diagnosis systems or Deep Blue. 1985---2005 Shift to autonomous, interacting AI systems (“agents”). Examples: shopping and bidding “agents” (e.g., TAC competition) and distributed sensor networks. Brings in ideas from economics, game theory, auctions, coordination, and distributed computing. Open issue: do truly new aspects of intelligence “emerge” in a distributed setting? 13 Bart Selman CS 475

14 Bart Selman CS 475