test2 Flashcards
what is localization
the problem of determining and tracking the robots position relative to a map of its environment
what are the two types of localization problems?
passive vs active and local vs global
what is passive localization
Interpret sensor data to determine the robots state, Algorithm on robot provides information on robots localization, but that algorithm does not drive the robot(see this more often)
what is active localization
choose actions designed to help determine the robots state, Localization algorithm is at the steering wheel
what is local localization
start with good information about the robots state, keep track of this knowledge as the robot moves around, eyes open at start then closed as moving around
what is global localization
start with no information about the robots state, try to eliminate this uncertainty
what is dudek-romanik-whitesides localization
Active global localization, lidar and a compass(can tell between rotated similar polygons) with no sensor noise, range sensor provides a visibility polygon of the robots state x, and if measured correctly there is only one spot where this exact polygon will be seen
what are the possible states
Set of points you can see from a line of sight from the robots location while staying in the Environment, the process of computing this set is hypothesis generation
what is the hypothesis generation algorithm
input: environment(n vertices) and visibility(m vertices) polygons, output: set of states that have that visibility polygon, O(mn) time(can be faster but take up more space if there are multiple queries), approx n/2 hypotheses, cant solve shortest path to localize.
what is visibility cell decomposition
divide environment by drawing rays outward from mutual vertices and incident edges
what is the hypothesis elimination algorithm
create an overlay(visibility cell) for all the candidates, choose a destination that crosses a ray in some but not all of the candidates, get new visibility polygon, eliminate candidates that dont match new reading, repeat until only one candidate remains. if destinations are chosen carefully, should only take more than k(candidates)-1 times as much as the optimal strat
what is the Kalman filter
a localization algorithm that maintains an estimate of the robots state, expressed as a mean and covariance matrix, is passive, local, and probabilistic
what is the state transition function associated with Kalman
xk+1 = f(xk, uk, thetak(action error))
what is the observation or sensing function
yk/sensor data = h(xk, observation error)
Why a linear gaussian system
a special class of robot models that can prove that the probability density over the state space is always a Gaussian no matter what
linear gaussian transitions
xk+1 = Axk+Buk+Gaction error
linear gaussian sensing
yk = Cxk+Hobs error
gaussian noise
both the action and obs errors are chosen randomly according to independent, zero-mean gaussian identities
kalman filter inputs
state(muk), square covariance matrix(sumk), action(uk), observation(yk), matrices(A,B,C,G,H), action and obs errors
kalman filter outpts
state(muk+1) and covariance matrix(sumk+1)
what is the extended kalman filter
takes a linear approximation of the system by taking partial derivatives of f and h which allows for kalman to be used on non linear systems. we do lose the guarantee that the probability is represented exactly, but generally works well in practice if the non-linearities arent too great
what is the histogram filter
a localization algorithm that maintains an estimate of the robots state, expressed as a collection of probabilities for individual cells, passive, local, and probabilistic
what is the particle filter
a localization algorithm that maintains an estimate of the robots state, expressed as a collection of samples, passive, local, and probabilistic
why do we need more algorithms beyond KF/EKF?
for if there are multiple likely options/non linear systems
what do transition models describe
transition models specify the probability distribution over the latest state variables given the previous values
what do observation models describe
A sensor (observation) model describes how the evidence (observed) variables depend on other variables
what is posterior distribution
keeping track of a probability distribution over the state space, given a history. provides and answer to the question “where am i”, based on things robot did and saw, where is robot likely to be
what is posterior updates
the update equation for posterior distribution, the long ass equation, has a scaling factor to ensure the probabilities add up to one
histogram filter posterior distribution
make a finite collection of cells, track the probability of each cell, use the update equation directly, could take up alot of time and memeory if cells made small to increase accuracy, as have to run equation for every cell(N^2), and most states will be zero
particle filter posterior distribution
track a finite set of samples, called particles, each with a state x and weight w, dont keep track of the probabilities, only the states that have a better chance of being where the robot is, have stacks where more than one particle has the same state
what is the particle filter algorithm
For each particle:
Assign weights to random states given the probability that what we saw matched with where we are(how likely is it that we wouldve seen this sensor reading), pretend s is the real state, if so how likely is it that we see what we saw
randomly choose with replacement a sample from the generated set(reinforces the data), with probabilities proportional to the weights. Get rid of particles with low weights, copy particles with higher weights(cliffnotes). add the sample to a new set.
what is SLAM
Simultaneous localization and mapping, the problem of using a mobile robot to build a map of its environment, since maps are hard to get
whats the basic idea of SLAM
a particle filter where each particle represents both a possible robot path and a possible map
what are the two steps of SLAM
-probabilistic mapping
-SLAM based on particle filters
why is SLAM hard?
you cannot separate localization and mapping, as localization usually requires a map agaisnt which to match the robots observations, and mapping usually requires the robot to be localized, so the locations of observed obstacles can be recorded
what does mapping look like with known robot locations?
you have an occupancy grid, where ml = 1 if cell l is an obstacle, and ml = 0 if cell l is free, and we want the probability that each cell is occupied, given the robots hostory of observations and states
how do you update the occupancy grid probabilities?
use the update rule, which depends on the likelihood of a given cell being free or an obstacle, given the robots current location and observation(left side), and the occupancy probability, given the history at the previous stage
what is an observation model?
for an ultrasonic range sensor, depends on the measured distance, and the angle and distance between occupancy grid and sensors emitter
what is rao-blackwellization?
Factoring the state space into one part we sample(path) and one part we derive(map). Instead of maintaining particles for the whole space, which would require an insane amount of memory, maintain particles for the space of robot paths, and given this path we can compute the most likely map
what is the Rao-Blackwellized particle filter?
-for each particle, compute the most likely map
-use this map along with the observation model to compute the weight for each particle
-resample using these weights as in the standard particle filter
why are cameras good for robots?
provide lots of information, small, light, cheap, energy efficient, many aspects of human environment designed with vision in mind.
why are cameras a challenge for robots?
can be challenging and computation intensive to extrat useful info from camera data, such as depth and correspondence
what is the intensity matrix
each image is an array of intensity values, either a single value at each position(greyscale) or different values for a small number of channels(rgb)
what is the main issue with cameras?
losing a dimension, fe the pinhole camera takes a 3d place and produces a 2d image
what is the purpose of camera callibration
to determine the projection matrix for a given camera, common to use a flat checkerboard with known square sizes that provide constraints on the matrix, want to find a matrix that minimizes the error of these constraints
what is stereopsis?
use multiple cameras(or views from same camera) then find one or more pairs of points that correspond between the two images
what is the baseline in stereopsis?
the distance between the cameras, comes with a tradeoff: if cameras are closer together, correspondence is easier(images are similar) but positioning errors are magnified, if they are farther apart, correspondence is harder but results may be more accurate
what is ground plane knowledge?
if we know that a certain plane(the ground) contains the point we are interested in, enough to use one camera to recover depth
other hardware for recovering depth
rgbd sensor(project infrared dots and measure distortion)
what problem does correspondence try to solve
matching objects from different images to one another
correspondence with histograms
represent an object by the histogram of its colors, useful when objects are distinguished by their combination of colors
correspondence with features
a feature is an image location that is stable under small changes to the image and in the viewpoint, a feature detector is an algorithm that finds a small, manageable number of features in a given image. dont always need to know what they are as long as they are consistent
what is a ros parameter
a configuration value of a node. You can think of parameters as node settings
what is a ros service
another method of node communication, call and response method, many clients only one server
what is ros bag
records and can play data published from topics in your system
