**Post: #1**

[attachment=386]

Presented by:Sougata Sinha

Use of A algorithm for obstacle avoidance

Abstract

A* algorithm is basically a path finding algorithm based on Artificial Intelligence. It is used nowadays extensively in the field of game programming and robotics to figure out an optimum path in an environment full of obstacles. The A* algorithm can be used in both 2-D and 3-D terrain. Each terrain is represented as a map. The beauty of the algorithm is that,by varying it's heuristics a scalability between efficiency and accuracy can be obtained. In a'nutshell A* algorithm is quick and accurate.For this reason it is used extensively in real-time programs.

Introduction

1'al.li finding is a process 1,1ml lot us look ahead and make plans rather than wailing until the last moment, to discover that there's a problem. Let us assume that, we have someone who wauls to gel from point A to point B. Let us assume that a wall separates the two points.First the search area has to be divided into a square grid. 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 walk able or not walk able. The path is found by figuring out, which squares we should take lo get from A to B. Once the path is found, our person moves from the center of one square to the center of the next until the target is reached.

Algorithm for path finding already existed like the Dijkstra and the Best First Search(BFS).

• Dijkstra's algorithm works by visiting vertices in the graph starting with the object's starting point. It then repeatedly examines the closest not-yet-examined vertex, adding its vertices to the set of vertices to be examined. It expands outwards from the starling point until it reaches the goal. Dijkstra's algorithm is guaranteed to find a shortest path from the starting point to the goal, as long as none of the edges have a negative cost.

• The Best-First-Search (BFS) algorithm works in a similar way, except that it lias some estimate (called a heuristic) of how far from the goal any vertex is. Instead of selecting the vertex closest to the starting point, it selects the vertex closest to the goal. BFS is not. guaranteed to find a shortest path, however, it runs much quicker than Dijkstra's algorithm because it uses the heuristic function to guide its way towards the goal very quickly. For example, if the goal is to the south of the starting position, BPS will tend to focus on paths that lead southwards.

For the simplest case when the map has no obstacles, and the shortest path really is a straight line. If consider the concave obstacle {as in real Ufe) Dijkstra's algorithm works hr.rder but is guaranteed to find a shortest path. BFS on the other hand does less work but its path will clearly not be as good because BFS is greedy and tries to move towards the goal even if it's not the right path. Since it only considers the cost to get to the goal and ignores the cost of the path so far, it keeps going even if the path it's on has become really long.

Here comes the need of the A* algorithm which combines heuristic approaches like BFS and formal approaches like Dijsktra's algorithm. It's a little unusual in that heuristic approaches like BFS usually gives an approximate way to solve problems without guaranteeing that we get the best answer. However, A* is built on top of the heuristic, and although the heuristic itself does not give us a guarantee, A* can guarantee a shortest path.

2 Description Of The Algorithm

The secret to its success is that it combines the pieces of information that Dijkstra's algorithm uses (favoring vertices that are close to the starting point) and information that BFS uses (favoring vertices that are close to the goal). In the standard terminology used when talking about A*, g(n) represents the cost of the path from the starting point to any vertex n, and h(n) represents the heuristic estimated cost from vertex n to the goal. A* balances the two as it moves from the starting point to the goal. Each time through the main loop, it examines the vertex n that has the lowest f(n) — g(n) + h(n).

2.1 The Heuristics

The heuristic function h(n) tells A* an estimate of the minimum cost from any vertex n to Ihe goal. It's important to choose a good heuristic function because heuristic can be used to

