72 lines
3.1 KiB
Markdown
72 lines
3.1 KiB
Markdown
# Sztuczna inteligencja 2019 - Raport 2
|
||
|
||
**Czas trwania opisywanych prac:** 06.03.2019 - 26.03.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
|
||
|
||
## Pierwszy algorytm przeszukiwania mapy - DFS
|
||
|
||
#### Implementacja
|
||
|
||
Pierwszym podejściem naszej grupy do rozwiązania problemu była implementacja
|
||
algorytmu przeszukiwania drzewa w głąb - DFS (Wersja rekurencyjna).
|
||
Aby zaimplementować ten algorytm, niezbędne było przygotowanie dla niego kilku
|
||
struktur pomocniczych dzięki którym będziemy mogli jasno zdefiniować warunki stopu i uzyskać satysfakcjonujące nas rozwiązanie.
|
||
|
||
Do użytych struktur należą:
|
||
|
||
- **Lista dwuwymiarowa przedstawiająca mapę w formie siatki po której można łatwo iterować** - Jeden stan takiej listy traktowaliśmy jako wierzchołek grafu
|
||
- **Lista możliwych ruchów do wykonania przez agenta przy konkretnym stanie mapy**
|
||
- **Licznik głębokości na którą zszedł algorytm** - Zapobiega zajściu za głęboko w przypadku braku rozwiązania
|
||
|
||
**Przebieg algorytmu**:
|
||
1. Sprawdź czy w pobliżu śmieciarki znajduje się nieopróżnioony domek
|
||
2. Jeżeli możliwa jest jakaś akcja (zebranie/oddanie smieci) wykonaj ją
|
||
- Jeżeli akcja została wykonana, zakończ algorytm
|
||
- Jeżeli nie, sprawdź czy głębokość przekroczyła 30
|
||
1. Jeżeli tak, zakończ algorytm informacją o braku rozwiązania
|
||
2. Jeżeli nie, kontynuuj algorytm
|
||
3. Dla każdego możliwego kierunku wykonaj algorytm od punktu 1
|
||
|
||
Rozwiązanie następuje wtedy, gdy domek zostaje opróżniony. Algorytm zostaje wywołany tyle samo razy, ile jest domków. Agent nie zna położenia domków na mapie podczas działania algorytmu.
|
||
|
||
#### Obserwacje
|
||
|
||
Przede wszystkim, algorytm przeszukiwania w głąb działa dla tego problemu
|
||
**zdecydowanie wolniej niż powinien**, przy jego działaniu łatwo wchodzić w głąb złej ścieżki, która nie doprowadzi nas do rozwiązania. Co prawda przy małej mapie algorytm radzi sobie z problemem, jednak z każdą kolejną większą
|
||
jest co raz gorzej.
|
||
|
||
Problem można pokazać na przykładzie:
|
||
|
||
Załóżmy, że hipotetyczne drzewo T wygląda w taki sposób:
|
||
|
||
```
|
||
a -- e
|
||
|
|
||
b
|
||
|
|
||
c
|
||
|
|
||
d
|
||
.
|
||
. - 100 wierzchołków
|
||
.
|
||
x
|
||
```
|
||
|
||
Naszym rozwiązaniem będzie doprowadzenie agenta z wierzchołka startowego **a** do wierzchołka końcowego **b**. DFS odwiedzi najpierw wierzchołki po kolei od a aż do x i dopiero później przyjdzie do e. Naturalnie można stwierdzić, że to nie jest sposób którego szukamy. Oczywiście 100 wierzchołków to mała liczba dla komputera, ale co jak będzie ich 1000, 10 000, lub 1 000 000 ?
|
||
|
||
#### Podsumowanie
|
||
|
||
Szukanie w głąb miałoby sens w innych przypadkach, na przykład gdybyśmy chcieli znaleźć możliwe wyniki w grze gdzie każda akcja pociąga za sobą kolejną, tworząc dość głęboki graf.
|
||
|
||
Do szukania ścieżki po której ma poruszać się agent lepiej byłoby jednak przeszukiwać graf wszerz.
|
||
|
||
#### Uruchamianie
|
||
|
||
Aby uruchomić DFS na mapie Śmieciarza WMI, należy kliknąć **0**.
|