Problem solving - The general problem solver PDF

Preview

Summary

Theories of problem solving - the general problem solver...

Description

The General Problem Solver Problem space theory (Newell & Simon, 1972)   

More steps = harder problem Navigate through steps Use heuristics to help: o Means-end analysis o Depth-first approaches o Backup avoidance (don’t like to go back to square 1) o Difference reduction/hill-climbing (get closer to the goal) o Anti-looping (don’t keep making the same move)

Sub-goal creation   

Note the difference between the current state and the goal-state (means-end analysis) Create a sub-goal to reduce this difference Select an operator that will solve this sub-goal

Any evidence? 

Verbal protocols suggest people do this (Newell & Simon, 1972) o This relies on people knowing what they are thinking (disputed by Nisbett & Wilson, 1977 – we don’t always know what we are thinking!) o Doesn’t agree with Pinker’s mentalese!

Experimental evidence? Egan & Greeno - 1974    

5 and 6 disc Tower of Hanoi Experimental group practise of 3 and 4 disc Control group have no prior experience Experimental group have better performance and better memory for top-level goals o Evidence of sub-goals?

State action tree involved in problem solving 

Cannibals and missionaries o Three missionaries and three cannibals want to cross a river. The boat holds two people. A person must be in the boat in order for it to move between banks. If there are more cannibals than missionaries at any time, on any bank, then the missionaries will be eaten

Introduction to Cognitive Psychology – Problem Solving: Lecture 2



Do people use a state action tree to complete the cannibals and missionaries task? Thomas (1974) o In a variant of the cannibals and missionaries problem (using orcs and hobbits), participants made a series of quick moves then paused before the next sequence o Participants paused and took longer over their next move and produced more errors at certain points at the completion of each sub-goal o These pause and error points occurs when the solution to the problem involved apparently moving away from the goal state (find these points in the problem space) o We don’t like to feel like we are moving away from the goal state, so we take a pause because we cannot commit to potentially moving away from the goal state. In the end, we have to accept failure and make the move, whether it means we have to move away from the goal state or not

Atwood & Polson (1976): The water jugs problem   

Means-ends analysis Anti-looping strategy One move look-ahead strategy o Limited by working memory constraints – humans can only remember 7 +/- 2 things in their STM and therefore cannot look ahead and remember previous or future moves in the way that they want to in order to solve the problem efficiently  Supports GPS – working memory limits how far we can look ahead Solution States Initial Intermedi ate

to the water-jug problem Jar 1 Jar 2 Jar 3 8-8 5-0 3-0 8-3

5-5

3-0

8-3 6-6 8-1 8-1 Goal 8-4 Do people use means-ends analysis?

5-2 5-2 5-5 5-4 5-4

3-3 3-0 3-2 3-3 3-0





Thomas (1974): Suggests people do ordinarily make use of a means-ends analysis o People must construct new sub-goals that seemingly increase the distance between the current state and the goal state (the correct move in a couple of places seemingly moves one further away from the problem – this requires a look-ahead ability and draws on working memory) BUT Greeno et al., (1974): Hobbits and orcs task shows that the GPS uses meansend analysis but people do not! o Instead, people use forward search, hill climbing, reasoning by analogy and other strategies – people use small forward steps, not means-end analysis

Simon & Reed (1976) 

In a version with 5 cannibals and 5 missionaries (and a boat that can only hold 3 people), it was noted that there are three distinct strategies participants used, often using a mixture of all three 1. Balancing: maintain equal numbers of Cs and Ms on each bank 2. Means-ends: move people to the goal side of the river 3. Anti-looping: don’t carry out moves that reverse the move just made

Does means-end analysis always work?

Introduction to Cognitive Psychology – Problem Solving: Lecture 2

  

People use various strategies, not just means-end analysis People don’t like moving away from the goal What about memory effects?

Anzai & Simon (1979)    

Single participant had 4 attempts at solving the 5 disc version of the Tower of Hanoi Participant used different strategies on each attempt at got near the solution every time Participant seemed to try to avoid making the same errors as before (loop avoidance heuristic) By avoiding errors, the participant found sequences of moves that were remembered and used in later attempts (learning)

Limitations to the General Problem Solver (GPS) 

  

  

