What You Will Learn
Problem Representation in AI: Introduction
Problem Representation in AI: Artificial Intelligence (AI) is a fastly growing field of computer science and engineering with the latest objective to build machines that are capable of acting, thinking, and behaving like human beings.
Anyhow, the way involved in the development of intelligent systems and machines is not so easy process, as it would have been invented by early researchers and analyst, instead it is one of most difficult, complex and in one way or other, most complicated job ever taken by humans on their hands, since researchers is trying to prototype his own mind. But there are many problems in these prototypes like Safety, Computation Power, Trust, Job Loss concern, etc. Before an AI problem can be solved it must be represented as a state space.
Weak and Strong AI
AI can be divided into two major categories, namely weak AI and strong AI.
The Strong AI line of thinking is very exuberant about AI and makes a strong possibility that computers can be made to think approximately equal to the level of humans and they can possibly be aware about themselves.
The Weak AI is however not so exuberant about the result of AI and it simply says that fewer features can be added to computers to make them more useful tools. It says that computers cannot be made more intelligent equal to human beings unless constructed absolutely differently.
Problem representation in AI
Before a solution can be found, the basic condition is that the problem must be defined very accurately. By defining it perfectly, one converts the problem into real workable states that are really understood.
The most common approaches of problem representation in AI are:-
State Space Representation and Problem Reduction
State Space Representation:
It is a set of all possible states for a given problem is known as the state space of the problem. Let suppose you are asked to make a cup of milk tea. What will you do? You will verify whether the necessary ingredients like tea leaves, milk powder, sugar, kettle, stove are available.
If so, you will follow the following steps to make a cup of tea:
1. Boil necessary water in the kettle.
2. Take some of the boiled water in a cup and put 1 very full teaspoon of tea leaves in the cup to make decoction.
3. Add milk powder to the remaining boiling water to make milk.
4. Now mix decoction and milk.
5. Add sufficient quantity of sugar to your taste and the tea is ready.
It’s time to think what has exactly happened. You started with the ingredients which is your initial state, followed a sequence of steps are called states and at last had a cup of tea which is your goal state. You added only needed amount of tea leaves, milk powder and sugar (operators). The following fig shows the sequence:
Problem Reduction:
In this technique a complex problem is dividing into a set of primitive sub problems. Solutions for these sub-problems are easily obtained. The solutions for all the sub-problems simultaneously give the solution for the complex problem.
In fact, the human brain adopts this method for finding solutions to majority of problems it face.
For example we consider the activities that must be done to set right a car punctured tyre. The following fig. shows the activities. The top level specifies the overall goal which is combination of tasks given in level 2, level 3 and level 4 indicate primitive sub-problems.
The above figure. is a pictorial representation of the problem using AND/OR tree. You can see an arc connecting different branches is called an AND tree.
Between the complex and the sub-problem, there exist two types of relationships. AND relationship and OR relationship.
In AND relationship, the solution for the problem is gained by solving all the sub problems.
In OR relationship, the solution for the problem is gained by solving any of the sub problems.
Process of problem-solving
First of all, discuss some terms related to AI problem and solution methodology:
Problem:
It is the real question or problem which is to be solved. For solving a problem it needs to be exactly defined. The definition means, defining the start state, goal state, other valid states and transitions.
Search Space:
It is the complete set of states which included start and goal states, where the answer to the problem is to be searched.
Search:
It is a method of finding the solution in search space. The input to search space algorithm is a problem and output is a solution in the form of the action sequence.
Well defined problem:
A problem definition has three major components. Initial state, final state, space including transition function or path function. A path cost value function assigns some numeric value to each path that specifies the superiority of that path.
Solution of the problem:
A solution of the problem is a path from initial state to final state. The movement from start states to goal states is instructing by transition rules. In the group of all solutions, which solution has least path cost is called optimal solution.
Thus, it is fact that the method of solving problem through AI techniques involves the process of defining the search space, deciding about initial and final state and then finding a path from start state to goal state using search space. The act from start state to goal state is guided by transition rules or production rules.
Hence, to build an AI computational system to solve a particular problem the following actions are needed to be performed.
- Define the problem precisely; this definition must include actual specifications of start states and goal states of the problem.
- Analyze the problem; this phase abstracts the important features of the problem that can have an great impact on the appropriateness of different possible techniques used for solving the problem.
- Represent and isolate the task knowledge that is necessary to solve the problem.
- Select the best problem solving technique and implement this technique to the particular problem.
Problem solving in AI
There are two types of solving a given problem in AI:
- Uninformed Search or Blind Search
- Informed Search or Heuristic Search
Uninformed Search:
In this strategy there is no additional information about the states except the information provided in the problem definition. They can only make the successors and differentiate a goal state from a non-goal state. This type of searches does not have any internal state, that’s why it is also known as Blind search.
Types of UnInformed searches
- Breadth-first search
- Uniform cost search
- Depth-first search
- Depth-limited search
- Iterative deepening search
- Bidirectional search
Informed Search:
In this strategy additional information is given about the states beyond the problem definition. This type of search uses problem-specific information to find more efficient solutions. This search maintains some sort of internal states via heuristic functions which provides hints, so it is also called heuristic search.
Types of Informed searches
- Best first search or Greedy search
- A* search
You may also know: What is Voice Speech Recognition | How does it work?