Coding a Dubins Car Optimal Path Planner

This video shows how to generate the shortest length path for a car that can only move forwards between given start and ending positions. All code is available at demonstrations.wolfram.com/Sh...
Lecture 26a (This video) Dubins car • Coding a Dubins Car Op...
Lecture 26b Homicidal Chauffeur at • the Homicidal Chauffeu...
Lecture 26c Reeds-Shepp car at • Coding a Reeds-Shepp C...
----
• Car wheel Rotate at 18... car driving sideways

[@SteakSawSr]

Awesome! I've been trying to figure this out for a game I'm making and this helped immensely. Thank you!

[@AaronBecker]

Excellent! Please share a link when you're ready!

[@Hyrtsi]

Well done! I did my msc thesis on this subject and had a lot of challenges but also fun. You distilled the key concepts really well

[@AaronBecker]

Thanks! Are you still in robotics?

[@tasnimsarker4653]

This is so interesting, thank you.

[@xianqihe]

Great video, thank you prof!

[@alan2here]

interesting :) thank you

[@calvinsuzuki3075]

Great video! But when facing a real problem, the steering wheel have an angular speed, which means that it takes time to turn the wheel to a certain direction. Its particular hard to make a vehicle follow a trajectory when its L -> R or R -> L, because the wheel have to be really fast OR the car to be very slow or stop while turning the wheel

[@amrgodovich]

Man, you r great!

[@niks6870]

Hello thank you for you explaination. but i have a question. Why for LSR we use pythagore to get the straight line length ? maybe I have a theorie but i let you correct me. we do hypothenus = distance from center for Lstart to Rend side = sqrt(hypothenus *hypothenus /2) //cause each side should have the same length the side length = the straight line between each steering circle am i right ?

[@yafesenessahiner4782]

Firstly, great content thanks for that. I have a one question: by looking at the start and finish positions, can we understand which maneuver type should be used? Are there any faster methods than calculating the length of each maneuver type? I'm trying to increase the speed of the my implementation.

[@AaronBecker]

[yes there are faster methods] The closed form equations for calculating the 6 path types are simple, and only require a few trig calls. By looking at the distance, you can often eliminate 2 of the 6 options. However, the configuration space can be partitioned into cells based on which path type is optimal. These cells are given precisely in Soueres, Philippe, and J-D. Boissonnat. "Optimal trajectories for nonholonomic mobile robots." Robot motion planning and control (2005): 93-170. With that said, in my code for the Reeds-Shepp car, which has 48 options, I calculate all 48 and measure their length, and I still get real time interaction ( see demonstrations.wolfram.com/ShortestPathForForwardAndReverseMotionOfACar/ ).

[@hakankosebas2085]

what about combination of backing up with forward driving to eliminate unreachable areas? can you make a tutorial about it? Also problem be solved when it is not constant speed?

[@AaronBecker]

@hakankosebas2085 ok, I'll make that tutorial! This is often called a Reeds-Shepp car, and I recently made a demo of it. They aren't that hard to code, and it will be fun to share. demonstrations.wolfram.com/ShortestPathForForwardAndReverseMotionOfACar/

[@hakankosebas2085]

@@AaronBecker thanks

[@AaronBecker]

@hakankosebas2085 I made the video for cars that can go forward and backward. Check out kzbin.info/www/bejne/nHLUmZKZrpyYhqs

[@user-oh3xs6ml2x]

I have a question, why u \in [-1, 1], u should \leq 1, but why u can \geq -1?

[@AaronBecker]

u is the amount of steering. If +1 means turn as much as you can to the left, 0 is go straight, and -1 is turn as much as you can to the right.

[@user-oh3xs6ml2x]

@@AaronBecker I do really thanks for your answer, but I still cannot understand. In the vedio, why you can change \dot{\theta}=\frac{1}{L} \tan \phi to \dot{\theta}=u\frac{1}{r_{min}} ,\quad u \in [-1,1]. Let me try to explain(maybe I am not right): (a.) \frac{1}{L} \tan \phi = \frac{1}{R} (b.) R > r_{min}, so we set a control u: u*R = r_{min} (c.) put this formula into R > r_{min}, we get R > u*R. (d.) radium R > 0, so u < 1. Am I right? I just don't know why it should \geq -1. Can u get the value -2,-3 ....?