Monte Carlo localization (MCL), also known as particle filter localization, is an algorithm for robots to localize using a particle filter. Given a map of the environment, the algorithm estimates the position and orientation of a robot as it moves and senses the environment. The algorithm uses a particle filter to represent the distribution of likely states, with each particle representing a possible state, i.e., a hypothesis of where the robot is. The algorithm typically starts with a uniform random distribution of particles over the configuration space, meaning the robot has no information about where it is and assumes it is equally likely to be at any point in space. Whenever the robot moves, it shifts the particles to predict its new state after the movement. Whenever the robot senses something, the particles are resampled based on recursive Bayesian estimation, i.e., how well the actual sensed data correlate with the predicted state. Ultimately, the particles should converge towards the actual position of the robot.
Basic description Consider a robot with an internal map of its environment. When the robot moves around, it needs to know where it is within this map. Determining its location and rotation (more generally, the pose) by using its sensor observations is known as robot localization. Because the robot may not always behave in a perfectly predictable way, it generates many random guesses of where it is going to be next. These guesses are known as particles. Each particle contains a full description of a possible future state. When the robot observes the environment, it discards particles inconsistent with this observation, and generates more particles close to those that appear consistent. In the end, hopefully most particles converge to where the robot actually is.
State representation The state of the robot depends on the application and design. For example, the state of a typical 2D robot may consist of a tuple ( x , y , θ ) {\displaystyle (x,y,\theta )} for position x , y {\displaystyle x,y} and orientation θ {\displaystyle \theta } . For a robotic arm with 10 joints, it may be a tuple containing the angle at each joint: ( θ 1 , θ 2 , . . . , θ 10 ) {\displaystyle (\theta _{1},\theta _{2},...,\theta _{10})} . The belief, which is the robot's estimate of its current state, is a probability density function distributed over the state space. In the MCL algorithm, the belief at a time t {\displaystyle t} is represented by a set of M {\displaystyle M} particles X t = { x t [ 1 ] , x t [ 2 ] , … , x t [ M ] } {\displaystyle X_{t}=\lbrace x_{t}^{[1]},x_{t}^{[2]},\ldots ,x_{t}^{[M]}\rbrace } . Each particle contains a state, and can thus be considered a hypothesis of the robot's state. Regions in the state space with many particles correspond to a greater probability that the robot will be there—and regions with few particles are unlikely to be where the robot is. The algorithm assumes the Markov property that the current state's probability distribution depends only on the previous state (and not any ones before that), i.e., X t {\displaystyle X_{t}} depends only on X t − 1 {\displaystyle X_{t-1}} . This only works if the environment is static and does not change with time. Typically, on start up, the robot has no information on its current pose so the particles are uniformly distributed over the configuration space.
Overview Given a map of the environment, the goal of the algorithm is for the robot to determine its pose within the environment. At every time t {\displaystyle t} the algorithm takes as input the previous belief X t − 1 = { x t − 1 [ 1 ] , x t − 1 [ 2 ] , … , x t − 1 [ M ] } {\displaystyle X_{t-1}=\lbrace x_{t-1}^{[1]},x_{t-1}^{[2]},\ldots ,x_{t-1}^{[M]}\rbrace } , an actuation command u t {\displaystyle u_{t}} , and data received from sensors z t {\displaystyle z_{t}} ; and the algorithm outputs the new belief X t {\displaystyle X_{t}} .
… excerpt ends here. Continue reading the full article.
