CSCE 452/752: Homework 13 Solutions

[a] Here is a snapshot from the execution of the RRT$^*$ algorithm, showing only part of the tree. Each node is label with its distance value $d$. A new node at $q_{\rm new}$ has been created and connected to the correct parent. Recall that the next step is to potentially rewire the tree, possibly updating the parent pointers and distance values of some other nodes. The dashed circle shows the connection radius used to determine which nodes are close enough to be considered “nearby” to $q_{\rm new}$.

Use a star to mark the nodes whose parent pointer will change. Use a circle to mark the nodes whose distance value will change. If any nodes change both their parent pointer and their distance value, mark them with both a circle and a star. (5 points)

[b] David tries to implement the RRT$^*$ algorithm, but he forgets about the condition that the rewiring step should be restricted to nearby nodes. Instead, his algorithm checks every node in the tree for possible rewiring.

Is David's implementation asymptotically optimal?

YES NO

Circle yes or no. Then give a persuasive argument for your answer. (5 points)

Yes, David's implementation will be asymptotically optimal. Rewiring can only update parent pointers and decrease the $d$ values. So the length of the best path in David's tree will be no longer than the best length in the correct RRT$^*$ tree. David's algorithm will be slower than RRT$^*$, but its solutions will correctly converge to optimal in the same number of iterations or fewer.