Rozkład komórek Boustrophedon po prostu dzieli środowisko na obszary, które można skutecznie pokryć ścieżką Boustrophedon. Wykona się trapezoidalny rozkład, który można osiągnąć za pomocą algorytmu przemiatania linii. Patrz [Choset 2000], ta strona internetowa
lub (polecam!) Znakomita książka „Geometria obliczeniowa” Mark de Berg i in. al, aby uzyskać pełny opis wymaganych struktur danych i algorytmów.
Choset, Howie. „Zasięg znanych przestrzeni: rozkład komórek Boustrophedona” Autonomous Robots , 2000.
Na przykład, rozważ zestaw przeszkód jako krawędzie i wierzchołki. Powiedzmy, że środowisko jest również ograniczone specjalnym wielokątem. Mamy coś takiego jak poniżej. Aby rozłożyć tę przestrzeń, po prostu dodajemy pionowe krawędzie między każdym wierzchołkiem a najbliższą linią lub wierzchołkiem.
Aby to zrobić w kodzie, potrzebujesz tylko testu przecięcia segmentu linii, posortowanej listy krawędzi i posortowanej listy wierzchołków.
- vi
- livi
- Na każdym skrzyżowaniu utwórz nowy wierzchołek.
Gdy to nastąpi, zestaw nowych krawędzi i wierzchołków obejmuje tylko trapezoidy. Podkreślam jednak, że nie można tego robić online (bez wcześniejszej wiedzy o przeszkodach). Jeśli chcesz uzyskać solidny zasięg bez wcześniejszej wiedzy, możesz spojrzeć na „algorytmy błędów”. W szczególności oto prosty algorytm, przy założeniu, że środowisko jest ograniczone.
Z pozycji początkowej poruszaj się w górę i w lewo, aż dojdziesz do lewego górnego rogu środowiska. Jeśli najpierw napotkasz przeszkodę, musisz ją ominąć. Wiesz, że coś jest przeszkodą, jeśli można go obejść (uderzać i poruszać się).
Od lewego górnego rogu przesuń w prawo, aż natrafisz na granicę. Następnie zejdź w dół i w lewo (robimy bulwar z całej przestrzeni).
Kiedy znajdujesz się na linii lewo-prawo i napotykasz przeszkodę, masz dwie możliwości. (i) Możemy opłynąć, dopóki nie dojdziemy do linii, którą próbujemy objąć po lewej i prawej stronie, a następnie kontynuować. (ii), Możemy zawrócić i pokryć nową linię lewą-prawą, dopóki nie znajdziemy się za przeszkodą lub nie znajdziemy się ponownie w tej sytuacji. Zilustruję.
Po lewej omijamy przeszkodę, aż możemy wrócić do „linii”, którą próbowaliśmy podążać. Po prawej stronie nadal pokrywamy (mniejszy) obszar po jednej stronie przeszkody.
Zaletą pierwszej metody jest to, że zawsze całkowicie wytyczasz przeszkodę przed podjęciem decyzji, jak ją ominąć, dzięki czemu możesz wybrać krótszą ścieżkę. Zaletą drugiej metody jest to, że wcale nie musisz ominąć przeszkody, możesz po prostu przejść do obszaru, w którym się znajdujesz.
Zauważ, że określa to rozkład twojego bulwaru w Internecie : pokrywasz obszar między przeszkodami lub między przeszkodami a granicą.
Jednak, o ile mi wiadomo, pierwsza metoda jest łatwiejsza do analizy. Bardziej skomplikowane algorytmy (takie jak BFS itp.) Są wybierane albo dlatego, że środowisko jest nieograniczone (nie chcesz spędzać wiecznie na poszukiwaniu granicy), albo istnieje naprawdę paskudna przeszkoda w sposobie, w jaki dzieli środowisko. Dlaczego to takie złe? spójrz na ten przykład:
Przesuwanie w lewo iw prawo, a następnie krąży każdą przeszkodę produkuje sposób zbyt wiele covery małych częściach pomiędzy każdą przeszkodę. W rzeczywistości bez globalnego planowania ścieżki można to zrobić tak źle, jak rozdzielczość siatki, umieszczając kolumny o szerokości 1 piksela, wysokości całego środowiska i odstępu 1 piksela. Następnie będziesz musiał omijać przeszkodę za każdym razem, gdy ją uderzysz.
Właśnie dlatego zapytałem, czy masz jakieś pojęcie o tym, gdzie jesteś w środowisku, czy może planujesz globalną ścieżkę. Ale dyskusja online vs offline i optymalne algorytmy nie są tym, czego naprawdę chciałeś.
Aktualizacja: Musiałem usunąć obrazy (nie https) i opublikuję to, co jest często używane w praktycznych aplikacjach w świecie rzeczywistym. http://www.cs.cmu.edu/~motionplanning/papers/sbp_papers/integrated1/yamauchi_frontiers.pdf