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.
To fulfill the demand for quickly locating and searching documents.
It is intelligent file search solution for home and business.
Related searches
- problem solving methods
- types of problem solving methods
- real life problem solving worksheets
- 5 why problem solving form
- 20 problem solving techniques
- list of problem solving techniques
- problem solving methods and techniques
- systematic problem solving examples
- list of problem solving tools
- problem solving examples in life
- examples of problem solving situations
- free problem solving skills worksheets