Jaki jest skuteczny sposób na odwiedzenie każdej dostępnej przestrzeni na siatce z nieznanymi przeszkodami?

Próbuję stworzyć mapę przeszkód w dość zgrubnej przestrzeni siatki 2D, używając eksploracji. Wykrywam przeszkody, próbując przenieść się z jednego pola na sąsiednie pole, a jeśli to się nie powiedzie, w polu docelowym jest przeszkoda (w tym problemie nie ma koncepcji czujnika odległości).

przykładowa siatka http://www.eriding.net/resources/general/prim_frmwrks/images/asses/asses_y3_5d_3.gif (na przykład)

Proces jest zakończony, gdy odwiedzone zostaną wszystkie dostępne kwadraty. Innymi słowy, niektóre przestrzenie mogą być całkowicie nieosiągalne, nawet jeśli nie mają przeszkód, ponieważ są otoczone. Jest to oczekiwane.

W najprostszym przypadku mógłbym użyć algorytmu DFS , ale obawiam się, że jego wykonanie zajmie zbyt dużo czasu - robot poświęci więcej czasu na cofanie się niż eksploracja nowego terytorium. Spodziewam się, że będzie to szczególnie problematyczne przy próbie dotarcia do niedostępnych kwadratów, ponieważ robot wyczerpuje każdą opcję.

W bardziej wyrafinowanej metodzie właściwą czynnością wydaje się być rozkład komórek Boustrophedona .

Nie mogę jednak znaleźć dobrego opisu algorytmu rozkładu komórek Boustrophedona (czyli pełnego opisu w prostych słowach). Istnieją zasoby takie jak ten , lub ten bardziej ogólny, dotyczący pionowego rozkładu komórek, ale nie zapewniają one wglądu w algorytmy wysokiego poziomu ani związane z nimi struktury danych niskiego poziomu.

$O(n^2)$$O(n^4)$$n*n$

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.

1. $v_i$
2. $l_i$$v_i$
3. 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.

1. 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ę).

2. 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).

3. 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

W końcu odkryłem, że najlepszym sposobem na to jest zastosowanie bardzo prostej koncepcji: Flood Fill . Użyłem iteracyjnego podejścia opartego na stosie zamiast opcji rekurencyjnej i zmodyfikowałem go dla przestrzeni fizycznej za pomocą wyszukiwania A *, aby znaleźć ścieżkę od bieżącej lokalizacji do następnej lokalizacji na stosie (używając tylko tych kwadratów siatki, które już miały odwiedzono mnie, ponieważ mam gwarancję, że między nimi jest ścieżka).

Wydajność wydaje się dość rozsądna.