Transcript Computational Discovery of Communicable Knowledge

Cognitive Architectures:
Psychological Constraints as Effective
Heuristics for Designing Intelligent Systems
Pat Langley
Computational Learning Laboratory
Center for the Study of Language and Information
Stanford University, Stanford, California USA
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.
Newell’s Claim
In 1973, Allen Newell argued “You can’t play twenty questions
with nature and win”. Instead, he proposed that we:
 view cognitive psychology and artificial intelligence as close
allies with distinct but related goals;
 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.
Newell was criticizing experimental psychology and looked to AI,
with its systems perspective, for the solution.
The Fragmentation of AI Research
Unfortunately, AI
has changed …
language
planning
perception

reasoning
action
learning
…and is not taking us
toward human-level
intelligent systems.
Psychological Constraints as 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.
Today, the most interesting research on intelligent systems uses
psychological ideas as heuristics in this manner.
This approach has led to many new insights, and we need more
work in this tradition.
One Approach to Intelligent Systems
language
planning
perception
reasoning
action
learning
software engineering / multi-agent systems
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.
Another Approach to Intelligent Systems
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 influence of psychology on 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.
Architectural Commitment to Memories
A cognitive architecture makes a specific commitment to:
 long-term memories that store knowledge and procedures;
 short-term memories that store beliefs and goals;
 sensori-motor memories that hold percepts and actions.
For each memory, a cognitive architecture also commits to:
 the representation of content in that memory;
 the organization of structures within the memory;
 the connections among structures across memories.
These memories correspond to ones postulated in psychology.
ICARUS’ Memories
Perceptual
Buffer
Long-Term
Conceptual
Memory
Short-Term
Belief Memory
Environment
Long-Term
Skill Memory
Short-Term
Goal Memory
Motor
Buffer
Ideas about Representation
Cognitive psychology makes important representational claims:
 concepts and skills encode different aspects of knowledge
that are stored as distinct cognitive structures;
 cognition occurs in a physical context, with concepts and
skills being grounded in perception and action;
 many mental structures are relational in nature, in that they
describe connections or interactions among objects;
 long-term memories have hierarchical organizations that
define complex structures in terms of simpler ones;
 each element in a short-term memory is an active version of
some structure in long-term memory.
ICARUS adopts these assumptions about the contents of memory.
Representing Long-Term Structures
ICARUS encodes two forms of general long-term knowledge:
 Conceptual clauses: A set of relational inference rules with
perceived objects or defined concepts in their antecedents;
 Skill clauses: A set of executable skills that specify:
 a head that indicates a goal the skill achieves;
 a single (typically defined) precondition;
 a set of ordered subgoals or actions for achieving the goal.
These define a specialized class of hierarchical task networks in
which each task corresponds to a goal concept.
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)))
((in-segment ?self ?seg)
:percepts ((self ?self segment ?seg) (segment ?seg)))
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)))
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)
Encoding Perceived Objects
(self me speed 5 angle-of-road -0.5 steering-wheel-angle -0.1)
(segment g562 street 1 dist -5.0 latdist 15.0)
(line g564 length 100.0 width 0.5 dist 35.0 angle 1.1 color white segment g562)
(line g565 length 100.0 width 0.5 dist 15.0 angle 1.1 color white segment g562)
(line g563 length 100.0 width 0.5 dist 25.0 angle 1.1 color yellow segment g562)
(segment g550 street A dist oor latdist nil)
(line g600 length 100.0 width 0.5 dist -15.0 angle -0.5 color white segment g550)
(line g601 length 100.0 width 0.5 dist 5.0 angle -0.5 color white segment g550)
(line g599 length 100.0 width 0.5 dist -5.0 angle -0.5 color yellow segment g550)
(intersection g522 street A cross 1 dist -5.0 latdist nil)
(building g431 address 99 street A c1dist 38.2 c1angle -1.4 c2dist 57.4 c2angle -1.0)
(building g425 address 25 street A c1dist 37.8 c1angle -2.8 c2dist 56.9 c2angle -3.1)
(building g389 address 49 street 1 c1dist 49.2 c1angle 2.7 c2dist 53.0 c2angle 2.2)
(sidewalk g471 dist 15.0 angle -0.5)
(sidewalk g474 dist 5.0 angle 1.07)
(sidewalk g469 dist -25.0 angle -0.5)
(sidewalk g470 dist 45.0 angle 1.07)
(stoplight g538 vcolor green hcolor red))
Hierarchical Structure 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.
Hierarchical Structure 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.
Architectural Commitment to Processes
In addition, a cognitive architecture makes commitments about:
 performance processes for:
 retrieval, matching, and selection
 inference and problem solving
 perception and motor control
 learning processes that:
 generate new long-term knowledge structures
 refine and modulate existing structures
