August 21 (Fri), 2009 HW1 assigned, due Wednesday, August 26, 2009. Administrative information: textbook, syllabus, grading policy. Definitions of AI.
August 24 (Mon), 2009 Q1. Q1 is based on a video of a panel on AI at the Charlie Rose show: http://www.charlierose.com/view/interview/1128. Discussion of the video.
August 26 (Wed), 2009 HW1 collected, Ch.1 [P], with emphasis on desiderata of representations. Issues from Ch.1 [P]: Succinctness (conciseness) of representations: state-space, features or propositions, objects and relations; Bounded rationality and anytime algorithms; complexity of some representational frameworks.
August 28 (Fri), 2009 HW1 returned, Ch.1 concluded. Four application domains: autonomous delivery robot, diagnostic assistant, trading agent, intelligent tutoring systems, listing example inputs (prior knowledge, past experience, goals, ond bservations) and sample activities. Ch.2 [P] started. Example of trading agent. Percept and command traces. Causal transductions. Belief states.
August 31 (Mon), 2009 Brief discussion of the PEAS (Performance Measure, Environment, Actuators, Sensors) agent model of [AIMA-2]. (The slides for PEAS are in the lecture notes for the fall 2008 offering of CSCE 580.) Ch.2 [P] ("Agent Architectures and Hierarchical Control") completed.
September 2 (Wed), 2009 The state-space approach to problem solving. Uninformed (blind) search: DFS, BFS, Dijkstra's algorithms (first part of Ch.3 [P]).
September 4 (Fri), 2009 HW2 assigned, due on Friday, September 11: exercises 3.(except (c)), 3.8, 3.9 (a only) [AIMA]: handout with problems given in class. Iterative deepening DFS. Heuristic (informed) search: admissible heuristics, (greedy) best-first search, A*.
September 9 (Wed), 2009 More on A*. Proof of admissibility (Proposition 3.1 [P]). The monotonicity (equivalently: consistency) restriction prevents re-expansion of nodes: proof. Admissible heuristics as solutions of auxiliary (relaxed) (sub)problems. Heuristics computed by problem relaxation are monotone (proof). Students are encouraged to attend two talks by Jeffrey Mark Siskind: on Friday from 1430-1530 in 2A31, and on Monday from 1010-1100 in 2A21. The second talk is an introduction to functional programming designed for AI students and takes place during CSCE 330.
September 11 (Fri), 2009 HW3 assigned: exercises 3.3 and 3.13 [P], due Wednesday, September 16. Example of A* use [AIMA]. Depth-first Branch-and-Bound with an example [P]. Other memory-bounded heuristic search algorithms: iterative deepening A* (IDA*), recursive best-first search (RBFS), simple memory-bounded A* (SMA*) [AIMA]. Island-driven search, dynamic programming, with an illustration of its use on stage graphs [P]. Chapter 3 (States and Searching) [P] completed. Students are encouraged to attend two talks by Jeffrey Mark Siskind: on Friday from 1430-1530 in 2A31, and on Monday from 1010-1100 in 2A21. The second talk is an introduction to functional programming designed for AI students and takes place during CSCE 330.
September 14 (Mon), 2009 HW2 returned. J.J. Shepherd presents a talk based on a paper on route planning using A* that he submitted for a conference. Details to follow.
September 16 (Wed), 2009 HW3 due date changed to Friday, September 18. HW4 assigned: exercise 3.4 [P] due Wednesday, September 23. Detailed discussion of issues concerning search algorithm and exposed by Exercise 3.3 in HW3, such as the difference between heuristic depth-first search and best-first search.
September 18 (Fri), 2009 HW3 collected. I request that two graduate student present Backtracking Search Vs. Variable Elimination for Propositional Satisfiability. The student presentaion link on the course web site is now active. Features and Constraints (Ch.4 [P]) through initial discussion of arc consistency.
September 21 (Mon), 2009 HW3 graded and discussed in class. Several good questions.
September 23 (Wed), 2009 MT1 will be on Friday, September 25. HW4 collected. Graduate students must choose a topic for presentation and a team of two students from the Student Presentations list (linked to the course web site) by Friday, September 25. Features and Constraints (Ch.4 [P]): the generalized arc consistency algorithm with examples run on AISpace; a little relational algebra and variable elimination to solve constraint problems. Recall that Poole and Mackworth's AISpace site is linked to the site for [P], which in turn is linked to the website for the course.
September 25 (Fri), 2009 MT1.
September 28 (Mon), 2009 MT1 returned. MT1 answered discussed. HW5 assigned: Exercises 4.1, 4.2, 4.3, 4.11 due Monday, October 5, 2009. Variable elimination. Nonserial dynamic programming as a technique for solving discreate optimization problems. (Notes used for this are linked to the course web site.)
September 30 (Wed), 2009 HW4 returned and discussed. Discovering heuristics. Sliding-block puzzles. Problem relaxation, pattern databases, linear conflict, using a presentation from the Fall 2008 edition of the course.
October 02 (Fri), 2009 PR1 handout given. PR1 assigned: exercises 1,4,6 from handout. HW5 due date changed to Wednesday, October 7, 2009. Discussion of crossword puzzle prohlems (similar to those of exercises 4.1 and 4.3 in HW5). Use of AISpace applet for constraint satisfaction approaches to CSPs: examples. Domain splitting, with examples (including one using the constraint satisfaction CSP applet in AISpace). Local search for CSPs: algorithm of Figure 4.6; random initialization, random restart (try), local search (walk); special cases: random sampling and random walk. Conflicts. Iterative best improvement. Greedy descent variants: choice of variable and value. Continuous domains for variables: gradient descent and gradient ascent.
October 05 (Mon), 2009 HW6 assigned, due Friday, October 16, 2009: exercises 4.4, 4.5, 4.6 [P]. Ch.4 [P] concluded. Ch.5 [P] (Propositions and Inference) started: intrepretations, entailment, models.
October 07 (Wed), 2009 Jingsong Wang presents the design and implementation of several search algorithm (depth-first, breadth-first, best-first) in Java.
October 12 (Mon), 2009 Due date for PR1 changed to midnight between Thursday, October 15, and Friday, October 16. Due date for HW6 changed to Monday, October 19. These changes were announce by an email message sent later in the day. Presentation by Andrew Smith and John Flowers on IDA* and Memory-Bounded Search Algorithms.
October 14 (Wed), 2009 The propositional calculus. Hilbert-style presentation: three axiom schemata, one rule of inference (modus ponens). Propositions and inference (Ch.5 [P]). Slides from [P]: axiomatizing the electrical building wiring diagnostic domain using definite clauses.
October 16 (Fri), 2009 The propositional calculus, ctd., with slides from [P]: soundness and completeness of inference procedures. Definite clauses. Bottom-up procedure. Consequence set. Soundness of the bottom-up procedure. Minimal models. Completeness of the bottom-up procedure. Answer clause. Query. Top-down procedure. Search tree for the top-down procedure. Askable atoms. How and why. Debugging definite knowledge bases. Top-down procedure.
October 19 (Mon), 2009 Due date for HW6 changed to Wednesday, October 21. Integrity constraints (impossibility axioms, indefinite clauses). Horn clauses. Negative and disjunctive conclusions. Algorithm for satisfiability of propositional Horn clauses (Uwe Schoening, see notes on courses web site).
October 21 (Wed), 2009 HW6 collected. AILog: discussion of how to install, where the documentation is, some basic features, loading knowledge bases, tell and ask, some knowledge-level debugging features. Students are strongly encouraged to installed AILog and SWI-Prolog on their computers.
October 23 (Fri), 2009 Introduction to Consistency-based and Explanation-based (i.e., abductive) diagnosis. Consistency-based diagnosis. Assumables. Conflicts. Diagnoses as hitting sets of conflicts. AILOG example of the diagnoztic assistant: create_nogoods, and nogoods. Top-down algorithm for computing conflicts.
October 26 (Mon), 2009 Bottom-up algorithm for computing conflicts. Clark's completion and negation as failure. Acyclic definite clauses and top-down interpreter with negation as failure.
October 28 (Wed), 2009 Complete knowledge bases, negation as failure, bottom-up and top-down interpreters for them. Abduction.
October 30 (Fri), 2009 HW7: Exercises 5.2, 5.3, 5.6, 5.7, 5.8, 5.9, 5.10, 5.11, 5.17, 5.18(part a only), due Monday, November 9. 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. Discussion of the "choose" instruction in the context of the bottom-up negation as failure consequence finding algorithm (Figure 5.12 [P]), based on student comments and correspodence with David Poole. Abduction. Causal models: interventions. Chapter 5 completed.
November 2 (Mon), 2009 Reasoning Under Uncertainty (ch.6 [P]): Probability (6.1 [P]). The possible world semantics; the axioms of Kolmogorov. Other models of the axioms of Kolmogorov: classic, limiting frequency, subjective.
November 4 (Wed), 2009 Probability (6.1 [P]), concluded: conditional probability, observations, conditioning, the chain rule. The "definition" of conditional probability is an axiom. Introduction to information theory: codes, entropy.
November 6 (Fri), 2009 Independence (6.2 [P]) and introduction to Bayesian networks.
November 9 (Mon), 2009 HW7 due date changed to Friday, November 13. Discussion of issues related to the exercises for HW7.
November 11 (Wed), 2009 Bayesian networks and their construction.
November 13 (Fri), 2009 Discussion of some issues related to exercise 5.8 [P]. HW7 date changed to Monday, November 16. Naive Bayes classifiers.
November 16 (Mon), 2009 HW7 collected. Probabilistic inference: variable elimination, Section 6.4.1 [P].
November 18 (Wed), 2009 Discussion of exercises 5.10 and 5.11 [P] using AILog.
November 20 (Fri), 2009 HW8 assigned: exercises 6.2, 6.3, 6.4 [P] due Monday, November 30. Variable elimination complete, with bucket elimination example. Stockastic simulation: forward and rejection sampling only. Markov chains and Hidden Markov models.
November 23 (Mon), 2009 HW9 assigned: Exercises 12.1, 12.15, 12.16 [P] due Friday, December 4. Individuals and Relations (First-order logic): Introduction, Symbols and Semantics, Datalog (Ch.12 [P] through 12.3).
November 30 (Mon), 2009 HW7 graded, but not returned (forgot!). HW8 due date delayed to Wednesday, December 2. Discussion of exercise 6.4. More Datalog. Examples. Proof procedures: instances, substiturions, Herbrand minimal models, bottom-up procedure, SLD-resolution with variables, unification. Examples. Function names. Lists (briefly).
December 2 (Wed), 2009 HW8 collected. The resolution refutation proof method for first-order logic. Handout from [AIMA-2]. Examples from 1980's Nilsson's book (_Principles of Artificial Intelligence_, Tioga Publishing).
December 4 (Wed), 2009 Student presentation (Brad Dunbar, Shamik Roy Chowdhury) of Bucket elimination (resolution vs. search) for propositional satisfiability. End-of-course questionnaire.