Return-Path: <@cs.cmu.edu:ginsberg%CS.Stanford.EDU@t.stanford.edu>
Received: from cs.cmu.edu by A.GP.CS.CMU.EDU id ac01137; 16 Sep 92 1:01:10 EDT
Received: from t.stanford.edu by CS.CMU.EDU id aa13432; 15 Sep 92 19:39:47 EDT
Received:  by T.Stanford.EDU (4.1/25-T-eef) id AA00290; Tue, 15 Sep 92 16:38:59 PDT
Date: Tue, 15 Sep 92 16:38:59 PDT
From: Matthew L. Ginsberg <ginsberg@CS.Stanford.EDU>
Message-Id: <9209152338.AA00290@T.Stanford.EDU>
To: mkant@cs.cmu.edu
Subject: Re: comments on AI FAQ

Here's a somewhat dated version of the Stanford reading list.  If
something more recent shows up, I'll pass it along.

						Matt

From @Sunburn.Stanford.EDU:geddis@Meta.Stanford.EDU Mon Sep 14 14:52:39 1992
Return-Path: <@Sunburn.Stanford.EDU:geddis@Meta.Stanford.EDU>
Received: from Sunburn.Stanford.EDU by T.Stanford.EDU (4.1/25-T-eef) id AA00817; Mon, 14 Sep 92 14:52:37 PDT
Received: from Meta.Stanford.EDU by Sunburn.Stanford.EDU with SMTP (5.61+IDA/25-eef) id AA29829; Mon, 14 Sep 92 14:52:33 -0700
Received:  by Meta.Stanford.EDU (4.1/25-eef) id AA16200; Mon, 14 Sep 92 14:53:19 PDT
From: Don Geddis <geddis@meta.stanford.edu>
Message-Id: <9209142153.AA16200@Meta.Stanford.EDU>
Subject: Re: stanford AI qual list
To: ginsberg@cs.stanford.edu (Matthew L. Ginsberg)
Date: Mon, 14 Sep 92 14:53:19 PDT
In-Reply-To: <9209142145.AA00814@T.Stanford.EDU>; from "Matthew L. Ginsberg" at Sep 14, 92 2:45 pm
Reply-To: Geddis@cs.stanford.edu
X-Mailer: ELM [version 2.3 PL11]
Status: RO

> Is this on line somewhere?

I've got a really old copy from years ago.  Don't know if it's changed
much since then.  "bureaucrats@cs" might have a better idea.  I looked
around in Xenon:/cs/public, where such a thing might be kept, and didn't
find anything.

In any case, my old copy follows...

	-- Don
-- 
Don Geddis (Geddis@CS.Stanford.Edu)
You know what would make a good story?  Something about a clown who makes
people happy, but inside he's real sad.  Also, he has severe diarrhea.
	--  Deep Thoughts by Jack Handey [SNL]
----------
16-Nov-88 17:09:37-PST,18594;000000000001
Mail-From: MYERS created at 16-Nov-88 17:09:29
Date: Wed 16 Nov 88 17:09:28-PST
From: Karen L. Myers <MYERS@Score.Stanford.EDU>
Subject: New and Improved AI Qual Reading List
To: Qual-List: ;
Message-ID: <12447134053.29.MYERS@Score.Stanford.EDU>




Hi,

	I sent out a copy of this message a while ago;  apprently a
large number of people on the mailing list didn't receive it.  My
apologies to those of you who are receiving it again!

	As you may or not know, Ramin, Devika and I have been working
on revising the AI Qual reading list.  We've got a draft prepared, and
we would greatly appreciate receiving comments on it. We are
interested in hearing about areas that have been overlooked or
outstanding references that should be included.  However,  the list is
already fairly long.  As a result,  we're *extremely* interested in
paring down the list.  Feel free to point out redundancies as well as
references that you feel are of little value.

	What follows is the Latex version of the current draft.  We're
under a bit of time pressure to get a draft to the faculty, so we'd
appreciate hearing from you soon (by Monday if possible).  Please
forward your comments to rdz@score, subramanian@score and myers@score.  Thanks!

Karen, Devika and Ramin

