定义最小距离：为简单起见，我们可以考虑在欧几里得空间中运动的点机器人。对于无冲突配置空间中的任何配置$ q $，定义一个函数$ d（q）$，该函数返回机器人与最近的C障碍物之间的距离。对于路径$ \ sigma $，最小间隙$ \ text {min_clear}（\ sigma）$是\ sigma $中所有$ q \ $ d（q）$的最小值。在最佳运动计划中，可能希望最大化与路径上的障碍物的最小距离。这意味着要定义一些成本度量$ c（\ sigma）$，以使$ c $随着最小清除率的降低而增加。一个简单的函数是$ c（\ sigma）= \ exp（-\ text {min_clear}（\ sigma））$。
在介绍$ \ text {RRT} ^ * $的第一篇论文中，对路径成本度量进行了一些假设，以便证明成立；假设之一涉及成本度量的可加性，而上述最小许可度量不适用。但是，在最近的描述该算法的期刊文章中，没有列出一些先前的假设，并且似乎最小清除成本指标也可以通过该算法进行优化。
有谁知道$ \ text {RRT} ^ * $的最优性证明是否可以适用于最小清算成本指标（也许不是我上面给出的，而另一个具有相同的最小值），或者是否已经进行了实验是为了支持算法对此类指标的有用性？
#1 楼
*注意，$ a | b $是路径$ a $和$ b $的串联。然后将$ c（\ cdot）$定义为最小间隙意味着$ c（a | b）= min（c（a），c（b））$您参考（参考文献1 ）：
定理11 ：（成本函数的可加性。）
对于所有
X \ {免费的$ \ sigma_1 $，$ \ sigma_2 $ $ \ } $
，成本函数c满足以下条件：
$ c（\ sigma_1 | \ sigma_2）= c（\ sigma_1）+ c（\ sigma_2）$
（在参考文献3中，问题2）已变为：
成本函数被假定为单调的，在某种意义上，对于所有$ \ sigma_1，
， \ sigma_2 \ in \ Sigma：c（\ sigma_1）\ leq c（\ sigma_1 | \ sigma_2）$
最小间隙距离仍然不是这样。
更新：鉴于宽松的路径成本限制，建议的exp（-min_clearance）看起来不错。
评论
$ \ begingroup $
您的回答使我意识到，正如我所描述的，该指标实际上是错误的。我们通常希望最大化路径上的最小间隙，因此，实际上，路径的成本应增加，因为路径的最小间隙减少了。为此，我想到的第一个成本函数是c（sigma）= 1 / min_clearance（sigma），但这使该函数在障碍物边界处未定义，我相信RRT *需要关闭Q_free才能使证明起作用。除非存在边界问题，否则新的成本函数将如证明所要求的那样单调。
$ \ endgroup $
– giogadi
2012-12-12 15:39
$ \ begingroup $
我想避免边界问题的简单成本函数可以是c（sigma）= -min_clearance（sigma），但是我不确定使用负度量对RRT *证明的其他部分有什么影响。 ..
$ \ endgroup $
– giogadi
2012-12-12 16:16
$ \ begingroup $
本文明确假定成本$ \ geq $为零。您可以将配置空间扩展$ \ epsilon> 0 $来解决触摸边界的奇异之处，但是本文还假定$ \ delta $ -clearance，这可能会与更改$ X_ {free} $产生冲突。我认为您现在正在尝试回答一个不同的问题，这可能需要进行一些讨论，采用这种格式并不容易。
$ \ endgroup $
–乔什·范德·胡克（Josh Vander Hook）
2012-12-12 19:42
$ \ begingroup $
另一种可能的度量标准：c（sigma）= exp（-min_clear（sigma））
$ \ endgroup $
– giogadi
2012年12月12日19:44
$ \ begingroup $
我最喜欢指数成本函数。
$ \ endgroup $
–乔什·范德·胡克（Josh Vander Hook）
2012年12月12日19:46
#2 楼
在上一个答案中，我们同意将成本函数定义为$ c（\ sigma）= \ text {exp}（-\ text {min_clear}（\ sigma））$
将满足RRT *在此指标下产生渐近最优性所需的属性。本文中的假设。具体来说，此成本函数违反了boundedness属性，定义为：
$ \存在k_c \ quad c（\ sigma）\ leq k_c \ text {TV}（\ sigma），\ forall \ sigma \在\ Sigma $
中，其中$ \ text {TV}（\ sigma）$是路径的总变化量，本质上是路径的欧几里得长度。在这种有界假设下，长度为0的路径的成本也必须为0。
让我们定义路径$ \ sigma_0 $由单个配置$ q $组成，即$ \ sigma_0 $为0。因此，我们的路径成本为$ c（\ sigma_0）= \ text {exp}（-d（q））> 0 $，这违反了有界假设。因此，此成本函数不满足IJRR文章中设定的产生渐近最优性的要求。
我想知道RRT *是否不会在这样的成本函数下简单地产生渐近最优解，或者是否仍然可能但也许这些假设简化了本文中的最优性证明。
评论
我对最小清关成本度量标准不熟悉，尽管通过它的名字我可以大致了解。是特定功能还是一类功能？很好的问题：由于指标因机器人而异，因此我们假设我们正在研究一个在欧几里德空间中移动的完整点机器人。在任何配置q下，我们都有一个函数d（q），该函数返回点机器人与最近的C障碍物之间的距离。因此，对于配置空间中的路径，整个路径的最小间隙是路径中所有q的d（q）的最小值。
元问题：建议我什么时候编辑原始问题，并在注释和其他答案中阐明清楚的内容？
这是一个很好的元问题，并且会在Robotics meta SE中获得更多响应。 ;）不过，为清楚起见，最好编辑问题。我特别建议您在得出的答案与预期的问题不符时这样做。