Planowanie ruchu - Motion planning

Planowanie ruchu , również planowanie ścieżki (znane również jako problem nawigacji lub problem z poruszaniem się fortepianu ) to problem obliczeniowy mający na celu znalezienie sekwencji prawidłowych konfiguracji, które przesuwają obiekt ze źródła do miejsca docelowego. Termin ten jest używany w geometrii obliczeniowej , animacji komputerowej , robotyce i grach komputerowych .

Rozważ na przykład nawigację robota mobilnego wewnątrz budynku do odległego punktu. Powinien wykonać to zadanie, unikając ścian i nie spadając ze schodów. Algorytm planowania ruchu przyjmie opis tych zadań jako dane wejściowe i wygeneruje polecenia prędkości i skrętu wysyłane do kół robota. Algorytmy planowania ruchu mogą dotyczyć robotów z większą liczbą połączeń (np. manipulatory przemysłowe), bardziej złożonych zadań (np. manipulowanie obiektami), różnych ograniczeń (np. samochód, który może jechać tylko do przodu) i niepewności (np. niedoskonałe modele środowiska lub robota).

Planowanie ruchu ma kilka zastosowań w robotyce, takich jak autonomia , automatyzacja i projektowanie robotów w oprogramowaniu CAD , a także zastosowania w innych dziedzinach, takich jak animowanie postaci cyfrowych , gry wideo , projektowanie architektoniczne , chirurgia robotyczna i badanie cząsteczek biologicznych .

Koncepcje

Przykład obszaru roboczego.
Przestrzeń konfiguracyjna robota punktowego. Biały = C wolny , szary = C obs .
Przestrzeń konfiguracyjna dla prostokątnego robota tłumaczącego (na zdjęciu w kolorze czerwonym). Biały = C wolny , szary = C ob , gdzie ciemnoszary = obiekty, jasnoszary = konfiguracje, w których robot dotyka przedmiotu lub opuszcza obszar roboczy.
Przykład prawidłowej ścieżki.
Przykład nieprawidłowej ścieżki.
Przykład mapy drogowej.

Podstawowym problemem planowania ruchu jest obliczenie ciągłej ścieżki łączącej konfigurację początkową S i konfigurację docelową G, przy jednoczesnym unikaniu kolizji ze znanymi przeszkodami. Geometria robota i przeszkody jest opisana w przestrzeni roboczej 2D lub 3D , podczas gdy ruch jest reprezentowany jako ścieżka w (prawdopodobnie bardziej wymiarowej) przestrzeni konfiguracyjnej .

Przestrzeń konfiguracyjna

Konfiguracja opisuje pozę robota, a przestrzeń konfiguracyjna C to zbiór wszystkich możliwych konfiguracji. Na przykład:

  • Jeśli robot jest pojedynczym punktem (o zerowej wielkości) przesuwającym się na dwuwymiarowej płaszczyźnie (obszarze roboczym), C jest płaszczyzną, a konfigurację można przedstawić za pomocą dwóch parametrów (x, y).
  • Jeśli robot ma kształt 2D, który może się przesuwać i obracać, przestrzeń robocza jest nadal dwuwymiarowa. Jednak C jest specjalną grupą euklidesową SE (2) = R 2 SO (2) (gdzie SO (2) jest specjalną grupą ortogonalną obrotów 2D), a konfigurację można przedstawić za pomocą 3 parametrów (x, y, θ ).
  • Jeśli robot jest bryłą 3D, która może się przesuwać i obracać, przestrzeń robocza jest trójwymiarowa, ale C jest specjalną grupą euklidesową SE(3) = R 3 SO (3), a konfiguracja wymaga 6 parametrów: (x, y, z) dla translacji oraz kąty Eulera (α, β, γ).
  • Jeśli robot jest manipulatorem o stałej podstawie z N przegubów obrotowych (i bez pętli zamkniętych), C jest N-wymiarowy.

Wolna przestrzeń

Zbiór konfiguracji pozwalający na uniknięcie kolizji z przeszkodami nazywany jest wolną przestrzenią C free . Dopełnienie wolnego C w C nazywa się przeszkodą lub obszarem zakazanym.

