Tuesday, March 20, 2012

One uninformed search algorithm to rule them all

Introduction

Uninformed search algorithms perform exhaustive search of trees and graphs looking for a solution to a given  problem. The trees/graphs traversed by the algorithms represent states of the world the problem concerns. You can read more about solving problems applying uninformed search in chapter 3 of the book "Artificial Intelligence: a Modern Approach" by Russell&Norvig.

In this post I'm tackling problem solving applying uninformed search using Python, and more specifically some of the less known features of the lenguage such as recursion, generators and closures. I think this is interesting because it gives you the chance to learn about problem solving, search algorithms and advanced Python in one single place.

Ther're a few standard algorithms that perform uninformed search on trees/graphs. These are:
  • Depth-first search: search the tree/graph starting from the root node and going deep down as fast as possible. When a dead end state (i.e. a state with no successors) is found, trace back to the state immediately preceding the dead end and try going down through another successor. Search ends when a solution is found, or alternatively when all nodes have been searched. The following drawing shows how a depth-first search progresses through an example tree:
Figure 1 - Evolution of depth-first search on example tree
  • Breadth-first search: search the tree/graph starting from the root node and searching every generation of nodes in full before moving down to the next generation. In every-day language, search all the parents before start searching their sons. Search ends when a solution is found, or alternatively when all nodes have been searched. The following drawing shows how a breadth-first search progresses through an example tree:
Figure 2 - Evolution of breadth-first search on example tree
  • Limited-depth search: this is a variant of depth-first search where traceback to the parent node takes place not when a dead-end state is found, but when a pre-determined, constant depth has been reached. Again in every-day language, if we limit search depth to grand-sons, a depth-first seach would stop and traceback at every grand-son of the root, regardless that grand-son has children of its own. this algorithm tackles the biggest weakness of depth-first search algorithms: if the tree has no pre-determined depth or is a graph a depth-first search algorithm shall easily get stuck without finding a solution. The following drawing shows how a limited-depth search progresses though an example tree:
Figure 3 - Evolution of limited-depth search with limit 2 on example tree
  • Iterative deepening depth-first search: this is a variant of limited-depth search, which deepens down into the tree progressively one level at a time. So it starts with the grandparent, then it searches grandparent and its children, then it searches grandparent, parents and their children, and so on. Iterative deepening search improves one weak spot of limited-depth search: if the solution lies one or more levels further down than the pre-determined depth limit the algorithm won't find it. The following drawing shows how an iterative deepening depth-first search algorithm proceeds through an example tree:
Figure 4 - Evolution of IDDF search on example tree

  • Bidirectional search: this is actually two parallel breadth-first searches that start with the root node respective solution node, and go down respective up until both searches meet at a common node. This algorithm can prove very fast at certain problems but has the obvious drawback that a solution node must be easily identifiable, and all the parent nodes of a given node must be easy to obtain. These conditions do not hold for most search problems. The following drawing shows how a bidirectional search algorithm proceeds through an example tree:
Figure 5 - Evolution of bidirectional search on example tree

Each of the above algorithms possesses its own strengths and weaknesses, and each lends better to certain kind of problems. As a rule of thumb, the one providing best memory/processor usage trade-off for most problems is iterative deepening depth-first search (IDDF). Additionally, IDDF search is complete, which means it shall always find a solution if there's one (and the tree is of finite depth, of course). I'll let the theoretical details of algorithm properties to the respectable book mentioned at the beginning of this post, and focus from here on algorithm implementation using Python.

Problem formulation


Well-established game theory postulates that solving complex problems by algorithmic means requires a specific problem formulation approach. More specifically, a problem formulation consists of:
  1. An initial state of the world
  2. A function f(s) = S' producing a set of world states S' from a known state s
  3. A set of one or more goal states of the world that we want to reach
  4. A cost function c(s,t) giving the cost of reaching state t from parent state s
Let's write a simple Python class modeling this approach to problem formulation:

from functools import reduce # Only for Python 3

