CS 440/ECE 448
Fall 2023
Margaret Fleck
Quiz 2 skills list
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?