search

motion-planning / rrt-algorithms

n-dimensional RRT, RRT* (RRT-Star)
MIT License
600 stars 173 forks source link

Add c_best update into lazy shortening. #21

Closed tahsinkose closed 5 years ago

tahsinkose commented 5 years ago

PR for #19 . Since lazyShortening shortens the path, there was a need for c_best update.

I also added a randomly generated world example.

SZanlongo commented 5 years ago

Good catch. Actually, I'm thinking that rather than iterate over all of 'sigma_best', we can do something like: Assume a function pairwise that does a pairwise traversal of a list. self.c_best = self.c_best - sum(distance_between_points(i,j) for i,j in pairwise(p[a:b]))+distance_between_points(self.sigma_best[a], self.sigma_best[b])

Naturally this would go before updating sigma_best. This should have the same effect, but only iterate over the portion of the path that will be removed, rather than the entire list (which would be the worst-case scenario).

Does that sound good, or would it be outweighed by being a bit more unfriendly to read?

tahsinkose commented 5 years ago

Well, I'm okay with any of the solutions. An analysis on an extreme case (e.g. 1000x1000x1000 3D volume with 1000 randomly scattered obstacles) should enlighten the need for such an optimization. And also it depends on the goal of this repository. If you want a practical application, then this optimization would be definitely useful. If you want to sustain an educational codebase (the reason why I have found myself in here at the first place :smiley: ), I believe readability is more important.

Nevertheless in your version, I think a detailed comment above the line for this operation becomes necessary. Let me make a stress test in weekend and see if it is really necessary to do such an optimization. Naturally, if you have time you can do as well.