1/105
Looks like no tags are added yet.
What are probabilistic robotics?
Modelling uncertainty in motion and sensing with probability distributions instead of single values
What is the belief bel(x_t)?
The robot's probability distribution over its state given all measurements and controls so far: p(x_t | z_1:t; u_1:t)
What can be part of the robot state?
Everything the robot models about itself and the world e.g. pose (x; y; theta) velocity and landmark positions
What is a robot pose?
Position and orientation of the robot: (x; y; theta) in a world frame
What is control data u_t?
The action commanded at time t e.g. drive distance or turn angle; treated as known
What is an observation z_t?
A sensor measurement at time t e.g. distance and bearing to a landmark
What does the Markov assumption say?
The current state depends only on the previous state and control; the measurement depends only on the current state
What is Bayes' rule?
p(x|z) = p(z|x) p(x) / p(z); posterior is likelihood times prior normalised
What is the law of total probability and where is it used?
p(x) = integral of p(x|y) p(y) dy; used in the Bayes filter prediction step
What is a Bayes filter?
Recursive state estimator with two steps: predict with the motion model then correct with the observation model
What happens in the prediction step of a Bayes filter?
Push the belief through the motion model p(x_t | x_t-1; u_t); belief becomes more uncertain
What happens in the correction step of a Bayes filter?
Multiply the predicted belief by the measurement likelihood p(z_t | x_t) and normalise; belief becomes more certain
What is the prior p(x_0)?
The belief about the state before any measurements
What is the motion model?
p(x_t | x_t-1; u_t): distribution of the new pose given the old pose and the control
What is the observation model?
p(z_t | x_t; m): likelihood of a measurement given the pose and the map
What is a particle filter?
Sample-based Bayes filter that represents the belief by a set of weighted state samples (particles)
What does one particle represent?
One hypothesis of the robot state; in my code a row (x; y; theta) of the array P
What is importance sampling?
Draw samples from a proposal distribution and weight them by target/proposal to represent the target distribution
What is the proposal distribution in MCL?
The motion model; particles are moved by sampling it and then weighted by the observation likelihood
What does an importance weight measure?
How well a particle explains the measurement; proportional to p(z_t | x_t)
What does resampling (the selection step) do?
Draw a new particle set with probability proportional to the weights; removes unlikely particles and duplicates good ones
What is weight degeneracy?
After a few updates almost all weight sits on one or a few particles; resampling fixes this
What is the effective sample size and what does it tell you?
N_eff = 1 / sum(w_i^2) for normalised weights; low value means degeneracy and is a signal to resample
How does systematic (low-variance) resampling work?
One random offset then N evenly spaced picks along the cumulative weights; lower variance than N independent draws
What is particle deprivation?
Too few particles near the true state so the filter cannot recover; worse with few particles or too little noise
What are the steps of the bootstrap particle filter?
Initialise; sample from the motion model; weight with the likelihood; resample; repeat
What is Monte Carlo Localisation (MCL)?
Particle filter localisation with a known map
What are the benefits of MCL?
Simple to implement; handles multimodal and non-Gaussian beliefs; global localisation possible
What is global localisation?
Finding the pose with no initial guess; particles start spread over all possible poses
What is position tracking?
Keeping an already known pose up to date; belief stays concentrated
What is the kidnapped robot problem?
The robot is moved without knowing it; the filter must detect this and recover
How does augmented MCL work?
Tracks short and long term average weights (w_fast and w_slow) and injects random particles when w_fast drops below w_slow
What does KLD sampling do?
Adapts the number of particles: many when the belief is spread out and few when it is concentrated
What is the map m in localisation?
Known description of the environment e.g. landmark positions in world coordinates
What is the world coordinate system in my code?
Fixed frame in the arena; L1 is the origin and the box centres are 440 x 340 cm apart
What is the robot coordinate system?
Frame attached to the robot (axle centre) with x pointing forward
What is the sensor coordinate system?
Frame attached to the camera or sonar; offset from the robot frame (camera 21 cm ahead of the axle)
How do you transform a point from sensor to robot to world coordinates?
Add the sensor offset in the robot frame then rotate by theta and translate by (x; y)
What is a rigid body transform?
Rotation plus translation; preserves distances and angles
What is the 2D rotation matrix?
[[cos t; -sin t]; [sin t; cos t]]; rotates a point by angle t
How does the odometry motion model decompose a move?
Into rot1 then trans then rot2; each corrupted by noise
What do the noise parameters alpha1-alpha4 do?
Scale motion noise from rotation and translation; hard to calibrate exactly so reasonable estimates are enough
Why is motion noise modelled as Gaussian?
Total error is a sum of many small independent errors so by the central limit theorem it is roughly Gaussian
Why can slightly too much motion noise be a benefit?
It keeps particle diversity and helps the filter recover from model errors
How do you sample the motion model for a particle?
Draw noisy rot1 trans rot2 and apply them to get a new pose sample
What is a landmark observation model?
Gaussian likelihood on the error between measured and expected distance and bearing to a landmark
How do you combine the likelihood of several landmarks?
Assume independence: multiply their likelihoods (sum of log-likelihoods)
Why use log-weights?
Summing log-likelihoods instead of multiplying probabilities avoids numerical underflow
What is differential drive?
Two independently driven wheels; turning comes from different wheel speeds
What is a digital image?
An M x N array of pixel values sampled from a continuous light intensity function
What are pixel coordinates?
Row and column (or u and v) position in the image; origin usually top left
What is the pinhole camera model?
Light rays pass through one point; a 3D point (X; Y; Z) projects to x = f X / Z and y = f Y / Z
What is perspective projection?
Mapping 3D points to the image plane; far objects appear smaller (division by depth Z)
What is the focal length f?
Distance from the pinhole to the image plane in pixels; in my code f = 1315 calibrated in Ex4
How did you calibrate the focal length?
Place a marker of known size X at a known distance Z and measure its image size x; f = x Z / X
What is the intrinsic matrix K?
[[f; 0; cx]; [0; f; cy]; [0; 0; 1]]; maps camera coordinates to pixel coordinates
What is the principal point?
Where the optical axis hits the image (cx; cy); about (820; 616) in my code
What are the extrinsic parameters?
Rotation and translation from the world frame to the camera frame
Why use homogeneous coordinates?
Add an extra coordinate (x; y; 1) so projection and translation become matrix multiplications
What is a homography?
3x3 matrix mapping points on one plane to another plane (e.g. a flat marker to the image); 8 degrees of freedom
What is camera calibration?
Estimating intrinsic (and distortion) parameters e.g. with a checkerboard or known marker
What is lens distortion?
Deviation from the pinhole model (radial or tangential); straight lines appear curved
What is an ArUco marker?
Square binary fiducial with an ID; OpenCV detects it and estimates its pose
How does ArUco pose estimation work?
From the 4 marker corners the known marker size and K OpenCV solves for rotation and translation vectors (rvec and tvec)
How do you get distance and bearing from tvec?
Distance = length of tvec; bearing = atan2 of the sideways and forward components
How does an ultrasonic sonar work and what are its limits?
Measures distance by echo time of a sound pulse; cheap but wide beam and fails on angled surfaces
What is specular reflection and how does it affect sonar?
Sound hitting a surface at an angle bounces away so no echo returns; why my code sweeps ±20 degrees
Why take the median of 3 sonar readings?
It removes single outlier readings
How do camera and sonar and LiDAR compare?
Camera: rich and cheap but needs processing; sonar: simple and short range; LiDAR: accurate but expensive
What is path planning?
Finding a collision-free sequence of waypoints or actions from start to goal
What is wrong with naive collision avoidance (drive to goal and turn when blocked)?
It does not look ahead and can get trapped in local minima
What is configuration space (C-space)?
The space of all robot configurations; obstacles are inflated by the robot size so the robot becomes a point
Why inflate obstacles and by how much in my code?
So the robot can be treated as a point; CLEAR = obstacle radius + robot radius + 15 cm
What is an occupancy grid and its trade-offs?
Map as an array of cells marked free/occupied (or probability); simple to query but costs memory and has limited resolution
What is a list-of-obstacles map and why did I use it?
Map as a list of object positions and shapes; resolution-free and compact for few objects
What does breadth-first search (BFS) guarantee?
Explores the grid level by level; finds the shortest path in number of steps
How does depth-first search (DFS) explore?
Follows one branch as deep as possible first; not guaranteed shortest
How does A* choose which node to expand?
The node with lowest f = g + h; g is cost so far and h is the estimated cost to the goal
What is an admissible heuristic and why does it matter?
It never overestimates the true cost to the goal; guarantees A* returns an optimal path
How does a wavefront planner work?
Spreads distance values out from the goal over the grid; follow decreasing values to the goal
What is global planning?
Plan a full path to a far goal using a full map and global localisation
What is local planning?
Plan to a nearby intermediate goal using the local surroundings; replanned often
What is RRT?
Rapidly-exploring Random Tree: grows a tree from the start by sampling random points and extending toward them
What happens in one RRT extend step?
Sample a point; find the nearest tree node; step a fixed distance toward the sample; add it if collision-free
What is goal bias in RRT?
Sample the goal itself with small probability (10% in my code) so the tree grows toward it
Is RRT complete?
Probabilistically complete: the chance of finding a path if one exists goes to 1 as samples increase
Is RRT optimal?
No: plain RRT gives zigzag paths; RRT* rewires the tree and is asymptotically optimal
What is path shortcutting?
Smooth an RRT path by jumping directly to the furthest waypoint still reachable in a straight line
How do you collision-check a path segment?
Sample points along the line (every 5 cm in my code) and test if any lies inside an inflated obstacle
Why replan?
Recheck the path after each step and plan again if blocked; handles newly seen obstacles
What is sampling-based planning?
Planning by random sampling of the continuous space (RRT and PRM) instead of searching a grid
What is the KISS principle?
Keep It Simple Stupid; the rally advice to implement only what is needed
What is the architecture of my rally code?
Layers: reactive sonar avoidance; particle filter localisation; RRT detours; go_to decision loop over situations A-E
How does my code initialise the particles?
Ring of particles around the first seen landmark at the measured distance; one landmark only constrains you to a circle
Why does localised() need 2 landmarks?
One landmark gives a ring of possible poses; a second one breaks the ambiguity
What does my localised() test check?
At least 2 landmarks used; x and y std below 50 cm; heading agreement above 0.9
How does my code compute the pose estimate?
Mean of particle x and y; circular mean of theta via atan2(mean sin; mean cos)
What is the weakness of using the mean pose?
With a multimodal belief the mean can lie between clusters where no particle is
What is the motion model in my code?
Commanded move applied to every particle plus Gaussian noise of 2 cm + 5% of distance and 3 degrees + 10% of turn
What is the observation likelihood in my code?
Gaussian on distance error with sigma 10 cm + 8% of distance and on bearing error with sigma 10 degrees