TCP Dynamic Behavior

This post has been moved here.

Finally: informed search algorithms

Introduction

In this post we'll look at how to implement informed search, a.k.a. heuristic search. Heuristic search leverages knowledge of the problem space to speed up search, which is a very nice feature when search trees are very wide and/or deep. Previous knowledge of the problem space is modeled as a heuristic function, which is a function receiving a state as argument and returning a value representing how far the heuristic function thinks that state is from a goal state.

The effectiveness of a heuristic search algorithm when compared to an uninformed search counterpart depends heavily on the heuristic function's ability to provide accurate hints about how far from a goal the current node being examined is. Devising accurate heuristics is an art in itself, though there are automated methods that may help. We won't be discussing heuristic devising in this post, but you can find additional information in the AI book I've used as reference across the series.

Heuristic function characterization

So can we use any function taking a state as input and providing a numerical value as output as an effective heuristic? The obvious answer is no. In order to be effective with a search algorithm, a heuristic function h must fulfill a number of properties:

1. Returned value must be positive and not zero for all but the solution state, and must be 0 for the solution state;
2. The function must be admissible, i.e. it must always underestimate the actual cost of reaching a solution from any given state;
3. In addition to being admissible the function should be consistent, i.e. when evaluated for a state actually closer to a solution than a previous state it must return a value lower than that returned for said previous state (this condition is required only when checking for duplicates, which concerns us since if you check the treeSearchWithCost() method from the previous post you'll see that's always the case)

The above conditions are necessary for a heuristic search algorithm to be complete and optimal, though they are not sufficient, as we we'll see shortly.

It turns out that it is not very common to meet not consistent heuristics, specially with real-world problems like the one we used in the previous post. Let's continue using the same problem. A consistent heuristic for that problem is the straight line distance SLD between two towns. Since the straight line distance is the shortest possible distance between two points (in 3 dimensions, for the astro-physicists amongst you), it must be admissible. And applying the triangle inequality it can be seen that it is also consistent. We can model this heuristic function in our problem definition as follows:

sld_bucharest = {     "Arad": 366,     "Bucharest": 0,     "Craiova": 160,     "Drobeta": 242,     "Eforie": 161,     "Fagaras": 176,     "Giurgiu": 77,     "Hirsova": 151,     "Iasi": 226,     "Lugoj": 244,     "Mehadia": 241,     "Neamt": 234,     "Oradea": 380,     "Pitesti": 100,     "Rimnicu Vilcea": 193,     "Sibiu": 253,     "Timisoara": 329,     "Urcizeni": 80,     "Vaslui": 199,     "Zerind": 374, } h = lambda n: sld_bucharest[n]

Snippet 1 - Modeling the consistent SLD heuristic

We will be using the SLD heuristic with the algorithms that follow.

Greedy best-first search

The simplest form of heuristic search algorithm is called greedy best-first search. In this algorithm search always follows blindly the path with the lowest value of h.

Implementing greedy best-first search in our generic search framework is stupidly simple; we just have to apply breadth-first search sorting the fringe in order of increasing h. See the following code.

@staticmethod def greedyBestFirstGenerator ( successor, h ):     heuristicSuccessor = lambda n: sorted(successor(n), key=h)     return Problem.breadthFirstGenerator(heuristicSuccessor)

Snippet 2 - Greedy best-first search algorithm

We wrap the passed successor() function into a heuristicSuccessor() function that merely sorts the children returned according to their h values. At every level down the tree, the search algorithm expands states in increasing order of estimated cost to the goal state. The first solution found at a given level is therefore the shortest solution down to that level. I underline "down to that level" because, as you'll see if you examine carefully the Romania road map from the previous post, the first solution popping up on the fringe is not actually the shortest solution (we know from the previous post that the first solution pops up at level 4 while the best solution pops up at level 6).

Therefore, despite using a consistent heuristic function greedy best-first search is complete but not optimal.

Notice that greedy-best first search is not a cost-based search algorithm, thus it must be used with the initial, unmodified search algorithm from the first post:

problem.graphSearch(Problem.greedyBestFirstGenerator(successor, h)) self.assertTrue(problem.solved()) print ("Solution found using greedy-best-first search: ", str(problem.solution)) print("Algorithm performance: ", problem.performance)

Snippet 3 - Testing greedy best-first search

A* search

Let's move on to a heuristic search algorithm that is both complete and optimal, as long as the heuristic function is consistent. It is the "a star" algorithm, which uses as sorting function a combination of what we know and what we believe, i.e.: f(s) = c(s) + h(s), being c(s) the actual cost of reaching state s from the initial state and h(s) the estimated cost of reaching the goal state from state s.

The mathematical proof that using a consistent heuristic function h with A* makes it optimal and complete can be found in the book. It is a beautiful while easy to follow demonstration so I encourage you to check it out.

The generator that enables A* in our common search framework is as follows:

@staticmethod def aStarGenerator ( successor, cost, h ):     def nestedGenerator ( fringe ):         best_node = heapq.heappop(fringe)         descendants = successor(best_node.item()) or []         for desc in descendants:             if desc != best_node.parent():  # going back where we come from                 f = best_node.cost() + cost(desc, best_node.item()) + h(desc)                 heapq.heappush(fringe, Problem.Node((f, desc, best_node)))         yield fringe     return nestedGenerator

Snippet 4 - Generator implementing A* search

Once more we're using the Python heap functions to deal with ordering the states according to their respective f values. If you compare the A* generator with the uniform cost generator from the previous post, you'll see the only difference is in the line that calculates the value of f. I could actually have used the same generator code for both but I think it is not a good idea to mix both algorithms under the same signature.

To test the A* algorithm with our example problem:

problem.treeSearchWithCost(Problem.aStarGenerator(successor, cost, h)) self.assertTrue(problem.solved()) print ("Solution found using A*: " + str(problem.solution)) print("Algorithm performance: ", problem.performance)

Snippet 4 - Generator implementing A* search

Voilá! If you check the output of this test, you'll see this algorithm is the only one that has been able to find the optimum solution for driving from Arad to Bucharest. This confirms the A* algorithm is both complete and optimal. However, this comes at a cost. The algorithm performance, measured as the number of states expanded, is by large the worst one we've seen so far.

There are several variants of the A* algorithm that tackle its weaknesses in order to make better usage of the  computing resources made available to the algorithm execution. I recommend that you check out the book to  round up your knowledge of heuristic search.

And this is it, we're done! I hope you've enjoyed this series of posts as much as I enjoyed writing it. One last thing: if you decide to use the common search framework in your own project, please leave a comment or something so I know my work is being useful to someone else.

Thanks for reading and catch you all around!