Logistics

• The midterm exam will be in class on Wednesday, 05 MAR.
• The exam will open book, open notes.
• Coverage: lectures through 03 MAR; assigned reading in R&N (Chs. 1-12), Turing, Braitenberg; Problem Sets 1-6; MiniPS 1.
• Study: read/review, problems/solutions, old exam, chapter summaries, formula sheets
• 491: you will have to do an extra problem; extra material includes G problems and assigned readings

• Four Approaches to AI
• History of AI
• State of the Art

• Agents and Environments
• Rationality
• Performance, Environment, Actuators, Sensors
• Properties of task environments:
  • fully/partially observable, deterministic/stochastic, static/dynamic, ...
• Agent programs/architectures: reflex; model-, goal-, and utility-based; learning
• Vehicles: S/R functions, logic, evolution, ...

• Problem Specification
  • states, initial state, successor function, goal test, path cost
• General Search Algorithm
• Performance Metrics: completeness, optimality, time/space complexity
• Uninformed Search: BFS, UCS, DFS, Depth-limited S, IDS, Bidirectional

• Informed Search and Heuristics
• Greedy BFS
• A*: admissible, consistency/monotonicity (and implications)
• Heuristic Functions: relaxed problems, max, pattern databases
• Local Search: gradient methods, beam search, simulated annealing, GAs

• Constraint Satisfaction Problems
  • definition, backtracking, forward checking, heuristics (MD, MRV, LCV)
• Min-Conflicts

• Games and Game Trees
• Optimal Decisions, Minimax
• Alpha-Beta Search/Pruning
• Games in practice: depth limits, evaluation funcs., horizon effect, quiescence
• Games with Chance
• State-of-the-Art in Games

• Logic: semantics, models, sound, complete, entailment
• Propositional Logic: syntax, truth tables, inference, proof, valid, satisfiable
• Reasoning Patterns, Resolution Algorithm, CNF Form
• Satisfiability Algorithms: DPLL, GSAT, WALKSAT
• Horn Clauses, AND/OR, Chaining
• Circuit-based agents

• STRIPS Planning operators, forward, backward, recursive, GraphPlan
• Planning in Practice: constraints, nondeterminism, multiple agents