MEA (Means-Ends Analysis) is a problem solving strategy first introduced in GPS (General Problem Solver) [Newell & Simon, 1963]. The search process over the problem space combines aspects of both forward and backward reasoning in that both the condition and action portions of rules are looked at when considering which rule to apply. Differences between the current and goal states are used to propose operators which reduce the differences. The correspondence between operators and differences may be provided as knowledge in the system (in GPS this was known as a Table of Connections) or may be determined through some inspection of the operators if the operator action is penetrable. This later case, which is true of STRIPS-like operators, allows task-independent correlation of differences to the operators which reduce them. When knowledge is available concerning the importance of differences, the most important difference is selected first to further improve the average performance of MEA over other brute-force search strategies. However, even without the ordering of differences according to importance, MEA improves over other search heuristics (again in the average case) by focusing the problem solving on the actual differences between the current state and that of the goal.
Return to the Table of Contents.