CSCE 580: Artificial Intelligence

TTh 1315-1430 300 Main B213

Prerequisites: CSCE 350 (Data Structures and Algorithms).

Instructor: Marco Valtorta
Office: Swaeringen 3A55, 777-4641
E-mail: mgv@cse.sc.edu
Office Hours: 1030-noon TTh

Teaching AssistantYuxin Cui (say: "Tree")
E-mail: ycui@email.sc.edu
Office: Swearingen 3D47
Office Hours: 1030-noon WF

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 (referred to as [P]; ISBN 978-0-521-51900). Supplementary materials from the authors are also available. Note that you may have to configure java to allow the applets at http://www.aispace.org and at http://aispace.org to run, because they are self-signed applications. See this tutorial for details.
  • Hector J. Levesque. Thinking as Computation. The MIT Press, 2012 (required text, referred to as [L]; ISBN 978-0-262-01699-5). Supplementary materials from the author are 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
  • Provide an argument for the notion that thinking is a computational process
  • Write Prolog programs that support the above argument
  • 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
  • Lecture Log

    Student Presentations

    Homework
    Some assignments are only listed in the lecture log.
    Grids to be used for exercise 3.3 [P]

    Tests
    Midterm from spring 2015.
    Final from spring 2014.

    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]
  • KenKen puzzle for HW2 (spring 2017)
  • Agent Architectures and Hierarchical Control, covering chapter 2 of [P]
  • Notes on an example of transduction and belief states used in the 2014-01-30 class (pdf)
  • States and Searching, covering chapter 3 of [P]
  • Uninformed (Blind) Search, covering chapter 3 of [AIMA-2] (as used in fall 2011)
  • Hints and requirements for HW4 (Exercise 3.3 [P]) as discussed in class on 2017-04-04.
  • Example: Dijkstra's algorithm on the graph of Figure 3.2[P]
  • Proof that Dijkstra's algorithm does not need to reopen closed nodes, p.170 of: Sara Baase. Computer Algorithms: Introduction to Design and Analysis, second edition. Addison-Wesley, 1988.
  • Heuristic Search, covering chapter 4 of [AIMA-2] (as used in fall 2011)
  • Prolog code for A* used in the 2015-02-05 lecture. See comments in the code for sources and limitations of this code.
  • Example of A* with a Non-Monotone Heuristic Re-Expanding Closed Nodes.
  • Pseudocode for the depth-first-search and backtracking algorithms from Judea Pearl's Heuristics, Addison-Wesley, 1984.
  • Grids for exercise 3.3 [P]
  • Features and Constraints, covering chapter 4 of [P]. (A description of IDA* is given at the beginning of this presentation. A presentation of non-serial DP is given near the end of this presentation.)
  • Description of the Davis-Putnam Logemann Loveland algorithm for propositional satisfiability from: Dechter, Rina. Constraint Processing. Morgan-Kaufmann, 2003.
  • Notes on Nonserial Dynamic Programming used on 2015-03-24; only the pages before "Globally Optimum Storage Patterns" were used.
  • Notes on computing heuristics by problem relaxation, including the Tower of Hanoi example
  • Three properties of heuristics computed by problem relaxation, as written in class on 2014-03-04
    Definition of search tree with an example, from Edelkamp and Schroedl (Stefan Edelkamp and Stefan Schroedl. Heuristic Search: Theory and Applications. Morgan Kauffman, 2011.
    Propositions and Inference, covering chapter 5 of [P]

    Quizzes (In-Class Exercises)
    Quiz 1 of 17-01-11 (with answer)
    Quiz 3 of 17-01-19 (with answer) (This quiz was assigned before quiz 2.)
    Quiz 2 of 17-01-24 (with answer)
    Quiz 4 of 17-02-02 (with answer) (The quiz as assigned had an error; all students who took it are given full credit.)
    Quiz 5 of 17-02-16 (with answer)
    Quiz 6 of 17-03-28 (with answer; docx format)
    Quiz 7 of 17-03-39 (with answer; docx format)
    Quiz 8 of 17-03-30 (with answer; docx format)
    Quiz 9 of 17-03-30 (with answer; docx format)
    Quiz 10 of 17-03-30 (with answer; docx format)
    Quiz 11 of 17-04-11 (with answer; docx format)
    Quiz 12 of 17-04-18 (with answer; docx format)

    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, including AI in the News, a digest compiled by the Association for the Advancement of Artificial Intelligence (AAAI).
    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. (local copy).
    4. Derek Partridge and Yorick Wilks. "Does AI Have a Methodology Different from Software Engineering?" Technical Report MCCS-86-53, Computing Research Laboratory, New Mexico State University, 1986 (local copy).
    5. 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).
    6. In this class, we write dates according to ISO Standard 8601.
    7. The Alan Turing Home Page, maintained by Andrew Hodges.
    8. Alan Turing's ``Computing Machinery and Intelligence,'' Mind, 49 (1950), pp.433-460 , in HTML format.
    9. 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).
    10. 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).
    11. Judea Pearl. "On the Discovery and Generation of Certain Heuristics." AI Magazine, 4, 1 (Winter/Spring 1983), 23-34 (local copy).
    12. M. Valtorta. "A Result on the Computational Complexity of Heuristic Estimates for the A* Algorithm. Information Sciences, 34, 47-59 (1984), (local copy).
    13. Irina Rish and Rina Dechter. "Resolution vs. Search: Two Strategies for SAT." Report R-80, Department of Information and Computer Science, University of California, Irvine, undated. Published under the same title in: Journal of Automated Reasoning. Volume 24, Issue 1/2 (special issue on SAT), pp. 225-275, January, 2000.
    14. John McCarthy's Obituary from the _New York Times_, 2011-10-25 (local copy).
    15. Local copy of Raymond Reiter, "A Theory of Diagnosis from First Principles." Artificial Intelligence, 32, 1, pp.57-96, 1987.
    16. 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.
    17. George F. Luger and William A. Stubblefield. AI Algorithms, Data Structures, and Idioms in Prolog, Lisp, and Java. Addison-Welsey, 2009 (local copy).