### Perit Cakir`s problem solving slides

```Problem Solving and Situated
Cognition
Murat Perit Cakir
COGS 503
Outline
• Classical Theory of Problem Solving
• Critiques to the Classical Theory
• Situated Cognition Perspective
– A case study of collaborative problem solving
• Discussion
Problem Solving
• We solve problems daily
– Not necessarily limited to math or science
• Usually motivated by our needs/desires
• Directed towards attaining a goal
• Problem solving research
– aims to develop a scientific theory to describe the
main elements and dynamics of problem solving
activities
Problem Solving
Current State
Goal
Classical Information Processing
Theory of Problem Solving
• Newell, A. & Simon, H. (1972). Human Problem
Solving. Englewood Cliffs, NJ: Prentice-Hall.
• Very influential on AI, Decision Science
• Based on well-defined, knowledge-lean problems
– e.g. games and puzzles like chess, towers of hanoi
• Assumption
– A theory for well-defined problems may be
augmented to cover ill-defined ones
Classical Theory
• Important concepts
– Problem Space
– States
– Operators
– Goals, subgoals
– Heuristics
• Abstract structure that corresponds to a problem
– Specifies the fundamental structure of the problem
– Capacities of agents for action may bring different task environments
to them
– Task environment includes only those actions that either bring agents
closer or farther from the the goal condition
• Abstract-> Same task environment can be instantiated in different
ways
– Chess with physical pieces vs computer-based
• Provides an interpretive framework
– What counts as a relevant pb solving move
Elements of Problem Solving
• Goal directedness – behavior is organized
toward a goal.
• Subgoal decomposition – the original goal can
be broken into subtasks or subgoals.
• Operator application – the solution to the
overall problem is a sequence of known
operators (actions to change the situation).
Problem Space
• Problem space – the various states of the
problem.
• State – a representation of the problem in
some degree of solution.
– Initial state – the initial (starting) situation.
– Goal state – the desired ending situation.
– Intermediate states – states on the way to the
goal.
Search
• Operator – an action that will transform the
current problem state into another problem
state.
• The problem space is a maze of states.
• Operators provide paths through the maze
– ways of moving through states.
• Problem solving is a search for the appropriate
path through the maze.
– Search trees – describe possible paths.
Production Systems
• Production rules – rules for solving a problem.
• A production rule consists of:
– Goal
– Application tests
– An action
• Typically written as if-then statements.
– Condition – the “if” part, goal and tests.
– Action – the “then” part, actions to do.
Features of Production Rules
• Conditionality –a condition describes when a
rule applies and specifies action.
• Modularity – overall problem-solving is broken
down into one production rule per operator.
• Goal factoring – each production rule is
relevant to a particular goal (or subgoal).
• Abstractness – rules apply to a defined class of
situations.
Sample Production Rules
Operator Selection
• How do we know what action to take to solve
a problem?
• Possible criteria for operator selection:
– Backup avoidance – don’t do anything that would
undo the existing state.
– Difference reduction – do whatever helps most to
reduce the distance to the goal.
– Means-end analysis – figure out what is needed to
reach the goal and make that a goal
Backup Avoidance
Tower of Hanoi
Missionaries and Cannibals
Move 3 missionaries & cannibals
across river. Cannibals cannot
outnumber missionaries or else they
will eat missionaries
To solve each of these problems one
must backup but most people will not do
this and so have difficulty.
Difference Reduction
• Select the operator that will produce a state
that is closer to the goal state.
– Or the one that produces a state that looks more
similar to the goal state.
• Also called “hill climbing”.
• Only considers whether next step is an
improvement, not overall plan.
• Sometimes the solution requires going against
similarity – hobbits & orcs.
Means-End Analysis
• Newell & Simon – General Problem Solver (GPS).
– A more sophisticated version of difference reduction.
– What do you need, what have you got, how can you get
what you need?
– Focus is on enabling blocked operators, not abandoning
them.
– Larger goals broken into subgoals.
General Problem Solver
Summary of Information Processing
Framework
• According to Newell & Simon PB Solving
– The ability to reduce difference between current state &
goal state
– Constrained by information processing system
• limited processing resources provide constraints on the degree to
which multiple moves can be considered
• Assumptions underlying GPS’s design
–
–
–
–
Serial processing: execute one thing at a time
Limited working memory
Propositions are the basic unit of LTM
Heuristically or strategically driven process
GPS vs Human Problem Solvers
• Think aloud protocols conducted with human problem
solvers show that humans approach puzzles in similar
ways (Greeno, 1974)
• GPS sometimes deviate from human problem solving
since humans tend to employ heuristics that will take
them closer to a solution (hill climbing)
• GPS is resilient to cases when hill-climbing performs
poorly (e.g. cannibals missionaries problem)
• GPS sometimes fail to find a solution since it applies
means-ends analysis very rigidly
GPS vs Human Problem Solvers
Well vs Ill-Defined Problems
• Puzzles
– unfamiliar
– involve no prior knowledge
– all necessary info. is present
in the problem statement
– requirements are
unambiguous
• Real-world problems
– familiar
– require prior knowledge
– necessary information often
absent
– solver must ask ‘what is the
goal’?
Case study of group problem solving
An Excerpt from VMT Spring Fest
• A team of 3 upper-middle school students (14-16 years old)
• Students were recruited via their teachers, who are Math
Forum users
• 5 teams completed 4 online sessions in 2 weeks
• A VMT project member was present in the room in case of
technical difficulties
• The members of the most collaborative team were
awarded with iPods
• The excerpt is taken from the first session of the team
VMT Chat
137
Extra tabs
(summary,
math topic,
wiki, browser,
help manual)
Explicit
reference
from chat
to white
board
Whiteboard
drawing
controls
Whiteboard
history
scrollbar
Who is active
on which tab
List of active
users in the
chat room
Message
to message
referencing
Drawing
activity
markers
embedded
in chat
Activity
awareness
messages
Here are the first few examples of a particular pattern,
which is made using sticks to form connected squares:
N
Squares
1
1
4
2
3
10
3
6
18
4
10 28
Sticks
How many squares will be in the Nth example of the pattern?
How many sticks will be required to make the Nth example?
Mathematicians do not just solve other people's problems,
they also explore little worlds of patterns that they define and
find interesting. Think about other mathematical problems
related to the problem with the sticks.
Go to the VMT Wiki and share the most interesting math
problems that your group chose to work on.
N=1
N=2
N=3
Excerpt 1
Co-construction of a new stick pattern
Excerpt 2
Constituting a shared problem
Excerpt 2 (cont.)
Developing a systematic counting approach
Questions
• How would you characterize the
– Problem space?
• Where is the problem space located?
• Were the group members primarily engaged
in search?
• What is the role of representations in the
group’s work?
• Do you think they understand each other?
Critique to Classical Theory from a
Situated Cognition Perspective
• Framing & Registration
• Interactivity & Epistemic Activity
– Interactions with others and cultural artifacts
– Role of external representations
– Adding structure to the environment
• Socio-cultural context
– Resources and Scaffolds
– Knowledge rich
Framing
•
Process of posing the problem in well-defined terms
– i.e. constructing the graph structure, identifying initial and goal states, subgoals etc.
•
Inappropriate abstraction filters away important cognitive processes relevant to
problem solving
– e.g. tic tac toe and the game of 15 are isomorphic mathematically but we rely on different
practices of reasoning when we play each
•
Street math vs school math
– Coconut sellers in Brasil, milk men in the US, grocery shoppers optimize their pb solving
performance by recognizing common patterns and using cultural resources
•
How agents frame a problem, how they project meaning into a situation,
determines the resources they see as relevant to its solution
•
A psychological theory of pb solving needs to explain many phases and dynamics
– how one sees a problem, why one sees it that way, how one exploits resources, interacts with
them, and solve the problems in acceptable time
Registration
• The activity of selecting environmental anchors to tie
mental/physical representations to the world
• In ecologically realistic problem solving settings registration is nontrivial
• e.g. driving around in a new city with a navigator
– You need to constantly anchor your physical location to the dynamic
representation presented in the navigator
• Registration is less of a problem in classical theory
– Puzzles constrain pb solving interactions to occur in a spatially
bounded location
• e.g. chess board, hanoi towers/pegs
Framing and Registration
• Framing and Registration mutually inform each other
• Cooking example
– Back and forth between the recipe and materials in the kitchen
– Recipe frames the problem in terms of things that are relevant to the
cooking process
• Ingredients, flame size, pots and pans, measurement cups
• Not in terms of chemical reactions that took place during cooking
– Framing constrains actions
• Our understanding of problems is usually tied to the resources and
tools at hand
• Problem solving involves moves back and forth between the
abstract and the concrete
Role of External Representations
• Problem solving is a process located partly in the mind, partly in the world
• External representations have a key mediating role in problem solving
• They bring affordances (cues and constraints on actions) that shape our
understanding of the problem
• Later work of Simon and Larken (1987) attempted to incorporate external
representations in their classical model
– But the focus remained on problem space and search heuristics, external
representations (diagrams, alternative symbolisms) were treated as secondary
aids
Role of External Representations
• Is an external representation same as its internal counterpart?
• Experiments on mental imagery of ambiguous objects indicate that
how people visually explore an external and mental image may
differ
• What if some of the mental constructs we use during problem
solving have a similar property?
Further Criticism
• Interactivity and epistemic activity
– Real world details of problem solving is not adequately captured by the notion
– Some of the ignored actions may be important in understanding human
problem solving (e.g. use of gestures, artifacts used to aid reasoning)
– Interactions with artifacts and other people can be used to explore the
structure of a problem and to manage its complexity
• Scaffolds, practices, resources available as aids for problem solving
– Problem solvers rarely work in isolation
• Knowledge-rich problem solving
– Most problems are ill defined, understanding a problem requires background
knowledge
– Even mundane tasks like shopping or cooking require background knowledge
But…
• Situated cognition does not offer an
alternative theory of problem solving
• It offers a conceptual framework
• Focuses on practices of problem solving, what
makes symbols, operators etc. meaningful to
humans
Further Analysis of VMT Excerpts
• Recurrent practical concerns for VMT participants
w.r.t. math artifacts and media affordances
– Identify and produce relevant mathematical artifacts to
constitute a shared problem
– Refer to those artifacts and their relevant features
– Manipulate and observe the manipulation of those
artifacts based on math practices known to participants
Representational Practices
• Group members display their reasoning by enacting
representational affordances of VMT
– The drawing actions performed by 137 and Qwertyuiop
• The organization of the lines revealed in 137’s first attempt led
Qwertyuiop to project what is needed
– Jason’s question with the explicit reference
• Displays his understanding of the hexagonal pattern being developed
• Availability of the production process
– Whiteboard affords an animated evolution of its contents that
makes the reasoning embodied in drawing actions visible
Referential Practices
• Group members establish relevancies across semiotic
modalities by enacting referential uses of the available
system features
– Verbal and explicit references
• The indexical “hexagonal array” refers to shared drawing coconstructed on the whiteboard.
• Jason’s use of the referencing tool to highlight a particular stage
– Temporal organization of actions
• The addition of 3 red lines were interpreted as a proposal to split
the hexagon into 6 parts, because it was made relevant in chat
Referential Practices (cont.)
• Through referential practices group members
– Isolate objects in the shared visual field and associate
them with local terminology stated in chat
– Establish sequential organization among actions
performed in chat and whiteboard spaces
so it has at least
6 triangles? in
this, for instance
Shared Mathematical Understanding
• In short, mathematical understanding at the group level is
achieved through the organization of representational and
referential practices
• Persistent whiteboard objects and prior chat messages form a
shared indexical ground for the group
• A new contribution…
– is shaped by the indexical ground
• i.e., interpreted in relation to relevant features of the shared visual field
and in response to prior actions
– reflexively shape the indexical ground
• i.e., give further specificity to prior contents
– set up relevant courses of action to be pursued next
Summary
• Shared mathematical understanding is a process, a
temporal course of work in the actual indexical detail
of its practical actions, rather than a process hidden in
the minds of the group members
• Mathematical understanding can be located in the
practices of collective multimodal reasoning displayed
by teams of students through the sequential and
spatial organization of their actions
```