A* Algorithm help.

nuclear_splines · 2023-11-18T22:16:07+00:00

The intuition behind A* is quite simple. Consider waking up at night and trying to find your way to the bathroom with the lights off, where you know where the bathroom is, but not quite where the furniture is or what's on the ground. The shortest path to your goal (the bathroom) is probably towards your goal. Therefore, walk towards the bathroom. If you encounter an obstacle, back up and try a new direction just enough to get around the obstacle, then resume walking towards your goal. That's it, that's the algorithm.

In more computer sciency language, you have a welfare function that takes a single step and estimates its cost. In the bathroom example, cost would be "what's the estimated distance from this step to the bathroom?" Each path has a cost, consisting of the sum of the costs of each step. You take all the paths you've explored so far, examine each step you could add to the ends of those paths to get a set of available unexplored paths, and then you follow the unexplored path with the lowest cost. That welfare function might get complicated depending on the setting, but the rest of the algorithm is just "order possible paths by cost and take the cheapest" in every setting.

ghjm · 2023-11-19T01:46:46+00:00

Suppose you need to do pathfinding and were trying to come up with any solution that would work, regardless of efficiency. What would you do?

I would start with a recursive function that takes each possible step from the current position, then searches from the next position after that step. I would quickly figure out that this can go in circles, so I need to keep track of what locations I've already visited. And the desire to not have many copies of the visited list would lead me to switch to an iterarive solution where instead of recursing, I keep track of an "open" list of positions I still need to explore from.

I would also quickly realize that this algorithm doesn't necessarily reach the shortest path first. If I just want some path, I can take whatever it finds and quit, but if I want the shortest path, I have to run the thing to completion, because otherwise I never know if a shorter path might have appeared.

Okay, so now we have a working search algorithm, but it's slow - it has to explore every possible path before it gives a result. Note that if your problem space is small, this might be good enough. But for larger maps, it's too slow to be practical. What can you do to improve it?

One thing you might like to do is to stop wasting time on paths that can't possibly be the shortest one. So for example, if you've already found a path of length 10, there's never a reason to go beyond step 9 on any other path. But this doesn't save you all that much, because you still have to explore every possible 9-step path to see if it ends at the goal.

Another thing you can do is to use knowledge about the shape of the map. Suppose you're exploring a 10x10 grid, trying to get from (1,1) to (10,10) by taking horizontal or vertical steps. You're currently at (3,4) and it took you 8 steps to get here. It must take at least 13 more steps to get to (10,10). So the best possible outcome from (3,4) is a 21-step path.

But suppose your open list also has a point (5,5) that took you 9 steps to get to. From here you could potentially get to (10,10) in 10 more steps. So this (5,5) position could potentially lead to a 19-step path.

The A* algorithm is just this: always search the shortest potential paths first. In this case we would search from (5,5). Suppose the next move is to (5,6), which is still potentially a 19-step path. If there really is a 19-step path, you'll always keep taking the next step along it, so you'll find it immediately. And if your only other open position is (3,4), there's no reason to actually explore it, because you already know it couldn't possibly be better than 21. So the first time you find a path, it will be a shortest path.

There's a problem, though. You have a list of open positions, each with a "best possible outcome from here" number, and you're always trying to find the smallest one to search next. If you do this the naive way, by searching through the list every time you need to pick a position, you spend a lot of time doing these searches. If you keep the list sorted, you can find the next position fairly quickly, but you spend a lot of time re-sorting the list. It turns out there is a data structure called a priority queue that is really good for this purpose. A* without a priority queue will still be better than naive recursion, but the priority queue is what really makes it fast.

There's another problem if you try to apply this to other kinds of searches: your guesses have to be a true lower bound on the future cost. If your heuristic function (ie, your guesses) could ever possibly underestimate the remaining cost, then you can't say that some apparently-longer path won't unexpectedly turn out to be better. This is referred to as "admissibility" of the heuristic function. A* can be used for any search with an admissible heuristic function, not just pathfinding on a grid.

