Aktualności

Dodano: 2020-03-19

Jest to kolejny artykuł z serii o Reinforcement Learning - uczeniu maszynowym ze wzmocnieniem. Zalecamy przeczytanie poprzednich, zaczynając od pierwszego [LINK], by w pełni zrozumieć pojęcia, którymi się posługujemy.

Algorytm A* w najprostszy sposób przedstawia poruszanie się między stanami oraz otrzymywanie informacji ze środowiska, w którym agent się znajduje. W algorytmie tym agent wie, gdzie znajduje się cel i na tej podstawie wyznacza swoją ścieżkę. Ścieżka nie zawsze jest najkrótsza, ale najbardziej optymalna względem danego kryterium. Zaletą algorytmu jest fakt, że w poszukiwaniu najlepszej ścieżki przechodzi tylko przez te stany (punkty na mapie), które z punktu widzenia celu stanowią kandydata na najlepszą ścieżkę (pod warunkiem, że start i meta nie znajdują się w największej odległości w skrajnych punktach środowiska).

Rysunek 1: Wyszukiwanie ścieżki przy pomocy algorytmu A* [1]

Określanie optymalnej ścieżki dla tego algorytmu odbywa się poprzez wybór sąsiadującego punktu (stanu) o najmniejszej wartości. Wartość dla danego punktu wyliczana jest na podstawie kosztu dokładnego oraz kosztu przybliżonego. Z punktu widzenia świata na mapie, przedstawia się to jako sumę odległości startu od aktualnego stanu oraz przybliżonej wartości od aktualnego stanu do celu (wartość heurystyczna). Wartość heurystyczna może być obliczana na różne sposoby, jednym z nich jest odległość Manhattańska (ang. manhattan distance).

Z punktu widzenia implementacji, sam algorytm do wyznaczania ścieżki prezentuje się tak:

Ustal stan początkowy, końcowy i możliwe akcje. Dodatkowo stwórz strukturę, określającą przejście od stanu “rodzic” do stanu “dziecko”. Ta struktura będzie tworzyła drogę od startu do mety.
Dodaj stan początkowy do listy stanów do sprawdzenia.
W liście stanów do sprawdzenia znajdź stan o najniższym koszcie f (f = koszt dokładny + koszt przybliżony).
Sprawdź, czy wybrany stan jest równy stanowi końcowemu.
Jeśli wybrany stan nie jest stanem końcowym, znajdź sąsiadów tego stanu i dodaj go do listy sprawdzonych stanów.
Jeśli sąsiad został już wcześniej sprawdzony (znajduje się na liście stanów sprawdzonych) lub nie da się wykonać w tym stanie żadnej akcji - zignoruj.
W przeciwnym razie:
- jeśli sąsiedni stan nie jest jeszcze w liście stanów do sprawdzenia - dodaj go
- jeśli znajduje się liście stanów do sprawdzenia, oblicz dla tego stanu koszt dokładny, aby sprawdzić, czy droga do celu jest lepsza. Im mniejsza wartość tym lepsza droga. Jeśli jest lepsza - zaktualizuj strukturę przejść oraz wartości kosztu f i kosztu dokładnego dla tego stanu.
Wróć do punktu 3. i sprawdzaj do momentu, aż punkt 4. będzie prawdziwy.

Rysunek 2: Szukanie optymalnej ścieżki. Żółte punkty - ścieżka. Czerwone punkty - przeanalizowane stany. [2]

Algorytm A* znajduje swoje zastosowanie w grach czy mapach, gdzie środowisko jest wyposażone w różnego rodzaju przeszkody, a celem jest znalezienie najbardziej optymalnej/najkrótszej ścieżki między startem a metą. Został on przez nas sprawdzony w grze Snake.

Aby uniknąć kolizji ze ścianą, przeszkodą czy nawet samym agentem, do algorytmu została wprowadzona dodatkowa wartość, jaką otrzyma agent przy zderzeniu przy którymś z powyższych elementów, która została wliczona w koszt dokładny. Tak prezentuje się ten algorytm w grze Snake:

Rysunek 3: Implementacja algorytmu A* w grze Snake.

ŹRÓDŁA:
[1] https://ceopedia.org/index.php?title=File:AStar_algorithm.gif&filetimestamp=20140203165537
[2] https://mathematica.stackexchange.com/questions/39465/how-to-display-each-step-of-an-a-star-algorithm

Autorzy: Izabela Wiatrowska i Adrianna Cieńciała

Algorytm A* - szybko i tanio