Heuristics: A*-algorithm 2

Theory

The A*-Algorithm is an algorithm to find the shortest path between two nodes in a graph. It can be used for any problem wich can be modeled as a graph, e.g. the navigation of a car or computer-enemies in a video game and it is able to find the optimal solution if there is any. It utilizes a heuristical method to calculate the expected total cost through the problem space per node and by this the next node between root node (or start node) and target node (or leaf node) to have a look at.

It may be easier to understand the background of the algorithm if one is aware of the fact that the Dijkstra-Algorithm is a special case of the A*-Algorithm without a heuristic ($h(i)=0$).

How it works

Before you start you need the following

• Your problem space modelled as a graph. Every node i of the graph has the following attribtues:
  • g: the cost from root node of the graph to the the current node
  • h: the cost from the node i to the target node. If these costs are unknown an estimator h' is used as h (calculated by the heuristic, e.g. the euclidean distance or the length of the minimal spanning tree + the length of the shortest connection to the spanning tree)
  • f: g(i) + h(i)
  • parent node (root node has none)
• Also the following lists are neaded:
  • „OPEN list“
  • „CLOSED list“

Procedure

1. Put the start node on the OPEN list
2. If the OPEN list is empty then there is no result
3. Choose the node i with minimal f from the OPEN list. Delete i from the and put in on the CLOSED list
4. If i is a target node, A* ends successfully. To look up the optimal path one has to go from the target node back to the root node via the parent-attribute.
5. Otherwise, expand i. Create all successors of i with i as parent node. For each sucessor i':
   1. If i' is not yet given in the OPEN or CLOSED list, evalute $f(i')=g(i')+h(i')$. Add i' to the OPEN list.
   2. If i' is already given in the OPEN or CLOSED list, the pointer must be revised along the path, in order to get the minimum g(i')
   3. If i' is on the CLOSED list and the pointers were modified, reopen i', i.e. Remove it from the CLOSED list and put it back on the OPEN list.
6. Go back to (2)

Optimistic Heuristic

If your heuristical value for h' is always better than the real value h (h'(i) Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): \leq

h(i) for every i) (wich means your heuristic is optimistic) the A*-Algorithm found the best way through the problem-space as it will never overlook a better path throughout the search.

Example

Imagine a navigation device, just simpler: You have a two-dimensional grid (internal represented by a graph were every box is connected if there is no obstacle inbetween) and you want to know the shortest path between X (B2) (start) and Y (E7) (target). Cost for moving horicontally and vertically in this example are 10 and moving diagonal costs 14 (Pythagorean theorem). Between the start node and the target node are some obstacles placed (dark box).

As a heuristic the airline will be used with costs of 1 per box. This is quiet a bad estimator because the costs are so low they are nearly of no consequences, but besides that we get more iterations wich is a good thing in order to understand how A* works. If you want a good estimator choosing costs of 10 per box would be better!

g h' f parent obstacle

OPEN = {}

CLOSED = {}

1st Iteration

• Calculate g, h and f for the start node B2
  • g = 0 (there is no node before the start node, so the way from start to B2 is 0)
  • h = h' = 5 (B2 → C3 → D4 → E5 → E6 → E7)
  • f = g + h = 5
• Put the start node on the OPEN list: OPEN = {B2} | CLOSED = {}
• Choose the node i with minimal f from the OPEN list: i = B2
• Delete i from the and put in on the CLOSED list: OPEN = {} | CLOSED = {B2}
• 'Expand i. Create all successors of i with i as parent node. For each sucessor i':
  • A1,A2,A3,B1,B3,C1,C2,C3: If i' is not yet given in the OPEN or CLOSED list, evalute $f(i')=g(i')+h(i')$. Add i' to the OPEN list

OPEN = {A1,A2,A3,B1,B3,C1,C2,C3}

CLOSED = {B2}

2nd Iteration

• Choose the node i with minimal f from the OPEN list: i = B3
• Delete i from the and put in on the CLOSED list: OPEN = {A1,A2,A3,B1,C1,C2,C3} | CLOSED = {B2,B3}
• Expand i. Create all successors of i with i as parent node. For each sucessor i':
  • A4,B4,C4: If i' is not yet given in the OPEN or CLOSED list, evalute $f(i')=g(i')+h(i')$. Add i' to the OPEN list
  • Note: There is no need to change the path to A3/C3/A2/C2 as the way would be longer than now. For example [A2 → A3 → C3] has costs of 20 while they are at the moment 14, wich is better.

OPEN = {A1,A2,A3,A4,B1,B4,C1,C2,C3,C4}

CLOSED = {B2,B3}

3rd Iteration

i = C2

Note: As there is no connection between C2 and D3 in the graph based on the grid because D3 is a roadblock or something you can ignore D3.

OPEN = {A1,A2,A3,A4,B1,B4,C1,C3,C4,D1,D2}

