Problem Solving



Overview

Foundation Issues in Cognitive Science

All Intelligent Behavior Can Be Described

as Problem Solving

Programs Can Be Written To Search

Problem Spaces

The Computational Complexity is O(bn) where

b is the branching factor and n is the number

of operators in the solution path

For interesting problems, b and n can be large

The Psychology 0f Problem Solving and Skilled

Performance

Common Themes

Fundamental Role of Similarity

Task Orientation

Interactions of Basic Processes to

Generate Action

Learning

Computer Simulation Models

Artificial Intelligence

Dealing with O(bn)

Learning the Hard Way About Values of b and n

Chess, Math, etc. b = 10 to 30, n = 10 to 40

Scene and Language Understanding, etc.

b and n Much Larger

Algorithms verses Heuristic Methods

Heuristic Search Methods

Reduce b by “ignoring” alternatives

Best First Search, Means-Ends Analysis

Look ahead (chess, etc)

Planning by Abstraction (reduce both b and n)

Problem Reduction

Changes in Representation (reduce both b and n)

Learning (reduce b to 1 in the limit)

Problem Space Hypothesis

The fundamental organizational unit of all human goal-oriented symbolic activity is the problem space.

Assumption:

Fundamental process underlying intelligent

action is Search

Alternative:

Language comprehension and knowledge-based

inferences

PROBLEM SPACE

knowledge states

operators that generate new knowledge states

a sequence of operators describes a path

PROBLEM

a set of initial states

a set of goal states

a set of path constraints

the problem is to find a path from a start state

to a goal state that satisfies the path constraints

Simple Cases

Tower of Hanoi

Possible Disk Configuration Generated by

Legal Moves

Water Jug Problem

Gets More Complex Quickly

“Right” Representation and Insight Problems

SEARCH CONTROL

Decide to quit the problem

Decide if a goal state has been produced

Select a state from the stock to be the current state

Select an operator to be the current operator

Decide to save the new state just produced by an operator

Operate Within the Following Cycle

1. Select a state; Select an operator

2. Apply operator to a state producing a new state

3. Decide if a goal state; decide to quit; decide to save a new state

Search control depend on know that is immediately available

Resource and Capacity Limits

Serial Action:

At most one problem space operator can be performed at one time

Problem solving will consider on one move at a time

In the problem space, maybe several moves in the external word

Example: A move a two disk stack in the tower of Hanoi

Finite Stock:

The subject has a limited number of states (the stock) available to become the current state.

(i.e. humans can and will only consider a limited number of alternatives)

Search Control:

Use only immediately available knowledge

Multiple problem spaces, e.g. an operator selection space

Time course of behavior: 5 to 15 second per state

Grain size of analysis: very detailed in comparison to most psychological models

Search Control II (Reduce b)

Search Methods

Generate and Test

Heuristic Search: Depth, Breadth, or Best First

Hill Climbing*

Mean-End Analysis

Operator Subgoaling

Planning

Evaluation Functions (Computers)

Distance To Goal

Likelihood that State Is On Solution Path

Weighted Average of Desirable Properties



Evaluation Functions (Human)

Similarity of Appearance to Goal

Similarity of Meaning to Goal

Knowledge that This State Is On Solution Path

Means-Ends Analysis

General Problem Solver

Newell, Shaw, and Simon (1968)

Difference Reduction

Several Kinds of Differences Between Goal and Current State

Ends (goals and subgoals)

Set Up Goals and Subgoals to Reduce Differences

Means (Operators)

Operators Effect Some Differences and Not Others

Table of Connections

Examples

Tower of Hanoi

Algebra

Monkey and Bananas

Top Goal =

(Transform the Initial-Object into the Desired-Object)

Initial-Object =

(Monkey’s-Place = Place-1, Box’s-Place = Place-2,

Contents-of-Monkey’s-Hand = Empty)

Desired-Object =

(Monkey’s-Place = On-Box,

Box’s-Place = Under-Bananas,

Contents-of-Monkey’s-Hand = Bananas)

Operators

Walk, Move-Box, Climb, Get-Bananas

Preconditions

Difference Ordering

Table of Connections

| |Monkey-Place |Box-Place |Monkey-Hand |

|Walk |X | | |

|Move-Box |X |X | |

|Climb |X | | |

|Get-Bananas | | |X |

Trace of GPS Solving Problem

1 Transform Initial-Obj into Desired-Obj

2 Reduce Contents-of-Monkey’s Hand Diff On Initial-Obj

3 Apply Get-Bananas on Initial-Obj

4 Reduce Location-of-Box Diff On Initial-Obj

5 Apply Move-Box to Under-Bananas On

Initial-Obj

6 Reduce Location-of-Monkey Diff On Initial-Obj

7 Apply Monkey Walk to Location of Box on Initial-Obj

(Monkey’s-Place = Place-2,

Box’s-Place = Place-2,

Contents-of-Monkey’s-Hand = Empty)

8 Apply Move-Box to Under-Bananas

(Monkey’s-Place = Under-Bananas,

Box’s-Place = Under-Bananas,

Contents-of-Monkey’s-Hand = Empty)

9 Apply Get-Bananas to Current-Obj

10 Reduce Location-of-Monkey Diff

11 Apply Climb to Current-Obj

12 Apply Get-Bananas to Current-Obj

13 Transform Initial-Obj into Desired-Obj

Psychology of Problem Solving

Major Traditions

Problem Taxonomies

