CS 121

CS 121

INTRODUCTION TO ARTIFICIAL INTELLIGENCE

Three units, Winter Quarter 1999

Class Information and Syllabus (DRAFT of 12/23/98)

Handout #1

Lecture: 3 units, TTh 11:00-12:15 PM, SEQ-TC201

Problem session: 0 units, Place and Time to be announced

Course web page: http://www-leland.stanford.edu/class/cs121

Instructor:

Nils J. Nilsson

Office: Gates 135

Phone: 650-723-3886

Email: nilsson@cs.stanford.edu

Web page: http://robotics.stanford.edu/users/nilsson/bio.html

Office Hours: Thursdays, 1-3 p.m.

Course Secretary:

Mina Madrigal-Torres

Office: Gates 146

Phone: 650-723-4137

Email: mina@cs.stanford.edu

Teaching Assistants:

Samar Mehta

Phone: 650-497-9589

Email: samar@leland.Stanford.EDU

Office Hours: to be announced

Mala Ramakrishnan

Phone: 650-497-9145

Email: malar@leland.Stanford.EDU

Kin Lun Law

Phone: 650-497-5581

Email: kenlaw@leland.stanford.edu

Office Hours: to be announced

(Use cs121help@cs.stanford.edu to e-mail the instructor and the TAs as a group.)

COURSE INFORMATION

OBJECTIVE:

To introduce students to the history and literature, the fundamental concepts and ideas, and the applications and techniques of artificial intelligence (AI).

DESCRIPTION:

The course begins with rather elementary reactive systems and progresses through a sequence of increasingly complex (intelligent?) artificial "agents." Topics surveyed as the sequence unfolds include: reactive systems, neural networks, computer vision, search, logic, knowledge representation and reasoning, expert systems, automatic planning, and agent communication.

PREREQUISITES:

Fundamental knowledge of computer science as covered in CS 109. Ability to write computer programs and facility with differential calculus, vector algebra, and probability theory will be assumed.

INTENDED AUDIENCE:

Undergraduate or Masters students specializing in computer science, symbolic systems, computer systems engineering, and other technical subjects. Those students who intend to take additional courses in AI should instead take the more advanced course, CS221

