Before an AI problem can be solved, it is necessary to understand the problem completely and represent it in such a manner that it is easier to find a solution to it. This is done by AI Problem Analysis and Representation of the given problem using any of the two different approaches. These commonly used approaches to represent a problem in AI are as follows:
AI Problem Analysis
When analysing any given problems in AI, we go through a number of different stages. These stages are:
- Defining the Problem
- Gathering relevant Data
- Designing the Model
- Model Training
- Evaluating the Model
- Quality Assurance
- Maintenance of the Application
AI Problem Representation
Before the gathering of relevant information for the problem, we need to first define and represent the problem in a very precise manner. This is done using one of the commonly used approaches to represent a problem in AI. These are:
- State Space Representation
- Problem Reduction
Now, let us have a closer look at the approaches.
State Space Representation
The state space of a problem can be defined as the set of all possible states in which a problem can be represented and solved.
The method of State Space Representation involves the process of defining the state space, defining the start and the goal states, and searching for a path from the start state to the goal state across this state space.
The state space hence forms a graph or tree, where states are represented as nodes and the arcs connecting the nodes represents the actions. The method of search for the goal state from the start state is governed by a set of rules known as the production rules.
Hence, a state space consists of the following:
- Set of States
- Starting State
- Set of Actions and an Action Function
- Set of Goal States
- Criteria to check the quality of the acceptable solution (optional)
Example of State Space Representation
To understand the concept in a better manner, let us consider an example to solve the 8-puzzle. 8-puzzle is a tile puzzle which consists of numbers from 1-8 arranged in a 3 * 3 cube. One of the squares of the cube is empty which facilitates the motion of the squares numbered 1 to 8.
The aim of the puzzle is to reach the goal state where the numbers are arranged in an ascending order. i.e., as follows
From a state where the numbers 1 to 8 are jumbled i.e.,
Now, a standard problem formulation of the above will be as follows:
- States–It is a set of all possible states where the location of the blank tile and the numbers will differ in each specific state.
- Initial State – The state from where the problem starts is its initial state.
- Goal State – The state to be reached is the goal state.
- Legal Moves – These are the rules which will be followed in order to reach the
goal state. Here, the moves which are termed as legal are:
- Blank square moves Left
- Blank square moves Right
- Blank square moves Up
- Blank square moves Down
- Cost of Path – If we assume a cost of 1 here then the cost of the path will be the number of steps taken in order to reach the goal state.
Now, have a look at a part of the state space representation tree:
This will extend on and on till all the states are represented.
Advantages of State Space Representation
State Space Search has the following advantages:
- It defines a set of all possible states, operations and goal states.
- It helps us to trace the path taken starting from the initial state to the goal state. This helps us in identifying or tracing the sequence of operations required in reaching till the goal state.
Disadvantages of State Space Representation
State Space Search has the following disadvantages:
- It is practically impossible to explore all the states for a given problem.
- Due to the huge combinational states in the state space, we need a high amount of CPU resources for the computer system to handle the load efficiently.
It is not an easy task to find the search space for all problems. When the problems get complex in nature it becomes easy to solve the problem by breaking it into smaller problems which would be easier to solve as compared to the problem as a whole. This is where problem reduction method is used.
In problem reduction method, the given problem is divided or broken down into a set of sub problems. Now, a solution to these sub problems is easy to obtain. Once the solutions to the sub problems are derived, these solutions are hence combined back in order to get to the solution for the problem as a whole.
The structure used to represent such problems is known as an AND OR Graph / Tree. In this graph, we select successor nodes based on the branch. If the branch is an AND branch, then we find solutions to all successors here. But, when we have an OR branch, then we find one best successor as the solution. Hence this graph is named the AND OR graph (or tree).
Example for AND OR Graph
Let us assume a situation where you want to acquire a car for yourselves. Now, we would represent this situation using the AND OR graph as follows.
If we take a look at the graph, we come to know that if we pursue the AND branch then we will have to consider both the successor nodes as a combined solution for the parent node. Hence as a result we will first have to earn money first and then buy a car. But in case of an OR branch we simply select one alternate which is to steal here.