CS 771
Artificial Intelligence
Introduction to AI

Outline
•
•
•
•

Course overview
What is AI?
A brief history
State of the Art

Course overview
•
•
•
•
•
•
•
•
•
•
•
•
•

Intro to AI (chapter 1)
Intelligent agents (chapter 2)
Goal based agents and uninformed search(chapter 3.1-3.4)
Informed Search : A* (chapter 3.5-3.6)
Beyond classical search (chapter 4)
Adversarial search alpha-beta pruning (chapter 5)
Constraint satisfaction problem (chapter 6)
Midterm 1 (chapter 1, 2, 3,4,5,6)
Logical agents and propositional logic (chapter 7)
First-order logic (chapter 8)
Inference in first order logic (chapter 9)
Midterm 2 (chapter 7, 8, 9)
Quantifying uncertainty (chapter 13)
Probabilistic reasoning using Bayes net (chapter 14)
Probabilistic reasoning over time (chapter 15)

Where is AI in Computer Science?
Computer science : problem solving using computers
• Computer Architecture and Operating System study how to build good computers.
• Computation and Complexity Theory study what can be computed, what cannot be computed, i.e., the limits of different computing devices. • Programming Languages study how to use computers conveniently and efficiently.
• Algorithms and Data Structures study how to solve popular computation problems efficiently.
• Artificial Intelligence is relevant to any intellectual tasks, e.g., playing chess, proving mathematical theorems, writing poetry, driving a car on a crowded street, diagnosing diseases

What is AI?
A scientific and engineering discipline devoted to: • understanding principles that make intelligent behavior possible in natural or artificial systems • developing methods for the design and implementation of useful intelligent artifacts

What is AI?
• Views of AI fall into four categories
1. Thinking humanly

2. Acting humanly

3. Thinking rationally

4. Acting rationally

AI definition 1: Thinking humanly
• Need to study the brain as an information processing machine: cognitive science and neuroscience AI definition 1: Thinking humanly
• Can we build a brain?

Source: L. Zettlemoyer

AI definition 1: Thinking humanly
• Can we build a brain?

AI definition 2: Acting humanly
• Turing test : proposed and designed by Alan Turing in 1950 to provide a satisfactory operational definition of intelligence

• What capabilities would a computer need to have to pass the Turing Test?
–
–
–
–

Natural language processing
Knowledge representation
Automated reasoning
Machine learning

The Turing Test
• Turing predicted that by the year 2000, machines would be able to fool 30% of human judges for five minutes
• Loebner prize
– 2008 competition: each of 12 judges was given five minutes to conduct simultaneous, split-screen conversations with two hidden entities
(human and chatterbot). The winner, Elbot of Artificial
Solutions, managed to fool three of the judges into believing it was human [Wikipedia].

A better Turing test?

Total Turing test
• Turing’s test deliberately avoided direct physical interactions between interrogator and the computer because physical simulation of a person is unnecessary for intelligence
• A total Turing test includes a video signal so that interrogator can test the subject’s perceptual abilities
• To pass a total Turing test the computer will need
– Computer vision : to perceive object
– Robotics : to manipulate objects and move about

• These six disciplines compose most of the AI

Relevance of Turing Test
• Turing deserves a credit for designing a test that remains relevant 60+ years later
• Yet AI researchers have devoted little effort to pass the
Turing test believing that it is more important to study underlying principles of intelligence than to duplicate an exemplar • Here is an analogy
– Quest for “artificial flight” succeeded when Wright brothers and others stopped imitating birds and started using wind tunnels and learning about aerodynamics
– In fact, aerospace/aeronautical engineering practitioners do not define the goal of their field as “machines that fly so exactly like pigeons that they can fool even other pigeons”

AI definition 3: Thinking rationally
“The law of thought” approach
• Idealized or “right” way of thinking
• Logic: patterns of argument that always yield correct conclusions when supplied with correct premises
– “Socrates is a man; all men are mortal; therefore Socrates is mortal.” • Logicist approach to AI: describe problem in formal logical notation and apply general deduction procedures to solve it
• Problems with the logicist approach
– Computational complexity of finding the solution
– Describing real-world problems and knowledge in logical notation – Dealing with uncertainty
– A lot of “rational” behavior has nothing to do with logic

