Means-Ends Analysis Search Technique (Algorithm) – Artificial Intelligence
In this tutorial, I will how to apply Means-Ends Analysis Search Technique (Algorithm) to solve the given problem.
Video Tutorial – Means-Ends Analysis
Means-Ends Analysis
In Artificial Intelligence, we have studied many search strategies which traverse either in forward or backward direction, but a mixture of these two is usually appropriate to solve a complex and large problem.
Such a mixed search algorithm, allow us to solve the major part of a problem first and then go back and solve the small problems which arise while combining the major parts of the problem.
Such a technique is called Means-Ends Analysis (MEA).
The MEA analysis process centered on finding the difference between the current state and goal state and applying the operators to reduce this difference.
How Means-Ends Analysis Algorithm Works
To solve a given problem, we need to apply the MEA Algorithm recursively.
Following are the major steps that describe the working principle of the MEA search technique to solve the problem.
- First, find the difference between Initial (start) State and Goal State.
- From the available set of operators, select an operator which can be applied to the current state to reduce the difference between the current state and goal state.
- Apply the selected operator.
Means-Ends Analysis – Operator Subgoaling
In the MEA process, first, we find the differences between the current state and the goal state.
Once we find the differences, then we apply an operator to reduce the differences.
But sometimes it is possible that an operator cannot be applied to the current state.
Hence we divide the current state into sub-problems, and then we apply an operator on sub-problems, such type of analysis is called Operator Subgoaling.
Means-Ends Analysis Algorithm
Let’s assume the Current state as CURRENT and Goal State as GOAL, then the following are the steps of the MEA algorithm.
Step 1: Compare CURRENT to GOAL, if there are no differences between both then return Success and Exit.
Step 2: Else, select the most significant difference between CURRENT and GOAL and reduce it by doing the following steps until success or failure occurs.
a) Select a new operator O which is applicable for the current difference, if there is no such operator, then signal failure.
b) Attempt to apply operator O to CURRENT. Make a description of two states.
i) O-Start, a state in which O’s preconditions are satisfied.
ii) O-Result, the state that would result if O were applied In O-start.
c) If (First-Part <—— MEA (CURRENT, O-START) And LAST-Part <—– MEA (O-Result, GOAL), are successful, then signal Success and return the result of combining FIRST-PART, O, and LAST-PART.
Means-Ends Analysis – Solved Example
Let’s take an example to understand how the MEA algorithm works.
Let’s assume the initial state and goal state as given below.
In this problem, we need to get the goal state from the initial state by finding differences between the initial state and the goal state and applying suitable operators.
To solve the given problem, we need to find the differences between the initial state and the goal state, and for each of these differences, we will apply an operator to generate a new state.
The operators we have for this problem are:
- Move – Move the object diamond outside the circle
- Delete – Delete the black circle
- Expand – Expand or increase the size of the diamond
1. Evaluating the initial state:
In the first step, we will evaluate the initial state and will compare the initial state and goal state to find the differences between both states.
2. Applying Delete operator:
As we can check the first difference is that in the goal state there is no dot symbol that is present in the initial state, so, first, we will apply the Delete operator to remove this dot.
3. Applying Move Operator:
After applying the Delete operator, the new state occurs which we will again compare with the goal state. After comparing these states, there is another difference that is the square is outside the circle, so, we will apply the Move Operator.
4. Applying Expand Operator:
Now a new state is generated in the third step, and we will compare this state with the goal state.
After comparing the states there is still one difference which is the size of the square, so, we will apply Expand operator, and finally, it will generate the goal state.
Summary:
In this tutorial, we understood the Means-Ends Analysis Search Technique (Algorithm) – Artificial Intelligence. If you like the tutorial share it with your friends. Like the Facebook page for regular updates and YouTube channel for video tutorials.