CSCE 580: Artificial Intelligence

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
  • 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 first-order logic
  • Do inference using resolution refutation theorem proving (if time allows)

    • Lecture Log

    Student Presentations

    Homework

    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 [AIMA-2] (as used in fall 2011)
  • Heuristic Search, covering chapter 4 of [AIMA-2] (as used in fall 2011)
  • 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
  • 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. Morgan-Kauffman, 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 (In-Class Exercises)
    Quiz 1 of 12-08-28 (with answer)
    Quiz 2 of 12-08-30 (with answer)
    Quiz 3 of 12-09-01 (with answer)
    Quiz 4 of 12-09-18 (with answer)

    The USC Blackboard has a site for this course.

    Some useful links:

    1. Brian Hayes. "The Manifest Destiny of Artificial Intelligence." American Scientist, Volume 100, Number 4 (July-August 2012), 282-287 (local copy) .
    2. Bruce G. Buchanan. "A (Very) Brief History of Artificial Intelligence." AI Magazine, Winter 2005, pp.53-60 (local copy), related links at aaai.org, compiled by the author.
    3. 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.
    4. 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).
    5. In this class, we write dates according to ISO Standard 8601. (Also see this).
    6. The Alan Turing Home Page, maintained by Andrew Hodges.
    7. Alan Turing's ``Computing Machinery and Intelligence,'' Mind, 49 (1950), pp.433-460 , in HTML format.
    8. 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).
    9. 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).
    10. Judea Pearl. "On the Discovery and Generation of Certain Heuristics." AI Magazine, 4, 1 (Winter/Spring 1983), 23-34 (local copy).
    11. M. Valtorta. "A Result on the Computational Complexity of Heuristic Estimates for the A* Algorithm. Information Sciences, 34, 47-59 (1984), (local copy).
    12. John McCarthy's Obituary from the _New York Times_, 2011-10-25 (local copy).
    13. Local copy of Raymond Reiter, "A Theory of Diagnosis from First Principles." Artificial Intelligence, 32, 1, pp.57-96, 1987.
    14. 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.
    15. George F. Luger and William A. Stubblefield. AI Algorithms, Data Structures, and Idioms in Prolog, Lisp, and Java. Addison-Welsey, 2009 (local copy).