CSCE 580: Artificial Intelligence


TTh 1400-1515 SWGN 2A24

Prerequisites: CSCE 350 (Data Structures and Algorithms).

Instructor: Marco Valtorta
Office: Swaeringen 3A55, 777-4641
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.


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

    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

    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.