Problems Encountered in Artificial Intelligence (Characteristics)

In order to solve a problem it need to be analyzed on the following lines:

1. Is the program decomposable into a set of independent smaller or easier sub-problems?

2. Can the solution steps be ignored or undone if they prove fruitless?

3. Is the problem’s universe predictable?

4. Is the good solution absolute or relative?

5. Is the desired solution a state of the problem’s world or a path to a state?

6. What is the role of knowledge about the problem’s domain?

7. Will the computer return the solution having fed the problem automatically or will the solution be obtained only after the interaction between the computer and the problem solver?

All these problem characteristics form the topic of this article.

There are two possible cases in problem characteristic. In the first case let us consider a mathematical problem on integration.

This problem (Fig. 3.1) can be solved by breaking it down into three smaller problems, each of which can then be solved by using specific rules. The problem tree is shown above. At every step it is checked if the problem, can be solved directly, if so its value is given otherwise it is broken into smaller sub-problems. Then by recursion method sub-problems are solved. The final solution is the sum of all the sub-problems.

 

Now consider another problem from Blocks World. Three blocks A, B, C are placed on the table top as shown in Fig. 3.2. (a) and they need to be arranged as shown in Fig. 3.2. (b).

Two operators are given, but one operator is to be executed at a time.

The Operators are:

1. CLEAR (x) (block x has nothing on it) ON (x, table) (pick up x and y put it on the table).

2. CLEAR (x) AND CLEAR (y) (block .v and blocky have nothing on them.)← ON (x, y) (put block x on block y).

Applying the problem decomposition technique to this block world would lead to a solution shown below by the tree (starting from goal state):

Goals have been underlined, whereas states which have been achieved are not underlined.

By this sub-division the sub two problems: placing A on B and putting B on C become two independent problems. The second one is quite simple, the first one needs little consideration. In order to solve ON (A, B), we need two steps; A has to be cleared off C, and then A can be put on B, so we need two operators, to be used simultaneously.

The two branches of the graph are joined by and sign. For the time being we can just say that in order to solve goal ON (A, B) the two branches need to be solved independently and their composite solutions combined, which is also true according to the given problem. Since we can use only one operator at a time, so we fail to combine two sub-solutions into a single one under the given conditions.

Thus, the two examples illustrate the decomposable and non-decomposable nature of the problem. Decomposable problems can be solved by divide and conquer technique of problem decomposition, whereas non-decomposable problems need special technique.

Can Solution Steps be Ignored or Undone?

This characteristic can be tackled from three different views: steps to the solution:

i. Can be ignored

ii. Have to be kept on record

iii. Are irrevocable (back tracked)

So consider three types of problems:

1. Mathematical,

2. 8-puzzle and

3. Playing chess.

1. Mathematical Problem:

In the case of mathematical problem suppose we want to prove some lemma or axiom say, what is the shortest distance between two points. Different alternatives can be tried till we prove that the vertical distances between the two points is the shortest.

If a particular trial, does not help getting the solution, nothing is lost, the problem still stands, what has been lost is the effort spent in exploring the blind alley, solution can be ignored, and a new one can be tried or in other words, the steps can be ignored.

2. 8-Puzzle Problem:

The 8-puzzle is a square tray in which are placed eight square tiles. The remaining ninth square is uncovered. Each tile has a number on it. A tile which is adjacent to the blank space can be sliced in to that space. The game consists of starting position and a specified goal position. The goal is to transform the starting position into the goal position by sliding the tiles around, as for example, shown in Fig. 3.4.

The 8-puzzle belongs to the family of sliding block puzzles. This general class is known to be NP-complete, so we do not expect to find methods significantly better than the search algorithms. The 8-puzzle and its larger cousin, the 15-puzzle, are standard test problems for new search algorithms in AI.

In the above problem move number 5 to hole (empty square), empty space now moves to place where it was 5. Now move 6 to that empty space. But number 6 can be moved back to empty space and 5 back to its position. Mistakes can be recovered though not as easy as in mathematically theorem proving.

An additional step must be performed to undo each incorrect step, whereas no action was required in the mathematical theorem to undo a useless lemma. In addition the control mechanism for an 8-puzzle solver must keep track of the order in which operations are performed so that operations can be undone one at a time, if necessary. The solution steps are recoverable indeed.

3. Playing Chess:

Suppose a chess-playing programme makes a stupid move and realised it a couple of moves later. Now, it cannot back track. Since the adversary has already moved and the state space has changed. All it can do is to try to make the best of the current situation and go from there. This is an irrecoverable game.

Recoverability of a problem plays an important role in determining the complexity of the control structure with which a solution can be found. Ignorable problems can be solved using a strategy which is simple, does not need back tracking. This is quite easy. Recoverable problem can be tackled by a strategy which does mistakes sometimes. Back tracking will be often needed in order to avoid or recover from mistakes.

So the control structure (strategy) must be implemented using back tracking and a push-down stack in which decisions were made, in case, they need to be undone later. Irrecoverable problems are to be solved by systems which put in lot of efforts to make decisions since these decisions ought to be final.