In most cognitive architectures, performance and learning are
tightly intertwined, again reflecting influence from psychology.
Ideas about Performance
Cognitive psychology makes clear claims about performance:
 humans can handle multiple goals with different priorities,
which can interrupt tasks to which attention returns later;
 conceptual inference, which typically occurs rapidly and
unconsciously, is more basic than problem solving;
 humans often resort to means-ends analysis to solve novel,
unfamiliar problems;
 mental problem solving requires greater cognitive resources
than execution of automatized skills;
 problem solving often occurs in a physical context, with
mental processing being interleaved with execution.
ICARUS embodies these ideas in its performance mechanisms.
ICARUS’ Functional 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
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.
This framework is very similar to the recognize-act cycle used in
production systems, which in turn borrowed from S-R theories.
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.
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.
Interleaving Reactive Control and Problem Solving
Solve(G)
Push the goal literal G onto the empty goal stack GS.
On each cycle,
If the top goal G of the goal stack GS is satisfied,
Then pop GS.
Else if the goal stack GS does not exceed the depth limit,
Let S be the skill instances whose heads unify with G.
If any applicable skill paths start from an instance in S,
Then select one of these paths and execute it.
Else let M be the set of primitive skill instances that have not already failed in which G is an effect.
If the set M is nonempty,
Then select a skill instance Q from M.
Push the start condition C of Q onto goal stack GS.
Else if G is a complex concept with the unsatisfied subconcepts H and with satisfied subconcepts F,
Then if there is a subconcept I in H that has not yet failed,
Then push I onto the goal stack GS.
Else pop G from the goal stack GS and store information about failure with G's parent.
Else pop G from the goal stack GS.
Store information about failure with G's parent.
This is traditional means-ends analysis, with three exceptions: (1) conjunctive
goals must be defined concepts; (2) chaining occurs over both skills/operators
and concepts/axioms; and (3) selected skills are executed whenever applicable.
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
Claims about Learning
Cognitive psychology has also developed ideas about learning:
 efforts to overcome impasses during problem solving can lead
to the acquisition of new skills;
 learning can transform backward-chaining heuristic search
into more informed forward-chaining behavior;
 learning is incremental and interleaved with performance;
 structural learning involves monotonic addition of symbolic
elements to long-term memory;
 transfer to new tasks depends on the amount of structure
shared with previously mastered tasks.
ICARUS incorporates these assumptions into its basic operation.
ICARUS Learns Skills from Problem Solving
Skill Hierarchy
Problem
Reactive
Execution
?
no
impasse?
Primitive Skills
yes
Problem
Solving
Skill
Learning
Executed plan
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.
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 Two Domains
Blocks World
FreeCell
Constraints from cognitive psychology can produce very effective
approaches to speedup learning.
Learning Skills for In-City Driving
We have trained ICARUS
to drive in a simulated
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.
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.
Experimental studies suggest that these lead to effective transfer.
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.
Thus, ideas from psychology can support 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
Intellectual Precursors
ICARUS’ design has been influenced by earlier research on:
 characteristics of human memory
 human problem solving
 logical reasoning and inference
 acquisition of cognitive skills
 cognitive architectures (especially ACT, Soar, and Prodigy)
We can debate whether ICARUS provides an adequate theory of
human behavior, but not its debt to cognitive psychology.
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 retreiving episodic memory traces.
These additions will increase further ICARUS’ debt to psychology.
Contributions of ICARUS
ICARUS is a cognitive architecture for physical agents that:
 includes separate memories for concepts and skills;
 organizes both memories in a hierarchical fashion;
 modulates reactive execution with goal seeking;
 augments routine behavior with problem solving; and
 learns hierarchical skills in a cumulative manner.
These ideas have their roots in cognitive psychology, but they
are also effective in building flexible intelligent agents.
For more information about the ICARUS architecture, see:
http://cll.stanford.edu/research/ongoing/icarus/
End of Presentation