search

AtsushiSakai / PythonRobotics

Python sample codes for robotics algorithms.
https://atsushisakai.github.io/PythonRobotics/
Other
23.02k stars 6.49k forks source link

RRT star may be improved #382

Closed rafaelrojasmiliani closed 4 years ago

rafaelrojasmiliani commented 4 years ago

Bug description

The RRT star algorithm implemented here seems to be slightly different from the one proposed by Karaman and Frazzoli. In this line the function choose_parent can return None if there are no nodes within the distance r. This prevents adding new nodes to the tree also if they are no collisions in their path to the tree.

Expected behavior

it may be seen in Karaman, Sertac, and Emilio Frazzoli. "Sampling-based algorithms for optimal motion planning." The international journal of robotics research 30.7 (2011): 846-894, algorithm 6 line 7 that the result of steer is added to tree if they are no collisions in its straight path to the nearest point. Then its parent is computed between lines 9 and 13. If there are no nodes within the distance r, its parent results to be the nearest point.

Note

Please, correct me if I'm wrong. Otherwise if it is possible I can fix this and provide my contribution.

Desktop

Ubuntu 18.04, Python3

AtsushiSakai commented 4 years ago

Thank you for your report. Could you please create a PR? let’s discuss in the PR.