Heuristic Search Techniques in Artificial IntelligenceSearching and organizing data is an important topic within Artificial Intelligence.
There are many problems that require searching for an answer within the solution domain.
DammnnBlockedUnblockFollowFollowingMay 8There 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 algorithm can be developed to find the right solution.
Also, going through every single 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 our search is called heuristic search.
Heuristic techniques are very handy because they help us speed up the process.
Even if the heuristic is not able to completely eliminate some options, it will help us to order those options so that we are more likely to get to the better solutions first.
Uninformed versus Informed searchIf you are familiar with computer science, you should have heard about search techniques like Depth First Search (DFS), Breadth First Search (BFS), and Uniform Cost Search (UCS).
These are search techniques that are commonly used on graphs to get to the solution.
These are examples of uninformed search.
They do not use any prior information or rules to eliminate some paths.
They check all the plausible paths and pick the optimal one.
Heuristic search, on the other hand, is called Informed search because it uses prior information or rules to eliminate unnecessary paths.
Uninformed search techniques do not take the goal into account.
These techniques don’t really know where they are trying to go unless they just stumble upon the goal in the process.
In the graph problem, we can use heuristics to guide the search.
For example, at each node, we can define a heuristic function that returns a score that represents the estimate of the cost of the path from the current node to the goal.
By defining this heuristic function, we are informing the search technique about the right direction to reach the goal.
This will allow the algorithm to identify which neighbour will lead to the goal.
We need to note that heuristic search might not always find the most optimal solution.
This is because we are not exploring every single possibility and we are relying on a heuristic.
But it is guaranteed to find a good solution in a reasonable time, which is what we expect from a practical solution.
In real-world scenarios, we need solutions that are fast and effective.
Heuristic searches provide an efficient solution by arriving at a reasonable solution quickly.
They are used in cases where the problems cannot be solved in any other way or would take a really long time to solve.
Constraint Satisfaction ProblemsThere are many problems that have to 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).
CSPs are basically mathematical problems that are defined as a set of variables that must satisfy a number of constraints.
When we arrive at the final solution, the states of the variables must obey all the constraints.
This technique represents the entities involved in a given problem as a collection of a fixed number of constraints over variables.
These variables need to be solved by constraint satisfaction methods.
These problems require a combination of heuristics and other search techniques to be solved in a reasonable amount of time.
In this case, we will use constraint satisfaction techniques to solve problems on finite domains.
A finite domain consists of a finite number of elements.
Since we are dealing with finite domains, we can use search techniques to arrive at the solution.
Local search techniquesLocal search is a particular way of solving a CSP.
It keeps improving the values 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.
Local search algorithm is a 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 minimal cost update at each step.
Hill climbing is a popular local search technique.
It uses a heuristic function that measures the difference between the current state and the goal.
When we start, it checks if the state is the final goal.
If it is, then it stops.
If not, then it selects an update and generates a new state.
If it’s closer to the goal than the current state, then it makes that the current state.
If not, it ignores it and continues the process until it checks all possible updates.
It basically climbs the hill until it reaches the summit.
Simulated AnnealingSimulated Annealing is a type of local search as well as a stochastic search technique.
Stochastic search techniques are used extensively in various fields such as robotics, chemistry, manufacturing, medicine, economics, and so on.
We can perform things like optimizing the design of a robot, determining the timing strategies for automated control in factories, and planning traffic.
Stochastic algorithms are used to solve many real-world problems.
Simulated Annealing is a variation of the hill climbing technique.
One of the main problems of hill climbing is that it ends up climbing false foothills.
This means that it gets stuck in local maxima.
So it is better to check out the whole space before we make any climbing decisions.
In order to achieve this, the whole space is initially explored to see what it is like.
This helps us avoid getting stuck in a plateau or local maxima.
In Simulated Annealing, we reformulate the problem and solve it for minimization, as opposed to maximization.
So, we are now descending into valleys as opposed to climbing hills.
We are pretty much doing the same thing, but in a different way.
We use an objective function to guide the search.
This objective function serves as our heuristic.
The reason it is called Simulated Annealing is because it is derived from the metallurgical process.
We first heat metals up and then let them cool until they reach the optimal energy state.
The rate at which we cool the system is called the annealing schedule.
The rate of cooling is important because it directly impacts the final result.
In the real world case of metals, if the rate of cooling is too fast, it ends up settling for the local maximum.
For example, if we take the heated metal and put it in cold water, it ends up quickly settling for the sub-optimal local maximum.
If the rate of cooling is slow and controlled, we give the metal a chance to arrive at the globally optimum state.
The chances of taking big steps quickly towards any particular hill are lower in this case.
Since the rate of cooling is slow, it will take its time to choose the best state.
We do something similar with data in our case.
We first evaluate the current state and see if it is the goal.
If it is, then we stop.
If not, then we set the best state variable to the current state.
We then define our annealing schedule that controls how quickly it descends into a valley.
We compute the difference between the current state and the new state.
If the new state is not better, then we make it the current state with a certain predefined probability.
We do this using a random number generator and making a decision based on a threshold.
If it is above the threshold, then we set the best state to this state.
Based on this, we update the annealing schedule depending on the number of nodes.
We keep doing this until we arrive at the goal.
Constructing a string using a greedy searchGreedy 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 would ask you to take routes that are shorter but might end up taking more time.
It can 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 think about the next step and not the globally optimal final solution.
Let’s see how to solve a problem using a greedy search.
In this problem, we will try to recreate the input string based on the alphabets.
We will ask the algorithm to search the solution space and construct a path to the solution.
We will be using a package called simpleai throughout this chapter.
It contains various routines that are useful in building solutions using heuristic search techniques.
It's available at https://github.
com/simpleai-team/simpleai.
We need to make a few changes to the source code in order to make it work in Python3.
A file called simpleai.
zip has been provided along with the code for the book.
Unzip this file into a folder called simpleai.
This folder contains all the necessary changes to the original library necessary to make it work in Python3.
Place the simpleai folder in the same folder as your code and you'll be able to run your code smoothly.
Create a new Python file and import the following packages:import argparse import simpleai.
search as ssDefine a function to parse the input arguments:def build_arg_parser(): parser = argparse.
ArgumentParser(description='Creates the input string using the greedy algorithm') parser.
add_argument("–input-string", dest="input_string", required=True, help="Input string") parser.
add_argument("–initial-state", dest="initial_state", required=False, default='', help="Starting point for the search") return parserCreate a class that contains the methods needed to solve the problem.
This class inherits the SearchProblem class available in the library.
We just need to override a couple of methods to suit our needs.
The first method set_target is a custom method that we define to set the target string:class CustomProblem(ss.
SearchProblem): def set_target(self, target_string): self.
target_string = target_stringThe actions is a method that comes with a SearchProblem and we need to override it.
It's responsible for taking the right steps towards the goal.
If the length of the current string is less than the length of the target string, it will return the list of possible alphabets to choose from.
If not, it will return an empty string:# Check the current state and take the right action def actions(self, cur_state): if len(cur_state) < len(self.
target_string): alphabets = 'abcdefghijklmnopqrstuvwxyz' return list(alphabets + ' ' + alphabets.
upper()) else: return []a method to compute the result by concatenating the current string and the action that needs to be taken.
This method comes with a SearchProblem and we are overriding it:# Concatenate state and action to get the result def result(self, cur_state, action): return cur_state + actionThe method is_goal is a part of the SearchProblem and it's used to check if we have arrived at the goal:# Check if goal has been achieved def is_goal(self, cur_state): return cur_state == self.
target_stringThe method heuristic is also a part of the SearchProblem and we need to override it.
We will define our own heuristic that will be used to solve the problem.
We will calculate how far we are from the goal and use that as the heuristic to guide it towards the goal:# Define the heuristic that will be used def heuristic(self, cur_state): # Compare current string with target string dist = sum([1 if cur_state[i] != self.
target_string[i] else 0 for i in range(len(cur_state))]) # Difference between the lengths diff = len(self.
target_string) – len(cur_state) return dist + diffe input arguments:if __name__=='__main__': args = build_arg_parser().
parse_args()Initialize the CustomProblem object:# Initialize the object problem = CustomProblem()Set the starting point as well as the goal we want to achieve:# Set target string and initial state problem.
set_target(args.
input_string) problem.
initial_state = args.
initial_stateRun the solver:# Solve the problem output = ss.
greedy(problem)Print the path to the solution:print('.Target string:', args.
input_string) print('.Path to the solution:') for item in output.
path(): print(item)The full code is given in the file greedy_search.
py.
If you run the code with an empty initial state:$ python3 greedy_search.
py –input-string 'Artificial Intelligence' –initial-state ''You will get the following output:If you run the code with a non-empty starting point:$ python3 greedy_search.
py –input-string 'Artificial Intelligence with Python' –initial-state 'Artificial Inte'You will get the following output:Solving a problem with constraintsWe have already discussed how Constraint Satisfaction Problems are formulated.
Let’s apply them to a real-world problem.
In this problem, we have a list of names and each name can only 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_VALUEDefine 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 second variable:# Constraint that specifies that one variable # should be bigger than other def constraint_bigger(variables, values): return values[0] > values[1]Define the constraint that specifies that if the first variable is odd, then the second variable should be even and vice versa:# Constraint that specifies that there should be # one odd and one even variables in the two variables def constraint_odd_even(variables, values): # If first variable is even, then second should # be odd and vice versa if values[0] % 2 == 0: return values[1] % 2 == 1 else: return values[1] % 2 == 0Define the main function and define the variables:if __name__=='__main__': variables = ('John', 'Anna', 'Tom', 'Patricia')Define the list of values that each variable can take:domains = { 'John': [1, 2, 3], 'Anna': [1, 3], 'Tom': [2, 4], 'Patricia': [2, 3, 4], }Define the constraints for various scenarios.
In this case, we specify three constraints as follows:John, Anna, and Tom should have different valuesTom’s value should be bigger than Anna’s valueIf John’s value is odd, then Patricia’s value should be even and vice versaUse the following code:constraints = [ (('John', 'Anna', 'Tom'), constraint_unique), (('Tom', 'Anna'), constraint_bigger), (('John', 'Patricia'), constraint_odd_even), ]Use the preceding variables and the constraints to initialize the CspProblemobject:problem = CspProblem(variables, domains, constraints)Compute the solution and print it:print('.Solutions:.Normal:', backtrack(problem))Compute the solution using the MOST_CONSTRAINED_VARIABLE heuristic:print('.Most constrained variable:', backtrack(problem, variable_heuristic=MOST_CONSTRAINED_VARIABLE))Compute the solution using the HIGHEST_DEGREE_VARIABLE heuristic:print('.Highest degree variable:', backtrack(problem, variable_heuristic=HIGHEST_DEGREE_VARIABLE))Compute the solution using the LEAST_CONSTRAINING_VALUE heuristic:print('.Least constraining value:', backtrack(problem, value_heuristic=LEAST_CONSTRAINING_VALUE))Compute the solution using the MOST_CONSTRAINED_VARIABLE variable heuristic and LEAST_CONSTRAINING_VALUE value heuristic:print('.Most constrained variable and least constraining value:', backtrack(problem, variable_heuristic=MOST_CONSTRAINED_VARIABLE, value_heuristic=LEAST_CONSTRAINING_VALUE))Compute the solution using the HIGHEST_DEGREE_VARIABLE variable heuristic and LEAST_CONSTRAINING_VALUE value heuristic:print('.Highest degree and least constraining value:', backtrack(problem, variable_heuristic=HIGHEST_DEGREE_VARIABLE, value_heuristic=LEAST_CONSTRAINING_VALUE))Compute the solution using the minimum conflicts heuristic:print('.Minimum conflicts:', min_conflicts(problem))If you run the code, you will get the following output:You can check the constraints to see if the solutions satisfy all those constraints.
Solving the region-colouring problemLet’s use the Constraint Satisfaction framework to solve the region-colouring problem.
Consider the following screenshot:We have a few regions in the preceding figure that are labeled with names.
Our 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, backtrackDefine 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', 'Joanne', 'Derek', 'Allan', 'Michelle', 'Kelly')Define the list of possible colors:# Define the possible colors colors = dict((name, ['red', 'green', 'blue', 'gray']) for name in names)We need to convert the map information into something that the algorithm can understand.
Let’s define the constraints by specifying the list of people who are adjacent to each other:# Define the constraints constraints = [ (('Mark', 'Julia'), constraint_func), (('Mark', 'Steve'), constraint_func), (('Julia', 'Steve'), constraint_func), (('Julia', 'Amanda'), constraint_func), (('Julia', 'Derek'), constraint_func), (('Julia', 'Brian'), constraint_func), (('Steve', 'Amanda'), constraint_func), (('Steve', 'Allan'), constraint_func), (('Steve', 'Michelle'), constraint_func), (('Amanda', 'Michelle'), constraint_func), (('Amanda', 'Joanne'), constraint_func), (('Amanda', 'Derek'), constraint_func), (('Brian', 'Derek'), constraint_func), (('Brian', 'Kelly'), constraint_func), (('Joanne', 'Michelle'), constraint_func), (('Joanne', 'Amanda'), constraint_func), (('Joanne', 'Derek'), constraint_func), (('Joanne', 'Kelly'), constraint_func), (('Derek', 'Kelly'), constraint_func), ]Use the variables and constraints to initialize the object:# Solve the problem problem = CspProblem(names, colors, constraints)Solve the problem and print the solution:# Print the solution output = backtrack(problem) print('.Color mapping:. More details