Często trudno jest jednoznacznie obliczyć kształt C free . Jednak testowanie, czy dana konfiguracja jest w C free, jest wydajne. Po pierwsze, kinematyka do przodu określa położenie geometrii robota, a wykrywanie kolizji sprawdza, czy geometria robota koliduje z geometrią otoczenia.

Miejsce docelowe

Przestrzeń docelowa to podprzestrzeń wolnej przestrzeni, która oznacza, dokąd ma się poruszać robot. W globalnym planowaniu ruchu przestrzeń docelowa jest obserwowana przez czujniki robota. Jednak w lokalnym planowaniu ruchu robot nie może obserwować przestrzeni docelowej w niektórych stanach. Aby rozwiązać ten problem, robot przechodzi przez kilka wirtualnych przestrzeni docelowych, z których każda znajduje się w obserwowalnym obszarze (wokół robota). Wirtualna przestrzeń docelowa nazywana jest podcelem.

Przestrzeń na przeszkodę

Przestrzeń z przeszkodami to przestrzeń, do której robot nie może się poruszać. Przestrzeń z przeszkodami nie jest przeciwieństwem wolnej przestrzeni.

Algorytmy

Problemy niskowymiarowe można rozwiązywać 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ść C free .

Dokładne planowanie ruchu dla systemów wielowymiarowych ze złożonymi ograniczeniami jest niewykonalne obliczeniowo . Algorytmy pól potencjałowych są wydajne, ale padają ofiarą lokalnych minimów (wyjątkiem są harmoniczne pola potencjałów). 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 ścieżka nie istnieje, ale prawdopodobieństwo awarii spada do zera w miarę spędzania większej ilości czasu.

Algorytmy próbkowania oparte są obecnie uważane state-of-the-art planowania ruchu w wysokich-wymiarowej przestrzeni, i były stosowane do problemów, które mają dziesiątki lub nawet setki wymiarów (robotów manipulatory, cząsteczki biologiczne, animowanych postaci cyfrowej, a po turecku roboty ).

Istnieje algorytm równoległego planowania ruchu (A1-A2) do manipulacji obiektami (do łapania obiektu latającego).

Wyszukiwanie w oparciu o siatkę

Podejścia oparte na siatce nakładają siatkę na przestrzeń konfiguracyjną i zakładają, że każda konfiguracja jest identyfikowana za pomocą punktu siatki. W każdym punkcie siatki, robot może poruszać się z sąsiednimi punktami siatki, tak długo jak linia między nimi jest całkowicie zawarty w C wolnej (to jest testowana z wykrywaniem kolizji). Dyskretyzuje to zestaw działań, a algorytmy wyszukiwania (takie jak A* ) służą do znalezienia ścieżki od początku do celu.

Te podejścia wymagają ustawienia rozdzielczości siatki. Wyszukiwanie jest szybsze w przypadku grubszych siatek, ale algorytm nie znajdzie ścieżek przez wąskie fragmenty C free . Co więcej, liczba punktów na siatce rośnie wykładniczo w wymiarze przestrzeni konfiguracji, co czyni je nieodpowiednimi dla problemów wysokowymiarowych.

Tradycyjne podejścia oparte na siatce tworzą ścieżki, których zmiany kierunku są ograniczone do wielokrotności danego kąta bazowego, co często skutkuje nieoptymalnymi ścieżkami. Podejścia planowania ścieżek pod dowolnym kątem znajdują krótsze ścieżki poprzez propagację informacji wzdłuż krawędzi siatki (w celu szybkiego wyszukiwania) bez ograniczania ich ścieżek do krawędzi siatki (w celu znalezienia krótkich ścieżek).

Podejścia oparte na siatce często wymagają wielokrotnego wyszukiwania, na przykład, gdy zmienia się wiedza robota o przestrzeni konfiguracji lub sama przestrzeń konfiguracji zmienia się podczas podążania ścieżką. Przyrostowe algorytmy wyszukiwania heurystycznego szybko przebudowują plany, wykorzystując doświadczenie z poprzednimi podobnymi problemami z planowaniem ścieżki, aby przyspieszyć wyszukiwanie bieżącego.

Wyszukiwanie na podstawie interwałów

