# Does RRT* guarantee asymptotic optimality for a minimum clearance cost metric?

The optimal sampling-based motion planning algorithm $\text{RRT}^*$ (described in this paper) has been shown to yield collision-free paths which converge to the optimal path as planning time increases. However, as far as I can see, the optimality proofs and experiments have assumed that the path cost metric is Euclidean distance in configuration space. Can $\text{RRT}^*$ also yield optimality properties for other path quality metrics, such as maximizing minimum clearance from obstacles throughout the path?

To define minimum clearance: for simplicity, we can consider a point robot moving about in Euclidean space. For any configuration $q$ that is in the collision-free configuration space, define a function $d(q)$ which returns the distance between the robot and the nearest C-obstacle. For a path $\sigma$, the minimum clearance $\text{min_clear}(\sigma)$ is the minimum value of $d(q)$ for all $q \in \sigma$. In optimal motion planning, one might wish to maximize minimum clearance from obstacles along a path. This would mean defining some cost metric $c(\sigma)$ such that $c$ increases as the minimum clearance decreases. One simple function would be $c(\sigma) = \exp(-\text{min_clear}(\sigma))$.

In the first paper introducing $\text{RRT}^*$, several assumptions are made about the path cost metric so that the proofs hold; one of the assumptions concerned additivity of the cost metric, which doesn't hold for the above minimum clearance metric. However, in the more recent journal article describing the algorithm, several of the prior assumptions weren't listed, and it seemed that the minimum clearance cost metric might also be optimized by the algorithm.

Does anyone know if the proofs for the optimality of $\text{RRT}^*$ can hold for a minimum clearance cost metric (perhaps not the one I gave above, but another which has the same minimum), or if experiments have been performed to support the algorithm's usefulness for such a metric?

-
I'm not familiar with the minimum clearance cost metric, though by its name I get the general idea. Is it a specific function or a class of functions? – DaemonMaker Dec 10 '12 at 18:36
Good question: since the metric varies depending on the robot, let's assume that we're looking at a holonomic point robot moving about in Euclidean space. At any configuration q, we have a function d(q) which returns the distance between the point robot and the closest C-obstacle. Therefore, for a path in configuration space, the minimum clearance of the entire path is the minimum value of d(q) for all q in the path. – giogadi Dec 10 '12 at 18:42
Meta-question: when is it recommended for me to edit the original question with clarifications that have been spelled out in comments and other answers? – giogadi Dec 12 '12 at 15:42
This is a good meta-question and would get more response in the Robotics meta SE. ;) However, it's generally good to edit the question for clarity. I especially recommend doing so when the answers elicited aren't inline with the intended question. – DaemonMaker Dec 12 '12 at 18:10

*Note, $a|b$ is the concatenation of paths $a$ and $b$. Then $c(\cdot)$ defined as the minimum clearance implies $c(a|b)=min(c(a),c(b))$

You refer to (in reference 1):

Theorem 11: (Additivity of the Cost Function.) For all $\sigma_1$,$\sigma_2$ $\in X_{free}$ , the cost function c satisﬁes the following: $c(\sigma_1|\sigma_2) = c(\sigma_1) + c(\sigma_2)$

Which has become (in reference 3, Problem 2):

The cost function is assumed to be monotonic, in the sense that for all $\sigma_1,\sigma_2\in\Sigma:c(\sigma_1)\leq c(\sigma_1|\sigma_2)$

Which is still not the case for minimum clearance distance.

Update: Given the relaxed restriction on path costs, your suggested exp(-min_clearance) seems fine.

-
Your answer made me realize that the metric as I've described it is actually ill-posed. We typically want to MAXIMIZE minimum-clearance over a path, so in fact the cost of a path should INCREASE as the minimum clearance of a path DECREASES. The first cost function I have in mind for this is c(sigma) = 1/min_clearance(sigma), but this leaves the function undefined at obstacle boundaries, and I believe RRT* requires Q_free to be closed in order for the proofs to work. Barring the boundary issue, this new cost function would be monotonic as the proof requires. – giogadi Dec 12 '12 at 15:39
I suppose a simple cost function that avoids the boundary issue could be c(sigma) = -min_clearance(sigma), but I'm not sure what having a negative metric might do to other parts of the RRT* proof... – giogadi Dec 12 '12 at 16:02
The paper explicitly assumes cost $\geq$ zero. You can expand the configuration space by some $\epsilon > 0$ to address the singularity of touching the boundary, but the paper also assumes $\delta$-clearance, and that might cause a conflict with altering $X_{free}$. I think you are trying to answer a different question now, and this might involve some discussion, which isn't easy in this format. – Josh Dec 12 '12 at 19:42
Another possible metric: c(sigma) = exp(-min_clear(sigma)) – giogadi Dec 12 '12 at 19:44
I like the exponential cost function best. – Josh Dec 12 '12 at 19:46

In a previous answer, we came to agree that a cost function defined as

$c(\sigma) = \text{exp}(-\text{min_clear}(\sigma))$

would satisfy the properties required for RRT* to yield asymptotic optimality under this metric.

However, upon reviewing the IJRR article which describes RRT*, this cost function does not technically satisfy the assumptions made in the article. Specifically, this cost function violates the boundedness property, defined as:

$\exists k_c \quad c(\sigma) \leq k_c\text{TV}(\sigma), \forall \sigma \in \Sigma$

where $\text{TV}(\sigma)$ is the total variation of a path, which is essentially the path's Euclidean length. Under this boundedness assumption, a path of length 0 must also have a cost of 0.

Let's define a path $\sigma_0$ to consist of a single configuration $q$, meaning the length of $\sigma_0$ is 0. Our path cost is therefore $c(\sigma_0) = \text{exp}(-d(q)) > 0$, which violates the boundedness assumption. Therefore, this cost function does not meet the requirements set in the IJRR article to yield asymptotic optimality.

I wonder if RRT* simply will not yield asymptotically optimal solutions under such a cost function, or if it still might but perhaps those assumptions simplified the optimality proofs in the paper.

-