SLAM is a technique used by robots and autonomous vehicles to build up a map within an unknown environment (without a priori knowledge) or to update a map within a known environment (with a priori knowledge from a given map) while at the same time keeping track of their current location. Mapping is the problem of integrating the information gathered for and /or with an autonomous entity (the robot's) sensors into a complex model and depicting with a given representation. by the first characteristic questionWhat does the world look like? Central aspects in mapping are the representation of the environment and the interpretation of sensor data.
Mapping
Sensing
Locating
Modeling
The lesser the precision of any locating process might result, the more the support of a locally relevant map improves the assessing of the real location. However, maps generally represent the status at the time of drawing the map, not necessarily consistent with the actual status of the environment at the time of using the map. Complexity of the technical processes of locating and mapping under conditions of errors and of noise do not allow for a coherent solution of both tasks. Simultaneous localization and mapping (SLAM) is a concept to bind these processes in a loop and therefore supports the contiguity of both aspects in separated processes. Iterative feedback from one process to the other one enhances the results of both consecutive steps.localization is the problem of estimating the place (and pose) of the robot relative to a map. In other words, the robot has to answer the second characteristic question, Where am I? Typically, solutions comprise tracking, where the initial place of the robot is known, and global localization, in which no or just some a priori knowledge about the ambience of the starting position is given.
SLAM is therefore defined as the problem of building a model leading to a new map or repetitively improving an existing map while at the same time localizing the robot within that map.
To find what the environment looks like given a set of observations, a robot needs to know the robot's own kinematicswhich qualities the autonomous acquisition of information has, from which sources additional supporting observations have been made.
The Kalman filter dynamics results from the consecutive cycles of prediction and filtering. The dynamics of these cycles is derived and interpreted in the framework of Gaussian probability density functions. Under additional conditions on the system dynamics, the Kalman filter dynamics converges to a steady-state filter and the steady-state gain is derived. The nonlinear version of the Kalman filter which linearizes about the current mean and covariance is the Extended Kalman Filter.With no loss of generality we will consider that the system has no external inputs.
One iteration of the EKF is composed by the following consecutive steps:
1. Consider the last filtered state estimate ˆx(k|k), 2. Linearize the system dynamics, xk+1 = f(xk) + wk around ˆx(k|k), 3. Apply the prediction step of the Kalman filter to the linearized system dynamics just obtained, yielding ˆx(k + 1|k) and P(k + 1|k), 4. Linearize the observation dynamics, yk = h(xk) + vk around ˆx(k + 1|k), 5. Apply the filtering or update cycle of the Kalman filter to the linearized observation dynamics, yielding ˆx(k + 1|k + 1) and P(k + 1|k + 1).
Let F(k) and H(k) be the Jacobian matrices of f(.) and h(.), denoted by F(k) = 5fk |ˆx(k|k) H(k + 1) = 5h |ˆx(k+1|k)
The Extended Kalman filter algorithm is stated below:
It this important to state that the EKF is not an optimal filter, but rathar it is implemented based on a set of approximations. Thus, the matrices P(k|k) and P(k + 1|k) do not represent the true covariance of the state estimates. Moreover, as the matrices F(k) and H(k) depend on previous state estimates and therefore on measurements, the filter gain K(k) and the matrices P(k|k) and P(k + 1|k) cannot be computed off-line as occurs in the Kalman filter. Contrary to the Kalman filter, the EKF may diverge, if the consecutive linearizations are not a good approximation of the linear model in all the associated uncertainty domain. [1]
3- http://www.cs.unc.edu/~welch/media/pdf/kalman_intro.pdf 4- http://http//en.wikipedia.org/wiki/Kalman_filter A good filtering algorithm can remove the noise while still retaining the useful information.A Kalman Filter produces values that tend to be closer to the true values of some observed value set using measured values that are observed over time containing noise/random variations and other inaccuracies. [? somewhat similar to the ID3 algorithm] The Kalman Filter producesestimates of the true values of measurements and their associated calculated values by predicting a value, estimating the uncertainty of the predicted value, and computing a weighted average of the predicted value and the measured value. The estimates produced by the method tend to be closer to the true values than the original measurements because the weighted average has a better estimated uncertainty than either of the values that went into the weighted average.
Filtering:
An example is filtering out noise from our surroundings. If we paid attention to all the little noises around us we would go crazy. We learn to ignore superfluous sounds (traffic, appliances, etc.) and focus on important sounds, like the voice of the person we're speaking with.
Mathematics:
The question which is addressed by the Kalman filter is : Given our knowledge of the behavior of the system, and given our measurements, what is the best estimate of position and velocity?
Consider the problem of estimating the variables of some system. In dynamic systems (that is, systems which vary with time) the variables are denoted as state variables. Let vector X represent the system variables. Assume that the system variables, represented by the vector x, are governed by the equation below.
xk+1= Axk + wk
wk is random process noise subscripts on the vectors represent the time step
Suppose that X represents the time step of a spacecraft which is accelerating. X consists of position - p & velocity - v .
ak is the random time-varying acceleration, and T is the time between step k and step k+1.
Now suppose we can measure the position p. Then our measurement at time k can be denoted
zk = pk+ vk
where vk is random measurement noise.
How can we determine the best estimate of the system variables? We can do better than just take each measurement at its face value, especially if we suspect that we have a lot of measurement noise. Suppose we assume that the process noise wkis white with a covariance matrix Q. Further assume that the measurement noise vk is white with a covariance matrix R, and that it is not correlated with the process noise.
The Kalman filter is formulated as follows, on average :
1. estimate of the state will equal the true state. 2. our algorithm gives the smallest possible estimation error.
Kalman filter is the estimation algorithm which satisfies these criteria.One of the formulations is : (In the equations, the superscript –1 indicates matrix inversion and the superscript T indicates matrix transposition. S is called the covariance of the innovation, K is called the gain matrix, and P is called the covariance of the prediction error. )
Sk = Pk + R
--5
The first term used to derive the state estimate at time k+1 is just A times the state estimate at time k. This would be the state estimate if we didn't have a measurement.The second term in Equation 5 is called the correction term, representing how much to correct the propagated estimated due to our measurement. If the measurement noise is much greater than the process noise, K will be small (that is, we won't give much credence to the measurement), & vice versa
Example of a simulated system generated using MATLAB shows how well the Kalman Filter was able to estimate the position.
Applications :
This is a simple implementation of a KF I happend to come across, that tracks the movement of a soccer player.
KF can be thought of as operating in two distinct phases: predict and update. In the prediction phase, the player's old position will be modified according to the physical laws of motion (the dynamic or "state transition" model) plus any changes produced. Not only will a new position estimate be calculated, but a new covariance will be calculated as well. Perhaps the covariance is proportional to the speed of the player because we are more uncertain about the accuracy of the dead reckoning estimate at high speeds but very certain about the position when moving slowly. Next, in the update phase, a measurement of the player's position is taken. Along with this measurement comes some amount of uncertainty, and its covariance relative to that of the prediction from the previous phase determines how much the new measurement will affect the updated prediction. Ideally, if the dead reckoning estimates tend to drift away from the real position, the measurement should pull the position estimate back towards the real position but not disturb it to the point of becoming rapidly changing and noisy.
Dead reckoning- The player's position can be estimated by integrating the velocity and direction over time, determined by keeping track of the amount the acceleration is put in and how much the body's turned. provide a very smooth estimate of the position, but it will drift over time as small errors accumulate.
