MT1

Question 1

Holonomic constraint:

Answer 1

A constraint on just the position but not the derivatives.

Question 2

Plan

Answer 2

A sequence of states for a robot

Question 3

Feasibility

Answer 3

If a given sequence of states and the transition between them obeys kinematic/dynamic constraints.

Question 4

Correctness

Answer 4

If an algorithm outputs feasible plans

Question 5

Complete

Answer 5

If an algorithm always finds the solution when it exists

Question 6

L3 Controllability

Answer 6

For every state x, there exists a trajectory to state x

Question 7

L3 Fully actuated

Answer 7

Robot can command any instantaneous acceleration

Question 8

L4 “Terminating” Algorithm

Answer 8

An algorithm that runs in finite time.

Question 9

L4 Difference between Bug 2 and Bug 1?

Answer 9

Bug 2 draws a line and remembers if it’s making progress. Bug 2 is complete.

Question 10

L4 Difference between Dijkstra and A*?

Answer 10

A* uses a heuristic; admissible cost-to-go plus cost-to-come

Question 11

L5: Visibility Graph

Answer 11

Connect all vertices, choose path with lowest cost.

Question 12

L5: What is RRT?

Answer 12

1) Sample random location
2) Find nearest node to location
3) grow node to that location

Question 13

L5 What is RRT-Connect?

Answer 13

Greedy RRT where you make trees from start AND end

Question 14

L5 Is RRT:

1) Correct?
2) Complete?
3) Terminating?

Answer 14

Correct, complete over infinite time, not necessarily terminating.

Question 15

L5 What is probabilistic completeness?

Answer 15

Probability that feasible solution will be found as samples tend to infinity.

Question 16

L5 What is PRM?

Answer 16

Probabilistic roadmap.

1) Sample spaces at random; keep if allowed
2) Connect allowed points and use as roadmap

Question 17

L6 What is metric, topological, topometric, time-series maps?

Answer 17

Metric: preserves distances and angles
Topo: structure reduced to a graph
Topometric: fusion of two?
Time-series: Raw footage.

Question 18

L6 Occupancy grids

Answer 18

Discretized grid; free, blocked, unexplored.

Question 19

L6 What are octrees, quadtrees?

Answer 19

Variable-resolution occupancy grids.

Question 20

Octree/quadtree properties?

Answer 20

O(n) lookup, sensitive to small changes in position

Question 21

L6 Advantages, disadvantages of occupancy grids?

Answer 21

Advantage: O(1) lookup
Disadvantage: Doesn’t scale well with dimensions

Question 22

L6 How are Generalized Voronoi Graphs made?

Answer 22

Draw lines equidistant from both obstacles. Safe roadmap.

Question 23

L6 Homotopic paths

Answer 23

When one path can be deformed into another without passing over obstacles.

Question 24

L6 How to do scan alignment with known correspondences?

Answer 24

Minimize quadratic error function for each point: ||p - Rq+t||^2, all points

Question 25

L7 What are two main sources of error in mapping?

Answer 25

1) Uncertainty in dynamics

2) Noisy sensors

Question 26

L7 Odometry mean depends on ____?

Answer 26

Odometry mean usually depends on state and control

Question 27

L7 Sensor mean depends on ____?

Answer 27

Sensor mean depends on state

Question 28

L7 Goal of mapping?

Answer 28

To estimate the p(m | x(1 to t), z(1 to t)

Question 29

L8 Bayes Rule of Conditional Probability

Answer 29

p(A||B,C) = p(B||A,C) * p(A||C) / p(B||C)

Question 30

L8 Occupancy Grid: How to evaluate p(mij = 1 || x(1:t), z(1:t)) with Bayes Rule of Conditional Probability?

Answer 30

mij = A
z(t) = B
x(1:t) and z(1:t-1) = C

Question 31

L8 Occupancy grid: simplify the following:
p(z(t) || mij = 1, z(1:t-1), x(1:t)
and explain why

Answer 31

1) Current sensor doesn’t depend on past sensor measurements
2) Current sensor depends only on current state
p(z(t) || mij = 1, x(t))

Question 32

L12 EKF What are two ways to deal with nonlinear dynamics?

Answer 32

1) Monte Carlo sampling

2) Taylor expansion linearization

Question 33

L13 What are the dynamics, sensor, noise of KF?

Answer 33

L, L, Uni

Question 34

L13 What are the dynamics, sensor, and noise of EKF?

Answer 34

NL, NL, Uni

Question 35

L13 What are the dynamics, sensor, and noise of PF?

Answer 35

NL, NL, Multi

Question 36

L13: What are the main goals of PF resampling?

Answer 36

Kill off unlikely particles and pursue likely ones

Question 37

L13 What are the three consequences of PF resampling?

Answer 37

1) Particle variance goes does
2) Approximation error variance goes up
3) Particle deprivation in vicinity of state

Question 38

L13 What are three ways to avoid particle deprivation?

Answer 38

1) Don’t resample when few points contribute
2) Introduce random particles
3) Increase number of particles

Question 39

L15 When do you use D and when do you use I?

Answer 39

D is for seeing the near future

I is for dealing with systematic biases

Question 40

L15 What is integrator windup?

Answer 40

When system can’t correct error over time, builds a large control

Question 41

L15 How to limit integrator windup?

Answer 41

1) Keep low I gain
2) Limit I error values
3) Stop I when error outside range

Question 42

L15 What are three reasons not to use PIDs?

Answer 42

1) Valid for specific region of state space
2) Need to adjust gain for every control variable
3) Gain scheduling

Question 43

L15 What are three limitations of PID?

Answer 43

1) Requires known best reference
2) Sometimes dynamics are the primary constraint
3) Doesn’t account for actions within achievable control

Question 44

L17: What requirements does LQR have? Why are they necessary?

Answer 44

1) Dynamics are linear and known
2) Cost is quadratic
Leads to easy expression of next state and cost-togo

Question 45

L17: Out of A, B, Q, and R, which ones have to be positive definite? Why?

Answer 45

Q, R. Requires a positive cost at all times, or else minimization will yield weird results.

Question 46

What is a positive definite matrix?

Answer 46

One where the matrix is symmetric and its eigenvalues are positive.

Question 47

L10 Difference between smoothing and filtering?

Answer 47

Filtering processes as info comes; smoothing has all measurements an controls known in advance

Question 48

L10 What is Markov assumption?

Answer 48

That the current state is probabilistically inconditional of past states and controls (except for last)

Question 49

L10 What is static world assumption?

Answer 49

Current observation independent of past observations and controls