Hector

The map built in the process of SLAM is an occupancy grid. Each cell in the occupancy grid can have either of three different values:

· 1 denoting that we received concrete laser heads i.e. LiDAR scans reflected back to the sensor after hitting an obstacle, thus the cell is an occupied cell.

· 0 denoting that the LiDAR scans passed through without hitting anything and didn’t reflect back thus it is a free cell.

· -1 denoting that the cells are unexplored by the mobile agent.

Hector-SLAM depends upon scan matching between consecutive frames to build the map and localize the agent. Hector-SLAM algorithm differs from other grid-based mapping algorithms, as it does not require odometry information, but it needs laser data and a priori map. It is suitable for mobile agents exhibiting roll/pitch motion. It takes scans at two consecutive timestamps and uses the point clouds of these scans and compares them.

It uses iterative closest point to produce a transformation which align one point cloud with another, thus yielding a transformation over the rotation and translation matrices to minimize the root mean square distance between these Point clouds. This minimization in the distance between the Point clouds is done over some iterations before it converges to zero.

Hector-SLAM is based on the Gauss–Newton iteration formula that optimally estimates the pose of the robot as represented by the rigid body transformation ξ = [Px, Py, ψ]T from the robot to the prior.

The optimal estimation is done by optimally matching the laser data and the map in the sense that the optimal ξ* below is solved:

Explanation: ξ represents the pose of the robot, Si represents the scan endpoints (end coordinates of a scanned obstacle), when the pose is ξ. The function M gives the value of the map cell at each particular scan coordinate, the map cell can have value between -1, 1 and 0. Since the can endpoints correspond to the coordinate of obstacle detected in the scanning, -1 can be correlated to 0. ξ* value correspond to 0 when the M value is 1. The goal is to minimize the summation because there might be noise and error from the sensor.

The pose ξ can be represented as summation of previous pose and the change in the pose between the previous and current timestamp. This changes the minimization function to a function in change in pose. Expanding the equation as Taylor series expansion of function M and using Gauss Newton expansion (Gauss–Newton algorithm is used to solve non-linear least squares problems), we get the step change in pose with respect to the previous time stamp. Thus, it provides a change in pose in each timestamp.

Pose is updated by taking into account the previous pose and the change in pose. Transform or align the LiDAR scan to new pose and the map is updated using these transformed laser scans.

The occupancy grid doesn’t assign a value to its cell by a single scan as it might introduce lot of noise and the cells might be incorrectly assigned. Apart from the binary value, the occupancy grid also assign one more value to each of its cell, the value is a function of number of times the cell is encountered by the scan as free or occupied and the probability of those scan measurement being correct. Thus after few iterations of laser scans when the map is confident about some chunk of cells being correctly valued, they are represented as occupied or free.

Multi resolution Map Approach

In this kind of optimization function, there is high probability of getting stuck in local minima i.e. representing some cells incorrectly. Therefore the map is initially represented as a coarse map to predict a pose estimate and this estimate is used as an input to a high resolution maps.