Schedule

1. [M 8/30] First half: introduction, syllabus, course information.

   Second half: introduction to Scheme, values, mathematical procedures, variables, quoting and literal expressions, defining procedures.

2. [R 9/2] First half: characteristics of environments, agent structures, structuring problems for search. Exercise 1.

   Second half: Scheme — defining local variables with let and let*, predicates, boolean values and operators, conditionals (if, cond, case), list operations, numerical recursion.

3. [R 9/9] Scheme — review of conditionals and list operations, recursion with lists, many ways of writing the list-head procedure, recursion patterns.

4. [M 9/13] First half: structuring problems for search, four characteristics of searches, state space versus search tree, breadth first search (BFS), depth first search (DFS), uniform cost search (UCS). Quiz 1.

   Second half: Scheme — finished recursion patterns; procedures as arguments to procedures, map, apply, lambda.

5. [R 9/16] Review: four characteristics of searches, state space versus search tree, BFS, DFS, UCS.

   First half: complexity analysis for BFS, DFS, and UCS. Depth-limited search (DLS), Iteative-deepening search (IDS), and Bidirectional search.

   Second half: Scheme — implemented missionaries & cannibals problem in class.

   Returned A1-written and Q1.

6. [M 9/20] First half: finished missionaries & cannibals and BFS implementation in Scheme. Avoiding repeated states. Searching with partial information (in particular, sensorless problems and belief states with vacuum cleaner world example and robotic tray tilting video).

   Second half: Introduction to heuristic searches, heuristics, best-first search framework, greedy search, uniform cost search, A* search.

7. [R 9/23] First half: review of blind search, review of heuristic search from monday, open/closed list formulation of A*, Exercise 2, went over quiz 2 solutions.

   Second half: Heuristics for A*, creating heuristics, admissibility, monotonicity, dominance of heuristics, combining multiple admissible heuristics, using relaxed versions of a problem to create admissible heuristics.

   Returned Quiz 2.

8. [M 9/27] First half: Heuristics, creating admissible heuristics via relaxed problems, heuristics using pattern databases (for subproblems) and disjoint pattern databases, heuristics using linear combinations of feature "detecting" functions. Examples illustrated using the 8-puzzle and included Nilsson's sequence score. Dominance of heuristics. Creating heuristics for the A3 sliding block puzzles.

   Second half: Wrapped up heuristic search (except for memory limited versions of A* which we'll cover later) — computational complexity and completeness of greedy search; completeness, optimality, and optimal efficiency. Quiz 3.

   Returned Exercise 2.

9. [R 9/30] First half: Proof of optimality of A*, introduction to game playing search, solutions for quiz 3.

   Second half: minimax search, perfect and imperfect decisions, minimax search with a depth cutoff, evaluation functions for game states, basic idea of alpha-beta pruning.

   Returned Quiz 3.

10. [M 10/4] First half: Review of search for game playing — types of games, minimax search, perfect versus imperfect decisions (search entire game tree versus search with depth cutoff), evaluation functions. Completed "intuitive" alpha-beta minimax example, alpha-beta minimax algorithm, alpha-beta minimax example, Exercise 3.

    Second half: evaluation functions for game playing, computational complexity of alpha-beta minimax, issues/problems in game-playing search (horizon effect, quiescent states/search, singular extensions, forward pruning). Quiz 4.

11. [R 10/7] First half: finished game playing search — computational-complexity of alpha-beta minimax, approaches to creating evaluation functions, expectimax. solutions to Quiz 4

    Second half: introduction to constraint satisfaction problems, assignment problems, example problems (n-queens, map coloring, circuit board routing), dumb application of blind search, backtracking, forward checking.

    Returned Quiz 4

12. [T 10/12] First half: Review of constraint satisfaction problems, constructive approaches using blind search — forward checking, constraint propagation (with 4-queens problem examples)

    Second half: Heuristics for constructive approaches (minimum remaining values, degree, least constraining value). Repair approaches — iterative improvement using the min-conflicts heuristic (with middle east map-coloring example). Quiz 5.

13. [R 10/14] First half: Exercise 4 (forward checking), iterative improvement algorithms, hill climbing, issues with hill climbing, random-restart hill climbing.

    Second half: Genetic algorithms, simulated annealing.

    Returned Quiz 5, A4p1, A3p8.

14. [M 10/18] First half: Recap of iterative improvement algorithms (hill climbing and relatives, simulated annealing, genetic algorithms), local beam search, local search in continuous spaces.

    Second half: memory bounded A* search — IDA*, RBFS Quiz 6.

15. [R 10/21] First half: Exercise 5 (heuristics for constructive approaches to CSP's), review of IDA* and RBFS, Quiz 6 solutions.

    Second half: SMA*, Introduction to Logic (very brief).

    Returned Quiz 6.

16. [M 10/25] First half: Introduction to Logic, propositional logic, inference rules, proof exercise, entailment exercise, definitions of soundness and completeness.

    Second half: Quiz 7

17. [R 10/28] Inference in propositional logic

    Returned Quiz 7.

18. [M 11/1] First half: Review of inference in propositional logic, forward chaining, backward chaining examples.

    Second half: Resolution proofs, Exercise 6, Quiz 8.

19. [R 11/4] First order logic, quantifiers, CNF, forward and backward chaining

    Returned Quiz 8.

20. [M 11/8] First half: First order logic

    Second half: decision trees and decision tree learning

21. [R 11/11] First half: Wrap up of first order logic, Exercise 7.

    Second half: Review of decision tree learning, dealing with missing attributes, discretizing continuous-valued attributes.

    Returned Quiz 9.

22. [M 11/15] Finish decision trees (pruning). Probability, Bayesian classifiers.

    Quiz 10.

23. [R 11/18] (Rational) Preferences, Utilities, maximum expected utility, Sequential decision problems, policies, value iteration. (this material is from sections 16.1-3 and 17.1-2

    Returned Quiz 10.

24. [M 11/22] Sequential decision problems, policy iteration, Reinforcement learning, passive reinforcement learning techniques (direct utility estimation, adp, temporal differencing)

25. [M 11/29] Reinforcement learning: review of passive reinforcement learning, active reinforcement learning, exploration versus exploitation, Q learning.

26. [R 12/2]