Znalezienie drogi - Pathfinding

Dla innych zastosowań, zobacz Pathfinder (ujednoznacznienie) .
Algorytmy wyszukiwania grafów i drzew
Aukcje
powiązane tematy
Równoważne ścieżki między A i B w środowisku 2D

Pathfinding lub pathing jest kreślenie, za pomocą aplikacji komputerowej, najkrótszej trasy między dwoma punktami. Jest to bardziej praktyczny wariant rozwiązywania labiryntów . Ta dziedzina badań opiera się w dużej mierze na algorytmie Dijkstry do znajdowania najkrótszej ścieżki na grafie ważonym .

Odnajdywanie ścieżek jest ściśle związane z problemem najkrótszej ścieżki w ramach teorii grafów , która bada, jak zidentyfikować ścieżkę, która najlepiej spełnia określone kryteria (najkrótsza, najtańsza, najszybsza itp.) między dwoma punktami w dużej sieci.

Algorytmy

W swej istocie metoda odnajdywania ścieżki przeszukuje graf , zaczynając od jednego wierzchołka i badając sąsiednie węzły, aż do osiągnięcia węzła docelowego, zwykle z zamiarem znalezienia najtańszej trasy. Chociaż metody przeszukiwania grafów, takie jak przeszukiwanie wszerz , znalazłyby trasę, gdyby miały wystarczająco dużo czasu, inne metody, które „badają” graf, miałyby tendencję do szybszego dotarcia do celu. Analogią byłaby osoba przechodząca przez pokój; zamiast sprawdzać z wyprzedzeniem każdą możliwą trasę, osoba zazwyczaj szłaby w kierunku celu i zbaczała z niej tylko po to, aby uniknąć przeszkód i czynić odchylenia tak małe, jak to tylko możliwe.

Dwa podstawowe problemy związane ze znajdowaniem ścieżki to (1) znalezienie ścieżki pomiędzy dwoma węzłami w grafie ; oraz (2) problem najkrótszej ścieżki — znalezienie optymalnej najkrótszej ścieżki . Podstawowe algorytmy takie jak szerokość pierwszego i głębokości pierwszego adresu wyszukiwarki Pierwszy problem przez wyczerpaniu wszystkich możliwości; zaczynając od danego węzła, iterują po wszystkich potencjalnych ścieżkach, aż dotrą do węzła docelowego. Algorytmy te działają w czasie liniowym, gdzie V to liczba wierzchołków, a E to liczba krawędzi między wierzchołkami.

Bardziej skomplikowanym problemem jest znalezienie optymalnej ścieżki. Wyczerpujące podejście w tym przypadku jest znane jako algorytm Bellmana-Forda , który daje złożoność czasową lub czas kwadratowy. Jednak nie jest konieczne badanie wszystkich możliwych ścieżek, aby znaleźć optymalną. Algorytmy, takie jak A* i algorytm Dijkstry, strategicznie eliminują ścieżki poprzez heurystykę lub programowanie dynamiczne . Eliminując niemożliwe ścieżki, algorytmy te mogą osiągnąć złożoność czasową tak niską, jak .

Powyższe algorytmy należą do najlepszych algorytmów ogólnych, które operują na grafie bez przetwarzania wstępnego. Jednak w praktycznych systemach wyznaczania tras, jeszcze lepszą złożoność czasową można osiągnąć dzięki algorytmom, które mogą wstępnie przetwarzać wykres w celu uzyskania lepszej wydajności. Jednym z takich algorytmów są hierarchie skurczowe .

Algorytm Dijkstry

Typowym przykładem algorytmu wyszukiwania ścieżki opartego na grafach jest algorytm Dijkstry . Ten algorytm rozpoczyna się od węzła początkowego i „otwartego zestawu” węzłów kandydujących. Na każdym kroku badany jest węzeł w zbiorze otwartym o najmniejszej odległości od początku. Węzeł jest oznaczony jako „zamknięty”, a wszystkie sąsiadujące z nim węzły są dodawane do zbioru otwartego, jeśli nie zostały jeszcze zbadane. Ten proces powtarza się, dopóki nie zostanie znaleziona ścieżka do miejsca docelowego. Ponieważ węzły o najmniejszej odległości są sprawdzane jako pierwsze, przy pierwszym znalezieniu miejsca docelowego ścieżka do niego będzie najkrótszą ścieżką.

