Transcript Computational Discovery of Communicable Knowledge

A Cognitive Architecture for
Integrated Intelligent Agents
Pat Langley
School of Computing and Informatics
Arizona State University
Tempe, Arizona
http://cll.stanford.edu/
Thanks to D. Choi, K. Cummings, N. Nejati, S. Rogers, S. Sage, and D. Shapiro for their
contributions. This talk reports research. funded by grants from DARPA IPTO and the
National Science Foundation, which are not responsible for its contents.
Claim 1: Integrated Cognitive Systems
The original goal of artificial intelligence was to design and
implement computational artifacts that:
 handled difficult tasks that require cognitive processing;
 combined many capabilities into integrated systems;
 provided insights into the nature of mind and intelligence.
Instead, modern AI has divided into many subfields that care
little about cognition, systems, or intelligence.
But the challenge remains and we need far more research on
integrated cognitive systems.
Claim 2: Psychology and Design Heuristics
To develop intelligent systems, we must constrain their design,
and findings about human behavior can suggest:
 how the system should represent and organize knowledge
 how the system should use that knowledge in performance
 how the system should acquire knowledge from experience
This approach has led to many new insights and methods, but
few modern AI researchers take advantage of it.
We need far more work that incorporates ideas from cognitive
psychology into the design of AI systems.
The Fragmentation of AI Research
language
planning
perception

reasoning
action
learning
The Domain of In-City Driving
Consider driving a vehicle
in a city, which requires:
 selecting routes
 obeying traffic lights
 avoiding collisions
 being polite to others
 finding addresses
 staying in the lane
 parking safely
 stopping for pedestrians
 following other vehicles
 delivering packages
These tasks range from
low-level execution to
high-level reasoning.
QuickTime™ and a
Cinepak decompressor
are needed to see this picture.
Newell’s Critique
In 1973, Allen Newell argued “You can’t play twenty questions
with nature and win”. Instead, he proposed that we:
 move beyond isolated phenomena and capabilities to develop
complete models of intelligent behavior;
 demonstrate our systems’ intelligence on the same range of
domains and tasks as humans can handle;
 evaluate these systems in terms of generality and flexibility
rather than success on a single class of tasks.
However, there are different paths toward achieving such systems.
A System with Communicating Modules
language
planning
perception
reasoning
action
learning
software engineering / multi-agent systems
A System with Shared Short-Term Memory
language
planning
perception
short-term
beliefs and goals
reasoning
action
learning
blackboard architectures
Integration vs. Unification
Newell’s vision for research on theories of intelligence was that:
 cognitive systems should make strong theoretical assumptions
about the nature of the mind;
 theories of intelligence 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.
A successful framework is all about mutual constraints, and it
should provide a unified theory of intelligent behavior.
He associated these aims with the idea of a cognitive architecture,
which were also to incorporate results from psychology.
A System with Shared Long-Term Memory
language
perception
planning
short-term
beliefs and goals
long-term memory
structures
action
learning
cognitive architectures
reasoning
A Constrained Cognitive Architecture
language
perception
planning
short-term
beliefs and goals
long-term memory
structures
action
learning
reasoning
The ICARUS Architecture
In this talk I will use one such framework  ICARUS  to illustrate
the advantages of cognitive architectures.
ICARUS incorporates a variety of assumptions from psychological
theories; the most basic are that:
1.
2.
3.
4.
5.
Short-term memories are distinct from long-term stores
Memories contain modular elements cast as list structures
Long-term structures are accessed through pattern matching
Cognition occurs in retrieval/selection/action cycles
Performance and learning compose elements in memory
These claims give ICARUS much in common with other cognitive
architectures like ACT-R, Soar, and Prodigy.
Cascaded Integration in ICARUS
ICARUS adopts a cascaded approach to integration in which
lower-level modules produce results for higher-level ones.
learning
problem solving
skill execution
conceptual inference
Each of these modules incorporates a variety of ideas that have
their origin in cognitive psychology.
Representing and Using Concepts
Cognitive psychology makes claims about conceptual knowledge:
 concepts are distinct cognitive entities that support both
categorization and inference;
 the majority of human concepts are grounded in perception
and action (Barsalou, 1999);
 many human concepts are relational in nature, describing
connections among entities (Kotovsky & Gentner, 1996);
 concepts are organized in a hierarchical manner, with more