(■Hill-id A*'s behavior.

The effect of heuristics on the path computing nature of A* are :-

• At one extreme, if h(n) is 0, then only g(n) plays a role, and A* turns into Dijkstra's algorithm, which is guaranteed to find a shortest path.

• If h(n) is always lower than (or equal to) the cost of moving from n to the goal, then A* is guaranteed to find a shortest path. The lower h(n) is, the more node A* expands, making it slower.

• If h(n) is exactly equal to the cost of moving from n to the goal, then A* will only follow the best path and never expand anything else, making it very fast. Although we can't make this happen in all cases, we can make it exact in some special cases. It's nice to know that given perfect information, A* will behave perfectly.

• If h(n) is sometimes greater than the cost of moving from n to the goal, then A* is not guaranteed to find a shortest path, but it can run faster.

• At the other extreme, if h(n) is very high relative to g(n), then only h(n) plays a role, and A* turns into BFS.

So we have an interesting situation in that we can decide what we want to get out of A*. At exactly the right point, we'll get shortest paths really quickly. If we're too low, then we'll continue to get shortest paths, but it'll slow down. If we're Loo high, then we give up shortest paths, but A* will run faster.In a game, this property of A* can be very useful. For example, we may find that in some situations, we would rather have a "good" path than a "perfect" path. To shift the balance between g(n) and h(n), we can modify either one.

3 Usefulness Of The Algorithm

A*'s ability to vary its behavior based on the heuristic and cost functions can be very useful in a game for path finding. For most cases (in a game), we don't really need the best path between two points. We just need something that's close.

3.1 An Example

Suppose we have two types of terrain, Flat and Mountain, and the movement costs are 1 for flat land and 3 for mountains, A* is going to search three times as far along flat land as it does along mountainous land. This is because it's possible that there is a path along fiat terrain that goes around the mountains. We can speed up A*'s search by using 1.5 as the heuristic distance between two map spaces. A* will then compare 3 to 1.5, and it won't look as bad as comparing 3 to 1. It is not as dissatisfied with mountainous terrain, so it won't spend as much time trying to find a way around it. Alternatively, we can speed up A*'s search by decreasing the amount it searches for paths around mountains by just telling A* that the movement cost on mountains is 2 instead of 3. Now it will search only twice as far along the flat terrain as along mountainous terrain. Either approach gives up idea! paths to get something quicker.

3.2 Effect of heuristic function

Let us consider a heuristic function:-g'(n) = 1 + alpha * (g(n) - 1)

If alpha is 0, then the modified cost functioih will always be 1. At this setting, terrain costs are completely ignored, and A* works at the level of simple passable/impassable grid spaces. If alpha is 1, then the original cost function will be used, and we get the full benefit of A*. We

nil) set alpha anywhere in between.

W'c slmuM also consider switching from the heuristic returning the absolute minimum cost, to returning tin: expected minimum cost. For example, if most of our map is grasslands with a movement cost of 2 but some spaces on the map are loads with a movement cost of 1, then we might consider having the heuristic assume no roads, and return 2 * distance.

4 Working Of The Algorithm

If our heuristic is exactly equal to the distance along the optimal path, we'll see A* expand very few nodes. What's happening inside A* is that it is computing f(n) — g(n) + h(n) at every node. When h{n) exactly matches g(n), the value of f(n) doesn't change along the path. All nodes not on the right path will have a higher value of f than nodes that are on the right path. Since A* doesn't consider higher-valued f nodes until it has considered lower-valued f nodes, it never strays off the shortest path.

4.1 Computation Of The Heuristic

One way to construct an exact heuristic is to pre-compute the length of the shortest path between every pair of points. This is not feasible for most game maps. However, there are ways to approximate this heuristic:

• We can fit a coarse grid on top of the fine grid and then pre-compute the shortest path between any pair of coarse grid locations.

• Pre-compute the shortest path between any pair of waypoints. This is a generalization of the coarse grid approach.

Then a heuristic h' is added that estimates the cost of going from any location to nearby waypoints. The final heuristic will be:

h(n) = h'(n, wl) + distaiice(wl, w2), h'(w2, goal)

If we want a better but more expensive heuristic, we evaluate the above with all pairs wl, w2 that are close to the node and the goal, respectively.