Algorytm Dijkstry zawodzi, jeśli występuje ujemna waga krawędzi . W hipotetycznej sytuacji, w której węzły A, B i C tworzą spójny graf nieskierowany o krawędziach AB = 3, AC = 4 i BC = −2, optymalna ścieżka z A do C kosztuje 1, a optymalna ścieżka z A do B kosztuje 2. Algorytm Dijkstry zaczynający się od A najpierw zbada B, ponieważ jest najbliższy. Przypisze mu koszt 3 i oznaczy go jako zamknięty, co oznacza, że ​​jego koszt nigdy nie zostanie ponownie oszacowany. Dlatego Dijkstra nie może ocenić ujemnych wag krawędzi. Ponieważ jednak z wielu praktycznych celów nigdy nie będzie ujemnej wagi krawędziowej, algorytm Dijkstry jest w dużej mierze odpowiedni do wyszukiwania ścieżek.

Algorytm A*

A* to wariant algorytmu Dijkstry powszechnie używanego w grach. A* przypisuje każdemu otwartemu węzłowi wagę równą wadze krawędzi tego węzła plus przybliżona odległość między tym węzłem a końcem. Ta przybliżona odległość jest znajdowana przez heurystykę i reprezentuje minimalną możliwą odległość między tym węzłem a końcem. Pozwala to wyeliminować dłuższe ścieżki po znalezieniu ścieżki początkowej. Jeśli istnieje ścieżka o długości x między początkiem a końcem, a minimalna odległość między węzłem a końcem jest większa niż x, ten węzeł nie musi być badany.

A* używa tej heurystyki, aby poprawić zachowanie względem algorytmu Dijkstry. Kiedy heurystyka daje zero, A* jest równoważne algorytmowi Dijkstry. Gdy oszacowanie heurystyczne rośnie i zbliża się do prawdziwej odległości, A* nadal znajduje optymalne ścieżki, ale działa szybciej (dzięki badaniu mniejszej liczby węzłów). Gdy wartość heurystyki jest dokładnie prawdziwą odległością, A* sprawdza najmniejszą liczbę węzłów. (Jednak generalnie niepraktyczne jest napisanie funkcji heurystycznej, która zawsze oblicza prawdziwą odległość, ponieważ ten sam wynik porównania można często uzyskać za pomocą prostszych obliczeń – na przykład używając odległości Manhattanu nad odległością euklidesową w przestrzeni dwuwymiarowej ). wartość wzrostu heurystyki, A* sprawdza mniej węzłów, ale nie gwarantuje już optymalnej ścieżki. W wielu aplikacjach (takich jak gry wideo) jest to akceptowalne, a nawet pożądane, aby algorytm działał szybko.

Przykładowy algorytm

Jest to dość prosty i łatwy do zrozumienia algorytm wyszukiwania ścieżek dla map opartych na kafelkach. Aby rozpocząć, masz mapę, współrzędne początkowe i współrzędne docelowe. Mapa będzie wyglądać tak, Xbędąc ścianami, Sbędącą początkiem, Obędącą końcem i _otwartymi przestrzeniami, liczby wzdłuż górnej i prawej krawędzi to numery kolumn i wierszy: 

  1 2 3 4 5 6 7 8
X X X X X X X X X X
X _ _ _ X X _ X _ X 1
X _ X _ _ X _ _ _ X 2
X S X X _ _ _ X _ X 3
X _ X _ _ X _ _ _ X 4
X _ _ _ X X _ X _ X 5
X _ X _ _ X _ X _ X 6
X _ X X _ _ _ X _ X 7
X _ _ O _ X _ _ _ X 8
X X X X X X X X X X

