Is the Problem Universe Predictable

Consider that we are playing with the 8-Puzzle problem. Every time we make a move, we know exactly what will happen. This means that it is possible to plan an entire sequence of moves and be confident what the resulting state will be. We can backtrack to previous moves if they prove wrong.

Suppose we want to play Bridge. We need to make some decisions like which card to play on the first trick. Then we need to make a plan for the entire hand before the first play, but we cannot plan and play with certainty since We cannot know where all the cards are or what the other players will do on their turns. So we have to investigate several plans and use probability of various outcomes to choose best plan for a good score.  So, the outcome of this game is very uncertain.

These two games shows us difference between certain outcome (e.g. 8-Puzzle) and uncertain outcome (e.g. play bridge ) .

In case of certain outcome, we can make a plan to generate a sequence of operation that guaranteed to lead to a solution. So, that the outcome is very certain.

In case of uncertain outcome problems, we follow the process of plan revision as the plan is carried out and the necessary feedback is provided. The disadvantage is that the planning in this case is often very expensive.

Artificial Intelligence : Solution steps can be ignored or undone

To find out whether the solutions steps can be ignored or undone. We have three classes of problems mentioned below :-

1. Ignorable : In which solution steps can be ignored (e.g., Theorem Proving).

Suppose we are trying to prove a mathematical theorem. First we proceed with proving a lemma that we think will be useful. Later we realize that it is not useful. So, Are we in serious trouble?. No, Still we can prove the theorem, only we need to ignore the first approach and start with another one to prove the theorem.

2. Recoverable :  In which solution steps can be undone. (e.g., 8-Puzzle Problem).Suppose we have a 8-puzzle problem as shown in above figure. While attempting to solve the 8-puzzle problem, mistakenly  we make a wrong move and realize that mistake. Now to correct our mistake we need to undo incorrect steps.

To undo incorrect steps the control mechanism for an 8-puzzle solver must keep track of the order in which steps are performed, so that we can backtrack to the initial state and start with some correct move.

3. Irrecoverable :  In which solution steps cannot be undone. (e.g., Chess).Consider the problem of playing chess. Suppose playing chess program makes a wrong move and realize it after couple of moves. It cannot simply ignore the mistake. Neither it can be undone its move and start the game again. Here, once we make a move we never recover from that step. Only we can try to give the best of the current situation.

Please follow, share, like and comment.

Artificial Intelligence : Problem Decomposition

Suppose we need to solve the problem of computing expression is:  ∫(X³ + X² + 2X + 3sinx)dx

We can solve this problem very intelligently by breaking down it into smaller sub problems, each of which
we can then solve by using a small collection of specific rules. Above figure shows the problem tree which is generated by using this technique of problem decomposition, we can solve very large problems very easily.

Here we can use recursive integration program that works as follow :-

Check whether the given problem immediately solvable (Yes or No).

If “Yes”, then the solution is returned directly.

If “No”, then the integrator check whether the given problem can decompose into smaller problem (Yes or No).

If “Yes”, then create sub smaller problems and call itself recursively.

If “No”, then problem is not solvable and decompose able.

 

Please subscribe, like, share and comment.

Artificial Intelligence Problem Characteristics

To choose an appropriate method for a particular problem, It is necessary to analyze the problem along following key dimensions:

1. Is the problem decomposable to independent smaller or easier problems? Read more…
2. Can solution steps can be ignored or undone if they prove wrong? Read more…
3. Is the problem’s universe predictable? Read more…
4. Is the best solutions are obvious without comparison to all other possible solutions? Read more…
5. Is the desired solution a state of the world or path of the states?
6. Is the lots of knowledge required to solve a problem or is knowledge only to constrain solutions?
7. Is the periodic interaction between human and computer required to solve a problem?

Click to read : History Of AI (Artificial Intelligence)