CSCE 452/752 Robotics and Spatial Intelligence, Spring 2026
Homework 18
Geno is writing code that implements the RRT algorithm. When adding new
nodes to the tree, his implementation extends toward the random sample by at
most 2 units.
In one of his tests, Geno's implementation produced a very unusual sequence
of samples, as shown below. (Spoiler: These samples are chosen to make it
easier to solve this problem by hand by ensuring that the tree edges are all
horizontal or vertical.)
Trace the execution of the RRT algorithm, starting from $q_{\rm
init}=(0,0)$, based on the samples below.
Write the coordinates of the
nearest neighbor in the tree ($q_{\rm near}$) and the new vertex added
($q_{
rm new}$) for each iteration. Draw the resulting tree, including
arrows from each non-root node to its parent.
| Iteration | $q_{\rm rand}$ | $q_{\rm near}$ | $q_{\rm new}$ |
| 1 | (4.7,0.0) | |
|
| 2 | (0.0,-5.1) | |
|
| 3 | (2.0,4.2) | |
|
| 4 | (4.9,0.0) | |
|
| 5 | (-3.3,0.0) | |
|
| 6 | (4.0,-2.1) | |
|
| 7 | (-2.0,4.3) | |
|
