Czy RRT * gwarantuje asymptotyczną optymalizację przy minimalnym koszcie rozliczenia?

Wykazano, że optymalny algorytm planowania ruchu oparty na próbkowaniu (opisany w tym artykule ) daje ścieżki bezkolizyjne, które zbiegają się z ścieżką optymalną wraz ze wzrostem czasu planowania. Jednak, o ile widzę, dowody optymalności i eksperymenty przyjęły, że metryką kosztu ścieżki jest odległość euklidesowa w przestrzeni konfiguracji. Can również wydajność właściwości optymalności dla innych metryk jakości ścieżka, takich jak maksymalizacji minimalny odstęp od przeszkody całej ścieżce? $\text{RRT}^*$ $\text{RRT}^*$

Aby zdefiniować minimalny prześwit: dla uproszczenia możemy rozważyć robota punktowego poruszającego się w przestrzeni euklidesowej. Dla każdej konfiguracji która znajduje się w przestrzeni konfiguracji wolnej od kolizji, zdefiniuj funkcję która zwraca odległość między robotem a najbliższą przeszkodą C. Dla ścieżki minimalny luz to minimalna wartość dla wszystkich . W optymalnym planowaniu ruchu można zmaksymalizować minimalny odstęp od przeszkód na drodze. Oznaczałoby to zdefiniowanie niektórych wskaźników kosztów $q$ $d(q)$ $\sigma$ $\text{min_clear}(\sigma)$ $d(q)$ $q \in \sigma$ tak, że wzrasta wraz ze spadkiem minimalnego luzu. Jedną prostą funkcją byłoby . $c(\sigma)$ $c$ $c(\sigma) = \exp(-\text{min_clear}(\sigma))$

W pierwszym artykule wprowadzającym poczyniono kilka założeń dotyczących metryki kosztu ścieżki, tak aby zachowały się dowody; jedno z założeń dotyczyło addytywności metryki kosztu, która nie dotyczy powyższej metryki luzu minimalnego. Jednak w najnowszym artykule w czasopiśmie opisującym algorytm nie wymieniono kilku wcześniejszych założeń i wydawało się, że algorytm może również zoptymalizować metrykę minimalnego kosztu rozliczenia. $\text{RRT}^*$

Czy ktoś wie, czy dowody na optymalności może trzymać za koszt minimalny prześwit metrycznym (być może nie jeden dałem powyżej, ale inny, który ma taką samą minimum), lub jeśli eksperymenty zostały przeprowadzone w celu wspierania przydatność algorytmu dla taka metryka? $\text{RRT}^*$

— Giogadi
źródło

Nie znam miary minimalnego kosztu odprawy, choć z jej nazwy mam ogólny pomysł. Czy jest to konkretna funkcja czy klasa funkcji?

— DaemonMaker,

Dobre pytanie: ponieważ metryka różni się w zależności od robota, załóżmy, że patrzymy na holonomicznego robota punktowego poruszającego się w przestrzeni euklidesowej. W dowolnej konfiguracji q mamy funkcję d (q), która zwraca odległość między robotem punktowym a najbliższą przeszkodą C. Dlatego dla ścieżki w przestrzeni konfiguracyjnej minimalny prześwit całej ścieżki jest minimalną wartością d (q) dla wszystkich q na ścieżce.

— giogadi,

Metapytanie: kiedy zaleca się edytowanie oryginalnego pytania z wyjaśnieniami zawartymi w komentarzach i innych odpowiedziach?

— giogadi,

To dobre meta-pytanie i uzyskałoby więcej odpowiedzi w metodzie SE Robotics . ;) Jednak generalnie dobrze jest edytować pytanie dla jasności. Szczególnie polecam to zrobić, gdy uzyskane odpowiedzi nie są zgodne z zamierzonym pytaniem.

— DaemonMaker,

Odpowiedzi:

$a|b$ $a$ $b$ $c(\cdot)$ $c(a|b)=min(c(a),c(b))$

Odwołujesz się (w odniesieniu 1):

$\sigma_1$ $\sigma_2$ $\in X_{free}$ $c(\sigma_1|\sigma_2) = c(\sigma_1) + c(\sigma_2)$

Który stał się (w odnośniku 3, Problem 2):

$\sigma_1,\sigma_2\in\Sigma:c(\sigma_1)\leq c(\sigma_1|\sigma_2)$

Co nadal nie dotyczy minimalnej odległości prześwitu.

Aktualizacja: Biorąc pod uwagę łagodne ograniczenie kosztów ścieżki, sugerowane exp (-min_clearance) wydaje się w porządku.

— Josh Vander Hook
źródło

Twoja odpowiedź uświadomiła mi, że metryka, którą opisałem, jest niewłaściwa. Zazwyczaj chcemy MAKSYMALIZOWAĆ minimalny prześwit nad ścieżką, więc w rzeczywistości koszt ścieżki powinien ZWIĘKSZYĆ, ponieważ minimalny prześwit ścieżki ZMNIEJSZA. Pierwszą funkcją kosztu, o której myślę, jest c (sigma) = 1 / min_clearance (sigma), ale pozostawia to funkcję niezdefiniowaną na granicach przeszkód, i uważam, że RRT * wymaga zamknięcia Q_free, aby działały dowody . Poza kwestią granic ta nowa funkcja kosztów byłaby monotoniczna, jak wymaga tego dowód.

— giogadi,

Przypuszczam, że prostą funkcją kosztu, która pozwala uniknąć problemu z granicami, może być c (sigma) = -min_clearance (sigma), ale nie jestem pewien, co posiadanie ujemnych danych mogłoby mieć

— wpływ

\geq

$\geq$

ϵ > 0

$\epsilon > 0$

δ

$\delta$

X_{f r e e}

$X_{free}$

Inna możliwa metryka: c (sigma) = exp (-min_clear (sigma))

— giogadi

Najbardziej podoba mi się funkcja kosztu wykładniczego.

— Josh Vander Hook,

W poprzedniej odpowiedzi ustaliliśmy, że funkcja kosztu zdefiniowana jako

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

spełniałby właściwości wymagane dla RRT * w celu uzyskania asymptotycznej optymalności w ramach tej miary.

Jednak po przejrzeniu artykułu IJRR, który opisuje RRT *, ta funkcja kosztów nie spełnia technicznie założeń zawartych w artykule. W szczególności ta funkcja kosztu narusza właściwość ograniczania , zdefiniowaną jako:

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

$\text{TV}(\sigma)$

$\sigma_0$ $q$ $\sigma_0$ $c(\sigma_0) = \text{exp}(-d(q)) > 0$

Zastanawiam się, czy RRT * po prostu nie da asymptotycznie optymalnych rozwiązań w ramach takiej funkcji kosztów, czy może nadal, ale być może te założenia uprościły dowody optymalności przedstawione w dokumencie.

— Giogadi
źródło