Transcript AI-01b- History

An introduction to
Artificial Intelligence
CE-40417
Lecture 1b: History of A.I.
It started by science fiction…
•
In 1921, the Czech author Karel Capek
produced the play R.U.R. (Rossum's
Universal Robots).
"CHEAP LABOR. ROSSUM'S ROBOTS."
"ROBOTS FOR THE TROPICS. 150 DOLLARS EACH."
"EVERYONE SHOULD BUY HIS OWN ROBOT."
"DO YOU WANT TO CHEAPEN YOUR OUTPUT?
ORDER ROSSUM'S ROBOTS"
The Gestation of A.I.
1943-1956
•
Modeling of Neurons
– Warren Mc Culloch & Walter Pitts, 1943
•
Learning by Neurons
– Donald Hebb, 1949
•
Implementation of Neurons
– Marvin Minsky & Dean Edmonds, 1951
The Gestation of A.I.
1943-1956
•
First Chess Player Program
– Claude Shannon & Alan Turing, 1950s
•
Logic Theorist
– Newell & Simon from CMU.
The Gestation of A.I.
1943-1956
•
Dartmouth Conf.: Birth place of AI, 1956
Marvin Minsky
Nathaniel Rochester
John McCarthy
Cloud E. Shannon
Early Enthusiasm,
Great Expectations
1952-1969
•
Successful Years, with limited resources.
•
General Problem Solver – CMU
– The first program, emulating human thinking.
•
Geometry Theorem Prover – IBM
– Gelenter, 1959
Early Enthusiasm,
Great Expectations
1952-1969
•
Checkers Player Machines
– Arthur Samuel, 1952– Presenting Learning…
– A TV Show!
•
Invention(!) of LISP and Time Sharing
– McCarthy, MIT, 1958
Early Enthusiasm,
Great Expectations
1952-1969
•
Advice Taker
– McCarthy, MIT, 1958
– General Knowledge, Not Implemented
•
Resolution Algorithm
– Robinson, ~1963
•
Planning Systems
– Green, 1969, Stanford
Early Enthusiasm,
Great Expectations
1952-1969
•
Micro Worlds
– Minskey, MIT, 1963
•
•
Blocks World
ANALOGY
– Tom Evans, 1968, MIT
•
Semantic Information Retrieval (SIR)
– Bertram Raphael, 1968
– Inputs in English
Early Enthusiasm,
Great Expectations
1952-1969
•
STUDENT
– Daniel Bobrow, 1967
•
If the number of customers Tom gets are twice the
square of 20 percent of the number of
advertisements he runs and the number of
advertisements he runs are 45, what is the number
of customers Tom gets.
Early Enthusiasm,
Great Expectations
1952-1969
•
Shakey , Stanford, 1966-1972
Shakey had a TV camera, a triangulating
range finder, and bump sensors, and was
connected to DEC PDP-10 and PDP-15
computers via radio and video links. Shakey
used programs for perception, world-modeling,
and acting. Low-level action routines took care
of simple moving, turning, and route planning.
Intermediate level actions strung the low level
ones together in ways that robustly
accomplished more complex tasks. The
highest level programs could make and
execute plans to achieve goals given it by a
user. The system also generalized and saved
these plans for possible future use.
Early Enthusiasm,
Great Expectations
1952-1969
•
Flourishing of Neural Networks
– Learning Large Amounts of Data
•
•
Adalines, 1962, Widrow
Perceptrons, 1962
Science Fiction…
•
Isaac Asimov
–
–
•
195043 Novels & 250 Short Stories
The three laws of robotics
•
•
•
A robot may not injure a human being, or, through inaction,
allow a human being to come to harm.
A robot must obey the orders given it by human beings
except where such orders would conflict with the First Law.
A robot must protect its own existence as long as such
protection does not conflict with the First or Second Law.
Science Fiction…
•
Sir Arthur C. Clark
– 2001, A Space Odyssey, 1968
Science
Fiction…
•
Star Trek
– 726 episodes from 1966-2005.
– 10 Movies
Data: "And for a time, I was tempted by her offer."
Picard: "How long a time?"
Data: "0.68 seconds, sir. For an android, that is nearly an
eternity."
– While lamenting the Borg Queen and her destruction in
First Contact.
A dose of reality
1966-1974
•
Herbert Simon, 1957
– The power of A.I. will increase so rapidly that
in a visible future, the range of problems they
can handle will be coextensive to that of
human.
– With in 10 years, the computer will be chess
champions and mathematic theorem provers.
A dose of reality
1966-1974
•
Automatic Translation after Sputnik lunch, 1957.
–
–
Famous Failures:
•
The spirit is willing, but the flesh is weak
 the vodka is good but the meat is rotten.
•
Out of mind, out of sight
 Invisible idiot!
1966, “there is no M.T. for general scientific text and
there would be no in immediate prospect.”  All
canceled.
A dose of reality
1966-1974
•
AI based on simple facts and informed
search. (Micro Words)
– Fine for a few objects and facts.
– Combinatorial Explosion
– Logical feasibility will not necessarily result in
practical possibility.
A dose of reality
1966-1974
•
Lighthill report to British Government,
1973
– Cancellation of all AI research in G.B. except
to universities. – Combinatorial Explosion
•
Minskey and Papert, 1969:
– Neural Networks can’t learn but trivials.
Knowledge Based Systems
1969-1979
•
DENDRAL
– Buchanan et al, 1969, Stanford
•
To have general knowledge about a field and
required inference rules.
– Extracting Analytic Chemists’ Expertise
– Inference based on given facts.
Knowledge Based Systems
1969-1979
•
MYCIN
–
–
–
•
Feigenbaum, et al, 1971
Diagnosis of blood infections with 450 rules.
Better than junior doctor and comparable with
experts.
PROSPECTOR
–
Duda et al, 1979
•
Recommendation of exploratory drilling positions at a
geological site.
Knowledge Based Systems
1969-1979
•
Schank, Yale:
– There is no such thing as language syntax.
– Its meaning that matters
•
LUNAR, Williams & Woods, 1973
– A natural language interface to Apollo moon
mission database.
AI Becomes industry
1980-1988
•
R1 Expert System at DEC, 1982
–
–
•
The Fifth Generation Project
–
–
•
Configuration of computer systems.
Saving $40 million per year.
10 year to build a Prolog processing machine by
Japanese.
Counter attacks in U.S. and G.B.
From a few million in 1980 to $2 billion in 1988.
The return of neural networks
1986•
Analysis of storage capacity
– Hopfield, 1982
•
Neural Models of Memory
– Different psychologists, 1980s
•
Reinvention of BACK-PROPAGATION
– First in 1969, then in 1986.
•
Connectionism School
Recent Events
1987•
Neats defeated Scruffies
– Continual of previous theories vs. proposing
brand new ones.
– Working on real domains vs. toy problems.
Recent Events
1987•
Speech Recognition
– Several ad hoc methods in 1970s.
– Hidden Markov Models
•
•
Based on Years of Mathematics
Training with real data
– SR and OCR at industry.
Recent Events
1987•
Planning
– Extending previous attempts
•
From early laying with Micorwords
– To
•
•
•
•
Factory workspace planning
Space Mission Planning
Scheduling
…
Recent Events
1987•
Belief Networks,1985
– Dealing with uncertainties in reasoning
•
Similar Advances in
– Robotics, Vision, Learning, Knowledge
Representation, Distributed Intelligence
State of the Art
•
•
•
•
•
•
•
Chess Grand Masters
Speech Understanding Interfaces
Mission Analyzers
Auto-Drivers
Expert Systems
Traffic Control
…