A* Search exercise instructions
Here's the A* search puzzle. Or, get out the copy you picked up in class.The intent is to get from Start to Finish by the shortest path that doesn't cross the gray areas.
Say we want to use a search to find the path. What could our actions be? How could we move? We could move from wherever we are to any point we can "see" from where we are -- any point that isn't blocked by a gray wall. But...that's an infinite number of points! In fact, because the coordinates of a point are real numbers, there are an "uncountable" infinity of points, even in just a tiny region about where we are. How could we ever hope to search?
There's a trick, just for the sort of maze we have, where the blocked areas are polygons...
Notice that it never helps us to move to a point that's out in the middle of an open area. In fact, it doesn't help to move to anywhere that's not either a vertex of a gray area or the goal point. That can never make our path shorter, and it may make it longer. For instance:
No matter how you move the dashed line, it will always be longer than the solid path from Start to Finish. For much the same reason, it doesn't help us to put curves in our path. So the only moves we need to bother with are straight lines to vertices (labeled by letters) or the goal point (Finish).
What are legal moves? We can move to any vertex that is "visible" from where we are now (i.e. is not blocked by a gray area), or we can move to Finish, if it's not blocked.
What's the "cost" of a move? We're trying to find the path with the shortest distance, so our cost would be the distance we moved. Since we're going straight from point to point, it's the straight-line distance from where we are, to where we move to.
What's the cost of a path? It's the sum of the costs of the moves.
Now the real question: What's a good "heuristic"? We want something that estimates the cost of the remaining path, from where we are to the goal -- that estimates the distance left to go. And we want it to never over-estimate the cost. (That is, we want an "admissible" heuristic.) One easy estimate is the straight-line distance from wherever we are to Finish, ignoring any obstacles. And, by good fortune, it's admissible: If the goal isn't blocked, the straight-line distance is our shortest path from where we are to the goal. If it is blocked, then our real path will be longer than the straight-line distance.
Ok, now let's do it. Here's the A* algorithm. (Although it uses words like "point", "length", "Start", and "Finish" because it's applied to this problem, just read "state", "cost", "initial state", and "goal state", and it'll be general.)
Start at the x mark labeled Start. This is now the "current point" -- call the current point P. Put it on the Open queue (this is shown already). Figure out its heuristic (straight-line distance to Finish) and total estimated path cost (path length plus the heuristic, but the path length from Start is zero for Start, so this is just the heuristic) and put those in the distance table.
A* search
Repeat until we reach the goal, or we run out of points on the Open queue:
Pick up whichever point in the Open queue has the smallest total estimated path length (look for this in the distance table) and move it to Closed. (That condition, in bold, is what differentiates this type of search from others.)Here's the solution. (I've converted distances to decimal and rounded to 2 places to fit them into the boxes on the worksheet. Note I always rounded the heuristic down, to keep it admissible...)Is it the goal? If so, we're done.
Find all the legal points to move to (the "visible" vertices, and Finish, if it's visible) -- these are the "successors". Make a mark where the empty spaces start in the table of distances, to help remember which points were in this set of successors.
For each successor:
Ignore, for the moment, whether we've seen this point before (we might have got here before by some other path). Figure out the following:If we haven't already seen this successor (i.e. it's neither on Open or Closed), put it on Open. Write it in the table of distances, along with the the information found above.
- Find the length of the current path to this point -- add the path length from Start to the parent point (the point we just got here from, which should be in the table) plus the distance from the parent to this point which you can measure). Note this path length may change
- Find the heuristic -- the straight-line distance to Finish.
- Find the total estimated path length -- path length plus the heuristic.
If we have seen it (on Open or Closed), find its old entry in the distance table. Is the new path length to this point shorter than the old one?
If not, leave the old entry alone -- do no more with this point.If so, we've found a better path. Cross out the old distance entry and write in a new one, but make a note of the old length -- we'll need that in a moment. Now we need to update any other paths that this point is on, to take into account the reduction in length. Compute the difference between the old length and the new length -- call that "delta".
Find any distance table entries that "came from" this point. Subtract delta from their path length and total estimated path length. If any of these points are in Closed, move them to Open.Now chain forward through the paths (follow the "came from" links from this new set of points) and do the same to their decendants. Repeat until these paths are followed to their ends (i.e. no entries have them in their "came from" field).