Important differences between human performance and GPS performance o GPS remembers better which moves have previously been made – it does not have the limitations to working and STM like humans have o GPS is more short sighted than humans – only looks one move ahead o The GPS does not have any problems with moving away from the goal state – humans do  The GPS is not a good model of human performance – has completely different cognitions Doesn’t explain ‘insight’ Doesn’t look at individual differences Although it can apply itself well to lab problems and well-defined problems, the GPS cannot apply itself to real-world, abstract and ill-defined problems because of its lack of experience of the world and human cognition o It needs a clear set and guideline to work with Action selection: don’t have to attempt a problem at all Innate biases e.g. people tend to start many problems the same way – where do these biases come from? Outcome evaluation – how do you decide if the problem is over? (Ohlsson, 2012) – A bit like an ill-defined problem

The 9 dot problem  



Have to connect all the dots with four straight lines and without lifting the pen from the paper Gestalt theory explains the problem o The 9 dots form a square shape and people assume that the ‘edges’ of the ‘square’ are the boundaries of the problem o Participants misrepresent the operators of the problem (Isaak & Just, 1995; Lung & Dominowski, 1985; Ohlsson, 1990) Macgregor et al., 2001 o Post-gestalt theories do not predict difficulty of the 9 dot problem – they also do not predict how helpful clues will be to solve the problem o This is unlike similar ‘move’ problems (e.g. missionaries and cannibals, Tower of Hanoi, water jugs) o One source of difficulty might be that the goal state of the 9 dot problem is not specified unlike other ‘move’ problems (Weisberg & Alba, 1981a)

Problems of ill-defined problems 

9 dot problem – what is the goal state?

Introduction to Cognitive Psychology – Problem Solving: Lecture 2





If Newell & Simon were right, then without a goal state, it becomes almost impossible to apply means-end analysis (you are comparing your current state with…what? Not many people solve the 9 dot problem - how do you solve it?

Progress monitoring theory 



A computer model based on two heuristics 1. Maximisation heuristic: aim at sub-goal (a bit like hill-climbing) 2. Progress monitoring: how successful is each operator at getting to the goal (like means-end analysis). Repeat successful operator. Operator fails = stuck (criterion failure)  Criterion failure: occurs when participants seem to be failing to make headway towards the goal state. It is important because it signals when and why participants decide to change strategy – could lead to insight (Kaplan & Simon, 1990) Applying a new solution: Like Ohlsson, MacGregor et al., (2001) suggests that constraint relaxation (realising that you don’t have to stick to the rules e.g. realising that you don’t have to end the line at a dot) is critical

Evidence for progress monitoring theory 

Mean Percentage Correct



A ‘locally rational operator’ that moves the problem solver towards the goal (connecting all of the dots) may be to draw lines that connect as many dots as possible Dominowski (1985) found 95% of participants chose first lines connecting three dots and 63% of second lines connected two dots (the maximum possible in each case)  MacGrego r et al., Results of Experiment 1 (2001) 93 90 tested 100 80 how much 90 73 difficulty 80 60 is caused 70 50 by having 60 to extend 50 Trial 1 the lines 40 Trial 10 30 and turn the line 20 10 where 0 there is no 0 90dot 11 dot 12 dot 13 dot dot (difficulty decreases as the number of dots increases). Allows testing f model’s predictions against human performance

Introduction to Cognitive Psychology – Problem Solving: Lecture 2

Strengths of GPS      

Has created a normative model – a base-line model to understand the basics of how human cognition might work Provides a solid foundation for research Explains puzzle-solving reasonably well Explains how we go from reasoning about new problems to applying earlier solutions (learning/analogical transfer) Ties in with existing models of cognition (e.g. memory) Has resulted in several successful AI expert systems (e.g. MYCIN)

Limitations of GPS    





Doesn’t have much ecological validity Most ‘real’ problems are not well-defined and the machine can only deal with welldefined problems Choice of which ‘operators’ to choose from is not well specified Heuristics are vague o People use lots of different ones and not that effective heuristics that interfere with one another (e.g. balancing interferes with means-ends analysis)  what causes us to abandon a heuristic and use another one? Homunculus effect 9 dot problem is a problem for GPS

Introduction to Cognitive Psychology – Problem Solving: Lecture 2...