Te podejścia są podobne do metod wyszukiwania opartych na siatce, z tą różnicą, że generują nawierzchnię pokrywającą całkowicie przestrzeń konfiguracyjną zamiast siatki. Nawierzchnię rozkłada się na dwie nawierzchnie X ,X + wykonane z pudełek takich, że X ⊂ C wolne ⊂ X + . Charakteryzowanie wolnych ilości C w celu rozwiązania problemu inwersji zbioru . Analiza interwałowa może zatem być stosowana, gdy C wolny nie może być opisany przez nierówności liniowe w celu uzyskania gwarantowanej obudowy.

Robot może więc swobodnie poruszać się w X i nie może wyjść poza X + . Do obu nawierzchni budowany jest graf sąsiada, a ścieżki można wyszukiwać za pomocą algorytmów takich jak Dijkstra lub A* . Kiedy ścieżka jest wykonalna w X , jest również wykonalna w C free . Gdy w X + nie istnieje żadna ścieżka od jednej konfiguracji początkowej do celu, mamy gwarancję, że w C free nie istnieje realna ścieżka . Jeśli chodzi o podejście oparte na siatce, podejście interwałowe jest nieodpowiednie dla problemów wysokowymiarowych, ze względu na fakt, że liczba generowanych pudełek rośnie wykładniczo w stosunku do wymiaru przestrzeni konfiguracyjnej.

Ilustracją są trzy cyfry po prawej stronie, na których hak o dwóch stopniach swobody musi przesunąć się od lewej do prawej, unikając dwóch poziomych małych segmentów.

Przejdź od początkowej konfiguracji (niebieski) do końcowej konfiguracji haka, omijając dwie przeszkody (czerwone segmenty). Lewy dolny róg haka musi pozostawać na linii poziomej, co daje haczykowi dwa stopnie swobody.
Rozkład z pudłami obejmującymi przestrzeń konfiguracyjną: Podtorza X to suma wszystkich czerwonych pudełek, a Podtorza X + to suma pudełek czerwonych i zielonych. Ścieżka odpowiada ruchowi przedstawionemu powyżej.
Ta liczba odpowiada tej samej ścieżce, co powyżej, ale uzyskana przy znacznie mniejszej liczbie pudełek. Algorytm pozwala uniknąć przecinania pól w częściach przestrzeni konfiguracyjnej, które nie wpływają na wynik końcowy.

Dekompozycja z podwarstwami przy użyciu analizy interwałowej umożliwia również scharakteryzowanie topologii C free, na przykład zliczanie jej połączonych elementów.

Algorytmy geometryczne

Wskaż roboty wśród wielokątnych przeszkód

Tłumaczenie przedmiotów wśród przeszkód

Znajdowanie wyjścia z budynku

  • najdalszy ślad promieni

Biorąc pod uwagę wiązkę promieni wokół aktualnej pozycji przypisanej długością uderzenia w ścianę, robot porusza się w kierunku najdłuższego promienia, chyba że zostaną zidentyfikowane drzwi. Taki algorytm został wykorzystany do modelowania awaryjnego wyjścia z budynków.

Sztuczne potencjalne pola

Jednym z podejść jest traktowanie konfiguracji robota jako punktu w potencjalnym polu, który łączy w sobie przyciąganie do celu i odpychanie od przeszkód. Wynikowa trajektoria jest wyprowadzana jako ścieżka. Takie podejście ma zalety polegające na tym, że trajektoria jest tworzona przy niewielkiej ilości obliczeń. Mogą jednak zostać uwięzione w lokalnych minimach potencjalnego pola i nie znaleźć ścieżki lub mogą znaleźć ścieżkę nieoptymalną. Sztuczne pola potencjału można traktować jako równania kontinuum podobne do pól potencjału elektrostatycznego (traktując robota jak ładunek punktowy), a ruch w polu można zdyskretyzować za pomocą zestawu reguł językowych. Funkcja nawigacji lub probabilistyczna funkcja nawigacji to rodzaje sztucznych potencjalnych funkcji, których jakość polega na tym, że nie mają punktów minimalnych poza punktem docelowym.

Algorytmy oparte na próbkowaniu

