CSCE 420 - Artificial Intelligence

Professor: Dr. Thomas R. Ioerger
Office: 322C Bright Bldg.
Phone: 458-5518
email: ioerger@cs.tamu.edu
office hours: Wednesdays, 3-4pm

TA: Wen Li
email: wen.li@neo.tamu.edu
office hours: Tu/Th 5:00-6:00, 311D Bright

Meeting: TR, 9:35-10:50 am, HRBB 113

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

Course Description (from TAMU course catalog): Basic concepts and methods of artificial intelligence; Heuristic search procedures for general graphs; game playing strategies; resolution and rule based deduction systems; knowledge representation; reasoning with uncertainty.

Prerequisites: CSCE 315 (Programming Studio) - Note, the real intention is that students have a solid understanding of data structures and algorithms before taking this class, as would be learned in CSCE 221.

Textbook

Russell, S. and Norvig, P. (2009). Artificial Intelligence: A Modern Approach. 3rd edition (blue cover). Prentice Hall.

Course Objectives

1. To learn about intelligent search methods and their role in building complex problem-solving programs.
   1. to learn how to formulate computational problems as search
   2. to learn how various search algorithms work
   3. to learn their computational properties (space- and time-complexity)
   4. to learn how heuristics can improve efficiency of search
2. To learn about knowledge representation techniques and methods for knowledge-based/intelligent decision-making in programs.
   1. to learn syntax and semantics of propositional logic and first-order logic
   2. to learn how inference algorithms work
   3. to learn the advantages of alternative knowledge respresentation systems
   4. to learn how to represent and reason about uncertainty using Bayesian probability
3. To gain exposure to traditional sub-fields of AI (automated deduction, planning, machine learning, natural language...).
   1. to learn how symbolic planning algorithms work
   2. to learn different decision-making architectures for intelligent agents
   3. to learn how machine learning can be used to generalize from experience/examples

• 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
• Modal logics, description logics, fuzzy logic
• Planning (goal-regression, STRIPS, frame problem)
• Uncertainty and Probability (Bayesian inference, belief nets, Markov decision problems)

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: 50% homework/programming projects, 50% exams. There will 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%, 70% for C, and so on, though these thresholds may be lowered depending on the performance of the class overall.

The penalty for late assignments is -5% per day (pro-rated over 24 hours).
After 10 days late, the deductions cease; the maximum loss of points is 50%. As long as you turn an assignment in by the end of the semester, it could still be worth as much as half-credit. This is to encourage you to eventually complete the assignment, even if you can't get it in on time initially.

Schedule:

Academic Integrity Statement and Policy

Americans with Disabilities Act (ADA) Policy Statement

Links

• notes on backchaining
• IBM's Jeopardy-playing WATSON, NY Times article
• Ch. 1, The Description Logic Handbook
• Ch. 2 from the Description Logic Handbook - Baader and Nutt
• Actions and Events in Interval Temporal Logic (1994). James F. Allen and George Ferguson. Journal of Logic and Computation.
• some background info on the Tile Puzzle - shows that half of randomized configurations are unsolvable
• PRIMES is in P. (Agarwal et al, 2004), perspective by Bornemann
• Satisfiability cliff
• jobs puzzle
• vision as CSP
• Deep Blue: 31-page paper describing implementation details
• TPTP Database - Thousands of Problems for Theorem Provers
• Naive Physics Manifesto - Ontology of Liquids Patrick Hayes, 1986
• first-order logic model theory
• 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
• wikipedia on Linear Programming
• application of CSP to job-shop scheduling
• jobs puzzle
• vision/3D interpretation - edge-labeling and Waltz constrain propagation (see section III)
• CSPLIB
• Stuart Russell's slides
• MAC