(http://www-leland.stanford.edu/class/cs221).

TEXTBOOK:

Artificial Intelligence: A New Synthesis, by Nils J. Nilsson, Morgan Kaufmann Publishers, Inc., 1998. (Some material will be presented in class that is not covered in the textbook.)

See http://www.mkp.com/books_catalog/1-55860-467-7.asp for updated information about the text, including pointers to pages with clarifications and errata.

HARDWARE/SOFTWARE REQUIREMENTS:

Students may use their own computers or their Stanford Leland accounts. Network and Web access will be required.

INSTRUCTOR BIO:

Nilsson teaches and writes about artificial intelligence and autonomous agents such as mobile robots. He is interested in robots that can function in complex environments with minimal human management---requiring them to be able to perceive, react, plan, and learn.

CLASS WORK AND GRADES:

The course will have four homework assignments (some with computational components) and open-book midterm and final exams. Students will be responsible for material covered in the lectures and for corresponding material assigned in the readings. The lectures will amplify and illustrate important topics and will be organized under the assumption that students will have read the readings before each lecture.

Homework will be due at the beginning of class on the dates assigned. Submission, grading, and return of all work will be timely, and solutions to homework problems will be handed out during the class following the due date. To accommodate possible emergencies, we will allow students to throw out their lowest homework score. Please take extra care to make sure that all work is legible; illegible work will be returned ungraded.

Please note the time for the final exam (at the end of this handout) and do not register for this class if you cannot attend the final at that time! We cannot arrange alternative times for the final exam.

Students are encouraged to discuss homework problems with each other in a general way, but all actual, detailed problem solutions must be individual work. Computer exercises can be done and handed in as team work. (Each member of a team will receive the same "team grade.")

Course grades will be based fifty percent on the homework, twenty percent on the mid-term, and thirty percent on the final exam. The course may be taken Pass/No Credit if desired.

Copies of in-class hand-outs, such as homework assignments and solutions, will be posted on the class web page, and hard copies will also be available in the "handout hangout" in Gates 1B.

Class announcements, corrections to the textbook and other information will be regularly posted to the newsgroup.

Students are encouraged to attend the weekly problem sessions and to attend office hours. We have only limited ability to answer questions via e-mail, and students should not assume that e-mail questions will be answered. However, your e-mail comments and suggestions about the course, including advice about textbook and/or lectures are encouraged (cs121help@cs.stanford.edu).

CS 121 CLASS SCHEDULE

(Tentative and subject to revision; readings refer to Nilsson's book)

Tue, 1/5 Course Overview; Introduction

Readings: Chapter 1

Topics: course mechanics and goals, the nature of intelligence, brief history of AI, approaches to AI, overview of course

Web Sites:

New York Times articles on computing and AI

http://www-rci.rutgers.edu/~cfs/472_html/Intro/NYT_Intro/History/WritingThatDefined.html

Overview (including history of the field)

http://tqd.advanced.org/2705/

Alan Turing’s 1950 paper on computers and intelligence and on the Turing test

http://www.sscf.ucsb.edu/~sung/comm115/writing-define-computing/Computing-machinery.html

The Alan Turing "Home Page"

http://www.wadham.ox.ac.uk/~ahodges/Turing.html

Thurs, 1/7 Reactive Agents

Readings: Chapters 2 and 5 (except for Section 5.2)

Topics: perception and action, production rules, T-R programs and circuits, emergent behavior

Web Sites:

Teleo-Reactive Robot Control

http://www.cim.mcgill.ca/~zelek/spott.htm

Subsumption Architectures

http://krusty.eecs.umich.edu/cogarch2/specific/subsumption.html

Tue, 1/12 and Thurs, 1/14 Neural Networks and Machine Learning

Readings: reread pp. 29-32 (Section 2.2.2 in Chapter 2), then read pp. 37-45 and pp. 51-55 (Sections 3.1, 3.2, 3.3.1 in Chapter 3) and pp. 87-88 (Section 6.2 in Chapter 6)

Topics: TLUs, perceptrons, supervised learning methods, generalization/accuracy/overfitting, accuracy estimation, pattern recognition and control applications, ALVINN

Web Sites:

ALVINN

http://www.cs.cmu.edu/afs/cs.cmu.edu/project/alv/member/www/projects/ALVINN.html

Neural Nets Frequently Asked Questions

ftp://ftp.sas.com/pub/neural/FAQ.html

Yahoo! Listings for neural nets

http://www.yahoo.com/Science/Engineering/Electrical_Engineering/Neural_Networks/

Tue, 1/19 Robot Vision

Readings: Chapter 6

HW 1 due at beginning of class!

Topics: purpose of perception (to produce models or to extract features), inverting a physical process (image example, speech example), extra knowledge needed, objects and discontinuities, convolution and the Marr-Hildreth operator,

scene knowledge (general to specific), models

Web Sites:

Computer Vision Online Demos

http://www.cs.cmu.edu/afs/cs/project/cil/ftp/html/v-demos.html

Computer Vision Homepage

http://www.cs.cmu.edu/afs/cs/project/cil/ftp/html/vision.html

See the world through the eyes of a bee

http://cvs.anu.edu.au/andy/beye/beyehome.html

Thurs, 1/21 and Tues, 1/26 Agents that Anticipate; Uninformed Search

Readings: Chapters 7 and 8, pp. 163-165 (Section 10.1 in Chapter 10)

Topics: models of actions, explicit graphs, marker

propagation, implicit graphs, start node/operators/goal, depth-first and iterative

deepening, robotic planning, search and action in the real world, sense-plan-act cycle

Web Sites:

Charles Schmidt’s animation of breadth-first, depth-first, and hill-climbing search

http://www-rci.rutgers.edu/~cfs/472_html/AI_SEARCH/SearchAnimations.html

Thurs, 1/28 Heuristic Search

Readings: Chapter 9

Topics: evaluation functions, A* for trees, admissibility and optimality, route-finding in a map

Web Sites:

http://www.mapblast.com/mapblast/start.hm

Tues, 2/2 Adversarial Search

Readings: pp. 195-208 (Sections 12.1 through 12.5 in Chapter 12)

HW 2 due at beginning of class!

Topics: minimax, alpha-beta, Deep Blue

Web Sites:

Deep Blue (Chess)

http://www.chess.ibm.com/

Chinook (Checkers)

http://web.cs.ualberta.ca:80/~chinook/

Thurs, 2/4 Reinforcement Learning

Readings: pp. 175-177 (Section 10.4 in Chapter 10), pp. 210-212 (Section 12.7 in Chapter 12)

Topics: Value iteration, Q-learning, TD-Gammon

Web Sites:

Sridhar Mahadevan’s reinforcement learning repository

http://www.cse.msu.edu/rlr/

TD-Gammon paper by Gerry Tesauro

http://www.research.ibm.com/massdist/tdl.html

Tues, 2/9 Midterm Examination (Open Book)

Thurs, 2/11 Alternative Search Formulations and Applications

Readings: Chapter 11

Topics: constructive methods, heuristic repair, hill climbing, simulated annealing, CSPs and constraint satisfaction problems

Web Sites:

University of New Hampshire’s archive of constraint satisfaction problems and related materials

http://www.cs.unh.edu/ccc/archive/

Tues, 2/16 and Thurs, 2/18 Knowledge Representation and Reasoning: The Propositional Calculus

Readings: Chapter 13, pp. 237-238 (Section 14.5 in Chapter 14), pp. 280-286 (Section 17.4 in Chapter 17)

Topics: constraints on features, propositional calculus, forward reasoning, backward reasoning, expert systems, SAT

Web Sites:

Tues, 2/23 Elementary First-order Calculus

Readings: Chapters 15 and 18

HW 3 due at beginning of class!

Topics: predicates and arguments, commonsense knowledge, semantic networks, frames, CYC

Web Sites:

Cycorp’s homepage and pointers to CYC

http://www.cyc.com/index.html

The CLASSIC knowledge representation system

http://www-db.research.bell-labs.com/user/pfps/classic/classic.html

Mathematical Theorem Proving (Robbins Algebra) using a Logic System

http://www-unix.mcs.anl.gov/~mccune/papers/robbins/

http://www.cyc.com/tech.html

Thurs, 2/25 Reasoning with Uncertain Information

Readings: pp. 317-330 (Sections 19.1 through 19.5 in Chapter 19)

Topics: Bayes’ Rule, probabilistic inference, conditional independence,

Bayes networks, patterns of inference

Web Sites:

Large set of links to belief network software

http://bayes.stat.washington.edu/almond/belief.html

Microsoft Belief Network Tools
http://www.research.microsoft.com/msbn/

Tues, 3/2 Planning

Readings: pp. 373-385 and pp. 393-395 (Sections 22.1 and 22,3 in Chapter 22)

Topics: STRIPS rules, recursive STRIPS, hierarchical planning, SATPLAN, scheduling

Web Sites:

Charles Schmidt’s discussion of STRIPS

http://www-rci.rutgers.edu/~cfs/472_html/Planning/STRIPS_472.html

GRAPHPLAN homepage

http://almond.srv.cs.cmu.edu/afs/cs.cmu.edu/usr/avrim/www/graphplan.html

Thurs, 3/4 Communicating Agents

Readings: pp. 425-440 (Sections 24.2 through 24.4 in Chapter 24)

Topics: parsing, semantic analysis, difficulties of understanding NL

Web Sites:

Tues, 3/9 Open for catch-up

HW 4 due at beginning of class!
Thurs, 3/11 (last class) Agent Architectures and Wrap-Up

Readings: Chapter 25

Topics: three-level architecture, arbitration architecture, triple tower,

prospects for AI

Web Sites:

Robot Soccer:

http://www.cs.cmu.edu/~robosoccer/

http://www.robocup.v.kinotrope.co.jp/02.html

Thurs, 3/18, 7-10 p.m Final Examination (Open Book)

Some Additional Web Sites

The following web site is highly recommended! It has a large number of links to AI people, programs, papers, and other material. It was compiled by Professor Stuart Russell of U.C. Berkeley and is organized to parallel the book entitled Artificial Intelligence: A Modern Approach, which he co-authored with Peter Norvig.

http://www.cs.berkeley.edu/~russell/ai.html

Frequently asked questions (FAQs) about AI:

http://www.cs.cmu.edu/Groups/AI/html/faqs/ai/ai_general/top.html

Links to various AI Resources:

http://ai.iit.nrc.ca/ai_point.html

The home page for the American Association for Artificial Intelligence:

http://www.aaai.org/

AI Education Repository

http://www.cacs.usl.edu/~manaris/ai-education-repository/

Interesting AI Demos and Projects:

http://www.cs.wisc.edu/~dyer/cs540/demos.html

The home page for the journal Artificial Intelligence