complex categories defined in terms of simpler ones.
ICARUS adopts these assumptions about conceptual memory.
ICARUS Concepts for In-City Driving
((in-rightmost-lane ?self ?clane)
:percepts ((self ?self) (segment ?seg)
(line ?clane segment ?seg))
:relations ((driving-well-in-segment ?self ?seg ?clane)
(last-lane ?clane)
(not (lane-to-right ?clane ?anylane))))
((driving-well-in-segment ?self ?seg ?lane)
:percepts ((self ?self) (segment ?seg) (line ?lane segment ?seg))
:relations ((in-segment ?self ?seg) (in-lane ?self ?lane)
(aligned-with-lane-in-segment ?self ?seg ?lane)
(centered-in-lane ?self ?seg ?lane)
(steering-wheel-straight ?self)))
((in-lane ?self ?lane)
:percepts ((self ?self segment ?seg) (line ?lane segment ?seg dist ?dist))
:tests
( (> ?dist -10) (<= ?dist 0)))
Structure and Use of Conceptual Memory
ICARUS organizes conceptual memory in a hierarchical manner.
Conceptual inference occurs from the bottom up, starting from
percepts to produce high-level beliefs about the current state.
Representing Short-Term Beliefs/Goals
(current-street me A)
(lane-to-right g599 g601)
(last-lane g599)
(at-speed-for-u-turn me)
(steering-wheel-not-straight me)
(in-lane me g599)
(on-right-side-in-segment me)
(building-on-left g288)
(building-on-left g427)
(building-on-left g431)
(building-on-right g287)
(increasing-direction me)
(current-segment me g550)
(first-lane g599)
(last-lane g601)
(slow-for-right-turn me)
(centered-in-lane me g550 g599)
(in-segment me g550)
(intersection-behind g550 g522)
(building-on-left g425)
(building-on-left g429)
(building-on-left g433)
(building-on-right g279)
(buildings-on-right g287 g279)
Skills and Execution
Psychology also makes claims about skills and their execution:
 the same generic skill may be applied to distinct objects that
meet its application conditions;
 skills support the execution of complex activities that have
hierarchical organization (Rosenbaum et al., 2001);
 humans can carry out open-loop sequences, but they can also
operate in closed-loop reactive mode;
 humans can deal with multiple goals with different priorities,
which can lead to interrupted behavior.
ICARUS embodies these ideas in its skill execution module.
ICARUS Skills for In-City Driving
((in-rightmost-lane ?self ?line)
:percepts ((self ?self) (line ?line))
:start
((last-lane ?line))
:subgoals ((driving-well-in-segment ?self ?seg ?line)))
((driving-well-in-segment ?self ?seg ?line)
:percepts ((segment ?seg) (line ?line) (self ?self))
:start
((steering-wheel-straight ?self))
:subgoals ((in-segment ?self ?seg)
(centered-in-lane ?self ?seg ?line)
(aligned-with-lane-in-segment ?self ?seg ?line)
(steering-wheel-straight ?self)))
((in-segment ?self ?endsg)
:percepts ((self ?self speed ?speed) (intersection ?int cross ?cross)
(segment ?endsg street ?cross angle ?angle))
:start
((in-intersection-for-right-turn ?self ?int))
:actions ((steer 1)))
ICARUS Skills Build on Concepts
ICARUS stores skills in a hierarchical manner that links to concepts.
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.
Skill Execution in ICARUS
Skill execution occurs from the top down, starting from goals
to find applicable paths through the skill hierarchy.
This process repeats on each cycle to give teleoreactive control
(Nilsson, 1994) with a bias toward persistence of initiated skills.
Ideas about Problem Solving and Learning
Psychology also has ideas about problem solving and learning:
 humans often resort to means-ends analysis to solve novel
problems (Newell & Simon, 1961);
 problem solving often occurs in a physical context and is
interleaved with execution (Gunzelman & Anderson, 2003);
 efforts to overcome impasses during problem solving leads to
incremental acquisition of new skills (Anzai & Simon, 1979);
 structural learning involves monotonic addition of symbolic
elements to long-term memory;
 learning can transform backward-chaining heuristic search into
