3.5 KiB
Opis dokumentu
Ten dokument to raport z wykonanego drugiego zadania projektu zespołowego na przedmiot Sztuczna Inteligencja. Celem zadania jestzastosowanie strategii przeszukiwania stanów A* do problemu planowania ruchu agenta na kracie. Tematem projektu jest inteligentny traktor.
Zespół
W skład zespołu wchodzą:
Tomasz Dzierzbicki,
Szymon Parafiński,
Laura Piotrowska,
Jarosław Zbąski.
Zasady poruszania się agenta po planszy
- Agent nie może wejść na pole oznaczone jako '#', gdyż jest to granica mapy.
- Koszt wejścia na pole bez buraków oznaczone jako '.' wynosi 1.
- Koszt wejścia na pole buraków oznaczone jako 'B' wynosi 9.
- Agent może poruszać się do przodu i obracać się w lewo/prawo.
Heurystyka i koszt w algorytmie przeszukiwania
Koszt f obliczany jest ze wzoru f=g+h, gdzie:
- g - suma wag należących do ścieżki
- h obliczne jest funkcją calculateHValue, która oblicza odległość w metryce Manhattan.
Obroty traktora
Zwrot traktora jest zmieniany pod wpływem niezgodności porządanego kierunku ruchu z obecnym zwrotem w funkcji CorrectMovement
Funkcja isValid
Sprawdza, czy pole nie jest ścianą ('#').
Test celu
Funkcja isDestination sprawdza, czy agent osiągnął zadany cel.
Funkcja aStarSearch
Jest to funkcja zawierająca główną pętlę strategii przeszukiwania.
Najpierw konfigurowane są początkowe parametry potrzebne do prawidłowego działania funkcji. Tworzone są dwie listy:
- bool closedList[][] , która jest tablicą z początkowymi wartościami False, która przechowuje informacje o tym, czy dana komórka została już odwiedzona.
- openList, która jest zbiorem par typu
<double, pair <int int> >W cellDetails[i][j].parent_i i cellDetails[i][j].parent_j zapisywane będą współrzędne poprzednika danej komórki
Główna pętla pozostaje otwarta, dopóki openList nie będzie pusta. Pierwszą z instrukcji zawartych w pętli while jest zapamiętanie współrzędnych z pary z początku zbioru openList, zapisanie ich pod zmiennymi i i j, usunięcie pary ze zbioru i oznaczenie komórki o danych współrzędnych jako odwiedzoną. Następnie do zmiennej waga przypisuje się wagę tego pola.
Następnie po kolei dla wszystkich akcji ruchu następuje sprawdzenie za pomocą isValid, czy z obecnego stanu można tę akcję wykonać. Jeśli następnie powiedzie się test celu dla stanu komórki otrzymanej po wykonaniu danej akcji, zapisujemy adres poprzedniej komórki jako rodzica (poprzednika) obecnej, wykonujemy funkcję tracePath i zamykamy program. W przeciwnym wypadku obliczmy nowe f, wyliczając uprzednio g i h. Jeśli f osiągnęło już zbyt wysoką wartość, dodajemy do openList nową parę złożoną z nowego f oraz współrzędnych obecnego pola i nadpisujemy stare f, g i h nowymi i ustawiamy rodzica (poprzednika) obecnej komórki na adres poprzedniego pola.
Funkcja tracePath
Ta funkcja składa się z dwóch funkcji while. W pierwszej z nich na stos Path odkładane są wszystkie adresy, które tworzą ścieżkę z celu do pola początkowego naszego agenta. Wykorzystujemy do tego wcześniej zapisane adresy poprzedników danych komórek w ścieżce. W drugiej pętli następuje translacja zebranych danych na faktyczny ruch agenta na planszy.
