Due Wednesday, February 18.
Implement the "rapidly exploring random tree" (RRT) algorithm from the LaValle and Kuffner paper, as applied to a steered car. The car can go forwards or backwards, and also follow curves that are no sharper than a certain curvature.
Here is some Java code that you can use for the graphics, to simulate simple motions, and to do collision detection.
The trickiest part of an RRT algorithm may be the nearest-neighbor query. The most obvious way to do this is to loop over all nodes in the current graph, and find the one that is closest to the extension point. This is very inefficient, since there is code to do approximate nearest-neighbor queries in nearly constant time, but acceptable for this project.
You do not have to implement the graph search itself; it is sufficient to just construct a tree that includes the start and the goal (or a configuration "close" to the goal). As output, you should print out a screen shot of the constucted tree for an interesting environment you construct, with four or more obstacles. Also print out the portion of the code you wrote.
Good luck and start early!
