YA's Blog

In order to map out an unknown environment for future reference, a robot uses the Simultaneous Localization And Mapping (SLAM) algorithm. We talked about solving the localization problem using Filtering in the previous posts. In this post, we will look at the mapping problem. We will assume that we know the position/orientation of the robot in the 3D world (which we obtain from filtering), and want to build a map of the objects in the world. Occupancy grid map (OGM) is a very common way of representing the layout of the unknown environment. It is a large gray-scale image where each pixel represents a cell in the physical world. The cells that are occupied are colored black and empty cells represent free space are colored white. The grey cells represent unexplored areas. Before moving forward, lets make some assumptions: Assumption 1: each cell is either free or occupied. We model each cell as a binary random variable that indicates occupancy. Let the probability that the cell

In this post, we look at particle filters (PFs) which are a generalization of the UKF that can handle non-Gaussian filtering distributions. When a robot uses a particle filter to localize itself, it is also called Monte Carlo localization. Just like the Unscented Transform (UT) forms the building block of the UKF, the building block of a particle filter is the idea of importance sampling. Importance Sampling Similar to UT, the sample points have equal weights but we can approximate different probability distributions depending upon how we pick the samples $x^{(i)}$ also called “particles”, just as shown in the Figure below. The higher the number of particles in a given region, higher is the approximated probability density of that region. Importance sampling is a technique to sample the particles to approximate a given probability distribution $p(x)$. The probability distribution is approximated as a sum of Dirac-delta distributions at points $x^{(i)}$, with weights $w^{(i)}$, \b