problemy o niskim wymiarze można rozwiązać za pomocą algorytmów opartych na siatce, które nakładają siatkę na przestrzeń konfiguracyjną lub algorytmów geometrycznych, które obliczają kształt i łączność Cfree.
dokładne planowanie ruchu dla Systemów wysokowymiarowych przy złożonych ograniczeniach jest obliczeniowo trudne. Algorytmy pola potencjalnego są wydajne, ale padają ofiarą lokalnych minimów (wyjątkiem są harmoniczne pola potencjału). Algorytmy oparte na próbkowaniu unikają problemu lokalnych minimów i dość szybko rozwiązują wiele problemów.Nie są w stanie określić, że żadna ścieżka nie istnieje, ale mają prawdopodobieństwo niepowodzenia, które zmniejsza się do zera, gdy więcej czasu jest spędzony.
algorytmy oparte na próbkowaniu są obecnie uważane za najnowocześniejsze w planowaniu ruchu w przestrzeniach wysokowymiarowych i zostały zastosowane do problemów, które mają dziesiątki, a nawet setki wymiarów (manipulatory robotów, cząsteczki biologiczne, animowane postacie cyfrowe i roboty z nogami).
istnieje algorytm równoległego planowania ruchu (A1-A2) do manipulacji obiektami (do łapania obiektu latającego).
wyszukiwanie oparte na siatce
metody oparte na siatce nakładają siatkę na przestrzeń konfiguracji i zakładają, że każda konfiguracja jest identyfikowana z punktem siatki. W każdym punkcie siatki robot może przemieszczać się do sąsiednich punktów siatki, o ile linia między nimi jest całkowicie zawarta w Cfree (jest to testowane z wykrywaniem kolizji). To dyskretyzuje zestaw działań, a algorytmy wyszukiwania (takie jak*) są używane do znalezienia ścieżki od początku do celu.
te podejścia wymagają ustawienia rozdzielczości siatki. Wyszukiwanie jest szybsze przy grubszych siatkach, ale algorytm nie znajdzie ścieżek przez wąskie części Cfree. Ponadto liczba punktów na siatce rośnie wykładniczo w wymiarze przestrzeni konfiguracyjnej, co czyni je nieodpowiednimi dla problemów wysokowymiarowych.
tradycyjne metody oparte na siatce wytwarzają ścieżki, których zmiany nagłówka są ograniczone do wielokrotności danego kąta bazowego, często skutkując ścieżkami nieoptymalnymi. Metody planowania ścieżek o dowolnym kącie znajdują krótsze ścieżki, propagując informacje wzdłuż krawędzi siatki (aby szybko szukać) bez ograniczania ich ścieżek do krawędzi siatki (aby znaleźć krótkie ścieżki).
podejścia oparte na siatce często wymagają wielokrotnego wyszukiwania, na przykład, gdy wiedza robota o przestrzeni konfiguracyjnej zmienia się lub sama przestrzeń konfiguracyjna zmienia się podczas podążania ścieżką. Przyrostowe heurystyczne algorytmy wyszukiwania szybko się powtarzają, wykorzystując doświadczenia z poprzednimi podobnymi problemami planowania ścieżki, aby przyspieszyć ich wyszukiwanie w bieżącym.
Interval-based searchEdit
te podejścia są podobne do metod wyszukiwania opartych na siatce, z wyjątkiem tego, że generują nawierzchnię pokrywającą całkowicie przestrzeń konfiguracyjną zamiast siatki. Kostka brukowa rozkładana jest na dwie podpory X -, X+ wykonane z pudeł takich jak X-CF Cfree ⊂ X+. Scharakteryzowanie kwot Cfree w celu rozwiązania problemu inwersji zestawu. Analiza interwałowa może być zatem stosowana, gdy Cfree nie może być opisana przez nierówności liniowe, aby mieć gwarantowaną obudowę.
robot może więc swobodnie poruszać się w X− i nie może wyjść poza X+. Dla obu podprogramów budowany jest wykres sąsiada i ścieżki można znaleźć za pomocą algorytmów takich jak Dijkstra lub a*. Gdy ścieżka jest wykonalna w X -, jest również wykonalna w Cfree. Gdy w X+ nie istnieje żadna ścieżka od jednej początkowej konfiguracji do celu, mamy gwarancję, że w Cfree nie istnieje żadna możliwa ścieżka. Jeśli chodzi o podejście oparte na siatce, podejście interwałowe jest nieodpowiednie dla problemów o dużych wymiarach, ze względu na fakt, że liczba generowanych pól rośnie wykładniczo w odniesieniu do wymiaru przestrzeni konfiguracyjnej.
ilustracją są trzy figury po prawej stronie, gdzie hak o dwóch stopniach swobody musi poruszać się od lewej do prawej, unikając dwóch poziomych małych segmentów.
ruch od początkowej konfiguracji (niebieski) do końcowej konfiguracji haka, omijając dwie przeszkody (czerwone segmenty). Lewy dolny róg haka musi pozostać na poziomej linii, co sprawia, że hak ma dwa stopnie swobody.
rozkład ze skrzynkami pokrywającymi przestrzeń konfiguracyjną: Subpaving X – jest związkiem wszystkich czerwonych pól, a subpaving X+ jest związkiem czerwonych i zielonych pól. Ścieżka odpowiada ruchowi przedstawionemu powyżej.
liczba ta odpowiada tej samej ścieżce, co powyżej, ale uzyskana z dużo mniejszą liczbą pól.Algorytm unika dzielenia pól w częściach przestrzeni konfiguracyjnej, które nie mają wpływu na wynik końcowy.
dekompozycja z wykorzystaniem analizy interwałowej umożliwia również scharakteryzowanie topologii Cfree, np. zliczanie jego liczby połączonych ze sobą elementów.
algorytmy Geometryczneedit
roboty punktowe wśród przeszkód wielokątnych
- Wykres widoczności
- rozkład komórek
tłumaczenie obiektów wśród przeszkód
- suma Minkowskiego
znajdowanie wyjścia z budynku
- najdalszy ślad promieni
biorąc pod uwagę wiązkę promieni wokół aktualnej pozycji przypisaną ich długością uderzającą w ścianę, robot przesuwa się w kierunku najdłuższego promienia, chyba że zidentyfikowane zostaną drzwi. Taki algorytm był używany do modelowania awaryjnego wyjścia z budynków.
pola o sztucznym potencjaleedytuj
jednym z podejść jest traktowanie konfiguracji robota jako punktu w polu potencjalnym, który łączy przyciąganie do celu i odpychanie się od przeszkód. Wynikowa trajektoria jest wyprowadzana jako ścieżka. Takie podejście ma zalety w tym, że trajektoria jest wytwarzana przy niewielkiej ilości obliczeń. Jednak mogą zostać uwięzieni w lokalnych minimach potencjalnego pola i nie znaleźć ścieżki lub znaleźć nieoptymalną ścieżkę. Sztuczne pola potencjału można traktować jako równania kontinuum podobne do elektrostatycznych pól potencjału (traktując robota jak ładunek punktowy), lub ruch przez pole można dyskrecjonować za pomocą zestawu reguł lingwistycznych.Funkcja nawigacyjna lub probabilistyczna funkcja nawigacyjna to rodzaje funkcji o sztucznym potencjale, które mają jakość braku minimalnych punktów z wyjątkiem punktu docelowego.
algorytmy oparte na Próbkachedit
algorytmy oparte na próbkowaniu reprezentują przestrzeń konfiguracyjną z mapą konfiguracji próbkowanych.Podstawowy algorytm sampluje N konfiguracji w C i zachowuje te w Cfree do wykorzystania jako kamienie milowe. Następnie konstruuje się mapę drogową, która łączy dwa kamienie milowe P I Q, jeśli segment linii PQ jest całkowicie w Cfree. Ponownie, wykrywanie kolizji jest używane do testowania włączenia do Cfree. Aby znaleźć ścieżkę łączącą S I G, są one dodawane do mapy drogowej. Jeśli ścieżka w mapie drogowej łączy S I G, planer powiedzie się i zwróci tę ścieżkę. Jeśli nie, powód nie jest definitywny: albo nie ma ścieżki w Cfree, albo planista nie pobrał wystarczającej ilości kamieni milowych.
algorytmy te działają dobrze dla wysokowymiarowych przestrzeni konfiguracyjnych, ponieważ w przeciwieństwie do algorytmów kombinatorycznych, ich czas działania nie jest (jawnie) wykładniczo zależny od wymiaru C. Są one również (ogólnie) znacznie łatwiejsze do wdrożenia. Są one probabilistycznie kompletne, co oznacza, że prawdopodobieństwo, że będą produkować rozwiązanie zbliża się do 1, Jak więcej czasu spędza. Nie są jednak w stanie określić, czy rozwiązanie nie istnieje.
biorąc pod uwagę podstawowe warunki widoczności na Cfree, udowodniono, że wraz ze wzrostem liczby konfiguracji N, prawdopodobieństwo, że powyższy algorytm znajdzie rozwiązanie zbliża się wykładniczo do 1. Widoczność nie jest wyraźnie zależna od wymiaru C; możliwe jest posiadanie przestrzeni wysokowymiarowej o „dobrej” widoczności lub przestrzeni niskowymiarowej o „złej” widoczności. Eksperymentalny sukces metod opartych na próbkach sugeruje, że najczęściej widziane przestrzenie mają dobrą widoczność.
istnieje wiele wariantów tego podstawowego schematu:
- zazwyczaj znacznie szybciej jest testować tylko segmenty między pobliskimi parami kamieni milowych, a nie wszystkie pary.
- nieliniowe rozkłady próbkowania próbują umieścić więcej kamieni milowych w obszarach, które poprawiają łączność mapy drogowej.
- próbki Quasirandom zazwyczaj dają lepsze pokrycie przestrzeni konfiguracyjnej niż pseudorandomowe, chociaż niektóre ostatnie prace dowodzą, że efekt źródła losowości jest minimalny w porównaniu z efektem rozkładu próbkowania.
- wykorzystuje lokalne próbkowanie, wykonując Kierunkowy łańcuch Markowa Monte Carlo random walk z pewną lokalną dystrybucją propozycji.
- możliwe jest znaczne zmniejszenie liczby kamieni milowych potrzebnych do rozwiązania danego problemu, pozwalając na zakrzywione przyrządy celownicze (na przykład czołgając się po przeszkodach, które blokują drogę między dwoma kamieniami milowymi).
- jeśli potrzebne jest tylko jedno lub kilka zapytań planistycznych, nie zawsze konieczne jest skonstruowanie mapy drogowej całej przestrzeni. Drzewa rosnące warianty są zazwyczaj szybsze w tym przypadku (planowanie pojedynczego zapytania). Mapy drogowe są nadal przydatne, jeśli wiele zapytań ma być wykonanych na tej samej przestrzeni (planowanie wielu zapytań)
lista znanych algorytmów
- A*
- D *