CSCE 580: Artificial Intelligence
TTh 14001515 SWGN 2A24
Prerequisites: CSCE 350 (Data Structures and Algorithms).
Instructor: Marco Valtorta
Office: Swaeringen 3A55, 7774641
Email:
mgv@cse.sc.edu
Office Hours: 11001200 MWF
Any student with a documented disability should contact the Office of
Student Disability Services at (803)7776142 to make arrangements for proper
accommodations.
Syllabus
Grading and Program Submission Policy
Reference materials:
David Poole and Alan Mackworth.
Artificial Intelligence: Foundations of
Computational Agents.
Cambridge University Press, 2010
(ISBN 978052151900).
Supplementary materials from the authors
are also available.
Specific objectives of this course are that the students will be able to:
Analyze and categorize software intelligent agents and the environments in
which they operate
Formalize computational problems in the statespace search approach and
apply search algorithms (especially A*) to solve them
Represent domain knowledge using features and constraints and solve
the resulting constraint processing problems
Represent domain knowledge about objects using propositions and solve the
resulting propositional logic problems using deduction and
abduction
Represent knowledge in Horn clause form and use the AILog dialect of
Prolog for reasoning
Reason under uncertainty using Bayesian networks
Represent domain knowledge about individuals and relations using
firstorder logic
Do inference using resolution refutation theorem proving (if time allows)
Lecture Log
Student Presentations
Homework
 Grades per assignment
 Program 1: Do either exercises 1 from Ch. 22 of Luger and Stubblefield
(link under "some useful links, below), or exercise 2 in chapter 4,
due on Tuesday, October 30.
Tests
Final exam from fall 2011.
Lectures
Most lecture use notes from the authors of the texbook. (See link under
"reference materials," above.)
Overhead transparencies for [P] are linked to the main page for [P]; the
specific link is here.
Introductory lectures, covering chapter
1 of [P]
Agent Architectures and Hierarchical
Control, covering chapter 2 of [P]
States and Searching, covering chapter 3
of [P]
Grids for exercise 3.3 [P]
Uninformed (Blind) Search, covering
chapter 3 of [AIMA2] (as used in fall 2011)
Heuristic Search, covering
chapter 4 of [AIMA2] (as used in fall 2011)
Notes on properties of A*,
as written in class of 20110908
Notes on computing
heuristics by problem relaxation,
as written in class of 20110913
Notes on Valtorta's
Theorem on the complexity of heuristics for A*,
as written in class of 20110913
Features and Constraints, covering
chapter 4 of [P]. (A description of IDA* is given at the beginning
of this presentation.)
Valtorta's Thorem as described in: Stefan Edelkamp and Stefan Schroedl. Heuristic Search: Theory and
Applications. MorganKauffman, 2011.
Doug Fisher's video on Constraint Satisfaction (as Search) (7mins approx.)
Doug Fisher's video on Generalized Arc Consistency (16 mins approx.)
Doug Fisher's video on Features, Constraints, Machine Learning, Printing
(15 mins, approx.)
Networks for exercises 4.3(c) and 4.4
Quizzes (InClass Exercises)
Quiz 1 of 120828
(with answer)
Quiz 2 of 120830
(with answer)
Quiz 3 of 120901
(with answer)
Quiz 4 of 120918
(with answer)
The USC Blackboard
has a site for this course.
Some useful links:

Brian Hayes. "The Manifest Destiny of Artificial
Intelligence." American Scientist, Volume 100, Number 4 (JulyAugust
2012), 282287
(local copy)
.
 Bruce G. Buchanan. "A (Very) Brief History of Artificial Intelligence."
AI Magazine, Winter 2005, pp.5360
(local copy),
related links at aaai.org, compiled
by the author.

Allen Newell. "Intellectual Issues in the History of Artificial Intelligence."
From: Fritz Machlup and Una Mansfield, eds. The Study of Information:
Interdisciplinary Messages. John Wiley and Sons, 1983, pp.187227.

An obituary of Ray Solomonoff,
(coinventor) of
descriptive complexity (Kolmogorov complexity) and advocate of the use
of probability in artificial intelligence, written by his wife, Grace
(_Algorithms_ 2010, 3, 255259).
 In this class, we write dates according to
ISO Standard 8601.
(Also see
this).

The
Alan Turing Home Page, maintained by Andrew Hodges.

Alan Turing's
``Computing Machinery and Intelligence,''
Mind, 49 (1950), pp.433460
, in HTML format.

Hart, P., Nilsson, N., and Raphael, B.,
"A Formal Basis for the Heuristic Determination of Minimum Cost Paths,"
IEEE Trans. Syst. Science and Cybernetics, SSC4(2):100107, 1968.
(local copy).

Hart, P., Nilsson, N., and Raphael, B.,
"Correction to 'A Formal Basis for the Heuristic Determination of
MinimumCost Paths'," SIGART Newsletter, no. 37, pp. 2829, December, 1972.
(local copy).

Judea Pearl. "On the Discovery and Generation of Certain Heuristics."
AI Magazine, 4, 1 (Winter/Spring 1983), 2334
(local copy).

M. Valtorta. "A Result on the Computational Complexity of Heuristic
Estimates for the A* Algorithm.
Information Sciences, 34, 4759 (1984),
(local copy).

John McCarthy's Obituary from the _New York Times_, 20111025
(local copy).

Local copy of
Raymond Reiter, "A Theory of Diagnosis from First Principles." Artificial
Intelligence, 32, 1, pp.5796, 1987.

Local copy of
Russell Greiner, Barbara A. Smith, and Ralph W. Wilkerson.
"A Correction to the Algorithm in Reiter's Theory of
Diagnosis. Artificial Intelligence, 41, pp.7988.

George F. Luger and William A. Stubblefield.
AI Algorithms, Data Structures, and Idioms in Prolog, Lisp, and Java.
AddisonWelsey, 2009
(local copy).