Methods of Problem Solving in Artificial Intelligence | Computer Science

The requisite background of intelligent systems or agents it is pertinent to discuss how a problem can be solved by these agents. An agent is anything which can be viewed as perceiving its environment through sensors and acting upon that environment through actuators.

A human agent has ears, eyes and other organs for sensors and hands, legs, mouth etc., for actuators. In intelligent agents knowledge base corresponds to environment, operators correspond to sensors and the search techniques are the actuators.

Before a solution can be found, the important point is that the problem must be very precisely defined that is the abstract problem should be converted into real workable states which are clearly understood. These states are operated upon by a set of operators and the decision of which operators to be applied, when and where is dictated by the overall control strategy.

The most common methods of problem solving in AI are:

1. State space representation

2. Problem reduction.

Method # 1. State Space Representation:

Suppose we are asked to prepare a cup of coffee; what should be done? All the ingredients such as coffee powder, milk powder, sugar, kettle, heating arrangement etc., must be made available.

The following steps are needed:

i. Boil water.

ii. Take some of the boiled water in a cup, add necessary amount of coffee powder to make decoction.

iii. Add milk powder to the some boiling water to make milk.

iv. Mix decoction and milk.

v. Add sugar to your taste.

vi. Coffee is prepared.

Now think a bit what has exactly happened. We started with the ingredients (initial state), followed a sequence of steps (called states) and at last had a cup of coffee (goal state). We added only needed amount of coffee powder, milk powder and sugar (operators) shows the sequence of operations.

A combination of all possible states for a given problem is known as the state space of the problem.

To explain it in a more detailed manner, let’s consider another problem, a small game, the 15-tile puzzle. The puzzle consists of a square frame containing 15 tiles and an empty slot. The tiles are numbered from 1 to 15. It is possible to move the tiles in the square frame by moving a tile into the empty slot. The objective is to get the squares in a numerical order shown in Fig. 1.8.

As discussed above, we need to have an initial state, a set of operators and a goal state. Fig. 1.8. shows the initial state with the tiles in a jumbled fashion and the goal state.

The operator for this problem are:

UP If the hole, created by moving a tile from one box to another is not touching the top frame, move it up.

DOWN If the hole is not touching the bottom frame, move it down.

LEFT If the hole is not touching the left frame, move it left.

RIGHT If the hole is not touching the right fame, move it right.

The state space is now a directed graph with all the states as nodes. A node is said to exist if it is possible to obtain it from the initial state by application of a set of operators. A small fragment of the state space for the 15-tile puzzle is shown in Fig. 1.9. (Point out any arrow in the direction of operators/ tile if any).

State-space representations for problem solving are highly beneficial in AI because they provide all possible states, operations and the goals. If the entire state-space representation for a problem is given, it is possible to trace the path from the initial state to the goal state and identify the sequence of operators necessary for doing it.

The major deficiency of this method is that it is not possible to visualize all states for a given problem. Moreover, the resources of the computer system are limited to handle huge state-space representations.

Look at Fig. 1.9., again which depicts the state space upto level 2 with root being level 0. At a level 2, the number of states is six, we may not end up with the goal even if we expand to another level. To overcome the deficiencies of this method, problem reduction technique becomes handy.

Method # 2. Problem Reduction:

In this method, a complex problem, is broken down or decomposed into a set of primitive sub-problems. Solutions for these primitive sub-problems can be obtained unless the goals are interactive. The solutions for all the sub- problems collectively give the solution for the complex problem.