Informed Search Methods

Continuing from my last post, I have been dealing with the 4th chapter in AIAMA book which is on informed search methods. Informed search methods use heuristic functions to guide them to goal states quicker so Search.SearcProblem class takes a list of heuristic functions for the problem and in order to use informed search methods you need to provide at least one heuristic function. Heuristic functions provided are assumed to be admissible since this is necessary for some informed search methods to produce optimal solutions. If multiple heuristic functions are given, dominating one (which yields a bigger heuristic value) is used for each node. In order to ensure monotonicity, if a child node’s total estimated path cost (sum of actual path cost so far and heuristic value for that node) is less than its parent’s, its parent’s total path cost is used which is called pathmax equation.
I have added the following search methods to the Search module I have implemented.

• Greedy Search: This method only uses the heuristic function to guide the search procedure.
• A* Search: A* uses total estimated path cost (sum of path cost so far and heuristic value) to choose the next node to expand. This simple search method is both complete and optimal making it one of the most important methods.
• Iterative Deepening A* Search: Like the counterpart in uninformed methods, IDA* runs multiple consecutive A* methods each covering more of the search space. However, A* uses a limit on the total estimated path cost not the search tree depth as it was in IDS.

For testing the code and demonstration, I have added heuristic functions for the two problems that I have implemented earlier and solved them with informed methods. I have also included very primitive GUIs for these problems where a random problem is drawn onto window and can be solved with the Solve button.

Misplaced tiles and Manhattan Distance heuristics are implemented for 8Puzzle problem. A sample code and screenshot of GUI can be seen below.

    initialGrid = list(range(9))
    random.shuffle(initialGrid)
    initialState = EightPuzzleState(initialGrid)
    operators = []
    operators.append(Search.Operator("Move Blank Left", MoveBlankLeft))
    operators.append(Search.Operator("Move Blank Right", MoveBlankRight))
    operators.append(Search.Operator("Move Blank Up", MoveBlankUp))
    operators.append(Search.Operator("Move Blank Down", MoveBlankDown))
    problem = Search.SearchProblem(initialState, operators, EightPuzzleGoalTest, None, [MisplacedTilesHeuristic, ManhattanDistanceHeuristic]) 
    node = problem.IterativeDeepeningAStarSearch()
    for n in problem.GetSolutionPath(node):
        print(n)

Note that some of the randomly generated puzzled are inherently hard and can take a long time to solve it. But worse is that some of the puzzles cannot be solved at all but program will try to find a solution and will probably crash. Take a look at the article on N-Puzzle in Wikipedia for a detailed analysis of this puzzle.
The other search problem you can find in source code is yet another famous problem, Traveling Salesman Problem (TSP). I have implemented minimum spanning tree construction with Prim’s algorithm and used the total cost of tree as a heuristic value for TSP. Below you can see the sample code and screenshot.

    tsp = TSP(15)
    initialState = TSPState([], 0, [], tsp)
    operators = []
    operators.append(Search.Operator("Add new edge", TSPGenerateNewStates))
    problem = Search.SearchProblem(initialState, operators, TSPGoalTest, TSPPathCost, [CalculateMinimumSpanningTreeCost])
    node = problem.AStarSearch()
    print(node)

As usual, all source code is implemented with Python 3.1 and I have used Tk for GUI programming.
I’d be happy to hear your questions, comments & suggestions.
Source Code Download

Uninformed Search and Constraint Satisfaction Problems

Recently, I’ve been busy with the exercises in Artificial Intelligence: A Modern Approach by Russell and Norvig. Third chapter of the book is on uninformed search methods and constraint satisfaction problems. I have implemented a class base that provides capabilities to define various search,  constraint satisfaction problems (CSP) and solve them. I aimed for an implementation that follows the approach in book (I have the 1st edition) closely and tried to make sure that each algorithm resembles the given pseudocodes. Performance was not a consideration for me so there are many different ways to implement better performing code and actually there are already many different libraries available for search and CSPs. All code is implemented in Python3.1.

I have implemented a SearchProblem class that can be used to solve a search problem. A search problem is defined with the following components;

• Initial State: Starting state for the problem. To be able to solve a problem, we need to find a state representation and define it. This is achieved by sub-classing Search.State class and implementing a few necessary methods.
• Operators: Operators generate new states from a given state. Operators are given as functions that return new states from a given one.
• Goal Test: Goal test checks a state and tells if we reached our goal and can stop searching. This is also implemented as a function that takes a state as parameter and returns a boolean value
• Path Cost Function: Although not necessary for every problem, path cost function gives a cost value for getting to a state from another state. If necessary, a path cost function should take two states as input and return a numeric value representing cost.

Different uninformed search methods are implemented.

• Depth-First
• Breadth-First
• Uniform Cost
• Depth Limited
• Iterative Deepening

