CSCE 580: Artificial Intelligence

TTh 1005-1120 300 Main B112

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

    • Lecture Log

    Homework
    Some assignments are only listed in the lecture log.

    Tests

    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]
  • Grids for exercise 3.3 [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.
  • Heuristic Search, covering chapter 4 of [AIMA-2] (as used in fall 2011)
  • Example of A* search on the eight-tile puzzle, using the "number of misplaced tiles" heuristic, as used in class on 2014-02-25
  • Example of use Depth-First Search, Heuristic Depth-First Search, and Best-First Search, as written in class on 2014-02-25
  • Notes on properties of A*, as written in class on 2011-09-08
  • Notes on computing heuristics by problem relaxation, as written in class of 2011-09-13
  • Three properties of heuristics computed by problem relaxation, as written in class on 2014-03-04
  • Example of A* with a Non-Monotone Heuristic Re-Expanding Closed Nodes.
  • Notes on Dynamic Programming for State-Space Search, used on 2014-03-06.
  • 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.)
  • Notes used on 2014-03-20.
  • Notes used on 2014-03-25.
  • Notes used on 2014-04-01 on exercise 4.3(b) [P].
  • Notes used on 2014-04-01 on exercise 4.3(c) [P].
  • Notes on Nonserial Dynamic Programming used on 2014-04-03; only the pages before "Globally Optimum Storage Patterns" were used.
  • Notes used on 2014-04-08 on assignment HW6 (exercise 4.11[P]).

    Quizzes (In-Class Exercises)
    Quiz 1 of 14-01-21 (with answer)
    Quiz 2 of 14-01-23 (with answer)
    Quiz 3 of 14-01-30 (with answer) (Note that the date on the quiz is incorrect.)
    Quiz 4 of 14-02-04 (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. -->
    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).