Transcript Artificial Intelligence Overview

The Future of Artificial
Intelligence
John Paxton
Montana State University
August 14, 2003
Bannack
What makes AI difficult?
• Different problems have inherently
different complexities to solve.
The Sorting Problem
• Input: 2 4 6 7 5 3 1
• Output: 1 2 3 4 5 6 7
Selection Sort
•
•
•
•
•
•
•
Step 1: 2 4 6 7 5 3 1
Step 2: 2 4 6 1 5 3 7
Step 3: 2 4 3 1 5 6 7
Step 4: 2 4 3 1 5 6 7
Step 5: 2 1 3 4 5 6 7
Step 6: 2 1 3 4 5 6 7
Step 7: 1 2 3 4 5 6 7
Selection Sort
• If there are n items to sort, selection sort
takes O(n2) time
• What does this mean? If we double the
size of the input, we can expect the
algorithm to take four times as long.
Quicksort
• O(n log2 n)
2467531
1
46753
3
675
5
7
Quicksort
n
n log2 n
n2
10
33.22
100
100
66.44
10000
1000
99.66
1,000,000
10000
132.88
100,000,000
Sorting
• It can be proven that sorting n numbers
based on comparisons has a best case of
O(n log n).
• Thus, the inherent complexity of sorting is
O(n log n), even though worse algorithms
such as selection sort exist.
The Class P
• P = Polynomial
• Any problem whose inherent complexity is
O(np) where p is a constant is in the class
P.
• Problems that are in P typically are
practical to solve on computers.
Travelling Salesperson Problem
• Starting in City A, what is the shortest
circuit that visits cities B, C, and D?
• A–B–C–D–A
• A–B–D–C–A
• A–C–B–D–A
• A–C–D–B–A
• A–D–B–C–A
• A–D–C–B-A
TSP
• In the preceding problem, there were 4
cities and 3! possible solutions
• In general, if there are n cities, one must
consider (n-1)! possibilities.
• (n-1)! is not O(np) for any fixed p. (n-1)! is
in the EXP class.
• Each problem in the EXP class is O(pn) for
some fixed p.
Comparison
n
n2
(n-1)!
5
25
24
10
100
362,880
15
225
8.7E10
20
400
1.2E17
The Class EXP
• As you can see from the preceding table,
problems that are in the class EXP do not
have practical solutions on computers
Relevance to AI
• Unfortunately, many interesting problems
in AI are in the class EXP.
• For example, the TSP problem.
Satisficing
• What can be done?
• Instead of settling for the optimal answer,
look for a “pretty good” solution instead.
This technique is also known as
satisficing.
Satisficing Example
Heuristics
• A “heuristic” is a rule-of-thumb that works
in practice, but has no guarantee of being
optimal.
Water Jug Problem
• Place 6 liters of water in the 8 gallon jug in
as few steps as possible
8
3
Water Jug Problem
• Place 8 liters of water in the 10 gallon jug
in as few steps as possible
10
4
Water Jug Problem
• Place 10 liters of water in the 15 gallon jug
in as few steps as possible
15
5
Past AI Predictions
• Game Playing. Researchers thought that
AI chess playing programs would beat the
best humans by 1970.
• Machine Translation.
– The spirit is willing, but the flesh is weak.
– The whisky is strong, but the meat is rotten.
Objections to AI
•
•
•
•
•
•
•
•
•
Theology
Heads-in-the-Sand
Mathematical
Self Awareness
Capability X is lacking (e.g. enjoy ice cream)
Lady Lovelace’s objection
Continuity of nervous system
Informality of behavior (no rules)
ESP
The Future
• Consumer Robots
The Future
• Gastrobots
(University of South
Florida)
• Sustain themselves
by eating naturally
occurring foods
The Future
• COG, a robot at MIT
•
•
•
•
Track eye movement
Recognize faces
Grab objects
Hear a rhythm, play it
back on drums
The Future
• Art – Raymond
Kurzweil’s
screensaver program,
Aaron
• Poetry
• Music
The Future
• Natural Language
• Charles Schwab incorporates iPhrase at
its web site to allow users to use natural
language to ask questions. For example,
“Which of these stocks has the highest
revenues?”
The Future
• Products that do one thing well.
• For example, Continental Divide Robotics
has developed a system based on GPS
that can locate any person or any object
anywhere in the world and notify a user if it
is “out of bounds”. This could help a
parent monitor a child, for example.
The Future
• Companionship
• At Microsoft, a product is under
development that learns about you. Who
is important to you? Are you busy? The
product can then monitor incoming e-mails
and phone calls.
The Future
• Virtual Reality
• Haptek, People Putty
• Create your own 3-D
interactive characters
The Future
• Computers will get faster
• Software will get better
• AI will creep closer to human capabilities
(search, learning, knowledge
representation)
The Future
• There are lots of potential
benefits!
• There are certainly some
potential drawbacks!
• Most AI researchers
believe humans will stay
in control
Questions?