Artificial Intelligencein the Open World
Eric Horvitz
Presidential Address
July 2008

Rich Intellectual History of AI
18th- Julien Offray de La Mettrie
L’homme machine (1747)
19th- Charles Babbage
Difference Machine, Analytical Engine
20th- Turing, von Neumann, Weiner, et al.
- Newell, Simon, Rochester, McCarthy, et al.

Computation as Basis ofThought & Intelligent Behavior
Theories of computability
 General purpose computerDartmouth MeetingMachine methods of forming abstractions fromsensory and other data

Carrying out activities which may best be
described as self-improvement

Manipulating words according to rules ofreasoning and rules of conjecture

Developing a theory of the complexity for various
aspects of intelligence

Paradigms of Computational Intelligence“AI”

Decision sciences / OR
Optimization
Logic
Computability
General purpose computerParadigms of Computational Intelligence
Satisficing“AI”

High-level symbols
Logic

Decision sciences / OR
Optimization
Logic
Computability
General purpose computer

Grappling with Incompletenessin an Open World

Grappling with Incompletenessin an Open World

Grappling with Incompletenessin an Open World
Bounded rationality (Simon, et al).
Hopelessly incomplete knowledge of …
 Preferences State of world Outcomes of action

Enduring Perspective: Intelligenceamidst Inescapable Incompleteness
Limited agents immersed in complex universes
 Limited representations
 Limited time and memory

Stepping into the Open WorldKey technical challenges
 AI moving into the world
 AI research communityStepping into the Open WorldKey technical challenges
 AI moving into the world
 AI research communityStepping into the Open World

Stepping into the Open World

Relevance & Attention in Open Worlds
 Frame problem

How to limit the scope of the reasoning required toderive the consequences of an action?
 Qualification problem
 All preconditions required for actions to haveintended effects
 Ramification problem
 All effects of action

Nonmonotonic logics, representation of fluentsParadigms of Computational Intelligence
Satisficing“AI”

High-level symbols
Logic
Uncertainty
UAI

Decision sciences / OR

Optimization
Logic
Computability
General purpose computer

High-level symbols
LogicParadigms of Computational Intelligence“AI”

Satisficing

Optimization

High-level symbols
LogicHigh-level symbols
Logic

UAI
Decision sciences / OR

Optimization
Logic
Computability

General purpose computer

Probability
Utility
MEUParadigms of Computational Intelligence“AI”

Satisficing

Optimization

High-level symbols
LogicHigh-level symbols
Logic

UAI
Decision sciences / OR

Optimization
Logic
Computability

General purpose computer

Probability
Utility
MEUParadigms of Computational Intelligence“AI”

Satisficing

Optimization

High-level symbols
LogicHigh-level symbols
Logic

UAI
Decision sciences / OR

Optimization
Logic
Computability

General purpose computer

Probability
Utility
MEU

Uncertainty as Organizing Principle
 Incompleteness is inescapable Uncertainty is ubiquitous State of world Outcome of action
 Problem solving itself

Push unknown & unrepresented details
into probabilities and propagate

Uncertainty as Organizing Principle

Machinery for handling
uncertainty & resource limitations
foundational in intelligenceExpressive Representationsof Uncertainty
 Graphical models for representing beliefs
 d-separation
 Sound and complete algorithm for identifying all

independencies entailed by the graph.

Fuel

Battery

p(F)

p(B)
Gauge

p(G|F,B)
TurnOverp(T|B)Start

p(S|F,T)Representing Problems of Action
Maximum expected utility (MEU) Influence diagrams (Howard & Matheson, 1975)


World
State H

UtilityRepresenting Problems of Action
Maximum expected utility (MEU) Influence diagrams (Howard & Matheson, 1975)


UtilityWorld
State H
E1

E2

E3

En

Representing Problems of Action
Maximum expected utility (MEU) Influence diagrams (Howard & Matheson, 1975)
Action A

UtilityWorld
State H
E1

E2

E3

En

Representing Problems of Action
Maximum expected utility (MEU) Influence diagrams (Howard & Matheson, 1975)
Action A

UtilityWorld
State H
E1

E2

E3

En

Representing Problems of Action
Maximum expected utility (MEU) Influence diagrams (Howard & Matheson, 1975)
Action A

UtilityWorld
State H
E1

E2

E3

En

Reasoning about Beliefs andActions over Time

A3,t3

A1,t1

State ofWorld H, to

