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

14

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

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

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

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

giogadi
источник
Я не знаком с метрикой минимальной стоимости оформления, хотя по ее названию я получаю общее представление. Это конкретная функция или класс функций?
DaemonMaker
1
Хороший вопрос: поскольку метрика меняется в зависимости от робота, давайте предположим, что мы смотрим на робота с голономной точкой, движущегося в евклидовом пространстве. В любой конфигурации q у нас есть функция d (q), которая возвращает расстояние между точечным роботом и ближайшим C-препятствием. Следовательно, для пути в конфигурационном пространстве минимальный зазор всего пути равен минимальному значению d (q) для всех q в пути.
Джогади
1
Мета-вопрос: когда мне рекомендуется редактировать исходный вопрос с пояснениями, которые были изложены в комментариях и других ответах?
Джогади
Это хороший мета-вопрос, который получит больше ответов в Robotics meta SE. ;) Впрочем, для ясности лучше отредактировать вопрос. Я особенно рекомендую делать это, когда полученные ответы не соответствуют предполагаемому вопросу.
DaemonMaker

Ответы:

4

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

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

Теорема 11: (Аддитивность функции стоимости.) Для всех , σ 2X f r e e функция стоимости c удовлетворяет следующему: c ( σ 1 | σ 2 ) = c ( σ 1 ) + c ( σ 2 )σ1σ2 Xfreec(σ1|σ2)=c(σ1)+c(σ2)

Который стал (в ссылке 3, проблема 2):

Функция стоимости считается монотонной, в том смысле , что для всех σ1,σ2Σ:c(σ1)c(σ1|σ2)

Что до сих пор не относится к минимальной дистанции.

Обновление: учитывая смягченное ограничение на стоимость пути, ваш предложенный exp (-min_clearance) кажется хорошим.

Джош Вандер Хук
источник
1
Ваш ответ заставил меня понять, что метрика, как я ее описал, на самом деле некорректна. Обычно мы хотим максимально увеличить минимальный зазор по пути, поэтому фактически стоимость пути должна УВЕЛИЧИТЬСЯ, так как минимальный зазор пути УМЕНЬШАЕТСЯ. Первая функция стоимости, которую я имею в виду, это c (sigma) = 1 / min_clearance (sigma), но это оставляет функцию неопределенной на границах препятствий, и я считаю, что RRT * требует закрытия Q_free для того, чтобы доказательства работали , За исключением вопроса о границе, эта новая функция стоимости будет монотонной, как того требует доказательство.
Джогади
1
Я полагаю, что простая функция стоимости, которая позволяет избежать проблемы с границами, может быть c (sigma) = -min_clearance (sigma), но я не уверен, что отрицательная метрика может повлиять на другие части доказательства RRT * ...
giogadi
ϵ>0δXfree
Другая возможная метрика: c (сигма) = exp (-min_clear (сигма))
giogadi
Мне больше всего нравится функция экспоненциальной стоимости.
Джош Вандер Хук
1

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

c(σ)=exp(min_clear(σ))

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

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

kcc(σ)kcTV(σ),σΣ

where TV(σ) 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 σ0 to consist of a single configuration q, meaning the length of σ0 is 0. Our path cost is therefore с(σ0)знак равноехр(-d(Q))>0, что нарушает предположение об ограниченности. Следовательно, эта функция затрат не соответствует требованиям, установленным в статье IJRR, для получения асимптотической оптимальности.

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

giogadi
источник