Introduction
If you've followed closely the previous posts, you might be wondering what the
cost formal argument in the generators' signatures is for. We've been consistently passing a constant lambda function as actual argument, and the code doesn't seem to be using it at all. Well, the time has come for providing an explanation: there's a kind of uninformed search algorithms that try to improve search time and/or space by filtering out nodes based on the actual cost of reaching a node. These algorithms are useful when the problem space allows allocating a numeric cost to the action of moving from a parent node to a child node. So far we haven't met such a problem space, hence we've been using a constant function (known as
unitary cost function).
A problem space that lends easily to cost-based search is that of finding the shortest path by car between two towns. Here the cost function is the driving distance between two cities connected by a road. If we map nodes to cities and paths to roads, we might use a cost-based search algorithm to try to find the optimum way of driving from city A to city B.
Let's define such a problem space to use it with our search algorithms. We'll use Romanian towns and roads to honor the
AI book all these posts are based on. Graphically the map looks as in the following figure (ignore the figure within braces inside each state, we'll see what's that about in the next post):
Figure 1 - Romania road map with driving distance between cities
We can model that map easily using a Python dictionary:
distance = {
("Oradea","Zerind"): 71,
("Oradea","Sibiu"): 151,
("Neamt","Iasi"): 87,
("Zerind","Arad"): 75,
("Iasi","Vaslui"): 92,
("Arad","Sibiu"): 140,
("Arad","Timisoara"): 118,
("Sibiu","Fagaras"): 99,
("Sibiu","Rimnicu Vilcea"): 80,
("Fagaras","Bucharest"): 211,
("Vaslui","Urziceni"): 142,
("Rimnicu Vilcea","Pitesti"): 97,
("Rimnicu Vilcea","Craiova"): 146,
("Timisoara","Lugoj"): 111,
("Lugoj","Mehadia"): 70,
("Pitesti","Bucharest"): 101,
("Pitesti","Craiova"): 138,
("Hirsova","Urziceni"): 98,
("Hirsova","Eforie"): 86,
("Urcizeni","Bucharest"): 85,
("Mehadia","Drobeta"): 75,
("Bucharest","Giurgiu"): 90,
("Drobeta","Craiova"): 120,
} |
Instead of defining classes to model a graph or using a data structures library, we're defining the problem space as a simple dictionary mapping pairs of towns to the driving distance between them. Pairs not present in the dictionary do not have a road connecting them.
Now let's define a cost function that uses the above problem space knowledge to measure the cost of driving from town A to town B, as long as A and B are connected by a single road segment (i.e. no intermediate towns need to be traversed) :
cost = lambda s, n: distance.get((s,n), distance.get((n,s))) or (s==n and 0) |
We're using the get() method of the dict class instead of direct subscripting, like in 'distance[("A","B")]'. The reason is that subscripting raises an exception if the index is not found in the dictionary, whereas get() gives us the chance of providing an additional argument that shall be used if the index is not found. In addition get() doesn't raise an exception if the search fails, but just returns None. That semantic allows us to condense the dictionary access code in a convenient single lambda function. Notice the driving distance between town A and itself is 0, so we add a final consideration to our cost function instead of adding all those stupid { ("A","A"): 0 } items to the dictionary.
The successor() function for this problem space can also be written as a simple lambda function:
successor = lambda n: [p[1-i] for i in range(1) for p in distance if p[i] == n] |
I'll let you try to find out how the successor() function does its job. From the second for loop in the comprehension it can be deduced this is not the best way of obtaining the successors of a node. A tree-like data structure would allow us to be much more efficient, but it would make the code more complex too. This is a trade-off that you'll find over and over when using Python: you'll be able to express complex concepts easy and fast, sacrificing run-time performance. But you'll have your system ready to show very quickly and nothing prevents you from optimizing the heavy parts as soon there's time for it.
Cost-based search: the basics
The main difference between the brute-force approaches we've seen so far and cost-based search is the order in which states are expanded. Cost-based search algorithms pick the next state to expand from the current fringe using a function of the cost of reaching that state from the initial state. An important implication of that behavior is that it is not possible to pick a set of states to expand at one time, as e.g. the breadth-first search algorithm does; the reason being that with each state expanded, new child states cheaper than the ones already in the fringe might be generated, thus altering any order established before the expansion.
One advantage of the recursive algorithm proposed in the first
post is that we don't need to perform housekeeping of the data structure holding the current fringe; all the states expanded down to a given recursion level are kept in the successive stacks of the enclosing recursion levels. This is possible because within a recursion level we don't need to access the states generated in an enclosing level. However, that
status quo changes with cost-based search. After expanding a number of states at a given recursion level, the candidate to be expanded next might have been generated at
any enclosing recursion level, in addition to the current level. This breaks our previous scheme and forces us to make slight modifications to the algorithm; unfortunately, these modifications turn the new algorithm incompatible with the previous one. The good news are that the new algorithm can efficiently behave as the previous one if the appropriate cost functions are used.
Another advantage of the previous algorithm is that it is able to model the search tree very efficiently by means of a dictionary relating children (keys) with parent (value). That has to do as well with the recursive nature of the algorithm and the order in which states are expanded; when returning from en enclosed recursion level because a solution has been found, the enclosing level can safely assume the parent of the state added to the solution by the enclosed level is held at its local stack and can be obtained as
desc[sol(0)]. From the paragraph above you can conclude this situation changes as well, since the parent of a state included in the solution by a recursion level might be in the local stack of
any enclosing level. Thus we need another way to model the parent-child relationship, while adding the step cost of going from parent to child to the equation.
Let's see how the slightly modified algorithm looks like:
class Problem(object):
...
class Node(tuple):
'''
A simple tuple wrapper to make the algorithm implementations
easier to understand
'''
cost = lambda n: n[0]
item = lambda n: n[1]
parent = lambda n: n[2]
def getPerformance ( self ):
return self.__performance
performance = property(getPerformance)
...
def treeSearchWithCost ( self, gen ):
self.__performance = 0
fringe = [Problem.Node((0, self.__initial, None))]
visited = set()
h = lambda n: fringe[0] == n and n not in visited
sol = self.__recurseWithCost(fringe, gen, visited, h)
if sol:
self.__solution = [n.item() for n in sol if n]
def __recurseWithCost ( self, fringe, gen, visited, h ):
for n in filter(h, fringe):
self.__performance += 1
if self.__goal(n.item()):
return [n] # the base case
for desc in gen(fringe):
try:
visited.update(\
map(Problem.Node.item, map(Problem.Node.parent, desc)))
except TypeError: # 'NoneType' is not subcsriptable
visited and visited.clear() # desc is the initial state, IDDF
except AttributeError: # 'NoneType' has no attribute 'visited'
pass # user doesn't want us to check for dups
sol = self.__recurseWithCost(desc, gen, visited, h) # the recursive case
if sol:
try:
sol.insert(0, sol[0].parent())
except:
pass
return sol
|
Snippet 1 - Modified code for cost-based search
We've added a
Node class to our definition of Problem. This is just a façade class for a tuple; we'll be using a tuple to hold the cost and the parent of a state, and using the façade class makes the code much more inteligible than using indexing, like in
cost = node[0],
parent = node[2] etc. In exchange for this syntactic sugar we lose some performance since a virtual function call is more expensive than indexing a small tuple, but in my oppinion that's a small loss compared to the understanding of the code we gain.
Another addition to the class is the
performance property. We're going to use a performance figure to evaluate the relative quality of the generators we explore in the coming sections, and the
performance property is the realization of that figure. As you can see in the code, the value of the property is reset each time we call the
treeSearchWithCost() method, and is increased with every node selected for expansion. thus, at the end of each algorithm run the performance property holds the number of expanded states. The smaller this value, the more efficient the algorithm is in finding a solution to the problem.
The single remarkable change that remains to explain is within the
treeSearchWithCost() method. As you can see, the filter function
h is set to
fringe[0] == n and n not in visited. If you remember the previous post, this function was used to prevent expanding already expanded states, returning
True when the state is not in the list of visited nodes. Here we're enhancing it so in addition to that, it returns only the
first element in the fringe. But why's that?
Remember brute-force algorithms just find a solution, they don't care whether it's the best one or if there are others (well, in fact breadth-first search shall find the solution with the
smallest number of steps). However a cost-based optimal algorithm cannot go by that simple rule. Imagine a solution pops up in the fringe at absolute cost 200, while there are some other, not yet expanded states in that fringe with absolute costs 100, 150 and 185. Any of those three states has the potential to reach a solution with a cost lower than 200, so we cannot just return the solution that popped up and go to sleep. The algorithm must explore all the states, in cost order, until it makes sure the first solution in the fringe is the best one. And that happens when the heap's head is a solution, because then there's no other unexpanded state whose absolute cost is lower than that of the head. Thus we'll check only the heap's head for deciding if we've found the solution.
Uniform cost-based search
Let's move on to the search algorithms themselves. We'll start with the simplest form of cost-based search, called
uniform cost-based search. The generator that runs uniform cost-based search on our problem space is as follows:
@staticmethod
def uniformCostGenerator ( successor, cost ):
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 to where we come from
f = best_node.cost() + cost(desc, best_node.item())
heapq.heappush(fringe, Problem.Node((f, desc, best_node)))
yield fringe
return nestedGenerator |
Snippet 2 - Uniform cost search generator function
Surprisingly simple, isn't it?. But hidden in the apparent simplicity lies a major change with respect to the previous generators: as opposed to those, this generator modifies the fringe it receives from its caller in-place, and yields that same fringe instead of a newly generated one. This is because after yielding, the next state to expand might indeed be in the fringe received (if e.g. all the states just generated are more expensive than some state in that fringe). We could have created a copy of the fringe received and returned the modified copy instead, but when the fringe is large the performance penalty would be unacceptable.
Other than that, the generator uses a heap to sort the descendants of the state it expands in the current iteration by cost order, with the node having the lowest cost sitting at the beginning of the heap. Actually, the only requirement the algorithm has on the heap is to keep the lowest cost node at the head (remember that
treeSearchWithCost() always expands the node at the head of the fringe), so using the Python heap implementation is very convenient due to the space and performance gains attained by partial ordering with respect to a fully sorted heap. For further details about the Python heap container see the
Python Library Reference.
The following image shows the patch followed by uniform-cost search down to the fringe leading to Bucharest:
Figure 2 - Path followed by Uniform Cost-based search from Arad down to Bucharest
Like breadth-first search, uniform-cost search will find a solution if there's one, i.e. it is
complete. If we consider path costs uniform-cost search will not only find a solution, but
the best solution in terms of path cost, i.e. it is
optimal. Notice breadth-first search might not be optimal in cost terms, since it always finds the
shortest path in terms of number of steps but the cost of taking those steps might actually be higher than that of the steps in another solution with a higher number of steps.
We can test uniform-cost search with our brand new problem definition, as follows (I suggest you put the problem space together with the code that follows in a testNavigation() method) :
initial = "Arad"
goal = "Bucharest"
problem = Problem(initial, goal, successor, cost)
problem.treeSearch(Problem.uniformCostGenerator(successor, cost))
self.assertTrue(problem.solved())
print ("Solution found using uniform-cost search: " + str(problem.solution))
print ("Algorithm performance: ", problem.performance)
|
Snippet 3 - Testing uniform cost search
If you check the solution the algorithm found, you'll see that it is not the apparently shortest Arad->Sibiu->Fagaras->Bucharest (4 steps). This is because the cost of that path is indeed higher than that of the Arad->Sibiu->R.Vilcea->Pitesti->Bucharest path (you can check that yourself by carefully looking at each step's cost in our problem state definition above).
Iterative Lengthening search
The same as we derived an iterative algorithm from breadth-first search (see the previous post), a cost-based iterative algorithm can be derived from uniform-cost search. The idea would be to keep the completeness and optimality guarantees of uniform-cost search while avoiding its excessive memory requirements (recall that uniform-cost search, as breadth-first search, keeps all the expanded nodes in local memory). This algorithm is called iterative lengthening search, and is coded as follows:
@staticmethod
def iterativeLengtheningGenerator ( successor, cost, anchor ):
var = { "max_cost": 0, "new_max_cost": 0 }
def nestedGenerator ( fringe ):
max_cost = var["max_cost"]
new_max_cost = var["new_max_cost"]
best_node = heapq.heappop(fringe)
descendants = successor(best_node.item()) or []
for desc in descendants:
if desc != best_node.parent(): # going back to where we come from
f = best_node.cost() + cost(desc, best_node.item())
if f <= max_cost:
heapq.heappush(fringe, Problem.Node((f, desc, best_node)))
else:
new_max_cost = min(f, new_max_cost or f)
var["new_max_cost"] = new_max_cost
if len(fringe) == 0:
var["new_max_cost"] = 0
var["max_cost"] = new_max_cost
heapq.heappush(fringe, Problem.Node((0, anchor, None)))
yield fringe
return nestedGenerator |
Snippet 4 - Iterative Lengthening search generator
If you check the iterative deepening search generator from previous post you'll find some resemblances here. The differences between that one and iterative lengthening search are that where iterative deepening search expands states in the current level in sequential order, iterative lengthening search expands states by cost order, starting with the one with the lowest cost; and instead of using a number of steps as limit, it uses the smallest cost from the previous iteration. The latter allows the algorithm to discard paths further down the tree which cost is higher than that of other state previously expanded. The search shall trace back and forth until it finds the optimum solution in terms of cost.
Unfortunately the addition of path costs to the equation considerably widens the alternative paths the algorithm has to explore, so it suffers from excessive trace back and forth overhead. Moreover, as I mentioned in the previous post this way of implementing an iterative search algorithm is far from optimal, since it keeps all the states expanded in a previous iteration in main memory. Actually, if you test this algorithm you'll probably get a
recursion limit reached error from the Python interpreter.
Once again, we can test this algorithm with our problem space as follows:
initial = "Arad"
goal = "Bucharest"
problem = Problem(initial, goal, successor, cost)
problem.treeSearchWithCost(
Problem.iterativeLengtheningGenerator(successor, cost, initial))
self.assertTrue(problem.solved())
print ("Solution found using ILS: " + str(problem.solution))
print ("Algorithm performance: ", problem.performance)
|
Snippet 5 - Testing iterative lengthening search
Conclusion
In
the next -and last- post, we shall look at a different, smarter breed of algorithms that leverage additional knowledge about the problem space to improve its search performance. Nonetheless, the new algorithms fit seamlessly in the common
treeSearchWithCost() search framework. I hope you follow me through to that point. While you wait eagerly :), there are two interesting exercises you can do on your own:
- Modify the treeSearch() algorithm from the previous post so it uses the Node class, instead of a simple dictionary-like structure. Also disable the optionality of duplicate checking, making it mandatory as in treeSearchWithCost(). diff what you get with the treeSearchWithCost() code from this post: there's a remarkable difference between both we haven't talked about, can you reason where it comes from?
- Enhance the treeSearch() algorithm from the previous post with performance measuring. Run the different brute-force algorithms from the previous post on the Romania road map and check the differences with respect to uniform-cost based search.