E1, toE2, toEn, toE1, t’

State ofWorld H, t4

State ofWorld H, t2

E2, t’

En, t’

E1, t’’

E2, t’’

En, t’’

Reasoning about Beliefs andActions over Time
Plan {(A1,t1)...(An,tn)}

A3,t3

A1,t1

State ofWorld H, to

E1, toE2, toEn, toE1, t’

Utility

State ofWorld H, t4

State ofWorld H, t2

E2, t’

En, t’

E1, t’’

E2, t’’

En, t’’

Acceleration of Machine Learning:
Discovering Structure and Concepts

e.g., Structure search
Measure of model likelihood*

Identification of Hidden Variables
“Unknown” variables discovered?
?

Beauty …and the Bottleneck
Insights arising in tight situationsBounded rationality  Bounded optimality
Economics of computation
Flexible computational strategies
Principles of reflection

Economics of Flexible Computation
Utility ofaction• Immediate value of resulttDeadline!

Economics of Flexible Computation
Utility ofaction• Immediate value of resulttEconomics of Flexible Computation
Utility ofaction• Immediate value of result• Net value of resultt• Cost of delay

Economics of Flexible Computation
Utility ofaction• Immediate value of result• Net value of resultt• Cost of delay

Flexible Procedures
Utility ofaction• Immediate value of result• Net value of result
Should I think more about this?

?

tFlexible Procedures
Utility ofaction• Immediate value of result• Net value of result
Should I think more about this?

?

tWhat’s the next best computational action?

Expected value of computation

Foundations of Reflection
Expected value of computation

Foundations of Reflection
Expected value of computation

Foundations of Reflection
Expected value of computation

Partition of resources

Foundations of Reflection
Expected value of computation

metalevel

object level

Real-World:
Uncertain performance & Cost of Delay
Tractable EVC in time-critical medical decisions
1.0

Treat patient for respiratory failure now!
0.8

Probability

EVC

EV Metareasoning >EV Default

0.6

0.4

Upper bound
0.2

Lower bound
0.0
0

10

20

Computation Time

30

40

Learning about Instances & Reasoning
from a Stream of Problems
e.g., Machine learning & SAT solvers
 Grappling with long tails
 Dynamic restart policy in SAT solvers (Kautz, et al)

(a

b

c)

(

b

d)

(b

c

e)

...

Open-World AI

Toward Situated, Flexible, Long-Lived
Open-World Systems
Flexible adaptation to varying & dynamic
situations– Streams of observations and challenges
over different time frames–Broad variation, uncertainty in goals, time
criticality, available actions– Learning about new objects, predicates,
goals, preferences…and about perception & reasoning

TimeFlexible adaptation to varying tasks,
situations, environments

Situation A

A,E-->MEU

Situation B

Situation C

Flexible adaptation to varying tasks,
situations, environments

Situation A

Situation B

A’,E’-->MEU

Situation C

Flexible adaptation to varying tasks,
situations, environments

Situation A

Situation B

Situation C

A’’,E’’-->MEU

Attentional Challenge: Coordinate
Sensing, Reflection, Action, LearningStanding challenge…

Value of information
Value of computation

Value of learning

Challenge: Lifelong LearningTradeoff local costs of exploration,labeling for long-term gains

Decisions about information collection

to?

Information
value

Recognized
eventsPerceptual
Exploration

Challenge: Handle Streams of Problems
Policies for using all time…incl. idle time How to best use available time to solve

future problems?
 How to trade current problem solving

for solving future problems?

Stream of Problem InstancesTimeStream of Problem InstancesTimeTrading Off Present for FutureTimeTrading Off Present for FutureTimeChallenge:
Frame – and Framing Problem
What goals, preferences, …objects,
predicates, relationships should be in adecision model?

How can tractable, relevant models beconstructed automatically?

How can the system learn about theframe?

Automated Framing & Executionof Local Decision Problems

Automated Framing & Executionof Local Decision Problems

Automated Framing & Executionof Decision Problems

Propositional
Probabilistic
RepresentationsFirst-Order Logic
Representations

Propositional
First-Order Logic
Probabilistic
Representations
Representations

Knowledge-Based Model Construction
Context-sensitive propositional models
from first-order knowledge baseFirst-Order Knowledge Base{(DX $x $z) |p (ABN $x $y) }{(ABN $x BP) |p (BP $x $z) ^ (AGE $x)}{(ABN $x BP) |p (BP $x $z) ^ (AGE $x )}……

