Heuristic Search Techniques

In this chapter, we are going to learn about heuristic search techniques. Heuristic search techniques are used to search through the solution space to come up with answers. The search is conducted using heuristics that guide the search algorithm. This heuristic allows the algorithm to speed up the process, which would otherwise take a long time to arrive at the solution.

By the end of this chapter, you will know about the following:

• What is heuristic search?
• Uninformed vs. informed search
• Constraint satisfaction problems
• Local search techniques
• Simulated annealing
• Constructing a string using greedy search
• Solving a problem with constraints
• Solving the region coloring problem
• Building an 8-puzzle solver
• Building a maze solver

Is heuristic search artificial intelligence?

In Chapter 2, Fundamental Use Cases for Artificial Intelligence, we learned about the five tribes as defined by Pedro Domingos. One of the most "ancient" tribes is the symbolist tribe. At least to me, this fact is not surprising. As humans, we try to find rules and patterns in everything. Unfortunately, the world is sometimes messy and not everything follows simple rules.

This is the reason why other tribes emerged to help us when we don't have an orderly world. However, when our search spaces are small and the domain is limited, using heuristics, constraint satisfaction, and other techniques laid out in this chapter, is useful for this set of problems. These techniques are useful when the number of combinations is relatively small and combinatorial explosion is limited. For example, solving the traveling salesman problem is simple with these techniques when the number of cities is around 20. If we try to solve the...

What is heuristic search?

Searching and organizing data is an important topic within artificial intelligence. There are many problems that require searching for an answer within the solution domain. There are many possible solutions to a given problem and we do not know which ones are correct. By efficiently organizing the data, we can search for solutions quickly and effectively.

More often, there are so many possible options to solve a given problem that no single algorithm can be developed to find a definite best solution. Also, going through every solution is not possible because it is prohibitively expensive. In such cases, we rely on a rule of thumb that helps us narrow down the search by eliminating the options that are obviously wrong. This rule of thumb is called a heuristic. The method of using heuristics to guide the search is called heuristic search.

Heuristic techniques are powerful because they speed up the process. Even if the heuristic is not able to eliminate...

Constraint satisfaction problems

There are many problems that must be solved under constraints. These constraints are basically conditions that cannot be violated during the process of solving the problem.

These problems are referred to as Constraint Satisfaction Problems (CSPs).

To gain some intuitive understanding, let's quickly look at an example section of a Sudoku puzzle. Sudoku is a game where we cannot have the same number twice across a horizontal line, vertical line, or in the same square. Here is an example Sudoku board:

Figure 1: Example of a Sudoku board

Using constraint satisfaction and the rules of Sudoku we can quickly determine which numbers to try and which numbers not to try to solve the puzzle. For example, in this square:

Figure 2: Considering a problem in Sudoku

If we were not using CSP, one brute force approach would be to try all of the combinations of numbers in the slots and then check if the rules applied. For example, our...

Local search techniques

Local search is a way of solving a CSP. It keeps optimizing the solution until all the constraints are satisfied. It iteratively keeps updating the variables until we arrive at the destination. These algorithms modify the value during each step of the process that gets us closer to the goal. In the solution space, the updated value is closer to the goal than the previous value. Hence, it is known as a local search.

A local search algorithm is a type of heuristic search algorithm. These algorithms use a function that calculates the quality of each update. For example, it can count the number of constraints that are being violated by the current update or it can see how the update affects the distance to the goal. This is referred to as the cost of the assignment. The overall goal of local search is to find the minimum cost update at each step.

Hill climbing is a popular local search technique. It uses a heuristic function that measures the difference...

Constructing a string using greedy search

Greedy search is an algorithmic paradigm that makes the locally optimal choice at each stage in order to find the global optimum. But in many problems, greedy algorithms do not produce globally optimum solutions. An advantage of using greedy algorithms is that they produce an approximate solution in a reasonable time. The hope is that this approximate solution is reasonably close to the global optimal solution.

