Introduction to Artificial Intelligence Algorithms #6 - A* Search Algorithm

However, the common labyrinths that children solve in children's magazines have both the beginning and the end of the labyrinth shown. Our optimization will therefore also focus on taking into account the position of the target. So let's choose a problem that is suitable for the A* algorithm. So we are looking for a maze where we know the beginning and the end of the labyrinth. A very nice such problem is the 12th task in Advent of Code 2022.

Problem introduction

Let's have a labyrinth in which we can only move vertically and horizontally and we can visit only those neighboring positions that are a maximum of 1 meter higher, the same height or however lower than the current position. The height is determined by a letter, for example b > a. The signs S and E represent the beginning and end of the labyrinth.

Sabqponm
abcryxxl
accszExk
acctuvwj
abdefghi

The solution to this labyrinth looks like this:

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

This labyrinth is only 7x5 in size. However, the maze we want to solve in the Advent Of Code problem is much bigger (https://adventofcode.com/2022/day/12/input).

Algorithm introduction

Dijkstra's algorithm always chose the one we entered first from the list of vertices we want to visit. A* selects a vertex from the list of vertices whose combined distance from the start and the destination is the lowest (we only estimate the distance from the destination, since we naturally do not know it). That is, if the peak is distant from the start 1 and from the destination 4, we prefer it to the peak that is distant 1 from the start and from the destination 6.

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

and points a, b, c, d, which are equidistant from S, we will choose point b because it is closest to the goal.

So what will our algorithm look like?

1. We create a list of vertices V and insert the vertex S into it (the beginning of the labyrinth)
2. In the cycle we repeat
3. v = From the list of vertices, we select min(distance_S + distance_E)
4. if v is our goal, we can end the algorithm*into the list of vertices
5. we insert all neighbors of the vertex that have not yet been in reviewed and are valid

We also need to keep some extra data in the peak list. At least distance_S and current position must be clear from them

Such a description of the algorithm is sufficient for our problem. However, it should be noted that we do not usually solve the movement along the grid in four directions, but rather the problems of finding the shortest path between two cities. In these problems, the lengths of the paths (edges) are different. In that case, we have to update the entries in the list of vertices V if it turns out that they are not ideal. Thus, point 2.c will be extended to verify whether the given vertex is not already in an existing path, and in that case we will recalculate whether it needs to be updated.

Solving the problem

In our list of vertices, we will store objects that know the already traveled path. From this path, we can determine the length of the already traveled route as well as the position where I am at the moment.

data class AStarNode(val route: List)

We can determine the heuristic distance of this vertex from the end position as the Manhattan distance. So as follows:

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

Note.: in the attached resulting code, the z coordinate will also be taken into account, i.e. the altitudeA now to the A* algorithm itself.

Let's look for the best vertex (2a) in the cycle. Of course, marshalling in every iteration is unnecessary, but it is the most readable solution

‍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
}

We will then find out if we have already reached the end

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
}

And finally, we add suitable neighbors to the list to be searched.

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) }

The final solution (with slight optimizations) is attached in the following gist. In the final solution, A* is also implemented with the implementation details mentioned above (updating saved ).

Wayfinding Visualization and Algorithm Comparison

Finding the shortest path is also ideal to visualize. I think it's time to put Dijkstra and A* side by side. I believe you will notice the difference in speed right away:‍

What awaits us?

The last two articles were about algorithms that do not significantly evoke the behavior of artificial intelligence. However, they are very important for understanding how we can work with graphs, which are the basis for any algorithm that behaves intelligently. Whether it is BFS, DFS, Beam search, MonteCarlo or a trained neural network. And actually... those are the algorithms I would like to show you...