Transcript CHS-Soar - AGI conferences

Introducing Constrained Heuristic Search
to the Soar Cognitive Architecture
(demonstrating domain independent learning in Soar)
The Second Conference on Artificial General Intelligence, AGI-09
Sean A. Bittle
Mark S. Fox
March 7th, 2009
1
/11
The Problem

General problem solving and learning are central goals of AI research
on cognitive architectures

However, there are few examples of domain independent learning in
cognitive architectures
The Goal

Demonstrate Soar can learn and apply domain independent knowledge
But to achieve this goal we need to augment the Soar’s problem-solving
paradigm (CHS-Soar)
2
/11
Soar Cognitive Architecture

Developed by Newell, Laird and Rosenbloom at
CMU, 1983

Symbolic Cognitive Architecture where all long
term knowledge is encoded as productions
rules.

Based on the hypothesis that all goal-oriented
behavior can be cast as the selection and
application of operators to a state in a problem
space
3
/11
Constrained Heuristic Search (CHS)

Developed by Fox, Sadeh and Bayken, 1989

CHS is a problem solving approach that combination of constraint satisfaction
and heuristic search where the definition of the problem space is refined to
include:

Problem Topology

Problem Textures

Problem Objective
Constraint Graph
Va
Ci
Vc
Cii
Vb

CP/CHS allows us to employ a generalized problem representation
(CSP) and utilize generic, yet powerful problem solving techniques
4
/11
CHS-Soar
“What
are we trying to learn?”
5
/11
CHS-Soar
What are “Texture Measures?”
Textures are
measures of the
problem topology
•Minimum Remaining Values (MRV) – variable selection
•Degree (DEG) – variable selection
•Least Constraining Value (LCV) – value selection
Constraint Graph
External Agent
Problem
Data
Var
Dom
Actual
MRV
Soar Agent
Normalized
DEG
MRV
DEG
Pruned
Num
MRV
DEG
WA
R,G,B 3
2
0.50
0.40
1
0.50
0.00
NT
R,G,B 3
3
0.50
0.60
2
-
0.40
SA
R,G,B 3
5
0.50
1.00
3
-
0.60
Q
R,G,B 3
3
0.50
0.60
4
-
1.00
NSW
R,G,B 3
3
0.50
0.60
V
R,G,B 3
2
0.50
0.40
T
R,G,B 3
0
0.50
0.00
6
/11
CHS-Soar
“How Do We Select a “Good” Texture Measure?”
MRV
DEG
DEG
DEG
DEG
0.50
0.00
0.40
0.60
1.00
7
/11
CHS-Soar
“What Do We Learn...Again?”
“Chunk” decoupled
from problem type
Traditional Soar Agent Chunks tend
to include domain specific
knowledge
Standard Soar Chunk (Water Jugs)
sp {chunk-54*d150*tie*2
:chunk
(state <s1> ^name water-jug ^operator <o1> +
^problem-space <p1>
^desired <d1> ^jug <j1> ^jug <j2>)
(<o1> ^name fill ^jug <j1>)
(<p1> ^name water-jug)
(<j1> ^contents 0 ^volume 3)
(<j2> ^contents 0 ^volume 5)
(<d1> ^jug <j3>)
(<j3> ^contents 1 ^volume 3)
-->
(<s1> ^operator <o1> >) }
Hyper-heuristics:
heuristics to choose heuristic
measures
CHS-Soar Chunk
sp {chunk-128*d351*tie*2
:chunk
(state <s1> ^phase |SelectVariableTexture|
^top-state <s1> ^name |CHS-Soar|
^operator <o1> + ^operator { <o2> <> <o1> } +
^problem-space <p1> ^desired <d1>)
(<o1> ^texture |DEG| ^value 0.66 ^name |VariableTexture|)
(<o2> ^texture |MRV| ^value 1.
^name |VariableTexture|)
(<p1> ^name |CHS-Soar|)
-->
(<s1> ^operator <o1> > <o2>) }
8
/11
Experiments
Three experiments conducted to investigate:
1.
2.
3.
Integration of rule and constraint based reasoning
Domain Independent Learning
Scalability of externally learned chunks
Problem types being considered:
•
•
•
•
•
•
•
Job Shop Scheduling (JSS)
Map Colouring
Radio Frequency Assignment Problem (RFAP)
N-Queens, Sudoku, Latin Square
Towers of Hanoi, Water Jugs
Configuration Problems
Random CSPs
9
/11
Results: Domain Independent Learning
Decisions
100
Map
Colouring
(n = 11)
Benchmark
Internal
External
90
80
70
Benchmark (HardCoded)
MapCol (n = 11)
JSS (n = 15)
RFAP (n = 200)
NQueens (n = 16)
75
Decisions
Job Shop
Scheduling
(n = 15)
65
55
45
Benchmark (HardCoded)
JSS (n = 15)
MapCol (n = 11)
RFAP (n = 200)
NQueens (n = 16)
Benchmark (HardCoded)
RFAP (n = 200)
MapCol (n = 11)
JSS (n = 15)
NQueens (n = 16)
RFAP
(n = 200)
Decisions
3700
3600
3500
3400
10
/11
Conclusions

Demonstrated integration of rule and constraint based reasoning

Demonstrated the ability to learn rules while solving one problem type that
can be successfully applied in solving another problem type

Demonstrated ability to discover, learn and use multi-textured “hyper-heuristics”
leading to improved solutions over traditional unary heuristics
11
/11