Sztuczna_Inteligencja_2020/route_planning.md

Raport 2

Algorytm A* znajduje się w pliku:

waiter.py

jako funkcja

findPath(self, goal)

Rozpoczyna się stworzeniem pustych list i określeniem wierzchołka startowego i końcowego.
Dla startowego wierzchołka określany jest rodzic: None

Pętla główna algorytmu

Główna pętla będzie trwać do momentu gdy openList będzie pusta.
Na początek openList jest sortowana, następnie usuwany jest z niej pierwszy wierzchołek i dodawany jest do closedList.

Następnym krokiem jest dodanie do tabeli children wierzchołki sąsiednie - sprawdzając czy takie istnieją tj. czy ich pozycja nie wychodzi poza zakres.

Wyszukiwanie następnika

Wyszukiwanie następnika polega na znalezieniu następnego wierzchołka do jakiego powinien pójść agent. Zawarte jest ono w pętli:

for child in children:

Na początku sprawdzamy czy danego "dziecka" nie ma w closedList tzn. wykluczamy możliwość cofnięcia się agenta po wierzchołkach, które już przeszliśmy.
Potem aktualizowane są parametry wierzchołka:

• ustalamy rodzica jako currentNode
• modyfikujemy startCost dodając jedynkę do startCost obecnego wierzchołka
• ustalamy heurystykę jako suma długości przyprostokątnych
• obliczamy totalCost dodając do siebie startCost i heuristic

Na koniec sprawdzamy jeszcze czy danego dziecka nie ma już w openList, a jeśli nie, to dodajemy go do openList.

Zwracanie ścieżki

Zwracanie ścieżki odbywa się gdy currentNode jest taki sam jak końcowy wierzchołek.
Tworzymy wtedy ścieżkę cofając się od końcowego wierzchołka do wierzchołka, którego rodzic jest równy: None

Translacja ścieżki

Znajduje się w pliku

waiter.py

jako funkcja

translatePath(self, path):

Przyjmuje jako argument ściężkę zwracaną przez algorytm A*.
Funckja ta sprawdza każdy wierzchołek ścieżki i porównując z obecną pozycją kelnera i kierunkiem w jaki jest odwrócony "tłumaczy" go na odpowiedni ciąg znaków, gdzie:

• F - oznacza ruch do przodu
• R - obrót w prawo
• L - obrót w lewo

Następnie zwraca ciąg output