All about Informed Search in Artificial Intelligence

# All about Informed Search in Artificial Intelligence

Last updated:
21st Mar, 2023
Views
10 Mins
View All

Informed search is a type of search algorithm that uses domain-specific knowledge to guide its search through a problem space. From navigation systems to game playing, natural language processing to supply chain management and more–informed search in artificial intelligence has significantly reduced the amount of time and computational resources required to solve different problems.

By using domain-specific knowledge to guide the search, informed search algorithms can quickly eliminate irrelevant or less promising paths, allowing the search to focus on the most promising options. To do this, these types of search algorithms in AI use heuristics to improve the efficiency and speed of the search.

Enrol for the Machine Learning Course from the World’s top Universities. Earn Master, Executive PGP, or Advanced Certificate Programs to fast-track your career.

This article will discuss the concept of informed search in artificial intelligence, its heuristics functions, examples of algorithms, and their advantages and disadvantages.

## Heuristics function

In simple terms, a heuristic function is a problem-solving approach that uses a rule of thumb or a “best guess” to estimate the distance or cost to a goal state in a search problem. The heuristic function estimates how far away the goal state is from the current state, which can be used to guide a search algorithm toward the goal.

Informed search algorithms use these functions as an additional source of information to make informed decisions about which path to take. Because of this reason, heuristics functions are essential in informed search algorithms.

## Real-life examples of heuristics function

To understand heuristic functions better, here are some real-life examples:

• In the classic “sliding tile puzzle” game, a simple heuristic function could be to count the number of tiles out of place in the current configuration compared to the goal configuration. The more tiles out of place, the further away the current state is from the goal state.
• In chess, a heuristic function could be to assign a value to each piece on the board based on its relative strength and position and use the sum of those values to estimate the current player’s advantage or disadvantage. This heuristic function can be used to guide a search algorithm toward moves that are likely to result in a better position.

With that settled, let’s now move ahead and understand some of the most used examples of informed search algorithms in artificial intelligence.

## Examples of Informed Search Algorithms

Two of the most commonly used informed search algorithms include best first search and A* search. Let’s understand these two algorithms along with some examples, advantages, disadvantages, and their Python implementation:

### 1. Best First Search

The best first search is a search algorithm that expands the most promising node first, according to a heuristic function. The algorithm starts at the initial node and examines all its children nodes, choosing the child with the lowest heuristic value as the next node to explore. This process continues until the goal node is found or all nodes have been explored.

#### Best first search – an illustrated example

Here is a simple example to illustrate the best first search:

Suppose you are trying to find the shortest route from your home to a nearby grocery store. You know the distance to the grocery store from a few nearby locations, but you don’t know the exact route to take. To solve this problem using best-first search, you could:

1. Start at your home location and calculate the heuristic value for each nearby location based on its distance to the grocery store.
2. Choose the nearby location with the lowest heuristic value as the next node to explore.
3. Calculate the heuristic value for each of its children’s locations from that nearby location and choose the one with the lowest heuristic value as the next node to explore.
4. Repeat this process until you reach the grocery store.

#### Best first search – Python implementation

Here’s how you can implement the best first search algorithm in Python:

import heapq

def best_first_search(start_state, goal_state, heuristic_func, actions_func, cost_func):

# initialize the frontier and explored set

frontier = [(heuristic_func(start_state, goal_state), start_state)]

explored = set()

# initialize the path and cost

path = {}

cost = {}

path[start_state] = None

cost[start_state] = 0

while frontier:

# get the node with the lowest heuristic value from the frontier

(h, current_state) = heapq.heappop(frontier)

if current_state == goal_state:

# return the path if the goal state is reached

return path

# generate possible actions from the current state

for action in actions_func(current_state):

next_state = action(current_state)

# calculate the cost of the new path

new_cost = cost[current_state] + cost_func(current_state, action, next_state)

if next_state not in explored and next_state not in [state for (h, state) in frontier]:

# add the new state to the frontier

heapq.heappush(frontier, (heuristic_func(next_state, goal_state), next_state))

path[next_state] = current_state

cost[next_state] = new_cost

# return None if the goal state is not reachable

return None

As you can see, you will need to define the following functions:

• heuristic_func(current_state, goal_state): This function takes the current state and the goal state as inputs and returns an estimate of the cost of reaching the goal state from the current state.
• actions_func(current_state): This function takes the current state as input and returns a list of actions that can be taken from the current state.
• cost_func(current_state, action, next_state): This function takes the current state, an action, and the next state as inputs and returns the cost of taking action from the current state to the next state.

#### Example of Best First Search

start_state = (0, 0)

goal_state = (4, 4)

def heuristic_func(current_state, goal_state):

return abs(current_state[0] – goal_state[0]) + abs(current_state[1] – goal_state[1])

def actions_func(current_state):

actions = []

