CSCE 580: Artificial Intelligence

TTh 1315-1430 SWGN 2A21

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. 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.

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

    • Lecture Log

    Student Presentations

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

    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]
  • 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)
  • Photo of board showing a solution to HW2: Run by hand Dijkstra's Algorithm (as stated in slide 68 at h ttp://www.cse.sc.edu/~mgv/csce580sp14/notes/580Ch3AIMA.ppt) on the example of Figure 3.2 [P] (also on slide 6 at http://www.cse.sc.edu/~mgv/csce580sp14/notes/580Ch3.ppt); show the OPEN and CLOSED lists with the g values of the nodes on those lists for each iteration of lines 2-6 from beginning to end.
  • 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-ftrst-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
    Propositions and Inference, covering chapter 5 of [P]

    Quizzes (In-Class Exercises)
    Quiz 1 of 15-01-15 (with answer)
    Quiz 2 of 15-01-20 (with answer)
    Quiz 3 of 15-01-22 (with answer) (Only the first two questions were used in determining the grade.)
    Quiz 4 of 15-02-03 (with answer)
    Quiz 5 of 15-02-10 (with answer; docx format)
    Quiz 6 of 15-02-12 (with answer; docx format)
    Quiz 7 of 15-02-12 (with answer; docx format)
    Quiz 8 of 15-02-12 (with answer; docx format)
    Quiz 9 of 15-02-12 (with answer; docx format)
    Quiz 10 of 15-02-17 (with answer; docx format)
    Quiz 11 of 15-02-19 (with answer; docx format)
    Quiz 12 of 15-03-19 (with answer; pdf 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. 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.
    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. 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.
    13. John McCarthy's Obituary from the _New York Times_, 2011-10-25 (local copy).
    14. Local copy of Raymond Reiter, "A Theory of Diagnosis from First Principles." Artificial Intelligence, 32, 1, pp.57-96, 1987.
    15. 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.
    16. George F. Luger and William A. Stubblefield. AI Algorithms, Data Structures, and Idioms in Prolog, Lisp, and Java. Addison-Welsey, 2009 (local copy).