SI2020/route-planning.md

63 lines
3.5 KiB
Markdown
Raw Permalink Normal View History

2020-04-27 20:40:09 +02:00
# 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,
Karol Piotrowski,
Jarosław Zbąski.
2020-04-27 21:14:32 +02:00
# 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.
2020-04-27 21:34:28 +02:00
* 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
2020-04-27 23:07:20 +02:00
* h obliczne jest funkcją *calculateHValue*, która oblicza odległość w metryce Manhattan.
2020-04-27 21:34:28 +02:00
![](images/calculateHValue.png)
2020-04-27 22:58:50 +02:00
# Obroty traktora
2020-04-27 23:13:15 +02:00
Zwrot traktora jest zmieniany pod wpływem niezgodności porządanego kierunku ruchu z obecnym zwrotem w funkcji *CorrectMovement*
2020-04-27 20:40:09 +02:00
2020-04-27 23:08:04 +02:00
![](images/CorrectMovement.png)
2020-04-27 23:13:15 +02:00
# Funkcja isValid
Sprawdza, czy pole nie jest ścianą ('#').
![](images/isValid.png)
2020-04-27 23:15:53 +02:00
# Test celu
2020-04-27 23:33:52 +02:00
Funkcja isDestination sprawdza, czy agent osiągnął zadany cel.
2020-04-27 23:15:53 +02:00
2020-04-27 23:33:52 +02:00
![](images/isDestination.png)
# Funkcja aStarSearch
2020-04-27 23:55:21 +02:00
Jest to funkcja zawierająca główną pętlę strategii przeszukiwania.
![](images/aStarSearch.png)
2020-04-27 23:55:51 +02:00
Najpierw konfigurowane są początkowe parametry potrzebne do prawidłowego działania funkcji. Tworzone są dwie listy:
2020-04-28 00:06:08 +02:00
* **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.
2020-04-28 00:44:37 +02:00
* *openList*, która jest zbiorem par typu `<double, pair <int int> >`
2020-04-28 00:11:31 +02:00
W *cellDetails[i][j].parent_i* i *cellDetails[i][j].parent_j* zapisywane będą współrzędne poprzednika danej komórki
![](images/mainLoop.png)
2020-04-28 00:21:32 +02:00
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.
2020-04-28 00:44:37 +02:00
![](images/actionCheck.png)
2020-04-28 00:56:06 +02:00
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.
2020-04-28 00:54:38 +02:00
# 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.
![](images/tracePath.png)