if current_state[0] > 0:

actions.append(lambda state: (state[0]-1, state[1]))

if current_state[0] < 4:

actions.append(lambda state: (state[0]+1, state[1]))

if current_state[1] > 0:

actions.append(lambda state: (state[0], state[1]-1))

if current_state[1] < 4:

actions.append(lambda state: (state[0], state[1]+1))

return actions

def cost_func(current_state, action, next_state):

return 1

path = best_first_search(start_state, goal_state, heuristic_func, actions_func, cost_func)

if path:

# construct the path from the start state to the goal state

current_state = goal_state

while current_state != start_state:

print(current_state)

current_state = path[current_state]

print(start_state)

else:

print(“Goal state is not reachable.”)

#### Advantages of Best First Search

• As compared to the breadth-first search, the time complexity of the best-first search is lower.
• The best first search obtains and implements the advantages of both the BFS and DFS algorithms

#### Disadvantages of Best First Search

• It can sometimes cover more distance than considered.
• The chances of getting stuck in a loop are highly likely.

### A* Search

A* search is a search algorithm that uses both the cost of reaching a node from the starting node and an estimate of the remaining cost to reach the goal node to guide its search. The algorithm starts at the initial node and examines all of its children nodes, choosing the child with the lowest combined cost and estimated remaining cost as the next node to explore. This process continues until the goal node is found or all nodes have been explored.

#### A* search – an illustrated example

Let’s re-look at the previous example of you trying to find the shortest route from your home to a nearby grocery store. Now, you could:

1. Start at your home location and calculate the total cost to reach each nearby location as the sum of the distance from your home to that location and the estimated remaining cost to reach the grocery store from that location.
2. Choose the nearby location with the lowest total cost as the next node to explore.
3. From that nearby location, calculate the total cost for each of its children locations as the sum of the distance from that location to the child location, the cost to reach that location from the start node, and the estimated remaining cost to reach the grocery store from that child location. Choose the child location with the lowest total cost as the next node to explore.
4. Repeat this process until you reach the grocery store.

An important thing to note here is that A* Search is an optimal search algorithm that guarantees to find the shortest path to the goal state. It’s efficient in problems with a large search space and is widely used in video games, robotics, and route planning. However, it requires a well-defined heuristic function to be effective. For this reason, the algorithm can be memory-intensive and slow down in complex problems with many nodes.

#### A* search – Python implementation

Here is how you can implement the A* search algorithm using Python programming:

import heapq

def astar_search(start_state, goal_state, heuristic_func, actions_func, cost_func):

# initialize the frontier and explored set

frontier = [(heuristic_func(start_state, goal_state), start_state)]

explored = set()

# initialize the path and cost

path = {}

cost = {}

path[start_state] = None

cost[start_state] = 0

while frontier:

# get the node with the lowest f-value from the frontier

(f, current_state) = heapq.heappop(frontier)

if current_state == goal_state:

# return the path if the goal state is reached

return path

# generate possible actions from the current state

for action in actions_func(current_state):

next_state = action(current_state)

# calculate the cost of the new path

new_cost = cost[current_state] + cost_func(current_state, action, next_state)

if next_state not in explored and next_state not in [state for (f, state) in frontier]:

# add the new state to the frontier

heapq.heappush(frontier, (new_cost + heuristic_func(next_state, goal_state), next_state))

path[next_state] = current_state

cost[next_state] = new_cost

elif next_state in [state for (f, state) in frontier] and new_cost < cost[next_state]:

# update the cost of the existing state in the frontier

index = [i for (i, (f, state)) in enumerate(frontier) if state == next_state][0]

frontier[index] = (new_cost + heuristic_func(next_state, goal_state), next_state)

path[next_state] = current_state

cost[next_state] = new_cost

# return None if the goal state is not reachable

return None

## Top Machine Learning and AI Courses Online

 Master of Science in Machine Learning & AI from LJMU Executive Post Graduate Programme in Machine Learning & AI from IIITB Advanced Certificate Programme in Machine Learning & NLP from IIITB Advanced Certificate Programme in Machine Learning & Deep Learning from IIITB Executive Post Graduate Program in Data Science & Machine Learning from University of Maryland To Explore all our certification courses on AI & ML, kindly visit our page below. Machine Learning Certification

#### Example of A* Search

Here’s an example of how you could use the astar_search function with these functions:

start_state = (0, 0)

goal_state = (4, 4)

def heuristic_func(current_state, goal_state):

return abs(current_state[0] – goal_state[0]) + abs(current_state[1] – goal_state[1])

def actions_func(current_state):

actions = []

if current_state[0] > 0:

actions.append(lambda state: (state[0]-1, state[1]))

if current_state[0] < 4:

actions.append(lambda state: (state[0]+1, state[1]))

if current_state[1] > 0:

