Constraint Satisfaction in Artificial Intelligence
undefined
1
Constraint Satisfaction
C
S
D
1
5
-
7
8
0
:
G
r
a
d
u
a
t
e
A
r
t
i
f
i
c
i
a
l
I
n
t
e
l
l
i
g
e
n
c
e
I
n
s
t
r
u
c
t
o
r
s
:
Z
i
c
o
K
o
l
t
e
r
a
n
d
Z
a
c
k
R
u
b
i
n
s
t
e
i
n
T
A
:
V
i
t
t
o
r
i
o
P
e
r
e
r
a
2
Constraint satisfaction problems
A
c
o
n
s
t
r
a
i
n
t
s
a
t
i
s
f
a
c
t
i
o
n
p
r
o
b
l
e
m
(
C
S
P
)
:
A
s
e
t
o
f
v
a
r
i
a
b
l
e
s
X
1
…
X
n
,
a
n
d
a
s
e
t
o
f
c
o
n
s
t
r
a
i
n
t
s
C
1
…
C
m
.
E
a
c
h
v
a
r
i
a
b
l
e
X
i
h
a
s
a
d
o
m
a
i
n
D
i
o
f
p
o
s
s
i
b
l
e
v
a
l
u
e
s
.
A
s
o
l
u
t
i
o
n
t
o
a
C
S
P
:
a
c
o
m
p
l
e
t
e
a
s
s
i
g
n
m
e
n
t
t
o
a
l
l
v
a
r
i
a
b
l
e
s
t
h
a
t
s
a
t
i
s
f
i
e
s
a
l
l
t
h
e
c
o
n
s
t
r
a
i
n
t
s
.
Representation of constraints as predicates.
V
i
s
u
a
l
i
z
i
n
g
a
C
S
P
a
s
a
c
o
n
s
t
r
a
i
n
t
g
r
a
p
h
.
3
Example: Map coloring
WA
SA
NT
N
S
W
V
Q
T
4
Finite vs. infinite domains
Finite domains: 8-queens, matching,
cryptarithmetic, job assignment
Infinite domains: job scheduling
Cannot enumerate all possibilities
Need a constraint language:
StartJob
1
+ 5 ≤ StartJob
3
5
Solving CSPs using search
I
n
i
t
i
a
l
s
t
a
t
e
:
t
h
e
e
m
p
t
y
a
s
s
i
g
n
m
e
n
t
S
u
c
c
e
s
s
o
r
f
u
n
c
t
i
o
n
:
a
v
a
l
u
e
c
a
n
b
e
a
s
s
i
g
n
e
d
t
o
a
n
y
v
a
r
i
a
b
l
e
a
s
l
o
n
g
a
s
n
o
c
o
n
s
t
r
a
i
n
t
i
s
v
i
o
l
a
t
e
d
.
G
o
a
l
t
e
s
t
:
t
h
e
c
u
r
r
e
n
t
a
s
s
i
g
n
m
e
n
t
i
s
c
o
m
p
l
e
t
e
.
P
a
t
h
c
o
s
t
:
a
c
o
n
s
t
a
n
t
c
o
s
t
f
o
r
e
v
e
r
y
s
t
e
p
.
6
High-order constraints
•
O
+
O = R
+
10•X1
•
X
1
+
W
+
W = U
+
10•X
2
•
X
2
+
T
+
T = O
+
10•X
3
•
X
3
= F
•
alldiff
(F,T,U,W,R,O)
T
W
O
+
T
W
O
F
O
U
R
F
T
U
W
R
O
X
3
X
2
X
1
7
Constraint optimization
Representing preferences versus
absolute constraints.
Constraint optimization is generally
more complicated.
Can be solved using local search
techniques.
Hard to find optimal solutions.
8
Commutativity
Naïve application of search to CSPs:
Branching factor is
n
•
d
at the top level, then
(
n-1
)
d
, and so on for
n
levels.
The tree has
n!
•
d
n
leaves, even though there
are only
d
n
possible complete assignments!
N
a
ï
v
e
f
o
r
m
u
l
a
t
i
o
n
i
g
n
o
r
e
s
c
o
m
m
u
t
a
t
i
v
i
t
y
o
f
a
l
l
C
S
P
s
.
S
o
l
u
t
i
o
n
:
c
o
n
s
i
d
e
r
a
s
i
n
g
l
e
v
a
r
i
a
b
l
e
a
t
e
a
c
h
d
e
p
t
h
o
f
t
h
e
t
r
e
e
.
9
Part of the map-coloring search tree
10
Simple backtracking
11
Heuristics that can help
Key questions:
1.
Which variable should be assigned next and in what
order should the values be tried?
2.
What are the implications of the current variable
assignments for the other unassigned variables?
3.
When a path fails, can the search avoid repeating this
failure in subsequent paths?
12
Variable and value ordering
Variable ordering
The most-constrained-variable heuristic
(
has the
fewest
“
legal
”
values
)
The most-constraining-variable heuristic (
involved in
largest number of constraints
)
Value ordering
The least-constraining-value heuristic
(
rules out
the fewest choices for neighboring vars
)
13
Constraint propagation
Reduce the branching factor by deleting values
that are not consistent with the values of the
assigned variables.
Forward checking
: a simple kind of propagation
14
Arc consistency
An arc from
X
to
Y
in the constraint graph is consistent
if, for
every
value of
X
, there is
some
value of
Y
that is
consistent with
X
.
Can detect more inconsistencies than forward checking.
Can be applied as a preprocessing step before search
or as a propagation step after each assignment during
search.
Process must be applied
repeatedly
until no more
inconsistencies remain. Why?
15
AC-3 Arc Consistency Algorithm
16
Complexity of arc consistency
A binary CSP has at most O(
n
2
) arcs
Each arc (
X
Y
) can only be inserted on the agenda
d
times because at most
d
values of
Y
can be
deleted.
Checking consistency of an arc can be done in O(
d
2
)
time.
Worst case time complexity is: O(
n
2
d
3
).
17
K-consistency
A graph is
k
-consistent
if, for any set of
k
variables, there is always a consistent value for
the
k
th variable given any consistent partial
assignment for the other
k
-1 variables.
A graph is
strongly k-consistent
if it is
i
-consistent for
i
= 1..
k
.
Higher forms of consistency offer stronger
forms of constraint propagation.
Specialized algorithms for resource constraints,
bounds constraints, etc.
18
Intelligent backtracking
C
h
r
o
n
o
l
o
g
i
c
a
l
b
a
c
k
t
r
a
c
k
i
n
g
:
a
l
w
a
y
s
b
a
c
k
t
r
a
c
k
t
o
m
o
s
t
r
e
c
e
n
t
a
s
s
i
g
n
m
e
n
t
.
N
o
t
e
f
f
i
c
i
e
n
t
!
C
o
n
f
l
i
c
t
s
e
t
:
A
s
e
t
o
f
v
a
r
i
a
b
l
e
s
t
h
a
t
c
a
u
s
e
d
t
h
e
f
a
i
l
u
r
e
.
B
a
c
k
j
u
m
p
i
n
g
:
b
a
c
k
t
r
a
c
k
t
o
t
h
e
m
o
s
t
r
e
c
e
n
t
v
a
r
i
a
b
l
e
a
s
s
i
g
n
m
e
n
t
i
n
t
h
e
c
o
n
f
l
i
c
t
s
e
t
.
Simple modification of B
ACKTRACKING
-S
EARCH.
Every branch pruned by backjumping is also pruned by forward
checking!
C
o
n
f
l
i
c
t
-
d
i
r
e
c
t
e
d
b
a
c
k
j
u
m
p
i
n
g
:
b
e
t
t
e
r
d
e
f
i
n
i
t
i
o
n
o
f
c
o
n
f
l
i
c
t
s
e
t
s
l
e
a
d
s
t
o
b
e
t
t
e
r
p
e
r
f
o
r
m
a
n
c
e
.
19
Local search for CSPs
Start state is some assignment of values to variables
that may violate some constraints.
Successor state: change value of one variable.
U
s
e
h
e
u
r
i
s
t
i
c
r
e
p
a
i
r
m
e
t
h
o
d
s
t
o
r
e
d
u
c
e
t
h
e
n
u
m
b
e
r
o
f
c
o
n
f
l
i
c
t
s
(
i
t
e
r
a
t
i
v
e
i
m
p
r
o
v
e
m
e
n
t
)
.
T
h
e
m
i
n
-
c
o
n
f
l
i
c
t
s
h
e
u
r
i
s
t
i
c
:
c
h
o
o
s
e
a
v
a
l
u
e
f
o
r
a
v
a
r
i
a
b
l
e
t
h
a
t
m
i
n
i
m
i
z
e
s
t
h
e
n
u
m
b
e
r
o
f
r
e
m
a
i
n
i
n
g
c
o
n
f
l
i
c
t
s
.
Can solve the
million
-queens problem in an average of
50 steps!
20
21
Example of min-conflicts
A two-step solution of an 8-queens problem. The number of remaining
conflicts for each new position of the selected queen is shown. Algorithm
moves the queen to the min-conflict square, breaking ties randomly.
22
Scheduling Example
A process consists of a set of tasks that are
constrained into a partial order by temporal
precedence constraints.
Each task can be accomplished using a set of
resources. There may be multiple sets of resources
that can satisfy the task.
The problem is to schedule the tasks in such a way
as to limit the amount of delay caused by the lack of
resource availability.
23
Scheduling Example (cont.)
Variables: tasks
Values: resource assignments
General algorithm:
Do critical path analysis
Choose task to schedule using variable-ordering heuristic.
Generate possible reservation assignments
This step is needed to account for the domain being so large
(not quite continuous but close).
Select reservation assignment using value-ordering heuristic
24
Scheduling Example (cont.)
In general, different heuristics result in different
schedules.
Still, cannot not guarantee quality in schedule. It depends
on the individual problem.
Not all solutions are possible – what do you do?
Backtrack
Relax termination condition by allowing delay to be
introduced.
Blackboard Systems
Based on a
“
brainstorming experts
”
analogy
Experts work as a team to
“
brainstorm
”
a
solution to a problem, using a large
blackboard as the workplace for
cooperatively developing the solution
Problem specifications are written onto the
blackboard
Experts all watch the blackboard,
contributing their expertise (on the
blackboard) when possible
AI Systems Using BB
Hearsay II and III – Speech
understanding
HASP – Interpretation of sonar signals
AGE – Generalized HASP architecture
OPM – Opportunistic Planner
BB1- Generalized OPM
GBBOpen – BB Framework
26
Blackboard Applications
Some blackboard and blackboard-like systems
include
GEST (Georgia Tech Research Institute)
really a hierarchical rule-based shell
HCVM (FMC & Cimflex Teknowledge)
BB1-like architecture with control-flow short cuts to avoid some
of BB1
’
s overhead
RT-1 (FMC)
another BB1-like architecture with short cuts
Erasmus (Boeing)
a meta-architecture built on top of BBB (Boeing
’
s BB1-like
architecture), UMass GBB, or GBB
ATOME (CRIN/INRIA-Lorraine, Franc)
another BB1-like architecture with control extensions
Blackboard Applications
DVMT (UMass, UMass GBB)
Vehicle monitoring task used to model issues in DAI
Protean (Stanford, BB1)
Identify family of solution-borne 3D protein structures from
NMR data
PBA (FMC/Teknowledge, RT-1)
Real-time monitoring and control of phosphorus
manufacturing
Pilot
’
s Associate (various, UMass GBB, GBB, home-
brew)
Enhance situational awareness and decision-making support
for pilots in advanced fighter aircraft
Early Blackboard Applications
CIM EX (Boeing, UMass GBB)
Pilot
’
s-associate-like domain with emphasis on smart
interface management (PVI)
Macro (Rockwell & Stanford, UMass GBB)
Control of carbon-carbon-composite pyrolysis
SARGE (TI, UMass GBB, GBB)
Develop, evaluate, and refine tactical decision aids
Guardian (Stanford, BB1)
Intensive-care patient monitoring
Intelligent Tutor (FMC, BB1)
Dynamic planning of instructional-material presentation
Blackboard Applications
Address-block recognition (SUNY Buffalo)
On-line network maintenance and diagnosis
(Framentec, France)
Model-based diagnostic reasoning (MIT,
Tektronix)
Pseike robot-control architecture (Purdue)
Weather prediction (Toronto)
Telecommunications-network management
(Neher Labs, The Netherlands)
Human-interface tool suite (MCC)
Blackboard-System
Application Areas
Sensory interpretation
Design and layout
Process control
Planning and scheduling
Computer vision
Knowledge-based simulation
Command and control
Symbolic learning
Case-based reasoning
Data fusion
Knowledge-based instruction
What is a Blackboard System?
E=mc2
E=mc2
A simple problem-solving
concept
Knowledge modules interacting
via a shared database
Extremely subtle and open-
ended in realization
Will detail these issues
Begin by contrasting with rule-
based systems
Many similarities
both approaches were
conceived about the same
time
both have notion of
anonymous invocation
M
M
o
o
d
d
u
u
l
l
e
e
A
A
M
M
o
o
d
d
u
u
l
l
e
e
B
B
M
M
o
o
d
d
u
u
l
l
e
e
C
C
M
M
o
o
d
d
u
u
l
l
e
e
E
E
M
M
o
o
d
d
u
u
l
l
e
e
D
D
Eat at Joe
Eat at Joe
’
’
s
s
`(first ,b)
`(first ,b)
Rule-Based Systems
Characteristics
Control implicit in rule ordering
Strong dependency between
inference engine and
knowledge base
Unstructured working memory
Lots of rules
Fine-grained control
Most working-memory changes
are significant
Working
Memory
Knowledge Base
(Rules)
Inference
Engine
Blackboard Systems
Characteristics
Explicit flexible control
separate from KB
Multiple inference engines
and KB representations
Structured working
memory (blackboard)
A few knowledge sources
Large-grained control
Many blackboard
changes are not
immediately significant
Knowledge Base
Inference
Engine
Blackboard
WM (internal)
Control Shell
Blackboard System Components
Knowledge Sources (KSs)
software specialists; each
providing expertise needed by
the application
The Blackboard
shared repository of problems,
partial solutions, suggestions,
recommendations, and
contributed information
Control Shell
controls the flow of problem-
solving activity in the
application
B
B
l
l
a
a
c
c
k
k
b
b
o
o
a
a
r
r
d
d
C
C
o
o
n
n
t
t
r
r
o
o
l
l
S
S
h
h
e
e
l
l
l
l
Blackboard-System Operation
Characteristics of a
Blackboard System
Large-grained cooperating knowledge source (KS) problem-solving
model
KSs can use diverse internal problem-solving representations and
implementations
KSs interact anonymously using shared global database called the
blackboard
Blackboard serves as communication medium and buffer
Blackboard serves as community memory of data, results, and control
information
Blackboard serves as KS trigger mechanism
Opportunistic problem solving directed by explicit control component
Separate from individual
“
domain
”
KSs
Large-grained control of KS executions
Additional Characteristics
No consensus, but often present!
Solution is generated incrementally
Multiple levels of abstraction
Structured blackboard
beyond level partitioning
Competing hypotheses problem-solving representation
Blackboard used for control information
Reflexive control implemented using blackboard system
Multiple KS representations
many classic
“
blackboard systems
”
support only a single KS
representation
actually partitioned rule-based systems
we won
’
t consider them as true blackboard systems
Communicating Modules
Data-flow-systems design
identify functional modules
connect them according to communication
paths
Advantages
simple, predictable organization
Disadvantages
static processing paths
direct interaction (changes in functional
modules requires redesign)
leads to
“
private
”
interaction protocols that
make interoperability difficult
Blackboard Systems
Blackboard-systems design
identify functional modules, blackboard structure,
and objects
add control strategies as needed
Advantages
dynamic processing paths
adapt to situation
indirect interaction
allows transparent reorganization
“
public
”
representation
allows other modules, development/monitoring tools,
and control components to access communications
blackboard serves as repository
Disadvantages
more complex system infrastructure is needed
Advantages of Blackboard
Systems
Modularity
KSs can be developed independently
KSs can have been developed long before the blackboard-
system application itself
Integration
KSs can use widely differing approaches, representations,
programming languages
KSs can use diverse hardware--locally or remotely
Extensibility
New KSs can be added easily
Existing KSs can be upgraded to new versions
Advantages of Blackboard
Systems
Reusability
KSs that provide expertise to one application can
be redeployed in new applications
Strategic control
Determines where the application expends its
resources
Important when
The number of KSs grows
KSs have overlapping capabilities
Why Use a Blackboard
System?
When multilevel reasoning or flexible, dynamic
control is required
The original AI focus
When heterogeneous problem-solving
representations and expertise must be integrated
Including integration of legacy applications
When many developers are involved
Large-grained anonymous modularity is important for design,
implementation and maintenance
“
metaprogramming
”
Development Strategy
Overview
Initial design
Determine blackboard structure
Determine blackboard objects and their attributes
The interaction
“
ontology
”
for the system
Identify KSs
Legacy and to be written
Sanity check
Match KS interactions with blackboard structure and objects
Prototyping
Prototype new KSs
Interface legacy KSs
Combine KSs to test interactions
Development Strategy
Overview
Adding control
Develop control knowledge and
appropriate control strategies
Test the application
Perform performance tuning
Hearsay-II: The original BB
system
Overview
Who: Carnegie Mellon University
When: 1975-1977
Domain: Connected speech recognition
database retrieval
Goals:
1000 word vocabulary, speaker trained, silent environment
90% functionally accurate interpretations
1/10th real time with a single processor
hoped to use multiprocessing to achieve real-time performance
Characteristics:
15 KSs (C1 configuration), 12-13 (C2 configuration)
Hearsay-II: Architectural
Requirements
Reduce search combinatorics using abstraction
Opportunistic application of diverse knowledge
Compensate for unreliable sensor data by
incremental application of constraints
Apply diverse knowledge intelligently, without a
known problem-solving algorithm
Support multiple system builders via modularization
Support system experimentation and evolution
based on experience using the system
Support high-performance problem solving
using procedural knowledge
Support parallelism
RPOL
WORD-CTL
WORD-SEQ-CTL
STOP
PREDICT
CONCAT
PARSE
WORD-SEQ
MOW
POM
Hearsay-II: Levels and KSs
Database Interface
Phrase
Word-sequence
Syllable
Parameter
SEG
VERIFY
SEMANT
time
Segment
Word
Hearsay-II: KSs
SEG: digitizes the signal
POM: synthesizes syllable-class hypotheses
MOW: synthesizes word hypotheses
WORD-SEQ: synthesizes word-sequence
hypotheses
PARSE: synthesizes a phrase
PREDICT: predicts all possible words before or after
a phrase
VERIFY: checks the consistency between segments
and paired words in a phrase
CONCAT: creates a phrase from verified phrase
predictions
Hearsay-II: KSs
WORD-CTL: controls the behavior of MOW
WORD-SEQ-CTL: controls the behavior of
WORD-SEQ
RPOL: rates the credibility of new or modified
hypotheses
STOP: decides when to halt processing and
attempt an answer
SEMANT: generates the answer when STOP
gives the go ahead
Hearsay-II: Synthesis Actions
Hearsay-II: Precondition-Action Model
KSs had two components
Precondition procedure
determines activation status
estimates behavior of action
procedure
Action procedure
did the real work
Stimulus/response frame
Held state computed by
precondition procedure for use
by action procedure
Could be invalidated if stimulus
context changed
P
P
r
r
e
e
c
c
o
o
n
n
d
d
i
i
t
t
i
i
o
o
n
n
P
P
r
r
o
o
c
c
e
e
d
d
u
u
r
r
e
e
A
A
c
c
t
t
i
i
o
o
n
n
P
P
r
r
o
o
c
c
e
e
d
d
u
u
r
r
e
e
S
S
/
/
R
R
F
F
r
r
a
a
m
m
e
e
Hearsay-II: Scheduling
Criteria
Attempted a linear combination of scheduling criteria:
quality of KS input data
importance of KS input data
estimated quality of KS output data
estimated importance of KS output data
quality of KS knowledge
KS performance
estimated global benefit of KS output data
Linear combination approach (with manual learning)
failed
scheduling needed to be context sensitive
Hearsay-II: Summary
Main contributions
The original blackboard system
The cooperating KS problem-solving model
The competing hypotheses representation
The precondition/action KS model
Identification of important scheduling criteria
Development of numerous programming
“
tricks
”
that were
precursors to later advances in blackboard architectures
Weaknesses
Complex and ill structured
due to numerous changes and advancements during its development
many important aspects buried in code and literature
Designing the Blackboard and
Units
Blackboard structure
What blackboards and spaces are appropriate?
How should the blackboards and spaces be organized?
An issue of representational convenience and personal style
similar to choosing a directory structure for files
Blackboard objects
What information needs to be represented on the
blackboard?
What is an appropriate
“
shared
”
language among KSs?
Does the application have natural objects associated with it?
Can use standard object-oriented design methodologies
Identifying KSs
What processing activities need to be performed?
Functional modularity
Are there obvious partitions of the activities based on
diverse types of processing?
Processing modularity
Are there obvious partitions based on representation
choices?
Representational modularity
Are there choices in what processing should be
applied?
Control modularity
Identifying KSs
Are there specific hardware
requirements for any of the processing?
Implementational modularity
What input/output data is needed?
Data modularity
Defining KSs
What will trigger each KS?
On what spaces will each KS look for input
objects?
What attributes will it use?
What assumptions are made about those
attributes?
What criteria are required for KS activation?
How complete must the input be?
Where will the KS create/modify objects?
What attributes will be initialized/modified?
Analyzing KS Interactions
Review the KS specifications to insure that
Some KS or other activity will trigger each KS
All important events trigger at least one KS
make certain all created/modified objects have the potential to
be used by some KS
Make certain something starts processing
an initial KS or event
Make certain something will stop the processing when
appropriate
continuous versus
“
once-only
”
applications
Use the KS specifications to begin coding KSs
Coding
Assign coding of
Each KS
Blackboard structure and unit definitions (infrastructure
support)
Control strategies (when needed)
KS modularity is advantageous for concurrent, team
coding
Assign domain experts to develop KSs
unless KSs already exist
Develop each KS according to the specifications
any changes affecting the interface specifications must be
relayed to the other KS writers and infrastructure builders
Test each KS in isolation using test data
Coding
KS modularity is advantageous for
evolutionary prototyping and
development
Use developers to simulate KSs via simple
interactive stub
Use canned solution to simple testbed
problem
Use simple (less complete, lower quality)
approach until full KS can be developed
Bringing It All Together
Combine all the KSs in order to get the system to
“
turn over
”
Be alert for
Lack of progress due to missing triggers or activation decisions
Cycles without progress (or with trivial progress)
Missed stop conditions
KS errors or poor output decisions
At this point, there is little strategic control
Watch for
Poor choice of what to do next
it would have been better to be working elsewhere
Poor choice of KS to work next
work is fine, but a better KS exists to do it
Adding Control
Consider what control knowledge exists for the
application
Consider what control problems (lack of focus) have
been encountered
Separate KS-specific control knowledge from generic
and application-wide control knowledge
KS-specific control knowledge should be bundled with the
KS
Choose a control approach (control shell)
Implement and test the control approach and
knowledge
Adding Control
Two levels of control
Sufficient control to get the job done
generally easy
Optimized control to get the job done most
effectively
potentially much harder
Recommendation
Use the simplest control approach and knowledge
that will get the job done
There is a tendency to over-complicate control
activities without evidence of need
Performance Tuning
Performance can be significantly improved by
Measuring what is occurring
Analyzing how performance can be improved
Implementing the improvements
need a flexible blackboard framework to easily implement the improvements
GBBOpen provides metering an mechanisms to easily tune an application
Concentrate on individual KSs
Majority of execution time is spent in KSs
GBBOpen metering indicates which KSs have the biggest impact on
performance
Don
’
t neglect the blackboard
Retrieval patterns and performance easily monitored and changed in
GBBOpen.
Explore the concept of constraint satisfaction in artificial intelligence, covering topics such as CSPs, finite vs. infinite domains, solving CSPs using search, high-order constraints, constraint optimization, and more. Learn about techniques, examples, and challenges in applying constraints to problem-solving in AI.
Download Presentation
Please find below an Image/Link to download the presentation.
The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author. Download presentation by click this link. If you encounter any issues during the download, it is possible that the publisher has removed the file from their server.
E N D
Presentation Transcript
Constraint Satisfaction CSD 15-780: Graduate Artificial Intelligence Instructors: Zico Kolter and Zack Rubinstein TA: Vittorio Perera 1
Constraint satisfaction problems A constraint satisfaction problem (CSP): A set of variablesX1 Xn, and a set of constraintsC1 Cm. Each variable Xi has a domainDi of possible values. A solution to a CSP: a complete assignment to all variables that satisfies all the constraints. Representation of constraints as predicates. Visualizing a CSP as a constraint graph. 2
Example: Map coloring NT Q WA SA NSW V T 3
Finite vs. infinite domains Finite domains: 8-queens, matching, cryptarithmetic, job assignment Infinite domains: job scheduling Cannot enumerate all possibilities Need a constraint language: StartJob1+ 5 StartJob3 4
Solving CSPs using search Initial state: the empty assignment Successor function: a value can be assigned to any variable as long as no constraint is violated. Goal test: the current assignment is complete. Path cost: a constant cost for every step. 5
High-order constraints TWO F T U W R O +TWO FOUR O+O = R+10 X1 X1+W+W = U+10 X2 X2+T+T = O+10 X3 X3 = F alldiff(F,T,U,W,R,O) X3 X2 X1 6
Constraint optimization Representing preferences versus absolute constraints. Constraint optimization is generally more complicated. Can be solved using local search techniques. Hard to find optimal solutions. 7
Commutativity Na ve application of search to CSPs: Branching factor is n d at the top level, then (n-1)d, and so on for n levels. The tree has n! dn leaves, even though there are only dn possible complete assignments! Na ve formulation ignores commutativity of all CSPs. Solution: consider a single variable at each depth of the tree. 8
Heuristics that can help Key questions: Which variable should be assigned next and in what order should the values be tried? What are the implications of the current variable assignments for the other unassigned variables? When a path fails, can the search avoid repeating this failure in subsequent paths? 1. 2. 3. 11
Variable and value ordering Variable ordering The most-constrained-variable heuristic fewest legal values) The most-constraining-variable heuristic (involved in largest number of constraints) Value ordering The least-constraining-value heuristic the fewest choices for neighboring vars) (has the (rules out 12
Constraint propagation Reduce the branching factor by deleting values that are not consistent with the values of the assigned variables. Forward checking: a simple kind of propagation 13
Arc consistency An arc from X to Y in the constraint graph is consistent if, for every value of X, there is some value of Y that is consistent with X. Can detect more inconsistencies than forward checking. Can be applied as a preprocessing step before search or as a propagation step after each assignment during search. Process must be applied repeatedly until no more inconsistencies remain. Why? 14
Complexity of arc consistency A binary CSP has at most O(n2) arcs Each arc (X Y) can only be inserted on the agenda d times because at most d values of Y can be deleted. Checking consistency of an arc can be done in O(d2) time. Worst case time complexity is: O(n2d3). 16
K-consistency A graph is k-consistent if, for any set of k variables, there is always a consistent value for the kth variable given any consistent partial assignment for the other k-1 variables. A graph is strongly k-consistent if it is i-consistent for i = 1..k. Higher forms of consistency offer stronger forms of constraint propagation. Specialized algorithms for resource constraints, bounds constraints, etc. 17
Intelligent backtracking Chronological backtracking: always backtrack to most recent assignment. Not efficient! Conflict set: A set of variables that caused the failure. Backjumping: backtrack to the most recent variable assignment in the conflict set. Simple modification of BACKTRACKING-SEARCH. Every branch pruned by backjumping is also pruned by forward checking! Conflict-directed backjumping: better definition of conflict sets leads to better performance. 18
Local search for CSPs Start state is some assignment of values to variables that may violate some constraints. Successor state: change value of one variable. Use heuristic repair methods to reduce the number of conflicts (iterative improvement). The min-conflicts heuristic: choose a value for a variable that minimizes the number of remaining conflicts. Can solve the million-queens problem in an average of 50 steps! 19
Example of min-conflicts A two-step solution of an 8-queens problem. The number of remaining conflicts for each new position of the selected queen is shown. Algorithm moves the queen to the min-conflict square, breaking ties randomly. 21
Scheduling Example A process consists of a set of tasks that are constrained into a partial order by temporal precedence constraints. Each task can be accomplished using a set of resources. There may be multiple sets of resources that can satisfy the task. The problem is to schedule the tasks in such a way as to limit the amount of delay caused by the lack of resource availability. 22
Scheduling Example (cont.) Variables: tasks Values: resource assignments General algorithm: Do critical path analysis Choose task to schedule using variable-ordering heuristic. Generate possible reservation assignments This step is needed to account for the domain being so large (not quite continuous but close). Select reservation assignment using value-ordering heuristic 23
Scheduling Example (cont.) In general, different heuristics result in different schedules. Still, cannot not guarantee quality in schedule. It depends on the individual problem. Not all solutions are possible what do you do? Backtrack Relax termination condition by allowing delay to be introduced. 24
Blackboard Systems Based on a brainstorming experts analogy Experts work as a team to brainstorm a solution to a problem, using a large blackboard as the workplace for cooperatively developing the solution Problem specifications are written onto the blackboard Experts all watch the blackboard, contributing their expertise (on the blackboard) when possible
AI Systems Using BB Hearsay II and III Speech understanding HASP Interpretation of sonar signals AGE Generalized HASP architecture OPM Opportunistic Planner BB1- Generalized OPM GBBOpen BB Framework 26
Blackboard Applications Some blackboard and blackboard-like systems include GEST (Georgia Tech Research Institute) really a hierarchical rule-based shell HCVM (FMC & Cimflex Teknowledge) BB1-like architecture with control-flow short cuts to avoid some of BB1 s overhead RT-1 (FMC) another BB1-like architecture with short cuts Erasmus (Boeing) a meta-architecture built on top of BBB (Boeing s BB1-like architecture), UMass GBB, or GBB ATOME (CRIN/INRIA-Lorraine, Franc) another BB1-like architecture with control extensions
Blackboard Applications DVMT (UMass, UMass GBB) Vehicle monitoring task used to model issues in DAI Protean (Stanford, BB1) Identify family of solution-borne 3D protein structures from NMR data PBA (FMC/Teknowledge, RT-1) Real-time monitoring and control of phosphorus manufacturing Pilot s Associate (various, UMass GBB, GBB, home- brew) Enhance situational awareness and decision-making support for pilots in advanced fighter aircraft
Early Blackboard Applications CIM EX (Boeing, UMass GBB) Pilot s-associate-like domain with emphasis on smart interface management (PVI) Macro (Rockwell & Stanford, UMass GBB) Control of carbon-carbon-composite pyrolysis SARGE (TI, UMass GBB, GBB) Develop, evaluate, and refine tactical decision aids Guardian (Stanford, BB1) Intensive-care patient monitoring Intelligent Tutor (FMC, BB1) Dynamic planning of instructional-material presentation
Blackboard Applications Address-block recognition (SUNY Buffalo) On-line network maintenance and diagnosis (Framentec, France) Model-based diagnostic reasoning (MIT, Tektronix) Pseike robot-control architecture (Purdue) Weather prediction (Toronto) Telecommunications-network management (Neher Labs, The Netherlands) Human-interface tool suite (MCC)
Blackboard-System Application Areas Sensory interpretation Design and layout Process control Planning and scheduling Computer vision Knowledge-based simulation Command and control Symbolic learning Case-based reasoning Data fusion Knowledge-based instruction
What is a Blackboard System? A simple problem-solving concept Knowledge modules interacting via a shared database Extremely subtle and open- ended in realization Will detail these issues Begin by contrasting with rule- based systems Many similarities both approaches were conceived about the same time both have notion of anonymous invocation E=mc2 `(first ,b) Module A Module B Module C Module D Module E
Rule-Based Systems Characteristics Control implicit in rule ordering Strong dependency between inference engine and knowledge base Unstructured working memory Lots of rules Fine-grained control Most working-memory changes are significant Inference Engine Knowledge Base (Rules) Working Memory
Blackboard Systems Characteristics Explicit flexible control separate from KB Multiple inference engines and KB representations Structured working memory (blackboard) A few knowledge sources Large-grained control Many blackboard changes are not immediately significant WM (internal) Inference Engine Knowledge Base Control Shell Blackboard
Blackboard System Components Knowledge Sources (KSs) software specialists; each providing expertise needed by the application The Blackboard shared repository of problems, partial solutions, suggestions, recommendations, and contributed information Control Shell controls the flow of problem- solving activity in the application Knowledge Sources Sources Sources Sources Knowledge Knowledge Knowledge Control Shell Blackboard
Characteristics of a Blackboard System Large-grained cooperating knowledge source (KS) problem-solving model KSs can use diverse internal problem-solving representations and implementations KSs interact anonymously using shared global database called the blackboard Blackboard serves as communication medium and buffer Blackboard serves as community memory of data, results, and control information Blackboard serves as KS trigger mechanism Opportunistic problem solving directed by explicit control component Separate from individual domain KSs Large-grained control of KS executions
Additional Characteristics No consensus, but often present! Solution is generated incrementally Multiple levels of abstraction Structured blackboard beyond level partitioning Competing hypotheses problem-solving representation Blackboard used for control information Reflexive control implemented using blackboard system Multiple KS representations many classic blackboard systems support only a single KS representation actually partitioned rule-based systems we won t consider them as true blackboard systems
Communicating Modules Data-flow-systems design identify functional modules connect them according to communication paths Advantages simple, predictable organization Disadvantages static processing paths direct interaction (changes in functional modules requires redesign) leads to private interaction protocols that make interoperability difficult
Blackboard Systems Blackboard-systems design identify functional modules, blackboard structure, and objects add control strategies as needed Advantages dynamic processing paths adapt to situation indirect interaction allows transparent reorganization public representation allows other modules, development/monitoring tools, and control components to access communications blackboard serves as repository Disadvantages more complex system infrastructure is needed
Advantages of Blackboard Systems Modularity KSs can be developed independently KSs can have been developed long before the blackboard- system application itself Integration KSs can use widely differing approaches, representations, programming languages KSs can use diverse hardware--locally or remotely Extensibility New KSs can be added easily Existing KSs can be upgraded to new versions
Advantages of Blackboard Systems Reusability KSs that provide expertise to one application can be redeployed in new applications Strategic control Determines where the application expends its resources Important when The number of KSs grows KSs have overlapping capabilities
Why Use a Blackboard System? When multilevel reasoning or flexible, dynamic control is required The original AI focus When heterogeneous problem-solving representations and expertise must be integrated Including integration of legacy applications When many developers are involved Large-grained anonymous modularity is important for design, implementation and maintenance metaprogramming
Development Strategy Overview Initial design Determine blackboard structure Determine blackboard objects and their attributes The interaction ontology for the system Identify KSs Legacy and to be written Sanity check Match KS interactions with blackboard structure and objects Prototyping Prototype new KSs Interface legacy KSs Combine KSs to test interactions
Development Strategy Overview Adding control Develop control knowledge and appropriate control strategies Test the application Perform performance tuning
Hearsay-II: The original BB system Overview Who: Carnegie Mellon University When: 1975-1977 Domain: Connected speech recognition database retrieval Goals: 1000 word vocabulary, speaker trained, silent environment 90% functionally accurate interpretations 1/10th real time with a single processor hoped to use multiprocessing to achieve real-time performance Characteristics: 15 KSs (C1 configuration), 12-13 (C2 configuration)
Hearsay-II: Architectural Requirements Reduce search combinatorics using abstraction Opportunistic application of diverse knowledge Compensate for unreliable sensor data by incremental application of constraints Apply diverse knowledge intelligently, without a known problem-solving algorithm Support multiple system builders via modularization Support system experimentation and evolution based on experience using the system Support high-performance problem solving using procedural knowledge Support parallelism
Hearsay-II: Levels and KSs Database Interface PREDICT STOP SEMANT Phrase WORD-SEQ-CTL CONCAT PARSE Word-sequence WORD-CTL WORD-SEQ VERIFY Word RPOL MOW Syllable POM Segment SEG Parameter time
Hearsay-II: KSs SEG: digitizes the signal POM: synthesizes syllable-class hypotheses MOW: synthesizes word hypotheses WORD-SEQ: synthesizes word-sequence hypotheses PARSE: synthesizes a phrase PREDICT: predicts all possible words before or after a phrase VERIFY: checks the consistency between segments and paired words in a phrase CONCAT: creates a phrase from verified phrase predictions
Hearsay-II: KSs WORD-CTL: controls the behavior of MOW WORD-SEQ-CTL: controls the behavior of WORD-SEQ RPOL: rates the credibility of new or modified hypotheses STOP: decides when to halt processing and attempt an answer SEMANT: generates the answer when STOP gives the go ahead
