Transcript Computational Discovery of Communicable Knowledge

Architectures for Intelligent Systems
Pat Langley
Computational Learning Laboratory
Center for the Study of Language and Information
Stanford University, Stanford, California
http://cll.stanford.edu/
Thanks to Dongkyu Choi, Kirstin Cummings, Wayne Iba, Negin Nejati, David Nicholas,
Seth Rogers, Stephanie Sage, and Daniel Shapiro for contributions to this research.
In the Beginning . . .
AI
monobloc
The Big Bang Theory of AI
language
planning
perception

reasoning
action
learning
Twenty Questions
At the 1971 Carnegie Symposium, Allen Newell argued that:
 psychology had focused too much on isolated issues;
 this strategy would never lead us to understand the mind;
 we could only achieve this by developing integrated theories.
He claimed “You can’t play twenty questions with nature and win”.
The same critique holds for what John Laird has called “niche AI”.
An Alternative to Twenty Questions
Newell’s alternative to twenty questions was that we should:
 move beyond isolated phenomena and capabilities to develop
complete models of intelligent behavior;
 demonstrate their intelligence on the same range of domains
and tasks as humans can handle;
 view artificial intelligence and cognitive psychology as close
allies with distinct but related goals;
 evaluate systems in terms of generality and flexibility rather
than success on a single application domain.
He associated these aims with the idea of a cognitive architecture.
Intelligent Systems as Communicating Modules
language
planning
perception
reasoning
action
learning
software engineering / multi-agent systems
Modules that Share Short-Term Memory
language
planning
perception
short-term
beliefs and goals
reasoning
action
learning
blackboard architectures
Modules that Share Long-Term Memory
language
perception
planning
short-term
beliefs and goals
long-term memory
structures
action
learning
cognitive architectures
reasoning
Aspects of Cognitive Architectures
As traditionally defined and utilized, a cognitive architecture:
 specifies the infrastructure that holds constant over domains,
as opposed to knowledge, which varies.
 models behavior at the level of functional structures and
processes, not the knowledge or implementation levels.
 commits to representations and organizations of knowledge
and processes that operate on them.
 comes with a programming language for encoding knowledge
and constructing intelligent systems.
Early candidates were cast as production system architectures,
but alternatives have gradually expanded the known space.
Examples of Cognitive Architectures
ACT
Soar
PRODIGY
EPIC
GIPS
RCS
CAPS
APEX
3T
CLARION
Dynamic
Memory
Society
of Mind
Listen to the Architecture
Newell’s vision for research on theories of intelligence was that:
 cognitive architectures should incorporate strong theoretical
assumptions about the nature of the mind.
 architectural designs should change only gradually, as new
structures or processes are determined necessary.
 later design choices should be constrained heavily by earlier
ones, not made independently.
The research program was all about mutual constraints, and it
was important to “listen to the architecture”.
A successful architecture should provide a unified theory of
intelligent behavior.
Mutually Constraining Components
language
perception
planning
short-term
beliefs and goals
long-term memory
structures
action
learning
reasoning
The ICARUS Architecture
We can use a candidate architecture, ICARUS, to illustrate the idea of
mutually constraining components.
Traditional architectures were influenced by theories of human
problem solving and other mental phenomena.
In contrast, ICARUS is an architecture for physical agents that:
 supports not only cognition but also perception and action;
 always operates in the context of an external environment.