However, some irrecoverable problems can be solved by recoverable style methods used in a planning process. In such cases the entire sequence of steps is analyzed well in advance to know how far or how near the goal the whole process would lead to.

Is the Universe Predictable?

Considering 8-Puzzle Game:

In the single player game when a move is made it is known in advance what is going to happen. In 8-puzzle game; it is possible to plan an entire sequence of moves and become confident of the resulting state. Planning can be used to avoid undoing the moves, though sometimes backtracking may still be needed.

In board games such a planning process may not be possible at all. Suppose we want to play Bridge. Planning may not be possible at all which card has to be thrown first can be planned at the most. It is not possible to plan completely because we do not know where all other ‘cards’ are or what the other players would do in their turn.

At best we can investigate some moves plans and use probabilities of the various outcomes to choose a plan or a combination of plans to know the path which has the highest expected probability of leading towards a solution.

These two games illustrate the difference between certain-outcome (say 8-puzzle) and uncertain-outcome (say bridge) problems. The simple method of describing planning is that it is problem solving without feedback from the environment (open-loop approach). For solving certain-outcome problems this type of approach can work safely since the result of an operation can be predicted perfectly.

Thus, planning can be used to generate a sequence of actions which is guaranteed to lead to a solution. For uncertain-outcome problems planning can at best generate a sequence of operators which has a good probability of leading to a solution.

In such cases planning is continuously monitored after getting the necessary feedback. Obviously continuous planning supplemented with continuous feedback involves a heavy cost because the number of solution paths goes on increasing exponentially where the outcome has to be predicted.

To solve such problems plans which may provide us some hint towards an optimum path has to be revised constantly with the necessary feedback. Moreover the solution with uncertain-outcome has the drawback that it is often very expensive since the number of solution paths which need to be explored increase exponentially with the number of points at which the outcome need be predicted.

From the second characteristics we infer that in some problems the solution steps can be ignorable, recoverable and irrecoverable and according to third characteristic we conclude that some problems have certain-outcome and others have uncertain outcome. There can be interesting interaction between these two characteristics. The problems with certain-outcome and steps ignorable can be solved without the need of any planning.

The problems in which steps are irrecoverable can be solved with some planning. But such planning helps in the case of certain-outcome problems. The activities like playing bridge problem is the example of such type of problems. Here accurate estimates of the probabilities of each of the possible-outcome can be made. So the irrecoverable problem with certain-outcome can be solved.

The still harder problem are those which are irrecoverable with uncertain outcome and cannot be solved with any degree of certainty. Controlling a robot arm is an example of a problem having a conglomeration of irrecoverable steps with uncertain outcome. The outcome is uncertain for many reasons: the gears of the arm might stick, some one might put an obstruction in the path of the robot, etc.

Helping a lawyer decide how to defend his client against a murder charge is yet another example of uncertain outcome plus irrecoverable steps. Here the probabilities of outcome cannot be predicted and the client may not be helped.

Is the Good Solution Absolute or Relative?

The answer to this quarry can be either yes or no. Consider the problem of answering, questions based on data base of simple facts such as:

1. Marcus was a man.

2. Marcus was a Pompeian.

3. Marcus was born in 40 AD.

4. All men are mortal.

5. All Pompeian’s died when volcano erupted in 79 AD.

6. No mortal lives longer than 150 years.

7. It is now 2011 AD.

Suppose we ask question, Is Marcus alive?

By representing each of the facts in a formal language, such as predicate logic and then using formal inference methods, we can easily derive an answer. But here the conclusion is derived using simple reasoning.

Two reasoning paths will lead to answer, no matter which path is followed:

Any path of reasoning will give the absolute answer to the problem, there is no reason to go back and see if the other path might lead to the absolute solution.

Consider now travelling salesman problem. Our goal is to find the shortest path so that the sales man visits each city exactly once. Suppose the cities we need to visit and the distances between them are known, (in km in Fig. 3.5).

Let the salesman start from Jammu. He could follow the one path covering the total distance of 1252 Km. But is this the solution? We are not sure unless other alternate paths are covered. A second or third path can also be known, a second one is shown on the right hand side of the earlier traversal tree giving certainly first path as the answer, which is of course relative (Fig. 3.6.).

Is the Solution a State or a Path?

In some problems we are only interested in the state representing the solution, whereas in other cases we also want to know how we got to the solution, that is which is the optimum path.

Consider the problem of finding a consistent interpretation for a sentence: which is so common in natural language understanding.

The sentence can be:

The bank president ate a dish of fruity ice cream with the fork.

There are several components of this sentence, each of which in isolation, may have more than one interpretation, but the components must form a coherent ‘whole’ and so they constrain each other’s interpretation.

Some of the sources of ambiguity in this sentence are the following:

1. The word ‘bank’ may refer to either a financial institution or to a side of a river. But only one of these may have a president (of a financial institute).

2. The word ‘dish’ is the object of the word ‘eat’. Is it possible that a dish (of metal or paper) was eaten? So it is more likely that fruity ice cream in it was eaten.

The phrase ‘with the fork’ could modify several parts of the sentence. In this case it personifies the verb ‘eat’. But, if the phrase had been with coke then the modified structure would be different and if the phrase had been ‘with his friends’ the structure would be different still.

