All about Informed Search in Artificial Intelligence
Updated on Mar 20, 2023 | 10 min read | 8.6k views
Share:
For working professionals
For fresh graduates
More
Updated on Mar 20, 2023 | 10 min read | 8.6k views
Share:
Table of Contents
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.
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.
To understand heuristic functions better, here are some real-life examples:
With that settled, let’s now move ahead and understand some of the most used examples of informed search algorithms in artificial intelligence.
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:
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.
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:
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:
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.”)
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.
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:
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.
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
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.”)
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!
Get Free Consultation
By submitting, I accept the T&C and
Privacy Policy
Top Resources