Greedy algorithms do not refine their solutions based on new information during the search. For example, let's say you are planning on a road trip and you want to take the best route possible. If you use a greedy algorithm to plan the route, it might ask you to take routes that are have a shorter distance but might end up taking more time. It may also lead you to paths that may seem faster in the short term but might lead to traffic jams later. This happens because greedy algorithms only see the next step and not the globally...

Solving a problem with constraints

We have already discussed how CSPs are formulated. Let's apply them to a real-world problem. In this problem, we have a list of names and each name can take a fixed set of values. We also have a set of constraints between these people that needs to be satisfied. Let's see how to do it.

Create a new Python file and import the following packages:

from simpleai.search import CspProblem, backtrack, \
        min_conflicts, MOST_CONSTRAINED_VARIABLE, \
        HIGHEST_DEGREE_VARIABLE, LEAST_CONSTRAINING_VALUE

Define the constraint that specifies that all the variables in the input list should have unique values:

# Constraint that expects all the different variables 
# to have different values
def constraint_unique(variables, values):
    # Check if all the values are unique
    return len(values) == len(set(values))

Define the constraint that specifies that the first variable should be bigger than the...

Solving the region-coloring problem

Let's use the constraint satisfaction framework to solve the region-coloring problem. Consider the following screenshot:

Figure 7: Framework for the region-coloring problem

We have a few regions in the preceding figure that are labeled with names. The goal is to color with four colors so that no adjacent regions have the same color.

Create a new Python file and import the following packages:

from simpleai.search import CspProblem, backtrack

Define the constraint that specifies that the values should be different:

# Define the function that imposes the constraint 
# that neighbors should be different
def constraint_func(names, values):
    return values[0] != values[1]

Define the main function and specify the list of names:

if __name__=='__main__':
    # Specify the variables
    names = ('Mark', 'Julia', 'Steve', 'Amanda', 'Brian',
        ...

Building an 8-puzzle solver

The 8-puzzle is a variant of the 15-puzzle. You can check it out at https://en.wikipedia.org/wiki/15_puzzle. You will be presented with a randomized grid and your goal is to get it back to the original ordered configuration. You can play the game to get familiar with it at http://mypuzzle.org/sliding.

We will use an A* algorithm to solve this problem. It is an algorithm that's used to find paths to the solution in a graph. This algorithm is a combination of Dijkstra's algorithm and a greedy best-first search. Instead of blindly guessing where to go next, the A* algorithm picks the one that looks the most promising. At each node, the list of all possibilities is generated and then the one with the minimal cost required to reach the goal is picked.

Let's see how to define the cost function. At each node, the cost needs to be computed. This cost is basically the sum of two costs – the first cost is the cost of getting to the...

Building a maze solver

Let's use the A* algorithm to solve a maze. Consider the following figure:

Figure 12: Example of a maze problem

The # symbols indicate obstacles. The symbol o represents the starting point, and x represents the goal. The goal is to find the shortest path from the start to the end point. Let's see how to do it in Python. The following solution is a variant of the solution provided in the simpleai library. Create a new Python file and import the following packages:

import math
from simpleai.search import SearchProblem, astar

Create a class that contains the methods needed to solve the problem:

# Class containing the methods to solve the maze 
class MazeSolver(SearchProblem):

Define the initializer method:

    # Initialize the class
    def __init__(self, board):
        self.board = board
        self.goal = (0, 0)

Extract the initial and final positions:

        for y in range(len(self.board)):
 ...

Summary

In this chapter, we learned how heuristic search techniques work. We discussed the difference between uninformed and informed searches. We learned about constraint satisfaction problems and how we can solve problems using this paradigm. We discussed how local search techniques work and why simulated annealing is used in practice. We implemented a greedy search for a string problem. We solved a problem using the CSP formulation.

We used this approach to solve the region-coloring problem. We then discussed the A* algorithm and how it can used to find the optimal paths to the solution. We used it to build an 8-puzzle solver as well as a maze solver. In the next chapter, we will discuss genetic algorithms and how they can used to solve real-world problems.