CSCE 580: Artificial Intelligence

MWF 1325-1410 SWGN 2A15

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:

By special arrangement, we will use drafts of chapters of the following text (required text, referred to as [P]) David Poole and Alan Mackworth. Artificial Intelligence: Foundations of Computational Agents. Supplementary materials from the authors are also available.

Here are the

  • current departmental syllabus for CSCE 580, an older
  • departmental syllabus for CSCE 580 (for historical information), and an even older
  • departmental syllabus for CSCI 580, (for historical information).
    • Note that syllabus flexibility is indicated as high, and our course is somewhat different from the model one; in particular, we do not use the textbooks of the model curriculum.
    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 Prolog for reasoning

    • Tests
    Notes for the final exam

    Student Presentations for Fall 2008

    Student Presentations

    Homework
    Grades per assignment
    Homework 1: definition of AI, state of the art
    Homework 2, due Friday, September 11: uninformed (blind) search: exercises 3.7 (except (c)), 3.8, 3.9(a) from the handout [AIMA-2]
    Homework 3, due Friday, September 18: informed (heuristic) search: exercises 3.3 and 3.13 [P]
    Homework 4, due Wednesday, September 23: informed (heuristic) search: exercise 3.4 [P]
    Homework 5, due Wednesday, October 7: features and constraints: exercises 4.1, 4.2, 4.3, 4.11 [P]
    Program 1, due Wednesday, October 14: Search algorithms in Java, exercises 1,4,6 from handout [LS-09]
    Homework 6, due Monday, October 19: features and constraints: exercises 4.4, 4.5, 4.6 [P]
    Homework 7, due Friday, November 13: propositions and inference: exercises 5.2, 5.3, 5.6, 5.7, 5.8, 5.9, 5.10, 5.11, 5.17, 5.18(part a only)[P]. Note: Use the html version of the manuscript on the course web site for the correct exercise numbers. Note: this assignment includes programming in AILog; it may be split into a proper HW part and a programming exercise part.
    Homework 8, due Monday, November 30: Bayesian (belief) networks: exercises 6.2, 6.3, 6.4 [P].
    Homework 9, due Friday, December 4: Individuals and relations: exercises 12.1, 12.15, 12.16 [P].

    Lecture Log

    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, coversing 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 for exercise 3.8 [AIMA] and 3.3 [P], including a state space for the Missionaries and Cannibals problem
    Features and Constraints, covering chapter 4 of [P]
    Constraint Satisfaction Problems, covering chapter 5 of [AIMA-2]
    Notes for exercise 3.3 [P]
    Notes on Nonserial Dynamic Programming
    Format of submission for PR1
    Notes on the propositional calculus
    Adversarial Search (2-player games), covering chapter 6 of [AIMA-2]
    Propositions and Inference, covering chapter 5 of [P]
    Algorithm for satisfiability of propositional Horn clauses
    Proposition and Inference, covering Section 5.5-5.7 (Complete Knowledge Assumption, Abduction, and Causal Models) of [P]
    Reasoning under Uncertainty, covering Section 6.1 (Probability) of [P]
    Reasoning under Uncertainty, covering Sections 6.2 and 6.3 (Independence and Bayesian Networks) of [P]
    Reasoning under Uncertainty, covering Sections 6.4 (Probabilistic Inference) of [P]
    Example for Bucket Elimination Algorithm (pdf)
    Authors' notes for Chapter 12 of [P]
    Individuals and Relations: Datalog: Section 12.3 of [P]
    Individuals and Relations: Proofs and Functions: Sections 12.4 and 12.5 of [P]
    Notes on Resolution Refutation in First Order Logic
    Examples of Proofs Using Resolution Refutation in First Order Logic
    Examples of AILog programs, and a proof using resolution refutation in first order logic

    Quizzes (In-Class Exercises)
    Quiz 1 of 09-08-24 (with answer)

    The USC Blackboard has a site for this course.

    Prolog Information (To be activated)

    Some useful links:
    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).
    In this class, we write dates according to ISO Standard 8601. (Also see this).
    The Alan Turing Home Page, maintained by Andrew Hodges.
    Alan Turing's ``Computing Machinery and Intelligence,'' Mind, 49 (1950), pp.433-460 , in HTML format.