4.1.1 Linear Exact Heuristic

In a special circumstance, we can make the heuristic exact without pre-computing anything. If we have a map with no obstacles and no slow terrain, then the shortest path from the starting point to the goal should be a straight line.

4.1.2 Heuristics For Grid Maps -

On a grid, there are well-known heuristic functions to use:-

• The standard heuristic is the textbf Manhattan distance.We look at our cost function and find the minimum cost D for moving from one space to an adjacent space. Therefore, the heuristic in this case should be D times the Manhattan distance:

h(n) = D * (abs(n.x-goal.x) + abs(n.y-goal.y))

• If on our map we allow diagonal movement we need a different heuristic. The Manhattan distance for (4 cast, A north) will be 8*D. However, we could simply move (4 northeast)

instead, so the heuristic should be 4*D. This function handles diagonals, assuming that

both straight and diagonal movement costs.D:

h{n) = D * max(abs(n.x-goal.x), abs(n.y-goal.y))

• If the cost of diagonal movement is not D, but something like D2 = sqrt(2)*D, the above heuristic won't he right for we. We will instead want something more sophisticated: hdiagonal(n) = min(abs(n.x-goal.x), abs(n.y-goal.y))

hstraight(n) = (abs{n.x-goal.x) + abi(n.y-goal.y))

= D2 * bdiagonalfn) + D * (hstraight(n) - 2*hdiagonaI(n)))

• Here we compute iidiagonal(n) ~ the number of steps we can take along a diagonal, hsi.nu'ght(n) = the Manhattan distance, and then combine the two by considering all diagonal sieps to cost D2, and then all remaining straight steps (note that this is the number of straight steps in the Manhattan distance, minus two straight steps for each diagonal step we took instead) cost D.

4.1.3 Euclidean Distance

If our units can move at any angle (instead of grid directions), then we should probably use a straight linij distance:

!i(n) = D * sqrt.ffn.x-goal.x)2 + (n.y - goaty)2)

However, if this is tiie case, then we may have trouble with using A* directly because the costs function g will not match the heuristic function h. Since Euclidean distance is shorter than Manhattan or diagonal distance, we will still get shortest paths, but A* will take longer to run.

5 Breaking Of Ties In Heuristics

