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

Question

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?

Answer 1

*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 satisfies 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.

Answer 2

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.