Problem Solving



Where Are We Going

Finish Up Problem Solving Lectures

Generate and Test

Problem Spaces

Invention of the Airplane

Preview of Next Week

Rule Based Models of Mind

Examples

Symbolic verses Subsymbolic Processes

Connectionism (Mike on Thursday)

Computational Requirements for a Rule Following Engine

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

Generate And Test

Problem solvers adhering to the generate-and-test paradigm use two basic modules.

> One module, the generator, enumerates possible solutions.

> The second, the tester, evaluates each proposed solutions, either accepting or rejecting that solution.

All Depends on Properties of Generator

A powerful intelligent Generator will only produce a few "good" solutions including the correct one.

Evolution is an example of Generate-and-Test

All controversies about Darwin and the application of evolutionary ideas focus on the claim that the generator is NOT intelligent.

Blind trial and error

Scientific Discovery

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

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

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

The Invention of the Airplane

Gary Bradshaw

How Did Two Bicycle Mechanics From Dayton, OH Succeed In Inventing the Airplane?

Many well financed research programs in Europe and US

Early Attempts To Build Heavier Than Air Aircraft

Ornithopters

The Correct Solution, Sir George Cayley, 1809

Lift from fixed wings

Thrust from power plant and propeller

Tail to provide stability

Bradshaw’s Figure 1

[pic]



How Did the Wright Bother Succeed?

Very Careful Study and Complete Mastery of Previous Research

Problem Reduction Verses Generate and Test

Generate and Test

A new design was identified, the craft was constructed and then taken out to the field for testing. The results of the testing were used in making a new design, completing the loop. (Bradshaw website)

Hill Climbing

Time and distance in flight.

global performance metrics that reflect the properties of the craft as a whole

insensitive to the particular strengths and weaknesses of any particular design

Trail and Error Search Though a Huge Design Space Using Ineffective Heuristics

Problem Reduction

Lateral Stability

Wing warping

Design of

Wings that Generate Enough Lift

Propellers that Generate Enough Trust

Use of Wind Tunnel

Wonderful Mechanics

Light Very Powerful Gasoline Engine

Searching Smaller Spaces

Can Use Feedback to Guide Search

Wright Bother’s First Flight

[pic]

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

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)

Building a Rule Following Engine Out of Connectionist Parts

Can Solve Hard Problems in Philosophy of Mind

Build Computational Modesl of Intelligent Behavior

With Symbolic Systems That Can

Create, Store, and Retrieve Symbols

Learn, Store, and Retrieve Symbol Manipulating Rules

Problems With Symbolic Systems

Brittle

Missing Fundamental Properties of Intelligent Behavior

How Do We Build a Symbolic Computational System Out of Neurons?

Connectionism

Distributed Representations

Massively Interconnect Simple Elements

Parallel Computation

Connectionist Parts:

Auto-Associators

Content Addressable Memory

Pattern Completion

Reconstructive

Deal With

Noisy Inputs

Hardware Failures

“Graceful Degradation”

Constraint Satisfaction

Generalization

Learning From Examples

Hidden Layer Networks

All of above

More complex concepts

Is Connectoplasm A Complete Model of Mind?

Disagreements

Pinker Says NO!

Concept of an individual

Compositionality

The baby ate the slug. Verses The slug ate the baby

Roles (agent, object, recipient,….)

Discrete combinatorial systems

Language

Variable Binding

Powerful, General Rules

Transfer of Skills

Recursion

Rule Based Classification

Verses Fuzzy Categories

Rule-Based Models of Mind

Production System

Anderson: Act-R

Newell; SOAR

Production Systems

Pinker’s Example Starting on Page 71 Is Not Just Any Old Turing Machine.

Production System

RULES

- Describe Knowledge Required to Perform Task

- Rules, Productions

IF condition THEN action (Condition- Action Pair)

IF (Goal and a specific situation)

THEN (do actions)

WORKING MEMORY

- Symbolic Data, Working Memory Elements

• Current Goals

• Symbolic Representation of External World

The Human Information Processing System as a Production System

Newell and Simon (1972, pp. 804-5)

1. Capable of expressing arbitrary calculations.

2. Homogeneous representation of control information.

3. Each rule of an independent fragment of behavior.

Implications for learning and skill acquisition.

4. Strong stimulus-response flavor; historical

implications.

5. Meaningful elements of a complete skill.

6. Working Memory equivalent to Short Term Memory.

7. Rules possible general model for long term memory.

8. Nice balance between goal-direct and stimulus-bound control.

9. Parallel recognition process with serial action generation process

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

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

Google Online Preview   Download