Problem Solving as Searching a State Space
Cognitivist explanations of problem solving are based on a generalized model of searching in a state space.A state space consists of the tree of symbolic states that are generated when all possible operators are iteratively applied to the current state of symbols representing objects composing the problem. If the problem is solvable, then eventually the goal state will be symbolically generated. The solution to the problem then consist of applying in sequence the real-world operators that are represented on the branch that terminates in the goal state.
Example: The Towers of Hanoi
In this famous problem, a number of perforated disks (64 in the mythic problem, 3 in this example), each a different size, are placed on top of each other in order of size, biggest at the bottom, on one of three pillars. The task is to transfer the entire pile to a specified pillar, moving only one at a time onto a pillar, and only placing a smaller disc on top of a larger one.The state space tree generated by this problem is illustrated below for two transitions. If the tree were fully expanded, the goal state would eventually be reached — if it can actually be done!
Note that, because some transitions return the disks to an earlier state, the tree if fully expanded would be of infinite size. So whilst generating the entire tree, searching it for the goal state, and reading off the transitions that lead to that state, is a guaranteed method of solving the problem, it's not actually possible to do (in a finite universe).
Whilst this is an extremely simple example, the contention is that any problem that involves transforming either material or abstract objects from one state to a goal state — that is ANY PROBLEM — can be analysed in this way.
As we don't appear to have infinite resources of material or time at our disposal, the issue then becomes how to manage the expansion and search of the state space so that a solution can be found economically.
For example, in the Towers of Hanoi problem, we could avoid expanding any branch that would result in the generation of a previous state, as we can be certain that the best solution to the problem will not be found by following that line.
However, we can't come up with a general solution like that to trim every problem tree. There will be some problem that every general strategy will not work for. (Developing a full understanding of this will take you into the realms of mathematical logic. For an entertaining and provocative introduction to this topic see Hofstadter, and for an extremely readable introduction to this in computer science see Harel.)
However, some methods are applicable to a wide range of problems, and whilst there is no guarantee that they will always work, they can be very successful. These are heuristic methods. ("heuristic: ... principles used in making decisions when all possibilities cannot be fully explored" Chambers English Dictionary.) A number of heuristic approaches which it is conjectured that humans use, are described below.
General Problem Solving
Difference-Reduction Method
Try to resolve the difference between the current state and the goal state. I.e., select the operator that will make the current state most like the goal state. This implies a need for a means of evaluating similarity between states.Experimental Evidence
Evidence that humans do apply this method is given by Atwood and Poulson (Atwood) using a water jug problem. Subjects were told:You have three jugs, which we will call A, B, and C. Jug A can hold exactly 8 cups of water, B can hold exactly 5 cups, and C can hold exactly 3 cups. A is filled to capacity with 8 cups of water. B and C are empty. We want you to find a way of dividing the contents of A equally between A and B so that both have 4 cups. You are allowed to pour water from jug to jug.The two shortest paths to the solution are:The subjects preferences for changes of state were recorded.
- 1:A>C, 2:C>B, 3:A>C, 4:C>B, 5:B>A, 6:C>B, 7:A>C, 8:C>B
- 1:A>B, 2:B>C, 3:C>A, 4:B>C, 5:A>B, 6:B>C, 7:C>A
From the initial state, twice as many preferred 2.1 (A>B) as 1.1 (A>C). This results in a state more like the goal (i.e., B containing water).
For many steps, similarity to the goal is a good heuristic, but in both 1.5 (B>A) and 2.4 (B>C) which are crucial steps, it does not apply.
At these critical steps, 50% the time, subjects deviated in favour of moves that appear closer to the goal.Means-Ends Analysis
Carries out state space searching by state evaluation and operator ordering. If a difference is detected between the current and goal states, then a subgoal to eliminate the difference is created.Apply the operator that will make the most important difference to the current state.
In selecting the operator to apply, match the conditions of the operator to the current state to identify the most important difference.An example of this:
I am hungry and I want to be full. What's the difference between what I have and what I want? An empty stomach. What changes the emptiness of my stomach? Eating food. But I don't have any food.The means-ends algorithm expressed in pseudo code (after Anderson p.212) is:
I want to have some food. What's the difference between what I have and what I want? The presence of food. What changes the presence of food? Searching, shopping, hunting, growing food.
I search for food, but there is nothing available.
I decide to shop for food. What do I need to shop? Money.
But I don't have any money.
I want some money. How do I get money? Withdraw from the bank, sell something, steal.
I decide to withdraw from the bank.
I want some money from the bank. What do I need to get money from the bank? I must be at the bank.
I want to be at the bank. What is the difference between where I am now and where the bank is? Distance. What changes distance? Walk, cycle, drive, bus.
.....
and so on.To Transform current state into goal stateMatch current state to goal state to find the most important difference.To Eliminate the difference.While difference detected between current and goal states.
Subgoal: Eliminate the difference.Exit: Success.If fail then EXIT: Failure.
Match current state to goal state to find the most important difference.
While there are operators to be examined and difference has not been eliminated.Search for operator relevant to reducing the difference.If no operators found then EXIT: Failure.
While success do.
Match condition of operator to current state to find most important difference.If differences are detected then
Eliminate the difference. (N.B. a recursive step)ElseEXIT: Apply operator.Newell and Simon’s GPS
A very influential early artificial intelligence system that used means-ends analysis developed by Newell and Simon in the late 60's (Newell). GPS stood for "General Problem Solver.Working Backwards and Non independent Goals
One method of problem solving that is frequently met with in areas such as proofs in mathematics, is to work backwards from the goal. Formally, this makes use of the logical rule of implication, modus ponens:(p & (p -> q)) -> q I.e., if we wish to prove q, and we have the rule p -> q, them we need to prove p.
When this is applied to planning problems, issues of subgoals interfering with each other arise. For example, for the problem of painting both a ceiling and a ladder green, when the ladder is needed to reach the ceiling, what follows is not a great subgoal decomposition, (sequence is implied by horizontal ordering) (Anderson p.217 after Sacerdoti):
Additional constraints need to be taken into account, e.g., that painting the ladder will make it unavailable for use.
Difficulties in problem solving can occur when such non independent goals arise. A whole range of techniques have been developed in artificial intelligence, particularly as applied to planning, to deal with these issues. However, how humans actually do this is an open question.
Use of Analogy
In this method, the known solution to one problem is used to guide the development of a solution to another problem. One straightforward example of this method in use is when a programmer takes a piece of code that implements a complicated function and modifies it to serve another purpose.More subtle analogies may also be used. For example, Gick and Holyoak (Gick) presented subjects with a medical problem involving the use of radiation to destroy cancerous tumour without killing the surrounding tissue. Very few of their subjects were able to come up with an appropriate solution. However, after they were told a story about a fortress being attacked by small bands of soldiers approaching simultaneously from many different directions, nearly 100% of the subject came up with an analogous solution to the cancer problem.
References
Anderson, J. R., 1985 "Cognitive Psychology and Its Implications" (Second Edition) W.H. Freeman and Company, New York.Atwood, M. E., & Polson, P. G., 1976 "A process model for water jug problems" Cognitive Psychology, 8, 191-216, in Anderson, 208-211.
Gick, M. L., & Holyoak, K. J., 1980 "Analogical problem solving" Cognitive Psychology, 12, 306-355.
Harel, D., 1987 "Algorithmics: The spirit of computing" Addison-Wesley.
Hofstadter, D., 1979 "Godel, Escher, Bach: An eternal golden braid" Harvester Press.
Newell, A., & Simon, H. 1972 "Human problem solving" Prentice-Hall.
Sacerdoti, E. D., 1977 "A structure for plans and behaviour" Elsever North-Holland.
Next