Broad area/overview

This paper deals with sampling-based algorithms for optimal motion planning, specifically Rapidly-exploring Random Trees (RRTs) and conditions under which this algorithm is non-optimal. It then goes on to compare RRTs to a newer algorithm, Rapidly-exploring Random Graphs (RRGs) and even introduces an implementation of RRGs that is structured similarly to RRTs called RRT*.

This paper goes over these new algorithms and investigates their optimality and computational complexity in comparison with the conventional RRTs.

Notation

• \(X\): The space of all possible robotic states.

• \(X_{free}\): The space of all robotic states that also avoid obstacles within the workspace.

• \(x\): A robotic state in space \(X\)

• \(x_{rand}\): A random sample of X.

• \(V\): The vertex space. This is a subset of X and is what has been sampled of it so far using \(x_{rand}\)

• \(E\): The edge space of vectors describing connections between to \(x\) in \(V\).

• \(G\): The graph space; \(G = (V, E)\)

• \(x_{new}\): The current robotic state in space \(X\).

• \(x_{nearest}\): The nearest \(x\) in \(V\) to the \(x_{new}\).

• \(X_{near}\): All \(x\) in \(V\) that is within some determined radius to \(x_{new}\)

• \(x_{near}\): An element in \(X_{near}\)

• ObstacleFree: A primitive function call that establishes that an edge between two vertices has no obstacles.

Specific Problem

A major struggle of sampling based approaches is optimality guarantees. That is, finding the most efficient obstacle free path in the workspace. In technical terms, RRTs likelihood to converge to some solution is 1 as the number of samples approaches infinity, but converges to 0 for finding the optimal solution. Nevertheless, the computational efficiency of sampling-based approaches is unrivaled and therefore the problem this paper aims to solve is to create a sampling-based algorithm with asymptotic optimality guarantees that maintains the computational efficiency of RRTs.

Solution Ideas

• The sampling approach of \(X_free\) is the same for both RRT and RRG.

• The major algorithmic difference between RRTs and RRGs are in their extension of their path at each sampling point. The RRT's extension attempts to tell if the edge between the current \(x\) and \(x_{nearest}\) are continuously in the \(X_{free}\) space. The RRG's however check this edge for all \(X_{near}\).

• The resulting graph maintained by these algorithms differ in structure. The RRT's algorithm resembles a tree with only one incoming neighbor while the RRG can have multiple.

• It formalizes that the RRG and RRT have the same performance in producing a feasible solution due to their similarity.

• Qualifying runtime complexity in terms of number of primitive calls sees that the RRG has an overhead of \(log(n)\) more calls to ObstacleFree than RRT where n is the number of sampled vertices. However, some primitive calls are more complex than others and, in particular, ObstacleFree can be done in constant time (\(O(1)\)) and therefore does not contribute to the worst-case complexity of RRG.

• RRT* differs from RRT and RRG only in its Extend procedure as well.

• RRT* uses accumulated cost to determine the path that G takes. Each iteration it connects \(x_{new}\) to the \(x_{near}\) that incurs the minimum accumulated cost up until \(x_{new}\). It also tracks the edges of \(x_{new}\) to \(X_{near}\) in order to be able to rewire G given that a new, lower-cost path arises.

• RRT* assures convergence to a feasible solution and asymptotic optimality while retaining the tree structure of RRT.

• Runtime complexity from RRT* to RRT is a ratio that converges to a constant value implying that they have the same O.

Comments

• This paper analytically compares 3 sampling-based trajectory planning approaches.

• Figure 3 and 4 represents the difference in optimality and behaviour of the algorithms very well.

• They do not address dynamic obstacles or differential constraints and it comes to concern that there is a possibility that some of their assumptions about the environment to get to optimality and solution convergence break down when these are introduced.

• They assume the primitive functions they use to be solved algorithms already which is reasonable but could see largely different results in each algorithms performance if you use suboptimal primitive functions. An investigation on optimizing these primitive functions for each would be interesting.

Recent Papers

• Flat-RRT*: A sampling-based optimal trajectory planner for differentially flat vehicles with constrained dynamics - this deals with the more real-world constraints that could violate some assumptions.

• Efficient Exploration of Protein Conformational Pathways using RRT* and MC - Application of RRT* in protein pathways.

• RRT*N: an efficient approach to path planning in 3D for Static and Dynamic Environments - RRT* with handling dynamic environments.