actions.append(lambda state: (state[0], state[1]-1))

if current_state[1] < 4:

actions.append(lambda state: (state[0], state[1]+1))

return actions

def cost_func(current_state, action, next_state):

return 1

path = astar_search(start_state, goal_state, heuristic_func, actions_func, cost_func)

if path:

# construct the path from the start state to the goal state

current_state = goal_state

while current_state != start_state:

print(current_state)

current_state = path[current_state]

print(start_state)

else:

print(“Goal state is not reachable.”)

• It is one of the leading heuristic techniques.
• A* search can be leveraged to solve complex search problems

## Trending Machine Learning Skills

 AI Courses Tableau Certification Natural Language Processing Deep Learning AI

• A* search performance heavily relies on the accuracy of heuristics algorithms.
• Has low search efficiency.

## Popular AI and ML Blogs & Free Courses

 IoT: History, Present & Future Machine Learning Tutorial: Learn ML What is Algorithm? Simple & Easy Robotics Engineer Salary in India : All Roles A Day in the Life of a Machine Learning Engineer: What do they do? What is IoT (Internet of Things) Permutation vs Combination: Difference between Permutation and Combination Top 7 Trends in Artificial Intelligence & Machine Learning Machine Learning with R: Everything You Need to Know AI & ML Free Courses Introduction to NLP Fundamentals of Deep Learning of Neural Networks Linear Regression: Step by Step Guide Artificial Intelligence in the Real World Introduction to Tableau Case Study using Python, SQL and Tableau

## Take away

Informed search algorithms are essential in artificial intelligence since they allow the computer to search for a goal state efficiently and effectively. These algorithms use heuristics functions to estimate the cost of each possible move and guide the search process towards the goal state. Best First Search and A* Search are examples of informed search algorithms widely used in various fields. However, a well-defined heuristic function is critical to the success of informed search algorithms.

If you’re interested in learning more about artificial intelligence and machine learning, check out upGrad’s Masters in Machine Learning & Artificial Intelligence program offered by Liverpool John Moores University. This program covers various machine learning and AI topics, including algorithms like informed search. By taking this program, you can gain the skills and knowledge you need to succeed in a variety of AI-related careers.

You can also check out our free courses offered by upGrad in Management, Data Science, Machine Learning, Digital Marketing, and Technology. All of these courses have top-notch learning resources, weekly live lectures, industry assignments, and a certificate of course completion – all free of cost!

Blog Author
Director of Engineering @ upGrad. Motivated to leverage technology to solve problems. Seasoned leader for startups and fast moving orgs. Working on solving problems of scale and long term technology strategy.
Get Free Consultation

Select Course
Select
By clicking 'Submit' you Agree to

#### Our Popular Machine Learning Course

1What is the difference between informed and uninformed search algorithms?

Informed search algorithms use heuristic functions to guide the search process, whereas uninformed search algorithms do not. This means that informed search algorithms can be more efficient when searching for solutions to complex problems, as they can avoid exploring unpromising paths.

2How do you choose a good heuristic function for an informed search algorithm?

The heuristic function should be admissible, meaning it never overestimates the true cost of reaching the goal state. Ideally, the heuristic function should also be consistent, meaning that the estimated cost of reaching any successor state is never greater than the estimated cost of reaching the current state plus the cost of getting to the successor state.

3What are some limitations of informed search algorithms?

The quality of the heuristic function can limit informed search algorithms. The algorithm may perform poorly if the heuristic function is inaccurate or provides useful information. In addition, informed search algorithms can be computationally expensive, especially if the search space is large or the heuristic function is complex.

## Suggested Blogs

86557
AWS Projects & Topics Looking for AWS project ideas? Then you’ve come to the right place because, in this article, we’ve shared multiple AWS proj

19 Sep 2023

126790
Summary: In this article, you will learn about data preprocessing in Machine Learning: 7 easy steps to follow. Acquire the dataset Import all the cr

18 Sep 2023

61708
These days, the minute you indulge in any technology-oriented discussion, interview questions on cloud computing come up in some form or the other. Th

15 Sep 2023

302087
Summary: In this Article, you will learn Stock Prices Predictor Sports Predictor Develop A Sentiment Analyzer Enhance Healthcare Prepare ML Algorith

14 Sep 2023

40509
Introduction Machine Learning Interviews can vary according to the types or categories, for instance, a few recruiters ask many Linear Regression int

10 Sep 2023

4621
The topic of neural networks has captivated the world of artificial intelligence and machine learning with its ability to mimic the human brain’

07 Sep 2023

60648
What is a Raspberry Pi? The Raspberry Pi is a low-cost computer about the size of a credit card that can be connected to a display or TV and controll

06 Sep 2023

900153
Summary: In this article, you will learn about AWS Salary in India For Freshers & Experienced. AWS Salary in India INR 6,07,000 per annum AW