Left: Map generated using wheel encoder odometry, Middle: Map generated using EKF on wheel encoders for odometry, Right: Map generated using our scan matching for odometry

Mapping using only laser range finder on Mobile Robot

Contributors:

Balakumar Sundaralingam, Sudarsan Balaji, Yaswanth Kodavali.

Advisor: Prof. Prem S.

Abstract

Mobile robots employ wheel encoders to generate odometric readings. But the odometric readings from the wheel encoders of the mobile robots are generally erroneous, even in indoor environments. Without proper guiding tools like GPS, it is very hard to localise the robot in each consecutive scan for mapping. To overcome this disadvantage, a generic approach to formulate an error function using wheel encoder readings is followed. This error model could be used in algorithms like EKF, Regression Analysis or Least-Squared Error Reduction, to get a more accurate localisation. This is followed by mapping, necessitating the use of high quality wheel encoders in the mobile robot for localisation.

This project aims at eliminating the requirement of such high quality wheel encoders for mapping an indoor environment. This task is achieved with scan data taken at discrete intervals, using line-based or point-based Plot Matching techniques, without the aid of odometric data from the wheel encoders. Currently, mapping of indoor environment has been done using the scan data obtained from the mobile platform. The scan data is used in a post-processing algorithm which provides promising results. This encourages a better future by completely eliminating the need for wheel encoders, thereby reducing the cost of production, and also the corresponding computational efforts. This project was part of my undergraduate thesis, advised by Prof. Prem .S.

Problem Definition and Data Collection

We define the problem as computing the transformation between consecutive laser scans to enable mapping of the environment. Laser scan data was collected using the Pionerr 3AT robot equipped with a SICK LMS laser range finder. The wheel encoder data is also recorded. The robot is run in “Wander mode” until it covers all areas of the environment.

Approach

The laser scan data is converted into the polar coordinates which consists of an angle $\Theta$ and a distance from the sensor $d$. The polar scan matching method brute forces a minimum distane

Polar Scan Matching
The orientation has a fixed range~$[0,2\pi]$. The translation distance however is infinitely large. We reduce the translation enumeration by matching the centroids between consecutive scans. When computing the centroid, outliers are removed by thresholding the distance as the outliers are usually data from new exploration.
Approximate Centroid Fixing:The green dot shows the position of the centroid of the detected convex hull of the completed polygon drawn in green. Note that two similar scans get dissimilar polygons and centroids due to the detection of some new points in the second scan. Also note that this does not affect the position of the centroid too much.
With polar scan matching, we can thus find homogenous transformations between consecutive scans. This can effectively replace wheel encoders for robot odometry. We then superimpose laser scan data from our collected data with transformations from our approach. This allows us to generate accurate 2D maps of the environment.
Map of the mobile robot lab generated using odometry from EKF on wheel encoders

A second room with three partitions was also explored

Line extraction

As part of this project, a line extraction method was formulated to generate lines from laser scan data which is made of points.

Split and Merge Algorithm
Split and Merge on Laser Scan data
Split and Merge generates lines with no knowledge of clusters as seen in Fig.2. Nearest neighbor clustering was used to generate clustered lines.
Clustered points are shown in different colors.
Split and Merge on Clustered Laser Scan data shows better lines
The lines obtained from clustered data produces broken lines. An additional step to line extraction which concatenates lines together based on their slope. The complete line extraction method is given below
Improved Line extraction with concatenation of lines based on slope.
Improved Line extraction with concatenation of lines based on slope.