Car RRT Path Planning

Non-holonomic motion planning, rapidly-exploring random tree.

Car RRT Path Planning

I saw an interesting image on the book Planning Algorithms, showing the path planning result for a car which can only turn left to drive through a complex environment. Thus I want to do the non-holonomic planning by myself.

So the first step should be implementing an RRT. And to achieve good execution time of fining closest nodes, it is neccesary to implement an underlying kd-tree.

Then we need a local planner which could give us a feasible solution for simple situations. It is not hard to derive a method to plan a path using the series of circles which lies to the left of the initial and terminal states. Just find the tangent circles, since we do not really need to guarantee to find a solution or find the optimal solution.

And it worked. Although since there's nothing to tell the car that we do not want to go reverse, the planned trajectory was full of segments of driving reverse :)