One thing that can lead to poor performance is ties in the heuristic. When several paths have the same f value, they are all explored, even though we only need to explore one of them. To solve this problem, we can add a small fie breaker to the heuristic. The tie breaker needs to be deterministic with respect to the vertex (i.e., it can't just be a random number), and it needs to make the f values differ. Since A* sorts by f value, making them different means only one of the "equivalent" f values will be explored.

5.1 Methods To Break Ties 5.1.1 Method I

• OIK; way to break ties is to nudge the scale of h slightly. If we scale it downwards, then f will increase as we move towards the goal. Unfortunately, this means that A* will prefer to expand vertices close to the starting point instead of vertices close to the goal. We can instead scale h upwards slightly {even by 0.1

heuristic *= (1.0 -)- p)

• The factor p should be chosen so that p is less than {minimum cost of taking one step) / (expected maximum path length). Assuming that we don't expect the paths to be more than 1000 steps long, we can choose p — 1/1000. The result of this tie-breaking nudge is that A* explores far less of the map than previously:

• When there are obstacles of course it still has to explore to find a way around them, but when that after the obstacle is passed, A* explores very little. Tie-breaking scaling added to heuristic, works nicely with obstacles.

5.1.2 Method II

A different, way to break ties is to prefer paths that are along the straight line from the starting point to the goal:

• dxl — current.x - goal.x

• dyl — current.y - goal.y

• dx2 — start.x - goal.x

• dy2 — start.y - goal.y

• cross = abs(dxl*dy2 - dx2*dyl)

• heuristic +== cross*0.001

fins code computes the vector cross-product between the start to goal vector and the current point to goal vector. When these vectors don't line up, the cross product will be larger. The result is that this code will give some slight preference to a path that lies along the straight line path from the start to the goal. When there are no obstacles, A* not only explores less of the map, the path looks very nice as well:

6 Implementation Of The Algorithm

There are two sets, OPEN and CLOSED. The OPEN set contains those nodes that are candidates for examining. Initially, the OPEN set contains just one element: the starting position. The CLOSED set contains those nodes that have already been examined. Initially, the CLOSED set is empty. Graphically, the OPEN set is the "frontier" and the CLOSED

is l he "interior" of iiie visited areas. Each node also keeps a pointer to its parent, nodi; so l.lial- we can determine liow it was found.

The following important events occur in the algorithm:-

• There is a main loop that repeatedly pulls out the best node n in OPEN (the node with the lowest, f value) and examines it.

• If n is the goal, then we're done. Otherwise, node n is removed from OPEN and added to CLOSED. Then, its neighbors n' are examined. A neighbor that is in CLOSED lias already been seen, so we don't need to look at it.

• A neighbor that is in OPEN is scheduled to be looked at, so we don't need to look at it now (*). Otherwise, we add it to OPEN, with its parent set to n. The path cost to n', g(n'), will be set to g(n) + movement cost(n, n').

There are three main operations we perform on the OPEN set:

• The main loop repeatedly finds the best node and removes it;

• The neighbor visiting will check whether a node is in the set; and the neighbor visiting will insert new nodes.

• In terms of priority, we want to pick something that optimizes membership test, insertion, and then remove-best, in that order. Insertion and remove-best are operations typical of a priority queue.

• In addition, there's a fourth operation, which is relatively rare but still needs to be im¬plemented. If the node being examined is already in the OPEN set (which does happen frequently), and if its f value is better than the one already in the OPEN set (which is rare), then the value in the OPEN set must be adjusted. The adjustment operation in¬volves removing the node (which is not the best f) and re-inserting it. These two steps may be optimized into one that moves the no

7 Interaction Of A* Algorithm In Real Time Games

Interactive (especialiy real-time games) introduce requirements that affect our ability to com¬pute the best path. It may be more important to get any answer than to get the best answer. Still, all other things being equal, a shorter path is better than a longer one.

7.1 Need Of Speed Over Accuracy

In general, computing the part of the path close to the starting point is more important than the path close to the goal. The principle of immediate start: get the unit moving as soon as possible, even along a suboptimal path, and then compute a better path later. In real-time games, the latency of A* is often more important than its throughput.

It is possible to exit early from the A* main loop and get a partial path. Normally, the loop exits when it finds the goal node. However, at any point before that, it can return a path to the currently best node in OPEN. That node is our best chance of getting to the goal, so it's a reasonable place to go.

7.2 Dealing With Group Movement

Path requests do not arrive evenly distributed. A common situation in a real-time strategy game is for the player to select multiple units and order them to move to the'same goal. This puts a high load on the path finding system. In this situation, it is very likely that the path found for one will be useful for other units. Basically there are three different ways:-

• One idea is to find a path P from the center of the units to the center of the destinations. Then, use most or that path for all the units, but replace the first 10 steps and the last 10 steps by paths that are found for each individual unit. Unit i will receive a path from its starting location to P[10], followed by the shared path P[l0..1en(P)-10], followed by a path from P|len(P)-10| to the destination..'

• Another approach is to make the units aware of each other (perhaps by picking a "leader" unit randomly, or by picking the one with the best sense of what's going on), and only find a path for the leader. Then use a flocking algorithm to make them move in a group.

• Yet another approach is to take advantage of A*'s intermediate state. This state can be shared among multiple units traveling to the same goal, as long as those units share the same heuristic and cost functions. When the main loop exits, do not erase the OPEN and CLOSED sets.Instead, start the next loop (with the starting position of the next unit) with the OPEN and CLOSED sets from the previous invocation of A*.