LabVIEW Robotics Documents
Introduction to the A* Algorithm
The A*(pronounced “A star”) path planning algorithm is used in everything from video game development to driving direction software to autonomous vehicle control. It is best to understand the algorithm conceptually so that you can use it most effectively. In this tutorial, you will learn the concepts behind A* as well as see a simple example that implements A* using NI LabVIEW.
Understanding the Example
Let’s start with a simple example to demonstrate the concept - suppose someone wants to move from point A to point B in the most efficient way possible. A wall separates the two points. In Figure 1, we see the field as we’ve described it.
Figure 1
We have divided our search area into a square grid. Simplifying the search area, as we have done here, is the first step in pathfinding. This particular method reduces our search area to a simple two dimensional array. Each item in the array represents one of the squares on the grid, and its status is recorded as walkable or unwalkable. The path is found by figuring out which squares we should take to get from A to B, and then walking from midpoint to midpoint (hereafter called the “nodes”) of each of the squares along the path. It is possible to divide up your pathfinding area into other shapes, but for this example, we will use squares since they are the simplest example.
Starting the Search
Once we have simplified our search area into a manageable number of node, the next step is to conduct a search to find the shortest path. We do this by starting at point A, checking the adjacent node, evaluating the best next step, and continuing until we find B.
The A* implementation accomplishes this search by forming two lists. The “open list” is a list of nodes that we are actively considering as potential candidates for our next step. The closed list is a list of nodes that we have already evaluated and need not consider again.
To start, add the starting node to the closed list.
Look at all the nodes adjacent to the starting point, and add the walkable nodes to the open list while ignoring nodes that are not walkable. In our case, all of the adjacent nodes are walkable, so we will add 8 new nodes to the open list. We also will assign a “parent” to each node (we’ll see why later) - here we’ll save point A as its "parent node". In Figure 2, we see that the open list is outlined in green squares, and the parent node is noted by gray arrows.
Figure 2
Path Scoring
The key to determining which nodes to use when figuring out the path is the following equation:
F = G + H
G = the movement cost to move from the starting point A to a given node on the grid
H = the estimated movement cost to move from that given node on the grid to the final destination, point B. This is often referred to as the heuristic
Our path is generated by repeatedly going through our open list and choosing the node with the lowest F score.
G is the movement cost to move from the starting point to the given node using the path generated to get there. In this example, we will assign a cost of 10 to each horizontal or vertical node moved, and a cost of 14 for a diagonal move. We use these numbers because the actual distance to move diagonally is the square root of 2 or roughly 1.414 times the cost of moving horizontally or vertically, so the ratio is correct and whole numbers are easier to manage (especially in a tutorial).
H can be estimated in a variety of ways. The method we use here is called the Manhattan method, where you calculate the total number of node s moved horizontally and vertically to reach the target node(B) from the current node, ignoring diagonal movement, and ignoring any obstacles that may be in the way. We then multiply the total by 10, our cost for moving one node horizontally or vertically.
Figure 3
Finding the Path
In Figure 3, we can see the results of the scoring of our first round of nodes. In the node that we have highlighted, G = 10 because it is just one node from the starting node (A) in a horizontal direction. The nodes immediately above, below, and to the left of the starting node node all have the same G score of 10. The diagonal nodes have G scores of 14.
The H scores are calculated by estimating the Manhattan distance to the target node(B), moving only horizontally and vertically and ignoring the wall that is in the way. Using this method, the node to the immediate right of the start is 3 nodes from the target node (B), for a H score of 30. The node just above and to the right of the the starting node (A) is 4 nodes away (remember, only move horizontally and vertically) for an H score of 40.
Next, we choose the lowest F score node from all those that are on the open list move it to the closed list. All of the adjacent nodes that are walkable should be added to the open list. The nodes that are on the closed list should be ignored, and nodes that are already on the open list should be evaluated to see if this new path is a better one.
Figure 4
In Figure 4, we can see this illustrated. Of our initial 9 nodes, we have 8 left on the open list (outlined in green). Of these, the node with the lowest F cost is the one to the immediate right of the starting nodes, with an F score of 40.
We move it from our open list and add it to our closed list (that's why it's now highlighted in blue). Then we check all of its adjacent nodes. The ones to the immediate right of this square are inside the wall, so we ignore those. The one to the immediate left is the starting square. That's on the closed list, so we ignore that, too.
The other four nodes are already on the open list, so we need to check if the paths to those nodes are any better if you go through the "current" node to get there, using G scores as our point of reference. Let's look at the node right above the current node. Its current G score is 14. If we instead went through the current node to get there, the G score would be equal to 20 (10, which is the G score to get to the current node, plus 10 more to go vertically to the one just above it). A G score of 20 is higher than 14, so this is not a better path. That should make sense if you look at the diagram. It's more direct to get to that node from the starting node (A) by simply moving one node diagonally to get there, rather than moving horizontally one node , and then vertically one node.
When we repeat this process for all 4 of the adjacent nodes already on the open list, we find that none of the paths are improved by going through the current node, so we don't change anything. So now that we looked at all of the adjacent nodes, we are done with the current node, and ready to move to the next best node on the open list.
Repeat this process for all of the nodes on the open list, and you get the results shown in Figure 5.
Figure 5
To plan the complete path, you need to continue to repeat this process until you add the target node to the closed list, at which point the map would look like Figure 6.
Figure 6
Now to determine the path, just start at the target node, and work backwards moving from one node to its parent - in the diagram you can see this by following the arrows. This will eventually take you back to the starting node. It should look like the Figure 7. This path is the least cost path from the starting node (A) to the target node (B).
Figure 7
Implementing A* in LabVIEW
The LabVIEW Robotics Module includes various path planning algorithms including A*, so the remainer of this tutorial will reference an example – building a simple maze and finding the best path to the end of the maze. In Figure 8, we see the end result.
Figure 8
Building the Map
In LabVIEW, a map is represented as a 2D array of non-zero values. Each value corresponds with a cost associated with moving through that node. This allows you to not only represent “walkable” and “unwalkable” areas, but also assign values to the walkable areas to signify how difficult they are to walk. For example, imagine that we’re developing a mapping algorithm akin to Google Maps. By assigning lower cost to highways than you do side streets, you can influence the results of the algorithm so that the path includes highways when possible and side streets only when necessary. If this were not possible, the algorithm would always provide the shortest absolute pate regardless of traffic patterns.
In our LabVIEW example, we are providing a simple map of two values, so we are using a 2D array of Boolean controls to serve as the map input. Thus, the possible costs are either 100 or 1. This portion of the code is shown in Figure 9.
Figure 9
Once the map is created, we can plan the path. To do so, we just need to know the starting and ending locations on the map, and the A Star Plan VI will provide the best path according to the A* algorithm. In Figure 10, we see the path planning portion of the LabVIEW code.
Figure 10
Finally, we do some simple array manipulation for display, and we use an intensity map to show the maze and the planned path.
Figure 11
The final code is attached, and it requires the LabVIEW 2009 Robotics Bundle. For more information on sensors, drivers, decision making, or motor control with LabVIEW, visit ni.com/robotics.
What should I do if the route needs to keep a certain distance from obstacles?
as the picture shows
