Classical Period:

General Problem Solving

(e.g., you are here, go to the bookstore

how does one graduate?)

One needs a formal description of problems:

suggested characteristics:

• the notion of an explicit goal (termination) - implicit criteria for success (what is a success)
• initial situation (start state)
• ability to perform - transform a situation (operations, rules)

Problem solving is essentially search

Characteristics of Search

• Control mechanism
• State-space
  (an apparent situation and possible options can generate over and over this set of states)
• Representation
  (here, our problem is not to recognize that a problem exists, rather we have a known problem : How can it be represented)

Aside: levels of problem solving: recognize ... solve

modularity and higher levels of understanding (one step at a time)

Water Jug Problem

You are given two jugs, a 4-gal. one and a 3-gal. one. Neither has any measuring markers on it. There is a pump that can be used to fill the jugs with water. How can you get exactly 2 gallons of water into the 4-gal. jug?

Solution: Define state space, give initial & final state(s), ops?

A representation:
The state space for the problem can be a set of ordered pairs (x,y) where x is the # of gallons in the 4-gal. jug, y is the 3-gal.

domain for x is 0,1,2,3,4 : domain for y is 0,1,2,3

Thus (4,2) represents what...

The start state is ?

The Goal state is (2,n), success does not depend on the 3-gal. jug

Control (operators):
pour either out, fill either one, pour one into another, etc.

Generate State Space, then use a control technique to
test all possible ops.

weak search (depth/breath first) led to need for heuristics

number of nodes can easily grow exponentially

(similarly problems with using theorem proving (Godel))

(note: neat/scruffy ("disillusionment", pg. 31))

Heuristics...allows for use of evaluation functions...

Hill Climbing:
Generate all (breath), use a heuristic function (evaluation functions) to pick best, then forget others at same level as go down (local min/max)

Additional Heuristics allow jumps in search or direct path

(e.g., Best-first, Branch-and-Bound, A*)

Heuristics improve efficiency but possibly sacrifice completeness

also, problems with how get the function (usually a formula)

Herbert Simon: Nobel Prize in Economics...

People are satisficers not optimizers

Important discoveries in this period: Jackson: page 23

Romantic Period:

Understanding (Schank - making sense, cognitive understanding, empathy)

Newell and Simon claimed GPS was like people (goal driven)

Rule-based systems - people answer and ask "if ... then ..."

protocol analysis

surface phenomonalism

Important contributions - knowledge representations

• rules (ubiquitous)
• semantic nets (e.g. atn's for grammars)
• logic (non-monotonic, etc.)
• frames
• combinations

• how to represent knowledge and reason
  (CYC, model-based reasoning, generic tasks)
• how to perceive equivalences or analogies
  (case-based reasoning)
• learning
  (machine learning: neural nets, genetic algorithms, etc)

Modern Period

task specific
domain specific

Jackson, pg. 28, 30

How to organize knowledge so that it can be accessed and used

Knowledge Representation and Expert Systems

What can expert systems bring to bear on these exponentially hard problems? Knowledge

Problem: this knowledge is hard to formalize - more "experience" than theory

Procedural vs Declarative Knowledge

interesting comparison to task and domain

Jackson, Second Edition (pg. 72): "Declarative representations of knowledge are rather more flexible than procedural ones, in that they can be put to a number of different uses, while procedural representations are usually crafted for a particular purpose.." consider rules

Heuristics allow Expert Systems to use "compiled" knowledge rather than "deep" knowledge (first principles).

Problem here - experts usually can go back and forth...

Use of heuristics also questions

• soundness (achieved by chain of reliable deductions)
• completeness (system misses info)