CLOSED = {B2,B3,C2}

Iterations without Results

For every of the following nodes you may start an iteration without a change of the grid:

i = A1, A2, A3, B1, C1, C3

OPEN = {A4,B4,C4,D1,D2}

CLOSED = {A1,A2,A3,B1,B2,B3,C1,C2,C3}

4th Iteration

i = B4

OPEN = {A4,A5,C4,D1,D2}

CLOSED = {A1,A2,A3,B1,B2,B3,B4,C1,C2,C3}

5th Iteration

i = D2

OPEN = {A4,A5,C4,D1,E1,E2}

CLOSED = {A1,A2,A3,B1,B2,B3,B4,C1,C2,C3,D2}

Iterations without Results

i = A4,C4,D1

OPEN = {A5,E1,E2}

CLOSED = {A1,A2,A3,A4,B1,B2,B3,B4,C1,C2,C3,C4,D1,D2}

6th Iteration

i = E2

OPEN = {A5,E1,F1,F2,F3}

CLOSED = {A1,A2,A3,A4,B1,B2,B3,B4,C1,C2,C3,C4,D1,D2,E2}

7th Iteration

i = A5

OPEN = {A6,B6,E1,F1,F2,F3}

CLOSED = {A1,A2,A3,A4,A5,B1,B2,B3,B4,C1,C2,C3,C4,D1,D2,E2}

Iterations without Results

i = E1

OPEN = {A6,B6,F1,F2,F3}

CLOSED = {A1,A2,A3,A4,A5,B1,B2,B3,B4,C1,C2,C3,C4,D1,D2,E1,E2}

8th Iteration

i = F2

OPEN = {A6,B6,F1,F3,G1,G2,G3}

CLOSED = {A1,A2,A3,A4,A5,B1,B2,B3,B4,C1,C2,C3,C4,D1,D2,E1,E2,F2}

9th Iteration

i = A6

OPEN = {A7,B6,B7,F1,F3,G1,G2,G3}

CLOSED = {A1,A2,A3,A4,A5,A6,B1,B2,B3,B4,C1,C2,C3,C4,D1,D2,E1,E2,F2}

10th Iteration

i = F3

OPEN = {A7,B6,B7,E4,F1,F4,G1,G2,G3,G4}

CLOSED = {A1,A2,A3,A4,A5,A6,B1,B2,B3,B4,C1,C2,C3,C4,D1,D2,E1,E2,F2,F3}

Iterations without Results

i = F1

OPEN = {A7,B6,B7,E4,F4,G1,G2,G3,G4}

CLOSED = {A1,A2,A3,A4,A5,A6,B1,B2,B3,B4,C1,C2,C3,C4,D1,D2,E1,E2,F1,F2,F3}

11th Iteration

i = B6

OPEN = {A7,B7,C6,C7,E4,F4,G1,G2,G3,G4}

CLOSED = {A1,A2,A3,A4,A5,A6,B1,B2,B3,B4,B6,C1,C2,C3,C4,D1,D2,E1,E2,F1,F2,F3}

Iterations without Results

i = G2

OPEN = {A7,B7,C6,C7,E4,F4,G1,G3,G4}

CLOSED = {A1,A2,A3,A4,A5,A6,B1,B2,B3,B4,B6,C1,C2,C3,C4,D1,D2,E1,E2,F1,F2,F3,G2}

12th Iteration

i = F4

OPEN = {A7,B7,C6,C7,E4,E5,F5,G1,G3,G4,G5}

CLOSED = {A1,A2,A3,A4,A5,A6,B1,B2,B3,B4,B6,C1,C2,C3,C4,D1,D2,E1,E2,F1,F2,F3,F4,G2}

13th Iteration

i = A7

OPEN = {A8,B7,B8,C6,C7,E4,E5,F5,G1,G3,G4,G5}

CLOSED = {A1,A2,A3,A4,A5,A6,A7,B1,B2,B3,B4,B6,C1,C2,C3,C4,D1,D2,E1,E2,F1,F2,F3,F4,G2}

Iterations without Results

i = G3,G1

OPEN = {A8,B7,B8,C6,C7,E4,E5,F5,G4,G5}

CLOSED = {A1,A2,A3,A4,A5,A6,A7,B1,B2,B3,B4,B6,C1,C2,C3,C4,D1,D2,E1,E2,F1,F2,F3,F4,G1,G2,G3}

14th Iteration

i = C6

OPEN = {A8,B7,B8,C7,D6,E4,E5,F5,G4,G5}

CLOSED = {A1,A2,A3,A4,A5,A6,A7,B1,B2,B3,B4,B6,C1,C2,C3,C4,C6,D1,D2,E1,E2,F1,F2,F3,F4,G1,G2,G3}

15th Iteration

Note: A path wich only misses one step to the target was found, but the algorithm only stops when the target is i.

