AI Problem Solving

Problem solving aims at reaching a desired goal or finds a solution for a given problem. In artificial intelligence, problem solving basically refers to the various techniques which are applied in order to reach to the solutions to problems using human intelligence. Problem Solving in AI techniques are primarily algorithms or heuristics.

As there can be a number of ways to reach to the solution of a particular problem, any number of these techniques can be used in AI to reach to the unique solution efficiently.

Artificial Intelligence Problems – Characteristics

The problems in AI have the following characteristics:

  • The problems of artificial intelligence are usually those which deal with a large number of solutions. AI helps in identifying the optimal solution among them.
  • Artificial intelligence problems manipulate symbolic information.
  • Most of the artificial intelligence techniques make use of heuristics to solve the problems.
  • For the system to be called an AI program it must have vast knowledge and must be represented in such a form that the AI system can easily manipulate.
  • AI program must have an ability to learn.
  • AI problems deal primarily real-life situations. AI Techniques help to solve the real-life problems and assist humans in taking the right decisions.

Representation of Problems in AI

There are two ways in which a problem in AI can be represented. These methods are as follows:

  • State Space representation
  • Problem Reduction

State Space Representation

In this method, we make use of a directed graph to represent problems. Problems are represented as states / nodes and changes in states are represented as operators. A state space representation comprises of the following:

  • States – It is a representation of various states that the system can be in.
  • Operators – The finite set of operators change the state from one to the other.
  • Initial State – This is the starting state of the system.
  • Final State – It is a set of some desirable and undesirable states.  Out of these states one state would define a Terminal/ Final / Goal or End state for the problem. After this state no more state transitions desirable.

If we have a full state space representation for a problem then we can trace a path from the initial state to the goal state. We will also be able to identify the sequence of operators used during this process.

Some Disadvantages of State Space Representation

But there are some disadvantages of this representation. These are as follows:

  • It is not possible to visualize all the states for a given problem.
  • If there is a possibility to visualize all states, it is nearly impossible to store the entire set of states for a problem in computer memory.

Problem Reduction

If a problem is not easily solvable, then we check that if the problem can be decomposed into smaller sub problems. If it is possible, then the problem is divided into several sub problems by following the problem decomposition process.

Once sub problems are created, solutions for each of these sub problems are obtained. The solution for the entire problem is reached only when the solutions for each of the sub problems are then recombined.

An And-Or graph is made in order to represent the problem. The And Node connects the sub problems with an arc. It signifies that all the solutions to the sub problems are a must to reach to the solution. On the other hand an Or Node has no arc as a connector. It signifies that any path may be taken amongst the sub problems to reach the solution.

Problem Solving in AI – Steps to be followed

In order to solve problems in AI the following steps are followed:

Problem Solving in AI
  1. Defining the Problem–the problem is to be defined precisely so that desirable solution of the given problem can be reached.
  2. Analysing the Problem–the problem area is properly understood and then decisions regarding how to reach solutions is taken. This is pertinent as some features of the problem may affect the solution for that problem.
  3. Identifying Solutions–here a number of possible solutions are generated for the given problem.
  4. Choosing the Best Solution–from the identified solutions a best solution for the problem is chosen.
  5. Implementing the Solution–after the choice for the best solution is made it is implemented.

Techniques of Problem Solving in AI

The problem solving techniques used in artificial intelligence are used for solving complex problems. Search methods form the basis of problem solving in AI. The standard problem solving techniques used in AI are as follows:

  • State Space Search
    • Water Jug Problem
    • Valid Chess Moves
  • Problem Reduction
  • Heuristic Search Algorithms / Techniques
    • Informed / Directed Search
      • Best First Search
      • Hill Climbing
      • Greedy Search
      • Branch and Bound
      • A*Search
    • Uninformed/ Blind Search
      • Breadth First Search
      • Depth First Search
      • Uniform Cost Search
      • IterativeDeepening Depth First Search
      • Bi Directional Search

Properties of Search Algorithms

Search is a mechanism which is used when no other direct method can be applicable. There are four main properties of search algorithms as follows:

  • Completeness: A search algorithm is complete if it returns a solution for the given problem.
  • Optimality: An algorithm is said to be optimal if it returns the ideal solution to the problem. An optimal solution is a solution which is the best amongst all the solutions which are possible for the given problem.
  • Time Complexity: time complexity measures the Amount of time taken by an algorithm to find the solution to the problem.
  • Space Complexity:  It refers to the amount of space that the algorithm will use during the search for the solution to the problem.

Heuristic Search Techniques

Heuristics search techniques make use of self discovering methods and approximations that help find optimal solutions for the problems by minimizing the search process.These are usually more efficient than the traditional brute force search methods used in AI. Hence, they tend to achieve better results.

Two types of problems are solved by using heuristic approach. These problems are:

  1. Problems for which no exact algorithms are defined.
  2. Problems for which the precise solutions are known.
Heuristic Function

The heuristic function guides the search process in the best efficient way possible. This is done by suggesting a part which must be followed first during the search process when more than one path are available. The function makes use of numbers for giving weights to individual aspects of the problem. These numbers then guide the search process.

Informed / Directed Algorithms

In these algorithms, information about problem space is used as a base to calculate a preference among the child nodes. The child nodes are explored and expanded on the base of this preference.

Uninformed / Blind Search Algorithms

These algorithms do not give any preference to the future nodes’ generation and selection. The selected path is followed blindly here. Hence, these algorithms are also known as brute force algorithms.

Production Systems

Production Systems provides structures for AI programs that facilitate describing the problem and then performing the search process. A production system consists of the following:

  • Constraints – This is a finite collection of rules. Each rule has two sides – left and right. Left side determines the applicability of the rule. The right side describes the operation to be performed.
  • Knowledge Database–This contains all the information needed to perform a particular task.
  • Control Strategy–This specifies the order in which rules will be used in resolving the conflicts that arise when a large number of rules match at the same time.
  • A Rule Applicator– This helps the selected rule to be applied on the problem.

Some examples of production systems are: OPS5, expert systems, SOAR etc.