AI definition 4: Acting rationally
• An agent is just something that acts
• A rational agent is one that acts so as to achieve the best outcome or acts to optimally achieve its goals
 Goals are application-dependent and are expressed in terms of the utility of outcomes
 Being rational means maximizing your utility or maximizing expected utility under uncertainty

• This definition of rationality only concerns the decisions/actions that are made, not the cognitive process behind them

Justification for acting rationally
• The “law of thought process” approach to AI emphasize on correct inference • Making correct inference is sometimes part of being a rational agent because – One way to act rationally is to reason logically to the conclusion that a given action will achieve one’s goals

• On the other hand correct inference is not all of rationality
– In some situations there may not be any provably correct thing to do yet something still must be done

• The rational agent approach has some advantages over other approaches
– It is more general than law of thought process
– It is more amenable to scientific development than are approaches based on human behavior or human thought
– The standard of rationality is mathematically well defined, completely general and can be used to generate agent designs that provably achieve it
Therefore, in this course we will concentrate on rational agent

History of AI

Image source

What are some successes of AI today?

IBM Watson

•
•
•
•

http://www-03.ibm.com/innovation/us/watson/
NY Times article
Trivia demo
IBM Watson wins on Jeopardy (February 2011)

Self-driving cars

•
•

Google’s self-driving car passes 300,000 miles (Forbes, 8/15/2012)
Nissan pledges affordable self-driving car models by 2020
(CNET, 8/27/2013)

Natural Language
• Speech technologies
• Google voice search
• Apple Siri

•

Machine translation
• translate.google.com
• Comparison of several translation systems

Vision
• OCR, handwriting recognition
• Face detection/recognition: many consumer cameras, Apple iPhoto • Visual search: Google Goggles, search by image
• Vehicle safety systems: Mobileye

Mathematics
• In 1996, a computer program written by researchers at
Argonne National Laboratory proved a mathematical conjecture unsolved for decades
• NY Times story: “[The proof] would have been called creative if a human had thought of it”
• Mathematical software:

Games
• IBM’s Deep Blue defeated the reigning world chess champion Garry Kasparov in 1997
• 1996: Kasparov Beats Deep Blue
“I could feel – I could smell – a new kind of intelligence across the table.”
• 1997: Deep Blue Beats Kasparov
“Deep Blue hasn't proven anything.”

• In 2007, checkers was “solved” (though checkers programs had been beating the best human players for at least a decade before then)

Logistics, scheduling, planning
• During the 1991 Gulf War, US forces deployed an AI logistics planning and scheduling program that involved up to 50,000 vehicles, cargo, and people

• NASA’s Remote Agent software operated the Deep Space 1 spacecraft during two experiments in May 1999
• In 2004, NASA introduced the MAPGEN system to plan the daily operations for the Mars Exploration Rovers

Robotics
• Mars rovers
• Autonomous vehicles
– DARPA Grand Challenge
– Self-driving cars

• Autonomous helicopters
• Robot soccer
– RoboCup

• Personal robotics
– Humanoid robots
– Robotic pets
– Personal assistants?

Towel-folding robot

YouTube Video
•
•

J. Maitin-Shepard, M. Cusumano-Towner, J. Lei and P. Abbeel, Cloth Grasp Point Detection based on Multiple-View Geometric Cues with Application to Robotic Towel Folding, ICRA 2010
More clothes folding

Origins of AI: Early excitement
• 1940s First model of a neuron (W. S. McCulloch & W. Pitts)
– Hebbian learning rule
– Cybernetics

• 1950s
–
–
–
–

Turing Test

Perceptrons (F. Rosenblatt)
Computer chess and checkers (C. Shannon, A. Samuel)
Machine translation (Georgetown-IBM experiment)
Theorem provers (A. Newell and H. Simon, H. Gelernter and N. Rochester)

