Tidying up the house

Introduction

In the series of posts on problem solving by means of search, either blind of informed, we ended up with a single Problem class containing all the data and functions/methods necessary for declaring, solving and obtaining solutions for complex problems. We applied the Problem class to a number of real-world problems like the well-known missionaries&cannibals and N-queens problems, and rounded it all up with a road  navigation problem across the beautiful land of Romania.

I've decided I'm going to write a new series on solving problems in continuous spaces by means of local search and optimization. This is the kind of problems that a rover robot meets when travelling the world, for  example.

But, as my Mom uses to say, "before hosting new guests tidy up the house". So we're going to revise the implementation used across the previous series and clean it up according to OO principles. Thus this post serves as a quick introduction of OO design as well. Are you ready? Let's go then, I hope you enjoy the trip!

Problems with the Problem class (no pun intended)

The main issue with the Problem class we developed is that it mixes two different concepts in one single class. The class does not only model a problem but also its solution and the algorithm used to reach it.

This fact shows up notoriously in the need for two methods, treeSearch() and treeSearchWithCost(), which perform the same function using different algorithm classes. Moreover, there is no clue whatsoever in the class definition about which algorithms can be used with which algorithm class (i.e. which generators can be passed to each method).

Another indication of this mix up is that we cannot -at least not simultaneously- get multiple solutions to the same problem, not even using different algorithms.

Here's the definition of the Problem class we ended up with after the previous series (I've omitted class' private members for clarity):

class Problem(object):     class Node(tuple): ...                  def __init__ ( self, initial, goal, successor, cost ): ...              performance = property(getPerformance)          resources = property(getResources)          solution = property(getSolution)          def solved ( self ): ...          def solutionCost ( self ): ...              def graphSearch ( self, gen ): ...          def treeSearch ( self, gen, chk_dups = False ): ...     def treeSearchWithCost ( self, gen ): ...                              @staticmethod     def depthFirstGenerator ( successor ): ...              @staticmethod     def breadthFirstGenerator ( successor ): ...                  @staticmethod     def depthLimitedGenerator ( successor, max_level ): ...              @staticmethod     def uniformCostGenerator ( successor, cost ): ...                          @staticmethod     def iterativeDeepeningGenerator ( successor, anchor ): ...     @staticmethod     def iterativeLengtheningGenerator ( successor, cost, anchor ): ...                          @staticmethod     def bidirectionalSearchGenerator ( goal ): ...     @staticmethod ...     def greedyBestFirstGenerator ( successor, h ):          @staticmethod     def aStarGenerator ( successor, cost, h ): ...

Snippet 1 - Class structure of class Problem from the previous series

Our design goals with this exercise are as follows:

1. Having a Problem class that models exclusively a single problem;
2. Having a ProblemSolver class that solves problems expressed as instances of Problem;
3. Separating the blind and cost-based algorithm classes so it can be chosen which algorithm class to use, if possible using the same interface

So we're going to split the Problem class into a -shorter- Problem class and a new ProblemSolver class. As criteria for what to put where, we'll use a simple but effective rule-of-thumb: if something can't live without a class, then it's part of that class. This criterion is not only used in OO design but in Entity-Relationship modelling as well.

Let's start with the Node sub-class. A Node is an artifact used to hold book-keeping information in a search tree while a problem is being solved by means of a given algorithm. Thus, from its definition and the fact it does not need a Problem instance to live, we'll remove it from Problem. We'll include it in ProblemSolver though, not because that's the only other place it could go but because it makes sense. After all, even if a Node can live without a ProblemSolver, what's the point anyway?.

Then with Problem's properties. Neither of those are properties of Problem (they can happily live without it), but seem to be part of ProblemSolver (apart from solution, which may be debatable, the others make no sense without being attached to a ProblemSolver).

And finally with the class' methods; none of the class nor instance methods are part of Problem according to our rule-of-thumb criterion, but seem to be part of ProblemSolver instead.

Thus we're moving the Node sub-class, properties and methods over to the new ProblemSolver class. We will end up with something like this:

