Making 2D LiDAR Occupancy Grid Mapping from scratch

Problem

I implement a serial baseline for a robotics mapping task: building a 2D occupancy grid map from many LiDAR scans.

The map is a grid of cells. Each cell stores how likely it is occupied by an obstacle. The robot moves along a trajectory and takes scans with many beams. Each beam says either:

This is a realistic robotics workload because mapping is used in mobile robot navigation and autonomous systems, and ray casting + grid updates are computationally heavy.

How the algorithm/baseline code works

Source file: raycast_mapping.cc

  1. Create a synthetic world
  2. Create robot trajectory
  3. Simulate LiDAR measurement (ray casting)
  4. Integrate into estimated occupancy map
  5. Report runtime and quality indicators

Compile and run example:

clang++ -O3 -Wall -std=c++17 raycast_mapping.cc -o raycast_mapping
./raycast_mapping --width 1024 --height 1024 --scans 1500 --beams 720 --max-range 220 --obstacles 140 --path-radius 300

Tested preset on Miyabi (serial baseline):

%%sub
cd code
./raycast_mapping \
    --seed 42 \
    --width 2040 \
    --height 2040 \
    --scans 80000 \
    --beams 4320 \
    --max-range 600 \
    --obstacles 600 \
    --path-radius 700 \
    --out-ppm map.ppm \
    --out-gt-ppm map_gt.ppm

Observed runtime for this preset: about 168 seconds.

Main size knobs:

Output images from the above run:

Estimated occupancy map Ground-truth occupancy map

Where is parallelism

The workload has large data parallel structure.

Possible mappings:

Main expected limits to speedup: