Motion Planning Feasibility Checker

Overview

Developed the feasibility checker module of the CommonRoad Drivability Checker Toolbox as part of the Cyber-Physical Systems group at the Technical University of Munich. The toolbox was published at the 2020 IEEE Intelligent Vehicles Symposium (IV) as “CommonRoad Drivability Checker: Simplifying the Development and Validation of Motion Planning Algorithms” (C. Pek, V. Rusinov, S. Manzinger, M. C. Üste, M. Althoff).

The Drivability Checker is an open-source toolbox that unifies three critical validation aspects for autonomous vehicle motion planning into a single framework:

1. Collision avoidance — verifying that planned trajectories do not collide with static or dynamic obstacles.
2. Kinematic feasibility — ensuring that planned motions respect the physical constraints of the vehicle (steering limits, acceleration bounds, etc.).
3. Road compliance — confirming adherence to road geometry, lane boundaries, and traffic rules.

My primary contribution was the feasibility checker module, which validates whether a given trajectory is physically realizable by a specific vehicle model. This involves forward-simulating the trajectory using differential equations that describe the vehicle’s kinematics and dynamics, and checking at each time step whether the planned states and inputs fall within the vehicle’s physical limits.

Feasibility Checking

The feasibility checker takes a planned trajectory (a sequence of states over time) and determines whether it can be executed by a real vehicle. This is done by:

• Forward simulation of vehicle models using the planned inputs (steering angle, acceleration) and comparing the resulting states against the planned trajectory states within configurable tolerances.
• Input reconstruction — given only a sequence of states, reconstructing the control inputs that would be required and verifying that they stay within feasible bounds.
• Support for multiple vehicle models — including kinematic single-track, dynamic single-track, and other models from the CommonRoad vehicle model library, each with different fidelity levels and physical parameters.

The module flags trajectories as infeasible when they require physically impossible maneuvers, such as turning radii tighter than the vehicle’s steering geometry allows or accelerations exceeding tire friction limits.

Architecture

The toolbox uses a Python frontend with a C++ backend for computational efficiency:

• C++ core — collision detection, geometry processing, and performance-critical computations are implemented in C++11, leveraging libraries such as Eigen3 (linear algebra), Boost, and OpenMP (parallelization).
• Python bindings — exposed via pybind11, allowing researchers and developers to use the toolbox from Python with minimal overhead.
• Collision detection — integrates the Flexible Collision Library (FCL) and Box2D physics engine, with libccd for continuous collision detection.
• Geometry processing — polygon clipping via the General Polygon Clipper library, with optional triangulation through Triangle or CGAL.

The toolbox is real-time capable and was validated for use in actual test vehicles at TUM.

Integration with CommonRoad

The Drivability Checker integrates directly with the CommonRoad benchmark suite, which provides thousands of standardized traffic scenarios for evaluating motion planning algorithms. It serves as the validation backend for the CommonRoad platform, which I also helped develop during my time at TUM — evaluating over 6,400 scenarios and 320,000 trajectories submitted through global competitions.

Tools & Technologies

• Python — Frontend API and feasibility checking module
• C++ / pybind11 — High-performance backend with Python bindings
• CommonRoad — Traffic scenario framework for motion planning benchmarks
• Eigen3, Boost, OpenMP — Numerical computation and parallelization
• FCL, Box2D, libccd — Collision detection libraries
• NumPy, SciPy — Scientific computing for vehicle model simulation