1956

Dartmouth meeting: “Artificial Intelligence” adopted

Herbert Simon, 1957
•“It is not my aim to surprise or shock you – but … there are now in the world machines that think, that learn and that create. Moreover, their ability to do these things is going to increase rapidly until – in a visible future – the range of problems they can handle will be coextensive with the range to which human mind has been applied. More precisely: within 10 years a computer would be chess champion, and an important new mathematical theorem would be proved by a computer.”

• Simon’s prediction came true – but forty years later instead of ten

Harder than originally thought
• 1966: Eliza chatbot (Weizenbaum)
• “ … mother …” → “Tell me more about your family”
• “I wanted to adopt a puppy, but it’s too young to be separated from its mother.”

• 1954: Georgetown-IBM experiment
• Completely automatic translation of more than sixty Russian sentences into English
• Only six grammar rules, 250 vocabulary words, restricted to organic chemistry • Promised that machine translation would be solved in three to five years (press release)
• Automatic Language Processing Advisory Committee (ALPAC) report
(1966): machine translation has failed
• “The spirit is willing but the flesh is weak.” →
“The vodka is strong but the meat is rotten.”

Blocks world (1960s – 1970s)

Larry Roberts, MIT, 1963

???

History of AI: Taste of failure
1940s

1950s

First model of a neuron (W. S. McCulloch & W. Pitts)
Hebbian learning rule
Cybernetics
Turing Test
Perceptrons (F. Rosenblatt)
Computer chess and checkers (C. Shannon, A. Samuel)
Machine translation (Georgetown-IBM experiment)
Theorem provers (A. Newell and H. Simon, H. Gelernter and N.

Rochester)
Late 1960s
Early 1970s
Late 1970s

Machine translation deemed a failure
Neural nets deprecated (M. Minsky and S. Papert, 1969)*
Intractability is recognized as a fundamental problem
The first “AI Winter”

History of AI to the present day
1980s
Late 1980sEarly 1990s
Mid-1980s
Late 1980s
1990s-Present

Expert systems boom
Expert system bust; the second “AI winter”
Neural networks and back-propagation
Probabilistic reasoning on the ascent
Machine learning everywhere
Big Data
Deep Learning

NY Times article

What accounts for recent successes in AI?
• Faster computers
• The IBM 704 vacuum tube machine that played chess in 1958 could do about 50,000 calculations per second
• Deep Blue could do 50 billion calculations per second
– a million times faster!

• Dominance of statistical approaches, machine learning • Big data
• Crowdsourcing

Historical themes
• Moravec’s paradox
• “It is comparatively easy to make computers exhibit adult level performance on intelligence tests or playing checkers, and difficult or impossible to give them the skills of a one-year-old when it comes to perception and mobility”
[Hans Moravec, 1988]

• Why is this?
• Early AI researchers concentrated on the tasks that they themselves found the most challenging, abilities of animals and two-year-olds were overlooked
• We are least conscious of what our brain does best
• Sensorimotor skills took millions of years to evolve, whereas abstract thinking is a relatively recent development

Historical themes
• Silver bulletism (Levesque, 2013):
• “The tendency to believe in a silver bullet for AI, coupled with the belief that previous beliefs about silver bullets were hopelessly naïve”

• Conceptual dichotomies (Newell, 1983):
•
•
•
•
•

Symbolic vs. continuous
High-level vs. low-level modeling of mental processes
Serial vs. parallel
Problem solving vs. recognition
Performance vs. learning

• Boom and bust cycles
• Periods of (unjustified) optimism followed by periods of disillusionment and reduced funding

• Image problems
• AI effect: As soon as a machine gets good at performing some task, the task is no longer considered to require much intelligence

Philosophy of this class
• Our goal is to use machines to solve hard problems that traditionally would have been thought to require human intelligence • We will try to follow a sound scientific/engineering methodology •
•
•
•
•

Consider relatively limited application domains
Use well-defined input/output specifications
Define operational criteria amenable to objective validation
Zero in on essential problem features
Focus on principles and basic building blocks