Heuristics Search Technique to Find shortest distance between two cities.
A heuristic is an approximation technique, which is not guaranteed to be optimal in achieving a goal.Our problem statement is to find shortest distance between two cities by using heuristics search technique. I will use Python jupyter notebook to implement heuristic search technique to find shortest distance between two cities.
We shall well pick the neighbours, that might give us a shorter path to the target node in a graph.
How can I guess if a particular node might lead us to a shorter path?
In the case of the road network, we can assume that closer the junction we pick, faster it might get to the target city. For this, we can use the readily available GPS information to compute a not so elite, but a rough distance from the air between points. Although, it might not be correct, given you might see bends and roundabouts, we can be sure that the general direction of movement must be towards the target city.
Implementation A* in Python
Step-1 - Importing necessary libraries.
Matplotlib - For data visualizations
Collections - Dictionary in Python is an unordered collection of data values that are used to store data values like a map.
Networkx - Storing the graph structure.
Heapq - Heap data structure is mainly used to represent a priority queue.
Step-2 - I will create a wrapper class to contain vertices (nodes) of the graph so that I can use them right away in heapq implementation of python. I override the __lt__ function of the wrapper so that heapq will use its val attribute to heappush and heappop elements. This val corresponds to the distance to target node.
Step-3 - Code to trace the shortest path once the algorithm runs and I have parents of the vertices we traverse.
Implementation A* in Python
Step-4 - Implementing the Graph and Visualization Matrix. I will check algorithm runs in real-time. Imagine we have a 2D terrain and we want to get to top right corner from the bottom left corner. We have an obstacle on the way as shown in black.
Step-5 - I populate above terrain using code. It is a simple matrix of size 50x50. The image is a matrix with 3 channels for RGB. So the obstacles are simply indices with [0, 0, 0].
Step-6 - Creating the NetworkX Graph
Since graph operations are best performed on a graph like data structure with graph functionalities, I migrate my terrain to a graph. Each pixel will be a node/vertex in our graph. From each node/vertex I can traverse in all 8 directions similar to the queen on a chessboard. In my case edges exist, unless the available reversible neighbour is black.
Step-7 - Implementing the Algorithm with Checkpointing
Now that I have prepared my graph, I want to implement and run A-Star. At the same time, when the algorithm searches neighbours, I want to snapshot the initial 2D terrain for visualization later.
I use the Euclidean distance as the distance heuristic, which is the guess from any node to the target.
Step-8- I will run the algorithm using runner snippet. I use a copy of the matrix since within the algorithm I update the initial mat object.
Step -9 - Final Execution and Creating a GIF
The visibility will be more clear when I see how things happen in animation. So I will combine all my created images to form a GIF. I write code to create the GIF out of my snapshot images.
Pseudo Code:-
function AStar(start, end, heuristic=h)
open_set = {start}
closed_set = {}
# distance so far to node
distance = lookup_table(default=INFINITY)
# guess to the end
guess = lookup_table(default=INFINITY)
distance[start] = 0
guess[start] = h(start)
while open_set not empty
current = node with lowest guess from open_set
if current is goal: END
open_set.remove(current)
closed_set.add(current)
for neighbour of current
score = distance[current]+length(current,neighbour)
if score < guess[neighbour]
distance[neighbour] = score
parent[neighbour] = current
guess[neighbour] = distance[neighbour]+h(neighbour)
if neighbour not in closed_set
open_set.add(neighbour)
OutPut animation
import numpy as np import matplotlib.pyplot as plt # for visualizations import matplotlib.cm as cm # for visualizations from collections import defaultdict #Dictionary in Python is an unordered collection of data values that are used to store data values like a map. Unlike other Data Types that hold only single value as an element, the Dictionary holds key:value pair. import networkx as nx # storing the graph structure
import heapq # pythons heap implementation -Heap data structure is mainly used to represent a priority queue. In Python, it is available using “heapq” module. The property of this data structure in Python is that each time the smallest of heap element is popped(min heap). Whenever elements are pushed or popped, heap structure in maintained.
mat = np.zeros((50, 50, 3), dtype=np.float32)
g = nx.Graph()
for x in range(50):
for y in range(50):
mat[x, y, 0] = 0.95
mat[x, y, 1] = 0.95
mat[x, y, 2] = 0.95
g.add_node("{},{}".format(x,y), x=x, y=y)
# end
mat[49, 0, 0] = .0
mat[49, 0, 1] = .0
mat[49, 0, 2] = 0.8
# start
mat[0, 49, 0] = .0
mat[0, 49, 1] = 0.8
mat[0, 49, 2] = .0
for x in range(20, 50):
for y in range(20, 50):
if x>y+5:
mat[x, y, 0] = .0
mat[x, y, 1] = .0
mat[x, y, 2] = .0
for x in range(0, 30):
for y in range(0, 30):
if x<y-5:
mat[x, y, 0] = .0
mat[x, y, 1] = .0
mat[x, y, 2] = .0
for x in range(26, 30):
for y in range(10, 20):
mat[x, y, 0] = .0
mat[x, y, 1] = .0
mat[x, y, 2] = .0
def is_black(arr):
return sum(arr) == 0
for x in range(50):
for y in range(50):
xi = g.nodes["{},{}".format(x,y)]['x']
yi = g.nodes["{},{}".format(x,y)]['y']
for xj in range(xi-1, xi+2):
for yj in range(yi-1, yi+2):
if xi==xj and yi==yj or xj<0 or yj<0 or xj>49 or yj>49: continue
# if black not a neighbour
if is_black(mat[xi, yi]) or is_black(mat[xj, yj]): continue
g.add_edge("{},{}".format(xi,yi), "{},{}".format(xj,yj))
fig = plt.figure(figsize=(10, 10))
plt.imshow(mat)
mat_copy = np.copy(mat)
plt.axis('off')
class NodeWrap:
def __init__(self, nid, dist_to_end):
self.nid = nid
self.val = dist_to_end
def __lt__(self, other):
return self.val < other.val
def store_image(world, node, i):
global mat
x = world.nodes[node]['x']
y = world.nodes[node]['y']
mat[x, y, 0] = 1
mat[x, y, 1] = .5
mat[x, y, 2] = .0
fig = plt.figure(figsize=(10, 10))
plt.imshow(mat)
plt.axis('off')
plt.savefig("im-{}.png".format(i))
plt.close()
def trace_path(parent_map, end):
node = end
path = []
while (node in parent_map):
path.append(node)
node = parent_map[node]
return path[::-1]
def euclidean_dist(world, node1, node2):
x1 = world.nodes[node1]['x']
x2 = world.nodes[node2]['x']
y1 = world.nodes[node1]['y']
y2 = world.nodes[node2]['y']
return ((x1-x2)**2 + (y1-y2)**2)**.5
def a_star(world, start, end):
stepper = 1
open_set = []
close_set = set()
parent_map = {}
start_node = NodeWrap(start, 0)
heapq.heappush(open_set, start_node)
store_image(world, start, stepper)
stepper += 1
cost_to_reach_node = defaultdict(lambda: float('inf'))
cost_to_reach_node[start] = 0
guess_to_destination = defaultdict(lambda: float('inf'))
guess_to_destination[start] = euclidean_dist(world, start, end)
while len(open_set) > 0:
current = heapq.heappop(open_set)
if current.nid == end:
path = trace_path(parent_map, end)
return path
close_set.add(current.nid)
for neighbor in world.neighbors(current.nid):
tentative_score = cost_to_reach_node[current.nid] + euclidean_dist(world, current.nid, neighbor)
if tentative_score < cost_to_reach_node[neighbor]:
parent_map[neighbor] = current.nid
cost_to_reach_node[neighbor] = tentative_score
guess_to_destination[neighbor] = cost_to_reach_node[neighbor] + euclidean_dist(world, neighbor, end)
if neighbor not in close_set:
neighbor_node = NodeWrap(neighbor, euclidean_dist(world, neighbor, end))
heapq.heappush(open_set, neighbor_node)
store_image(world, neighbor, stepper)
stepper += 1
path = a_star(g, "49,0", "0,49") for node in path: x = g.nodes[node]['x'] y = g.nodes[node]['y'] mat_copy[x, y, 0] = 1 mat_copy[x, y, 1] = .5 mat_copy[x, y, 2] = .0 fig = plt.figure(figsize=(10, 10)) plt.imshow(mat_copy)
plt.axis('off')
import imageio
import glob
anim_file = 'out.gif'
with imageio.get_writer(anim_file, mode='I', fps=10) as writer:
filenames = glob.glob('im-*.png')
filenames = sorted(filenames, key=lambda x: int(x.replace("im-", "").replace(".png", "")))
last = -1
for i,filename in enumerate(filenames):
frame = 2*(i**0.5)
if round(frame) > round(last):
last = frame
else:
continue
image = imageio.imread(filename)
writer.append_data(image)
image = imageio.imread(filename)
writer.append_data(image)
image = imageio.imread(filename)
writer.append_data(image)
image = imageio.imread(filename)
writer.append_data(image)