Theoretical and Empirical Methodologies

Levels (Kinds) Of Theoretical Analyses

Understanding and Search

Major Research Traditions

Cognitive Action

Account for Complex Action Sequences

General behavior theory

(Thorndike, Hull, Skinner, Tolman, Staats, .)

Modern cognitive theory-

e.g., Rule-based models of skill acquisition

(Newell, Simon, Anderson, .....)

Cognitive Representation

Mental Representations That Generate

Action Sequences

Gestalt psychology

(Duncker, Katona, Kohler, Wertheimer, ...)

Modern research on representation

(Greeno, Kintsch, Simon, ....)

Modern Research On Problem Solving Attempts to Synthesize the Two Traditions

Problem Taxonomies

Task Orientation

How are various tasks related?

Well-Structured (Closed) Problems

Puzzles

Instructional Problems

Characteristics of ...

Explicit goal

Known operators

Known values of b and n, often small!

Ill-Structured (Open) Problems

Design

Real-Life” Problems

Characteristics of ...

b and n large or indefinite!

Ill-Structured Characteristics of Well-Structured

Problems (Simon)

Decomposition of an Ill-Structured Problem Into

A Collection of Well Structured Problems

Theoretical and Empirical Methodologies

Explicit Process Models

Computer Simulations

Production Systems (Rule-Based)

Verbal Protocol Analysis

Comparisons between Novices and Experts

Problems designed for the instruction of novices

Common task done by both experts and novices

Task done by experts

Problem Solving as an Arena to Test General Theories

Levels (Kinds) Of Theoretical Analyses

Decomposition into “Higher-Level” Processes

Preparation, Insight, Creativity, Incubation, Set,

Functional Fixedness, Brain Storming, ...

Demonstrations of ....

Process Models

Rules

Elementary Information Processes

Description verses Explanation ...

Demonstrations verses Explanations ...

Continuum Hypothesis (Simon)

Solution of Ill-structured problems by reduction

to a collection of well-structured problems

Creativity and scientific discovery can be

explained using the same processes used

to solve well-structured problems

E.g., Insight is just a memory process (Recognition)

Understanding and Search

Problem Solving as

Understanding (Comprehension)

(Wertheimer, Hayes and Simon, Kintsch, ....)

Search

(Newell, Simon, AI Literature...)

Problem Space Hypothesis

Understanding-Search

Increasing Importance of Understand Processes

Multiple Problem Spaces

Weak Methods In Human

Generate and Test

Means-Ends Analysis

Difference Reduction-Similarity

Operator Subgoaling

Problem Decomposition (Reduction)

Planning by Abstraction

Difference Reduction-Similarity

A Form of Hill Climbing

In Many Simple Problems It Turns Into:

Select moves by comparing consequences

of each move from the current state with goal.

Pick move that leads to state that is "closer" (more similar to ) the goal.

Atwood and Polson (1976) Water Jug Problems

Similarity of Descriptions

Select moves by comparing descriptions

of each available action from the current state with a description of the goal.

Learning to use computers, phone mail, and other complex systems.

Lewis and Polson (1990) Label following

CoLiDeS (Kitajima, Blackmon, Polson, In Press)

Atwood and Polson (1976)

Perfect Example of Problem Space Hypothesis

States

Legal configurations of water in each jug

Operators

Legal pouring operations

Search Control Knowledge

Decide to quit the problem

Quit if succeed

Quit when told by the experimenter

Decide if goal state has been produced

Select an operator to be the current operator

Prefer operators that lead to states that

are similar to the goal state

Prefer operators that lead to new states

Do not prefer operators that lead to old states

Reject operators that lead to the immediately

preceding state

Always select operators that lead to the

goal state

Select operator at random if no other

basis for preferred move

Brief Review of Polson and Jeffries

Three Stage Move Selection Process

1. Means-Ends (Similarity, Evaluation Function)

2. New moves (Use of LTM)

3. Best move or random (STM limits)

Memory

Very simplified model

Parameters

Description of random process

Simplifying assumptions

Individual differences/noise in decision processes

Constraints on parameter values

Constant across some kinds of manipulations

Vary in a “lawful” way for other kinds of

manipulations

Water Jugs

Figure showing (8,5,3) problem

Test of means-ends assumption

(8,5,3) Vs (24,21,3)

Goodness of fit

Observed and Predicted Means

and Standard Deviations

(8, 5, 3) Observed Predicted

Mean 24.90 23.69

StD 14.75 15.31

(24, 21, 3) Observed Predicted

Mean 12.03 11.84

StD 7.44 6.66

Working Backwards

Geometry

Novices Solving Physics Problems

Planning problems

Paint the ladder and ceiling green

Define new subgoals

Monkey and the Bananas

Trivial (for humans)

Huge search space

Important Problem in the Early History of AI

Knowledge

Use of Knowledge to:

* Build Effective Representations

* Control Search

Search Control

Basic Operations (Actions)

Knowledge of Individual Steps

Rule-based representation

Transfer implications

Strategic Knowledge

Strategic Knowledge

Beyond Simple Puzzle Like Problems

Text Book Problems in Geometry, Algebra, Physics

Ill-structured Problems like Design

Interaction between problem representation and

search methods

Specialized knowledge required by a given search

method

Strategic Knowledge, Constructions, Etc.

Solution Schemata

Problem Classification

Problem Representation

Expertise

................
................

In order to avoid copyright disputes, this page is only a partial summary.

Google Online Preview   Download