# How to implement path planning algorithm considering orientation?

I am developing GUI c++ program to test path planning algorithms: A*, Dijkstra, ....etc in occupancy grid map.

I found many open source codes , but I need to modify them to design a GUI for testing purposes since I am trying to develop new algorithm.

I noticed that the c++ implementations (which is not for ROS) do not consider the rotation or the orientation for robot when deciding the next cell or movement, they only use x and y values with up, down, left, right movements.

Is it enough to consider x and y only?

What about the rotation when I want to use my code in ROS? How to consider it in this case?

x,y may not be enough depends on your vehicle model. You need to use Hybrid A* in case you are using car like model. Refers to the following paper.

paper: Practical Search Techniques in Path Planning for Autonomous Driving

You can have a look at Hybrid A*, a lot more complicated than normal A*, but it takes into account the orientation. Here the paper.

Unfortunately, path planning is more complicated to implement than other algorithm within computer science. If the subject would be a simple audio compression algorithm (mp3) or an array sorting (quicksort) technique, it's possible to discuss the details of how to realize a certain algorithm in C++. In contrast, path planning is a problem from the Artificial Intelligence domain which prevents that the algorithm can be realized in a framework or as a library.

For the concrete problem of an orientation aware path planner some papers were published in the past. The common strategy is to use domain knowledge as a heuristic guidance for a sampling based planner. This description means anything and nothing at the same time. A more elaborated starting point in developing an algorithm from scratch is to program only a path planner annotation system which is able to recognize actions of a human user who controls the robot with a joystick. Such a system would detect, if the robot changes it's direction and what the target location would be. Unfortunately, the task is strongly connected to probabilistic robotics and finite state machine parsers which results into a full blown phd thesis writing projects which goes over 3 years and longer.

• The existance of path planning libraries like: ompl.kavrakilab.org dagoodma.github.io/dppl_code github.com/yrouben/Sampling-Based-Path-Planning-Library contradicts this answer! ... and these are just from the first page of a google search for path planning libraries
– 50k4
Jan 3, 2020 at 8:43
• Path planning is not necessarily connected to probabilistic robotics. Path planning for the Shakey robot at Standford using the Strips framework was done in the 50s, probabilistic robotics (or even modern robotics) did not exist back then
– 50k4
Jan 3, 2020 at 8:45
• Also a finite state machine parser is not at all needed for a path planning!
– 50k4
Jan 3, 2020 at 8:46