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 store and learn. Goal-based agent, on the other hand, considers future actions and the desired outcomes.

Here, we will discuss one type of goal-based agent known as a problem-solving agent, which uses atomic representation with no internal states visible to the problem-solving algorithms.

Problem-solving agent

The problem-solving agent perfoms precisely by defining problems and its several solutions.

According to psychology, “a problem-solving refers to a state where we wish to reach to a definite goal from a present state or condition.”

According to computer science, a problem-solving is a part of artificial intelligence which encompasses a number of techniques such as algorithms, heuristics to solve a problem.

Therefore, a problem-solving agent is a goal-driven agent and focuses on satisfying the goal.

Steps performed by Problem-solving agent

• Goal Formulation: It is the first and simplest step in problem-solving. It organizes the steps/sequence required to formulate one goal out of multiple goals as well as actions to achieve that goal. Goal formulation is based on the current situation and the agent’s performance measure (discussed below).
• Problem Formulation: It is the most important step of problem-solving which decides what actions should be taken to achieve the formulated goal. There are following five components involved in problem formulation:
• Initial State: It is the starting state or initial step of the agent towards its goal.
• Actions: It is the description of the possible actions available to the agent.
• Transition Model: It describes what each action does.
• Goal Test: It determines if the given state is a goal state.
• Path cost: It assigns a numeric cost to each path that follows the goal. The problem-solving agent selects a cost function, which reflects its performance measure. Remember, an optimal solution has the lowest path cost among all the solutions.

Note: Initial state, actions, and transition model together define the state-space of the problem implicitly. State-space of a problem is a set of all states which can be reached from the initial state followed by any sequence of actions. The state-space forms a directed map or graph where nodes are the states, links between the nodes are actions, and the path is a sequence of states connected by the sequence of actions.

• Search: It identifies all the best possible sequence of actions to reach the goal state from the current state. It takes a problem as an input and returns solution as its output.
• Solution: It finds the best algorithm out of various algorithms, which may be proven as the best optimal solution.
• Execution: It executes the best optimal solution from the searching algorithms to reach the goal state from the current state.

Example Problems

Basically, there are two types of problem approaches:

• Toy Problem: It is a concise and exact description of the problem which is used by the researchers to compare the performance of algorithms.
• Real-world Problem: It is real-world based problems which require solutions. Unlike a toy problem, it does not depend on descriptions, but we can have a general formulation of the problem.

Some Toy Problems

• 8 Puzzle Problem: Here, we have a 3×3 matrix with movable tiles numbered from 1 to 8 with a blank space. The tile adjacent to the blank space can slide into that space. The objective is to reach a specified goal state similar to the goal state, as shown in the below figure.

• In the figure, our task is to convert the current state into goal state by sliding digits into the blank space.

In the above figure, our task is to convert the current(Start) state into goal state by sliding digits into the blank space.

The problem formulation is as follows:

• States: It describes the location of each numbered tiles and the blank tile.
• Initial State: We can start from any state as the initial state.
• Actions: Here, actions of the blank space is defined, i.e., either left, right, up or down
• Transition Model: It returns the resulting state as per the given state and actions.
• Goal test: It identifies whether we have reached the correct goal-state.
• Path cost: The path cost is the number of steps in the path where the cost of each step is 1.

Note: The 8-puzzle problem is a type of sliding-block problem which is used for testing new search algorithms in artificial intelligence.

• 8-queens problem: The aim of this problem is to place eight queens on a chessboard in an order where no queen may attack another. A queen can attack other queens either diagonally or in same row and column.

From the following figure, we can understand the problem as well as its correct solution.

It is noticed from the above figure that each queen is set into the chessboard in a position where no other queen is placed diagonally, in same row or column. Therefore, it is one right approach to the 8-queens problem.

For this problem, there are two main kinds of formulation:

• Incremental formulation: It starts from an empty state where the operator augments a queen at each step.

Following steps are involved in this formulation:

• States: Arrangement of any 0 to 8 queens on the chessboard.
• Initial State: An empty chessboard
• Actions: Add a queen to any empty box.
• Transition model: Returns the chessboard with the queen added in a box.
• Goal test: Checks whether 8-queens are placed on the chessboard without any attack.
• Path cost: There is no need for path cost because only final states are counted.

In this formulation, there is approximately 1.8 x 1014 possible sequence to investigate.

• Complete-state formulation: It starts with all the 8-queens on the chessboard and moves them around, saving from the attacks.

Following steps are involved in this formulation

• States: Arrangement of all the 8 queens one per column with no queen attacking the other queen.
• Actions: Move the queen at the location where it is safe from the attacks.

This formulation is better than the incremental formulation as it reduces the state space from 1.8 x 1014 to 2057, and it is easy to find the solutions.

Some Real-world problems

• Traveling salesperson problem(TSP): It is a touring problem where the salesman can visit each city only once. The objective is to find the shortest tour and sell-out the stuff in each city.
• VLSI Layout problem: In this problem, millions of components and connections are positioned on a chip in order to minimize the area, circuit-delays, stray-capacitances, and maximizing the manufacturing yield.

The layout problem is split into two parts:

• Cell layout: Here, the primitive components of the circuit are grouped into cells, each performing its specific function. Each cell has a fixed shape and size. The task is to place the cells on the chip without overlapping each other.
• Channel routing: It finds a specific route for each wire through the gaps between the cells.
• Protein Design: The objective is to find a sequence of amino acids which will fold into 3D protein having a property to cure some disease.

Searching for solutions

We have seen many problems. Now, there is a need to search for solutions to solve them.

In this section, we will understand how searching can be used by the agent to solve a problem.

For solving different kinds of problem, an agent makes use of different strategies to reach the goal by searching the best possible algorithms. This process of searching is known as search strategy.

Measuring problem-solving performance

Before discussing different search strategies, the performance measure of an algorithm should be measured. Consequently, there are four ways to measure the performance of an algorithm:

Completeness: It measures if the algorithm guarantees to find a solution (if any solution exist).

Optimality: It measures if the strategy searches for an optimal solution.

Time Complexity: The time taken by the algorithm to find a solution.

Space Complexity: Amount of memory required to perform a search.

The complexity of an algorithm depends on branching factor or maximum number of successors, depth of the shallowest goal node (i.e., number of steps from root to the path) and the maximum length of any path in a state space.

Search Strategies

There are two types of strategies that describe a solution for a given problem:

Uninformed Search (Blind Search)

This type of search strategy does not have any additional information about the states except the information provided in the problem definition. They can only generate the successors and distinguish a goal state from a non-goal state. These type of search does not maintain any internal state, that’s why it is also known as Blind search.

There are following types of uninformed searches:

• Breadth-first search
• Uniform cost search
• Depth-first search
• Depth-limited search
• Iterative deepening search
• Bidirectional search

Informed Search (Heuristic Search)

This type of search strategy contains some additional information about the states beyond the problem definition. This search uses problem-specific knowledge to find more efficient solutions. This search maintains some sort of internal states via heuristic functions (which provides hints), so it is also called heuristic search.

There are following types of informed searches:

• Best first search (Greedy search)
• A* search

Uninformed Search Strategies in Artificial Intelligence

 

Breadth-first search (BFS)

It is a simple search strategy where the root node is expanded first, then covering all other successors of the root node, further move to expand the next level nodes and the search continues until the goal node is not found.

BFS expands the shallowest (i.e., not deep) node first using FIFO (First in first out) order. Thus, new nodes (i.e., children of a parent node) remain in the queue and old unexpanded node which are shallower than the new nodes, get expanded first.

In BFS, goal test (a test to check whether the current state is a goal state or not) is applied to each node at the time of its generation rather when it is selected for expansion.

Breadth-first search tree

In the above figure, it is seen that the nodes are expanded level by level starting from the root node A till the last node I in the tree. Therefore, the BFS sequence followed is: A->B->C->D->E->F->G->I.