class Problem(object):
    '''
    Model of a problem following the problem formulation theory of chapter 3
    '''

    def __init__ ( self, initial, goal, successor, cost ):
        '''
        Constructor
        '''
        self.__goal = goal
        self.__successor = successor
        self.__cost = cost
        self.__initial = initial
        self.__solution = None

    def getSolution ( self ):

        '''
        Returns the current solution to the problem if any has been
        found, or None otherwise.
        The solution is a list of states, with the initial state at [0]
        and the goal state at [-1].
        '''
        return self.__solution
    solution = property(getSolution)

    def solved ( self ):

        '''
        Tells whether the problem has been solved
        '''
        return self.__solution and (self.__goal == self.__solution[-1])

    def solutionCost ( self ):

        '''
        Returns the cost of reaching the found solution if any has been found,
        or None otherwise
        '''
        if self.solved():
            return reduce(self.__cost, self.__solution)
Sinppet 1 - Python class modeling a problem definition

Search algorithms


Given the previous definition, the following methods implement depth-first and breadth-first search respectively using recursion:

def treeSearch ( self, search_func ):
    '''
    Call passing Problem.recurseDepthFirst or Problem.recurseBreadthFirst
    as search_func as appropriate.
    '''
    fringe = [self.__initial]

    self.__solution = search_func(self, fringe)

def recurseDepthFirst ( self, next ):
    if next == self.__goal:
        return [next] # the base case

    descendants = self.__successor(next) or [] # the recursive case
    for desc in descendants:
    sol = self.recurseDepthFirst(desc)
    if sol:
        sol.append(next)
        return sol

def recurseBreadthFirst ( self, fringe ):
    for n in fringe:
        if n == self.__goal:
            return [n] # the base case

    new_fringe = {}
    for n in fringe:
        descendants = self.__successor(n) or []
    for desc in descendants:
        new_fringe[desc] = n
    if len(new_fringe): # don't remove!!!
        sol = self.recurseBreadthFirst(new_fringe)
        if sol:
            sol.append(new_fringe[sol[-1]])
            return sol
Snippet 2 - Depth-first and breadth-first search implemented using recursion

We could go on and implement similar methods for depth-limited search and IDDF search. However, looking at the code for both search algorithms above we can't help but notice some remarkable similarities. The first paragraph of recurseDepthFirst() is a particularization of the first paragraph of recurseBreadthFirst() for a sequence of lenght 1. Thus it can be easily made common across both methods. Something similar goes for the second paragraph. That made me wonder if it'd be possible to perform both searches using a single algorithm, parameterized somehow to perform one or the other search. The interesting answer is yes, it is possible. Leveraging Python's generators we can write a common search method that uses one or the other search algorithm. Let's see how:


def treeSearch ( self, gen ):

    fringe = [self.__initial]

    self.__solution = self.__recurse(fringe, gen)



def __recurse ( self, fringe, gen ):

    for n in fringe:

        if n == self.__goal:

            return [n] # the base case



    for desc in gen(fringe):

        sol = self.__recurse(desc, gen) # the recursive case

        if sol:
            try:
                sol.insert(0, desc[sol[0]])
            except:
                pass
            return sol
Snippet 3 - Common search algorithm

The snippet above is a generalization of the structure of the previous algorithms. It is valid for both depth-first and breadth-first search, and the specific algorithm behavior is provided by means of the 'gen' argument. That can in principle be any iterable type, but we'll use a couple of generator functions to achieve the 'magic' we're looking for:
@staticmethod
def depthFirstGenerator ( successor ):
    def nestedGenerator ( fringe ):
        for n in fringe:
            descendants = successor(n) or []
            for desc in descendants:
                yield { desc: n }
    return nestedGenerator

@staticmethod
def breadthFirstGenerator ( successor ):
    def nestedGenerator ( fringe ):
        new_fringe = {}
        for n in fringe:
            descendants = successor(n) or []
            for desc in descendants:
                new_fringe[desc] = n
        yield new_fringe
    return nestedGenerator
Snippet 4 - Generator functions for depth-first and breadth-first search

In Python, any function containing a yield sentence is a generator function, or generator in short. The interpreter creates an iterable from the generator that can then be used in any construct where a normal iterable can be used. Since the functions do not use any members of the Problem class they could have been defined anywhere in a namespace accessible from the calling code, but to keep global namespace tidy we've defined the methods within the Problem class as static methods (using the @staticmethod decorator).

Notice the definition of function nestedGenerator() enclosed inside the supposed generator method. According to what you've just read, nestedGenerator() is the actual generator function (since it contains the yield sentence). The enclosing method is a facility to parameterize the actual generator with a successor() function, so we avoid passing the successor function around all the time. The Python facility that enables the nested function to "see" the actual value of the successor argument in run-time is called a closure. When a function is defined within another function, all the variables local to the enclosing function at the moment it is called are provided to the enclosed function as part of its namespace. This set of variables is known as the closure of the enclosed function (as a side note you could have made the successor function and the two above methods members of the Problem class, but then I wouldn't need to use the cool closure facility).

