Transcript Document

INFO 372:
Explorations in Artificial Intelligence
Prof. Carla P. Gomes
[email protected]
Module 2
Example Applications
Previous Lecture:
What's involved in Intelligence?
A) Ability to interact with the real world
to perceive, understand, and act
speech recognition and understanding
image understanding (computer vision)
B) Reasoning and Planning
modelling the external world
problem solving, planning, and decision making
ability to deal with unexpected problems, uncertainties
C) Learning and Adaptation
We are continuously learning and adapting.
We want systems that adapt to us!
INFO 372
Previous Lecture
• AI goals:
– understand “intelligent” behavior
– build “intelligent” agents
• Intelligence  not necessarily human like
Issue: The Hardware
• The brain
–
–
–
–
a neuron, or nerve cell, is the basic information
processing unit (10^11 )
many more synapses (10^14) connect the neurons
cycle time: 10^(-3) seconds (1 millisecond)
• How complex can we make computers?
– 10^8 or more transistors per CPU
– supercomputer: hundreds of CPUs, 10^10 bits of RAM
– cycle times: order of 10^(-9) seconds (1 nanosecond)
Computer vs. Brain
• Conclusion
– In near future we can have computers with as many
processing elements as our brain, but:
far fewer interconnections (wires or synapses)
much faster updates.
Fundamentally different hardware may require
fundamentally different algorithms!
– Very much an open question.
Previous Lecture
• AI goals:
– understand “intelligent” behavior
– build “intelligent” agents
• Intelligence  not necessarily human like
Developing methods to match or exceed human performance
in certain domains, possibly by very different means
 e.g., Deep Blue;
Focus of INFO372 (most recent progress).
1997:
Deep Blue beats the World Chess Champion
vs.
I could feel human-level intelligence across the room
-Gary Kasparov, World Chess Champion (human…)
How Intelligent is Deep Blue?
• Saying Deep Blue doesn't really think about
chess is like saying an airplane doesn't
really fly because it doesn't flap its wings.
- Drew McDermott
On Game 2
(Game 2 - Deep Blue took an early lead.
Kasparov resigned, but it turned out he could
have forced a draw by perpetual check.)
This was real chess. This was a game any human
grandmaster would have been proud of.
Joel Benjamin grandmaster, member Deep Blue team
Kasparov on Deep Blue
• 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.”
Game Tree Search
• How to search a game tree was
independently invented by Shannon (1950)
and Turing (1951).
• Technique called: MiniMax search.
• Evaluation function combines material &
position.
Game Tree Search
History of Search Innovations
•Shannon, Turing
•Kotok/McCarthy
•MacHack
•Chess 3.0+
•Belle
•Cray Blitz
•Hitech
•Deep Blue
Minimax search 1950
Alpha-beta pruning1966
Transposition tables1967
Iterative-deepening1975
Special hardware 1978
Parallel search
1983
Parallel evaluation 1985
All of the above 1997
Transposition Tables
• Introduced by Greenblat's Mac Hack (1966)
• Basic idea: caching
– once a board is evaluated, save it in a hash table, avoid reevaluating.
– called “transposition” tables, because different orderings
(transpositions) of the same set of moves can lead to the same
board.
– Form of root learning (memorization)
– Don’t repeat blunders  can’t beat the computer twice in a row
using same moves
Deep Blue --- huge transposition tables (100,000,000+),
must be carefully managed.
Positions with Smart Pruning
Search Depth
2
4
6
8
10
12
14
16
(<1 second DB)
(5 minutes DB)
Positions
60
2,000
60,000
2,000,000
60,000,000
2,000,000,000
60,000,000,000
2,000,000,000,000
How many lines of play does a grand master consider?
Around 5 to 7
Special-Purpose and Parallel Hardware
•
•
•
•
Belle (Thompson 1978)
Cray Blitz (1993)
Hitech (1985)
Deep Blue (1987-1996)
– Parallel evaluation: allows more complicated
evaluation functions
– Hardest part: coordinating parallel search
– Deep Blue never quite plays the same game,
because of “noise” in its hardware!
Deep Blue
• Hardware
– 32 general processors
– 220 VSLI chess chips
• Overall: 200,000,000 positions per second
– 5 minutes = depth 14
• Selective extensions - search deeper at
unstable positions
– down to depth 25 !
Tactics into Strategy
• As Deep Blue goes deeper and deeper into a
position, it displays elements of strategic
understanding. Somewhere out there mere
tactics translate into strategy. This is the
closet thing I've ever seen to computer
intelligence. It's a very weird form of
intelligence, but you can feel it. It feels like
thinking.
– Frederick Friedel (grandmaster), Newsday, May 9, 1997
Goals of INFO 372
Introduce the students to a range of computational
modeling approaches and solution strategies using
examples from AI and Information Science.
Formalisms:
Logical representations;
Constraint-based languages,
Mathematical programming – Linear and Integer programming;
Multi-agent formalisms (including adversarial games);
Solution strategies:
Logical inference;
General complete backtrack search; (e.g., Iterative Deepening)
Local search;
Dynamic Programming;
Game tree search (e.g., alpha-beta pruning)
Goals of INFO 372
Special models:
Satisfiability (SAT); Maximum SAT; Horn
Constraint Satisfaction; Binary Constraint Satisfaction;
Mixed Integer Programming, Linear Programming and
Network Flow Models;
Themes:
Expressiveness and efficiency tradeoffs of the various representation
formalisms
Students learn about the tradeoffs in modeling choices.;
Concrete examples to move from one representation modeling
formalism to another formalism;
Example of a reasoning formalism:
Constraint Satisfaction
Escher:
Waterfall, 1961
Escher:
Belvedere, May 1958
Escher:
Ascending and Descending, 1960
How do we Interpret the
Scenes in Escher’s Worlds?
Analysis of Polyhedral Scenes
origins of Constraint Reasoning 
researchers in computer vision in the 60s-70s were
interested in developing a procedure to assign 3dimensional interpretations to scenes;
They identified
Three types of edges
Four types of junctions
Edge Types
Hidden – if one of its planes cannot be seen
Huffman-Clowes
Labeling
represented with arrows:
 or 
