Artificial Intelligence

Problem Solving in AI

We know the agent (see previous tutorial Agents in AI) directly maps the states into action. Whenever the state of mapping is too large and the agent fails to perform in those environments (see the previous tutorial Task environment) then the given problem is divided into smaller tasks by the problem-solving domain and resolves these smaller storage areas one by one. Finally, the results are integrated to get the desired outcomes. Problem-solving in AI includes various techniques like efficient algorithms, heuristics, and performing root cause analysis to obtain desirable solutions. For a given problem in AI, there may be various solutions by different heuristics and at the same time, there are problems with unique solutions. These all depend on the nature of the problem to be solved.

Characteristics of problem in AI

Each problem given to an AI is with different aspects of representation and explanation. The given problem has to be analyzed along with several dimensions to choose the most acceptable method to solve. Some of the key features of a problem are listed below.

  • Can the problem decompose into subproblems?
  • Can any of the solution steps be ignored?
  • Is the given problem universally predictable?
  • Can we select a good solution for the given problem without comparing it to all the possible solutions?
  • Whether the desired output is a state of the world or a path to a state?
  • Did the problem require a large amount of knowledge to solve?
  • Does it require any interaction with computers and humans?

The above-listed characteristics of a problem are called 7-problem characteristics. The solution for the given problem must take place under these characteristics. 

Problems in AI can basically be divided into two types. Toy Problems and Real-World Problems.

Toy Problem:

It can also be called a puzzle-like problem which can be used as a way to explain a more general problem-solving technique. For testing and demonstrating methodologies, or to compare the performance of different algorithms, Toy problems can be used. Toy problems are often useful in providing divination about specific phenomena in complicated problems. Large complicated problems are divided into many smaller toy problems that can be understood in detail easily. Sliding-block puzzles, N-Queens problem, Tower of Hanoi are some examples.

Real-World Problem:

 As with the name, it is a problem based on the real world. Real-world problems require a solution. It doesn't depend on descriptions, but with a general formulation. Online shopping, Fraud detection, Medical diagnosis are some examples of real-world problems in AI.

Steps performed in problem-solving

Steps performed in problem-solving
  • Goal formulation: The first step in problem-solving is to identify the problem. It involves selecting the steps to formulate the perfect goal out of multiple goals and selecting actions to achieve the goal.
  • Problem formulation: The most important step in problem-solving is choosing the action to be taken to achieve the goal formulated.
  • Initial State: The starting state of the agent towards the goal.
  • Actions:  The list of the possible actions available to the agent.
  • Transition Model: What each action does is described.
  • Goal Test: The given state is tested whether it is a goal state.
  • Path cost:  A numeric cost to each path that follows the goal is assigned. It reflects its performance. Solution with the lowest path cost is the optimal solution. 

Example for the problem-solving procedure

Eight queens puzzle

Eight queens puzzle

The problem here is to place eight chess queens on an 8*8 chessboard in a way that no queens will threaten the other. If two queens will come in the same row, column, or diagonal one will attack another.

Consider the Incremental formulation for this problem: It starts from an empty state and the operator expands a queen at each step.
Following are the steps involved in this formulation:

  • States: Arranging  0 to 8 queens on the chessboard.
  • Initial State: An empty chessboard
  • Actions: Adding a queen to any of the empty boxes on the chessboard.
  • Transition model: Returns the new state of the chessboard with the queen added in a box.
  • Goal test: Checks whether 8-queens are kept on the chessboard without any possibility of attack.
  • Path cost: Path costs are neglected because only final states are counted.

Problem-solving methods in Artificial Intelligence

Let us discuss the techniques like Heuristics, Algorithms, Root cause analysis used by AI as problem-solving methods to find a desirable solution for the given problem.

1. ALGORITHMS

A problem-solving algorithm can be said as a procedure that is guaranteed to solve if its steps are strictly followed. 
Let's have a simple example to get to know what it means:
A person wants to find a book on display among the vast collections of the library. He does not know where the book is kept. By tracing a sequential examination of every book displayed in every rack of the library, the person will eventually find the book. But the approach will consume a considerable amount of time. Thus an algorithmic approach will succeed but are often slow.

Types of AI Algorithms

  • Regression Algorithms.
  • Instance-Based Algorithms. 
  • Decision Tree Algorithms. 
  • Clustering Algorithms. 
  • Association Rule Learning Algorithms. 
  • Artificial Neural Network Algorithms. 
  • Deep Learning Algorithms.
  • Search Algorithms

2. HEURISTICS.

A problem-solving heuristic can be said as an informal, ideational, impulsive procedure that leads to the desired solution in some cases only. The fact is that the outcome of a heuristic operation is unpredictable. Using a heuristic approach may be more or less effective than using an algorithm.
Consider the same example discussed above. If he had an idea of where to look for the book, a great deal of time could be saved. This can be said as searching heuristically. But if one happens to be wrong on the first trial, He has to try another heuristic.
The frequently used problem-solving heuristics are 

WORKING FORWARD 

It is a forward approach problem-solving solution. In this method, the problem is solved from the beginning itself and working to the end.

WORKING BACKWARD

It is a backward approach problem-solving solution. Here the problem is solved from the endpoint or goal to steps that led to the goal.

MEANS-ENDS ANALYSIS.

A problem-solving technique where a mixture of the above two directions. This method is appropriate for solving complex and large problems. MEA is a strategy to control the searching procedure in problem-solving. It is centered on evaluating the difference between the current state and the goal state. First, the difference between the initial state and the final state is calculated. Then select various operators for each difference. The application of these operators will reduce the difference between the current state and the goal state.

GENERATE-AND-TEST.

The Generate-and-test method is a problem-solving heuristics that involve an alternate set of actions in a random method. Each alternate method is to check whether it will solve the problem.  It ensures that the selected best possible solution is checked against the generated possible solutions.

Difference between algorithm and heuristics

Algorithm Heuristics

An automated solution to a problem

Deterministic and proven to grant an optimal result

Containing a finite set of instructions to solve a problem.

 

Arbitrary choices or educated guesses

No proof of correctness, may not grant optimal results.

Applied to improve the running time of algorithms.

The terms heuristics and algorithms overlap somewhat in AI. A heuristic may be a subroutine that can be used to determine where to look first for an optimal algorithm. Heuristic algorithms can be listed under the categories of algorithms. In a sense of heuristics are algorithms, heuristic makes a guessing approach to solve the problem, granting a good enough answer rather than finding the best possible outcome. The level of indirection is the main difference between the two.

3. Root Cause Analysis

Like the name itself, it is the process of identifying the root cause of the problem. The root cause of the problem is analyzed to identify the appropriate solutions. A collection of principles, techniques, and methodologies are used to identify the root causes of a problem. RCA can identify an issue in the first place.

The first goal of RCA is to identify the root cause of the problem. The second goal is to understand how to fix the underlying issues within the root cause. The third goal is to prevent future issues or to repeat the success.

The core principles of RCA are:

  • Focus on correcting the root causes.
  • Treating symptoms for short-term relief.
  • There can be multiple root causes.
  • Focus on HOW? and WHY?
  • Root cause claims are kept back up with concrete cause-effect.
  • Provides information to get a corrective course of action.
  • Analyze how to avoid a root cause in the future.