https://aie24.pl/
Alternatywnym podejściem do planowania ruchu jest dyskretyzacja przestrzeni C. Metody dekompozycji komórek rozkładają wolną przestrzeń na skończoną liczbę sąsiadujących regionów, zwanych komórkami. Komórki te są zaprojektowane tak, aby problem planowania ścieżki w obrębie pojedynczej komórki można było rozwiązać prostymi środkami (np. poruszając się po linii prostej). Problem planowania ścieżki staje się wtedy problemem wyszukiwania dyskretnych grafów (jak w przypadku grafów widoczności i grafów Woronoja), aby znaleźć ścieżkę przez sekwencję komórek. Najprostszy rozkład komórek składa się z regularnie rozmieszczonej siatki. Rysunek 26.16(a) przedstawia rozkład przestrzeni w siatce kwadratowej oraz ścieżkę rozwiązania, która jest optymalna dla tego rozmiaru siatki. Cieniowanie w skali szarości wskazuje wartość każdej wolnej komórki siatki — koszt najkrótszej ścieżki z tej komórki do celu. Oczywiście moglibyśmy również użyć algorytmu A, aby znaleźć najkrótszą ścieżkę. Ten rozkład siatki ma tę zaletę, że jest prosty do wdrożenia, ale ma trzy ograniczenia. Po pierwsze, działa tylko dla przestrzeni konfiguracyjnych o niskim wymiarze, ponieważ liczba komórek siatki wzrasta wykładniczo wraz z liczbą wymiarów d. (Brzmi znajomo? To przekleństwo wymiarowości.) Po drugie, ścieżki przez dyskretną przestrzeń stanów nie zawsze będą gładkie. Na rysunku 26.16(a) widzimy, że ukośne części ścieżki są postrzępione, przez co robotowi bardzo trudno jest je dokładnie śledzić. Robot może próbować wygładzić ścieżkę rozwiązania, ale nie jest to proste. Po trzecie, pojawia się problem, co zrobić z komórkami, które są „mieszane” – to znaczy ani w całości w wolnej przestrzeni, ani w całości w zajętej przestrzeni. Ścieżka rozwiązania obejmująca taką komórkę może nie być rzeczywistym rozwiązaniem, ponieważ może nie być możliwości bezpiecznego przejścia przez komórkę. To sprawiłoby, że planowanie ścieżki byłoby nierozsądne. Z drugiej strony, jeśli upieramy się, że można używać tylko całkowicie wolnych komórek, planer będzie niekompletny, ponieważ może się zdarzyć, że jedyne ścieżki do celu przechodzą przez mieszane komórki — może być tak, że korytarz jest w rzeczywistości szeroki wystarczy, aby robot mógł przejść, ale korytarz jest pokryty tylko mieszanymi komórkami. Pierwszym podejściem do tego problemu jest dalszy podział komórek mieszanych — być może przy użyciu komórek o połowie oryginalnego rozmiaru. Może to być kontynuowane rekurencyjnie, aż zostanie znaleziona ścieżka, która leży całkowicie w wolnych komórkach. Ta metoda działa dobrze i jest kompletna, jeśli istnieje sposób na stwierdzenie, czy dana komórka jest komórką mieszaną, co jest łatwe tylko wtedy, gdy granice przestrzeni konfiguracyjnej mają stosunkowo proste opisy matematyczne. Należy zauważyć, że rozkład komórek niekoniecznie wymaga wyraźnego przedstawienia kolby przestrzeni z przeszkodami. Możemy zdecydować, czy dołączyć komórkę, czy nie, korzystając z narzędzia do sprawdzania kolizji. Jest to kluczowe pojęcie w planowaniu ruchu. Kontroler kolizji to funkcja (q), która odwzorowuje 1, jeśli konfiguracja koliduje z przeszkodą, a 0 w przeciwnym razie. Dużo łatwiej jest sprawdzić, czy konkretna konfiguracja jest w kolizji, niż jawnie skonstruować całą przestrzeń przeszkód Cobs. Badając ścieżkę rozwiązania pokazaną na rysunku 26.16(a), widzimy dodatkową trudność, którą trzeba będzie rozwiązać. Ścieżka zawiera dowolnie ostre zakręty, ale fizyczny robot ma pęd i nie może natychmiast zmienić kierunku. Problem ten można rozwiązać, przechowując dla każdej komórki siatki dokładny stan ciągły (położenie i prędkość), który został osiągnięty, gdy komórka została osiągnięta podczas wyszukiwania. Załóżmy dalej, że propagując informacje do pobliskich komórek siatki, używamy tego ciągłego stanu jako podstawy i stosujemy model ciągłego ruchu robota do przeskakiwania do pobliskich komórek. Więc nie robimy natychmiastowego 90 tury; wykonujemy zaokrąglony zwrot rządzony prawami ruchu. Możemy teraz zagwarantować, że uzyskana trajektoria jest gładka i rzeczywiście może zostać wykonana przez robota. Jednym z algorytmów, który to realizuje, jest hybryda A*