class Problem(object):     def __init__ ( self, initial, goal, successor, cost ): ... class ProblemSolver(object):              class Node(tuple): ...                  performance = property(getPerformance)          resources = property(getResources)          solution = property(getSolution)          def solve ( self, problem, gen, chk_dups = False ): ...     def solved ( self ): ...          def solutionCost ( self ): ...              def graphSearch ( self, gen ): ...          def treeSearch ( self, gen, chk_dups = False ): ...     def treeSearchWithCost ( self, gen ): ...                              @staticmethod     def depthFirstGenerator ( successor ): ...              @staticmethod     def breadthFirstGenerator ( successor ): ...                  @staticmethod     def depthLimitedGenerator ( successor, max_level ): ...              @staticmethod     def uniformCostGenerator ( successor, cost ): ...                          @staticmethod     def iterativeDeepeningGenerator ( successor, anchor ): ...     @staticmethod     def iterativeLengtheningGenerator ( successor, cost, anchor ): ...                          @staticmethod     def bidirectionalSearchGenerator ( goal ): ...     @staticmethod ...     def greedyBestFirstGenerator ( successor, h ):          @staticmethod     def aStarGenerator ( successor, cost, h ): ...

Snippet 2 - Class split between Problem and ProblemSolver

We've taken a first stab at the design but we're not done yet. Still our ProblemSolver class mixes up the two algorithm classes and provides no clue at which generators can be applied to which search method. Since we're talking about algorithm classes here, the design seems to naturally lend towards separating ProblemSolver into two different classes: one using blind search and another one using cost-based search. In order to offer the same interface for both algorithm classes, we might devise a inheritance scheme where the basic ProblemSolver provides the foundation for problem solving like properties, initialization method etc. plus an implementation of the interface using blind search, whereas a derived CostBasedProblemSolver overloads the interface to use cost-based search. We'd end up with something like in the following snippet:

class Problem(object):     def __init__ ( self, initial, goal, successor, cost ): ... class ProblemSolver(object):              class Node(tuple): ...                  performance = property(getPerformance)          resources = property(getResources)          solution = property(getSolution)          def solve ( self, problem, gen, chk_dups = False ): ...     def solved ( self ): ...          def solutionCost ( self ): ...              def graphSearch ( self, gen ): ...          def treeSearch ( self, gen, chk_dups = False ): ...                              @staticmethod     def depthFirstGenerator ( successor ): ...              @staticmethod     def breadthFirstGenerator ( successor ): ...                  @staticmethod     def depthLimitedGenerator ( successor, max_level ): ...              @staticmethod     def iterativeDeepeningGenerator ( successor, anchor ): ...                          @staticmethod     def bidirectionalSearchGenerator ( successor, goal ): ...     @staticmethod ...     def greedyBestFirstGenerator ( successor, h ): class CostBasedProblemSolver(ProblemSolver):     def treeSearch ( self, gen, chk_dups = False ): ...     @staticmethod     def uniformCostGenerator ( successor, cost ): ...                          @staticmethod     def iterativeLengtheningGenerator ( successor, cost, anchor ): ...          @staticmethod     def aStarGenerator ( successor, cost, h ): ...

Snippet 3 - Final class split fulfilling all our design goals

This re-factoring forces us to update all our unit tests to adapt to the new classes. The update is no big deal, just slight modifications to the test code. For example:

initial = ...     goal = ...     cost = lambda s, n: ...     successor = lambda n: ...     h = lambda n: ...                 problem = Problem(initial, goal, successor, cost)              solver = ProblemSolver()     solver.solve(problem, ...)     self.assertTrue(solver.solved(problem))

Snippet 4 - Modified unit test code using the new class split

I specially love how much sense the solver.solved(problem) call seems to have. When calls to your interface seem to mean what they actually do, it's good sign that you're on the right track with your design.

The complete code for the re-factored search framework can be obtained here. As always, if you're actually leveraging this code in your designs please drop me a line so I know this work is being useful to someone else.

In the next post we'll implement Local Search and Optimization based problem solvers that enable us to solve problems in continuous spaces. I hope to see you there.