In the Revisiting the navigation application section, you learned that a heuristic value is a property of the node, and it is a guess, or estimate, of which node will lead to the goal state quicker than others. It is a strategy used to reduce the nodes explored and reach the goal state quicker. In greedy BFS, the heuristic function computes an estimated cost to reach the goal state. For our application, the heuristic function can compute the straight-line distance to the goal state, as follows:
As you can see, in the preceding diagram the initial state is the Bus Stop. From the Bus Stop node, we have one channel, which is the Library node. Let's suppose that we're at the Library now; from the Library node, there are three child nodes: the Car Park, the Bus Stop, and the Student Center. In real life, we'd prefer to go to the Car Park, because it seems closer to the goal state, and the chances that we will reach the AI Lab faster are much higher:
...
#connections between places
connections = {}
connections["Bus Stop"] = {"Library"}
connections["Library"] = {"Bus Stop", "Car Park", "Student Center"}
connections["Car Park"] = {"Library", "Maths Building", "Store"}
connections["Maths Building"] = {"Car Park", "Canteen"}
connections["Student Center"] = {"Library", "Store" , "Theater"}
...
Let's use the location data of these four places (Library, Car Park, Bus Stop, and Student Center) to compute the heuristic functions for the three nodes. When you compute the heuristic functions for these three nodes, you will find that the value for Car Park is 6.4, Bus Stop is 8.9, and Student Center is 8.0. According to these heuristic values, we will select the first value in the fringe, which is the node with the lowest heuristic value (Car Park):
...
def computeHeuristic(self):
"""
This function computes the heuristic value of node
"""
#find the distance of this state to goal state
#goal location
goalLocation = location["AI Lab"]
#current location
currentLocation = location[self.state.place]
#difference in x coordinates
dx = goalLocation[0] - currentLocation[0]
#difference in y coordinates
dy = goalLocation[1] - currentLocation[1]
#distance
distance = math.sqrt(dx ** 2 + dy ** 2)
print "heuristic for", self.state.place, "=", distance
self.heuristic = distance
...
Let's take a look at the preceding computeHeuristic function. The Node class has a method called computeHeuristic. This function computes the heuristic value of the node by finding the distance from this state to the goal state. You can find the goal location by using the location dictionary of the navigation data and using the AI Lab as the key. You can find the current location by using the location dictionary, with the current place as the key. We find the difference in the x coordinates as follows: dx = goalLocation[0] - currentLocation[0]. We find the difference in the y coordinates as follows: dy = goalLocation[1] - currentLocation[1]. Finally, we compute the distance as the square root of dx square plus dy square, and we assign this distance to the heuristic property of the Node class:
Now that you understand this heuristic function, let's look at the flow of the greedy BFS algorithm. The flow of this algorithm is similar to BFS. Instead of using a queue, we are going to use a priority queue, and we are going to compute the heuristic of the node and add the node, along with the heuristic value, to the priority queue:
- We initially create the root node and add it to the tree, and then add this node, along with its heuristic value, to the priority queue.
- We get the front node from the priority queue, and we check if it has goal state. If it does, we end our search here, and if it doesn't have the goal state, then we find its child nodes, add them to the tree, and then add them to the priority queue, along with a heuristic value.
- We carry on with this process until we find the goal state or we've exhausted all of the nodes in our search stream.
Let's try to code the greedy BFS algorithm as follows:
...
def performGreedySearch():
"""
This method performs greedy best first search
"""
#create queue
pqueue = Queue.PriorityQueue()
#create root node
initialState = State()
#parent node of root is None
root = Node(initialState, None)
#show the search tree explored so far
treeplot = TreePlot()
treeplot.generateDiagram(root, root)
#add to priority queue
pqueue.put((root.heuristic, root))
while not pqueue.empty():
#get front node from the priority queue
_, currentNode = pqueue.get()
#remove from the fringe
#currently selected for exploration
currentNode.fringe = False
print "-- current --", currentNode.state.place
...
In the Python GreedySearch.py module, we have created a performGreedySearch() method, which will perform the greedy BFS. In this method, we have created an empty priority queue for holding the nodes. With initialState, we are creating a root node, and, as mentioned earlier, the constructive node has changed; there is an additional argument in the parent node. For the root node, the parent node is None.
We are creating a TreePlot object and calling its generateDiagram() method to visualize the current search tree. In this case, the search tree will only contain the root node. We're adding the root node, along with its heuristic value, to the priority queue. We check whether the priority queue is not empty; if it is not empty, we get the front element and call it currentNode. As mentioned earlier, the format of the priority queue is a tuple containing the heuristic value and the node. Since we only want the node, we'll ignore the heuristic value. We will set the fringe property of currentNode to False, because it's currently selected for exploration:
...
#check if this is goal state
if currentNode.state.checkGoalState():
print "reached goal state"
#print the path
print "----------------------"
print "Path"
currentNode.printPath()
#show the search tree explored so far
treeplot = TreePlot()
treeplot.generateDiagram(root, currentNode)
break
#get the child nodes
childStates = currentNode.state.successorFunction()
for childState in childStates:
#create node
#and add to tree
childNode = Node(State(childState), currentNode)
#add to priority queue
pqueue.put((childNode.heuristic, childNode))
#show the search tree explored so far
treeplot = TreePlot()
treeplot.generateDiagram(root, currentNode)
...
We check whether the current node has the goal state; if it has the goal state, we print the path from the initial state to the goal state. We show the current search tree by calling the treeplot.generateDiagram method. If it doesn't have the goal state, we find the child states of the current node, and for each childState, we create the childNode by using the new constructor. In this new constructor, we pass the parent node as the currentNode, and we add the child node, along with its heuristic value, to the priority queue; we then display the current search tree.
So, we actually display the search tree at each step, whenever one level of the search tree is added. In this case, the search tree contains the root node. When one level of the search tree is added, we display the search tree; finally, when we reach the goal state, we prepare and then display the search tree that has been explored:
As you can see in the preceding output, we have a root node with the heuristic value 8.9 in our search tree. The Bus Stop node has been selected for exploration, and its child node library has been added to the search tree. The heuristic value of Library is 8.2, which is lower than the heuristic value of Bus Stop, which is 8.9. Since this is the only node in the fringe, it will be selected for exploration later:
As shown in the preceding diagram, Library has been selected for exploration, and the child nodes of the Library node are added. We can see that for the three child nodes in the fringe, Bus Stop has a heuristic value of 8.9, Car Park has a heuristic value of 6.4, and Student Center has a heuristic value of 8.0. Out of the three nodes, Car Park has the lowest heuristic value, so this will be selected for exploration:
Now, Car Park has been selected for exploration, and its child nodes are added to the priority queue. Here, we have five nodes in the fringe. Bus Stop has a heuristic value of 8.9, the Maths Building has a heuristic value of 2.2, Library has a value of 8.2, Store has a value of 4, and Student Center has a value of 8.0. Of these five nodes, Maths Building has the lowest heuristic value (2.2), so it will be selected for exploration:
Now, Maths Building has been selected for exploration, and its child nodes are added to the search tree. Of the nodes in the fringe, Canteen has the lowest heuristic value (1.0), so it will be selected for exploration:
Now, the Canteen node has been selected for exploration, and its child nodes are added to the search tree and to the fringe. Out of all of the blue nodes, AI Lab has the lowest heuristic value (0.0), so it will be selected for exploration:
Finally, the AI Lab is selected for processing, and we find that we've reached the goal state, so we end our search here. The optimal path is shown by the green nodes and by the red node. The optimal path is Bus Stop, Library, Car Park, Maths Building, Canteen, and AI Lab.
As we go from the initial state to the goal state, we can observe that the heuristic values reduce. Bus Stop has the value 8.9, Library has the value 8.2, Car Park has the value 6.4, Maths Building has the value 2.2, Canteen has the value 1, and AI Lab has the value 0. This means that as we traverse the search tree, we are getting closer to the goal state. In the greedy BFS algorithm, the heuristic value reduces as we progress toward the goal state.
Now that you have learned the heuristic function for the greedy BFS algorithm, in the next section you will learn the problems with the greedy BFS algorithm, and you will see how A* Search solves those problems.