BFS Algorithm

• Set a variable NODE to the initial state, i.e., the root node.
• Set a variable GOAL which contains the value of the goal state.
• Loop each node by traversing level by level until the goal state is not found.
• While performing the looping, start removing the elements from the queue in FIFO order.
• If the goal state is found, return goal state otherwise continue the search.

The performance measure of BFS is as follows:

• Completeness: It is a complete strategy as it definitely finds the goal state.
• Optimality: It gives an optimal solution if the cost of each node is same.
• Space Complexity: The space complexity of BFS is O(bd), i.e., it requires a huge amount of memory. Here, b is the branching factor and d denotes the depth/level of the tree
• Time Complexity: BFS consumes much time to reach the goal node for large instances.

Disadvantages of BFS

• The biggest disadvantage of BFS is that it requires a lot of memory space, therefore it is a memory bounded strategy.
• BFS is time taking search strategy because it expands the nodes breadthwise.

Note: BFS expands the nodes level by level, i.e., breadthwise, therefore it is also known as a Level search technique.

Uniform-cost search

Unlike BFS, this uninformed search explores nodes based on their path cost from the root node. It expands a node n having the lowest path cost g(n), where g(n) is the total cost from a root node to node n. Uniform-cost search is significantly different from the breadth-first search because of the following two reasons:

• First, the goal test is applied to a node only when it is selected for expansion not when it is first generated because the first goal node which is generated may be on a suboptimal path.
• Secondly, a goal test is added to a node, only when a better/optimal path is found.

Thus, uniform-cost search expands nodes in a sequence of their optimal path cost because before exploring any node, it searches the optimal path. Also, the step cost is positive so, paths never get shorter when a new node is added in the search.

                                    Uniform-cost search on a binary tree

In the above figure, it is seen that the goal-state is F and start/initial state is A. There are three paths available to reach the goal node. We need to select an optimal path which may give the lowest total cost g(n). Therefore, A->B->E->F gives the optimal path cost i.e., 0+1+3+4=8.

Uniform-cost search Algorithm

• Set a variable NODE to the initial state, i.e., the root node and expand it.
• After expanding the root node, select one node having the lowest path cost and expand it further. Remember, the selection of the node should give an optimal path cost.
• If the goal node is searched with optimal value, return goal state, else carry on the search.

The performance measure of Uniform-cost search

• Completeness: It guarantees to reach the goal state.
• Optimality:  It gives optimal path cost solution for the search.
• Space and time complexity: The worst space and time complexity of the uniform-cost search is O(b1+LC*/ᵋ˩).

Note: When the path cost is same for all the nodes, it behaves similar to BFS.

Disadvantages of Uniform-cost search

• It does not care about the number of steps a path has taken to reach the goal state.
• It may stick to an infinite loop if there is a path with infinite zero cost sequence.
• It works hard as it examines each node in search of lowest cost path.

Depth-first search

This search strategy explores the deepest node first, then backtracks to explore other nodes. It uses LIFO (Last in First Out) order, which is based on the stack, in orderto expand the unexpanded nodes in the search tree. The search proceeds to the deepest level of the tree where it has no successors. This search expands nodes till infinity, i.e.,  the depth of the tree.

DFS search tree

In the above figure, DFS works starting from the initial node A (root node) and traversing in one direction deeply till node I and then backtrack to B and so on. Therefore,  the sequence will be A->B->D->I->E->C->F->G.

DFS Algorithm

• Set a variable NODE to the initial state, i.e., the root node.
• Set a variable GOAL which contains the value of the goal state.
• Loop each node by traversing deeply in one direction/path in search of the goal node.
• While performing the looping, start removing the elements from the stack in LIFO order.
• If the goal state is found, return goal state otherwise backtrack to expand nodes in other direction.

The performance measure of DFS

