means–ends analysis
In plain wordsA problem-solving method that compares where you are with where you want to be, picks an action that shrinks the biggest difference, and sets itself smaller goals when that action cannot yet be taken.
A problem-solving strategy that repeatedly identifies a difference between the current state and the goal, selects an operator relevant to reducing that difference (using a table linking types of difference to operators), and, if the operator's preconditions are not met, recursively sets up the subgoal of satisfying them. Tackling differences in order of importance gives a crude hierarchy, and the recursion mixes goal-directed backwardbackward chaining, n.: A way of reasoning that starts from the question ('is this true?') and works backward, looking for rules that would prove it and then checking whether their conditions hold. reasoning with forward action. Means–ends analysis was the core mechanism of the General Problem SolverGeneral Problem Solver, prop. n.: A 1950s program meant to solve any well-defined puzzle by repeatedly comparing where it was with where it wanted to be and choosing steps that closed the gap. and influenced STRIPSSTRIPS, prop. n.: An early AI planning program, and the simple action language it introduced, in which each action lists what must be true beforehand, what becomes true and what stops being true. and later automated planningautomated planning, n.: The branch of AI that works out a sequence of actions to reach a goal, such as the steps a robot must take to assemble a part, from descriptions of what each action needs and what it changes. as well as cognitive models of human problem solving. It fails when reducing one difference undoes another, as in the blocks-world puzzle known as the Sussman anomaly.
Origin
Introduced by Allen Newell, Cliff Shaw and Herbert Simon in the General Problem Solver (1957–1959), modeled on think-aloud protocols of people solving logic problems; Newell and Simon's Human Problem Solving (1972) developed it as a psychological theory.
Related
- General Problem SolverGeneral Problem Solver, prop. n.: A 1950s program meant to solve any well-defined puzzle by repeatedly comparing where it was with where it wanted to be and choosing steps that closed the gap.
- automated planningautomated planning, n.: The branch of AI that works out a sequence of actions to reach a goal, such as the steps a robot must take to assemble a part, from descriptions of what each action needs and what it changes.
- STRIPSSTRIPS, prop. n.: An early AI planning program, and the simple action language it introduced, in which each action lists what must be true beforehand, what becomes true and what stops being true.
- backward chainingbackward chaining, n.: A way of reasoning that starts from the question ('is this true?') and works backward, looking for rules that would prove it and then checking whether their conditions hold.
- state space searchstate space search, n.: Solving a problem by treating every situation it could be in as a point on a map, with each possible move as a road between points, and searching for a route from the start to a goal.
- Allen NewellAllen Newell, prop. n.: An American computer scientist who, with Herbert Simon, wrote early AI programs that solved problems the way people do, and who sought a single theory of how the mind works.
Sources
- Newell, A., Shaw, J. C. & Simon, H. A. (1959). Report on a General Problem-Solving Program. Proceedings of the International Conference on Information Processing, UNESCO, Paris.
Mentioned in
backward chainingbackward chaining, n.: A way of reasoning that starts from the question ('is this true?') and works backward, looking for rules that would prove it and then checking whether their conditions hold., hierarchical task networkhierarchical task network, n.: A planning method that breaks a big task, such as 'travel to Paris', into smaller tasks, such as 'book a flight' and 'pack', using stored recipes, until only simple actions remain., STRIPSSTRIPS, prop. n.: An early AI planning program, and the simple action language it introduced, in which each action lists what must be true beforehand, what becomes true and what stops being true.