3.0 KiB
Sztuczna inteligencja 2019 - Raport 3
Czas trwania opisywanych prac: 03.04.2019 - 14.04.2019
Członkowie zespołu: Anna Nowak, Magdalena Wilczyńska, Konrad Pierzyński, Michał Starski
Wybrany temat: Inteligentna śmieciarka
Link do repozytorium projektu: https://git.wmi.amu.edu.pl/s440556/SZI2019SmieciarzWmi
Planowanie ruchu - Algorytmy BFS i Best-first search
Implementacja
BFS (Iteracyjnie)
Algorytm przeszukiwania drzewa w głąb.
Algorytm jest niepoinformowany.
W przypadku BFS użyte struktury pozostają w gruncie rzeczy te same (z tym, że tym razem zamiast stosu do przechowywania stanu używamy kolejki), zmienia się tylko kolejność wykonywanych instrukcji:
Przebieg algorytmu:
- Dodaj do kolejki pierwszy krok
- Dopóki kolejka nie jest pusta:
- Zdejmij z kolejki następny nieodwiedzony wierzchołek grafu
- Jeżeli możliwa jest jakaś akcja (zebranie/oddanie smieci) wykonaj ją
- Sprawdź wszystkie sąsiednie wierzchołki wybranego wierzchołka, które jeszcze nie zostały odwiedzone
Best-first search
Agent idzie w kierunku celu do którego jest najbliżej w linii prostej w danym momencie.
Algorytm jest poinformowany.
Przebieg algorytmu
- Ustaw pozycję początkową
- Znajdź obiekt w znajdujący się najbliżej w linii prostej
- Jeżeli odległość od obiektu wynosi 1, wykonaj interakcję i usuń obiekt z listy celów, zwróć ścieżkę do obiektu
- Jeżeli przekroczono limit rekursji lub nie można wykonać kroku zakończ
- Na podstawie pozycji nowoobranego celu wybierz preferowane oraz niechciane kierunki poruszania się
- Posortuj dozwolone ruchy zgodnie z preferencjami
- Dla każdego kierunku na liście przeszukuj dostępne ścieżki dopóki jakakolwiek nie zostanie znaleziona
Ponadto, dołożyliśmy śmieciarzowi możliwość oddawania śmieci na wysypisko w ten sposób kompletując założenia planszy.
Obserwacje
W porównaniu do poprzednio zaimplementowanego DFS oba algorytmy sprawują się zdecydowanie szybciej. Przez to, że szukanie drogi nie odbywa się w głąb, agent nie traci czasu na przeszukiwanie wierzchołków z góry skazanych na porażkę. Poniżej przedstawiamy tabelę mierzącą liczbę kroków, która była potrzebna do wykonania przez agenta przy użyciu DFS, BFS i Best-first search na 5 przygotowanych do testów mapach:
| Algorytm / Kroki | Mapa 1 | Mapa 2 | Mapa 3 | Mapa 4 | Mapa 5 |
|---|---|---|---|---|---|
| DFS | 134 | 45 | 67 | 191 | 12 |
| BFS | 62 | 23 | 57 | 101 | 12 |
| Best-first | 55 | 20 | 58 | 99 | 12 |
Po wykonaniu testów możemy stwierdzić, że najlepszym z tych 3 algorytmów okazał się Best-first search. Warto jednak zauważyć, że różnica kroków jest mała.
Co widać bez jakichkolwiek wątpliwości DFS okazał się najgorszy (zgodnie z uzasadnieniem znajdującym się w raporcie nr. 2). Liczba kroków jest prawie dwukrotnie większa od tej w konkurujących algorytmach.
(Mapa 5 posiadała tylko jedną możliwe przejście posiadające 12 kroków ten wynik można pominąć.)