CPSC 420 - Artificial Intelligence

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

Meeting: MWF, 9:10-10:00, 105B Zachry

Professor: Dr. Thomas R. Ioerger
Office: 322C Bright Bldg.
Phone: 845-0161
email: ioerger@cs.tamu.edu
office hours: Tues & Thurs, 10:00-11:00

Teaching Assistant: Reetal Pai

Prerequisites: CPSC 311 (Analysis of Algorithms)

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.

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

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, 30% projects, 40% exams. There will most likely be a mid-term exam and a final exam. The minimum score for a 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.

Schedule:

Wed, Jan 17: class canceled (ice storm)
Fri, Jan 19: first day of class; go over syllabus
Mon, Jan 22: What is AI? [Ch. 1] (perspectives; core concepts)
Wed, Jan 24: philosophical/psychological/engineering perspectives
Fri, Jan 26: Intelligent Agents [Ch. 2] - agent characteristics, rationality
Mon, Jan 29: agent architectures, environments
Wed, Jan 31: Search [Ch. 3] (can skip sec. 3.6)

Fri, Feb 2: DFS, BFS, complexity analysis
Mon, Feb 5: iterative deepening
Wed, Feb 7: uniform-cost, greedy/best-first
Fri, Feb 9: A* [Ch. 4] (skip stuff on memory-bounded search, pp. 101-105, and GA's, continuous spaces, and online search, pp. 116-129)
Mon, Feb 12: Local Search (hill-climbing, simulated annealing, beam search)
Wed, Feb 12: Where do heuristics come from?; Constraint Satisfaction Problems [Ch. 5]
Fri, Feb 12: CSP algorithms and heuristics
Mon, Feb 19: Game Search [Ch. 6] (can skip pp. 145-150); minimax algorithm
Wed, Feb 21: expecti-minimax; alpha-beta pruning
Fri, Feb 23: board evaluation functions
Mon, Feb 26: Mid-term Exam I (covers Chapters 2-6)
Wed, Feb 28: Knowledge-based programming/agents, KR, Propositional Logic, syntax [Ch. 7]

Fri, Mar 2: semantics (model theory)
Wed, Mar 7: example of knowledge-base and inference for decision-making in the Wumpus World
Fri, Mar 9: resolution refutation proofs
Mar 12-16: (Spring break)
Mon, Mar 19: forward/backward chaining; satisfiability algorithms
Wed, Mar 21: Davis-Putnam, WalkSat; Homework #1 due
Fri, Mar 23: First-Order Logic [Ch. 8], syntax, semantics
Mon, Mar 26: model theory
Wed, Mar 28: (examples: set axioms, kinship axioms); Inference in FOL [Ch. 9], new inference rules for quantifiers
Fri, Mar 30: unification, proofs, resolution

Mon, Apr 2: forward-chaining, Rete, Jess (example: animals.clp); Homework #2 due
Wed, Apr 4: resolution in FOL, Herbrand's theorem; back-chaining, PROLOG
Fri, Apr 6: reading day (class cancelled)
Mon, Apr 9: Ontologies [Ch. 10], categories, measures, spatial relations, event calculus; Homework #3 due (skip situation calculus for now, as well as belief reasoning)
Wed, Apr 11: Exam #2 (covering Ch. 7-10)
Fri, Apr 13: default reasoning and alternative KR systems: non-monotonic logic, frames, semantic nets, description logics [Ch. 10.6-10.8]
Mon, Apr 16: probabilistic reasoning [Ch. 13.1-13.2, 13.6]
Wed, Apr 18: Bayesian networks [sec. 14.1]
Fri, Apr 20: Situation calculus [sec. 10.3, pp. 328-334]
Mon, Apr 23: Planning [Ch. 11], STRIPS operators; Homework #4 due
Wed, Apr 25: goal-regression (see section 3.2 of Weld (1994))
Fri, Apr 27: partial-order planning [sec. 11.3]
Mon, Apr 30: Learning - Candidate Elimination [sec. 19.1]; Homework #5 due
Tues, May 1: (last day of class); handed out take-home final

Mon, May 7: final exam, 9:00-10:00am (note: starting 1 hour later)

Links

• Loebner Prize - annual Turing Test competition (see the transcripts)
• Deep Blue - IBM's grand-master chess computer (see this paper for technical details on design, including search algorithms, hardware architecture, evaluation function, and so on)
• map of Romania
• Eliza - therapist chatterbot
• Map Four-Coloring Theorem
• Korf (1997) - paper on IDA* search for Rubik's cube
• Cyc - real-world open-source knowledge base
• Weld (1994) - section 3.2 contains a nice description of goal-regression