The code in this repository is the result of my master's thesis which I have written at the Integrated Research Lab (ITRL) at KTH Royal Institute of Technology (2016). The code is documented here and the associated thesis can be found here.
The goal of the thesis and hence this code is to create a real-time path planning algorithm for the nonholonomic Research Concept Vehicle (RCV). The algorithm uses a binary obstacle map as an input, generated using LIDAR mounted on top of the vehicle. The algorithm is being developed using C++ due to real-time requirements in combination with ROS to ensure modularity and portability as well as using RViz as a visualization/simulation environment.
- Sampling in continuous space with 72 different headings per cell (5° discretization)
- Constrained Heuristic - nonholonomic without obstacles
- Unconstrained Heuristic - holonomic with obstacles
- Dubin's Shot
- C++ real-time implementation (~10 Hz)
Large parts of the implementation are closely related to the hybrid A* algorithm developed by Dmitri Dolgov and Sebastian Thrun (Path Planning for Autonomous Vehicles in Unknown Semi-structured Environments DOI: 10.1177/0278364909359210)
- Path Planning with Search Visualization
- Dubin's Path - Constrained Heuristic
- 2D A* Search - Unconstrained Heuristic
- Open Loop Path Planning using Sensor Fusion
Run the following command to clone, build, and launch the package (requires a sources ROS environment):
sudo apt install libompl-dev \
&& mkdir -p ~/catkin_ws/src \
&& cd ~/catkin_ws/src \
&& git clone https://github.com/karlkurzer/path_planner.git \
&& cd .. \
&& catkin_make \
&& source devel/setup.bash \
&& rospack profile \
&& roslaunch hybrid_astar manual.launch
- Add -> By Topic ->
/map,/path,/pathVehicle, (/visualizeNode2DPoses) - Click 2D Pose Estimate to set a start point on the map (
p) - Click 2D Nav Goal to set a goal point on the map (
g) - Wait for the path being searched! (this process can be visualized [optional])
I would appreciate if you cite my work, in case you are using it for your work. Thank you :-)
@mastersthesis{Kurzer1057261,
author = {Kurzer, Karl},
institution = {KTH, Integrated Transport Research Lab, ITRL},
pages = {63},
school = {KTH, Integrated Transport Research Lab, ITRL},
title = {Path Planning in Unstructured Environments : A Real-time Hybrid A* Implementation for Fast and Deterministic Path Generation for the KTH Research Concept Vehicle},
series = {TRITA-AVE},
ISSN = {1651-7660},
number = {2016:41},
abstract = {On the way to fully autonomously driving vehicles a multitude of challenges have to be overcome. One common problem is the navigation of the vehicle from a start pose to a goal pose in an environment that does not provide any specic structure (no preferred ways of movement). Typical examples of such environments are parking lots or construction sites; in these scenarios the vehicle needs to navigate safely around obstacles ideally using the optimal (with regard to a specied parameter) path between the start and the goal pose. The work conducted throughout this master's thesis focuses on the development of a suitable path planning algorithm for the Research Concept Vehicle (RCV) of the Integrated Transport Research Lab (ITRL) at KTH Royal Institute of Technology, in Stockholm, Sweden. The development of the path planner requires more than just the pure algorithm, as the code needs to be tested and respective results evaluated. In addition, the resulting algorithm needs to be wrapped in a way that it can be deployed easily and interfaced with di erent other systems on the research vehicle. Thus the thesis also tries to gives insights into ways of achieving realtime capabilities necessary for experimental testing as well as on how to setup a visualization environment for simulation and debugging. },
year = {2016}
}