Najpierw utwórz listę współrzędnych, której użyjemy jako kolejki. Kolejka zostanie zainicjowana z jedną współrzędną, współrzędną końcową. Każda współrzędna będzie również miała dołączoną zmienną licznika (cel tego wkrótce stanie się oczywisty). Tak więc kolejka zaczyna się jako ((3,8,0)).

Następnie przejrzyj każdy element w kolejce, w tym nowe elementy dodawane na końcu w trakcie działania algorytmu i dla każdego elementu wykonaj następujące czynności:

  1. Utwórz listę czterech sąsiednich komórek ze zmienną licznika zmiennej licznika bieżącego elementu + 1 (w naszym przykładzie cztery komórki to ((2,8,1),(3,7,1),(4, 8,1),(3,9,1)))
  2. Sprawdź wszystkie komórki na każdej liście pod kątem następujących dwóch warunków:
    1. Jeśli komórka jest ścianą, usuń ją z listy
    2. Jeśli na liście głównej znajduje się element o tych samych współrzędnych, usuń go z listy komórek
  3. Dodaj wszystkie pozostałe komórki z listy na koniec głównej listy
  4. Przejdź do następnej pozycji na liście

Zatem po pierwszej turze lista elementów wygląda następująco: ((3,8,0),(2,8,1),(4,8,1))

  • Po 2 turach: ((3,8,0),(2,8,1),(4,8,1),(1,8,2),(4,7,2))
  • Po 3 turach: (...(1,7,3),(4,6,3),(5,7,3))
  • Po 4 turach: (...(1,6,4),(3,6,4),(6,7,4))
  • Po 5 turach: (...(1,5,5),(3,5,5),(6,6,5),(6,8,5))
  • Po 6 turach: (...(1,4,6),(2,5,6),(3,4,6),(6,5,6),(7,8,6))
  • Po 7 turach: (...(1,3,7)) – problem rozwiązany, zakończ ten etap algorytmu – zauważ, że jeśli masz kilka jednostek goniących ten sam cel (jak w wielu grach – koniec do początku algorytm ma to ułatwić), możesz kontynuować, aż cała mapa zostanie zajęta, wszystkie jednostki zostaną osiągnięte lub osiągnięty limit licznika

Teraz zmapuj liczniki na mapę, uzyskując to: 

  1 2 3 4 5 6 7 8
X X X X X X X X X X
X _ _ _ X X _ X _ X 1
X _ X _ _ X _ _ _ X 2
X S X X _ _ _ X _ X 3
X 6 X 6 _ X _ _ _ X 4
X 5 6 5 X X 6 X _ X 5
X 4 X 4 3 X 5 X _ X 6
X 3 X X 2 3 4 X _ X 7
X 2 1 0 1 X 5 6 _ X 8
X X X X X X X X X X

Teraz zacznij od S (7) i przejdź do sąsiedniej komórki o najniższym numerze (niezaznaczone komórki nie mogą być przeniesione). Śledzona ścieżka to (1,3,7) -> (1,4,6) -> (1,5,5) -> (1,6,4) -> (1,7,3) -> ( 1,8,2) -> (2,8,1) -> (3,8.0). W przypadku, gdy dwie liczby są równie niskie (na przykład, jeśli S było na (2,5)), wybierz losowy kierunek – długości są takie same. Algorytm jest teraz gotowy.

W grach wideo

Chris Crawford w 1982 roku opisał, jak „spędził dużo czasu”, próbując rozwiązać problem z odnajdywaniem ścieżki w Tanktics , w którym czołgi komputerowe zostały uwięzione na lądzie w jeziorach w kształcie litery U. „Po wielu zmarnowanych wysiłkach odkryłem lepsze rozwiązanie: usuń z mapy jeziora w kształcie litery U”, powiedział.

Hierarchiczne znajdowanie ścieżki

Drzewa czwórkowe mogą być używane do hierarchicznego znajdowania ścieżek path

