CommonRoad-Reach-Flow: A Modular Toolbox for Specification-Compliant Reachability Analysis of Automated Vehicles

Reachability analysis has gained increasing popularity in motion planning and safeguarding of automated vehicles. Restricting the search space of the motion planner to the reachable set of the ego vehicle can significantly accelerate planning, as it eliminates many infeasible solutions a priori. In particular, in critical scenarios, where the solution space is much smaller than the unconstrained search space, this approach keeps planning times manageable. CommonRoad-Reach-Flow is a Python package with a C++ backend that provides a modular toolbox for computing reachable sets in traffic scenarios. The key features of the toolbox are:

• Computation of collision-free and rule-compliant reachable sets
• Extraction of driving corridors (subsets corresponding to one high-level maneuver) from the reachable set
• Best-first reachability analysis to provide a first driving corridor quickly
• Flexible configuration of the reachability analysis by the composition of several processing layers

System Requirements

The software is written in Python 3.10 and C++-20, and was tested on Ubuntu 22.04.

Building from Source

Note: If you want to use this package with the PyPI versions of its dependencies, you need to compile it using GCC 10 (which is the compiler we use to create the PyPI wheels). Otherwise, nanobind will not be able to detect the Python bindings of the dependencies correctly (see here). To do so, indicate the path to GCC 10 in the CXX environment variable before building the code (e.g. export CXX=/usr/bin/g++-10). Note that you need to start with a fresh build directory if you change the compiler, as CMake caches the compiler used for the build. Alternatively, if you cannot use GCC 10 for some reason, you can install the following packages from source using the compiler of your choice: commonroad-clcs, commonroad-drivability-checker. Make sure to use the correct versions of these packages as specified in the pyproject.toml file.

Third-Party Dependencies

While most of these dependencies are added automatically during the build process, you can install them manually via your package manager to speed up the build process.

Manual installation required:

• OpenMP

Manual installation recommended to speed up the build:

• Boost
• spot

Manual installation optional:

• Eigen3
• yaml-cpp
• spdlog
• pybind11

Optional dependencies:

• GTest (optional: for building unit tests)

The additional Python dependencies are listed in pyproject.toml.

Building the Code

1. We strongly recommend installing this package in a virtual Python environment using one of the following tools:

   • uv
   • Anaconda
   • Miniconda

2. Install spot (version 2.14.1). See the spot documentation for instructions. If you are using Ubuntu, you can install spot with:

wget -q -O - https://www.lre.epita.fr/repo/debian.gpg | sudo tee /etc/apt/keyrings/lre-spot.gpg
echo 'deb [signed-by=/etc/apt/keyrings/lre-spot.gpg] http://www.lre.epita.fr/repo/debian/ stable/' | sudo tee -a /etc/apt/sources.list
sudo apt-get update
sudo apt-get install libspot-dev=2.14.1.0-1 libbddx-dev=2.14.1.0-1 libspot0=2.14.1.0-1 libspotltsmin0=2.14.1.0-1 libbddx0=2.14.1.0-1

Otherwise, you need to install spot from source as described under "Installing and compiling from a tarball" here. After installing from source, you may need to run sudo ldconfig to discover the newly installed library.

3. Install C++ dependencies:

sudo apt-get update
sudo apt-get install libomp-dev libboost-all-dev libeigen3-dev libyaml-cpp-dev libspdlog-dev pybind11-dev libgtest-dev libgmock-dev

4. Build the C++ extension and install the Python package:

pip install -v .

or, if you are using uv:

uv sync -v

This will build the Python bindings (cr_reach_flow_core) required for C++-boosted computations.

Note: The -v flag (verbose) prints information about the build progress

Optional:

• To build the code in Debug mode, add the flag
  • --config-settings=cmake.build-type="Debug" if you are using pip
  • --config-settings-package cr_reach_flow:cmake.build-type="Debug" if you are using uv

See here for further information on configuring CMake arguments via our build system (scikit-build-core).

Note: scikit-build-core uses ninja for building the C++ extension by default. Thus, the build is automatically parallelized using all available CPU cores. If you want to explicitly configure the number of build jobs, you can do so by passing the flag --config-settings=cmake.define.CMAKE_BUILD_PARALLEL_LEVEL=$BUILD_JOBS to the pip command, where $BUILD_JOBS is the number of parallel jobs to use. For uv, use --config-settings-package cr_reach_flow:cmake.define.CMAKE_BUILD_PARALLEL_LEVEL=$BUILD_JOBS. See here for further details.

Note: Building the package in Debug mode (see above) significantly increases the computation time of the C++ backend. Please make sure you are building in Release mode (default setting) if you require fast computations.

You can also have a look at the Dockerfile for the CI pipeline to see how to set up a consistent development environment on Debian/Ubuntu.

Running the Code

Run the example script main.py to compute specification-compliant reachable sets:

python main.py

or, if you are using uv:

uv run main.py

The outputs will be stored in the ./output/ directory. Default and scenario-specific configurations are stored in the ./configurations/ directory. The scenarios themselves are located in the ./scenarios/ directory.

Note: You might need to adjust the path_root argument of SemanticConfigurationBuilder to your setup.

Possible Installation Problems

• Protobuf error like this CHECK failed: GeneratedDatabase()->Add(encoded_file_descriptor, size): this is caused by the commonroad_cpp Python package and the version of the environment model used by our C++ code trying to register the same type with the same protobuf instance twice. To work around this issue, you can add the --config-settings=cmake.define.COMMONROAD_SYSTEM_PROTOBUF=OFF option to the pip install command.
• error: 'to_finite' is not a member of 'spot' during cmake build: this is caused by an old version being used for compiling even you have installed the latest one. The function to_finite is declared in the header remprop.hh. You can search for sudo find / -name remprop.hh 2>/dev/null and then delete the folders that are not under /usr/.
• ImportError: /.../commonroad-reach-flow/commonroad_reach_flow/cr_reach_flow_core.cpython-310-x86_64-linux-gnu.so: undefined symbol: _ZN4spot9to_finiteESt10shared_ptrIKNS_9twa_graphEEPKc when importing pybind11 bindings: you can use this tool to demangle the symbol name. There might still be some old version of spot is used from your conda environment. Try uninstalling spot and see whether the error still appears. If yes, delete other spot files in your anaconda folder and reinstall spot.

Development

Check out the README_FOR_DEVS for information on setting up your development environment.

References

Collision-Free Reachability Analysis

S. Söntges and M. Althoff, "Computing the Drivable Area of Autonomous Road Vehicles in Dynamic Road Scenes," IEEE Transactions on Intelligent Transportation Systems, vol. 19, no. 6, pp. 1855–1866, 2018, doi: 10.1109/TITS.2017.2742141.

Rule-Compliant Reachability Analysis

F. Lercher and M. Althoff, "Specification-Compliant Reachability Analysis for Autonomous Vehicles Using On-the-Fly Model Checking," in Proc. of the IEEE Intelligent Vehicles Symposium (IV), 2024, pp. 1484–1491. doi: 10.1109/IV55156.2024.10588549.

Best-First Reachability Analysis for Driving Corridors

F. Lercher and M. Althoff, "Efficient Driving Corridor Extraction for Autonomous Vehicles Using Best-First Reachability Analysis," in Proc. of the IEEE International Conference on Intelligent Transportation Systems (ITSC), 2025, pp. 407–414. doi: 10.1109/ITSC60802.2025.11423713.