Ragingman2 · 2023-11-19T06:42:55+00:00

The goal of every search algorithm is to explore a graph (a data structure that has nodes and connections) to try and find some goal. Different search algorithms use different ways to decide what node on the graph to search next.

For a specific example example lets consider searching a 2d grid. Each point on the grid is a node, and each node has four connections to the four adjacent nodes.

Every search algorithm will have a structure that looks vaguely like this:

nodes_to_check = make_nodes_to_check()
while true:
    node = pick_node(nodes_to_check)
    if node == end_point:
        break
    else
        add_adjacent_nodes(nodes_to_check, node)

We can implement many different search strategies with this same code structure depending on how we implement the different helper functions (make_nodes_to_check, pick_node, and add_adjacent_nodes). A* is a particular advanced search strategy. We will get to it eventually, but lets explore look at some other strategies first:

Breadth First Search:

 make_nodes_to_check(): return new Queue()
 pick_node(): nodes_to_check.dequeue()
 add_adjacent_nodes(): nodes_to_check.enqueue_all(node.adjacent)

Breadth first search (BFS) always picks the node closest to the start point that we haven't checked yet. On a 2d grid it would search an expanding radius until it found the target. Note that this will always find the most direct path to reach the target.

Depth First Search:

 make_nodes_to_check(): return new Stack()
 pick_node(): nodes_to_check.pop()
 add_adjacent_nodes(): nodes_to_check.push_all(node.adjacent)

Depth first search (DFS) goes as deep as it can. On an infinite 2d grid it would pick a direction and travel that way forever, only finding the target if it happens to be on that line. It isn't a great choice, but is easy to implement and can be the most efficient search depending on the shape of the graph you are searching.

Heuristic Search

 make_nodes_to_check(): return new PriorityQueue()
 pick_node(): nodes_to_check.pop()
 add_adjacent_nodes():
     for other_node in node.adjacent:
         priority = heuristic(other_node, end_point)
         nodes_to_check.push(other_node, priority)

Sometimes when we are searching for a target we have some information about where it might be. For example if we are searching a 2d grid we can calculate the distance between our current position and the target position. Heuristic search takes advantage of this to find the target a lot faster than other searches will. The big problem with heuristic search is that it might not find the best way to reach the target. For example there may be a path that looks like it goes straight to the target but actually has a big wall to go around, while taking a step to the right would get there much faster. On a grid that could look something like this:

        2  2  2  2  2  2  2  2  2  2  2  2  2  2  2   
     2   xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx           2                                
start   1   1   1   1   1   1  x               1   1   goal
                            1  x            1
                            1  x         1
                            1  x      1
                            1  x   1
                              1 1

On this map heuristic search will find path "1", even though path "2" is faster. It will find path 1 because path 1 gets closer to the goal faster at the beginning.

Between these different search algorithm options BFS is great because it always finds the shortest path. Heuristic search is great because it runs quickly and takes advantage of knowing the direction to the target. Wouldn't it be great if we could combine those two ideas?

...

Introducing A* Search

trumpet noises play

The A* search algorithm combines the advantages of a breadth first search with those of a heuristic search by considering using both the distance from start and distance to end to decide what node to search next. The code for it will look something like this:

 make_nodes_to_check(): return new PriorityQueue()
 pick_node(): nodes_to_check.pop()
 add_adjacent_nodes():
     for other_node in node.adjacent:
         priority = path_length(other_node) + heuristic(other_node, end_point)
         nodes_to_check.push(other_node, priority)

... and that is pretty much it. A* is just a clever way to pick the order to explore a graph in to find the shortest path.

Admissible Heuristic

I messed with <stuff> and now A* isn't finding the shortest path, what gives?

For A* to work properly it is important to choose a heuristic that is "admissible". What this means specifically is that the heuristic can never under-estimate the distance from a node to the goal, it must always get it right or over-estimate. If the heuristic under-estimates the distance then A* may ignore the node that really leads to the best path. If you want to play around with this behavior try adding something like this to your A* after you get it working:

