Ponieważ określenie odpowiedniej pozycji docelowej może być trudne w wielu sytuacjach, warto rozważyć następujące podejście oparte na mapach siatek zajętości 2D. Jest powszechnie nazywany „iteracją wartości”, aw połączeniu z gradientem opadania / wznoszenia daje prosty i dość wydajny (w zależności od implementacji) algorytm planowania ścieżki. Ze względu na swoją prostotę jest dobrze znany w robotyce mobilnej, w szczególności do „prostych robotów” poruszających się w pomieszczeniach zamkniętych. Jak sugerowano powyżej, takie podejście zapewnia sposób znalezienia ścieżki od pozycji początkowej bez wyraźnego określenia pozycji docelowej w następujący sposób. Pamiętaj, że opcjonalnie można określić pozycję docelową, jeśli jest dostępna. Ponadto podejście / algorytm stanowi pierwsze wyszukiwanie,
W przypadku binarnym dwuwymiarowa mapa obłożenia jest mapą dla zajętych komórek siatki i zerową gdzie indziej. Zauważ, że ta wartość zajętości może być również ciągła w zakresie [0,1], wrócę do tego poniżej. Wartość danego ogniwa siatkowego g i wynosi V (g i ) .
Wersja podstawowa
- Zakładając, że komórka siatki g 0 zawiera pozycję początkową. Ustaw V (g 0 ) = 0 i umieść g 0 w kolejce FIFO.
- Weź kolejną komórkę siatki g i z kolejki.
- Dla wszystkich sąsiadów g j z g i :
- Jeśli g j nie jest zajęty i nie był wcześniej odwiedzany:
- V (g j ) = V (g i ) +1
- Oznacz g j jako odwiedzone.
- Dodaj g j do kolejki FIFO.
- Jeśli dany próg odległości nie został jeszcze osiągnięty, przejdź do (2.), w przeciwnym razie przejdź do (5.).
- Ścieżkę uzyskuje się po najbardziej stromym wzniesieniu, zaczynając od g 0 .
Uwagi na temat kroku 4.
- Jak podano powyżej, krok (4) wymaga śledzenia maksymalnego pokonywanego dystansu, który został pominięty w powyższym opisie ze względu na jasność / zwięzłość.
- Jeśli podano pozycję docelową, iteracja zostaje zatrzymana, gdy tylko pozycja docelowa zostanie osiągnięta, tzn. Przetworzona / odwiedzona w ramach kroku (3.).
- Oczywiście można również po prostu przetworzyć całą mapę siatki, tzn. Kontynuować, aż wszystkie (wolne) komórki siatki zostaną przetworzone / odwiedzone. Czynnikiem ograniczającym jest oczywiście rozmiar mapy siatki w połączeniu z jej rozdzielczością.
Rozszerzenia i dalsze komentarze
Równanie aktualizacji V (g j ) = V (g i ) +1 pozostawia dużo miejsca na zastosowanie wszelkiego rodzaju dodatkowej heurystyki poprzez obniżenie V (g j )lub składnik addytywny w celu zmniejszenia wartości niektórych opcji ścieżki. Większość, jeśli nie wszystkie, takie modyfikacje można ładnie i ogólnie wprowadzić za pomocą mapy siatki o ciągłych wartościach od [0,1], co skutecznie stanowi etap wstępnego przetwarzania początkowej, binarnej mapy siatki. Na przykład dodanie przejścia od 1 do 0 wzdłuż granic przeszkód powoduje, że „aktor” najlepiej pozostaje wolny od przeszkód. Taką mapę siatki można na przykład wygenerować z wersji binarnej poprzez rozmycie, ważoną dylatację lub podobne. Dodając zagrożenia i wrogów jako przeszkody o dużym promieniu rozmycia, karze ścieżki, które do nich zbliżają się. Można również zastosować proces dyfuzji na ogólnej mapie siatki w następujący sposób:
V (g j ) = (1 / (N + 1)) × [V (g j ) + suma (V (g i ))]
gdzie „ suma ” odnosi się do sumy wszystkich sąsiednich komórek siatki. Na przykład zamiast tworzenia mapy binarnej wartości początkowe (całkowite) mogą być proporcjonalne do wielkości zagrożeń, a przeszkody stanowią „małe” zagrożenia. Po zastosowaniu procesu dyfuzji wartości siatki należy / należy przeskalować do [0,1], a komórki zajmowane przez przeszkody, zagrożenia i wrogów należy ustawić / zmusić do 1. W przeciwnym razie skalowanie w równaniu aktualizacji może nie działa zgodnie z życzeniem.
Istnieje wiele odmian tego ogólnego schematu / podejścia. Przeszkody itp. Mogą mieć małe wartości, podczas gdy wolne komórki siatki mają duże wartości, które mogą wymagać opadania gradientu w ostatnim kroku, w zależności od celu. W każdym razie podejście to jest zaskakująco wszechstronne, dość łatwe do wdrożenia i potencjalnie dość szybkie (w zależności od rozmiaru / rozdzielczości mapy sieci). Wreszcie, podobnie jak w przypadku wielu algorytmów planowania ścieżki, które nie przyjmują określonej pozycji docelowej, istnieje oczywiste ryzyko utknięcia w ślepych zaułkach. Do pewnego stopnia może być możliwe zastosowanie dedykowanych kroków przetwarzania końcowego przed ostatnim krokiem w celu zmniejszenia tego ryzyka.
Oto kolejny krótki opis z ilustracją w Java-Script (?), Chociaż ilustracja nie działała w mojej przeglądarce :(
http://www.cs.ubc.ca/~poole/demos/mdp/vi.html
Dużo więcej szczegółów na temat planowania można znaleźć w następującej książce. Iteracja wartości została szczegółowo omówiona w rozdziale 2 sekcja 2.3.1. Optymalne plany o stałej długości.
http://planning.cs.uiuc.edu/
Mam nadzieję, że pomaga, pozdrawiam, Derik.