ICARUS’ emphasis on embodied agents distinguishes it from
production system architectures like ACT-R and Soar.
ICARUS’ Theoretical Constraints
ICARUS also incorporates some other strong design principles:
1. Cognitive reality of physical objects
2. Cognitive separation of categories and skills
3. Hierarchical organization of long-term memory
4. Correspondence of long-term/short-term structures
5. Modulation of symbolic structures with utility functions
6. Primacy of categorization and execution over problem solving
These constraints influence the nature of ICARUS agents and the
manner in which one constructs them.
Overview of the ICARUS Architecture*
Perceptual
Buffer
Long-Term
Conceptual
Memory
Long-Term
Skill Memory
Categorization
and Inference
Short-Term
Conceptual
Memory
Perception
Skill
Retrieval
Environment
Short-Term
Skill Memory
Skill
Execution
Motor
Buffer
* without learning
Organization of Long-Term Memory
ICARUS organizes both concepts and skills in a hierarchical manner.
concepts
Each concept is defined in terms of other concepts and/or percepts.
skills
Each skill is defined in terms of other skills, concepts, and percepts.
Organization of Long-Term Memory
ICARUS interleaves its long-term memories for concepts and skills.
concepts
skills
For example, the skill highlighted here refers directly to
the highlighted concepts.
An In-City Driving Environment
The ICARUS Language: Driving Concepts
(in-segment (?self ?sg)
:percepts ((self ?self segment ?sg) (segment ?sg)))
(aligned-with-lane (?self ?lane)
:percepts ((self ?self) (lane-line ?lane angle ?angle))
:positives ((in-lane ?self ?lane))
:tests
((> ?angle -0.05) (< ?angle 0.05)) )
(on-street (?self ?packet)
:percepts ((self ?self) (packet ?packet street ?street)
(segment ?sg street ?street))
:positives ((not-delivered ?packet) (current-segment ?self ?sg))
:value
80 )
(increasing-direction (?self)
:percepts ((self ?self))
:positives ((increasing ?b1 ?b2))
:negatives ((decreasing ?b3 ?b4)) )
The ICARUS Language: Driving Skills
(turn-around-on-street (?self ?packet)
:percepts ((self ?self segment ?segment direction ?dir)
(building ?landmark))
:start
((on-street-wrong-direction ?packet))
:effects
((on-street-right-direction ?packet))
:ordered
((get-in-U-turn-lane ?self) (prepare-for-U-turn ?self)
(steer-for-U-turn ?self ?landmark)) )
(get-aligned-in-segment (?self ?sg)
:percepts ((lane-line ?lane angle ?angle))
:requires ((in-lane ?self ?lane))
:effects
((aligned-with-lane ?self ?lane))
:actions
((steer (times ?angle 2))) )
(steer-for-right-turn (?self ?int ?endsg)
:percepts ((self ?self speed ?speed) (intersection ?int cross ?cross)
(segment ?endsg street ?cross angle ?angle))
:start
((ready-for-right-turn ?self ?int))
:effects
((in-segment ?self ?endsg))
:actions
((times steer 2)) )
The ICARUS Control Cycle
On each successive execution cycle, the ICARUS architecture:
1. places descriptions of sensed objects in the perceptual buffer;
2. infers instances of concepts implied by the current situation;
3. finds paths through the skill hierarchy from top-level intentions;
4. selects one or more applicable skill paths for execution;
5. invokes the actions associated with each selected path.
Thus, ICARUS is an example of what Nilsson (2003) refers to as
a “three-tower architecture”.
Basic ICARUS Processes
ICARUS matches patterns to recognize concepts and select skills.
concepts
Concepts are matched bottom up, starting from percepts.
skills
Skill paths are matched top down, starting from intentions.
Perceptual Buffer from Driving Domain
(self me speed 24.0 wheel-angle 0.02 limit 25.0 road-angle 0.06)
(segment g1059 street 2 dist -5.0 latdist 15.0)
(segment g1050 street A dist -45.0 latdist nil)
(segment g1049 street A dist oor latdist nil)
(lane-line g1073 length 100.0 width 0.5 dist 35.0 angle 1.57 color white)
(lane-line g1074 length 100.0 width 0.5 dist 15.0 angle 1.57 color white)
(lane-line g1072 length 100.0 width 0.5 dist 25.0 angle 1.57 color yellow)
(lane-line g1100 length 100.0 width 0.5 dist -15.0 angle 0.0 color white)
(lane-line g1101 length 100.0 width 0.5 dist 5.0 angle 0.0 color white)
(lane-line g1099 length 100.0 width 0.5 dist -5.0 angle 0.0 color yellow)
(lane-line g1104 length 100.0 width 0.5 dist 5.0 angle 0.0 color white)
(intersection g1021 street A cross 2 dist -5.0 latdist nil)
(building g943 address 246 c1dist 43.69 c1angle -0.73 c2dist nil c2angle nil)
(building g941 address 246 c1dist 30.10 c1angle -1.30 c2dist 43.70 c2angle -0.73)
(building g939 address 197 c1dist 30.10 c1angle -1.30 c2dist 33.40 c2angle -2.10)
(building g943 address 172 c1dist 33.40 c1angle -2.09 c2dist 50.39 c2angle -2.53)
(sidewalk g975 dist 15.0 angle 0.0)
(sidewalk g978 dist 5.0 angle 1.57)
Short-Term Memory from Driving Domain
(buildings-on-right me g2231 g2230 g2480)
(buildings-on-right me g2231 g2222 g2480)
(buildings-on-right me g2231 g2211 g2480)
(buildings-on-right me g2230 g2222 g2480)
(buildings-on-right me g2230 g2211 g2480)
(buildings-on-right me g2222 g2211 g2480)
(buildings-on-left me g2366 g2480)
(buildings-on-left me g2370 g2480)
(not-on-street me g2980)
(not-approaching-cross-street me g2980)
(current-street me A)
(not-delivered g2980)
(in-leftmost-lane me g2533)
(fast-for-right-turn me)
(driving-in-segment me g2480 g2533)
(steering-wheel-straight me)
(aligned-with-lane me g2533)
(on-right-side-of-road me)
(increasing me g2231 g2230 g2480)
(increasing me g2231 g2222 g2480)
(increasing me g2231 g2211 g2480)
(increasing me g2230 g2222 g2480)
(increasing me g2230 g2211 g2480)
(increasing me g2222 g2211 g2480)
(buildings-on-left me g2368 g2480)
(buildings-on-left me g2372 g2480)
(currrent-building me g2222)
(not-on-cross-street me g2980)
(current-segment me g2480)
(in-U-turn-lane me g2533)
(lane-to-right me g2533)
(fast-for-U-turn me)
(at-speed-for-cruise me)
(centered-in-lane me g2533)
(in-lane me g2533)
(in-segment me g2480)
Basic ICARUS Architecture
perception
short-term
beliefs and goals
long-term memory
structures
action
reasoning
The Challenge of Hierarchy Learning
ICARUS’ commitment to hierarchical organization raises a serious
question about the origin of its structures.
We want mechanisms which acquire these structures in ways that:
 are consistent with knowledge of human behavior;
 operate in an incremental and cumulative manner;
 satisfy constraints imposed by other ICARUS components.
