The quiz will cover material on search and robotics.

Historical and other trivia

We've seen a lot of trivia, most of it not worth memorizing. The following items are the exceptions. Be able to explain (very briefly) what they are and (approximately) what time period they come from.

• Shakey and Blocks world
• Boston Dynamics
• Google self-driving bike

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 excessive search and infinite loops, storing or reconstructing return path
• Uninformed search strategies: breadth-first, uniform cost search, depth-first, length-bounded DFS, iterative deepening, backwards, bidirectional

Edit distance (problem and algorithm)

A* search

• basic definitions and algorithm
• Manhattan vs. straight-line distance
• 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?

Variants of A*

• suboptimal search (i.e. with non-admissible heuristics)
• iterative deepening A*
• beam search

Comparison of search methods

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

Configuration space

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

• 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, probabilistic roadmaps
• how can search be complicated by big open areas? by narrow passages? by robots with more than a couple degrees of freedom?