Path planning algorithm better than RRT* and Artificial Potential Field

Question

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.

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.

FourierFlux · Answer

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.

Answered by FourierFlux on December 21, 2020

Ben · Answer

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.

Path planning algorithm better than RRT* and Artificial Potential Field

Goal

What I tried

2 Answers

Add your own answers!

Ask a Question