TTh 1400-1515 SWGN 2A24

Prerequisites: CSCE 350 (Data Structures and Algorithms).

Instructor: Marco Valtorta
Office: Swaeringen 3A55, 777-4641
E-mail: mgv@cse.sc.edu
Office Hours: 1100-1200 MWF

Any student with a documented disability should contact the Office of Student Disability Services at (803)777-6142 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 978-0-521-51900). 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 state-space 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

Reason under uncertainty using Bayesian networks

Represent domain knowledge about individuals and relations using first-order logic

Do inference using resolution refutation theorem proving

Represent knowledge in Horn clause form and use the AILog dialect of Prolog for reasoning

Tests

Student Presentations

Homework
Grades per assignment
Homework 1: definition of AI, state of the art
Homework 2: Exercises 3.3 and 3.4 [P].
Homework 3: Exercises 4.1 and 4.3 [P], due October 25, 2011.
Homework 4: Enter the crosswork problem of 4.3(a) and 4.1(c) [P] in the CSP applet at AISpace. Solve with the generalized arc consistency algorithm. Turn in a printout of the netwok after the GAC algorithm stops. (This will not be a unique solution.) This homework is due on Thursday, October 27.
Homework 5: Exercises 4.2, 4.4, and 4.11 [P], due November 1, 2011.
Program 1: exercises 1, 4, and 6 from Ch. 22 of Luger and Stubblefield (copy on blackboard), due on Thursday, November 10.
Program 2 (PR2): exercise 5.13 [P], due Tuesday, November 22. (Use AILog. Turn in hardcopy with code and a sample run.)
Homework 6 (HW6): Exercises 5.7 and 5.8 [P], due Tuesday, November 22. (You may use AILog for these exercises, if you find it convenient.)
Homework 7: Exercise 6.2 [P], due Thursday, December 1.

Lecture Log

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]
Uninformed (Blind) Search, covering chapter 3 of [AIMA-2]
Heuristic Search, covering chapter 4 of [AIMA-2]
Notes on properties of A*, as written in class of 2011-09-08
Notes on computing heuristics by problem relaxation, as written in class of 2011-09-13
Notes on Valtorta's Theorem on the complexity of heuristics for A*, as written in class of 2011-09-13
M. Valtorta. "A Result on the Computational Complexity of Heuristic Estimates for the A* Algorithm." Information Sciences, 34, 47-59 (1984).
Features and Constraints, covering chapter 4 of [P]
Notes on submission format for PR1.
Notes on search algorithms in Java, used by Jingsong Wang on 2011-10-18.
Notes on HW3, especially exercises 4.3(a) and (c) [P], as written in class of 2011-10-25
Propositions and Inference, covering chapter 5 of [P] (Note: some of these slides may be different from the latest version available directly from the authors of [P].
Notes from the review session of 2011-12-06.

Quizzes (In-Class Exercises)

The USC Blackboard has a site for this course.

Prolog Information (To be activated)

Some useful links:

1. 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.187-227.
2. An obituary of Ray Solomonoff, (co-inventor) of descriptive complexity (Kolmogorov complexity) and advocate of the use of probability in artificial intelligence, written by his wife, Grace (_Algorithms_ 2010, 3, 255-259).
3. In this class, we write dates according to ISO Standard 8601. (Also see this).
4. The Alan Turing Home Page, maintained by Andrew Hodges.
5. Alan Turing's ``Computing Machinery and Intelligence,'' Mind, 49 (1950), pp.433-460 , in HTML format.
6. Hart, P., Nilsson, N., and Raphael, B., "A Formal Basis for the Heuristic Determination of Minimum Cost Paths," IEEE Trans. Syst. Science and Cybernetics, SSC-4(2):100-107, 1968. (local copy).
7. Hart, P., Nilsson, N., and Raphael, B., "Correction to 'A Formal Basis for the Heuristic Determination of Minimum-Cost Paths'," SIGART Newsletter, no. 37, pp. 28-29, December, 1972. (local copy).
8. John McCarthy's Obituary from the _New York Times_, 2011-10-25 (local copy).
9. Local copy of Raymond Reiter, "A Theory of Diagnosis from First Principles." Artificial Intelligence, 32, 1, pp.57-96, 1987.
10. 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.79-88.