• Completeness: DFS does not guarantee to reach the goal state.
• Optimality: It does not give an optimal solution as it expands nodes in one direction deeply.
• Space complexity: It needs to store only a single path from the root node to the leaf node. Therefore, DFS has O(bm) space complexity where b is the branching factor(i.e., total no. of child nodes, a parent node have) and m is the maximum length of any path.
• Time complexity: DFS has O(bm) time complexity.

Disadvantages of DFS

• It may get trapped in an infinite loop.
• It is also possible that it may not reach the goal state.
• DFS does not give an optimal solution.

Note: DFS uses the concept of backtracking to explore each node in a search tree.

Depth-limited search

This search strategy is similar to DFS with a little difference. The difference is that in depth-limited search, we limit the search by imposing a depth limit l to the depth of the search tree. It does not need to explore till infinity. As a result, the depth-first search is a special case of depth-limited search. when the limit l is infinite.

                                       Depth-limited search on a binary tree

In the above figure, the depth-limit is 1. So, only level 0 and 1 get expanded in A->B->C DFS sequence, starting from the root node A till node B. It is not giving satisfactory result because we could not reach the goal node I.

Depth-limited search Algorithm

• Set a variable NODE to the initial state, i.e., the root node.
• Set a variable GOAL which contains the value of the goal state.
• Set a variable LIMIT which carries a depth-limit value.
• Loop each node by traversing in DFS manner till the depth-limit value.
• While performing the looping, start removing the elements from the stack in LIFO order.
• If the goal state is found, return goal state. Else terminate the search.

The performance measure of Depth-limited search          

• Completeness: Depth-limited search does not guarantee to reach the goal node.
• Optimality: It does not give an optimal solution as it expands the nodes till the depth-limit.
• Space Complexity: The space complexity of the depth-limited search is O(bl).
• Time Complexity: The time complexity of the depth-limited search is O(bl).

Disadvantages of Depth-limited search

• This search strategy is not complete.
• It does not provide an optimal solution.

Note: Depth-limit search terminates with two kinds of failures: the standard failure value indicates “no solution,” and cut-off value, which indicates “no solution within the depth-limit.”

Iterative deepening depth-first search/Iterative deepening search

This search is a combination of BFS and DFS, as BFS guarantees to reach the goal node and DFS occupies less memory space. Therefore, iterative deepening search combines these two advantages of BFS and DFS to reach the goal node. It gradually increases the depth-limit from 0,1,2 and so on and reach the goal node.

In the above figure, the goal node is H and initial depth-limit =[0-1]. So, it will expand level 0 and 1 and will terminate with A->B->C sequence. Further, change the depth-limit =[0-3], it will again expand the nodes from level 0 till level 3 and the search terminate with A->B->D->F->E->H sequence where H is the desired goal node.

Iterative deepening search Algorithm

• Explore the nodes in DFS order.
• Set a LIMIT variable with a limit value.
• Loop each node up to the limit value and further increase the limit value accordingly.
• Terminate the search when the goal state is found.

The performance measure of Iterative deepening search

• Completeness: Iterative deepening search may or may not reach the goal state.
• Optimality: It does not give an optimal solution always.
• Space Complexity: It has the same space complexity as BFS, i.e., O(bd).
• Time Complexity: It has O(d) time complexity.

Disadvantages of Iterative deepening search

• The drawback of iterative deepening search is that it seems wasteful because it generates states multiple times.

Note: Generally, iterative deepening search is required when the search space is large, and the depth of the solution is unknown.

Bidirectional search

The strategy behind the bidirectional search is to run two searches simultaneously–one forward search from the initial state and other from the backside of the goal–hoping that both searches will meet in the middle. As soon as the two searches intersect one another, the bidirectional search terminates with the goal node. This search is implemented by replacing the goal test to check if the two searches intersect. Because if they do so, it means a solution is found.

The performance measure of Bidirectional search

• Complete: Bidirectional search is complete.
• Optimal: It gives an optimal solution.
• Time and space complexity: Bidirectional search has O(bd/2)

Disadvantage of Bidirectional Search

• It requires a lot of memory space.