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.

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

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

Disadvantages of A* Search

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

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!