Planowanie ruchu
Planowanie ruchu (angielski harmonogram ruchu ) to zestaw matematyki technicznej i komputera do obliczania trajektorii dla kinematyki systemu , z naciskiem na brak kolizji .
Istnieją dwie główne kategorie metod planowania ruchu:
- Pierwsza to tak zwane metody deterministyczne , zwane tak, ponieważ umożliwiają znalezienie tej samej ścieżki przy każdym wykonaniu, przy zachowaniu równoważnych warunków początkowych. Mówi się, że metody deterministyczne są kompletne pod względem rozdzielczości, ponieważ gwarantują znalezienie rozwiązania lub wskazują, że nie ma rozwiązania. Niektóre dobrze znane algorytmy: pola potencjalne, rozkład komórek, diagramy Woronoja ...
- Druga kategoria obejmuje metody probabilistyczne. Metody te nie mają pełnej rozdzielczości, ale gwarantują znalezienie rozwiązania, jeśli takie istnieje. Mówi się, że są one pełne prawdopodobieństwa. Te metody niekoniecznie znajdą tę samą ścieżkę za każdym razem, gdy są wykonywane, nawet przy podobnych warunkach początkowych. Metody probabilistyczne można podzielić na dwie podkategorie: metody próbkowania i metody dyfuzyjne. Pierwsze starają się przybliżyć otoczenie obiektu do przeniesienia, aby zbudować mapę wielokrotnego użytku (w taki sam sposób jak mapę drogową). Sekundy przeprowadzają losowe wyszukiwanie w środowisku, aż do znalezienia żądanej ostatecznej konfiguracji. Niektóre dobrze znane algorytmy: algorytm bułki tartej, probabilistyczna mapa drogowa (PRM) dla metod próbkowania, szybko eksplorujące drzewa losowe (RRT) dla metod dyfuzyjnych.
Oprogramowanie realizacji tych technik jest nazywany planera ruchu (w języku angielskim planowania ścieżki ).
Używa
Planowanie ruchu to bardzo aktywna dziedzina badań, która ma już szereg zastosowań:
- we wzornictwie przemysłowym, rozwiązywanie problemów demontażowych ;
- w robotyce - obliczanie trajektorii umożliwiających robotowi przemieszczanie się z jednego punktu do drugiego;
- w robotyce humanoidalnej obliczanie ruchów chodzenia i obsługi z uwzględnieniem ograniczeń kinematycznych i dynamicznych ;
- w bioinformatyce badanie ruchów cząsteczek;
- w symulowanych środowiskach (w szczególności w grach wideo ), obliczanie prawdopodobnych trajektorii postaci lub pojazdu.
Teoria
Obszar konfiguracji
Większość technik planowania ruchu wykorzystuje to samo narzędzie matematyczne do przedstawienia położenia układu przegubowego ciała sztywnego: przestrzeń konfiguracji . Jest to skończona wymiarowa przestrzeń wektorowa, w której każdy wymiar reprezentuje parametr kinematyczny - lub stopień swobody - układu (kąt obrotu, przemieszczenie translacji itp.). Zatem każdemu wektorowi przestrzeni konfiguracyjnej odpowiada pozycja systemu. Innymi słowy, znając układ przegubowy (położenie przegubów i kształt sztywnych ciał połączonych z przegubami), wektor w przestrzeni konfiguracyjnej jest wystarczający do dokładnego odwzorowania położenia każdego z jego elementów w przestrzeni rzeczywistej (zwanej przestrzenią pracy ).
Na przykład dla ludzkiego ramienia (bez uwzględnienia palców dłoni) przestrzeń konfiguracyjna ma wymiar siedem (trzy stopnie swobody na ramieniu, jeden stopień swobody w łokciu i trzy stopnie swobody w nadgarstku) .
Bryła poruszająca się swobodnie w przestrzeni (nazywana swobodnie latającym ) to szczególny przypadek układu przegubowego z trzema przesunięciami i trzema obrotami (ogólnie przechylenie, pochylenie i odchylenie, ale możliwe są inne reprezentacje). Jego przestrzeń konfiguracyjna ma zatem wymiar szósty.
Tak więc, z wyjątkiem szczególnego przypadku optymalizacji dla konkretnego systemu, algorytmy planowania ruchu mogą być zastosowane zarówno do swobodnego lotu, jak i do złożonego układu przegubowego, dzięki abstrakcji, która stanowi przestrzeń konfiguracyjną.
Bibliografia
- J.-C. Latombe, Planowanie ruchu robotów , 1991.
- SM LaValle, Algorytmy planowania , 2006.
- J. Cortés, L. Jaillet, T. Siméon, Planowanie demontażu molekularnego z algorytmami podobnymi do RRT , IEEE Int. Conf. on Robotics and Automation, 2007.
Powiązane artykuły