Гарантирует ли RRT * асимптотическую оптимальность для минимальной метрики клиренса?

Было показано, что оптимальный алгоритм планирования движения на основе выборки (описанный в этой статье ) дает пути без столкновений, которые сходятся к оптимальному пути при увеличении времени планирования. Однако, насколько я вижу, доказательства оптимальности и эксперименты предполагали, что метрика стоимости пути - это евклидово расстояние в конфигурационном пространстве. Может ли также дать свойства оптимальности для других метрик качества пути, например, для максимального уменьшения минимального зазора от препятствий на всем пути?$\text{RRT}^*$$\text{RRT}^*$

Чтобы определить минимальный зазор: для простоты мы можем рассмотреть точечного робота, движущегося в евклидовом пространстве. Для любой конфигурации которая находится в пространстве конфигурации без столкновений, определите функцию которая возвращает расстояние между роботом и ближайшим C-препятствием. Для пути минимальный зазор является минимальным значением для всех . При оптимальном планировании движения можно пожелать максимизировать минимальный зазор от препятствий на пути. Это будет означать определение некоторой метрики стоимости такой, что$q$$d(q)$$\sigma$$\text{min_clear}(\sigma)$$d(q)$$q \in \sigma$$c(\sigma)$$c$увеличивается при уменьшении минимального зазора. Одной простой функцией была бы $c(\sigma) = \exp(-\text{min_clear}(\sigma))$ .

В первой статье, вводящей $\text{RRT}^*$ , делается несколько предположений о метрике стоимости пути, так что доказательства выполнены; одно из предположений касалось аддитивности метрики стоимости, которая не выполняется для вышеуказанной минимальной метрики клиренса. Однако в более поздней журнальной статье, описывающей алгоритм, некоторые из предыдущих предположений не были перечислены, и казалось, что минимальная стоимость клиренса также может быть оптимизирована алгоритмом.

Кто-нибудь знает, могут ли доказательства оптимальности иметь место для минимальной метрики клиренса (возможно, не той, что я дал выше, а для другой, которая имеет такой же минимум), или были ли проведены эксперименты для поддерживать полезность алгоритма для такой метрики?$\text{RRT}^*$

* Обратите внимание, | b - это конкатенация путей a и b . Тогда c ( ⋅ ), определенный как минимальный зазор, подразумевает c ( a | b ) = m i n ( c ( a ) , c ( b ) )$a|b$$a$$b$$c(\cdot)$$c(a|b)=min(c(a),c(b))$

Вы ссылаетесь (в ссылке 1):

Теорема 11: (Аддитивность функции стоимости.) Для всех , σ 2 ∈ X f r e e функция стоимости c удовлетворяет следующему: c ( σ 1 | σ 2 ) = c ( σ 1 ) + c ( σ 2$\sigma_1$$\sigma_2$ $\in X_{free}$$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) кажется хорошим.

В предыдущем ответе мы пришли к соглашению, что функция стоимости определяется как

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

будет удовлетворять свойствам, необходимым для RRT *, чтобы получить асимптотическую оптимальность при этой метрике.

Однако при просмотре статьи IJRR, в которой описывается RRT *, эта функция затрат технически не удовлетворяет сделанным в статье допущениям. В частности, эта функция стоимости нарушает свойство ограниченности , определяемое как:

$\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$, что нарушает предположение об ограниченности. Следовательно, эта функция затрат не соответствует требованиям, установленным в статье IJRR, для получения асимптотической оптимальности.

Интересно, если RRT * просто не даст асимптотически оптимальных решений при такой функции стоимости, или все-таки может, но, возможно, эти предположения упростили доказательства оптимальности в статье.