This requires some source of experience from which to create
hierarchical structures.
An Approach to Hierarchy Learning
We have extended ICARUS to incorporate a module for means-ends
problem solving that:
 decomposes complex problems into subproblems;
 relies on heuristic search to find useful decompositions.
When ICARUS cannot execute a skill because its start condition is
unmet, this mechanism:
 chains backward off skills that would achieve the condition; or
 chains backward off definitions of the unsatisfied concept.
Traces of successful problem solving serve as the basis for new
hierarchical structures.
The Extended ICARUS Architecture*
Perceptual
Buffer
Long-Term
Conceptual
Memory
Long-Term
Skill Memory
Categorization
and Inference
Means-Ends
Analysis
Short-Term
Conceptual
Memory
Perception
Skill
Retrieval
Environment
Goal/Skill
Stack
Skill
Execution
Motor
Buffer
* without learning
An Abstract Means-Ends Trace
11
10
9
8
1
7
6
3
5
4
2
Learning Skills from Means-Ends Traces
ICARUS learns four types of structures from means-ends traces:
 new skills based on backward chaining over skills;
 new skills based on backward chaining over concepts:
 skills that achieve the desired concept;
 guard skills that ensure execution in desired order;
 concepts for the start fields of newly built skills.
Each of these is based on a single solution to an impasse and may
build on skills and concepts learned previously.
Learning is fully embedded within problem solving and execution.
Learning Skills from Means-Ends Traces
11
10
9
8
1
7
A
6
3
5
4
concept chaining
2
Learning Skills from Means-Ends Traces
11
10
9
8
1
7
A
6
3
5
4
skill chaining
B
2
Learning Skills from Means-Ends Traces
concept chaining
11
10
C
9
8
1
7
A
6
3
5
4
B
2
Learning Skills from Means-Ends Traces
skill chaining
11
10
C
9
D
8
1
7
A
6
3
5
4
B
2
Learning Skills from Means-Ends Traces
E
11
10
C
9
D
8
1
7
A
6
3
5
4
concept chaining
B
2
Results from Chaining Driving Skills
In the driving domain, skill chaining produces structures like:
(s-skill-5 (?me ?packet)
:percepts
:start
:effects
:ordered
(s-skill-4 (?me ?packet)
:percepts
:start
:effects
:ordered
(s-skill-1 (?me)
:percepts
:start
:objective
:ordered
((self ?me) (packet ?packet)
((concept-1 ?me))
((delivered ?packet))
((s-skill-4 ?me ?packet) (drop-off ?me ?packet)))
((self ?me) (packet ?packet))
((current-seg ?me ?sg) (street-4-ahead-on-A ?me))
((at-address ?me ?packet ?sg ?building))
((s-skill-3 ?me ?packet)
(continue-to-address ?me ?packet)))
((self ?me))
((street-4-ahead-on-A ?me))
((street-C-ahead-on-4 ?me))
((straight-until-4-on-A ?me) (turn-onto-4 ?me)))
More Results from Skill Chaining
In the blocks world, skill chaining can produce structures like:
(s-skill-21 (?A ?T1 ?B ?C)
:percepts
((block ?A) (table ?T1) (block ?B) (block ?C))
:start
((concept-46 ?A ?T1 ?B ?C))
:effects
((on ?B ?C))
:ordered
((s-skill-20 ?A ?T1 ?B) (stack ?B ?C))
:duration
4)
(s-skill-20 (?A ?T1 ?B)
:percepts
((block ?A) (table ?T1) (block ?B))
:start
((concept-43 ?A ?T1 ?B))
:effects
((holding ?A))
:ordered
((c-skill-22 ?A ?T1 ?B) (pickup ?B ?T1))
:duration
3)
(concept-46 (?A ?T1 ?B ?C)
:percepts
((block ?A) (table ?T1) (block ?B) (block ?C))
:positives
((concept-43 ?A ?T1 ?B) (clear ?C)) )
Extended ICARUS Architecture
planning
perception
short-term
beliefs and goals
long-term memory
structures
action
learning
reasoning
Modularity of Knowledge Elements
The notion of modules is central to software engineering, and
cognitive architectures benefit from similar ideas.
Fine-grained modularity occurs with knowledge elements (e.g.,
rules or skills), which:
 can be added and deleted easily by a developer;
 enable automated composition through problem solving;
 support learning through composition and modification.
This approach requires that knowledge elements share symbols,
but otherwise is very general.
Modularity of Architectural Components
Another form of modularity involves replacing one architectural
component with another, which:
 seems closer to the coarse-grained view common in software
engineering circles;
 occurs not through communication protocols but rather through
shared knowledge structures;
 is highly constrained due to cognitive architectures’ strong
representational assumptions.
Nevertheless, such component-level modularity is possible for
architectures in the same representational class.
Modularity in PRISM
PRISM (Langley & Neches, 1981) was an early framework that
supported this notion of component-level modularity.
(switches decay-strategy
time-decay
ordering-strategies
(strength summed-activation randomize)
selection-strategies
(select-best select-best select-one)
strengthening-function (* x 1.1)
weakening-function
( x 0.5)
discrimination-conditions (positive negative)
)
PRISM offered a functional decomposition of production system
architectures with alternative modules for each dimension.
Modularity of Task Knowledge
Another form of coarse-grained modularity, which occurs at the
knowledge level, assumes that:
 knowledge is organized into sets of elements relevant to
handling large-scale tasks;
 these modules share some structures for communicating
requests and results;
 the cognitive architecture is fixed and shared among these
distinct modules.
This form of modularity in cognitive architectures comes closest
to its intended use in software engineering.
Moreover, it supports hierarchical decomposition of knowledge
available to an intelligent system.
Evaluation of Intelligent Systems
Experimental studies of intelligent systems have lagged behind
ones for component methods because:
 they focus on more complex, multi-step behavior;
 they require more engineering to develop them;
 they rely on interaction among their components.
Together, these factors have slowed the widespread adoption of
experimental evaluation.
Repositories for Intelligent Systems
Public repositories are now common among the AI subfields,
and they offer clear advantages for research by:
 providing fast and cheap materials for experiments;
 supporting replication and standards for comparison.
However, they can also produce undesirable side effects by:
 focusing attention on a narrow class of problems;
 encouraging a ‘bake-off ’ mentality among researchers.
To support research on intelligent systems, we need testbeds
and environments designed with them in mind.
Desirable Characteristics of Testbeds
Testbeds that are designed to support research on intelligent
systems should:
 include a variety of domains to ensure generality;
 be well documented and simple for researchers to use;
 have standard formats to ease interface with systems.
However, these features are already present in many existing
repositories, and other characteristics are necessary.
Desirable Characteristics of Testbeds
In addition, testbeds for integrated intelligent systems should:
 contain not data sets but task environments
 which support agents that exist over time
 at least some of which involve physical domains
 provide an infrastructure to ease experimentation with
 external databases (e.g., geographic information systems)
 controlled capture, replay, and restart of scenarios
 methods for recording performance measures
These features will reduce greatly the cost of experimentation.
Physical vs. Simulated Environments
For domains that involve external settings, one can either a
physical or a simulated environment for evaluation.
Simulated environments have many advantages, including:
 ability to vary domain parameters and physical layout;
 ease of recording traces of behavior and cognitive state.
One can make simulated environments more realistic by:
 using simulators that support kinematics and dynamics;
 including data from real sensors in analogous locations.
This approach combines the relevance of physical testbeds
with the affordability of synthetic ones.
Some Promising Domains
A number of domains hold promise for the experimental study
of intelligent systems:
 urban search and rescue (Balakirsky & Messina, 2002);
 flying aircraft on military missions (Jones et al., 1999);
 driving a vehicle in a city (Choi et al., 2004);
 playing strategy games (Aha & Molineaux, 2004);
 general game playing (Genesereth, 2004).
Each requires the integration of cognition, perception, and
action in a complex, dynamical setting.
However, successful testbeds also require a suite of tasks that
can be used to drive research and evaluate systems.
Concluding Remarks
We need more research on integrated intelligent systems that:
 are embedded within a unified cognitive architecture;
 incorporate modules that provide mutual constraints;
 demonstrate a wide range of intelligent behavior;
 are evaluated on multiple tasks in challenging testbeds.
We must also think about ways to overcome social obstacles to
pursuing this research agenda.
End of Presentation