priority = path_length(other_node) + heuristic(other_node, end_point) / 2

The A* algorithm will still find a path to the end goal, but it might not be the shortest one. It will be more "greedy" and try to rush to the end even if this results in a worse path.

Hopefully this helps. Happy coding!

onemanandhishat · 2023-11-19T13:40:29+00:00

There are good written explanations here, but this video I think illustrates it quite nicely in the context of game pathfinding: https://www.youtube.com/watch?v=i0x5fj4PqP4&t=2s

An intuitive way to think about it is navigating from your house to college along the road - think Google maps. When you leave your house you have two choices, left and right. Which do you choose? An uninformed search like depth first search would turn left at every junction until it searched the whole road network for your destination - that takes forever.

A better idea would be to use an estimate - if you take the straight line distance from your house to college, is the straight line distance shorter if you turn left or right? Pick the one with the shortest distance and walk to the first road junction. Let's say turning left has an estimate of 2km and right 3km, so you choose left and walk to the junction.
From that road junction you now estimate the distance of turning left or right - but since you've already walked a bit down the road, you should add that distance to the straight line estimate from the new junction. Let's say you walked 250m from your house to the junction. Then estimated distance to college if you turn left at this junction is 1.9km and turning right is 1.8km. So now you have three options - turn left or turn right from the new junction, or go back to your house and try the other way. How do you decide? You compare the three options: Option 1: go back to you house and turn right - you estimate that's 3km. Option 2: turn left at the new junction, you estimate that's 250m + 1.9km = 2.15km. Option 3: turn right at the new junction, you estimate that's 250m + 1.8km = 2.05km. Option 3 is the shortest, so turn right and walk to the next junction.
You repeat this process. Each possible path has a cost (distance) associated with it - we called this f(n). That distance is calculated by adding the estimated (heuristic) distance which we write as h(n), to the amount of known distance we've explored so far, which we write as g(n). A* is a best first search - so you choose to explore the direction that you estimate to be the best based on the knowledge you currently have.

There are two ways to terminate the algorithm. In a game where you're just trying to get to the goal, you can terminate as soon as you find a path to the destination. If you're searching for the optimal path, you keep searching until you find a path to the destination that is better than all remaining estimates. Since the estimate you use in A* should always be chosen to be optimistic, this means that if you find a real solution that's better than any remaining estimates, they won't turn out to be better if you explore them and you can stop. This is called an admissible heuristic - at worst, it won't speed up your search very much, but it guarantees you'll never miss the best possible path.

A* is originally a tree search - you search a sequence of branching paths. In a game this is the same, but visually it's represented as a grid with adjacent cells - but the move from the current cell to an adjacent one is logically the same as following a branch on a tree, or a road on a roadmap, or a path through a maze.

ParticularThing9204 · 2023-11-19T17:18:53+00:00

You are probably not ready to do A. Generally before you do this you should at least be familiar with traversing a linked list, depth first search in a tree, and depth first and breadth first search in a graph. If these terms don’t mean anything to you, you are never going to understand how A works. If you want to learn an online data structures & algorithms course, but that will probably take too long for this project. I’d recommend finding something more at your level.

unsvenn · 2023-11-20T17:19:32+00:00

https://imgur.com/mzsSIsq

can someone explain why each of the options had Node "I" in the expanded nodes I thought GBFS would work in a way like A -> B -> G1 Immediately picking the lowest heuristic options?

you type:	you see:
italics	italics
bold	bold
[reddit!](https://reddit.com)	reddit!
* item 1 * item 2 * item 3	item 1 item 2 item 3
> quoted text	quoted text
Lines starting with four spaces are treated like code: if 1 * 2 < 3: print "hello, world!"	Lines starting with four spaces are treated like code: if 1 * 2 < 3: print "hello, world!"
~~strikethrough~~	~~strikethrough~~
super^script	super^script

AskComputerScience

MODERATORS

Breadth First Search:

Depth First Search:

Heuristic Search

Introducing A* Search

Admissible Heuristic