Here's how the Problem class can be used:

class ProblemTest(unittest.TestCase):

    def testProblem(self):
        initial = 1
        successor = lambda x : (2*x, 2*x + 1)
        cost = lambda x : 1
        goal = 8 # goal must be on a leftmost branch of the tree!!
        problem = Problem(initial, goal, None, cost)
        problem.treeSearch(Problem.depthFirstGenerator(successor))
        self.assertTrue(problem.solved())
        self.assertEqual(
            problem.solution, [1, 2, 4, 8],
            "Solution found is " + str(problem.solution))
Snippet 5 - Unit test class showing how to use the Problem class with depth-first search

Notice that we've not changed the Problem class constructor signature from the initial implementation; but since now the successor function is an argument to the pseudo-generator function, we set the constructor argument's actual value to None to make sure it is not being called elsewhere.

Notice also the comment beside the goal setting sentence. From your knowledge of search algorithm properties, can you tell what would happen if the goal value weren't in a leftmost branch of the tree?.

Using breadth-first search is just as easy:

        goal = 10
        problem = Problem(initial, goal, successor, cost)
        problem.treeSearch(Problem.breadthFirstGenerator(successor))
        self.assertTrue(problem.solved())
        self.assertEqual(
            problem.solution, [1, 2, 5, 10],
            "Solution found is " + str(problem.solution))
Snippet 6 - Continuation of ProblemTest.testProblem() method showing how to use breadth-first search

Observe in this case we can set any goal we want (I picked 10 so execution is fast, but you may try and test different values to see how it goes). The reason for this is that breadth-first is complete as long as the successor() function produces a finite number of states.

OK, so far we've implemented the two main classes of search algorithms with one single method. But now you should be intrigued: can the other search algorithms be implemented leveraging the same method as well?. Once again, I can say the answer is yes. Both depth-limited search and IDDF search can be implemented without changing a line by writing new specialized generators. Let's start with the easy one, depth-limited search:

@staticmethod
def depthLimitedGenerator ( successor, max_level ):
    var = { "level": 0 }
    def nestedGenerator ( fringe ):
        var["level"] = var["level"] + 1
        if var["level"] < max_level:
            for n in fringe:
                descendants = successor(n) or []
                for desc in descendants:
                    yield { desc: n }
        var["level"] = var["level"] - 1
    return nestedGenerator
Snippet 7 - Generator fulfilling the depth-limited search algorithm

We're diving into the darkest corners of Python here. Remember the concept of closures introduced above? What we want to do here is adding level and max_level variables to the generator's closure. Then inside the generator we increase the level variable until it reaches max-level, at which moment we trace back one generation (decreasing the level variable by one and returning). But why am I using the map subterfuge instead of just declaring variable level as normal, like "level = 0" and then "level = level + 1" inside the generator function?. Think for a while before continue reading.

The answer to the above question lies in the way the Python interpreter handles nested namespaces and variables local to a function. Whenever the interpreter defines a function a new namespace is assigned to that function; the new namespace inherits all the enclosing namespaces all the way up to the global namespace. Your function code can read the value of a symbol defined within any of those namespaces, however when writing a value to one of those symbols the interpreter creates a new symbol in the function namespace that shadows any symbol with the same name in any enclosing namespace.