informed forward-chaining execution (Larkin et al., 1980).
ICARUS reflects these ideas in its problem solving and learning.
ICARUS Interleaves Execution and Problem Solving
Skill Hierarchy
Problem
Reactive
Execution
?
no
impasse?
Primitive Skills
yes
Executed plan
Problem
Solving
This organization reflects the psychological distinction between automatized
and controlled behavior.
A Successful Problem-Solving Trace
initial state
(clear C)
(hand-empty)
(unst. C B)
(unstack C B)
(clear B)
(on C B)
goal
(unst. B A)
(ontable A T)
(holding C)
(putdown C T)
(clear A)
(unstack B A)
(hand-empty)
(on B A)
(holding B)
C
B
B
A
A
C
ICARUS Learns Skills from Problem Solving
Skill Hierarchy
Problem
Reactive
Execution
?
no
impasse?
Primitive Skills
yes
Problem
Solving
Skill
Learning
Executed plan
Constructing Skills from a Trace
(clear C)
skill chaining
1
(hand-empty)
(unst. C B)
(unstack C B)
(clear B)
(on C B)
(unst. B A)
(ontable A T)
(holding C)
(putdown C T)
(clear A)
(unstack B A)
(hand-empty)
(on B A)
(holding B)
C
B
B
A
A
C
Constructing Skills from a Trace
(clear C)
1
(hand-empty)
(unst. C B)
(unstack C B)
(clear B)
(on C B)
(unst. B A)
(clear A)
(unstack B A)
skill chaining
2
(ontable A T)
(holding C)
(putdown C T)
(hand-empty)
(on B A)
(holding B)
C
B
B
A
A
C
Constructing Skills from a Trace
concept chaining
(clear C)
3
1
(hand-empty)
(unst. C B)
(unstack C B)
(clear B)
(on C B)
(unst. B A)
(clear A)
(unstack B A)
2
(ontable A T)
(holding C)
(putdown C T)
(hand-empty)
(on B A)
(holding B)
C
B
B
A
A
C
Constructing Skills from a Trace
skill chaining
(clear C)
1
(hand-empty)
(unst. C B)
(unstack C B)
4
3
(clear B)
(on C B)
(unst. B A)
(clear A)
(unstack B A)
2
(ontable A T)
(holding C)
(putdown C T)
(hand-empty)
(on B A)
(holding B)
C
B
B
A
A
C
Learned Skills in the Blocks World
(clear (?C)
:percepts ((block ?D) (block ?C))
:start
((unstackable ?D ?C))
:skills
((unstack ?D ?C)))
(clear (?B)
:percepts ((block ?C) (block ?B))
:start
((on ?C ?B) (hand-empty))
:skills
((unstackable ?C ?B) (unstack ?C ?B)))
(unstackable (?C ?B)
:percepts ((block ?B) (block ?C))
:start
((on ?C ?B) (hand-empty))
:skills
((clear ?C) (hand-empty)))
(hand-empty ( )
:percepts ((block ?D) (table ?T1))
:start
((putdownable ?D ?T1))
:skills
((putdown ?D ?T1)))
Hierarchical skills are
generalized traces of
successful means-ends
problem solving
Cumulative Curves for Blocks World
Cumulative Curves for FreeCell
Learning Skills for In-City Driving
We have also trained
ICARUS to drive in our
in-city environment.
We provide the system
with tasks of increasing
complexity.
Learning transforms the
problem-solving traces
into hierarchical skills.
The agent uses these
skills to change lanes,
turn, and park using
only reactive control.
QuickTime™ and a
Cinepak decompressor
are needed to see this picture.
Skill Clauses Learning for In-City Driving
((parked ?me ?g1152)
:percepts ( (lane-line ?g1152) (self ?me))
:start
( )
:subgoals ( (in-rightmost-lane ?me ?g1152)
(stopped ?me)) )
((in-rightmost-lane ?me ?g1152)
:percepts ( (self ?me) (lane-line ?g1152))
:start
( (last-lane ?g1152))
:subgoals ( (driving-well-in-segment ?me ?g1101 ?g1152)) )
((driving-well-in-segment ?me ?g1101 ?g1152)
:percepts ( (lane-line ?g1152) (segment ?g1101) (self ?me))
:start
( (steering-wheel-straight ?me))
:subgoals ( (in-lane ?me ?g1152)
(centered-in-lane ?me ?g1101 ?g1152)
(aligned-with-lane-in-segment ?me ?g1101 ?g1152)
(steering-wheel-straight ?me)) )
Learning Curves for In-City Driving
Transfer of Skills in ICARUS
The architecture also supports the transfer of knowledge in that:
 skills acquired later can build on those learned earlier;
 skill clauses are indexed by the goals they achieve;
 conceptual inference supports mapping across domains.
