Historical trivia

What were the following (in just a couple words)? When and where were they developed?

• Shakey and Blocks world
• Waltz line labelling
• STRIPS

Search

You've done an MP on this, so can be expected to answer quite detailed questions, e.g about A*.

Key examples: graph search, maze search, Missionaries and Cannibals puzzle. 8-puzzle

Basic search methods

• Search problem formulation: initial state, actions, transition model, goal state(s), path cost, state space
• Outline for search algorithms: frontier, explored (done) states, best path, avoiding loops, storing or reconstructing return path
• Uninformed search strategies: breadth-first, uniform cost search, depth-first, iterative deepening, bidirectional

Edit distance (problem and algorithm)

A* search

• basic definitions and algorithm
• definitions of admissible and consistent, how do they relate? why is consistency useful?
• returns optimal path if heuristic admissible
• what makes one heuristic better than another?
• greedy search: how does it differ from A*? how can it fail?
• weighted A*

Comparison of search methods

• Advantages and disadvantages of each of these search methods compared to the others

Constraint satisfaction problems

Key examples (be familiar with basic rules)

• n-queens, map/graph coloring, Sudoku, Cryptarithmetic, Waltz line labelling
• Graph coloring is NP-complete.

Backtracking search (DFS)

• Variable assignments can be done in any order, search is to a known depth
• Why isn't looping a worry?
• Heuristics for variable and value selection: most constrained/most constraining variable, least constraining value
• Forward checking, constraint propagation
• AC-3 algorithm

Hill-climbing

• how it works (high-level idea only)
• how it differs from backtracking search

Planning

• State and action representation
• Preconditions and effects (postconditions)
• Situation space vs. plan space planners
• Forward and backward planning
• Sussman anomaly, interleaved planning
• Partial order planning: the idea, plan modification operations
• The Frame Problem
• Towers of Hanoi takes time exponential in input size (number of rings)

Configuration space

You've done an MP on this, but the math/geometry turns evil very fast. So expect concrete 2D problems involving relatively simple situations.

• Example configuration spaces: circular robot, n-link arm, rectangular robot with/without rotation.
• Sketch, or answer questions about, the configuration space for a (very simple) robot motion planning problem.

General knowledge (i.e. superficial only)

• types of robots (e.g. arms, moving carts, snakes, ...)
• ideal robot path: short but also smooth, safe
• graph-based planning: visibility graphs, cell decompositions, generalized Voronoi diagrams

Probability

The MP for this is still in the future. So expect straightfoward questions about definitions and proving very simple lemmas.

• Random variables, axioms of probability
• Joint, marginal, conditional probability

Naive Bayes (basic definitions only)

The MP for this is still in the future. So expect straightfoward questions about definitions and proving very simple lemmas.

• Bayes rule
• Likelihood, prior, posterior
• argmax operator
• Maximum a posteriori (MAP) esimate, Maximum likelihood (ML) estimate, factoring out P(evidence)
• How does prior affect these estimates?
• Independence and conditional independence
• Basic Naive Bayes model: suppose we have several conditionally independent pieces of evidence, how do we combine these to calculate P(cause | evidence)? (Just the main equation.)

Not on exam

The following material is NOT ON THIS EXAM

Items that won't be covered:

• Historical survey material, except where explicitly noted above

Items that will be on midterm 2 (even though they may have been partly covered in lecture before midterm 1).

• Further details of Naive Bayes, esp. anything to do with implementation details.
• Bayes networks