Thus, in our generator above, static method depthLimitedGenerator() gets a new namespace in which variables successor and max_level exist, in addition to the Problem class and global namespaces. We could have defined a variable called level as well before the actual generator function nestedGenerator(); however, within that function we can only read the value of level, and if we do something like "level = level + 1", the interpreter creates a new level variable local to nestedGenerator()'s namespace that shadows the level variable from the enclosing function's namespace, rendering the value of that variable (part of nestedGenerator()'s closure) inaccessible. You can go and try this yourself.

So our only alternative is to wrap the variable we want to write from within the enclosed function in a map. In fact what we're doing is creating our own namespace local to the depthLimitedGenerator() and enclosed functions. From within nestedGenerator() we can safely write the new level value since in doing that we're not writing the map itself but the item referenced by the map.

Another quirk from the Python language is we cannot reuse the existing depth-first generator implementation; to be considered a generator, the function must explicitly contain the construct "yield". A generator called from within another function does not turn the latter into a generator itself.

You can test our depth-limited search implementation as follows:

    goal = 10
    problem = Problem(initial, goal, successor, cost)
    problem.treeSearch(Problem.depthLimitedGenerator(successor, 4))
    self.assertTrue(problem.solved())
    self.assertEqual(
        problem.solution, [1, 2, 5, 10],
        "Solution found is " + str(problem.solution))
Snippet 8 -  Continuation of ProblemTest.testProblem() method showing how to use depth-limited search 

Observe how we instantiate the generator passing a max_level value of 4. Can you guess what would happen if we passed a max_level value of 3 instead?

To conclude this post, I'll show you the generator implementing IDDF search. This is the most complex one but if you've made it this far you've got all you need to understand it. Here it goes:

@staticmethod
def iterativeDeepeningGenerator ( successor, anchor ):
    var = { "max_level": 1, "level": 0 }
    def nestedGenerator ( fringe ):
        var["level"] = var["level"] + 1
        if var["level"] <= var["max_level"]:
            new_fringe = {}
            for n in fringe:
                descendants = successor(n) or []
                for desc in descendants:

                    yield { desc: n }
                var["level"] = var["level"] - 1
            yield new_fringe
        else:
            var["level"] = 0
            var["max_level"] = var["max_level"] + 1
            yield [anchor]
    return nestedGenerator
Snippet 9 - Generator fulfilling the IDDF search algorithm

We're passing a new parameter to the pseudo-generator function (the one that creates the actual generator), which contains the state which the algorithm must trace back to when reaching the current level of depth in the search tree. Aside that, there's nothing really different in this generator from what you've already seen before.

One drawback of this way of implementing an iterative search is that when tracing back to the anchor node, we are keeping the whole set of states expanded to that moment in the stacks of the enclosing recursion levels; this is necessary for the previous algorithms since they use that set to trace back and to build the path to the solution once one has been found. But for an iterative algorithm it is a waste of memory since we won't need those states anymore (we're re-starting the algorithm from the initial node).

I'll let as an exercise to you fixing the search algorithm so previously generated states are dropped when re-starting the algorithm from the initial state. You won't achieve that by tweaking or re-ordering the lines in the generator, you need to change the treeSearch() method so it calls recurse() in a loop until a solution is found (or the search tree is exhausted). You'll need some additional stuff in the recurse() method to allow treeSearch() to distinguish when recurse() returns because it has exhausted the search tree, otherwise treeSearch() will get stuck in an endless loop!.

Checking for duplicates

So far we've been dealing with searching solutions for problems whose evolution follows a strict tree pattern. What happens if we apply the above algorithms to problems whose world evolves following a graph pattern? If the graph is acyclic it poses no major issue; it shall take longer for the algorithms to find a solution, but in the end if the algorithm is complete it shall find one. Things are different for cyclic graphs though. When the graph is cyclic all but the depth-limited search algorithm shall get stuck when entering the cycle.

Problems whose world evolves as a cyclic graph are not uncommon. For instance, when searching a route between two locations on a road map, usually ther're two roads between every intermediate location: the modern, fast roadway and the old, two-way slow road. Without further ado our algorithms shall get stuck navigating from A to B then from B to A over and over again.

Thus we need to enhance our algorithms for avoiding cyclic graphs, and the easiest way of doing it is allowing the algorithm to know when it has already "visited" a world state it reaches. Armed with this knowledge the algorithm may decide to not progress any further along that line and trace back and forth until it reaches a new, unknown state. This approach is known as checking for duplicates.

The idea is simple: every state that is expanded (i.e. its subsequent states are generated) by the algorithm is added to a list of visited states. Before expanding a state, the algorithm checks for the presence of the state in that list, and if it finds it then the state won't be expanded. Let's see how this logic fits in our general uninformed search method:

def treeSearch ( self, gen, chk_dups = False ):
    fringe = [self.__initial]
    visited = None
    h = None
    if chk_dups:
        visited = set()
        h = lambda n: n not in visited
    self.__solution = self.__recurse(fringe, gen, visited, h)

def __recurse ( self, fringe, gen, visited, h ):
    for n in filter(h, fringe):
        if n == self.__goal:
            return [n] # the base case

    for desc in gen(filter(h, fringe)):
        try:
            visited.update(desc.values())
        except:
            pass

    sol = self.__recurse(desc, gen, visited, h) # the recursive case
    if sol:
        try:
            sol.insert(0, desc[sol[0]])
        except:
            pass
    return sol