For example, for the famous missionaries and cannibals problem, after defining necessary classes and methods following piece of code solves it with breadth-first search. (Details of the implementation can be found in the source code at the end of post)

     """
    Problem Definition
    """
    # operators
    operators = []
    operators.append(Search.Operator("Move 2 M", Move2MAcross))
    operators.append(Search.Operator("Move 1 M", Move1MAcross))
    operators.append(Search.Operator("Move 2 C", Move2CAcross))
    operators.append(Search.Operator("Move 1 C", Move1CAcross))
    operators.append(Search.Operator("Move 1 M 1 C", Move1M1CAcross))

    # create initial state
    initialState = MCState(3, 3, 1)

    # define problem
    MCProblem = Search.SearchProblem(initialState, operators, MCGoalTest)

    node = MCProblem.BreadthFirstSearch()
    solution = MCProblem.GetSolutionPath(node)
    for n in solution:
        print(n)

Solution found;

State: 3M 3C |B-| 0M 0C, Depth: 0, Path Cost: 0, Applied Operator: None
State: 3M 1C |-B| 0M 2C, Depth: 1, Path Cost: 1, Applied Operator: Move 2 C
State: 3M 2C |B-| 0M 1C, Depth: 2, Path Cost: 2, Applied Operator: Move 1 C
State: 3M 0C |-B| 0M 3C, Depth: 3, Path Cost: 3, Applied Operator: Move 2 C
State: 3M 1C |B-| 0M 2C, Depth: 4, Path Cost: 4, Applied Operator: Move 1 C
State: 1M 1C |-B| 2M 2C, Depth: 5, Path Cost: 5, Applied Operator: Move 2 M
State: 2M 2C |B-| 1M 1C, Depth: 6, Path Cost: 6, Applied Operator: Move 1 M 1 C
State: 0M 2C |-B| 3M 1C, Depth: 7, Path Cost: 7, Applied Operator: Move 2 M
State: 0M 3C |B-| 3M 0C, Depth: 8, Path Cost: 8, Applied Operator: Move 1 C
State: 0M 1C |-B| 3M 2C, Depth: 9, Path Cost: 9, Applied Operator: Move 2 C
State: 1M 1C |B-| 2M 2C, Depth: 10, Path Cost: 10, Applied Operator: Move 1 M
State: 0M 0C |-B| 3M 3C, Depth: 11, Path Cost: 11, Applied Operator: Move 1 M 1 C

I have implemented necessary state classes, operators and goal tests for the following problems; chain problem (exercise 3.15), sequence prediction problem (exercise 3.16) and 8 Puzzle.

For CSPs, there is no need to define specific state classes for each problem. CSPs are defined with their variables, their domains and constraints. Since CSP is actually a more specific version of a search problem, I have tried to re-use code implemented for search problem as much as possible. CSP class is initialized with variables, their domains and constraint functions and it converts the problem to a search problem, uses depth-first search to solve it. Forward checking is also implemented where a function that returns the illegal values for a specific assignment of variables should be given to CSP class.

For 8-queens problem, following code implements the constraints, forward checking function, defines a CSP and solves it.

import itertools
import CSP

def CheckConstraints(state):
    # for every pair of queen
    for s1, s2 in itertools.combinations(state.assignments.keys(), 2):
        #if 2 queens are on the same column
        if state.assignments[s1] == state.assignments[s2]:
            return False
        #if 2 queens are attacking each other diagonally
        rowDiff = ord(s2)-ord(s1)
        if state.assignments[s1] + rowDiff == state.assignments[s2] or state.assignments[s1] - rowDiff == state.assignments[s2]:
            return False
    return True

def ForwardChecking(state, val):
    """
    Return a dictionary of illegal values for each unassigned variable
    """
    # find unassigned variables
    unassignedVars = list(state.varList)
    [ unassignedVars.remove(k) for k in state.assignments.keys() ]
    # nextVariable is being assigned right now it is not an unassigned variable
    unassignedVars.remove(state.nextVariable)
    # dictionary that holds values to be removed for each variable
    removeVals = {}
    # for every unassigned variable, construct a list of values to be removed
    for v in unassignedVars:
        vals = []
        # two queens can't be on same column
        vals.append(val)
        # add diagonal positions if they are inside boundaries of chess board
        rowDiff = ord(v)-ord(state.nextVariable)
        if val+rowDiff > 0 and val+rowDiff <= 8:
            vals.append(val+rowDiff)
        if val-rowDiff > 0 and val-rowDiff <= 8:
            vals.append(val-rowDiff)
        removeVals[v] = vals
    return removeVals

if __name__ == '__main__':
    varsAndDomains = {('A','B','C','D','E','F','G','H'):[1,2,3,4,5,6,7,8]}
    csp = CSP.CSP(varsAndDomains, [CheckConstraints], ForwardChecking)
    node = csp.Solve()
    print(node)

Solution found for the problem (each letter corresponds to a row on chess board and values are columns where queen is located);

State: {'A': 1, 'C': 8, 'B': 5, 'E': 3, 'D': 6, 'G': 2, 'F': 7, 'H': 4}, Depth: 8, Path Cost: 8, Applied Operator: Assign Value

You can also find definition of a cryptarithmetic problem given in the book in source code.

Source Code

Feel free to contact me for any bug reports, suggestions and I’d be glad to answer your questions.