I've been looking into path planning for a non-holonomic robot with 3 DOF in a 2D plane and recently learned about Voronoi diagrams but I cannot find any open source planning libraries that use this technique. Are there any open source implementations of using Voronoi diagrams (preferably in C++)? If yes, then where? If not, then why?

  • $\begingroup$ Are you looking for something like this? github.com/ptroja/voronoi If you just want to use Voronoi diagrams as a representation of 'frontiers', sampling based planners like RRT etc. exploit their Voronoi bias to quickly sample a 2D space and compute a possibly optimal path. Unless there's something specific you have in mind for why you need Voronoi diagrams. $\endgroup$ – HighVoltage Feb 28 '17 at 3:26
  • $\begingroup$ If you're using voronoi regions as obstacle avoidance, I would highly recommend another approach. The voronoi approach leads to very conservative paths $\endgroup$ – combo Feb 28 '17 at 4:56
  • $\begingroup$ @HighVoltage As I understand it, sampling based algorithms like RRT develop Voronoi bias because the Voronoi lines will lie in open (mostly) collision free areas. The bias just comes about as a result and not by pre computing. I found this paper to be very interesting regarding the subject. $\endgroup$ – Klik Feb 28 '17 at 14:39
  • $\begingroup$ @combo could you elaborate as to why you would recommend another approach? It's part of my question to ask why I don't see a Voronoi diagram approach in open source libraries. I'm not aware of any fatal flaws. $\endgroup$ – Klik Feb 28 '17 at 14:40
  • $\begingroup$ @Klik I was referring to a planner which forms a Voronoi diagram using obstacles as centers, and then plans paths on the edges of the resulting diagram (such as this). This planner will go very far out of its way to avoid an obstacle, so if you have any wide open spaces you will likely be disappointed by the resulting behavior. I am less familiar with using voronoi bias, but given that it is an old paper by a good author which has gotten little traction, I am skeptical. Have you considered kinoRRT or kinoFMT? $\endgroup$ – combo Feb 28 '17 at 17:17

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.