How is the D value being updated at simple RRT algorithm?

Question

I am studying the following lecture (image) regarding 5 iterations of the simple RRT algorithm.

I am trying to understand how each value is being updated regarding each iteration. I have figured out how everything is being updated except the way by which the D value is being updated.

DATA: Initial pose of robot is (5,15) , $\ D_{wall} = 0 $ , $\ D_{exp} = 5 $ and goal is at (18,4). We don't need to reach the goal just perform the 5 iterations.

Answer 1

I don't think $D$ is updated at all. It is just a temporary value for $D_{exp}$ times uniform random value in [0,1].

As a general remark, RRT means Rapidly-exploring Random Tree. Hence, the algorithm will involve branching and random directions with step sizes.

On the left hand slide of the slide there is a column list of the random numbers used. Strike-through means they have been expended. In the middle there is the grid which we need to explore. "R" marks the initial robot position, "G" is the goal. The thick lines mark a wall where the robot cannot pass. The green dots mark the step the robot takes (one per iteration), blue marks a proposed step.

The algorithm then proceeds as follows:

1. Branch
2. Create random directions
3. Step in random directions and check for walls
4. If wall, branch dies. If not, branch continues at 1. or 2. (when it branches again is not possible to judge from the slide)

In more detail, each of the steps involves the following:

1. Branch:
   • from the slide it is only possible to guess but seemingly we start with initially two branches. Therefore, iteration 1 and 2 start at the same $x_{near}$.
   • this is not done in every iteration. Conditions may depend on number of still active branches and number of steps till last branching.
2. Create a random direction:
   • The size of the grid is [20,20]. Hence, we pick a random point on the grid by multiplying the size with values drawn from [0,1], for examle $0.5$ for x and $1$ for y in the first step, giving the random spot $x_{rand} = [10, 20]$,
   • This random spot $x_{rand}$ together with the current position in $x_{near}$ gives the random direction (vector from near to rand). This direction is normalized but from the slides I can only guess that a sort of Manhattan norm is used.
   • Then a step size is randomly calculated. The maximum size is $D_{exp}$, i.e. 5. Again, we draw a random value and multiply with the maximum and take the truncated integer value, i.e. 2.825 becomes a step size of 2, such that we only move on grid points. This step size times the normalized direction starting from the current branch's $x_{near}$ is our candidate for $x_{new}$.
3. Step and check
   • For each proposed new position we check whether we hit a wall. This is the case for $x_{near} = [7,17]$ in iteration #3: direction [13,-7] leads through a wall. As $D_{wall}=0$, we eliminate this branch (mark: crossed out).
   • for all other steps, the proposed step is accepted and becomes the new $x_{near}$ for this branch (mark: tick).
4. Go to 1 for each still active branch.