Because of the interaction among the interpretations of the constituents of this sentence, some search may be required to find a complete interpretation for the sentence. But to solve the problem of finding the interpretation we need to produce only the interpretation itself, no record of the processing by which the interpretation was found is necessary. Now, compare this with water jug problem.

Here it is not sufficient to report that we have solved the problem and that the final state is (2, 0). For this kind of problem, what we really report is not the final state but the path which led to the determination of the state. Thus, a goal state or a solution to this problem must be a sequence of operations (called a plan) which produces the final state (of the water jug problem) a path.

The two examples-natural language understanding and water jug problem illustrate the difference between problem whose solution is a state or path of the world assumes. This difference can be ignored and all problems can be formulated as ones in which only a state is required to be reported.

If we do this for problems such as water jug then we must re-describe our states so that each state represents a partial path of a solution rather than just a single state of the water jug problem. So this question is not a formally significant one.

But just as for question of ignorability vs. recoverability, there is often a (economical) formulation of a problem in which problem states, (say in Chess), correspond to situations in the world, not sequence of operations so record of states in a path becomes important during the course of looking for the solution.

Examples of State:

Crossword puzzle, eight-queens problem, magic squares, natural language problem or mathematical theorem proving. The main interest is that the crossword is completed, how it is completed no one worries.

In the natural language processing example, because of the interaction between various components some search may be required to find a complete interpretation, otherwise we are concerned only about the solution.

Mathematical theorem proving has always been a driving force in AI. If we consider this, we see that it is not only important how we solved the required theorem, but the steps we take are also recorded that is the proof.

Examples of Path:

In all these problems we know precisely not only what the goal state is to be, it is also the means of getting there which also is required. The solutions to such problems must include not just a single goal state but instead a sequence of states, visited and the moves made between them.

Travelling Salesman Problem:

He wants the route to be as short as possible. Here goal state is not specified in advance, moreover it has to be as short as possible. Although the final state is given (the same as the start state), the important property is one of the whole path, namely each place is visited exactly once. It would be no good to find a route which reached no where at all.

A Magic Square is a square of numbers where each row, column and diagonal adds upto the same number.

The 8-queen Problem is a classic placing problem. The goal is to place eight queens on a chess board such that no queen attacks any other (A queen attacks any piece in the same row, column or diagonal).

Towers of Hanoi Problem:

In a monastery in deepest Tibet there are three crystal columns and 64 golden rings. The rings are of different size and rest over three columns. At the beginning of time all the rings rested on the left most column and since then the monks have toiled ceaselessly moving the rings one by one between the columns. It is said that when all the rings lie on the center column the world would end and the monks can at least rest.

The two rules to be obeyed are:

1. Rings are moved one at a time.

2. Larger disk cannot rest on a smaller one.

Role of Knowledge in Computing:

In chess playing suppose we have an efficient computer (a work station or even a super-computer) all the rules for determining legal moves are known and an efficient control strategy is also available, then the problem can be solved after the application of tactical moves.

Now same computing facilities are available will the computer be able to give verdict on whether, India should develop friendship with Israel. In view of the 2003 visit of Israeli Prime Minister Mr. Ariel Sharon to New Delhi. Even some trade pacts including sale of war ships by Israel to India have been signed by the two Governments. There are so many parameters contributing to this political dilemma. A few of the contributing factors are.

In 1948, India voted for the partition of Palestine and the creation of two independent states of Israel and Palestine, when the league of Nations, mandate of Britain to administer Palestine was surrendered to the UN. Indian Government have been supporting Palestinian Liberation Organization (PLO) ever since then.

The Government in saddle (in 2003) even welcomed Yasser Arafat President of PLO, to India many times while fully aware that he and his allies, like the Islamic Jihad and Hamas, had vowed to destroy Israel and has massacred innocent Israeli Citizens. Visit of Sharon President of Israel in November, 2003 coupled with forging the closer relations between India and Israel should outrage certain communal and ideological groups in India.

Israeli Prime Minister had to cut short his stay in India due to two Palestinian suicide bombings, killing fifteen Israelis. He wanted Palestinian head of the state to immediately leave Palestine. But USA objects to Palestinian leader Yasser Arafat as being called an obstacle to peace and sabotaging the peace efforts of Israel. Even US state department spokesman stated that it would not be helpful to expel Arafat because it would just give him another stage to play on. So much so UNO also does not support this point of Israel.

This visit has even outraged President of Pakistan, Mr. Parvez Musharraf who has described the emerging friendship between India and Israel as a great threat to Pakistan. He is reported to have appealed to the Israeli Prime Minister to ‘understand’ the sensitivity of Indo-Israel relationship and maintain a ‘balance’ in relationship between Pakistan and Israel.

The computer, howsoever intelligent and powerful it can be won’t be able to combine all these aspects and analyze them and it would not be possible for it to arrive at a solution, worth the salt involving many beliefs and convictions.

In brief the computer can only give solution to problems which have some legal rules but those depending upon the sentiments, emotions, likes and dislikes would not be solvable by the computer howsoever intelligent it could become.