% -*- Mode: Latex -*-
\documentstyle[11pt]{article}
\font\sc=cmcsc10
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%
%%%%%%      Bigger margins produced by this 
\setlength{\textwidth}{6in}                                
\setlength{\textheight}{8in}                               
\setlength{\topmargin}{0pt}                          
\setlength{\oddsidemargin}{0pt}                          
\setlength{\parskip}{\smallskipamount}
\setlength{\evensidemargin}{0pt}                         
\setlength{\headheight}{0pt}                             
\setlength{\headsep}{0pt}    
%%% today macro from letterhead
\def\today{\ifcase\month\or
  January\or February\or March\or April\or May\or June\or
  July\or August\or September\or October\or November\or December\fi
  \space\number\day, \number\year}

\newenvironment{required}%
{\begin{itemize}\renewcommand{\labelitemi}{$\bullet$}}%
{\end{itemize}}

\newcommand{\paper}{\item}

\newenvironment{optional}%
{\begin{itemize}\renewcommand{\labelitemi}{$\circ$}}%
{\end{itemize}}

\hyphenation{Leves-que}


\title{AI Qual Reading List} 
\author{Karen Myers\\
        Devika Subramanian\\
        Ramin Zabih} % I hate alphabetical order...

\date{Draft of \today}

\begin{document}

\maketitle


\section*{Overview}

This is the current draft of the reading list for the Stanford
Qualifying examination in Artificial Intelligence.  The list is
currently undergoing revisions, and we would be most grateful for
comments.  The authors can be reached electronically as {\sc
myers@score}, {\sc subramanian@score} and {\sc rdz@score}.

\subsection*{Conventions}

The reading list is divided into~\ref{sec:last} sections.  Each
section contains a list of required papers, which contain the basic
material in the area which an AI grad student ought to know.  The
required papers appear first, and are annotated with a bullet
($\bullet$).  In addition, we have included a list of optional papers
($\circ$) which we feel are also worth reading.

The following abbreviations appear throughout the readings.
\begin{itemize}

\item[{\bf AIJ}] {\em Artificial Intelligence}.  The journal of record
in the field.

\item[{\bf ARCS}] {\em Annual Review of Computer Science}.  A yearly
collection of articles.

\item[{\bf WN}]  {\em Readings in Artificial Intelligence}, edited by
Bonnie Weber and Nils Nilsson.  The blue book of collected readings.

\item[{\bf BL}] {\em Readings in Knowledge Representation}, edited by
Ronald Brachman and Hector Levesque.  The red book of collected
readings.

\item[{\bf G}] {\em Readings in Non-Monotonic Reasoning}, edited
by Matt Ginsberg. The aquamarine book of collected readings.

\item[{\bf EAI}] {\em Exploring Artificial Intelligence}, edited
by Howie Schrobe. The AAAI-87 survey talks.

\item[{\bf AIE}] {\em The AI Encyclopedia}, edited by Stuart C.
Shapiro. A 2 volume collection.

\end{itemize}
In addition, the following books are relied on heavily.
\begin{itemize}

\item[] {\em Artificial Intelligence}, Patrick Winston, 2nd edition.

\item[] {\em Handbook of Artificial Intelligence}, Barr and Feigenbaum
(editors). 

%\item[] {\em Encylopedia of Artificial Intelligence}, Stuart Shapiro
%(editor). 

\item[] {\em Logical Foundations of Artificial Intelligence},
Genesereth and Nilsson, 1987.

\end{itemize}


\section{Search}
\label{sec:search}

\begin{required}

\paper Pearl and Korf, Search techniques.  ARCS 1987. The best current
survey of results.

\paper Winston, Artificial Intelligence, (2nd edition).  Chapter 4,
search methods (this has lots of good examples).  Chapter 3 pp 79-84
(on dependency-directed backtracking).

\paper Nilsson, Principles of Artificial Intelligence.  Sections
2.4.1--2.4.4 (on A*).  Sections 3.1 and 3.2 (on AND/OR trees and AO*),
and Sections

\paper Mackworth, Consistency in networks of relations.  Sections
1--6, the rest is optional. WN collection.

\end{required}

\begin{optional}

\paper   Berliner, The B* tree search algorithm: a best-first proof
     procedure.  WN collection.  Read about the two bounds and how
     they're used.

\end{optional}

\section{Representation}
\label{sec:representation}

\begin{required}

  \paper AI handbook Vol. 1 Chapter 3, read sections A, B, C.2, C.5,
and pages 170--171 (on the benefits of logical representation).  An
overview of the basic formalisms.

\paper Rich, {\em Artificial Intelligence}, section 7.2.  Basic declarative
formalisms.

  \paper Ch 1,2 Genesereth/Nilsson.  The declarativist approach and
