1
$\begingroup$

Hello robotics stack exchange community, hope my message finds you well during these challenging times. I need an opinion regarding path planning algorithms.

Goal

I am looking for a path planning algorithm that is able to produce smooth paths that are shorter and more predictable than RRT and RRT*. It shouldn't get stuck in local minima like Artificial Potential Field.

What I tried

I have set up a Linux 16 system with ROS Kinetic Kame and Python. I implemented Artificial Potential Field Path Planning, RRT and RRT* and ran those on a robot in a small arena. The arena was a square and I placed different objects inside of it that needed to be avoided. See the picture below for an example of how my arena configuration looks like. enter image description here

Artificial Field Path Planning creates nice, smooth curves and a robot executes smooth movements to follow it. My problem with them is local minima where my robot gets stuck.

RRT produced jagged paths, but the nice thing about it was that it always found a path (albeit it was always a different one). I implemented RRT* to get smoother paths, but they're quite "branchy" looking (still better than RRT though).

I have also looked into other algorithm such as A* and MEA, but rather than trying to implement them straight away, I wanted to ask for your opinion.

Improve this question
$\endgroup$

3 Answers 3

Reset to default
1
$\begingroup$

My understanding is that most people don't use the raw RRT solution directly. First they smooth it. A google search will yield many papers on this. For example: Improved Path-Finding Algorithm for Robot Soccers by Rahib H. Abiyev, Nurullah Akkaya, Ersin Aytac, Irfan Günsel, and Ahmet Çağman.

The smoothed trajectory will necessarily be different than the RRT path and will therefore have a possibility of collision. So you will have to check for that and possibly adjust the smoothing parameters iteratively.

You can also use a more modern motion planner. CHOMP is a popular one. Original paper: CHOMP: Covariant Hamiltonian Optimization for Motion Planning by Matt Zucker, Nathan Ratliff, Anca D. Dragan, Mihail Pivtoraiko, Matthew Klingensmith, Christopher M. Dellin, J. Andrew Bagnell, Siddhartha S. Srinivasa.

Another idea is to use a completely different approach. TrajOpt is an optimization based approach and produces smooth trajectories without a secondary smoothing step. Paper here: Motion Planning with Sequential ConvexOptimization and Convex Collision Checking by John Schulman, Yan Duan, Jonathan Ho, Alex Lee, Ibrahim Awwal, Henry Bradlow, Jia Pan, Sachin Patil, Ken Goldberg, Pieter Abbeel.

Improve this answer
$\endgroup$
0
$\begingroup$

You can apply rrt using a selection of smooth movements, basically you discritize the possible actions making sure you always connect paths in a way which is smooth. It increases the dimensionality of your problem by quite a bit though, so idk.

Improve this answer
$\endgroup$
1
  • $\begingroup$ Thank you for your input. I assume you are talking about using motion primitives or things like RRT Star Dubins? I have tried both, in any case. Although I didn't articulate it in the question as such, I was looking for an algorithm such as A*. I was looking for an algorithm that produces the same paths given that it starts from the same point -> i have done some research in the meantime and that's how I came to the conclusion that I needed something like A* Nonetheless, I upvoted your comment (sadly it won't display since i've got less than 15 rep :( ) $\endgroup$
    – Nikthebrick
    Apr 18, 2020 at 2:28
0
$\begingroup$

First some notes:

  • RRT* is not an optimal algorithm, it just tends to converge to the optimal path as time approaches infinity. Similarly, it is not guaranteed that it will find a path (even though it usually finds it with enough time). In other words it is a probabilistically complete algorithm.
  • A*-derivates are resolution complete. If the resolution is low enough to find a path, it will find it, and it will be the optimal path as long as a) the heuristic is admissible (never overestimates the real distance to the goal) and b) consistent (the heuristic of the goal node is 0 and the triangle inequality is fulfilled).

In my experience, I would encourage you to deep further into A* derived planners for your use-case. More specifically, take a look at Hybrid A* which takes into account continuous values within the discrete grid, thus allowing motion constraints to be taken into account.

Take this paper in which Hybrid A* is adapted to work in the 3D (underwater) space with AUV constraints, for example. The algorithm (for 2D) is explained there as well: https://www.mdpi.com/1424-8220/21/4/1152.

Hope this helps.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.