Deductive
Inference

Situation!

Propositional Model(BP Tom 144/90)(ABN Tom BP)(DX Tom HPN )Breese, Goldman, Wellman, et al.

Probabilistic
Inference

Eventprobabilities
Best actions

Learning & First-Order
Probabilistic Representations
Generate objects, relations, models
Plan recognition networks

Probabilistic relational models

Markov logic networks



BLOG: Probabilistic models withunknown objects

Reasoning about …and Expecting
the Unknown
Probabilistic Models with Unknown Objects

Brian Milch, et al.

Reasoning about …and Expecting
the Unknown
Probabilistic Models with Unknown Objects

Brian Milch, et al.

Reasoning about …and Expecting
the Unknown

Krumm, H., et al.

Reasoning about …and Expecting
the Unknown

Krumm, H., et al.

Extending Proficiency in a Messy World

Assume unmodeled objects, relations, noiseContinue to extend models with experiences(video)Pasula, Zettlemoyer, KaelblingExtending Proficiency in an Open World

Assume unmodeled objects, relations, noiseContinue to extend models with experiences

Pasula, Zettlemoyer, KaelblingExtending Perceptual Proficiency with
Shape Prototypes and Deformations

G. Elidan, G. Heitz, and D. Koller

Extending Perceptual Proficiency with
Shape Prototypes and Deformations
MAN

“man
walkingdog”

DOG

G. Elidan, G. Heitz, and D. Koller

Proficiency via Transfer in Open Worlds
Transferring prior knowledge to new situations

Klingbeil, Saxena, Ng, et al.

Proficiency via Transfer in Open Worlds
Transferring prior knowledge to new situations(video)Klingbeil, Saxena, Ng, et al.

Prospering in the Open WorldTo know that you do not know is the best.
Lao TzuProspering in the Open WorldTo know that you do not know is the best.
Lao TzuModeling model competencies, limitations,extensions
Context-sensitive failures & successes
Models of anomaly & surprise
Value of prototypes, analogy, transfer
Learning objects, predicates, preferences, goals
in noisy environments

Value of Open-World Challenges


AAAI / CVPR Semantic Robot Vision Challenge Robots must perform a scavenger hunt in apreviously-unknown indoor environment.

Web access-e.g.,- scientific calculator- Ritter Sport Marzipan- DVD “Shrek”- DVD “Gladiator”- CD “Hey Eugene”- electric iron.
.
.

Value of Open-World Challenges
2004 DARPA Challenge: Sandstorm Closed world vs open world model• Model of anomaly, surprise• Thinking out of the box?

Where there’s Smoke…
2004 DARPA Challenge: Sandstorm Closed world vs open world model• Model of anomaly, surprise• Thinking out of the box?

(video)Stepping into the Open WorldKey technical challenges
 AI moving into the world
 AI research communityAI Moving into the World:
Trends & Directions
Robust services in dynamic settings Human-computer collaboration
 Integrative intelligence Sciences
 Harnessing webRobust Services in Dynamic SettingsContext-sensitive competencies & policies
Example: Traffic prediction & routing“Sensor”

Robust Services in Dynamic SettingsContext-sensitive competencies & policies
Example: Traffic prediction & routing

Prediction
challenge“Sensor”

Multiuser Location Survey~4.5 years of data collection

Case library• 2,349,600 points• ~300,000 km• ~20,000 trips

ClearFlow

Fielded in 72 cities in North America (April 2008)
Roads speeds assigned to ~60 million streets
across North America every few minutes

Pittsburgh
LouisvillePhiladelphia
Norfolk
Dallas/Ft. Worth
Columbus
DetroitCharlotte
HoustonHartford
Los Angeles
Raleigh-Durham
New York
Richmond
San Francisco
Tulsa
Chicago
AlbanyBaltimoreJacksonville
BostonGreensboro
Washington, D.C.
Nashville
Miami
West Palm Beach
Tampa
New Orleans
OrlandoTucsonSan Diego
AlbuquerqueMinneapolis
Colorado Springs
St. Louis
Allentown

DenverHarrisburg
Cleveland
Wilkes-Barre
PortlandBuffalo
Sacramento
DaytonSeattleFresnoAtlanta
Grand Rapids
Birmingham
ToledoIndianapolis
Greenville
Las Vegas
MemphisOklahoma City
Lincoln
Phoenix
Omaha
Providence
Little RockSalt Lake City
MobileCincinnati
Portsmouth-Manchester
San Antonio
Rochester
Milwaukee
Syracuse
AustinSpokaneKansas City
TorontoChicago