the fundamentals of logic.

  \paper  Artificial Intelligence, Winston (pg. 21-24, 41-42)
     Desiderata for good representations.

  \paper  An overview of production systems, Davis and King (MYCIN book, Ch. 4)

  \paper Knowledge Representation and Reasoning, Levesque (ARCS 1986)

  \paper On Representations of Problems of Reasoning about Actions,
Amarel (WN) [RDZ will annotate]

  \paper Computer Science as Empirical Enquiry: Symbols and Search,
Newell and Simon (CACM, Vol 19, no 3, pp 113--126).

  \paper Newell, The Knowledge Level, (AIJ Vol. 18 pp 87--127, 1982).

  \paper  The Logic of Frames, Hayes (WN) 

  \paper Frame Representations and the Declarative/Procedural
Controversy, Winograd (BL).  Sections 1--3, mostly a historical
overview.

  \paper  Blackboard Systems, Penny Nii (AI Mag Vol 7, No 3)

  \paper  Soar: An Architecture for General Intelligence, Laird, Newell and
Rosenbloom (AIJ Vol 33  No 1), sections 1, 3.1, 3.2 and 4.

  \paper  Ch 9  Genesereth/Nilsson, Knowledge and Belief
     [Sections 9.1,9.2,9.4,9.5,9.7-9.10; ignore all details about derivations]

  \paper  Temporal Reasoning, Shoham and Goyal. (EAI)

  \paper  Qualitative Physics: Past, Present and Future, Forbus (EAI)
Read sections 1-3.

  \paper  Second Naive Physics Manifesto, Hayes (BL) [klm will annotate]

\end{required}

\begin{optional}

  \paper  KRYPTON: A Functional Approach to Knowledge Representation,
        Brachman, Fikes and Levesque (BL) 

  \paper  I Lied About the Trees, Brachman, (AI Mag, Fall 1985)

  \paper  Some Problems and Nonproblems in Representation Theory (Hayes) (BL)

  \paper  Vision, Marr. (pp 19-29)

\end{optional}

\section{Reasoning}
\label{sec:reasoning}

\begin{required}

  \paper Ch 3,4,5 of Genesereth and Nilsson.  Skip the proofs in 4.10.
Also skip 5.8.  Logical inference, resolution and resolution
strategies.

  \paper Principles of Rule-based Expert Systems, Buchanan and Duda
(HPP-82-14).  Read the sections on uncertain reasoning.

  \paper Charniak and McDermott [8.1,8.2,8.4].  Abduction from both a
logical and a statistical perspective.

  \paper  Handbook [Vol. 3 Ch. 12: Skim A, Read C and D, Skip B,E,F]

  \paper Non-resolution Theorem Proving, Bledsoe (WN).  Highly uneven,
but an overview of the state of the art.

  \paper Nonmonotonic Reasoning, Reiter (1987 ARCS) OR Readings in
Nonmonotonic Reasoning (introduction), Ginsberg.  [KLM will annotate]

  \paper Prolegomena to a Theory of Mechanized Formal Reasoning,
Weyhrauch (WN). Sections 1--9 except 9.1 and 9.2.  The key ideas are
meta-level reasoning and attachment to models.

\paper Rich, Artificial Intelligence, section 6.2.2 for n overview of
Truth Maintenance.

\paper deKleer, An assumption-based TMS.  Ginsberg collection on
Non-monotonic Reasoning, also AIJ 28, 1986 pp 127--162.  Read section
1 to understand the basic ideas; read more if you find it interesting.

\end{required}

\begin{optional}

  \paper  Applications of Circumscription to Formalizing Commonsense Knowledge, 
        McCarthy (AIJ Vol. 28, 1986)

  \paper  Meta-level architecture (Genesereth and Smith)

  \paper  Algorithm = Logic + Control, Kowalski  (CACM Vol 22 No 7)

  \paper  On Closed World Databases, Reiter (WN)

  \paper Subjective Bayesian Methods for Rule-based Inference Systems,
Duda, Hart and Nilsson (WN).

\end{optional}

\section{Planning and Problem Solving}
\label{sec:planning}

\begin{required}

\paper   AI Handbook:
     Chapter 2.D.2 for GPS;
     Chapter 2.D.6 for ABSTRIPS;
     Chapter 15 (Skip the STRIPS and ABSTRIPS section --- the other
references to them are much better.) [KLM will check]