Algorytmy oparte na próbkowaniu reprezentują przestrzeń konfiguracyjną z mapą drogową próbkowanych konfiguracji. Próbki algorytm Basic N konfiguracjach C i utrzymuje w tych C wolny do wykorzystania jako etapów . Mapa drogowa jest wówczas zbudowane, że łączy dwa etapy P i Q PQ jeśli odcinek jest całkowicie C wolne . Ponownie, wykrywanie kolizji jest używane do testowania włączenia w C free . Aby znaleźć ścieżkę, która łączy S i G, są one dodawane do mapy drogowej. Jeśli ścieżka na mapie drogowej łączy S i G, planista odniesie sukces i zwróci tę ścieżkę. Jeśli nie, przyczyna nie jest ostateczna: albo nie ma ścieżki w C free , albo planista nie spróbował wystarczającej liczby kamieni milowych.

Algorytmy te sprawdzają się dobrze w przypadku wielowymiarowych 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 zaimplementowania. Są one probabilistycznie kompletne, co oznacza, że ​​prawdopodobieństwo, że wytworzą rozwiązanie, zbliża się do 1, im więcej czasu spędzają. Nie potrafią jednak ustalić, czy nie ma rozwiązania.

Biorąc pod uwagę podstawowe warunki widzialności na C free , udowodniono, że wraz ze wzrostem liczby konfiguracji N prawdopodobieństwo znalezienia rozwiązania przez powyższy algorytm zbliża się wykładniczo do 1. Widoczność nie jest wyraźnie zależna od wymiaru C; możliwe jest posiadanie przestrzeni wysokowymiarowej z „dobrą” widocznością lub przestrzeni niskowymiarowej ze „słabą” 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 dużo szybciej jest testować tylko segmenty między pobliskimi parami kamieni milowych niż wszystkie pary.
  • Nierównomierne rozkłady próbkowania próbują umieścić więcej kamieni milowych w obszarach, które poprawiają łączność mapy drogowej.
  • Próbki quasi-losowe zazwyczaj dają lepsze pokrycie przestrzeni konfiguracyjnej niż próby pseudolosowe , chociaż niektóre ostatnie prace dowodzą, że wpływ źródła losowości jest minimalny w porównaniu z efektem rozkładu próbkowania.
  • Wykorzystuje lokalne próbkowanie, wykonując losowy spacer losowy Monte Carlo w łańcuchu Markowa z lokalną dystrybucją propozycji.
  • Możliwe jest znaczne zmniejszenie liczby kamieni milowych potrzebnych do rozwiązania danego problemu poprzez umożliwienie celowania z zakrzywionym okiem (na przykład czołganie się po przeszkodach blokujących 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. W tym przypadku warianty wzrostu drzewa są zazwyczaj szybsze (planowanie pojedynczego zapytania). Mapy drogowe są nadal przydatne, jeśli wiele zapytań ma być wykonanych na tej samej przestrzeni (planowanie wielu zapytań)

Lista ważnych algorytmów

Kompletność i wydajność

Mówi się, że planista ruchu jest kompletny, jeśli planista w skończonym czasie albo opracuje rozwiązanie, albo poprawnie zgłosi, że go nie ma. Większość kompletnych algorytmów opiera się na geometrii. Wydajność kompletnego planera ocenia się na podstawie jego złożoności obliczeniowej . Udowadniając tę ​​właściwość matematycznie, należy upewnić się, że dzieje się to w skończonym czasie, a nie tylko w granicy asymptotycznej. Jest to szczególnie problematyczne, jeśli podczas określonej techniki dowodzenia wystąpią ciągi nieskończone (które zbiegają się tylko w przypadku granicznym), gdyż wtedy teoretycznie algorytm nigdy się nie zatrzyma. Intuicyjne „sztuczki” (często oparte na indukcji) są zazwyczaj błędnie uważane za zbieżne, co robią tylko dla nieskończonej granicy. Innymi słowy, rozwiązanie istnieje, ale planista nigdy go nie zgłosi. Ta właściwość jest zatem związana z Kompletnością Turinga i służy w większości przypadków jako teoretyczna podstawa / wskazówka. Planery oparte na podejściu brute force są zawsze kompletne, ale można je zrealizować tylko w przypadku skończonych i dyskretnych konfiguracji.

W praktyce zakończenie algorytmu zawsze można zagwarantować za pomocą licznika, który dopuszcza tylko maksymalną liczbę iteracji, a następnie zawsze zatrzymuje się z rozwiązaniem lub bez rozwiązania. W przypadku systemów czasu rzeczywistego zazwyczaj osiąga się to za pomocą timera watchdog , który po prostu zabije proces. Watchdog musi być niezależny od wszystkich procesów (zazwyczaj realizowany przez procedury przerwań niskiego poziomu). Asymptotyczny przypadek opisany w poprzednim akapicie nie zostanie jednak osiągnięty w ten sposób. Zgłosi najlepszy znaleziony do tej pory (co jest lepsze niż nic) lub żaden, ale nie może poprawnie zgłosić, że go nie ma. Wszystkie realizacje z uwzględnieniem watchdoga są zawsze niekompletne (poza wszystkimi przypadkami, które można ocenić w skończonym czasie).

Kompletność może być zapewniona tylko przez bardzo rygorystyczny dowód poprawności matematycznej (często wspomagany narzędziami i metodami opartymi na wykresach) i powinien być wykonywany tylko przez wyspecjalizowanych ekspertów, jeśli aplikacja zawiera treści dotyczące bezpieczeństwa. Z drugiej strony, obalenie kompletności jest łatwe, ponieważ wystarczy znaleźć jedną nieskończoną pętlę lub zwrócony jeden błędny wynik. Weryfikacja formalna/poprawność algorytmów jest samodzielnym polem badawczym. Prawidłowa konfiguracja tych przypadków testowych jest bardzo skomplikowanym zadaniem.

Kompletność rozdzielczości jest właściwością, którą planista gwarantuje znalezienie ścieżki, jeśli rozdzielczość podstawowej siatki jest wystarczająco dobra. Większość planistów z pełną rozdzielczością jest oparta na siatce lub interwałach. Złożoność obliczeniowa planistów z pełną rozdzielczością zależy od liczby punktów w podstawowej siatce, która wynosi O(1/h d ), gdzie h to rozdzielczość (długość jednego boku komórki siatki), a d to konfiguracja wymiar przestrzeni.

Probabilistyczna kompletność to właściwość polegająca na tym, że im więcej „pracy” jest wykonywanych, prawdopodobieństwo, że planista nie znajdzie ścieżki, jeśli taka istnieje, asymptotycznie zbliża się do zera. Kilka metod opartych na próbkach jest prawdopodobnie ukończonych. Wydajność prawdopodobnie kompletnego planisty jest mierzona przez stopień zbieżności. W zastosowaniach praktycznych zwykle używa się tej właściwości, ponieważ pozwala ona na ustawienie limitu czasu dla watchdoga na podstawie średniego czasu zbieżności.

Niekompletni planiści nie zawsze tworzą wykonalną ścieżkę, jeśli taka istnieje (patrz pierwszy paragraf). Czasami niekompletni planiści dobrze sprawdzają się w praktyce, ponieważ zawsze zatrzymują się po pewnym czasie i pozwalają innym procedurom przejąć kontrolę.

Warianty problemu

Opracowano wiele algorytmów do obsługi wariantów tego podstawowego problemu.

Ograniczenia różniczkowe

Holonomiczny

  • Ramiona manipulatora (z dynamiką)

Nieholonomiczny

  • Drony
  • Samochody
  • Monocykle
  • Samoloty
  • Systemy ograniczone akceleracją
  • Przenoszenie przeszkód (czas nie może cofnąć się)
  • Sterowana igła ze skosem
  • Roboty z napędem różnicowym

Ograniczenia optymalności

Systemy hybrydowe

Systemy hybrydowe to takie, które łączą zachowanie dyskretne i ciągłe. Przykładami takich systemów są:

Niepewność

  • Niepewność ruchu
  • Brakująca informacja
  • Aktywne wykrywanie
  • Planowanie bezczujnikowe

Aplikacje

Zobacz też

Bibliografia

Dalsza lektura

Linki zewnętrzne