IGHAStar

IGHAStar: Incremental Generalized Hybrid A* Search

Fig. 1: The issue with Hybrid A* Search. Too coarse grid resolution risks failure (a), while too fine leads to excessive expansions and slow planning (e).

We address the problem of efficiently organizing search over very large trees, which arises in many applications such as autonomous driving, aerial vehicles, and so on; here, we are motivated by off-road autonomy, where real-time planning is essential. Classical approaches use graphs of motion primitives and exploit dominance to mitigate the curse of dimensionality and prune expansions efficiently. However, for complex dynamics, repeatedly solving two-point boundary-value problems makes graph construction too slow for fast kinodynamic planning. Hybrid A* (HA*) addressed this challenge by searching over a tree of motion primitives and introducing approximate pruning using a grid-based dominance check. However, choosing the grid resolution is difficult: too coarse risks failure (Fig. 1(a)), while too fine leads to excessive expansions and slow planning (Fig. 1(e)). To overcome this, we propose Incremental Generalized Hybrid A* (IGHA*), an anytime tree-search framework that dynamically organizes vertex expansions without rigid pruning. IGHA* provably matches or outperforms HA*, and has been tested in both simulation (Fig. 2, left) and in the real world on a small scale off-road platform (Fig. 2, right).

Fig. 2: IGHAStar in simulation (left) and real-world testing on a small-scale off-road platform (right).

Generally speaking, IGHA* will find better paths given the same compute budget, compared to a smart multi-resolution version of HA* (HA*M), which produces suboptimal (looping) paths, visible in the simulation comparison.

Note that IGHA*'s main dependency is Pytorch; other dependencies are for data I/O and display. The code for IGHA* is written in C++ (src/ighastar.cpp), and we use CUDA for edge evaluation and expansion. We use Pytorch C++/CUDA to handle all of the compilation and python binding. This allows us to get the performance of C++/CUDA with the abstraction of Python/Pytorch. The first time you run the planner, it will cache all the compiled objects for future use.

Compute Environment Selection

For the standalone examples, the system automatically detects CUDA availability:

• If CUDA is available: Uses GPU-accelerated planning
• If CUDA is not available: Falls back to CPU implementation

Installation

Note: This has currently only been tested on Ubuntu 20.04. Use virtual environments for initial testing.

1. Clone the Repository

git clone https://github.com/personalrobotics/IGHAStar.git
cd IGHAStar

2. Set Up Conda Environment (Optional; only do this if you want to isolate the environment in case a requirement conflicts with your global env.)

conda env create -f ighastar.yml
conda activate ighastar

3. Install the Package

Install the IGHAStar package in editable mode:

pip install -e .

Note: This step is required to make the IGHAStar modules importable from anywhere in your environment.

Usage

Running the Standalone Example

Fig. 3: Example planning results: Kinematic planning on urban streets (left), Kinodynamic planning on off-road terrain (middle), and Simple planning on generated maps (right).

The main example script supports different planning modes through configuration files:

# Use default kinematic configuration
python examples/standalone/example.py

# Specify a different configuration file
python examples/standalone/example.py --config Configs/kinodynamic_example.yml

# Use simple planning configuration
python examples/standalone/example.py --config Configs/simple_example.yml

# Use a specific test case
python examples/standalone/example.py --config Configs/kinematic_example.yml --test-case case2

For detailed configuration and usage instructions, see examples/standalone/README.md. For information on how to create your own Environment, see ighastar/Environments/README.md

Project Structure

IGHAStar/
├── ighastar/             # Main package directory
│   ├── src/              # Core C++/CUDA source files and Python modules
│   │   ├── ighastar.cpp  # Main IGHA* C++ implementation
│   │   └── Environments/ # Environment implementations
│   │       ├── *.h       # Header files
│   │       ├── *.cu      # CUDA implementations
│   │       └── *.cpp     # CPU implementations
│   └── scripts/          # Utility scripts
│       ├── common_utils.py # Common utilities (create_planner, etc.)
├── examples/             # Example scripts and configurations
│   ├── standalone/       # Standalone examples
│   │   ├── example.py    # Main example script
│   │   ├── README.md     # Detailed usage guide
│   │   ├── Configs/      # Configuration files
│   │   └── Maps/         # Map files
│   └── *              # Other example folders
├── Content/              # Figures and media files
├── ighastar.yml          # Conda environment file
├── pyproject.toml        # Package configuration
├── setup.py              # Package setup (for editable installs)
└── README.md             # This file

Contributing

1. Fork the repository
2. Create a feature branch
3. Make your changes
4. Format your code:
   • For C++ files, use clang-format to ensure consistent style.
     • Example: clang-format -i path/to/file.cpp
   • For Python files, use black for code formatting.
     • Example: black path/to/file.py
   • Use PEP 484 type hints for all Python functions and methods.
5. Test with both CPU and GPU environments (if that applies)
6. Submit a pull request