flatloc

‘flatloc’ is a localization package for localizing a robot driving on the ground based on a ‘flat’ range scan. Range scans are a sensor representation where the distance to the first obstacles is reported for a regular grid of rays emitted from a center point. Flat range scans are produced directly by certain Lidar sensors or can be computed based on sensor data from a Lidar or a depth image. They can also be computed based on images by a neural network as a simplified version of a stereo depth neural network.

Algorithms around flat range scans are highly efficient and thus flatloc has a small resource footprint. This leaves the rest of the system available for more advanced computer vision and planning jobs. Flatscans however can not capture an environment with the same fidelity as a full 3D range scan or a depth image. This can lead to poor performance in feature deprived environments; a general challenge for localization methods.

A “flat” range scan is simply a 2D range scan specified in polar coordinates. It consists of a list of rays with an azimuth angle in radians and the range in meters at which the ray hits an obstacle for the first time.

\[(\alpha_i, r_i)_{1 \le i \le n}, \alpha_i \in [0,2\pi], r_i > 0\]

For localization and mapping we have to compute range scans from a hypothetical position based on a given map. Specifically we want to compare a raytraced range scan with a given measured range scan and compute how well they match. To support these operations we provide the following functions to raytrace an occupancy grid map.

• Bresenham The Bresenham algorithm was originally used to draw lines on a discrete canvas. Out algorithm traces a line from a start pixel coordinate to a target pixel coordinate and executes a callback for every grid cell on the path. The algorithm stops when the callback returns false or the end of the map is reached. This is the most versatile and customizable of the three tracing algorithms, but it is also the slowest.
• “Trace” This is a more optimized version of the Bresenham algorithm which traces a ray through a binary grid map and returns the distance at the first blocked cell is encountered. This algorithm works with a distance map which on average allows larger step sizes than the per-pixel steps of the Bresenham algorithm. This algorithm is quite fast and naturally works with floating point start and endpoints.
• “Trace & Match” For a given point on the map this function returns the optimal rotation under which the difference between the computed and a given range scan is minimal. Tracing multiple rays for a full range scan is a highly parallel operation which can benefits from GPU acceleration. This version also compares the resulting scan against a given scan to compute a matching score for all possible orientation which is an expensive convolution operations again well suited for GPU acceleration.