i = B7

OPEN = {A8,B7,B8,C7,C8,D6,E4,E5,F5,G4,G5}

CLOSED = {A1,A2,A3,A4,A5,A6,A7,B1,B2,B3,B4,B6,C1,C2,C3,C4,C6,D1,D2,E1,E2,F1,F2,F3,F4,G1,G2,G3}

Iterations without Results

i = E4,G4,B7

OPEN = {A8,B8,C7,C8,D6,E5,F5,G5}

CLOSED = {A1,A2,A3,A4,A5,A6,A7,B1,B2,B3,B4,B6,B7,C1,C2,C3,C4,C6,D1,D2,E1,E2,E4,F1,F2,F3,F4,G1,G2,G3,G4}

16th Iteration

i = B7

OPEN = {A8,B8,C8,D6,D8,E5,F5,G5}

CLOSED = {A1,A2,A3,A4,A5,A6,A7,B1,B2,B3,B4,B6,B7,C1,C2,C3,C4,C6,C7,D1,D2,E1,E2,E4,F1,F2,F3,F4,G1,G2,G3,G4}

17th Iteration

i = F5

OPEN = {A8,B8,C8,D6,D8,E5,E6,F6,G5,G6}

CLOSED = {A1,A2,A3,A4,A5,A6,A7,B1,B2,B3,B4,B6,B7,C1,C2,C3,C4,C6,C7,D1,D2,E1,E2,E4,F1,F2,F3,F4,F5,G1,G2,G3,G4}

Iterations without Results

i = A8

OPEN = {B8,C8,D6,D8,E5,E6,F6,G5,G6}

CLOSED = {A1,A2,A3,A4,A5,A6,A7,A8,B1,B2,B3,B4,B6,B7,C1,C2,C3,C4,C6,C7,D1,D2,E1,E2,E4,F1,F2,F3,F4,F5,G1,G2,G3,G4}

18th Iteration

i = D6

OPEN = {B8,C8,D8,E5,E6,E7,F6,G5,G6}

CLOSED = {A1,A2,A3,A4,A5,A6,A7,A8,B1,B2,B3,B4,B6,B7,C1,C2,C3,C4,C6,C7,D1,D2,D6,E1,E2,E4,F1,F2,F3,F4,F5,G1,G2,G3,G4}

Iterations without Results

i = E5,G5,B8,C8

OPEN = {D8,E6,E7,F6,G6}

CLOSED = {A1,A2,A3,A4,A5,A6,A7,A8,B1,B2,B3,B4,B6,B7,B8,C1,C2,C3,C4,C6,C7,C8,D1,D2,D6,E1,E2,E4,E5,F1,F2,F3,F4,F5,G1,G2,G3,G4,G5}

19th Iteration

i = F6

OPEN = {D8,E6,E7,F7,G6}

CLOSED = {A1,A2,A3,A4,A5,A6,A7,A8,B1,B2,B3,B4,B6,B7,B8,C1,C2,C3,C4,C6,C7,C8,D1,D2,D6,E1,E2,E4,E5,F1,F2,F3,F4,F5,F6,G1,G2,G3,G4,G5}

20th Iteration

i = F6

OPEN = {E6,E7,F7,G6}

CLOSED = {A1,A2,A3,A4,A5,A6,A7,A8,B1,B2,B3,B4,B6,B7,B8,C1,C2,C3,C4,C6,C7,C8,D1,D2,D6,D8,E1,E2,E4,E5,F1,F2,F3,F4,F5,F6,G1,G2,G3,G4,G5}

Iterations without Results

i = E6

OPEN = {E7,F7,G6}

CLOSED = {A1,A2,A3,A4,A5,A6,A7,A8,B1,B2,B3,B4,B6,B7,B8,C1,C2,C3,C4,C6,C7,C8,D1,D2,D6,D8,E1,E2,E4,E5,E6,F1,F2,F3,F4,F5,F6,G1,G2,G3,G4,G5}

21th Iteration

i = G6

OPEN = {E7,F7}

CLOSED = {A1,A2,A3,A4,A5,A6,A7,A8,B1,B2,B3,B4,B6,B7,B8,C1,C2,C3,C4,C6,C7,C8,D1,D2,D6,D8,E1,E2,E4,E5,E6,F1,F2,F3,F4,F5,F6,G1,G2,G3,G4,G5,G6}

22th Iteration

i = E7

• This is the target node, so A* ends successfully.
• To recover the path we start at the target node and go from there to every parent node on our path until there is none (wich means we are at the start node):
• E7 → D6 → C6 → B6 → A5 → B4 → B3 → B2
• Total cost is g(target node) = 82

Sources for further study

1. OR-Script 2013 (Heuristics.26 ff)

2. Wikipedia (En): A*-Algorithmus: http://en.wikipedia.org/wiki/A*_search_algorithm