Convex – from the viewer’s perspective
represented with
+
Concave – from the viewer’s perspective
represented with
-
Types of Junctions
Type of junction:
L
Fork
T
Arrow
Scene Interpretation
Constraint Reasoning Problem:
Variables  Edges;
Domains  {+,-,,}
Constraints:
1- The different type junctions define constraints:
L, Fork, T, Arrow;
L = {(, ) , ( , ), (+, ), (,+), (-, ), (,-)}
L(A,B)  the pair of values assigned to variables A,B
has to belong in the set L;
Fork = { (+,+,+), (-,-,-), (,,-), (,-,),(-,,)}
Fork(A,B,C)  the trio of values assigned to variables A,B,C
has to belong in the set Fork;
CSP Model
• T = {(, , ) , ( ,,), (,,+), (,-)}
T(A,B,C)  the trio of values assigned to variables A,B,C
has to belong in the set T;
• Arrow = { (,,+), (+,+,-), (-,-,+)}
Arrow(A,B,C)  the trio of values assigned to variables A,B,C
has to belong in the set Arrow;
2- For each edge XY its reverse YX has a compatible value
Edge = { +,+), (-,-), (,),(,)}
Edge(A,B)  the pair of values assigned to variables A,B
has to belong in the set Edge;
CSP Model - Cube
E
A
F
B
How to label the cube?
G
C
D
CSP Model
Variables: Edges: AB, BA,AC,CA,AE,EA,CD,
DC,BD,DB,DG,GD,GF,FG,EF,FE,AE,EA;
Domains  {+,-,,}
Constraints:
L(AC,CD); L(AE,EF); L(DG,GF);
Arrow(AC,AE,AB); Arrow(EF,FG,BF); Arrow(CD,DG,DB);
E
Fork(AB,BF,BD);
Edge(AB,BA); Edge(AC,CA); Edge(AE,EA);
A
Edge(EF,FE); Edge(BF,FB); Edge(FG,GF);
Edge(CD,DC); Edge(BD,DB); Edge(DG,GD);
C
F
B
G
D
CSP Model
Variables: Edges: AB, BA,AC,CA,AE,EA,CD,
DC,BD,DB,DG,GD,GF,FG,EF,FE,AE,EA;
Domains  {+,-,,}
Constraints:
L(AC,CD); L(AE,EF); L(DG,GF);
Arrow(AC,AE,AB); Arrow(EF,FG,BF); Arrow(CD,DG,DB);
Fork(AB,BF,BD);
A
Edge(AB,BA); Edge(AC,CA); Edge(AE,EA);
Edge(EF,FE); Edge(BF,FB); Edge(FG,GF);
Edge(CD,DC); Edge(BD,DB); Edge(DG,GD);
C
E
+
F
+
B
G
+
D
One (out of four) possible labelings
The Impossible Objects is Escher’s Worlds
Penrose & Penrose Stairs
Penrose Triangle
Impossible Objects:
No labeling!
Other examples using
a Constraint Satisfaction formalism
Sudoku
Constraint Satisfaction Problem (CSP)
and Satisfiability and Integer
Programming
9 55 ~ 3x 10 52 possible completions
Latin Squares
Given an N X N matrix, and given N colors, a Latin Square of
order N is a a colored matrix, such that:
-all cells are colored.
- each color occurs exactly once in each
row.
- each color occurs exactly once in each
column.
Quasigroup or Latin Square
(Order 4)
Constraint Satisfaction Problem (CSP)
and Satisfiability and Integer
Programming
Latin Squares
Given an N X N matrix, and given N colors, a Latin Square of
order N is a a colored matrix, such that:
-all cells are colored
-a color is not repeated in a row
-a color is not repeated in a column
Quasigroup or Latin Square
(Order 4)
Constraint Satisfaction Problem (CSP)
and Satisfiability and Integer
Programming
Latin Square Completion Problem
Given a partial assignment of colors (10 colors in this
case), can the partial latin square be completed so we
obtain a full Latin square?
Example:
32% preassignment
10 68 possible completions
Fiber Optic Networks
Wavelength
Nodes
connect point to point
fiber optic links
Division
Multiplexing (WDM)
the most promising
technology for the
next generation of
wide-area
Each fiber optic link supports a
large number of wavelengths
backbone networks.
Nodes are capable of photonic switching
--dynamic wavelength routing -which involves the setting of the wavelengths.
Routing in Fiber Optic Networks
preassigned channels
Input Ports
1
Output Ports
1
2
2
3
3
4
4
Routing Node
How can we achieve conflict-free routing in each node of the network?
Dynamic wavelength routing is a NP-hard problem.
LSCP Application Example:
Routers in Fiber Optic Networks
Dynamic wavelength routing in Fiber Optic Networks can be
directly mapped into the Latin Square Completion Problem.
•each channel cannot be repeated in the same input port (row constraints);
• each channel cannot be repeated in the same output port (column
constraints);
1
2
3
4
Output ports
Output Port
1
2
3
4
Input ports
Input Port
CONFLICT FREE
LATIN ROUTER
Design of Statistical Experiments
We have 5 treatments for growing beans. We want to know what treatments are
effective in increasing yield, and by how much.
The objective is to eliminate bias and distribute the treatments somewhat evenly
over the test plot.
Latin Square Analysis of Variance
A
D
E
B
C
C
B
A
E
D
D
C
B
A
E
E
A
C
D
B
B
E
D
C
A
(*) Already in use
in this sub-plot
Spatially Balanced Latin Squares
Really hard to build balanced LS’s
Timetabling:
Constraint Satisfaction Problem (CSP) and
Integer Programming
The problem of generating schedules with complex
constraints (in this case for sports teams).
An 8 Team Round Robin Timetable
Period 1
Week 1
0 vs 1
Week 2
0 vs 2
Week 3
4 vs 7
Week 4
3 vs 6
Week 5
3 vs 7
Week 6
1 vs 5
Week 7
2 vs 4
Period 2
2 vs 3
1 vs 7
0 vs 3
5 vs 7
1 vs 4
0 vs 6
5 vs 6
Period 3
4 vs 5
3 vs 5
1 vs 6
0 vs 4
2 vs 6
2 vs 7
0 vs 7
Period 4
6 vs 7
4 vs 6
2 vs 5
1 vs 2
0 vs 5
3 vs 4
1 vs 3
28 28 ~ 3.3 x 1040 possibilities
Why Sports Scheduling???
Source:
Mike Trick
Big Business!
US National TV pays $500 million / year for baseball
College basketball conferences get up to $30 million
Manchester United has (had) a market cap of £400 million
No rights holder wants to pay those sums and then get a “bad” schedule
Difficult to automate:
Huge variety of problem types
Small instances are difficult
Strong break between easy/hard (for all algorithms)
Significant theoretical background
CP and IP differ in modeling
CP has clean models with [1..n] variables
IP uses 0-1 variables reasonably naturally
Practical interest in instances at the easy/hard interface
Graph Coloring
nn ~ possible colorings for n nodes
Coloring the nodes of the graph:
What’s the minimum number of colors such that any two nodes
connected by an edge have different colors?
Graph Coloring
Constraint Satisfaction Problem (CSP)
and Satisfiability and Integer Programming
Another example of a reasoning formalism
A restricted form of Constraint Satisfaction:
Satisfiability
Propositional Satisfiability problem
Satifiability (SAT): Given a formula in propositional calculus, is there
an assignment to its variables making it true?
We consider clausal form, e.g.:
( a OR NOT b OR NOT c ) AND ( b OR NOT c) AND ( a
2
n
OR
c)
possible assignments
SAT: prototypical hard combinatorial search and reasoning
problem. Problem is NP-Complete. (Cook 1971)
Surprising “power” of SAT for encoding computational problems.
Significant progress in
Satisfiability Methods
Software and hardware verification –
complete methods are critical - e.g. for
verifying the correctness of chip design, using
SAT encodings
Going from 50 variable, 200 constraints
to 1,000,000 variables and 5,000,000 constraints
in the last 10 years
Current methods can verify automatically the
correctness of > 1/7 of a Pentium IV.
Applications:
Hardware and
Software Verification
Planning,
Protocol Design, etc.
A “real world” example
Bounded Model Checking instance:
i.e. ((not x1) or x7)
and ((not x1) or x6)
and … etc.
10 pages later:
…
(x177 or x169 or x161 or x153 …
or x17 or x9 or x1 or (not x185))
clauses / constraints are getting more interesting…
4000 pages later:
!!!
a 59-cnf
clause…
…
Finally, 15,000 pages later:
… !!!
Note that:
The Chaff SAT solver solves
this instance in less than one minute.
Another example of a reasoning formalism
Integer Programming
Knapsack Problem (one resource)
A hiker trying to fill her knapsack to maximum total value. Each item she considers
taking with
her has a certain value and a certain weight. Goal – maximize the value of the
contents of the
knapsack considering the overall weight constraint.
•
This problem is an abstraction with many practical applications:
Project selection and capital budgeting allocation problems
Storing a warehouse to maximum value given the indivisibility of goods and space
limitations
Sub-problem of other problems e.g., generation of columns for a given model in the
course of optimization – cutting stock problem (beyond the scope of this course)
Capital Budgeting Example
Investment budget = $14,000
Investment
Cash
Required
(1000s)
NPV
added
(1000s)
1
2
3
4
5
6
$5
$7
$4
$3
$4
$6
$16 $22 $12 $8
$11 $19
maximize 16x1 + 22x2 + 12x3 + 8x4 +11x5 + 19x6
subject to
5x1 + 7x2 + 4x3 + 3x4 +4x5 + 6x6  14
xj binary for j = 1 to 6
Binary Optimization:
Applications in Regional
Planning
Zevi Azzaino
Jon Conrad
Carla Gomes
Models
Knapsack and Variants
I
Maximize
c x
i 1
i i
I
Subject to
w x
i 1
i i
M
x i  {0,1} and i  1,...I
Stream Footage
Phosphorous
Pathogen
Parcel Size
Parcel Value
Budget Constraint
Town of Skaneateles:
-1834 parcels
-12341 acres
52 land use class.
Riparian Buffer in the
Skaneateles Lake Watershed
Objective: Identify the best collection
of parcels to include
in a riparian buffer subject to a budget constraint
Contribution to a scenic landscape
or agricultural setting
Historic significance
2,345 barns registered in year 2000
464 barns in Finger Lakes Region only.
Budget: $2 million; Max of $25,000
grant per barn
Office of Parks, Recreation and
Historic Preservation
Preservation in NY State
Important Natural Community
Geological Importance
Aesthetic/Cultural Qualities
Budget Constraint
Unique Natural Areas in
Tompkins County
Southwestern Airways Crew Scheduling
• Southwestern Airways needs to assign
crews to cover all its upcoming flights.
• Simple example  assigning 3 crews based
in San Francisco (SFO) to 11 flights.
Question: How should the 3 crews be
assigned 3 sequences of flights so that
every one of the 11 flights is covered?
Other Integer Programming problems
Southwestern Airways Flights
Seat tl e
(SEA)
San Francis co
(SFO)
Los Angel es
(LAX)
Denver
(DEN)
Chi cago
ORD)
Data for the Southwestern Airways Problem
Feasible Sequence of Flights (pairings)
Flights
1
1. SFO–LAX
1
2. SFO–DEN
2
3
5
6
1
1
3. SFO–SEA
1
2
3
3
3
4
9. DEN–ORD
3
4
4
4
6
7
3
5
5
3
3
4
5
7
2
4
2
3
2
2
2
11. SEA–LAX
1
5
2
10. SEA–SFO
12
4
7. ORD–SEA
2
11
1
3
3
10
1
1
2
2
9
1
2
8. DEN–SFO
8
1
1
6. ORD–DEN
Cost, $1,000s
7
1
4. LAX–ORD
5. LAX–SFO
4
8
5
2
4
4
2
9
9
8
9
Algebraic Formulation
Let xj = 1 if flight sequence (paring) j is assigned to a crew; 0 otherwise. (j = 1, 2, … , 12).
Minimize Cost = 2x1 + 3x2 + 4x3 + 6x4 + 7x5 + 5x6 + 7x7 + 8x8 + 9x9 + 9x10 + 8x11 + 9x12
(in $thousands)
pairings
subject to
Flight 1 covered:
x1 + x4 + x7 + x10 ≥ 1
Flight 2 covered:
:
Flight 11 covered:
Three Crews:
x2 + x5 + x8 + x11 ≥ 1
:
x6 + x9 + x10 + x11 + x12 ≥ 1
x1 + x2 + x3 + x4 + x5 + x6 + x7 + x8 + x9 + x10 + x11 + x12 ≤ 3
and
xj are binary (j = 1, 2, … , 12).
Combinatorial Problems
Combinatorial Problems
•
Many computational tasks, such as planning or
scheduling, can in principle be reduced to an exploration
of a large set of all possible scenarios.
•
Try all possible schedules, try all possible plans, pick the
best.
Problem: combinatorial explosion!
AI PLANNING
In AI, planning involves the generation of an action
plan (i.e. a sequence of actions) for an agent, such as a robot or
a software system or a living artefact, that can alter
its surroundings.
Planning implies the notion of synthesis: synthesis of actions, to go
from an initial state to a goal state.
Examples:
•plan to perform astronomical observations for the Hubble space
telescope;
•plan for a robot to assemble pieces in a factory
Planning Example:
Blocks world
• objects: blocks and a table
• actions: move blocks ‘on’ one object to ‘on’
another object
• goals: configurations of blocks
• plan: sequence of actions to achieve goals
B
A
A
B
D
D
C
C
Initial State
Goal State
T
Blocks world:
propositional and first order logic representation
Knowledge Base:
On(A,T)^On(B,T)^On(C,T)^On(D,C)
^Block(A)^Block(B)^Block(C)^Block(D) )^Table(T)
^Clear(A)^Clear(B)^Clear(D)
D
A
B
C
T
Move(A,T,D)
A
D
B
C
T
KB:
On(A,D)^On(B,T)^On(C,T)^On(D,C)
^Block(A)^Block(B)^Block(C)^Block(D)^Table(T)
^Clear(A) ^Clear(B)
Planning Complexity
Planning (single-agent):
find the right sequence of actions
HARD: 10 actions, 10! = 3 x 106 possible plans
100 ! = 9.33262154 × 10157
Contingency planning (multi-agent):
actions may or may not produce the desired effect!
…
1 out
of 10
4 out
2 out of 8
of 9
REALLY HARD: 10 x 92 x 84 x 78 x … x 2256 = 10224 possible contingency plans!
Exceptions:
Some Kinds of Networks
Networks are Everywhere
Physical Networks
Road Networks
Railway Networks
Airline traffic Networks
Electrical networks, e.g., the power grid
Computer networks
New areas of application 
Social networks - e.g. relationships networks (6 degrees of
Kevin Bacon ); communities such as researchers, CEO’s etc
Economic/ technological networks – e.g. patents:
Applications of Network Optimization
Applications
Physical analog
of nodes
Physical analog
of arcs
Flow
phone exchanges,
Cables, fiber optic Voice messages,
Communication
computers,
links, microwave
Data,
systems
transmission
relay links
Video transmissions
facilities, satellites
Pumping stations
Reservoirs, Lakes
Integrated
Gates, registers,
computer circuits
processors
Hydraulic systems
Pipelines
Water, Gas, Oil,
Hydraulic fluids
Wires
Electrical current
Mechanical systems
Joints
Rods, Beams,
Springs
Heat, Energy
Transportation
systems
Intersections,
Airports,
Rail yards
Highways,
Airline routes
Railbeds
Passengers,
freight,
vehicles,
operators
Network Flow Algorithms:
• “Nice” combinatorial problem (Min Cost Flow) – exception to
combinatorial explosition  polynomial scaling !
• General formulation for special problems:
–
–
–
–
shortest paths
transportation problem
assignment problem
plus more
• Important subproblem of many optimization problems,
including multicommodity flows
But most interesting real-world problems are:
NP-Complete and
NP-Hard Problems
EXPLOSIVE
COMBINATORICS
Start
Goal
Experiment
Design
Planning and Scheduling
And Supply Chain Management
Satisfiability
(A or B) (D or E or not A)
Data Analysis
Protein
& Data Mining
Folding
Capital Budgeting
And Medical
And Financial Appl. Combinatorial Information
Applications
Auctions
Retrieval
EXPONENTIAL-TIME
ALGORITHMS
Software & Hardware
Verification
Hard Computational
Problems
Scale Exponentially
Fiber optics routing
Many more
applications!!!
Require
powerful computational and
mathematical tools!
EXPONENTIAL
FUNCTION
POLYNOMIAL
FUNCTION
Goals of INFO 372
Introduce the students to a range of computational
modeling approaches and solution strategies using
examples from AI and Information Science.
Formalisms:
Logical representations;
Constraint-based languages,
Mathematical programming – Linear and Integer programming;
Multi-agent formalisms (including adversarial games);
Solution strategies:
Logical inference;
General complete backtrack search; (e.g., Iterative Deepening)
Local search;
Dynamic Programming;
Game tree search (e.g., alpha-beta pruning)
Goals of INFO 372
Special models:
Satisfiability (SAT); Maximum SAT; Horn
Constraint Satisfaction; Binary Constraint Satisfaction;
Mixed Integer Programming, Linear Programming and
Network Flow Models;
Themes:
Expressiveness and efficiency tradeoffs of the various representation
formalisms
Students learn about the tradeoffs in modeling choices.;
Concrete examples to move from one representation modeling
formalism to another formalism;