search

karlkurzer / path_planner

Hybrid A* Path Planner for the KTH Research Concept Vehicle
http://karlkurzer.github.io/path_planner/
BSD 3-Clause "New" or "Revised" License
1.49k stars 526 forks source link
motion-planning planning-algorithms robotics

readme

Hybrid A* Path Planner for the KTH Research Concept Vehicle Build Status

This repository contains the implementation of a Hybrid A Path Planner for autonomous vehicles, specifically developed for the KTH Research Concept Vehicle. The Hybrid A algorithm is a powerful path planning approach that combines the benefits of A* search in continuous space with a discretized set of headings. It enables the generation of efficient and smooth paths for nonholonomic vehicles navigating complex environments.

Table of Contents

Introduction

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.

Key Characteristics

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)

Videos

Images

Reversing in a Maze Parking Mitigating a U-shape Obstacle

Dependencies

Setup

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

Visualization (Rviz)

  1. Add -> By Topic -> /map, /path, /pathVehicle, (/visualizeNode2DPoses)
  2. Click 2D Pose Estimate to set a start point on the map (p)
  3. Click 2D Nav Goal to set a goal point on the map (g)
  4. Wait for the path being searched! (this process can be visualized [optional])

Citation

I would appreciate if you cite my work, in case you are using it for your work. Thank you :-)

@mastersthesis{Kurzer1057261,
    title        = {Path Planning in Unstructured Environments : A Real-time Hybrid A* Implementation for Fast and Deterministic Path Generation for the KTH Research Concept Vehicle},
    author       = {Kurzer, Karl},
    year         = 2016,
    series       = {TRITA-AVE},
    number       = {2016:41},
    pages        = 63,
    issn         = {1651-7660},
    institution  = {KTH, Integrated Transport Research Lab, ITRL},
    school       = {KTH, Integrated Transport Research Lab, ITRL},
    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.}
}
Cited By (not complete)