I am developing an RRT (rapidly exploring random tree) for car-like robots in SE2 space using Dubins steering function and have a question that has implications on the performance of RRTs.

In order for an RRT to be performant, an efficient nearest neighbor data structure needs to be used. There are efficient nearest neighbor data structures for metric spaces (like Euclidean space), however, none that I know of for a non-metric space (like the Dubins space).

This leads me to wonder if I can use a different distance function than the Dubins curve length in my RRT despite using the Dubins steering function to connect states.


1 Answer 1


I asked this question on OMPL's mailing list. OMPL is an very popular motion planning library. Here is the response: https://sourceforge.net/p/ompl/mailman/message/35918890/

The answer is yes, they should be related.


Your Answer

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

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