Pomysł został po raz pierwszy opisany przez branżę gier wideo , która potrzebowała planowania na dużych mapach z małą ilością czasu procesora . Koncepcja wykorzystania abstrakcji i heurystyki jest starsza i po raz pierwszy została wymieniona pod nazwą ABSTRIPS (Abstraction-Based STRIPS ), która była używana do efektywnego przeszukiwania przestrzeni stanów gier logicznych. Podobną techniką są siatki nawigacyjne (navmesh), które służą do planowania geometrycznego w grach oraz planowania transportu multimodalnego, które wykorzystuje się w problemach komiwojażera z więcej niż jednym pojazdem transportowym.

Mapa jest podzielona na klastry . W warstwie wysokiego poziomu planowana jest ścieżka pomiędzy klastrami. Po znalezieniu planu planowana jest druga ścieżka w ramach klastra na niższym poziomie. Oznacza to, że planowanie odbywa się w dwóch krokach, co jest lokalnym przewodnikiem wyszukiwania w oryginalnej przestrzeni. Zaletą jest to, że liczba węzłów jest mniejsza, a algorytm działa bardzo dobrze. Wadą jest to, że hierarchiczny pathplanner jest trudny do wdrożenia.

Przykład

Mapa ma rozmiar 3000x2000 pikseli . Planowanie ścieżki na podstawie piksela zajęłoby bardzo dużo czasu. Nawet wydajny algorytm będzie musiał obliczyć wiele możliwych grafów. Powodem jest to, że taka mapa zawierałaby łącznie 6 milionów pikseli, a możliwości eksploracji przestrzeni geometrycznej są niezmiernie duże. Pierwszym krokiem hierarchicznego planowania ścieżki jest podzielenie mapy na mniejsze pod-mapy. Każdy klaster ma rozmiar 300x200 pikseli. Ogólna liczba klastrów to 10x10=100. W nowo utworzonym grafie ilość węzłów jest niewielka, możliwe jest poruszanie się pomiędzy 100 klastrami, ale nie w obrębie mapy szczegółowej. Jeśli na wykresie wysokiego poziomu znaleziono prawidłową ścieżkę, następnym krokiem jest zaplanowanie ścieżki w każdym klastrze. Podmapa ma rozdzielczość 300x200 pikseli, którą z łatwością poradzi sobie normalny pathplanner A* .

Algorytmy używane w odnajdywaniu ścieżek

  • Algorytm Dijkstry
  • Algorytm przeszukiwania A* , szczególny przypadek algorytmu Dijkstry
  • D* rodzina przyrostowych algorytmów heurystycznych wyszukiwania problemów, w których ograniczenia zmieniają się w czasie lub nie są całkowicie znane, gdy agent po raz pierwszy planuje swoją ścieżkę
  • Algorytmy planowania ścieżek pod dowolnym kątem , rodzina algorytmów do planowania ścieżek, które nie są ograniczone do poruszania się wzdłuż krawędzi na wykresie wyszukiwania, zaprojektowane tak, aby móc przyjąć dowolny kąt, a tym samym znaleźć krótsze i prostsze ścieżki

Wieloagentowe odnajdywanie ścieżek

Wyszukiwanie ścieżek wielu agentów polega na znajdowaniu ścieżek dla wielu agentów od ich bieżących lokalizacji do ich lokalizacji docelowych bez kolizji ze sobą, przy jednoczesnej optymalizacji funkcji kosztu, takiej jak suma długości ścieżek wszystkich agentów. Jest to uogólnienie odnajdywania drogi. Wiele wieloagentowych algorytmów odnajdywania ścieżek jest uogólnionych z A* lub opartych na redukcji do innych dobrze zbadanych problemów, takich jak programowanie liniowe całkowitoliczbowe. Jednak takie algorytmy są zazwyczaj niekompletne; innymi słowy, nie udowodniono, że daje rozwiązanie w czasie wielomianowym. Inna kategoria algorytmów poświęca optymalność na rzecz wydajności, wykorzystując znane wzorce nawigacyjne (takie jak przepływ ruchu) lub topologię przestrzeni problemu.

Zobacz też

Bibliografia

Linki zewnętrzne