Gridplan: Graph-Search Planner Benchmark

A hybrid C++20/Python path-planning library implementing BFS, Dijkstra, A*, and weighted A* on 2D and 3D occupancy grids. It’s the first piece of a drone autonomy project track, providing the search foundation for later trajectory generation and incremental replanning work.

The search runs in a C++ core exposed to Python through pybind11 bindings that accept NumPy arrays and release the GIL during search. A pure-Python reference implementation of every planner serves as a correctness oracle. C++ and Python results are cross-validated in tests, and the core is checked under AddressSanitizer and UBSan.

Architecture

• C++ core: flat-array grid with padded borders, precomputed neighbor offset/cost tables, and planners with configurable heuristics and tie-breaking
• pybind11 bindings: expose every planner to Python with NumPy input and the GIL released during search
• Python layer: environment generation, reference planners, 2D/3D visualization, and the benchmark sweep and analysis

Design Decisions

• Flat std::vector<uint8_t> with padded borders: eliminates bounds checks in the inner loop. Neighbors are found by adding precomputed offsets to linear indices.
• Runtime-parameterized dimensions: one Grid class handles both 2D and 3D instead of templating on dimension, at the cost of one negligible branch.
• Lazy-deletion priority queue for Dijkstra, closed set for A*: the stale-entry check doesn’t hold once f-values include a heuristic, so A* tracks a closed set instead.
• Corner-cutting constraints in the neighbor table: each diagonal entry carries the component offsets that must be free, checked at neighbor-generation time.

Results

• A* vs Dijkstra: on open 8-connected grids with the octile heuristic, A* expands ~200 nodes vs ~50,000 for Dijkstra. The gap narrows on cluttered grids, where obstacles force detours the heuristic can’t predict.
• Weighted A*: at w=5.0, paths are only ~1.1–1.15x optimal, far below the theoretical 5x bound, while running ~100x faster than BFS/Dijkstra on 1024² grids.
• Tie-breaking: preferring larger g on equal f cuts expansions on open 4-connected grids from ~20,000 to ~500.
• C++ vs Python: the C++ core is 11–28x faster than the Python reference, and binding overhead drops below 5% on 1024² grids.
• 2D vs 3D: a 64³ grid (~260k cells) takes time comparable to a 1024² grid (~1M cells). That cubic scaling is why onboard drone planners favor sparser representations like octrees over dense voxel grids.

Screenshots

Planner Comparison (64×64)

3D A* Path

A* Expansion Reduction

Tie-Breaking Effect

Weighted A* Suboptimality

C++ vs Python Speedup

Tech Stack

Core: C++20, CMake Bindings: pybind11, NumPy Python: pytest, Matplotlib Testing & Profiling: GoogleTest, Google Benchmark, AddressSanitizer/UBSan, Instruments

Links

• GitHub