A* Algorithm for
Dynamic Graphs
on GPU
- Lokesh Koshale
What is
A* Algorithm ?
A* Algorithm
- A* is one of the widely used path planning algorithms applied in a diverse set of problems in robotics and video games.
- It was developed by Peter Hart, Nils Nilsson and Bertram Raphael in 1968.
- It can be seen as an extension of Dijkstra's algorithm. A* achieves better performance by using heuristics to guide its search.
Example Graph
h(x) : heuristic value
Each Node has :
( euclidean distance )
10
8
0
6
2
9
7
3
2
2
B
D
H
E
I
G
C
A
J
1
4
Each Edge has positive weight
g(x) : Cost of reaching node x
from source
f(x) = g(x) + h(x)
Approximate cost of reaching destination from source via node x.
A* Algorithm
s = start_node
e = end_node
open_list = { s }
closed_list = { }
g(s) = 0
h(s) = heuristic_function(s,e)
f(s) = g(s) + h(s)
while open_list is not empty:
m = node in open_list with least f
if m == e:
return
remove m from open_list
add m to closed_list
for each n in child(m):
cost = g(m) + distance(m,n)
if n in open_list and cost < g(n):
remove n from open_list
if n in closed_list and cost < g(n):
remove n from closed_list
if n in open_list and n not in closed_list:
g(n) = cost
h(n) = heuristic_function(n, end)
f(n) = g(n) + h(n)
add n to open_list
return failure...
10
10
8
0
6
2
9
7
3
2
2
2
8
10
Open List :
A* Algorithm
while open_list is not empty:
m = node in open_list with least f
if m == e:
return
remove m from open_list
add m to closed_list
for each n in child(m):
cost = g(m) + distance(m,n)
if n in open_list and cost < g(n):
remove n from open_list
if n in closed_list and cost < g(n):
remove n from closed_list
if n in open_list and n not in closed_list:
g(n) = cost
h(n) = heuristic_function(n, end)
f(n) = g(n) + h(n)
add n to open_list
return failure...
10
8
0
6
2
9
7
3
2
2
2
8
10
Open List :
A* Algorithm
while open_list is not empty:
m = node in open_list with least f
if m == e:
return
remove m from open_list
add m to closed_list
for each n in child(m):
cost = g(m) + distance(m,n)
if n in open_list and cost < g(n):
remove n from open_list
if n in closed_list and cost < g(n):
remove n from closed_list
if n in open_list and n not in closed_list:
g(n) = cost
h(n) = heuristic_function(n, end)
f(n) = g(n) + h(n)
add n to open_list
return failure...
10
8
0
6
2
9
7
3
2
2
2
8
10
9
10
17
Open List :
9
10
17
A* Algorithm
while open_list is not empty:
m = node in open_list with least f
if m == e:
return
remove m from open_list
add m to closed_list
for each n in child(m):
cost = g(m) + distance(m,n)
if n in open_list and cost < g(n):
remove n from open_list
if n in closed_list and cost < g(n):
remove n from closed_list
if n in open_list and n not in closed_list:
g(n) = cost
h(n) = heuristic_function(n, end)
f(n) = g(n) + h(n)
add n to open_list
return failure...
10
8
0
6
2
9
7
3
2
2
2
8
10
9
10
17
Open List :
10
17
6
11
11
A* Algorithm
while open_list is not empty:
m = node in open_list with least f
if m == e:
return
remove m from open_list
add m to closed_list
for each n in child(m):
cost = g(m) + distance(m,n)
if n in open_list and cost < g(n):
remove n from open_list
if n in closed_list and cost < g(n):
remove n from closed_list
if n in open_list and n not in closed_list:
g(n) = cost
h(n) = heuristic_function(n, end)
f(n) = g(n) + h(n)
add n to open_list
return failure...
10
8
0
6
2
9
7
3
2
2
2
8
10
9
10
17
Open List :
9
11
6
4
9
17
A* Algorithm
while open_list is not empty:
m = node in open_list with least f
if m == e:
return
remove m from open_list
add m to closed_list
for each n in child(m):
cost = g(m) + distance(m,n)
if n in open_list and cost < g(n):
remove n from open_list
if n in closed_list and cost < g(n):
remove n from closed_list
if n in open_list and n not in closed_list:
g(n) = cost
h(n) = heuristic_function(n, end)
f(n) = g(n) + h(n)
add n to open_list
return failure...
10
8
0
6
2
9
7
3
2
2
2
8
10
9
10
17
Open List :
12
6
4
9
6
12
17
Dijkstra's Algorithm
A* Algorithm
Robot Motion Planning
Property of A* search
Lemma 1: If we have found a node d which has cost f_d then all the nodes i ∈ V which have cost f_i < f_d are already visited(expanded).
Intuition: We always pick lowest cost node from priority queue.
Parallel A* Algorithm on GPU
A* Algorithm on GPU
-
Proposed in paper “Massively Parallel A* Search on a GPU” by Yichao Zhou and Jianyang Zeng, 2015.
-
Instead of just using one single priority queue for the open list, allocate a multiple priority queues queues for A* search.
- Extract k-nodes in parallel from the k-priority queues, and in parallel compute the cost for their children.
...
10
8
0
6
2
9
7
3
2
2
2
8
10
9
10
17
Priority Queue:
9
10
17
In next step node with cost 9 will be extracted from priority queue and its children cost will be calculated.
A* Algorithm ( Sequential)
Bottleneck : Sequential nature of PQ.
...
10
8
0
6
2
9
7
3
2
2
2
8
10
9
10
17
9
10
17
Parallel A* Algorithm
...
...
PQ1
PQ2
PQ3
As number of parallel priority queue increases, execution time decreases
Dynamic Graphs
Dynamic Graphs
Graphs that are subject to an Update operation.
Insert (u, v)
Delete (u, v)
Typical Updates:
Partially dynamic problems: Graphs subject to insertions only, or deletions only, but not both.
Fully dynamic problems: Graphs subject to intermixed sequences of insertions and deletions
Insertion of Edges
Partially Dynamic: Insertions only
In the incremental setting, there are only edge-insertions, i.e. edge u → v is added in G where u ∈ V and v ∈ V.
Lemma 2: Insertion of an edge can not increase the cost of source to destination Optimal Path.
B
D
H
E
I
G
C
A
J
Inserted edges: C → G
D → G
Intitution: Optimal Path is the lowest cost path.
Lemma 3: If we add an edge u → v and
f (u) > f(destination) then addition of this edge will not affect the Optimal Path. *
*For all such graphs where h(x) is constant, i.e Euclidean distance
Processing Insertions
for each edges(u,v) inserted:
lock(v)
if f_new(v) < f_old(v):
add node v to update_list
unlock(v)
while update_list is not empty:
extract node n from update_list
for each child of n:
lock(child)
if f_new(child) < f_old(child):
add child to update_list
unlock(child)
10
8
0
6
2
9
3
2
2
2
8
10
9
10
17
6
4
9
6
12
5
2
?
Multiple Threads trying to update cost of single node, therefore we require synchronization.
Processing Insertions
for each edges(u,v) inserted:
lock(v)
if f_new(v) < f_old(v):
add node v to update_list
unlock(v)
while update_list is not empty:
extract node n from update_list
for each child of n:
lock(child)
if f_new(child) < f_old(child):
add child to update_list
unlock(child)
10
8
0
6
2
9
3
2
2
2
8
10
9
10
17
6
4
9
6
12
5
2
9
Propagate updated cost to all affected nodes
3
10
of Edges
Deletion
Partially Dynamic: Deletions only
In Decremental setting there are only removal of edges u → v where u ∈ V and v ∈ V.
Lemma 4: Deletion of edge u → v where u ∈ V and v ∈ V can not decrease f (v).
Lemma 6: If edge(u,v) is deleted and
optimal_parent(v) ≠ u, then deletion of such edges doesn’t affect the Optimal Path.
B
D
H
E
I
G
C
A
J
Deleted Edges: A → C
optimal_parent(v): neighbor of node v from which its f is calculated.
for each deleted edge(u,v):
if f(v) != INFINITY and optimal_parent(v)==u:
compute f(v) from all of its parents
chose the least one as optimal_parent(v)
update f(v)
if v doesn’t have any parent then f (v) == INFINITY:
add v to update_list.
while update_list is not empty:
extract node n from update_list.
for each child of n such that optimal_parent(child)==n:
if f_old(child) > f_new(child):
compute f(child) from all parents of child node
chose the least one as optimal_parent
add child to update_list.10
8
0
6
2
9
3
2
2
2
8
10
9
10
17
6
4
9
6
5
2
9
3
10
12
Processing Deletions
for each deleted edge(u,v):
if f(v) != INFINITY and optimal_parent(v)==u:
compute f(v) from all of its parents
chose the least one as optimal_parent(v)
update f(v)
if v doesn’t have any parent then f (v) == INFINITY:
add v to update_list.
while update_list is not empty:
extract node n from update_list.
for each child of n such that optimal_parent(child)==n:
if f_old(child) > f_new(child):
compute f(child) from all parents of child node
chose the least one as optimal_parent
add child to update_list.10
8
0
6
2
9
3
2
2
2
8
10
9
10
17
6
4
9
6
2
3
10
12
13
12
Processing Deletions
for each deleted edge(u,v):
if f(v) != INFINITY and optimal_parent(v)==u:
compute f(v) from all of its parents
chose the least one as optimal_parent(v)
update f(v)
if v doesn’t have any parent then f (v) == INFINITY:
add v to update_list.
while update_list is not empty:
extract node n from update_list.
for each child of n such that optimal_parent(child)==n:
if f_old(child) > f_new(child):
compute f(child) from all parents of child node
chose the least one as optimal_parent
add child to update_list.10
8
0
6
2
9
3
2
2
2
8
10
9
10
17
6
4
9
6
2
3
12
12
Processing Deletions
Deletion and Cycles
Infinite propagation due to a cycle in the graph
S
A
B
C
E
D
4
2
5
10
8
S
A
B
C
E
D
4
2
5
10
8
4
S
A
B
C
E
D
4
2
5
10
8
Deletion and Cycles
Propagation of deletion never halts, as given in the example. It’s because we chose the wrong optimal_parent(B) = E, as node B
itself is an optimal_ancesstor of E. So cost
of the node E is calculated based on the cost of node B.
Solution: each time we chose the optimal
parent for a node, we check if the cost of that
parent is not calculated from the node or not
4
S
A
B
C
E
D
4
2
5
10
8
S
A
B
C
I
G
H
E
F
D
5
6
2
6
10
2
5
10
6
2
5
2
Parallel Deletion and Cycle
-
Edges A→C and B→G are deleted.
- When node C performs cycle check for its only parent node I, it reads I→H→G→B→S, as node G's deletion process is executing in parallel, so it reads stale value and sets node I as its optimal_parent.
- Similarly node G sets node F as its optimal_parent.
-
Node C, G are added in update list.
Parallel Deletion and Cycle
S
A
B
C
I
G
H
E
F
D
6
2
6
10
2
5
10
6
2
2
- When try to get path from node D→S, we get stuck at optimal_parents cycle, and node D has wrong cost value.
- Similarly node G sets node H as its optimal_parent.
Propagation of Deletions
Lemma 8: At the end of propagation for deletion all node n ∈ V such that f_new(n) ≠ ∞ has the latest f(n) which is optimal cost in new graph including deletions.
Lemma 9: At the end of propagation f(destination) might not be the optimal cost of reaching destination from source in new graph.
open_list = {B,C}
closed_list= {S,A,D}
f(E) = ∞
Deleted edge S → D.
after propagation f(D) = ∞
but optimal path exists which is:
S→A→C→E→D
Require A* from last saved state,if there exist node with cost less than destination in PQ.
S
A
B
C
E
D
2
6
5
6
8
3
Fully
Dynamic
Fully Dynamic : Separate Propagation
-
Real-world graphs are dynamic and edges are changing continuously so there are insertions of edges and deletions of edges at the same time
-
Separate Propagation:
- Propagate for Insertion of edges.
- Propagate for deletion of edges.
- Do A* if necessary
-
We can infer the dynamic change in edges at a single instance as addition happening first then deletion or vice versa
Fully Dynamic : Simulatneous Propagation
while update_list not empty:
extract node n from update list.
for each child of n:
if f(child) decreases:
update f(child) and make n optimal_parent
add child to update list
if f(child) increases and n is optimal_parent(child):
choose the best optimal_parent from all parents of child
add child to update list.- Consider insertion and deletion of an edge as an update
- Added necessary checks for cycles and infinite propagation
Experimental
Results
Insertion:
Deletion:
Deletion is computationally costlier than insertions due to the cycle checks.
Initially static A* performs better but as the number of time the graph is subjected to updates increases Dynamic A* performs better.
Results on SNAP dataset
Table: Compares execution time of Static A* with Dynamic A* for various temporal graph (Time in seconds)
| Graph | N | E | Queries | DGA* | multi GA* | Speedup |
|---|---|---|---|---|---|---|
| live-journal | 3,997,962 | 34,681,189 | 10 | 6.01 | 33.93 | 5x |
| wiki-talk | 1,140,149 | 7,833,140 | 10 | 12.24 | 24.84 | 2x |
| ask-Ubuntu | 159,316 | 964,437 | 10 | 0.25 | 1.31 | 5x |
| Youtube | 1,157,828 | 2,987,624 | 10 | 0.81 | 5.78 | 7x |
| math-overflow | 24,818 | 506,550 | 10 | 0.09 | 0.067 | 7x |
| superuser | 194,085 | 1,443,339 | 10 | 0.41 | 2.89 | 7x |
| live-journal | 3,997,962 | 34,681,189 | 10 | 11.41 | 424.06 | 37x |
Applications
Wireless Sensor Networks
- In Wireless Sensor Network, light-weight, low power and small size sensor nodes are used which are operated by a small battery.
- Sensors nodes are used for monitoring physical phenomena like temperature, humidity, vibrations and so on
- A* is used in many such energy efficient algorithm one of such is Energy efficient routing protocol ( EERP)
- Sensors nodes are used for monitoring physical phenomena like temperature, humidity, vibrations and so on
Replacing multiple static A* to dynamic A* gives 35x speedup
Maze Solver
- A maze can be defined as a network of path in which one has to find a way out of the maze.
- In a maze where obstacle and edges can change with time is refered as dynamic maze.
- Tremaux’s algorithm, Maze-routing algorithm, BFS, DFS, and A* al-gorithm are well-known maze solver algorithms.
- To find the shortest path in a dynamic maze, we have applied the proposed algorithm.
Maze Solver
We achieved 10x speedup by applying the proposed algorithm
Path Planning for AGV
- AGV is a robot that follows previously defined paths using wire or magnetic strips and they use sensors to navigate in the known environment.
- Chunbao Wang and Lin Wang et al. have proposed shortest time planing algorithm which utilizes the K-shortest path obtained from running the A-Star algorithm
- AGV has become an integral part of the global supply chain and logistic system. It reduces labour cost, improves working condition and unifies the logistic information flow.
K-Shortest Path Problem
path_library = []
path = []
number_pq = set_number_of_threads()
#in Parallel
GPU_A*(source, sink, number_pq, path)
# for path of size n, delete edge(path[n-1],path[n])
remove_edge(Graph,path)
path_library.insert(path)
for i in range(1,K):
#in parallel
propagate_deletions(deleted_edges,N,E)
remove_edge(Graph,path)
path_library.insert(path)Find K number of shortest path from source to destination.
To find K-shortest path from source to destination authors have proposed to delete the last edge of the optimal path and re-run the A* algorithm from start, K times.
Instead of re-executing A* from source, we have used propagation for deletion to find the next optimal path
K-Shortest Path Problem
Replacing K-times A* algorithm with propagation gave 10x speedup
Heuristics
Heuristics
The heuristic function also plays a key role in determining the correctness and admissibility of the algorithm.
There can be four possible scenarios with heuristics function h :
- If h(x) = 0, then A* turns into in Dijkstra’s Algorithm
- If h(x) ≤ cost of reaching destination from x, we are guaranteed to find the shortest path but it will be slower.
- If h(x) = cost of reaching destination from x, we will follow only the best path.
- If h(x) is sometimes greater than cost of reaching destination from x, A* algorithm is not guaranteed to find the shortest path
Types of Heuristics
For dynamic graphs heuristics can be divided into two categories:
- h is independent of the addition and deletion of edges and may depend on some other attribute of the node. ex: latitude and longitude coordinates for computing the distances.
- h is dependent on the edges of the graph and thus adding and deleting edges will also change the h. ex: BFS distance from the destination
Updating the Heuristics
Deletion of Edges :
Deletion of edges doesn't affect the correctness and admissibility of the heuristics
S
A
B
C
D
E
2
6
5
6
8
3
0
1
2
1
3
2
In the example graph heuristic is BFS distance from destination node (D) and edge E->D is deleted. The heuristic value of node E and S changes to 4 and 1 respectively.
3
4
As deletion of edges cause increase in heuristic values, thus old values are an underestimate of actual cost. So it only affects the performance not the correctness of the algorithm.
Updating the Heuristics
Insertion of Edges:
S
A
B
C
D
E
2
6
5
6
3
0
1
2
4
3
3
11
Insertion of edges might decrease the heuristic values, thus old values are an overestimate of the actual cost and overestimate can lead to incorrect results. Thus there is need to update the heuristic values.
In the example graph edge S->D is inserted.
Without updating heuristic value of node S, A* algorithm returns the path S->A->C->D, which is not optimal.
1
So for Insertion we propagate the new heuristic value of affected nodes towards the source.
Updating the Heuristics
Trade-off between performance and accuracy
Thank You
And special thanks to prof. Rupesh Nasre for his invaluable guidance throughout this project.