We are exploring such effects in ICARUS as part of a DARPA
program on the transfer of learned knowledge.
Testbeds include first-person shooter games, board games, and
physics problem solving.
Transfer Effects in FreeCell
On tasks with more cards, prior training aids solution probability.
Transfer Effects in FreeCell
However, it also lets the system solve problems with less effort.
Architectures as Programming Languages
Cognitive architectures come with a programming language that:
 includes a syntax linked to its representational assumptions
 inputs long-term knowledge and initial short-term elements
 provides an interpreter that runs the specified program
 incorporates tracing facilities to inspect system behavior
Such programming languages ease construction and debugging
of knowledge-based systems.
For this reason, cognitive architectures support far more efficient
development of software for intelligent systems.
Programming in ICARUS
The programming language associated with ICARUS comes with:
 a syntax for concepts, skills, beliefs, and percepts
 the ability to load and parse such programs
 an interpreter for inference, execution, planning, and learning
 a trace package that displays system behavior over time
We have used this language to develop adaptive intelligent
agents in a variety of domains.
An ICARUS Agent for Urban Combat
QuickTime™ and a
Cinepak decompressor
are needed to see this picture.
ICARUS’ Memories and Processes
Perceptual
Buffer
Long-Term
Conceptual
Memory
Long-Term
Skill Memory
Conceptual
Inference
Problem Solving
Skill Learning
Short-Term
Belief
Memory
Perception
Skill Retrieval
and Selection
Environment
Short-Term
Goal Memory
Skill
Execution
Motor
Buffer
Similarities to Previous Architectures
ICARUS has much in common with other cognitive architectures
like Soar (Laird et al., 1987) and ACT-R (Anderson, 1993):
1. Short-term memories are distinct from long-term stores
2. Memories contain modular elements cast as symbolic structures
3. Long-term structures are accessed through pattern matching
4. Cognition occurs in retrieval/selection/action cycles
5. Learning involves monotonic addition of elements to memory
6. Learning is incremental and interleaved with performance
These ideas all have their origin in theories of human memory,
problem solving, and skill acquisition.
Distinctive Features of ICARUS
However, ICARUS also makes assumptions that distinguish it from
these architectures:
1. Cognition is grounded in perception and action
2. Categories and skills are separate cognitive entities
3. Short-term elements are instances of long-term structures
4. Inference and execution are more basic than problem solving
5. Skill/concept hierarchies are learned in a cumulative manner
Some of these assumptions appear in Bonasso et al.’s (2003) 3T,
Freed’s APEX, and Sun et al.’s (2001) CLARION architectures.
Directions for Future Research
Future work on ICARUS should incorporate other ideas about:
 progressive deepening in forward-chaining search
 graded nature of categories and category learning
 model-based character of human reasoning
 persistent but limited nature of short-term memories
 creating perceptual chunks to reduce these limitations
 storing and retrieving episodic memory traces
These additions will increase further ICARUS’ debt to psychology.
Concluding Remarks
We need more research on integrated intelligent systems that:
 are embedded within a unified cognitive architecture;
 incorporate constraints based on ideas from psychology;
 demonstrate a wide range of intelligent behavior;
 are evaluated on multiple tasks in challenging testbeds.
For more information about the ICARUS architecture, see:
http://cll.stanford.edu/research/ongoing/icarus/
End of Presentation
ICARUS’ Inference-Execution 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 goals;
4. selects one or more applicable skill paths for execution;
5. invokes the actions associated with each selected path.
ICARUS agents are teleoreactive (Nilsson, 1994) in that they are
executed reactively but in a goal-directed manner.
ICARUS’ Constraints on Skill Learning
 What determines the hierarchical structure of skill memory?
 The structure emerges the subproblems that arise during
problem solving, which, because operator conditions and
goals are single literals, form a semilattice.
 What determines the heads of the learned clauses/methods?
 The head of a learned clause is the goal literal that the
planner achieved for the subproblem that produced it.
 What are the conditions on the learned clauses/methods?
 If the subproblem involved skill chaining, they are the
conditions of the first subskill clause.
 If the subproblem involved concept chaining, they are the
subconcepts that held at the subproblem’s outset.
Cumulative Curves for Blocks World