CSCE 625 - Artificial Intelligence

Professor: Dr. Thomas R. Ioerger
Office: 322C Bright Bldg.
Phone: 845-0161
email: ioerger@cs.tamu.edu
office hours: Tu/Th 1:00-2:00, or by appointment

TA: Huei-Fang Yang
office hours: Wed/Thurs, 10:30-noon, 322A Bright

Meeting: TR, 2:20-3:35, 105B Zachry

Course Web Page: http://www.cs.tamu.edu/faculty/ioerger/cs625-fall09/index.html

Prerequisites: CSCE 315 (Programming Studio)

Textbook

Russell, S. and Norvig, P. (2002). Artificial Intelligence: A Modern Approach. 2nd edition (green cover). Prentice Hall.

Goals of this Course

1. To learn about intelligent search methods and their role in building complex problem-solving programs.
2. To learn about knowledge representation techniques and methods for exploiting knowledge in programs.
3. To gain exposure to traditional sub-fields of AI (automated deduction, planning, learning...).

• Perspective on AI (philosophical, psychological, engineering)
• Intelligent Agents (characteristics, environments, architectures)
• Search Algorithms (depth-first, breadth-first, iterative deepening)
• Heuristic Search (best-first, A*, hill-climbing)
• Constraint Satisfaction Problems
• Adversarial (Game) Search (minimax, alpha-beta pruning)
• Propositional Logic
• First-Order Logic (syntax and semantics)
• Inference Methods (natural deduction, resolution, unification)
• Knowledge Representation, Ontologies
• PROLOG
• Default logics, fuzzy logic
• Uncertainty and Probability (Bayesian inference, belief nets, Markov decision problems)
• Planning (goal-regression, STRIPS, frame problem)
• Other types of planners (partial-order planning, hierarchical, graph/SAT, scheduling)
• Machine Learning (perceptrons, decision trees, etc.)
• Natural Language Processing (grammars, parsing, semantics, disambiguation)

The work for this course will consist of a mix of homework assignments, programming projects, and exams. The final grade for the course will be a weighted combination of these three components, which is tentatively set as follows (though subject to change): 30% homework, 40% projects, 30% exams. There will most likely be a mid-term exam and a final exam. The minimum score for an grade of an A will be 90%, the minimum for a B will be 80%, and so on, though these thresholds may be lowered depending on the performance of the group overall. The penalty for late assignments is -5% per day (24 hours).

Schedule:

Tues, Sep 1: first day of class; What is AI? [Ch. 1] (perspectives; core concepts)
Thurs, Sep 3: Intelligent Agents [Ch. 2] (characteristics, environments, architectures)
Tues, Sep 8: Uninformed Search [Ch. 3] (DFS, BFS, ID, UC)
Thurs, Sep 10: Informed Search [Ch. 4] (heuristics, greedy, A*)
Tues, Sep 15: Local Search (hill-climbing, simulated annealing); Programming Assignment #1 due
Thurs, Sep 17: Game-Playing (Ch. 6)
Tues, Sep 22: Constraint-Satisfaction (Ch. 5)
Thurs, Sep 24:
Tues, Sep 29: Exam #1; Project #1 due

Thurs, Oct 1: Propositional Logic, read Ch. 7
Tues, Oct 6: inference methods
Thurs, Oct 8:
Tues, Oct 13: First-Order Logic, read Ch. 8; Homework 3 due
Thurs, Oct 15: model theory, unification, inference rules in FOL
Tues, Oct 20: Homework #4 due; Ontologies; read Sec 8.3-8.4, pp. 320-328 (10.1-10.2), 334-340, and 10.5 (skip Situation Calculus, Beliefs); slides
Thurs, Oct 22: Automated Deduction - Practical first-order inference systems (Otter, Prolog, CLIPS, Jess); read Ch. 9, slides
Tues, Oct 27: Homework #5 due; limitations of FOL, default reasoning; other KR methods (frames, DLs...), read Sec 10.6-10.8, slides
Thurs, Oct 29: Exam #2 (Ch. 7-10)

Tues, Nov 3: Situation Calculus and the Frame Problem (Sec. 10.3)
Thurs, Nov 5: Planning (Ch. 11) - STRIPS, goal regression
Tues, Nov 10: Homework #6 due; partial-order planning
Thurs, Nov 12: assorted topics in planning; read sec. 11.5, 12.1-12.3, 12.5; (slides)
Tues, Nov 17: Prolog; Homework #7 due
Thurs, Nov 19: Uncertainty Reasoning, read Ch. 13
Tues, Nov 24: Homework #8 due, Bayesian networks, exact inference (read Sec 14.1-14.4), (slides)
Thurs, Nov 26: Thanksgiving - class cancelled

Tues, Dec 1: Homework #9 due; belief propagation and inexact inference (read 14.5), also Sec 8.4.2-8.4.4 from Bishop's PR&ML book, (slides)
Thurs, Dec 3: Summary discussion (read Ch. 26)
Tues, Dec 8: last class - final exam; Homework #10 due

Links

• Deep Blue: 31-page paper describing implementation details
• TPTP Database - Thousands of Problems for Theorem Provers
• Ch. 7 notes
• Naive Physics Manifesto - Ontology of Liquids Patrick Hayes, 1986
• first-order logic model theory
• Ch. 1, The Description Logic Handbook
• Weld (1994) - section 3.2 contains a nice description of goal-regression
• SWI-Prolog manual
• my notes (mini-tutorial) on Prolog
• Charniak, E. (1991). Bayesian Networks without Tears. AI magazine.
• D'Ambrosio, B. (1999). Inference in Bayesian Networks. AI Magazine.
• Ch. 8 from Patt Rec and ML by C. Bishop