Integrated Path Planning in an Extended Kalman Particle Filter Framework for Vehicle Navigation

1 Background

Path planning is a critical component of autonomous vehicle navigation, especially within complex environments. The ability to navigate efficiently and safely relies on sophisticated algorithms that can make informed decisions. This thesis aims to compare three well-known path planning approaches – Dijkstra, A*, and Rapidly-exploring Random Tree* (RRT*) – using a real-world dataset known as LUCOOP [Axmann et al., 2023]. The focus will be on integrating these path planning algorithms with a recently developed advanced particle filter called Robust Extended Kalman Particle Filter with Implicit observation models (R-EKPFI) [Moftizadeh, 2024] to determine which combination yields the best results. The ultimate goal is to develop an algorithm that not only assists in localization but also incorporates a path planner where the planned path is used to aid the prediction step of the filter. The student is encouraged to incorporate innovative ideas throughout the entire process as needed.

2 Objectives

The primary objectives of this master thesis are:

• To implement and compare three path planning approaches (Dijkstra, A*, and RRT*) for vehicl navigation within an urban environment.
• To integrate these path planning approaches with the R-EKPFI localization filter.
• To evaluate the performance of each path planning approach under the localization filter using the LUCOOP dataset.
• To provide a comprehensive analysis and comparison of the path planning approaches in terms of efficiency, accuracy, and robustness within the localization framework.

3 Specific Methodology

The methodologies to be investigated and implemented include, but are not limited to:

3.1 Path Planning Approaches

• Dijkstra: A classic graph search algorithm that finds the shortest path between nodes in a graph.
• A*: An extension of Dijkstra’s algorithm that uses heuristics to improve search efficiency.
• RRT*: A sampling-based algorithm that is designed for efficient path finding in high-dimensional spaces.

3.2 Localization Filter

• R-EKPFI: A hybrid filter that combines the advantages of both Extended Kalman Filter (EKF) and particle filters.

4 Provided Material

•  LUCOOP Dataset: A publicly available real-world dataset consisting of Global Navigation Satellite System (GNSS) and Light Detection and Ranging (LiDAR) data for urban vehicle navigation.
• Implemented Filtering Methods: Pre-existing MATLAB implementations of the R-EKPFI filter.

5 Programming Language

The entire thesis work, including the implementation and integration of path planning algorithms with the localization filter, is to be conducted using MATLAB. The provided codes for the filtering methods are already in MATLAB, ensuring a consistent development environment.

References

Jeldrik Axmann, Rozhin Moftizadeh, Jingyao Su, Benjamin Tennstedt, Qianqian Zou, Yunshuang Yuan, Dominik Ernst, Hamza Alkhatib, Claus Brenner, and Steffen Schön. Lucoop: Leibniz University cooperative perception and urban navigation dataset. In 2023 IEEE Intelligent Vehicles Symposium (IV), pages 1–8. IEEE, 2023.

Rozhin Moftizadeh. Advanced Particle Filtering for Vehicle Navigation based on Collaborative Information. PhD thesis, Fachrichtung Geod¨asie und Geoinformatik der Leibniz Universit¨at Hannover, 2024.

Acronyms

RRT* = Rapidly-exploring Random Tree*
R-EKPFI = Robust Extended Kalman Particle Filter with Implicit observation models
EKF = Extended Kalman Filter
GNSS = Global Navigation Satellite System
LiDAR = Light Detection and Ranging