HistogramFilterLocalization

C++ implementation of a 2D histogram filter for robot localization on cyclic colored grid maps, with validated sensing, motion, and belief updates.

Overview

This project implements the core pieces of a 2D histogram filter for robot localization in a discrete colored world. The robot maintains a belief distribution over all cells in a cyclic grid, updates that distribution after movement, and re-weights it after sensing map colors.

The codebase focuses on the localization mechanics themselves rather than a full application shell. It includes reusable helper functions, a localization module, sample map fixtures, and a Makefile-driven test harness that validates the implemented behavior.

Key Features

Core Capabilities

• Uniform belief initialization: Starts localization with equal probability across every cell in the map.
• Probabilistic sensing update: Re-weights each cell using p_hit and p_miss based on the sensed color.
• Cyclic motion update with blur: Shifts beliefs across a wraparound grid and models motion uncertainty through probability blurring.

Additional Project Value

• Map loading helpers: Reads small text-based grid maps from the maps/ directory.
• Validation harness: Includes deterministic tests for normalization, blurring, initialization, motion, and sensing logic.
• Simulation scaffold: Contains a Simulation class skeleton for extending the project beyond the current tests.

Problem Statement

A robot moving through a grid world rarely knows its exact position. Motion is noisy, sensing is imperfect, and the environment may contain repeated visual features. The localization task is to maintain and update a belief distribution over all possible positions as the robot moves and collects observations.

This project addresses that problem with a histogram-filter approach on a discrete cyclic grid, where uncertainty is modeled explicitly and belief updates remain interpretable.

Objectives

• Implement normalized probability updates for grid-based localization.
• Model noisy motion using cyclic shifts plus probabilistic blurring.
• Update beliefs from sensor observations using relative hit and miss likelihoods.
• Validate each core operation with repeatable C++ tests.

Results

All included validation checks currently pass through the provided test harness.

Validation Check	Result
normalize()	Pass
blur()	Pass
initialize_beliefs()	Pass
move()	Pass
sense()	Pass

Interpretation:

• Current implementation status: Core histogram-filter functions are working as validated by the included tests.
• Main takeaway: The repository contains a completed, testable localization core rather than just starter code.
• Limitation: The project is centered on unit-style validation and does not yet expose a standalone simulation executable or interactive demo.

Demo / Outputs

This repository does not include a GUI or deployed demo. The primary executable outcome is the local test binary produced by the Makefile.

• Validation binary generated locally: tests
• Sample map fixtures: maps/m1.txt, maps/m2.txt, maps/half_red.txt
• Terminal output: pass/fail messages for each helper and localization function

If a test fails, the harness prints the expected and actual belief grids to help debug the implementation.

Tech Stack

Languages & Tools

• C++11
• Make
• Apple clang / g++-compatible compiler
• Terminal-based validation

Libraries

• C++ standard library only

Project Structure

HistogramFilterLocalization/
├── README.md
├── Makefile
├── helpers.cpp
├── helpers.h
├── localizer.cpp
├── localizer.h
├── simulate.cpp
├── simulate.h
├── debugging_helpers.cpp
├── debugging_helpers.h
├── tests.cpp
├── tests.h
└── maps/
    ├── half_red.txt
    ├── m1.txt
    └── m2.txt

File Guide

File / Folder	Purpose
helpers.cpp / helpers.h	Probability normalization, blurring, map loading, and utility helpers
localizer.cpp / localizer.h	Core histogram-filter belief initialization, motion update, and sensing update
simulate.cpp / simulate.h	Simulation scaffold for extending the localization workflow
debugging_helpers.cpp / debugging_helpers.h	Grid-printing helpers for debugging beliefs and maps
tests.cpp / tests.h	Validation harness for the implemented functions
maps/	Small text fixtures used to validate localization behavior

Dataset

This project does not depend on an external dataset.

Instead, it uses small built-in text maps stored in maps/ to represent discrete colored environments for localization tests.

Methodology

1. Load a discrete map from a text file.
2. Initialize a uniform belief distribution over all grid cells.
3. Apply motion using cyclic wraparound translation.
4. Blur the resulting grid to model motion uncertainty.
5. Apply a sensing update using hit/miss likelihoods based on cell color.
6. Normalize the belief grid after each probabilistic update.
7. Validate expected behavior with deterministic tests.

Architecture / Pipeline

Map Grid -> initialize_beliefs -> move -> blur -> sense -> normalize -> updated belief grid

Setup

Prerequisites

• macOS, Linux, or another Unix-like environment
• A C++11-compatible compiler
• make

Installation

git clone https://github.com/gour6380/HistogramFilterLocalization.git
cd HistogramFilterLocalization
make tests

How to Run

Run the validation harness directly:

./tests

Or use the Makefile convenience target:

make run

Expected Outcome

After building and running the project, you should expect:

• A local tests executable generated by make
• Terminal output confirming whether each core function passes validation
• Detailed grid comparisons printed automatically if a test fails

Outcome Files Produced

File / Folder	What It Contains	Why It Matters
tests	Locally built validation executable	Confirms the localization logic compiles and runs

Example Commands

make tests
./tests
make clean

Testing / Validation

The project currently validates:

• probability normalization
• probability blurring
• uniform belief initialization
• deterministic cyclic motion updates
• sensing updates with p_hit and p_miss

The validated execution path is:

make tests
./tests

Example Use Cases

• Study how histogram filters update beliefs in a discrete environment
• Validate a C++ implementation of grid-based robot localization
• Use the helpers and localization functions as a starting point for a richer simulator
• Extend the project with additional maps, motion models, or visualization layers

Challenges and Learnings

• Biggest challenge: modeling uncertainty while keeping updates easy to verify
• What improved results: using deterministic fixture maps and explicit pass/fail checks
• Key learning: simple probabilistic localization becomes much easier to reason about when each update step is isolated and testable

Limitations

• No standalone interactive simulator or visualization is exposed yet
• The current build compiles through a single test entrypoint rather than a more modular multi-target setup
• Validation is focused on core functions and a few fixed map scenarios

Future Improvements

• Add a dedicated simulation executable with step-by-step belief updates
• Refactor the build to compile translation units separately instead of including .cpp files
• Expand the test suite with more motion and sensing edge cases
• Add CI to run make tests automatically on each push

License

This repository does not currently include a license file.