MT1 Flashcards
Holonomic constraint:
A constraint on just the position but not the derivatives.
Plan
A sequence of states for a robot
Feasibility
If a given sequence of states and the transition between them obeys kinematic/dynamic constraints.
Correctness
If an algorithm outputs feasible plans
Complete
If an algorithm always finds the solution when it exists
L3 Controllability
For every state x, there exists a trajectory to state x
L3 Fully actuated
Robot can command any instantaneous acceleration
L4 “Terminating” Algorithm
An algorithm that runs in finite time.
L4 Difference between Bug 2 and Bug 1?
Bug 2 draws a line and remembers if it’s making progress. Bug 2 is complete.
L4 Difference between Dijkstra and A*?
A* uses a heuristic; admissible cost-to-go plus cost-to-come
L5: Visibility Graph
Connect all vertices, choose path with lowest cost.
L5: What is RRT?
1) Sample random location
2) Find nearest node to location
3) grow node to that location
L5 What is RRT-Connect?
Greedy RRT where you make trees from start AND end
L5 Is RRT:
1) Correct?
2) Complete?
3) Terminating?
Correct, complete over infinite time, not necessarily terminating.
L5 What is probabilistic completeness?
Probability that feasible solution will be found as samples tend to infinity.
L5 What is PRM?
Probabilistic roadmap.
1) Sample spaces at random; keep if allowed
2) Connect allowed points and use as roadmap
L6 What is metric, topological, topometric, time-series maps?
Metric: preserves distances and angles
Topo: structure reduced to a graph
Topometric: fusion of two?
Time-series: Raw footage.
L6 Occupancy grids
Discretized grid; free, blocked, unexplored.
L6 What are octrees, quadtrees?
Variable-resolution occupancy grids.
Octree/quadtree properties?
O(n) lookup, sensitive to small changes in position
L6 Advantages, disadvantages of occupancy grids?
Advantage: O(1) lookup
Disadvantage: Doesn’t scale well with dimensions
L6 How are Generalized Voronoi Graphs made?
Draw lines equidistant from both obstacles. Safe roadmap.
L6 Homotopic paths
When one path can be deformed into another without passing over obstacles.
L6 How to do scan alignment with known correspondences?
Minimize quadratic error function for each point: ||p - Rq+t||^2, all points
L7 What are two main sources of error in mapping?
1) Uncertainty in dynamics
2) Noisy sensors
L7 Odometry mean depends on ____?
Odometry mean usually depends on state and control
L7 Sensor mean depends on ____?
Sensor mean depends on state
L7 Goal of mapping?
To estimate the p(m | x(1 to t), z(1 to t)
L8 Bayes Rule of Conditional Probability
p(A||B,C) = p(B||A,C) * p(A||C) / p(B||C)
L8 Occupancy Grid: How to evaluate p(mij = 1 || x(1:t), z(1:t)) with Bayes Rule of Conditional Probability?
mij = A
z(t) = B
x(1:t) and z(1:t-1) = C
L8 Occupancy grid: simplify the following:
p(z(t) || mij = 1, z(1:t-1), x(1:t)
and explain why
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))
L12 EKF What are two ways to deal with nonlinear dynamics?
1) Monte Carlo sampling
2) Taylor expansion linearization
L13 What are the dynamics, sensor, noise of KF?
L, L, Uni
L13 What are the dynamics, sensor, and noise of EKF?
NL, NL, Uni
L13 What are the dynamics, sensor, and noise of PF?
NL, NL, Multi
L13: What are the main goals of PF resampling?
Kill off unlikely particles and pursue likely ones
L13 What are the three consequences of PF resampling?
1) Particle variance goes does
2) Approximation error variance goes up
3) Particle deprivation in vicinity of state
L13 What are three ways to avoid particle deprivation?
1) Don’t resample when few points contribute
2) Introduce random particles
3) Increase number of particles
L15 When do you use D and when do you use I?
D is for seeing the near future
I is for dealing with systematic biases
L15 What is integrator windup?
When system can’t correct error over time, builds a large control
L15 How to limit integrator windup?
1) Keep low I gain
2) Limit I error values
3) Stop I when error outside range
L15 What are three reasons not to use PIDs?
1) Valid for specific region of state space
2) Need to adjust gain for every control variable
3) Gain scheduling
L15 What are three limitations of PID?
1) Requires known best reference
2) Sometimes dynamics are the primary constraint
3) Doesn’t account for actions within achievable control
L17: What requirements does LQR have? Why are they necessary?
1) Dynamics are linear and known
2) Cost is quadratic
Leads to easy expression of next state and cost-togo
L17: Out of A, B, Q, and R, which ones have to be positive definite? Why?
Q, R. Requires a positive cost at all times, or else minimization will yield weird results.
What is a positive definite matrix?
One where the matrix is symmetric and its eigenvalues are positive.
L10 Difference between smoothing and filtering?
Filtering processes as info comes; smoothing has all measurements an controls known in advance
L10 What is Markov assumption?
That the current state is probabilistically inconditional of past states and controls (except for last)
L10 What is static world assumption?
Current observation independent of past observations and controls
