Blog_Banner_Asset
    Homebreadcumb forward arrow iconBlogbreadcumb forward arrow iconArtificial Intelligencebreadcumb forward arrow iconAll about Informed Search in Artificial Intelligence

All about Informed Search in Artificial Intelligence

Last updated:
21st Mar, 2023
Views
Read Time
10 Mins
share image icon
In this article
Chevron in toc
View All
All about Informed Search in Artificial Intelligence

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.

Ads of upGrad blog

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

        explored.add(current_state)

        # 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

        explored.add(current_state)

        # 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

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.”)

Advantages of A* Search

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

Trending Machine Learning Skills

Disadvantages of A* Search

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

Popular AI and ML Blogs & Free Courses

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.

Ads of upGrad blog

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!

 

Profile

Pavan Vadapalli

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 Coursecaret down icon
Selectcaret down icon
By clicking 'Submit' you Agree to  
UpGrad's Terms & Conditions

Our Popular Machine Learning Course

Frequently Asked Questions (FAQs)

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.

Explore Free Courses

Suggested Blogs

Artificial Intelligence course fees
5219
Artificial intelligence (AI) was one of the most used words in 2023, which emphasizes how important and widespread this technology has become. If you
Read More

by venkatesh Rajanala

29 Feb 2024

Artificial Intelligence in Banking 2024: Examples &#038; Challenges
5720
Introduction Millennials and their changing preferences have led to a wide-scale disruption of daily processes in many industries and a simultaneous g
Read More

by Pavan Vadapalli

27 Feb 2024

Top 9 Python Libraries for Machine Learning in 2024
75264
Machine learning is the most algorithm-intense field in computer science. Gone are those days when people had to code all algorithms for machine learn
Read More

by upGrad

19 Feb 2024

Top 15 IoT Interview Questions &#038; Answers 2024 – For Beginners &#038; Experienced
64237
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
Read More

by Kechit Goyal

19 Feb 2024

Data Preprocessing in Machine Learning: 7 Easy Steps To Follow
151429
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
Read More

by Kechit Goyal

18 Feb 2024

Artificial Intelligence Salary in India [For Beginners &#038; Experienced] in 2024
908012
Artificial Intelligence (AI) has been one of the hottest buzzwords in the tech sphere for quite some time now. As Data Science is advancing, both AI a
Read More

by upGrad

18 Feb 2024

24 Exciting IoT Project Ideas &#038; Topics For Beginners 2024 [Latest]
755278
Summary: In this article, you will learn the 24 Exciting IoT Project Ideas & Topics. Take a glimpse at the project ideas listed below. Smart Agr
Read More

by Kechit Goyal

18 Feb 2024

Natural Language Processing (NLP) Projects &amp; Topics For Beginners [2023]
106866
What are Natural Language Processing Projects? NLP project ideas advanced encompass various applications and research areas that leverage computation
Read More

by Pavan Vadapalli

17 Feb 2024

45+ Interesting Machine Learning Project Ideas For Beginners [2024]
326861
Summary: In this Article, you will learn Stock Prices Predictor Sports Predictor Develop A Sentiment Analyzer Enhance Healthcare Prepare ML Algorith
Read More

by Jaideep Khare

16 Feb 2024

Schedule 1:1 free counsellingTalk to Career Expert
icon
footer sticky close icon