Snippet 10 - Enhanced search method able to navigate cyclic graphs

We have introduced a few changes here, haven't we? First, we allow the user of the treeSearch function to specify whether it wants the search to check for duplicates. Checking for duplicates makes the algorithm slower and more memory-hungry so it's a good idea to be able to short-circuit it if we know we're dealing with a tree before hand.

If our user wants duplicates checked, we create a list of visited states and a discarding function. The discarding function receives a state as actual argument and returns False when the state is to be discarded in the search, or True otherwise. Notice how the closure concept applies here once more? No matter where we call the h function, it shall have access to the visited variable. I've chosen the variable name h for this function for reasons that will be exposed when we talk about informed search algorithms; for now it should be enough to say the h stands for heuristic. Both the list of visited and the discard function are given to our recursive method as actual arguments.

Now within the recursive method, in the initial loop where we check for goals we use a filter() iterator instead of the whole fringe passed as argument. The filter() iterator applies its first argument as a function to every element of its second argument as an iterable, and returns only those elements for whose the result of the function is False. Thus, with this enhancement we're avoiding checking a state that has already been checked. in a previous call.

Next, instead of passing the whole fringe to the generator we're passing it a filter() iterator again. Remember that the different generators we have just expand the state list they receive in one or other way depending on the algorithm they correspond to. Thus, by filtering out certain states we prevent those states from being expanded. One might be tempted to optimize the code above and create a single filter() iterator that is re-used in both loops; don't do it. Once the filter() iterator is burned in the first loop it shall not return any more states and the second loop shall be skipped.

Now how do we decide which states shall be filtered out in the two loops? Simple: once a list of states has been returned by the generator, we add any parent states of the former to the list of visited states. Remember the lists of states returned by our generators are actually dictionaries whose entries point to their respective parent states (except when the list contains only the initial state, in which case it is exactly that: a list; hence the try: except clause wrapping the "sol.insert( desc[sol[0]] )" sentence).

Why the try: except clause when updating the list of visited states? The purpose is two-fold: for correctness, just in case the fringe contains only the initial state in which case the fringe is a raw list and calling values() on it would fail; and for efficiency, avoiding an if sentence checking for visited set to None in every step of the for loop. This idiom gives the microprocessor a tip that visited set to None is an exceptional case, thus allowing its code and data HW pre-fetchers to perform more eficiently when running that piece of code. Here I'm assuming users of treeSearch() shall set chk_dups argument to True in 90% of the cases, since otherwise each step of the loop raises an exception ruining our optimization attempt.

The enhanced function can be tried adding some code to our testSearch() unit test; instead of the simple f(n) = (2*n, 2*n+1) successor function we've been using up to here, we shall use a modified successor function that one in two times returns a parent state in addition to the child states:

f(n) = (random() < 0.5 and (2*x, 2*x + 1)) or (max(1, int(x/2)), 2*x, 2*x + 1)

Observe the above successor function returns changing graphs between searches, or even within the same search!. However that poses no issue for our enhanced search algorithm, as you'll see if you run the test method with varying goal values.

    goal = 10
    successor = \

        lambda x: (random() < 0.5 and (2*x, 2*x + 1)) \
        or (max(1, int(x/2)), 2*x, 2*x + 1)
    problem = Problem(initial, goal, successor, cost)
    problem.treeSearch(Problem.breadthFirstGenerator(successor), chk_dups=True)
    self.assertTrue(problem.solved())
    self.assertEqual(
    problem.solution, [1, 2, 5, 10],
    "Solution found is " + str(problem.solution))
Snippet 11 - Continuation of testSearch() unit test trying our enhanced search method

Obviously, for the just described approach to be valid states must be possible to tell apart of each other; even if it may not have been fully apparent to you, the tree search algorithms did not require this property!.

Conclusion

I hope you've enjoyed this little journey into uninformed search algorithms and Python. My next challenge would be designing a generator for the common algorithm that performs bidirectional search.

In the next post we'll see how to use this algorithm framework to solve some classic computing problems. Enjoy yourselves till then!



No comments:

Post a Comment

Go middlewares for object-oriented programmers Go language (Golang, http://golang.org ) is a very simple procedural programming language of ...