1
$\begingroup$

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

enter image description here

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.

$\endgroup$
  • $\begingroup$ Can you post the link to the rest of the slides? Can you explain what the variable D represents? Can you explain what the rest of the variables mean? There are many ways to implement this algorithm and the slide doesn't contain much context by itself. $\endgroup$ – Richard Jul 2 at 20:02
  • $\begingroup$ dropbox.com/s/uycwnr2v82ikafp/13.%20Exercises.pdf?dl=0 Pages: 65-69 $\endgroup$ – Teo Protoulis Jul 2 at 20:05
  • $\begingroup$ Is there a possibillity that the value by which we multiply $\ D_{exp} $ at each iteration is random as well ? $\endgroup$ – Teo Protoulis Jul 2 at 20:17
  • 1
    $\begingroup$ συγγνώμη. It's been a while since I've studied Greek. It would be easier for me, and more useful to you (since some people have never studied Greek), if you edited your question to provide additional information and context. $\endgroup$ – Richard Jul 2 at 20:20
  • $\begingroup$ I don't think you should understand Greek in order how the D value is being updated. Howver, I think that the values we need to update the D value and moreover find the coordinates of $\ x_{new} $ is random and maybe given. $\endgroup$ – Teo Protoulis Jul 2 at 20:23
2
$\begingroup$

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.
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.