MP practicalities

Questions related to what you built in MP 1 and 2.

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
• Coning a self-driving car

Search

Example tasks

• In some detail: roadmap search, maze search, 8-puzzle, edit distance,
• Seen briefly: speech recognition, adventure game, Missionaries and Cannibals puzzle,

Basic search methods

• Search problem formulation: state space, initial state, actions, transition model, goal state(s), path costs
• Outline for search algorithms: frontier/queue, best/optimal path, visited states table, backpointers and reconstructing return path
• Breadth-first, uniform cost search, depth-first search, length-bounded DFS, iterative deepening
• What information should be stored in each state?

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 is a good heuristic? what makes one heuristic better than another?
• suboptimal search (non-admissible heuristics) and tie-breaking
• beam search

Details for each algorithm

• How does it manage its frontier/queue?
• Preventing loops and duplicative work
• What happens if we reach a state via a second, shorter, path?
• When does the algorithm halt and return its final result?
• When would each method be an appropiate choice, when would it be inappropriate, and why?

Compare advantages and disadvantages of each of these search methods

Robotics and 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, ...)
• links, joints, degrees of freedom, workspace
• 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?