\paper Nilsson, Principles of Artificial Intelligence, Chapter 7.
[KLM will annotate].

\paper Learning and executing generalized robot plans, Fikes, Hart \&
Nilsson (WN), sections 1, 3--6.  A good overview of triangle tables.

\paper Winston, Artificial Intelligence, Chapter 3.  Constraint
propagation.

\paper Waldinger, Achieving several goals simultaneously, in WN collection.

\paper   Swartout, DARPA Santa Cruz Workshop on Planning, AI Magazine,
Summer 1988.  A good survey of current work and issues in planning.

\paper   Barstow survey of AP in Intro to Software Engineering and Automatic
Programming. (Morgan Kaufmann collection on automatic programming)

\end{required}

\begin{optional}



 \paper   Manna \& Waldinger, A deductive approach to program synthesis  (WN)

 \paper   Lifschitz, On the Semantics of STRIPS (Timberline Proceedings)

 \paper Chapman, Planning for conjunctive goals.  AIJ June 1987.  [RDZ
will annotate extensively, argue w/ KLM].

 \paper Sussman and Steele, Constraints: a language for expressing
almost hierarchical descriptions, AIJ 14 (1980).  Read section 1 and
enough of section 2 to understand what the program does.

\end{optional}


\section{Speech Understanding and Natural Language}
\label{sec:speech}

\begin{required}

 \paper AI Handbook, Chapter 5 (the Speech Recognition chapter).

 \paper Rich, Chapter 9.

 \paper Grosz, Readings in Natural Language Processing.  Introduction
only.

 \paper Winograd, What does it mean to understand language?  Cognitive
Science 4(3) 1980.  Winograd's further thoughts on the matter are in
Winograd \& Flores, Computers and Cognition.

\end{required}

\begin{optional}

 \paper   The Hearsay II Speech Understanding System (WN)
     Read the introduction for some insight into the complexities of
     speech understanding and the conclusion for a summary of Hearsay.

\end{optional}

\section{Vision}
\label{sec:vision}

\begin{required}

  \paper Winston (2nd ed), Chapter 10 except last section.  This is
introductory reading and is essential for understanding the contents
of the following survey by Brady.

  \paper Computational approaches to image understanding.  ACM
Computing surveys, Vol 14, no 1, March 1982.  Excellent survey of
methods in computer vision.

  \paper AI Handbook, Chapter 13 Sections E.1,E.2 for vision
algorithms and sections F.1,F.3 for overviews of systems.

\end{required}

\begin{optional}
      
  \paper Marr, Chapter 1 This chapter presents a philosophy of AI and
vision research that has been important in shaping vision research at
MIT.

  \paper   Survey of model-based image analysis systems (Binford),
      International Journal of Robotics Research, Vol.1 No. 1, 1982 (pg. 18-28)
      Surveys and critiques the state of the art (circa 1982) of model
      based vision systems and describes principles in the design of
      general vision systems. It is interesting to contrast the approach
      with that of Marr.

\end{optional}

\section{Robotics}
\label{sec:robotics}

\begin{required}

\paper Winston, Chapter 10, last section.  A basic introduction to
robotics.

\paper Path planning and obstacle avoidance, AIE pages 708--715.
  
\paper Mobile robots, AIE pages 957--961.

\paper Sensors, AIE pages 1031--1036.

\end{required}

\begin{optional}

\paper Brooks, A Robust Layered Control System for a Mobile Robot,
IEEE Journal of Robotics and Automation, March 1986.

\end{optional}

\section{Expert systems}
\label{sec:expert-systems}

\begin{required}

  \paper  AI Handbook, Vol 2
     Read sections 7.A, 8.A, 9.A, 9.B for overviews of this area.
     You should be fairly familiar with the PROSPECTOR system.  Also
     take a look at the sections on MACSYMA, TEIRISIAS, Casnet,
     Internist, Sophie, Buggy, Guidon, Excheck. 

  \paper  Dendral and Meta-Dendral: Their Applications Dimension, 
        Buchanan and Feigenbaum (WN)
     Now we are into specific systems. This short paper gives an
     excellent overview of the Dendral and MetaDendral programs:
     two programs that were (and still are) impressive. 

  \paper Rule-based Expert Systems, Buchanan and Shortliffe (Chapters
1,3,4,15).  Chapters 1 and 4 of this book explain the historical
context of its evolution as well the structure of the system.  Chapter
3 describes their decision to use rules. Chapter 15 gives an overview
of the Emycin shell.

  \paper  Principles of Rule-based Systems, Buchanan and Duda (HPP-82-14).
     This paper discusses key issues in expert system design:
     representation, inference and uncertainty management. 
     Has a large number of pointers to specific expert systems.
     Also has a discussion of the range of problems for which
     rule-based systems are useful.

  \paper Randy Davis, Expert systems: where are we? Where are we
