×

Heuristic Functions in Artificial Intelligence

Heuristic Functions in AI: As we have already seen that an informed search make use of heuristic functions in order to reach the goal node in a more prominent way. Therefore, there are several pathways in a search tree to reach the goal node from the current node. The selection of a good heuristic function matters certainly. A good heuristic function is determined by its efficiency. More is the information about the problem, more is the processing time.

Some toy problems, such as 8-puzzle, 8-queen, tic-tac-toe, etc., can be solved more efficiently with the help of a heuristic function. Let’s see how:

Consider the following 8-puzzle problem where we have a start state and a goal state. Our task is to slide the tiles of the current/start state and place it in an order followed in the goal state. There can be four moves either left, right, up, or down. There can be several ways to convert the current/start state to the goal state, but, we can use a heuristic function h(n) to solve the problem more efficiently.

heuristic function for the 8-puzzle problem

A heuristic function for the 8-puzzle problem is defined below:

h(n)=Number of tiles out of position.

So, there is total of three tiles out of position i.e., 6,5 and 4. Do not count the empty tile present in the goal state). i.e. h(n)=3. Now, we require to minimize the value of h(n) =0.

We can construct a state-space tree to minimize the h(n) value to 0, as shown below:

heuristic function for the 8-puzzle problem 2

It is seen from the above state space tree that the goal state is minimized from h(n)=3 to h(n)=0. However, we can create and use several heuristic functions as per the reqirement. It is also clear from the above example that a heuristic function h(n) can be defined as the information required to solve a given problem more efficiently. The information can be related to the nature of the state, cost of transforming from one state to another, goal node characterstics, etc., which is expressed as a heuristic function.

Properties of a Heuristic search Algorithm

Use of heuristic function in a heuristic search algorithm leads to following properties of a heuristic search algorithm:

  • Admissible Condition: An algorithm is said to be admissible, if it returns an optimal solution.
  • Completeness: An algorithm is said to be complete, if it terminates with a solution (if the solution exists).
  • Dominance Property: If there are two admissible heuristic algorithms A1 and A2 having h1 and h2 heuristic functions, then A1 is said to dominate A2  if h1 is better than h2 for all the values of node n.
  • Optimality Property: If an algorithm is complete, admissible, and dominating other algorithms, it will be the best one and will definitely give an optimal solution.

Related Topics

Artificial Intelligence vs. Machine learning

Artificial Intelligence This word is trending in the world of technology. Artificial means something which was not present naturally, and it is built by humans, and intelligence means the ability to...

4 minutes read.

Quantifying Uncertainty

The concept of quantifying uncertainty relies on how an agent can keep away uncertainty with a degree of belief. The term uncertainty refers to that situation or information which is either unknown or...

5 minutes read.

Top 7 Artificial Intelligence and Machine Learning trends for 2024

Artificial Intelligence is the ability of machines to perform the same function as human beings, like problem-solving, learning, reasoning and recognizing. Machine Learning is another branch of Computer Science and...

6 minutes read.

Backward Chaining in AI: Artificial Intelligence

Backward Chaining is a backward approach which works in the backward direction. It begins its journey from the back of the goal. Like, forward chaining, we have backward chaining for Propositional logic as...

6 minutes read.

Information Retrieval

Information Retrieval: In order to analyze and categorize the text, we'd like to be able to figure out information about the text, some meaning about the text as well. And,...

14 minutes read.

Supervised Learning in AI

Supervised Learning in AI Learning Supervised LearningClassification TasksNearest Neighbor ClassificationK nearest neighbor AlgorithmPerceptron LearningSupport Vector MachineRegression TasksLoss FunctionOverfittingRegularizationScikit LearnK Nearest Neighbor ImplementationPerceptron Algorithm ImplementationSupport Vector Machine Algorithm ImplementationRegression Implementation Machine Learning In the Artificial...

33 minutes read.

Unsupervised Learning in AI

Unsupervised Learning in AI Unsupervised LearningIntroductionClusteringComparison between Supervised, Unsupervised, and Reinforcement Learning. Unsupervised Learning This is the third major category of Machine Learning. Unsupervised learning happens when we have data without additional feedback,...

2 minutes read.

Cryptarithmetic Problem in AI

Cryptarithmetic Problem Cryptarithmetic Problem is a type of constraint satisfaction problem where the game is about digits and its unique replacement either with alphabets or other symbols. In cryptarithmetic problem, the...

3 minutes read.

Top 10 Artificial Intelligence Technologies in 2024

Artificial Intelligence Technologies in 2020 1. Augmented Reality This is one of the most fascinating technology nowadays. Augmented Reality is the use of text, graphics, audio, etc. in real time. In Simple...

4 minutes read.

Intelligent Agents | Agents in AI

What is an Agent? An agent can be viewed as anything that perceives its environment through sensors and acts upon that environment through actuators. For example, human being perceives their surroundings through...

8 minutes read.

Problem-solving in Artificial Intelligence

The reflex agents are known as the simplest agents because they directly map states into actions. Unfortunately, these agents fail to operate in an environment where the mapping is too large to...

7 minutes read.

Artificial Satellites

Many objects like stars, satellites and the moon are visible in the night sky. Satellites are objects revolving around the planet or a more significant object. Moon is the most...

6 minutes read.

Artificial Intelligence Tutorial | AI Tutorial

Today, Artificial Intelligence (AI) has become the norm of how humans communicate with and understand technology. Even though you've been hearing this buzzword now and then, do you know what...

6 minutes read.

The Wumpus World

The Wumpus world is a game playing which provides an environment to the knowledge-based agent to showcase its stored knowledge. It was developed by Gregory Yob in 1973. About the game:  It...

3 minutes read.

Reinforcement Learning in AI

Reinforcement Learning in AI Reinforcement LearningMarkov’s Decision ProcessQ leaningGreedy Decision MakingNIM GameNIM Game Implementation with Python Reinforcement Learning Reinforcement Learning is about learning from experience, where agents are given a set of rewards...

15 minutes read.

Knowledge Based Agents in AI

Knowledge is the basic element for a human brain to know and understand the things logically. When a person becomes knowledgeable about something, he is able to do that thing in a better...

4 minutes read.

Propositional Logic

It is a branch of logic which is also known as statement logic, sentential logic, zeroth-order logic, and many more. It works with the propositions and its logical connectivities. It deals with the...

5 minutes read.

Constraint Satisfaction Problems in Artificial Intelligence

Constraint Satisfaction Problems in Artificial Intelligence We have seen so many techniques like Local search, Adversarial search to solve different problems. The objective of every problem-solving technique is one, i.e., to find a solution to...

5 minutes read.

Integration of Blockchain and Artificial Intelligence

A Blockchain is a shared database or ledger where pieces of data are stored in data structures known as blocks. So, we can say that Blockchain is the distribution storage...

6 minutes read.

Hidden Markov Models

Hidden Markov Model is a partially observable model, where the agent partially observes the states. This model is based on the statistical Markov model, where a system being modeled follows the Markov process...

4 minutes read.