Default

Chicago

Clearflow

Planning while the Sands are Shifting Lab: Temporal models forecast future speeds

and uncertainties
 Path planning with changing situation
 Variances, robustness, flexibility… finding paths with contingenciestttHuman-Computer Collaboration inOpen Worlds

Grounding
Converging on shared references,beliefs, and intentions?
STOPGrounding
Converging on shared references,beliefs, and intentions*&(#))(@%+%%$#*%$#*&%*&(^*^&*%^*&+#

STOP*&(#)@%+ !

Grounding
Converging on shared references,beliefs, and intentions*&(#))(@%+%%$#*%$#*&%*&(^*^&*%^*&+#

STOP*&(#)@%+ ! ?

*&(#))(@%+%%$#*%$#*&(#))(@%+

Grounding
Converging on shared references,beliefs, and intentions*&(#))(@%+%%$#*%$#*&%*&(^*^&*%^*&+#

STOP*&(#)@%+ ! ?

*&(#))(@%+%%$#*%$#*&(#))(@%+

Grounding
Converging on shared references,beliefs, and intentions*&(#))(@%+%%$#*%$#*&%*&(^*^&*%^*&+#

STOP*&(#)@%+ ! ?

*&(#))(@%+%%$#*%$#*&(#))(@%+

Grounding on Beliefs

H2

H1

E1

E2

E3
E4

Grounding on Beliefs

H2

H1

E1

E2

E3
E4
H2

H1

E2

E3
E4

Grounding on Beliefs

H2

H1

E1

E2

E3
E4






Debiasing human judgment
Tutoring, advising, education
Human expectation & surprise
Ideal display & alerting

H2

H1

E2

E3
E4

Mixed-Initiative Collaboration
Interleaving of contributions from machine
and human to jointly solve problems.
 Problem recognition, decomposition, coordination

Mixed-Initiative Collaboration
Interleaving of contributions from machine
and human to jointly solve problems.
 Problem recognition, decomposition, coordinationab

Mixed-Initiative Collaboration
Interleaving of contributions from machine
and human to jointly solve problems.

 Problem recognition, decomposition, coordination

Complementary ComputingConsider systems of people & computation
Policies for coordinating contributions
Task markets for humans, computers, sensors,effectors
Plannerab

Example: Adaptive Policies in an
Automated Reception System
Changing dialog competencies
 Changing load on staffSpeechrecognitioncompetency

Preferences
Human
resources
Complementary
Computing
PolicyH., Paek

Learning about Human Cognition
for Augmenting Human Abilities
20th Century cognitive psychology:
Characterizable limitations & bottlenecks

Cognition

Abilities & efficiencies

HumanLearning about Human Cognition
for Augmenting Human Abilities
20th Century cognitive psychology:
Characterizable limitations & bottlenecks

Cognition

Promise of
sensing &reasoning
Attention

Learning
Computation
MemoryAbilities & efficiencies

HumanLearning about Human Cognition
for Augmenting Human Abilities
20th Century cognitive psychology:
Characterizable limitations & bottlenecks

Cognition

Promise of
sensing &reasoning
Attention

Learning

MemoryAbilities & efficiencies

HumanModels of Memory in Reminding
Model of forgetting

Cost of interruption
Kamar, H.

Models ofcontext-sensitive
relevance / valueModels of Memory in Reminding
Model of forgetting

Models ofcontext-sensitive
relevance / value

Cost of interruption
Reminders at ideal times

Integrative Intelligence
Opportunity: More comprehensive, “integrative
intelligences,” probing open world







Sensing & symbols
Goals & preferences
Action execution, monitoring
Learning, semi- and unsupervised
Interaction of components

Integrative Intelligence
Opportunity: More comprehensive, “integrative
intelligences,” probing open worldWeaving together components that havebeen developed separately

Speechgeneration

Robot motion /manipulation
Speechrecognition

Planning

VisionLearning

Inference

NLP

Localization

Integrative Intelligence

Vision, manipulation, navigation, learning(video)
STAIR, Ng, et al.

Integrative Intelligencewide-angle camera
4-element microphone array
touch screen
card reader
speakers

SpeechSynthesis

AvatarSynthesis

OutputManagement

SpeechRecognition

Conversational
Scene
Analysis

Behavioral control
Dialog management &Interaction Planning
Models of user frustration, task time

Receptionist: Bohus, H., et al.

Tracker

Machine learning about interaction

Integrative Intelligencewide-angle camera
4-element microphone array
touch screen
card reader
speakers

SpeechSynthesis

AvatarSynthesis

OutputManagement

SpeechRecognition

Conversational
Scene
Analysis

Behavioral control
Dialog management &Interaction Planning
Models of user frustration, task time

Receptionist: Bohus, H., et al.

Tracker

Machine learning about interaction

Integrative Intelligencewide-angle camera
4-element microphone array
touch screen
card reader
speakers

SpeechSynthesis

AvatarSynthesis

OutputManagement

SpeechRecognition

Conversational
Scene
Analysis

Behavioral control
Dialog management &Interaction Planning
Models of user frustration, task time

Receptionist: Bohus, H., et al.

Tracker

Machine learning about interaction

Integrative Intelligence

infer, track and verify
group relationships
behavioral modelfor gaze(video)Transformation of ScienceScientific discovery & confirmation



Learning & inference

Triage of experimentation

DendralPlanner, hypothesis generator, confirmation

Learning about Structure & Function

Segal, Pe'er, Regev, Koller, Friedman, et al.

Insights From & About Neurobiology

A Study in Representation

Mitchell, et al.

A Study in Representation

Mitchell, et al.

A Study in Representation

Mitchell, et al.

Coming Era of Neuroinformatics(video)Reid, et al.

Toward a Computational Microscope(video)Kapoor, H., et al.

Learning to Harness the Web

Learning to Harness the Web

Learning to Harness the Web?
ResultsWeb

Learning to Harness the Web?
Results

Web!
Learning &Decision making

Learning to Harness the Web

Azari, H., Dumais

Learning to Harness the Web

Azari, H., Dumais

Learning to Harness the Web

Azari, H., Dumais

Learning to Harness the Web“Where is the Orinoco River?"
15

10

Value

5

0
0

5

10

15

20

-5

-10

-15

Total Queries
Azari, H., Dumais25

AI in the Open World: Responsibilities
Social value & quality of lifePrivacy, democracy, freedomLong-term AI futures

AI in the Open World: Responsibilities
AAAI Presidential Panel on
Long-Term AI Futures“…Deliberation will include reflection about
concerns about long-term outcomes, and,if warranted, on potential recommendations
for guiding research and on creating
policies that might constrain or bias the
behaviors of autonomous and semiautonomous systems so as to address theconcerns…”

Stepping into the Open WorldKey technical challenges
 AI moving into the world
 AI research communityEvolution of Subdisciplines
Logic

Uncertain
Reasoning

Decision
MakingDiagnosis

MachineLearning &Datamining

Planning

Qualitative
Reasoning
Metareasoning& Control

Distributed
AI

Artificial
Intelligence

Real-Time
Reasoning
TemporalReasoning

SearchKnowledge
Representation

Rationality
Constraint
Satisfaction

Cognitive
ScienceEvolution of Specialty Areas
SpeechRecognition

VisionNaturalLanguage
Search &Retrievel

User
Modeling
Intelligent
User Interfaces

Ecommerce

Artificial
Intelligence

SensorNetworks

AI in Medicine
AI in Education

Computational
Neuroscience
AI and Law
Satisfiability& Hardness

Robotics
Ubiquitous
ComputingGame
Playing

Evolution of Communities
VisionNaturalLanguage

UAI

SpeechAAMAS
Recognition
User
Modeling
COLTIntelligent
User Interfaces

COGSCI
SensorNetworks

EC
Search &Retrievel

NIPS

RSS

Artificial
Intelligence

Ecommerce
CVPR
AI in Medicine

ICML

AI in Education

Computational
KDD
Neuroscience

SAT INTERSPEECH

AI and Law

ACLSatisfiability
IUI

Robotics& Hardness
Ubiquitous
UM
Computing

Game
AIED
Playing

Cooperation, Coordination, andInnovation in the Open WorldOn the Nature of the Organization
Herb Simon, 1947
„Three bricklayers were asked what they were doing.
“Laying bricks,”“Building a wall,”“Helping to build a great cathedral”…were their respective answers.‟

Bricks, Arches, Domes …and Spandrels

Bricks, Arches, Domes …and Spandrels

In the Distance, Through the Mist

In the Distance, Through the Mist