going?  (AI Mag Spring 1982).  Even though this is somewhat dated
(1982), it is still a very readable report on the state of the art
with respect to expert systems. A program of research on model-based
systems is proposed as a solution to some of the problems with
rule-based expert systems.

  \paper  R1 Revisited: Four Years in the Trenches, J. McDermott (AI Mag Fall 1984) 
     Get the basics of the R1 system --- it's one of the few
     forward-chaining expert systems ever built.


\end{required}

\begin{optional}

  \paper  Model Design in the PROSPECTOR Consultant System for Mineral Exploration,
     Duda, Hart and Nilsson (WN paper)
     This paper outlines the structure of the Prospector system.  Look
     closely at the scheme they use for reasoning with uncertain beliefs. 

  \paper Model-based reasoning: troubleshooting, Davis and Hamscher.
(EAI) Only Sections 1-3.

  \paper  Consultation Systems for Physicians, Shortliffe (WN collection)
     This is an excellent discussion of the user-interface 
     requirements for bringing diagnostic expert systems
     into hospital wards for use by doctors.

\end{optional}

\section{Learning}
\label{sec:learning}

\begin{required}


  \paper  Handbook of AI, Ch 14
     A comprehensive introduction to work on learning, though a bit
dated.  Details of Mostow's operationalizer, Waterman's poker player
are irrelevant. The only systems that you need to know in some detail
are AM, Meta-Dendral, Samuels's checkers player.  Skim the rest of the
systems. Skip Section D.5e (grammatical inference).

  \paper Machine Learning, (AIE) pp 464-485.  A review of more recent
work in machine learning, including analogy. Complements the Handbook.

  \paper Soar: An Architecture for General Intelligence, Laird, Newell
and Rosenbloom (AIJ Vol 33 No 1).  Read Section 3.3

\end{required}

\begin{optional}

  \paper Generalization as Search, Mitchell (WN) A well-written paper
that views generalization as a search problem.

  \paper Learning and Problem Solving: The Computers and Thought Award
Lecture, IJCAI-83, Tom Mitchell.  (Also appears in AIJ). The problem
of bias in learning generalizations.

  \paper  A Theory of the Learnable, Valiant (CACM 27 (11) 1984)

  \paper Why should machines learn?, Simon, in Machine Learning,
edited by Michalski, Carbonell and Mitchell.
 This is a philosophical paper that explains why (or not!) machine
learning research is relevant. 

\end{optional}


\section{Perspectives}
\label{sec:perspectives}
\label{sec:last}

\begin{required}

   \paper  Programs with Common Sense, McCarthy (BL)

   \paper  Some philosophical problems from the standpoint of AI, McCarthy (WN)

   \paper  Some epistemological problems in AI, McCarthy (WN)

   \paper  Intelligence Without Representation, Brooks, in the proceedings
        of the Workshop on the Foundations of Artificial Intelligence
        (Draft of 1987 --- ask around for it)

   \paper  The Limits of AI: Schwartz (AI Encyclopedia)

   \paper  The Synthesis of Machines with Provable Epistemic Properties,
        Rosenschein and Kaelbling, in Proceedings of the Conference on
        Theoretical Aspects of Reasoning about Knowledge, Edited by J.
        Halpern 1986 

\paper Fahlman and Hinton, Connectionist Architectures for Artificial
Intelligence.  {\em IEEE Computer}, January 1987, pp 100--109.

\paper CYC, AI Magazine 1986, Vol 7 no 1. (?)

\end{required}

\begin{optional}

   \paper  Computational Intelligence Issue on McDermott's article (Vol. 3
        No. 3 August 1987)

   \paper  Ascribing Mental Qualities to Machines, McCarthy (BL)

   \paper  Sciences of the Artificial, Simon, MIT Press, second edition.

   \paper  AI: A Personal View, Marr (AIJ Vol. 9 No.1 1977, also in Mind Design)

   \paper  Computers and Cognition,  Winograd and Flores 

\end{optional}

\end{document}
-------
-------

