Úvod do algoritmov umelej inteligencie #6 - Vyhľadávací algoritmus A*

Bežné labyrinty, ktoré deti lúštia v časopisoch pre deti však majú znázornený aj začiatok, aj koniec labyrintu. Naša optimalizácia sa teda zameria aj na zohľadnenie pozície cieľa. Zvoľme si teda problém, ktorý je vhodný pre A* algoritmus. Teda hľadáme bludisko, kde poznáme začiatok a koniec labyrintu. Veľmi pekným takýmto problémom je 12ta úloha v Advent of Code 2022.

Predstavenie problému

Majme labyrint v ktorom sa môžeme pohybovať len vertikálne a horizontálne a navštíviť môžeme len tie susedné pozície, ktoré sú maximálne o 1 meter vyššie, rovnako vysoké alebo akokoľvek nižšie ako aktuálna pozícia. Výška je určená písmenom, teda napríklad b > a. Znaky S a E reprezentujú začiatok a koniec labyrintu.

Sabqponm
abcryxxl
accszExk
acctuvwj
abdefghi

Riešenie tohto labyrintu vyzerá nasledovne:

v..v<<<<
>v.vv<<^
.>vv>E^^
..v>>>^^
..>>>>>^

Tento labyrint má veľkosť len 7x5. Labyrint, ktorý chceme vyriešiť v Advent Of Code probléme, je však oveľa väčší.

Predstavenie algoritmu

Dijkstrov algoritmus si zo zoznamu vrcholov, ktoré chceme navštíviť vždy vybral ten, ktorý sme tam vložili ako prvý. A* vyberá taký vrchol zo zoznamu vrcholov, ktorého kombinovaná vzdialenosť od štartu a cieľa je najnižšia (vzdialenosť od cieľa len odhadujeme, keďže ju prirodzene nepoznáme). Teda ak je vrchol vzdialený od štartu 1 a od cieľa 4 uprednostníme ho pred vrcholom, ktorý je od štartu vzdialený 1 a od cieľa 6.

.a......
dSb...E.
.c......

a bodov a, b, c, d, ktoré sú rovnako vzdialené od S si vyberieme bod b, pretože je najbližšie k cieľu.

Ako teda bude náš algoritmus vyzerať?

1. Vytvoríme si zoznam vrcholov V a vložíme doň vrchol S (začiatok labyrintu)
2. V cykle opakujeme
3. v = Zo zoznamu vrcholov, vyberieme min(vzdialenost_S + vzdialenost_E)
4. ak v je náš cieľ, môžeme algoritmus ukončiť*
5. do zoznamu vrcholov vložíme všetkých susedov vrcholu v ktoré ešte neboli preskúmané a sú validné

V zozname vrcholov si potrebujeme držať aj nejaké údaje navyše. Minimálne z nich musí byť jasná vzdialenost_S a aktuálna pozícia

Takýto popis algoritmu pre nami riešený problém stačí. Treba si však uvedomiť, že bežne neriešime pohyb po mriežke v štyroch smeroch, ale skôr problémy hľadania najkratšej cesty medzi dvoma mestami. V týchto problémoch sú dĺžky ciest (hrán) rôzne. V takom prípade položky v zozname vrcholov V musíme aktualizovať ak sa ukáže, že nie sú ideálne. Teda bod 2.c sa rozšíri o overovanie, či sa daný vrchol už nenachádza v niektorej existujúcej ceste a v takom prípade prepočítame, či ho netreba aktualizovať.

Riešenie problému

Do nášho zoznamu vrcholov si budeme ukladať objekty, ktoré poznajú už prejdenú cestu. Z tejto cesty vieme určiť dĺžku už prejdenej trasy ako aj pozíciu na ktorej sa práve nachádzam.

data class AStarNode(val route: List)

Heuristickú vzdialenosť tohto vrcholu od koncovej pozície môžeme určiť ako manhattanovskú vzdialenosť. Teda nasledovne:

‍fun distanceFromEnd() : Int {
    return abs(route.last().x - endPosition.x) + abs(route.last().y - endPosition.y)
}

Pozn. v priloženom výslednom kóde bude zohľadnená aj súradnica z, teda nadmorská výška

A teraz k samotnému A* algoritmu. Poďme v cykle hľadať najlepší vrchol (2a). Samozrejme zaradzovanie v každej iterácii je zbytočné, ale je to najčitateľnejšie riešenie

‍fun astar(map: List>, position: Position): AStarNode? {
    // pozicie z ktorych budeme urcovat najkratsiu cestu
    val positions = mutableListOf(AStarNode(listOf(position)))
    
    // pozicie, ktore uz nechceme navstivit (uz sme ich ulozili do positions)
    val resolvedPositions = mutableListOf(position)
    
    while (positions.isNotEmpty()) {
        // zoradenie podla min(vzdialenost_S + vzdialenost_E)
        positions.sortBy { it.route.size + it.distanceFromEnd() }
        // vyber najlepsieho vrcholu
        val node = positions.removeAt(0)
        // ...
    }
    return null
}

Následne zistíme, či sme už dosiahli koniec:

val route = node.route
val actualPosition = route.last()
val actualSymbol = map[actualPosition.y][actualPosition.x]

// dosiahli sme koniec
if (map[actualPosition.y][actualPosition.x] == endSymbol) {
    return node
}

A nakoniec pridáme vhodných susedov do zoznamu na prehľadanie.

val left = Position(actualPosition.x - 1, actualPosition.y)
val top = Position(actualPosition.x, actualPosition.y - 1)
val right = Position(actualPosition.x + 1, actualPosition.y)
val bottom = Position(actualPosition.x, actualPosition.y + 1)

if (left.isValid(resolvedPositions, actualSymbol)) { positions.add(AStarNode(route + left)); resolvedPositions.add(left) }
if (top.isValid(resolvedPositions, actualSymbol)) { positions.add(AStarNode(route + top)); resolvedPositions.add(top) }
if (right.isValid(resolvedPositions, actualSymbol)) { positions.add(AStarNode(route + right)); resolvedPositions.add(right) }
if (bottom.isValid(resolvedPositions, actualSymbol)) { positions.add(AStarNode(route + bottom)); resolvedPositions.add(bottom) }

Finálne riešenie (s miernymi optimalizáciami) sú priložené v nasledujúcom gist-e. Vo finálnom riešení je A* implementovaný aj s implementačnými detailami, spomenutými vyššie (aktualizácia uložených ).

Vizualizácia hľadania cesty a porovnanie algoritmov

Hľadanie najkratšej cesty je ideálne aj vizualizovať. Myslím, že je čas postaviť vedľa seba Dijkstru a A*. Verím, že rozdiel v rýchlosti spozorujete hneď:

Dijkstra - prehľadávanie bezprostredného okolia, takmer celá mapa bola navštívená

A-Star - všimnite si podstatne priamejšie smerovanie k cieľu (vizualizácia je mierne prikrášlená)

Čo nás čaká?

Posledné 2 články boli o algoritmoch, ktoré výrazne neevokujú správanie umelej inteligencie. Sú však veľmi dôležité pre pochopenie toho, akým spôsobom dokážeme pracovať s grafmi, ktoré sú podkladom pre akýkoľvek algoritmus, ktorý sa správa inteligentne. Či už sa jedná o BFS, DFS, Beam search, MonteCarlo alebo vytrénovanú neurónovú sieť. A vlastne… to sú práve tie algoritmy, ktoré by som vám chcel ukázať…