Jingren Xu

Jingren Xu

PhD student in Robotics

Why is RRT efficient?

less than 1 minute read

Published:

Trajectory optimization is a local method, it only explores the neighborhood of an initial seed, besides, in the direct transcription, we discretize along the trajectory instead of every dimension of the C-space, thus it scales well in high dimensional space. But RRT is a global method, what makes it efficient in exploring a collision-free path in high dimensional space?

  • Voronoi bias, the nodes in the search tree with the largest Voronoi regions tend to be selected for exploration.
  • It does not explicitly construct the C-space. We leave the planing “in the dark”, the only light is provided by a collision detection algorithm.

But how about the cost of searching for the nearest neighbors?

  • RRT*:

  • Informed RRT*:

  • BIT*:

Reference:

Lindemann, Stephen R., and Steven M. LaValle. “Incrementally reducing dispersion by increasing Voronoi bias in RRTs.” IEEE International Conference on Robotics and Automation, 2004. Proceedings. ICRA’04. 2004. Vol. 4. IEEE, 2004.

To be continued…

You May Also Enjoy

Convex optimization, QP, SQP

3 minute read

Published:

Definition of convex function

For all ${ 0\leq t \leq 1}$ and all ${ x_{1},x_{2}\in X,}$ ${ f\left(tx_{1}+(1-t)x_{2}\right)~\leq ~tf\left(x_{1}\right)+(1-t)f\left(x_{2}\right).}$

Quadratic forms and Convexity

Quadratic form in variables ${ x_1,x_2…, x_n}$ is a polynomial function $Q$, where all the terms in $Q(x_1, x_2,…, x_n)$ have order two. Quadratic functions $\neq$ convex functions.

Simulated Annealing

less than 1 minute read

Published:

Simulated Annealing is a probabilistic method for approximating the global optimum of a given function. It is helpful especially in the case of large search space.

  • Make use of randomness, random walk on a search graph.
  • Transition probabilities..
  • Higher probability of accepting worse solutions in the begining (high temperature).