cartographer/mapping/2d/probability_grid.h

Overview

ProbabilityGrid is a 2D occupancy grid using log-odds representation. Each cell stores the log-odds of occupancy, allowing efficient Bayesian updates during range data insertion.

Class: cartographer::mapping::ProbabilityGrid

Inheritance

Grid2D (abstract)
└── ProbabilityGrid

Grid2D Interface

class Grid2D {
 public:
  virtual ~Grid2D() {}
  virtual const MapLimits& limits() const = 0;
  virtual float GetProbability(const Eigen::Array2i& cell_index) const = 0;
  virtual bool IsKnown(const Eigen::Array2i& cell_index) const = 0;
  virtual void SetProbability(const Eigen::Array2i& cell_index,
                              float probability) = 0;
};

ProbabilityGrid Methods

Construction

explicit ProbabilityGrid(const MapLimits& limits);
ProbabilityGrid(const proto::ProbabilityGrid2D& proto,
                const MapLimits& limits);

Grid Access

const MapLimits& limits() const override;
float GetProbability(const Eigen::Array2i& cell_index) const override;
bool IsKnown(const Eigen::Array2i& cell_index) const override;
void SetProbability(const Eigen::Array2i& cell_index,
                    float probability) override;

Iteration

void ApplyToCells(const std::function<void(const Eigen::Array2i&)>& function) const;

Calls function for every known cell.

Serialization

proto::ProbabilityGrid2D ToProto() const;
void ToProto(proto::ProbabilityGrid2D* proto) const;

Log-Odds Representation

Internally stores log-odds (logit) values:

log_odds = log(p / (1 - p))

Where p is the occupancy probability.

Advantages:

• Bayesian updates become addition: log_odds_new = log_odds_prior + log_odds_measurement

• No division or clamping during updates

• Efficient incremental updates

Constants

constexpr int16 kMaxCorrespondenceCost = 32767;
constexpr int16 kMinCorrespondenceCost = 0;
constexpr int16 kUnknownCorrespondenceCost = 32767;

Correspondence cost maps to probability:

• 0 → probability 1.0 (occupied)

• 32767 → probability 0.0 (free) or unknown

Correspondence Cost

Used for scan matching cost computation:

int GetCorrespondenceCost(const Eigen::Array2i& cell_index) const;

Returns cost in [0, 32767] where lower = more likely occupied.

Conversion Functions

static float ProbabilityToCorrespondenceCost(float probability);
static float CorrespondenceCostToProbability(int correspondence_cost);

MapLimits

Defines the grid bounds and resolution:

struct MapLimits {
  double resolution;           // Meters per cell
  Eigen::Vector2d max;         // Max x, y in grid frame
  Eigen::Array2i cell_limits;  // Number of cells (x, y)
  
  Eigen::Array2i GetCellIndex(const Eigen::Vector2f& point) const;
  Eigen::Vector2f GetCellCenter(const Eigen::Array2i& cell_index) const;
  bool Contains(const Eigen::Array2i& cell_index) const;
};

ProbabilityGridRangeDataInserter2D

Located in probability_grid_range_data_inserter_2d.h/.cc.

Insertion Algorithm

For each range data insertion:

1. Hit cells (returns) → Increase occupancy probability

2. Miss cells (free space along rays) → Decrease occupancy probability

struct Options {
  bool insert_free_space = true;
  float hit_probability = 0.55;
  float miss_probability = 0.49;
};

Update equations:

• Hit: log_odds += log(hit_prob / (1 - hit_prob))

• Miss: log_odds += log(miss_prob / (1 - miss_prob))

With defaults: hit adds ~0.2, miss adds ~-0.04 (slight free space bias).

Ray Casting

Uses Bresenham’s algorithm to trace rays from origin to returns/misses.

Usage

// Create grid
MapLimits limits(0.05, Eigen::Vector2d(50, 50), Eigen::Array2i(1000, 1000));
ProbabilityGrid grid(limits);

// Insert range data
ProbabilityGridRangeDataInserter2D inserter(options);
inserter.Insert(range_data, &grid);

// Query probability
Eigen::Array2i cell = limits.GetCellIndex(Eigen::Vector2f(1.0, 2.0));
float prob = grid.GetProbability(cell);

// For scan matching: get correspondence cost
int cost = grid.GetCorrespondenceCost(cell);

Configuration

From trajectory_builder_2d.lua:

range_data_inserter = {
  probability_grid_range_data_inserter = {
    insert_free_space = true,
    hit_probability = 0.55,
    miss_probability = 0.49,
  },
}

See Also

• TSDF — Alternative 2D representation

• Submap2D — Submap using ProbabilityGrid