Artificial Intelligence 169 (2005) 104–141
Field review
www.elsevier.com/locate/artint
Metacognition in computation: A selected research review
Michael T. Cox
BBN Technologies, 10 Moulton St., Cambridge, MA 02138, USA
Available online 15 November 2005
Abstract
Various disciplines have examined the many phenomena of metacognition and have produced numerous results, both positive and negative. I discuss some of these aspects of cognition about cognition and the results concerning them from the point of view of the psychologist and the com- puter scientist, and I attempt to place them in the context of computational theories. I examine metacognition with respect to both problem solving (e.g., planning) and to comprehension (e.g., story understanding) processes of cognition.
2005 Published by Elsevier B.V.
Keywords: Cognitive monitoring; Computational introspection; Limited rationality; Metacognition;
Meta-explanation; Metaknowledge; Meta-level architecture; Metareasoning; Self-reference; Reflection
Contents
1. Introduction …………………………………………….105
2. Psychology,metacognition,andhumanbehavior………………………. 107
2.1. Cognitionandmetacognition ……………………………… 108
2.2. Problemsolvingandmetacognition………………………….. 109
2.3. Computationalmodels …………………………………. 111
2.4. Caveats and the relation of psychological research to computational research . . . . 112
3. Artificialintelligence,metareasoning,andintrospection . . . . . . . . . . . . . . . . . . . . . . . 114
3.1. Logicandbeliefintrospection …………………………….. 116
E-mail address: mcox@bbn.com (M.T. Cox).
0004-3702/$ – see front matter 2005 Published by Elsevier B.V. doi:10.1016/j.artint.2005.10.009
M.T. Cox / Artificial Intelligence 169 (2005) 104–141 105
3.2. Knowledge-basedsystems,metareasoning,andcontrol . . . . . . . . . . . . . . . . . . 118
3.3. Limitedrationality ……………………………………. 120
3.4. Model-based reasoning, case-based reasoning and introspective learning . . . . . . 122
4. Trendsincurrentresearch ……………………………………. 126
5. Summaryanddiscussion……………………………………..129
Acknowledgements . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 131 References . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 132
1. Introduction
Any intelligent agent with a choice between what to do in the world actually has three very different choices. First it must decide which of several actions to perform is best in its current situation. For example it might decide that spending its lunch money on a new watch offered by a stranger in the parking lot is a good bargain. But secondly it also must decide whether it has thought enough about the decision that the choice is sufficiently informed to warrant commitment to action or whether more thought is in order. That is it must think about its own thinking. Furthermore given that it chooses to save the money for a rainy day and exercise at lunch to drop a few pounds instead, the agent has a third kind of choice when it considers the reasons that led to poor judgement and being mugged by the watch thief. That is, it must decide what went wrong and why in its reasoning process through a bit of introspection and self-criticism. This paper examines the research involved with the latter two types of reasoning. We discuss not only the literature in the computer sciences, but we also review a select portion of the metacognition literature in psychology with the goal of better understanding the computational issues.
In its most basic form, the algorithm-selection problem [197] in computer science repre- sents a classical metacognition task. In such situations the input to a program is a particular problem and a set of algorithms that can compute solutions to that class of problems. The task is to choose the algorithm that will run in the least amount of time. Decisions can be based on not just characteristics of the input problem, but a good choice involves knowl- edge about algorithm performance. Lagoudakis, Littman, and Parr [129,130] illustrate this task with simple sorting problems. Three choices are quick sort, insertion sort, and merge sort. They show that the decision can be formulated as a Markov decision process (MDP) where the state is the size of the input problem, the actions that cause state transitions are the algorithms, and the objective function is estimated by an empirically gathered profile of times it took to perform the sort on past problems. Note that because two of the three algorithms are recursive, the algorithm selection task is repeatedly performed over prob- lems of many sizes during a typical sort. Now using this statistical model of reasoning (where reasoning is sorting in this case), a system can rationally choose the best reasoning process to maximize its utility (here, run-time). The combined solution outperforms any of the individual algorithms.
The distinctions in the metacognition literature are often very subtle, however, and the line between reasoning and metareasoning is sometimes less clear than with sorting. Con- sider a story understanding task. Fig. 1 shows that a story is composed of characters and
106 M.T. Cox / Artificial Intelligence 169 (2005) 104–141
Fig. 1. Metacognition entails two levels of reasoning and representation but three sets of states and events (dashed arrows indicate what is being represented).
events that change these characters and the world in which the story takes place. To under- stand the story requires that some intelligent system reason about the events and states and why characters choose to perform the particular actions the events represent. Such NLP systems will have a representation of the story and will perform certain computations that alter the representations until a satisfactory interpretation of the story is achieved. Like the states and events in the story’s domain, this NLP domain (shown in the central part of Fig. 1) has mental states (e.g., story interpretations) and mental events (e.g., schema retrieval). Now if these mental states and events are themselves represented in a third do- main, they too can be reasoned about as was the story itself. The resulting introspection is therefore reasoning about the NLP reasoning task and hence is a second-order reasoning process called metareasoning or more generally metacognition.
The metacognitive task may be to explain errors in the cognitive task or it may be to select between cognitive “algorithms” to perform the reasoning. In either case, confusion arises when the various levels, processing or representations are conceptually intermixed or left implicit. One of the goals of this article is to examine some of the various research programs related to metacognition in computation and separate these various aspects for the reader.
The 21st century is experiencing an interest in computational models of higher order reasoning analogous to the kinds of metacognitive activity exhibited by humans. In addi- tion to the recent 2005 AAAI Spring Symposium on Metacognition in Computation [5], the AI community has conducted several similar workshops including the AISB 2000 sym- posium on How to Design a Functioning Mind, April, 2000 [58]; the St. Thomas Common Sense Symposium: Designing Architectures for Human-Level Intelligence, April, 2002 [163]; the DARPA Workshop on Self-Aware Computer Systems, April, 2004 [149]; the NDIST Workshop on Self-Reconfiguring Software Systems, December, 2004; and the LEMORE05 Workshop: Learner Modelling for Reflection to Support Learner Control, Metacognition and Improved Communication between Teachers and Learners held at the 12th International Conference on Artificial Intelligence in Education in Amsterdam. The excitement associated with these developments can especially be seen in [22]. However, many of the foundations for this work were formulated at the beginning of artificial intel- ligence and in some cases earlier.
M.T. Cox / Artificial Intelligence 169 (2005) 104–141 107
Metacognition research encompasses studies regarding reasoning about one’s own thinking, memory and the executive processes that presumably control strategy selection and processing allocation. Metacognition differs from standard cognition in that the self is the referent of the processing or the knowledge [233]. In most interpretations (e.g., [108,126]), meta-X can be translated to “X about X:” Thus metaknowledge is knowledge about knowledge, and metacognition is cognition about cognition. But often metaknowl- edge and metamemory (memory about one’s own memory) are included in the study of metacognition, because they are important in self-monitoring and other metacognitive processes. Thus in much of the literature, the term metacognition is broadly construed to apply to all self-reflective facets of cognition.
Artificial intelligence certainly does not have a monopoly of interest concerning metacognition. Philosophers and observers of the human condition have been fascinated by the subject for a very long time. Around the turn of the 16th century in De Trinitate, Augustine [10] asks “What then can be the purport of the injunction, know thyself? I sup- pose it is that the mind should reflect upon itself”.1 Mathematicians and philosophers have realized since at least the time of Socrates the problems associated with self-referential sentences such as the liar’s paradox represented by the statement “This sentence is false.” ([76]; see [183] for a treatment of some of these metalanguage problems.)
More recently, Hofstadter [110] convincingly argues that the concept of reflection, or an object turning in upon itself (i.e., his concept of “Strange Loops”), is a common and powerful theme, in and outside of science. Strange Loops can be found in mathematics with the proofs of Gödel, in art with the painting of Escher, and in music with the com- positions of Bach. But with few exceptions (e.g., [136,185]), AI and cognitive psychology present the most thorough mechanistic explanations for such phenomena. Many of the roots of metacognition in computation are influenced by the large body of work in cogni- tive, developmental, and social psychology, cognitive aging research, and the educational and learning sciences. This paper examines a selection of these research areas as well as those in computer science.2 Initially I limit this history to the 20th century, starting first with the formative metacognition research in the human psychology literature and then with related research in computer science. Research in the 21st century is summarized toward the end of this paper.
2. Psychology, metacognition, and human behavior
The psychological literature on metacognition and metamemory3 provides a wide array of influences that bear on metacognition in computation. Here I examine specific studies that emphasize cognitive self-monitoring, the importance of explicit representation, higher- order problem-solving, the function of understanding one’s own memory system, and data
1 Cited in Lyons [136, p. 1].
2 I deliberately exclude cognitive neuroscience research from this review. I also do not address the considerable
body of research on consciousness. But see the selected bibliography on consciousness in philosophy, cognitive science and neuroscience [156] and also Chalmers’ online bibliography at consc.net/biblio.html.
3 I also will not discuss the extensive literature on metamemory here. For a general review see [74] or [153].
108 M.T. Cox / Artificial Intelligence 169 (2005) 104–141
demonstrating a person’s ability to assess (or not) the veracity of their own responses and learning. I end this section on a note of caution with some caveats.
2.1. Cognition and metacognition
Since Flavell’s [80] coining of the term metamemory, and especially since the seminal metacognition research of Flavell and Wellman [82], many have investigated the phenom- enon surrounding cognition about cognition.4 Of all research on the modern-day concept of metacognition, the child development literature (i.e., how cognitive function develops during childhood) has perhaps the longest history (see, for example, [237]). Moreover, developmental psychology has reported the most positive evidence for the importance of metacognitive strategies and monitoring (see [208,233]). Researchers interested in learning disabilities have studied the metacognitive components of such pathologies. For example, Part II: Macrolevel Cognitive Aspects of Learning Disabilities [29] contains a number of papers relevant to this class of investigations. Research examining the relationship be- tween metacognitive skills and educational instruction have made significant progress. For example, Forrest-Pressley, MacKinnon, and Waller [84] and Garner [92] report successful instruction procedures related to both problem solving and reading comprehension (see also [193], for a related discussion from computer/cognitive science). Most of these works concentrate on applications relevant to teaching in general school environments, although some address specific instruction of the learning disabled. Finally, the social psychology and philosophical communities have all taken considerable interest in individuals’ beliefs about their own beliefs and beliefs about others’ beliefs (e.g., [8,155,185,186]).5
Wellman [233–235] views human metacognition, not as a unitary phenomenon, but rather as a multifaceted theory of mind. Metacognition involves several separate but re- lated cognitive processes and knowledge structures that share as a common theme the self as referent. Such a theory of mind emerges during childhood from of an awareness of the differences between internal and external worlds, that is, from the perception that there exist both mental states and events that are quite discriminable from external states and events. This theory encompasses a number of knowledge classes considered by Wellman to be psychological variables: person variables that deal with the individual and others (for example, cognitive psychologists can recall many facts about cognition, whereas most people cannot), task variables, which concern the type of mental activity (for example, it is more difficult to remember nonsense words than familiar words), and strategy variables that relate to alternative approaches to a mental task (e.g., to remember a list it helps to re- hearse). Finally, Wellman’s theory includes a self-monitoring component, whereby people evaluate their levels of comprehension and mental performance with respect to the theory and the norms the theory predicts.
Nelson and Narens [172] present a general information-processing framework for inte- grating and better understanding metacognition and metamemory. This framework is illus-
4 Brown [24] notes that the relationship between text comprehension and metacognitive activities has been studied since the turn of the century, but under the guise of other technical terms.
5 Pollock in particular [186] distinguishes between knowledge about the facts that one knows and knowledge about one’s motivations, beliefs and processes.
M.T. Cox / Artificial Intelligence 169 (2005) 104–141 109
Fig. 2. Metacognitive monitoring and control of cognition.
trated in Fig. 2. Behind it lie three basic principles: (1) Cognitive processes are split into an object-level (cognition) and a meta-level (metacognition); (2) The meta-level contains a dynamic model of the object-level; and (3) A flow of information from the object-level to the meta-level is considered monitoring, whereas information flowing from the meta- level to the object-level is considered control. Monitoring informs the meta-level about the state of the object-level and thus allows the meta-level’s model of the object level to be updated. Then depending upon the state of this model, control can initiate, maintain, or terminate object-level behavior. Object-level behavior consists of cognitive activities such as problem solving or memory retrieval.
Nelson and Narens address knowledge acquisition (encoding), retention, and retrieval in both monitoring and control directions of information flow during memory tasks. Mon- itoring processes include ease-of-learning judgements, judgements of learning (JOLs), feelings of knowing (FOKs) and confidence in retrieved answers. Control processes include selection of the kind of processes, allocation of study time, termination of study, selec- tion of memory search strategy, and termination of search. Both acquisition and retrieval of memory items have computationally explicit decompositions in their paper. Although the framework is directed at memory related performance rather than inference-based problem-solving, the distinctions between monitoring and control and the information processing perspective is highly compatible with the views presented in the computational sciences. Their framework has been widely used in psychology to integrate disparate re- search and we will summarize some of that here. We will also use it to frame some of the research topics in computer science and AI.
2.2. Problem solving and metacognition
Problem solving is one area where a natural fit exists to computational theories in AI. Concepts such as executive control and monitoring are important to problem solving in order to manage problem complexity and to evaluate progress towards goals. Here much leverage for metacognitive knowledge could be gained by humans. But although Flavell [81] represents the first reference with metacognition and problem solving in the title, relatively few psychological studies have examined this phenomena explicitly since then. Some are described here.
Dörner [71] reports the earliest experiment on the effects of cognitive monitoring on human problem solving. The experimental design categorizes subjects into one of two con- ditions according to how they perform protocols after problem solving. In the introspective condition, subjects reflect out loud about their own reasoning during problem solving (at the meta-level), whereas subjects in the statistical-control group discuss their solution to
110 M.T. Cox / Artificial Intelligence 169 (2005) 104–141
the problem in terms of the hypotheses they developed (at the object level). The experi- ment itself involves a complicated machine with three lights. Each light can be turned on in four different colors. There are eight push-buttons on the machine with which subjects control the lights and their colorations. The subjects solve ten problems during the exper- imental trials. Problems consist of an initial state in which the lights of the machine begin operation and a goal state consisting of a different light configuration. Dörner reports that the experimental group performs significantly better than the control group after the third trial. Moreover, Dörner claims that introspective subjects exhibited improved performance during transfer tasks of subsequent experiments, although the details of many of the exper- iments are lacking and no replication of these results appear in the literature.
Derry [69] offers a comprehensive model of reflective problem solving for mathematical word problems inspired by John Anderson’s ACT* [1] and PUPS [2] theories of general cognition. Based on such a theory, Derry and her colleagues developed a computer-based instructional system to teach word problems to military servicemen. Prior to the develop- ment of this application, Derry performed the following experiment on groups of college students and military personnel. Given an assumption that general problem solving behav- iors, such as reasoning from the goal backwards to the solution and means ends analysis, form the bases for human problem solving, the experimenter gathered subject protocols during solution of mathematical word problems. The protocols were classified into 27 cat- egories falling into four basic phases of problem solving: clarifying a problem, developing a strategy, executing a strategy, and monitoring/checking performance. The surprising re- sult was that neither group performed problem solving in a linear fashion, and that most protocols were classified into clarifying and execution phases. The strategy-development and monitoring/checking phases lacked significant protocols.
Delclos and Harrington [67] report that both subject conditions with general problem- solving skill training and those with problem-solving coupled with metacognitive skill training demonstrate equal performance on a problem solving task. With greater task com- plexity, though, subjects with the problem-solving/metacognitive training perform better than either a control group or the problem solving training alone group. Also, Swan- son [224] claims to have established the independence of general problem aptitude from metacognitive ability. Subjects with relatively low aptitude, but high metacognitive ability, often use metacognitive skills to compensate for low ability so that their performance is equivalent to high aptitude subjects.
Finally, Davidson, Deuser, and Sternberg [57] present results from a series of studies that show the use of metacognitive abilities correlate with standard measures of intelli- gence. In their experiments on insight problem-solving they report that, although higher IQ subjects are slower rather than faster on analyzing the problems and applying their in- sights (not surprising if more processing is being performed), their performance is higher. They argue that the difference in performance is due to effective use of metacognitive processes of problem identification, representation, planning how to proceed, and solution evaluation, rather than problem solving abilities per se.
Dominowski [70] reviews many such studies (particularly those that require talking aloud protocols) and concludes that although some conflicting evidence exists, subjects in metacognitive conditions generally do better on problem-solving tasks. The reason for the difference is not just that subjects are verbalizing their thoughts. Silent thinking and simple
M.T. Cox / Artificial Intelligence 169 (2005) 104–141 111
thinking out loud perform equally well. The difference is that problem-focussed attention of subjects improve local problem-solving behavior, whereas metacognitive attention allow subjects to be flexible globally and thus have a greater chance of finding a more complex and effective problem-solving strategy.
Berardi-Coletta, Buyer, Dominowski, and Rellinger [14] illustrate this difference in a task where subjects must deal out a deck of cards such that alternating cards are placed either on a table face up or on the bottom of the deck. Thus to deal out the cards 1, 2, 3, and 4, the deck must be arranged as 1, 3, 2, and 4. Berardi-Coletta et al. identified five pos- sible subject strategies in this task that range from simple guessing or swapping incorrectly dealt cards, to more complex approaches such as differentially representing the difference between “up” and “bottom” cards. Subjects in the metacognitive verbalization condition answer out loud questions such as “How are you deciding what went wrong?” and “How are you deciding on a way to work out the order for the cards?” Subjects in a problem- fo- cussed group answer question such as “What is the goal of the problem?” and “What cards do you have in order so far?”. They discovered that subjects in the metacognitive group never guess, and, although some may use swapping at first, they abandon it to pursue the more complex reasoning approaches.
This section has illustrated some of the findings that describe how humans introspect about their cognitive performance (processes) when solving problems and how this ability can lead to improved performance. Although the findings are mixed, and no researcher claims that humans are inwardly omniscient, the results support the relevance of metacog- nitive theories for modeling intelligence and high-level reasoning. The careful monitoring of cognitive activities allows humans to control not only search for a problem solution but search for an effective problem-solving strategy.
2.3. Computational models
Finally a number of psychologists have also built computational models that represent various aspects of human performance related to metacognition. Lynn Reder and her col- leagues have an interesting model of metacognitive awareness of one’s own knowledge implemented in a computational model called SAC (Sources of Activation Confusion) [196]. As a spreading activation model of declarative memory, it accounts for fast FOK judgements by activation of a problem node at the intersection of two or more semantic nodes triggered by terms in a given question. It successfully predicts whether or not sub- jects will use a memory retrieval or compute from scratch strategy to answer the question based on such judgements. Although a highly contentious proposition in the cognitive psy- chology community, the model also supports the notion that much of metacognition is an implicit process not subject to verbal reports.
Chi [32,33] reports that improved learning is correlated with human subjects who gen- erate their own questions during reasoning and explicitly explain the answers themselves (see also [187]). This is the so called self-explanation effect. This strong and positive effect has been modeled computationally by VanLehn and colleagues [227,228]. Note that this effect refers to explanations of self-generated questions about problems and not necessarily explanations about the self.
112 M.T. Cox / Artificial Intelligence 169 (2005) 104–141
In relation to Chi and VanLehn’s research, Recker and Pirolli [194] have shown that a Soar-based model of learning called SURF can explain individual differences exhibited by human subjects while learning to program in LISP using instructional text. The dif- ference that accounted for much of the variability was self-explanation strategies. Those students who explained problems to themselves during comprehension of the instructions performed well on a subsequent performance task consisting of LISP programming ex- ercises. The students who did not exhibit this behavior were not as likely to excel in the LISP task. The SURF model predicted such differences. The model took into account only domain-related elaborations; however, subjects exhibited other self-explanations that the model did not cover. In particular, some subjects seemed to exploit metacognitive feedback, like comprehension monitoring, in order to judge when to learn [184]. If self-reflection on the states of a subject’s comprehension of the instruction indicated an understanding fail- ure, then this was sometimes used as a basis to form a goal to learn.
2.4. Caveats and the relation of psychological research to computational research
Research concerning introspection has long been controversial (e.g., see [20,176] for objections to such research). Around the turn of the 19th century, trained introspection was assumed to be the proprietary scientific tool of the psychologist when “objectively” studying the mind.6 The behaviorists tried to erase all scientific association with intro- spection by claiming not only that learning should be examined without the use of such introspective methods (e.g., [232]), but moreover that learning should be explained with- out reference to any intervening mental variables whatsoever (e.g., [216,217]). Under the banner of metacognition research, however, interest returned to the study of introspection, second-order knowledge, and their roles in cognitive activities.
Yet, to believe that metacognition is a kind of psychological or computational panacea is a deceptive assumption. Wilson and Schooler [236] have empirically shown that conditions exist under which introspection actually degrades specific performance (e.g., preference judgements). In the context of story understanding, Glenberg, Wilkinson, and Epstein [95] reported that human self-monitoring of text comprehension is often illusory and overes- timated, especially under the conditions of long expository text. In general, people are overly-confident in cognitive tasks such as question answering [91]. Furthermore recent studies specifically about metacognition have emphasized the fragility of people’s knowl- edge concerning themselves and their own reasoning processes.
Metcalfe [154] surveys a variety of cognitive tasks in which humans over-estimate their actual performance and exhibit a wide range of false expectations. For example they will think that they can solve particular problems when they cannot; they become very confi- dent that they are about to generate a correct answer when they are actually on the verge of failing; they think they have answers on the tip of their tongue when an answer actually
6 Titchener and others took great pains to develop a rigorous method of introspection and attempted to equate it with objective inspection (observation) as practiced in physics. For example, Titchener [226] claims that “Ex- perimental introspection, we have said, is a procedure that can be formulated; the introspecting psychologist can tell what he does and how he does it” (p. 500). This remarkable statement is at the same time naïve and arrogant, given the hindsight of history.
M.T. Cox / Artificial Intelligence 169 (2005) 104–141 113
does not exist; and most amazingly they insist that they did give correct answers when pro- vided evidence to the contrary. Such data make suspect earlier more simple interpretations of metacognition such as Dörner’s.
Likewise, computational introspection is not effective under many circumstances given the overhead associated with it, and, given the demonstrated limitations of human intro- spection, computational theories should try not to overstate its scope. One must be cautious, however, when dismissing metacognition simply because of computational overhead costs. Doyle [73, p. 30] warns that to disregard the introspective component and self-knowledge in order to save the computational overhead in space, time, and notation is discarding the very information necessary to avoid combinatorial explosions in search.
Research regarding metacognition processes in humans is relevant to metacognition in computation in at least two ways. First, and foremost, is the emphasis on cognitive self- monitoring for control. This behavior is the (limited) human ability to read one’s own mental states during cognitive processing and use the information to influence further cognition. Thus, there exists some insight into the content of one’s mind resulting in an internal feedback for the cognition being performed and a judgement of progress (or lack thereof). Garner [92] has argued that metacognition and comprehension monitoring are important factors in the understanding of written text. Reading comprehension is there- fore considered to be chiefly an interaction between a reader’s expectations and the textual information.7 Psychological studies have also confirmed a positive correlation between metamemory and memory performance in cognitive monitoring situations [208,233]. This evidence, along with results from the studies above linking problem-solving performance with metacognitive abilities, directly supports the conviction that there must be a second- order introspective process that reflects to some degree on the performance element in an intelligent system, especially a learning system involved in understanding tasks such as story understanding.
Second, much of AI theory (especially GOFAI, or “good old fashioned AI”, a term coined by Haugeland [106]) places a heavy emphasis on explicit representation. Trains of thought, as well as the products of thought, are represented as metaknowledge struc- tures, and computation is not simply the calculated results from implicit side-effects of processing. This emphasis is echoed in Chi’s [31] argument, that to understand knowl- edge organization and to examine research issues there must be some representational framework. Although diverging from the framework suggested by Chi, the following section describes specific research in the computer sciences that represent knowledge about knowledge and knowledge about process. It also surveys many other important theories and implementations that bear on the phenomena discussed in the current sec- tion.
7 A special relation exists between metacognition, question asking and text understanding (see [93,187]). In effect, human learners use question-asking and question-answering strategies to provide an index into their feeling of comprehension of a given piece of text. This metacognitive feedback helps readers find areas where their understanding of the story is deficient, and thus where greater processing is necessary. As a final tangent, not only is metacognition important in language understanding, it is also important in language generation (i.e., in metalinguistic development; see [97]).
114 M.T. Cox / Artificial Intelligence 169 (2005) 104–141
3. Artificial intelligence, metareasoning, and introspection
The AI community has long considered the possibility of providing machines with metacognitive faculties. In the 1980s and 1990s, researchers organized a number of confer- ences and symposia to explore some of the issues that relate to this concern: the Workshop on Meta-level Architectures and Reflection held in Alghero, Italy, during October, 1986 [140]; the International Workshop on Machine Learning, Meta-Reasoning and Logics held in Sesimbra, Portugal during February, 1988 [23]; the IMSA-92 Workshop on Re- flection and Metalevel Architectures held in Tokyo, Japan, during November, 1992; the AAAI Spring Symposium on Representing Mental States held at Stanford University dur- ing March, 1993 [111]; the AAAI Spring Symposium on Representing Mental States and Mechanisms held at Stanford during March, 1995 [51]; and the Second International Con- ference on Meta-level Architectures and Reflection held in Saint-Malo, France during July, 1999 [37]. In general, the loci of related research efforts has tended to focus the logic community on belief representation and introspective reasoning about such beliefs; the expert system community on metaknowledge and the control of rules; the decision- making and planning communities on search control and the choice of reasoning actions; and the model-based and case-based reasoning community on reasoning about reasoning failure, representations of process, and learning. This section presents a brief sketch of these trends.
From the very early days of AI, researchers have been concerned with the issues of ma- chine self-knowledge and introspective capabilities. Two pioneering researchers, Marvin Minsky and John McCarthy, considered these issues and put them to paper in the mid-to- late 1950’s. Although first exchanged among colleagues, and then printed at conferences at the turn of the decade in preliminary form,8 reprints of these papers were refined and gathered together in the seminal collection of early AI articles entitled Semantic Informa- tion Processing [161]. Minsky’s [160] contention was that for a machine to adequately answer questions about the world, including questions about itself in the world, it would have to have a executable model of itself. McCarthy [145] asserted that for a machine to adequately behave intelligently it must declaratively represent its knowledge. These two positions have had far-reaching impact.
Roughly Minsky’s proposal was procedural in nature while McCarthy’s was declara- tive. Minsky believed that an intelligent machine must have a computational model of the outside world from which a simulated execution could answer questions about actions in the world without actually performing any action. He argued that if a machine uses models to answer questions about events in the world and the machine itself is in the world, then it must also use a recursive self-model or simulation to answer questions about itself, its own dispositions, and its own behavior in the world. This was a very early prototype of a mental model that became a precursor to similar research in both problem solving and
8 Minsky notes that he had been considering the ideas in this paper since 1954. It first appeared as Minsky [159], although the concluding two pages of Minsky [158] address exactly the same issue. A significant portion of McCarthy’s ideas was first published as McCarthy [144].
M.T. Cox / Artificial Intelligence 169 (2005) 104–141 115
Fig. 3. A taxonomy of knowledge.
understanding (e.g., [16,17,64,1169,152]). In the spirit of Minsky’s original theme, some very novel work has also been performed to enable a machine to procedurally simulate itself (e.g., [220]).
As a four and one half page discussion of the mind-body problem and the idea that human understanding is essentially the process of executing some model of the world, Minsky’s paper is most interesting because it includes the modeling of not only the world, but the self (the modeler) as well (see Fig. 3). Thus, there is W, the world, and M, the modeler who exists in the world. The model of the world is referred to as W*. W* is used to understand and answer questions about the world. So to answer questions about oneself in the world, it must also be the case that there exists within the model of the world, W*,
9 Johnson-Laird [117, p. 361] explicitly takes issue with the suggestion that Minsky’s concept of a self-model was in such a form that it could correspond to a human’s capacity for self-reflection. He claims that Minsky’s formulation is equivalent to a Turing machine with an interpreter that consults a complete description of itself (presumably without being able to understand itself), whereas humans consult an imperfect and incomplete men- tal model that is somehow qualitatively different. However, this argument appears to be extremely weak because the two positions are so similar and closely related.
116 M.T. Cox / Artificial Intelligence 169 (2005) 104–141
a model of the modeler, termed M*. One should conceive of W* simply as the agent’s knowledge of the world, and likewise, M* as the agent’s reflective knowledge of itself in the world.
Furthermore, as Minsky notes, one must have a model of one’s model of the world, or W**, in order to reason about and answer questions concerning its own world knowledge. Although Minsky does not label it as such, the kind of knowledge embodied in this model is typically referred to as metaknowledge. Finally, M** represents the agent’s knowledge of its self-knowledge and its own behavior, including its own thinking. Within M** one might include most metacognitive knowledge of person variables (at least concerning the self). It would have a semantic component like “I am good at general memory tasks,” as well as episodic components such as knowledge gained through monitoring (e.g., “I just solved a problem by remembering a similar past solution.”). Again, although Minsky does not refer to it as such, M** represents introspective knowledge. Minsky elaborates on his ideas at the end of his book Society of Mind [162].
In the following subsection, I explore McCarthy’s proposals and their local impact on the logic community and their more global effect on the tone of research into a com- putational explanation of metacognition. The second subsection then looks at additional varieties of research in the expert-system and decision-making communities. Finally, the last subsection relates some of the relevant research from the case-based reasoning and model-based reasoning communities to the research presented here.
3.1. Logic and belief introspection
A logical belief system can answer queries about the world given axiomatic facts (a knowledge base) and a logical inference mechanism. Furthermore a logical agent can determine what action to take in a given situation by proving that the action achieves some goal; that is the action necessarily follows from what it knows. Model-theoretic reasoning maintains the set of possible worlds consistent with the knowledge base. Logical resolution makes this kind of reasoning practical (e.g., using PROLOG).
As mentioned above, McCarthy [145] not only established a manifesto for AI (i.e., knowledge representation is foundational, especially in declarative axiomatic form), but suggests that machines can examine their own beliefs when such beliefs are explicitly represented.10 This suggestion is developed in [150] and made explicit in both [107] and [146]. A system requires such a metacognitive capability if it is to reason fully about the correctness of its knowledge. This is especially useful because beliefs are subject to re- traction in the face of new information (i.e., knowledge is nonmonotonic). But beyond any technical details, McCarthy also wonders what it means for a machine to have a mental life. McCarthy [146] enumerates six reasons why attributing mental qualities to programs and machines is a useful exercise. Among them, he claims (as does Dennett’s [68] essay on the intentional stance) that humans can more quickly and more easily understand a pro- gram, its behavior, and its intended function by ascribing beliefs and goals to the machine than by analyzing and explaining it in the language of program code and computer states.
10 The paper repeatedly illustrates Advice Taker examples with propositions that use the indexical “I”.
M.T. Cox / Artificial Intelligence 169 (2005) 104–141 117
But most interestingly, McCarthy takes the business of understanding and simulating a machine’s mental life beyond a mere practical metaphor. He questions what it means for a machine to have consciousness and to introspect about its mental world. Furthermore, he realizes that “introspection is essential for human level intelligence and not a mere epiphe- nomenon” [148, p. 89]. Thus, he is keenly interested in the relation between machine and human metacognition.
McCarthy [146] defines introspection as a machine having a belief about its own men- tal states rather than about propositions concerning the world. This position has focussed much of the logic community, especially researchers such as Konolige [121,123] and Moore [168,169], on reasoning about knowledge, belief, and internal states, rather than reasoning about process and computation (but exceptions exist such as Genesereth’s [94] MRS system that reasons about the correctness of logical proofs).
Konolige [122] represents a belief system with a deductive model rather than a possible worlds model. A deduction structure is a mathematical abstraction of many types of belief systems, especially expert systems (see the next section). The structure contains a knowl- edge base of facts and a finite set of inference rules. Although the model assumes that all possible deductions are made by a belief system, it does not assume that all possible logical consequences of the particular facts will be made, because the inference rules the system actually has may be incomplete due to the domain abstraction chosen by the designer. Re- gardless if a bounded belief system or machine, M, uses an introspective machine, IM, to answer queries concerning itself, the belief system is defined to be an introspective be- lief system. Furthermore Konolige defines self-beliefs answered by M as extrinsic; intrinsic self-beliefs are answered solely by IM. Although some self-questions such as “Is my broth- er’s name John?” can be answered extrinsically, only by introspective deduction through the system IM can it answer questions such as “Can M deduce some consequent given a particular deduction structure?”. Moreover by separating the two levels, some problems of the liar’s paradox and self-reference are eliminated [9]. Unfortunately the drawback is that non-paradoxical self-referential and mutually referential sentences cannot be represented (see [181,182]).
McCarthy [147] further formalizes the idea of introspection by introducing context as a first-class object about which a system can reason. By encapsulating mental situations in formalized contexts, the reasoner can view the mental state as providing an outer context. Reasoning about one’s own thoughts then involves transcending the outer context [147]. However, the realization of such an introspective mechanism has not been implemented. Furthermore, McCarthy [148] notes that even though reason maintenance systems (e.g., [72]) record justifications for their beliefs and can retract beliefs in response to new infor- mation, they do not have the capability of inspecting the justification structures or making specific assertions about them, nor do they have the power to derive explanations from such structures.11
11 McCarthy [146,148] also outlines a number of additional issues concerning the mental domain that have received lesser attention by the logic community. He raises the issue of consciousness, language, intentions, free will, understanding and creativity, all of which have come to represent provocative focal aspects of intelligent reasoning. But of course see [160,162] for further analyses of free will.
118 M.T. Cox / Artificial Intelligence 169 (2005) 104–141
3.2. Knowledge-based systems, metareasoning, and control
The expert system community has also invested much effort into the formalization of metareasoning and metaknowledge. It was recognized in the late 1970’s that differences exist between domain knowledge in the form of expert rules, and declarative control knowl- edge in the form of meta-rules ([59–61]; see also [36]). Metarules encode knowledge about how rules should be executed, whereas ordinary rules encode domain-specific knowledge. Barr [11,12] noted, as I do here, the parallel relation between higher-order knowledge and reasoning by knowledge-based systems and human metacognition (see also [133]). Es- pecially when trying to automate the transfer of domain knowledge from human expert to machine expert, these and other researchers have attempted to give programs abstract knowledge of human reasoning and inference procedures, so that programs can under- stand human experts (see for example [34]). Additionally, when expert systems explain a conclusion by providing to the user a list of rules through which the system chained to generate the conclusion, the system is said to introspect about its own reasoning. This view appears, however, to be an over-simplified example of both metacognition and explana- tion.
Davis and Buchanan [62] claim that four types of meta-level knowledge exist: knowl- edge about object representations (encoded in schemata), knowledge about function rep- resentation (encoded in function templates), knowledge about inference rules (encoded in rule models), and knowledge about reasoning strategies (encoded in metarules). But much of this information is less akin to metacognitive knowledge than it is to ordinary abstract knowledge. For example, the schematic object knowledge above is equivalent to class de- finitions in an object-oriented language such as Java. Furthermore to claim that default inheritance and learning are inherently introspective processes [138] or that extrapolating from past experience is reflective thinking [219] is perhaps stretching the definitions of introspection and reflection respectively.
As another example, Batali ([13]; also [139]) considers the meta-level to be that which decides about the base-level (or actions in the world) and explicitly includes planning as a meta-level reasoning process. This unfortunately conflates metareasoning with reason- ing (c.f., the confusion between metacognition and cognition12), because the system is not reasoning about the reasoning process itself. A procedural difference exists between rea- soning about a solution or a problem and the metareasoning directed at the reasoning that produces such solutions or engages such problems. For instance, Carbonell [26] notes that in order to transfer knowledge from programming a quicksort problem on a computer in Pascal to solving the same problem in LISP, a student cannot analogically map the Pascal solution to LISP code. The languages are too dissimilar in data structures and process con- trol. Instead the reasoner must reason about how the original solution was derived and what
12 For example, Derry [69] claims that metacognitive components are associated with, not only knowledge of the problem-solving process, but with the ability of a subject to orchestrate and monitor these same processes (see the second subsection of Section 2). Yet the paper often combines discussion of domain-independent problem solving processes with that of the orchestration and monitoring processes. Problem solving itself is often discussed in terms of strategy, thus further blurring the delineation between cognition and metacognition.
M.T. Cox / Artificial Intelligence 169 (2005) 104–141 119
decisions were made while solving the first problem, analogically mapping the derivation to LISP. Reasoning is at the algorithm level, rather than the code level.
Another popular research issue has been to develop systems that can reason about LISP functions and the actual code that represents a program’s control [13,62,137,139,219]. However, this form of metacognition is at a low-level as compared to other methods cov- ered here. Programs need to reason about the functioning at the level of cognitive or logical processes, as well as at the level of program execution.13 Nonetheless, this research has motivated an important DARPA thrust [128] into self-adaptive software systems that ad- just their configurations in response to experience.
Some in the AI community have come to recognize some of the more subtle differ- ences between the different families of metareasoning. For example, Clancey [35] notes that many of the metarules employed by systems such as TEIRESIAS [60], although deal- ing with control, are nonetheless domain specific. He claims that strategic knowledge is inherently procedural whereas domain specific knowledge is rule-based. Moreover, unlike his previous work (e.g., [34]), he currently eschews modeling the mental process that the expert uses when reasoning about the domain, and instead he emphasizes modeling the do- main that the expert knows. This change of focus to cognitive engineering, however, seems to be as much a concession to the difficulty of representing metacognitive knowledge as it is a necessity dictated by representation itself.
Although many in the artificial intelligence community have recognized the necessity of reasoning about one’s own beliefs, few have both modeled and represented the processes that generates beliefs, and made them available to the reasoner itself. In this category of metacognitive system, a categorical distinction exists between those systems that reason forward to decide what action to perform or what computation to execute, and those that reason backward to explain a failure or to learn. This is related to the distinction made in the psychological literature between forward strategic control and backward metacognitive monitoring (see again Fig. 2). In AI researchers use the terms metareasoning (or meta-level control) and introspection respectively.
In the former category, systems attempt to choose a reasoning action based on some knowledge of the mental actions at the disposal of the system. Doyle [73], as well as Rus- sell and Wefald [204,205,225], use probabilistic estimations and decision theory to select a computation that has the most expected utility. Etzioni [77] uses decision-analytic meth- ods to weigh the trade-off between deliberation cost, execution cost and goal value when choosing a goal toward which to direct attention and when deciding which action to take in service of a chosen goal.14 The latter category of systems represents feedback from the reasoning process. This feedback can further inform the forward metareasoning, or it can be used in learning in causal abductive tasks such as explanation and interpretive under- standing. The subsequent subsection looks at the metareasoning issues of decision making
13 In the terms of Newell [173], the reasoning should be at the symbol level as well as at the register-transfer level of intelligent systems.
14 The consensus is that Good’s [98] research on Type II rationality (i.e., taking into consideration of the expected utility of action that includes the cost of deliberation itself) provided the foundation from which all such research began.
120 M.T. Cox / Artificial Intelligence 169 (2005) 104–141
under limited conditions. It examines both control and monitoring sides. Discussion of introspective explanation and learning waits until the section after next.
3.3. Limited rationality
One of the core problems of AI (and indeed of human intelligence) is that of deciding what to do in any given situation. In all but the most trivial of conditions, many actions exist from which to choose, and the outcomes of such actions are often unclear or involve considerable uncertainty. Decision theory states that the most rational behavior is the action that maximizes the expected utility under all possible conditions [231]. The expected utility is defined as
x∈X
where X is the set of possible outcomes, Pr(x) is the probability of a particular outcome x ∈ X and U : X → R is a real-valued utility function over outcomes. The best action, a∗, then is the one across whose possible resultant states sums to the highest expected utility.
a∗ = argmax EU | Pr, results(a). a∈A
Here A is the set of possible actions and results(a) is the distribution of states that could result from performing a particular action, a. Seen another way and given that an agent can be considered a function that maps to actions observations of the environment (including outcomes of its actions), a rational agent is represented by the optimal function, f∗, such that
f∗ =argmaxV(f,E,U), f
where V returns the global value of the expected utility in environment E. The problem with this solution is that, even if an agent could calculate the values of all possible states reachable with all available actions, the world will change while the calculation is being made. That is rational choice is resource-bounded by time, and the search space is so large that perfect rationality is impossible. Thus as mentioned at the very beginning of this paper, the agent must reason about both the benefits and costs of the actions and the associated benefits and costs of the reasoning about the actions. As such metacognition includes both control and monitoring components parallel to that in Fig. 2.
Russell [201] has outlined a comprehensive theoretical approach to this trade off that turns the imprecise question of preferred behavior of an abstract agent into the design of the optimal program on a specific machine. Traditional AI has operationalized the task of producing good behavior by substituting for perfect rationality the idea of computing a choice with an agent program or calculative rationality. But for computationally complex problems (e.g., chess), the fact that a program will eventually reach the best decision be- cause it has encoded sufficient knowledge to ascertain the solution (e.g., knows the rules of chess and has the goal of achieving checkmate) does little to guarantee that an actual solution will be computed in feasible time frames. Instead rational metareasoning seeks to
E[U |Pr,X]=
Pr(x)U(x),
M.T. Cox / Artificial Intelligence 169 (2005) 104–141 121
include into the calculation the cost of the time it takes to select an action. Bounded opti- mality seeks further to analyze reasoning and metareasoning using the tools of complexity theory.
Russell and Wefald’s [204,205] research seeks to find an equilibrium between reason- ing and action using metacognitive control of computations. In AI this meta-level control problem is equivalent to the control information flow that Fig. 2 shows from the perspec- tive of psychology. Such tradeoffs between thinking and doing arise in anytime systems [63,112].15 An anytime system has the property that a current best choice always exists as an approximation to the perfect choice. The decision then is whether to execute the chosen action at time t or to perform additional reasoning with the hope of possessing a better choice at t + i, where i is a time increment often equal to 1. According to Russell and Wefald, the construction of a system to make this kind of decision is based upon two principles. First computations are to be treated as actions (i.e., mental actions) and thus selected as to their expected utility in the joint physical/mental space of outcomes. Second this utility is based upon the cost associated with doing nothing due to intervening changes in the world and upon the possible computational improvement due to the choice of a better mental action.
The previous approach assumes that checking to ascertain the results of a computation is negligible. However such monitoring of computations may itself result in time and cost, so a more complete agent must reason about the monitoring of anytime calculations [239]. Consider that if the rate of decision improvement of reasoning is rather constant, then a contract can be made to specify the duration of running an anytime algorithm to achieve the maximum overall expected utility. However if a large amount of variability exists with the performance of the reasoning, the results must be periodically checked to ascertain the current progress and to determine whether or not to halt reasoning. Otherwise reasoning is wasted. Monitoring thus can serve two purposes. It can provide feedback as to the progress of the current reasoning and it can also be used to compile online (or offline) a profile of algorithm performance used to judge future reasoning.
Compiling performance profiles are especially important for complex algorithms that themselves may be composed of more primitive anytime algorithms [240]. The question then arises as to the allocation of computation resources to the individual pieces of the reasoning task. Algorithms may be arranged as a competing concurrent ensemble or in serial cascade such that the output of one provides the input to another. For example in a serial case, the meta-level control problem is how long to allow a vision computation before stopping it to run a path planning algorithm when the system must improve the overall robot trajectory. The vision component develops a terrain map that the planner uses. Whereas the planner initially creates an abstract general route and incrementally refines various path segments. Conditionalized performance profiles represent compiled introspective metaknowledge (M** in Minsky’s terms) used to estimate the distribution of future run-times based upon input quality and past run-time.
15 Note that this research focussed on one-step look-ahead local search rather than general anytime planning. We disregard the difference for the purpose of this discussion.
122 M.T. Cox / Artificial Intelligence 169 (2005) 104–141
Hansen and Zilberstein [103] took this approach further by modeling the set of termina- tion choices of the anytime process as a sequential Markov decision problem. The discrete states are levels of quality at a particular time, the action transitions between states are stop and continue, and the cost function is the expected value of the computation. The system then can use dynamic programming to determine an optimal stopping policy, π∗(q,t). The important difference between this work and the previous is that the meta-level control in- formation (i.e., the policy) is a statistical model of the reasoning process and its transitions rather than a statistical summary of the process behavior (i.e., the conditional performance profile).
Note that Hansen and Zilberstein’s model is similar to the MDP developed for the algo- rithm selection task I used to motivate metareasoning in the beginning of this paper. This leads to the idea that reasoning is performed in a joint space of internal and external states and actions. The object level controls actions to be taken in the world and the meta-level controls the reasoning method to be taken in the mental world. Moreover just as an object level policy can be learned using reinforcement learning, so too can a meta-level policy be learned in the mental space. The advantage of using reinforcement learning is that it avoids myopic measurements that estimate the value of the computation solely based on local information. Harada and Russell [105] has made some progress using this idea, and the concept has been implemented in the object domain of Tetris. Their approach uses semi-Markov decision processes (SMDPs) instead of MDPs, because SMDPs model the variable length of time between decisions.
One of the original theoretical goals of Russell and Wefald was to change the focus of finding the optimal agent, f∗, to the more concrete objective of designing the optimal agent program, l∗. written in a language, L, that runs on machine, M. with respect to the available computational resources in the environment E.
∗ l = argmax V Agent(l, M), E, U .
l∈LM
Russell and Subramanian [203] have proved that this is possible for some small search tasks (e.g., automated mail sorting) and have argued for a more relaxed asymptotic version whose criterion for optimality depends upon a constant improvement in processor speed. This argument is not unlike the definition of optimality in complexity analysis.
Many other researchers have worked on problems of bounded rationality of course including Simon [213,214] and Doyle [73]. See [113] for a emphasis on control of the decision making of bounded optimal agents and reasoning about the value of computa- tions similar to that of Russell and Wefald. Note also that many researchers such as Fink [78,79] use statistical methods to choose problem-solving strategies without ever framing the problem in terms of metacognitive processes.
3.4. Model-based reasoning, case-based reasoning and introspective learning
Clearly people can and often do reason about their own reasoning and memory. Hayes [107] recounts a discussion he once had with a Texan about the number of scan lines in television screens in England. He thought it was one number whereas the Texan thought that it was another. At first Hayes was not sure about his answer. However if the number had
M.T. Cox / Artificial Intelligence 169 (2005) 104–141 123
changed at some point from his to the Texan’s, it would have been an event that he would surely remember, but he did not. Thus after this realization in the dialogue, his confidence in the answer solidified. Hayes concludes that, more than simply not recalling the event, he had to realize that there was the lack of recall and actually use this fact as an argument in his reasoning.
The model-based reasoning and case-based reasoning communities have not missed such insights either. Like Minsky’s insistence on a self-model and McCarthy’s insistence on declarative knowledge, Collins, Birnbaum, Krulwich and Freed [39] argue that to plan ef- fectively a system must have an explicit model of its of planning and execution processes.16 Given an explicit model of the causal and teleological properties of a standard physical de- vice such as an electronic circuit [65], a system can reason about future artifact design of similar electronics or can diagnose faults in specific circuits of that device class. Likewise researchers such as Stroulia [221,222] and Murdock [170] treat the system itself as a device from whose model the system can generate a redesign or perform self-diagnosis.
Functional models are a particularly valuable form of knowledge for metacognitive rea- soning. Whereas knowledge about the composition and behavior of reasoning strategies is important, such knowledge is more useful in supporting reflection and learning, if it is augmented by information about the functions of those strategies. Functional descriptions are particularly useful in metacognitive reasoning for three reasons: (a) functional descrip- tions can act as indices for retrieving relevant strategies to accomplish new requirements, (b) functional descriptions of required and retrieved strategies can be compared to compute differences to motivate adaptation, and (c) functional descriptions of the parts of a retrieved strategy can guide adaptation of the strategy to eliminate these differences (Murdock, per- sonal communication).
At the heart of case-based reasoning (CBR) and case-based explanation [120,131,207] is the learning and use of episodic past experience in the form of a cases in a case mem- ory. Given a new problem, a CBR system retrieves an older solution to a similar problem and then adapts it to fit the current problem-solving context. CBR systems have also been used to interpret actions and understand events in such comprehension tasks as story under- standing (natural language processing). Old explanation schemata or cases can be retrieved from memory and used to understand interesting or otherwise unusual events in the input. Finally learning has traditionally been central to CBR. It involves not only acquiring new case experience from success, but has focussed on repairing cases that fail and then learn- ing to anticipate and avoid future performance failures by explaining what went wrong with executed actions in the world (e.g., [102]).
The theory presented in [46,55] is a computational model of introspection and failure- driven learning anchored firmly in the CBR tradition. In large part, the work represents a machine learning theory in the area of multistrategy systems that investigates the role of the planning metaphor as a vehicle for integrating multiple learning algorithms [54,192]. To another extent, the research is a cognitive science treatise on a theory of introspective learning that specifies a mechanistic account of reasoning about reasoning failure. The
16 This contention concerning planning is also shared by Fox and Leake [86,132] with respect to case-based planning and, moreover, was independently stated by Kuokka [126] outside of the case-based reasoning commu- nity.
124 M.T. Cox / Artificial Intelligence 169 (2005) 104–141
central idea is to represent explicitly the reasoning of an intelligent system in specific knowledge structures17 or cases called meta-explanation patterns (Meta-XPs) that explain how and why reasoning fails [44,47,53]. When failure occurs, the learner can then examine the trace structures (TMXPs; i.e., the how part), retrieve an introspective failure pattern (IMXP; i.e., the why part) from case memory, and unify the two to determine the proper learning methods. The overarching goal of the theory is to understand systems that turn inwards upon themselves in order to learn from their own mistakes.
The implementation of the theory is a case-based reasoning system called Meta-AQUA whose base performance task is story understanding (AQUA, [190,191]). The idea is to have the system keep a trace of its explanation process, and when it generates an unsuc- cessful explanation of some event in the story, it needs to explain the explanation failure (hence meta-explanation). As Fig. 1 shows, the AQUA component represents the story as a connect graph of action sequences that change the state of the environment in the story. When an unusual event occurs, AQUA will attempt to explain why the characters decided to perform the event. In a like manner, Meta-AQUA represents the actions and events in AQUA. Consider the following story (quasi-random generated).
Lynn was bored and asked Dad, Do you want to play ball? Then Dad went to the garage and picked up a baseball, and they went outside to play with it. He hit the ball hard so that it would reach her in left field. Lynn threw the ball back. They continued like this all afternoon. Because of the game, Lynn was no longer bored.
In the story Meta-AQUA finds it unusual for a person to strike a ball because its con- cept of “hit” constrains the object attribute to animate objects. It tries to explain the action by hypothesizing that Dad tried to hurt the ball (an abstract explanation pattern, or XP, retrieved from memory instantiates this explanation). However, the story specifies an alter- nate explanation (i.e., the hit action is intended to move the ball to the opposing person). This input causes an expectation failure (contradiction) because the system had expected one explanation to be true, but another proved true instead.
When Meta-AQUA detects an explanation failure, the performance module passes a trace of the reasoning (a TMXP) to the learning subsystem. The learner is composed of
17 To support effective explanation of reasoning failure, and therefore to support learning, it is necessary to rep- resent explicitly the thought processes and the conclusions that constitute the reasoning being explained. A large number of terms exist in the English language that concern mental activity. The earliest research to represent such content is Schank, Goldman, Rieger and Riesbeck [206] who attempted to specify the primitive representations for all verbs of thought in support of natural language understanding. They wished to represent what people say about the mental world, rather than represent all facets of a complex memory and reasoning model. Schank’s con- ceptual dependency theory distinguishes between two sets of representations: primitive mental ACTs and mental CONCEPTUALIZATIONs upon which the ACTs operate. In addition, the theory proposes a number of causal links that connect members of one set with members of the other. They used only two mental ACTS, MTRANS (mental transfer of information from one location to another) and MBUILD (mental building of conceptualiza- tions), and a few support structures such as MLOC (mental locations, e.g., working memory, central processor and long-term memory) to create a mental vocabulary. Schank’s theory has been corroborated by parts of the psychological literature, such as Schwanenflugel, Fabricius, Noyes, Bigler and Alexander’s [212] analysis of folk theories of knowing. Subject responses during a similarity judgement task decomposed into memory, inference, and I/O clusters through factor analysis.
Table 1
Learning from explanation failure
Symptoms
Faults
Learning goals
Learning plan
Plan execution results
Contradiction between input and memory
Contradiction between expected explanation and actual explanation
Incorrect domain knowledge Novel situation
Erroneous association
Reconcile input with conceptual definition Differentiate two explanations
Abstraction on concept of hit Generalization on hit explanation Index new explanation
Mutually re-index two explanations
Object of hit constrained to physical obj, not animate obj
New case of movement explanation acquired and indexed
Index of hurt-explan = animate obj; of move-explan = inanimate obj
M.T. Cox / Artificial Intelligence 169 (2005) 104–141 125
a CBR module for self-diagnosis and learning-goal generation and a non-linear planner for learning-strategy selection. At this time, the learner needs to explain why the failure occurred by applying an introspective explanation to the trace. An IMXP is retrieved using the failure symptom as a probe into memory. Meta-AQUA instantiates the retrieved meta- explanation and binds it to the trace of reasoning that preceded the failure. The resulting structure is then checked for applicability. If the explanation pattern does not apply cor- rectly, then another probe is attempted. An accepted IMXP either provides a set of learning goals that are designed to modify the system’s memory or generates additional questions to be posed about the failure. Once a set of learning goals is posted, the goals are passed to the nonlinear planner for building a learning plan.
Table 1 lists the major state transitions that the learning processes produce. The learning plan is fully ordered to avoid interactions. For example, the abstraction step must precede the other steps. A knowledge dependency exists between the changes on the hit concept as a result of the abstraction and the use of this concept by both generalization and the index- ing.18 After the learning is executed and control returns to sentence processing, subsequent sentences concerning the hit predicate causes no anomaly. Instead, Meta-AQUA predicts the proper explanation.
Several fundamental problems are addressed to create such learning plans or strategies. These problems are (1) determining the cause of a reasoning failure (introspective blame assignment, [192]), (2) deciding what to learn (learning goal formulation, [48,54]), and (3) selecting and ordering the best learning methods to pursue its learning goals (learning strategy construction, [52]). The system can reason about both errors of inference as well as memory retrieval (e.g., forgetting, [42,44]). A large empirical evaluation of Meta-AQUA
18 During mutual re-indexing, the explanations are differentiated based on the object attribute-value of the hit. However, the abstraction repair changes this attribute. The generalization method applied to the new explanation also uses this attribute. See [46] for a more complete analysis.
126 M.T. Cox / Artificial Intelligence 169 (2005) 104–141
demonstrated the positive value of introspective reasoning for effective learning using a corpus of six runs that includes 166 stories and comprises a total of 4,884 sentences [45,55]. In general, the orientation is similar to many approaches based on reasoning traces (e.g., [26,164,223]) or justification structures (e.g., [18,66,72]) to represent problem-solving per- formance and to other approaches that use characterizations of reasoning failures for blame assignment and multistrategy learning (e.g., [118,167,180,222]). Reasoning trace informa- tion has primarily been used for blame assignment during planning (e.g., [18,39,229]) and for speedup learning (e.g., [166]). In addition to Meta-AQUA, many other systems have used an analysis of reasoning failures to determine what needs to be learned. Some ex- amples include Mooney and Ourston’s [167] EITHER system, the CASTLE system of Krulwich [39,125], Fox’s [85–87] ROBBIE path planning system, and Stroulia’s [221]
Autognostic system.
The IULIAN system of Oehlmann, Edwards and Sleeman [178,179] maintains metacog-
nitive knowledge in declarative introspection plans. Freed’s RAPTER system [50,89] uses three types of self-knowledge when learning. Records of variable bindings maintain an implicit trace of system performance, justification structures provide the knowledge of the kinds of cognitive states and events needed to explain the system’s behavior, and transformation rules [38,101] describe how the mostly implementation-independent knowledge in justification structures corresponds to a particular agent’s implementation. In the Meta-AQUA system, however, TMXPs maintain reasoning traces explicitly, and most implementation-dependent knowledge is avoided.
Birnbaum et al. [18] focuses on the process of blame assignment by backing up through justification structures but do not emphasize the declarative representation of failure types. They explicitly model, however, the planner. They also explicitly model and reason about the intentions of a planner in order to find and repair the faults that underlie a planning failure (see [90]). Though much is shared between CASTLE and Meta-AQUA in terms of blame assignment (and to a great extent CASTLE is also concerned with deciding what to learn; see [124]), CASTLE does not use failure characterizations to formulate explicit learning goals nor does it construct a learning strategy in a deliberate manner within a mul- tistrategy framework. The only other system to introspectively deliberate about the choice of a learning method is the ISM system of Cheng [30]. ISM optimizes learning behavior dynamically and under reasoning failure or success, but the system chooses the best single learning algorithm, rather than composing a strategy from multiple algorithms. ISM does not therefore have to consider algorithm interactions. Regardless of the differences, all of the systems, representations, methods and theories described in this section have more in common than not with respect to metacognitive reasoning analyses.
4. Trends in current research
Perhaps one of the most influential research trends in artificial intelligence is that of control of anytime systems through metareasoning. Given that intelligent agents are necessarily resource bounded and that nontrivial problems tend to be computationally in- tractable, an agent must reason about the state of its reasoning process to make significant progress. However Conitzer and Sandholm [40] recently proved that certain forms of the metareasoning problem are NP-hard whereas others are NP-complete. Recent research has
M.T. Cox / Artificial Intelligence 169 (2005) 104–141 127
made progress with respect to the problem nonetheless. A special issue of Artificial Intel- ligence [114] highlights this progress.19
One of the difficulties with earlier research such as Russell and Wefald’s [204,205] is that the estimate of the utility of computation they use is myopic. That is, they base a decision to deliberate further, on whether the net expected utility of the solution after com- putation minus the cost of time is greater than the expected utility of the current solution. However the performance profiles of anytime algorithms are not always certain; indeed they can vary considerably. Therefore alternative algorithms, such as Hansen and Zilber- stein’s [104] dynamic programming method that uses a more global utility estimate and that adds decisions about whether to monitor the state of the world or not at given points during the process, represent a more general and accurate treatment of the metareasoning problem.
Raja [188,189] also report progress related to the research of Harada and Russell using reinforcement learning techniques to generate a meta-level control policy that govern de- cisions in multiagent environments. They learn a meta-level MDP where the state consists of set of abstract qualitative features of a multiagent hierarchical task net (HTN) problem environment, the mental actions are processes such as scheduling a task and negotiating with another agent, and the reward function is the overall utility gained by the multiagent system as a result of the execution of the HTN plans. The system learns the MDP by mak- ing random decisions to collect state transition probabilities. Value iteration of Q-values computes an optimal meta-level policy. Finally, the system is re-implemented using the learned policy.
In contrast to advances such as those regarding metareasoning above, some recent re- search into introspective learning has strayed from its original formulation. Fox and Leake [86,87] originally defined and continue to emphasize [88] that introspective learning uses a model of the reasoning process to derive expectations concerning the behavior of the reasoning process. Thus by monitoring the reasoning process given these expectations, an introspective system can uncover failures that point to useful learning. As a result the sys- tem can adjust case indices to improve performance. However other researchers, such as Bonzano, Cunningham, and Smyth [19], interpret introspective learning as monitoring the results of problem solving in relation to an objective function and adjusting memory indices as a function of the comparison. But to do so is to revert to a more standard machine learn- ing perspective. They lack the emphasis on a declarative self-model of the reasoning that guides the detection of failure as opposed to an external objective function (specifically a training set of examples). This trend is continued by the research of Zhang and Yang [238] and of Coyle and Cunningham [56], still under the term of introspective learning where the learning is considered to be specific to learning index weights.
Others in the CBR community have successfully extended their previous research adding such constructs as meta-cases [171].20 Research that makes computational use
19 For a brief informal introduction to the research, see [202].
20 Notice the ambiguity of the term meta-case-based reasoning as used by Murdock and Goel. In their research
meta-cases represent general cases that contain information about functional model cases; hence it is a case about a case. Whereas as used by Leake [132], the term can be construed as case-based reasoning about the case-based reasoning process itself.
128 M.T. Cox / Artificial Intelligence 169 (2005) 104–141
of meta-rules continues into the present as well. See for example the work of Cazenave [21,28] and the implemented Introspect system used to solve problems in the game of Go. Hudlicka [115] also presents a novel implemented system that uses metacognition to me- diate the effects of emotion on deliberation for action selection. Her research is inspired by the many new developments in the psychological metacognition literature.
One of the most encouraging trends has been the new research efforts that take a cross- disciplinary approach (e.g., [4,99,177]) where each integrates computational methods with psychological or philosophical approaches. A prominent example is the work of Gordon and Hobbs [100,109]. They have undertaken the first-order logical representation of 30 commonsense domains of mental activities and strategies such as memory, knowledge management, envisionment, planning, goals, and execution monitoring. But rather than us- ing intuition to construct a competency formalism (c.f., [148,206]), they have performed a large-scale analysis of human planning protocols [99], to obtain independent coverage first. That is, the representation of a content theory of logical terms depends upon a cognitive analysis of a natural corpus of mental terms. Note that this is in contrast to a third method whereupon the representation depends upon theoretical assumptions about metacognition [44,55].21
Anderson and Perlis [6,7] also take a decidedly cognitive science direction. Anderson is a computationally-oriented philosopher by training who, from an embodied cognition perspective [3,4], has studied technical problems associated with representation of the self. Countering the claims that the self is essentially an indexical, Anderson argues that self-representing mental tokens structurally organize self-knowledge, having a biological underpinning related to somatoception in the body. Furthermore Anderson and Perlis [6] propose a computational theory of the “metacognitive loop” that accounts for improved performance in such behavioral components as reinforcement learning, robot navigation, and human-computer dialogue.
Most importantly many researchers have recently begun to work on significant archi- tectures that specifically support metacognitive layers of monitoring and control of delib- eration (i.e., cognition) of both inference and of memory. Examples include the work of Minsky, Sloman and colleagues (see [151,218]), Forbus and Hinrichs [83]), Anderson and Perlis [6], Schubert [209], and Cox [49]. Minsky and Sloman have proposed a three-level architecture that mediates perception and action through reactive, deliberative, and reflec- tive process layers. Forbus and Hinrichs [83] propose a new architecture for “companion cognitive systems” that employ psychologically plausible models of analogical learning and reasoning and that maintain self-knowledge in the form of logs of activity. Cox [49] proposes a preliminary architecture consisting of planning, understanding, and learning in which awareness is exhibited by an agent as it generates its own goals to change perceived anomalies in the world and in which self-awareness is exhibited as it generates explicit learning goals to change perceived anomalies in its own knowledge.
21 The representational content theories of mental states and actions developed by Schank et al., by Gordon and Hobbs, and by Cox and Ram are all at the knowledge level. Newell [173] used Schank’s conceptual dependency representation as a specific example of a theory at the knowledge level, and both Gordon and Cox use the exact same approach as did Schank.
M.T. Cox / Artificial Intelligence 169 (2005) 104–141 129
Singh [215] has recently created an architecture called EM-ONE, that supports layers of metacognitive activities that monitor reasoning in physical, social, and mental do- mains. These layers range from the reactive, deliberative, reflective, self-reflective, and self-conscious to the self-ideals layer. Mental critics are represented as a case base of commonsense narratives that associate specific situations with a method of debugging the situation. Critics themselves are selected and retrieved by an executive set of meta-level critics that detect and classify problems in the environment or within the system.
The metacognition community in psychology has recently started a novel line of re- search on metacognition and vision (see [134] in particular). Although some consider metacognition specifically related to higher order thought, this new research examines how people think about their own visual perception. Levin and Beck [135] demonstrate that not only do people overestimate their visual capabilities, but most interesting, given feedback on their errors, they refuse to believe the evidence “before their eyes”. For example humans will fail to perceive changes in clothing (e.g., a scarf that disappears) if the change occurs during video tape cuts or scene shifts. This robust effect is called change blindness. As Keil, Rosenblit, and Mills [119] notes, this effect may be related to the illusion of explana- tory depth, because human subjects do not fully understand the mechanisms behind their own visual perception, although they believe that they do.
Thus again I emphasize that metacognition in its many forms has limitations. As noted above in the general case metareasoning is intractable. But at the same time, it has the potential to provide a level of decision making that can make an intelligent system robust and tolerant of errors and of dynamic changing environments. As the twenty-first century opened, Bruce Buchanan in his AAAI Presidential Address [25] claimed that the meta-level of computation provides a principled basis for genuine creativity. Surveying the literature in creativity, he argued that the feature that is most characteristic of creativity is the ability to bring something novel into existence. The argument was that search at the meta-level enables the identification of choices that are most effective for successfully completing particular tasks. This search allows the reasoner to modify the ontological vocabulary, the criteria, and the methods used at the object level to make decisions. Finally it allows an intelligent agent to define new problems for itself. Given these kinds of attributes, agents might have the capacity to go beyond the limitations of intelligent systems of the past. Yet at the current time, this is still a distant dream. Or is it?
5. Summary and discussion
This paper outlined some of the research related to metacognition both from the artificial intelligence perspective and from the cognitive psychology point of view. This paper first examined psychological research into metacognition and human problems solving. It then described the genesis of interest in computational theories of introspection and metacog- nition during the formative years of AI. The logic community has a large part to play in this early research, because they established a formalism (and a legitimacy) for the repre- sentation of mental states and belief, including beliefs about a system’s own beliefs. I also examined the research of the expert system community and others that have developed in- trospective systems, but take a different approach. I also discussed systems that combine
130 M.T. Cox / Artificial Intelligence 169 (2005) 104–141
metacognitive theories with model-based reasoning, case-based reasoning, and theories of learning. Finally I examined a set of more recent papers on all of these subjects that have been published since the turn of the century.
The computational community should take note of the results from other disciplines concerning metacognition. For example it is enticing to design an organized memory or knowledge base so that it is “indexed” to answer queries concerning the contents of mem- ory. Indeed Nilsson [175] begins his section on Meta-Knowledge with “We would like to be able to build systems that know or can deduce whether or not they know facts and rules about certain subjects without having to scan their large knowledge bases searching for these items”. After all humans exhibit tip-of-the-tongue behavior, so this sounds reason- able.
However Reder and Ritter [195] argue that such behavior (e.g., game-show events where people have to quickly hit a buzzer, if they think they can answer a question), is tied to fa- miliarity with the questions rather than with the answers. This has important ramifications for those researchers like Nilsson wishing to build systems with metaknowledge. It indi- cates that direct access to memory content may not be fruitful and that inferential measures such as cue familiarity or current access to related concepts may provide a better measure (see the discussion in [74], for why these alternatives work with humans). In any case knowing the metacognitive literature and the human data can point computer scientists toward new possibilities and warn them about potential pitfalls.
Conversely Ghetti [96] provides recent evidence to support Hayes’ proposed metarea- soning strategy about television scan lines discussed at the beginning of the section on model-based and case-based reasoning.22 That is Ghetti showed that humans infer event nonoccurrences from the premise that, if they did occur, then the event would be mem- orable. Because they do not immediately retrieve the fact, they therefore must not know it. Regardless, computer scientists should have a working knowledge of the psychological literature on metacognition to provide evidence for or against their intuitions concerning the mental abilities of humans.
Yet many ambiguities and conflicting evidence exist within all of the disciplines enu- merated here. Often, authors use different terms for the same concept (e.g., introspection and reflection23), and sometimes the same terms are used in different ways (e.g., metacog- nition is a multiple overloaded term). Indeed, Brown [24] has described research into metacognition as a “many-headed monster of obscure parentage.” This characterization applies equally as well to the many AI approaches that deal with metacognition, metarea- soning, and metaknowledge and the relationships between each of them.
Finally, both metacognition theory and computational theories address the issue con- cerning a person’s ability to assess the veracity of their own responses. In addition, because a person has a feeling of knowing, even when recall is blocked, the agent can make efficient use of search. Search and elaboration is pursued when an item is on the “tip of the tongue” and abandoned when an item is judged unfamiliar. This search heuristic provides some con-
22 Moore [168] uses the same logic in his example of autoepistemic reasoning whereby one concludes the lack of an older brother given that the experience of having such a brother would be saliently represented and given the lack of an assertion concerning a brother in the knowledge base.
23 Although note that I have differentiated these two terms when discussing Minsky’s use of M* and M**.
M.T. Cox / Artificial Intelligence 169 (2005) 104–141 131
trol of memory and helps to alleviate the combinatorial explosion of inferences [127,157]. Although people sometimes make spurious and biased inferences when assessing their own memories and reasoning, these inferences nonetheless affect people’s decisions and thus are important components when understanding human decision-making.
By some measures, few people are working on metacognition, but in another sense used by some in the AI community, everyone in AI must be working on introspection and metareasoning. Most intelligent programs deliberate to some extent about the types of actions that are optimal given their goals. For example, Soar [174,199,200], Theo [165], and PRODIGY [27,230] are all programs that make deliberate control decisions as to the best action available in their domains. Moreover, if metaknowledge were taken to be any abstract knowledge (e.g., default knowledge), and metareasoning is any of the higher cog- nitive functions (e.g., planning), then virtually all AI programs would be metacognitive. Instead I echo Maes’ assessment that an introspective system is one whose domain is itself [138]. But in essence a metacognitive reasoner is a system that reasons specifically about itself (its knowledge, beliefs, and its reasoning process), not one that simply uses such knowledge.24
It needs to be better appreciated just how extensive the research is on metacognitive aspects of intelligent behavior. Indeed I have been forced to omit much important research such as the work on metacognitive monitoring in high-level perception and analogy (e.g., [141,142]), active logic [75] and more generally logic programming (but see [41]), models of introspective distributed agents (e.g., [143]), self-adaptive software (e.g., [198]) and BDI agents that reconsider intentions using decision-theoretic metareasoning [210,211]. But much of the past research covered in this paper contains valuable lessons to teach us and provides firm foundations with which to make progress in our individual fields of expertise. In any case and as is with all careful research, we should be aware of the work that has preceded us, if for nothing else than to prevent ourselves from reinventing the wheel or repeating past failures.
Acknowledgements
I thank David Leake and Mike Anderson for recent comments on the content of this article. I also thank the anonymous reviewers for their insights and suggestions. This paper started with a literature search for a paper [43] that was originally written for a graduate school seminar in metacognition and cognitive aging taught by Chris Hertzog at Georgia Tech. Over the years many people have provided me with pointers into the various liter- atures and feedback on portions of the material contained here. For a rather large set of acknowledgments see [46]. Because the material I cover is so broad, I necessarily have both sins of omission as well as commission in the historical references. See also the In- trospection home page that I maintain on an irregular basis: hcs.bbn.com/cox/Introspect/.
24 Thus systems that use metaknowledge are not necessarily metacognitive. For example metaknowledge con- cerning the properties of constraints may assist CSP solvers to be more efficient in terms of reducing the number of arc consistency checks [15], but I assert that such algorithms in isolation should not be included in metacogni- tion in computing activities.
132 M.T. Cox / Artificial Intelligence 169 (2005) 104–141
References
[1] J.R. Anderson, The Architecture of Cognition, Harvard Univ. Press, Cambridge, MA, 1983.
[2] J.R. Anderson, R. Thompson, Use of analogy in a production system architecture, in: S. Vosniadou, A. Ortony (Eds.), Similarity and Analogical Reasoning, Cambridge Univ. Press, Cambridge, 1989, pp. 267–
297.
[3] M.L. Anderson, How to study the mind: An introduction to embodied cognition, in: F. Santoianni,
C. Sabatano (Eds.), Brain Development in Learning Environments: Embodied and Perceptual Advance-
ments, Cambridge Univ. Press, New York, in press.
[4] M.L. Anderson, Embodied cognition: A field guide, Artificial Intelligence 149 (1) (2003) 91–130.
[5] M.L. Anderson, T. Oates (Eds.), Metacognition in Computation: Papers from 2005 AAAI Spring Sympo-
sium, AAAI Press, Menlo Park, CA, 2005, AAAI Technical Report SS-05-04.
[6] M.L. Anderson, D.R. Perlis, Logic, self-awareness and self-improvement: The metacognitive loop and the
problem of brittleness, J. Logic Comput. 15 (1) (2005) 21–40.
[7] M.L. Anderson, D.R. Perlis, The roots of self-awareness, in: Phenomenology and the Cognitive Sciences,
in press.
[8] C. Antaki, A. Lewis (Eds.), Mental Mirrors: Metacognition in Social Knowledge and Communication,
Sage Publications, London, 1986.
[9] G. Attardi, M. Simi, Reflections about reflection, in: J. Allen, R. Fikes, E. Sandewall (Eds.), Principles
of Knowledge Representation and Reasoning: Proceedings of the 2nd International Conference (KR91),
Morgan Kaufmann, San Mateo, CA, 1991.
[10] A. Augustine, De Trinitate, in: J. Burnaby (Ed.), Augustine: Later Works, in: Library of Christian Classics,
Bk. 10, Sec. 7, vol. 8, SCM Press, 1955. Transl. by J. Burnaby, original work published around 1600.
[11] A. Barr, Meta-knowledge and memory, Technical Report, HPP-77-37, Stanford University, Department of
Computer Science, Stanford, CA, 1977.
[12] A. Barr, Meta-knowledge and cognition, in: Proceedings of the Sixth International Joint Conference on
Artificial Intelligence, Morgan Kaufmann, Los Altos, CA, 1979, pp. 31–33.
[13] J. Batali, Computational introspection, Technical Report, 701, Artificial Intelligence Laboratory, Massa-
chusetts Institute of Technology, Cambridge, MA, 1983.
[14] B. Berardi-Coletta, L.S. Buyer, R.L. Dominowski, R.E. Rellinger, Metacognition and problem-solving:
A process-oriented approach, J. Experimental Psychology: Learning, Memory, and Cognition 21 (1) (1995)
205–223.
[15] C. Bessiere, E.C. Freuder, J.-C. Regin, Using constraint metaknowledge to reduce arc consistency compu-
tation, Artificial Intelligence 107 (1999) 125–148.
[16] S. Bhatta, Model-based analogy in innovative device design, Ph.D. Dissertation, College of Computing,
Georgia Institute of Technology, Atlanta, 1995.
[17] S. Bhatta, A. Goel, Use of mental models for constraining index learning in experience-based design, in:
Proceedings of the AAAI-92 Workshop on Constraining Learning with Prior Knowledge, 1992.
[18] L. Birnbaum, G. Collins, M. Freed, B. Krulwich, Model-based diagnosis of planning failures, in: Proceed- ings of the Eighth National Conference on Artificial Intelligence, AAAI Press, Menlo Park, CA, 1990,
pp. 318–323.
[19] A. Bonzano, P. Cunningham, B. Smyth, Using introspective learning to improve retrieval in CBR: A case
study in air traffic control, in: D.B. Leake, E. Plaza (Eds.), Case-Based Reasoning Research and Develop-
ment: Second International Conference on Case-Based Reasoning, Springer, Berlin, 1997, pp. 291–301.
[20] E.G. Boring, A history of introspection, Psychological Bull. 50 (3) (1953) 169–189.
[21] B. Bouzy, T. Cazenave, Computer Go: An AI oriented survey, Artificial Intelligence 132 (2001) 39–103.
[22] R.J. Brachman, Systems that know what they are doing, IEEE Intelligent Systems (Nov/Dec.) (2002) 67–
71.
[23] P.B. Brazdil, K. Konolige (Eds.), Machine Learning, Meta-Reasoning and Logics, Kluwer Academic, Nor-
well, MA, 1990.
[24] A. Brown, Metacognition, executive control, self-regulation, and other more mysterious mechanisms, in:
F.E. Weinert, R.H. Kluwe (Eds.), Metacognition, Motivation, and Understanding, LEA, Hillsdale, NJ, 1987, pp. 65–116.
M.T. Cox / Artificial Intelligence 169 (2005) 104–141 133
[25] B.G. Buchanan, Creativity at the meta-level: AAAI-2000 presidential address, AI Magazine 22 (3) (2000) 13–28.
[26] J.G. Carbonell, Derivational analogy: A theory of reconstructive problem solving and expertise acquisition, in: R. Michalski, J. Carbonell, T. Mitchell (Eds.), Machine Learning: An Artificial Intelligence Approach, vol. 2, Morgan Kaufmann, San Mateo, CA, 1986, pp. 371–392.
[27] J.G. Carbonell, C.A. Knoblock, S. Minton, PRODIGY: An integrated architecture for planning and learn- ing, in: K. VanLehn (Ed.), Architectures of Cognition: The 22nd Carnegie Mellon Symposium on Cogni- tion, LEA, Hillsdale, NJ, 1991, pp. 241–278.
[28] T. Cazenave, Metarules to improve tactical go knowledge, Inform. Sci. 154 (3–4) (2003) 173–188.
[29] S.J. Ceci (Ed.), Handbook of Cognitive, Social, and Neuropsychological Aspects of Learning Disabilities,
vol. 2, LEA, Hillsdale, NJ, 1987.
[30] J. Cheng, Management of speedup mechanisms in learning architectures, Technical Report, CMU-CS-95-
112, Ph.D. Dissertation, School of Computer Science, Carnegie Mellon University, Pittsburgh, 1995.
[31] M.T.H. Chi, Representing knowledge and metaknowledge: Implications for interpreting metamemory re- search, in: F.E. Weinert, R.H. Kluwe (Eds.), Metacognition, Motivation, and Understanding, LEA, Hills-
dale, NJ, 1987, pp. 239–266.
[32] M.T.H. Chi, Revising the mental model as one learns, Plenary address to the Seventeenth Annual Confer-
ence of the Cognitive Science Society, Pittsburgh, July 23, 1995.
[33] M.T.H. Chi, M. Bassok, M. Lewis, P. Reimann, R. Glasser, Self-explanations: How students study and use
examples in learning to solve problems, Cognitive Science 13 (1989) 145–182.
[34] W.J. Clancey, The knowledge engineer as student: metacognitive bases for asking good questions, Tech- nical Report, STAN-CS-87-1183, Department of Computer Science, Stanford University, Stanford, CA,
1987.
[35] W.J. Clancey, Model construction operators, Artificial Intelligence 53 (1992) 1–115.
[36] W.J. Clancey, C. Bock, Representing control knowledge as abstract task and metarules, Technical Report,
STAN-CS-87-1168, Department of Computer Science, Stanford University, Stanford, CA, 1985.
[37] P. Cointe (Ed.), Meta-Level Architectures and Reflection: Second International Conference, Reflection ‘99,
Springer, Berlin, 1999.
[38] G. Collins, Plan creation: Using strategies as blueprints, Technical Report, 599, Ph.D. Dissertation, Depart-
ment of Computer Science, Yale University, New Haven, CT, 1987.
[39] G. Collins, L. Birnbaum, B. Krulwich, M. Freed, The role of self-models in learning to plan, in: A. Mey-
rowitz (Ed.), Machine Learning: Induction, Analogy and Discovery, Kluwer Academic, Boston, 1993.
[40] V. Conitzer, T. Sandholm, Definition and complexity of some basic metareasoning problems, in: G. Gottlob, T. Walsh (Eds.), Proceedings of the 18th International Joint Conference on Artificial Intelligence (IJCAI-
03), Morgan Kaufmann, San Francisco, CA, 2003, pp. 1099–1106.
[41] S. Costantini, Meta-reasoning: A survey, in: A. Kakas, F. Sadri (Eds.), Computational Logic: From Logic
Programming into the Future (Special volume in honour of Bob Kowalski), Springer, Berlin, 2002.
[42] M.T. Cox, Machines that forget: Learning from retrieval failure of mis-indexed explanations, in: A. Ram, K. Eiselt (Eds.), Proceedings of the Sixteenth Annual Conference of the Cognitive Science Society, LEA,
Hillsdale, NJ, 1994, pp. 225–230.
[43] M.T. Cox, Metacognition, problem solving and aging, Cognitive Science Tech. Rep. No. 15, Atlanta, Geor-
gia Institute of Technology, College of Computing, 1994.
[44] M.T. Cox, Representing mental events (or the lack thereof), in: M.T. Cox, M. Freed (Eds.), Proceedings of
the 1995 AAAI Spring Symposium on Representing Mental States and Mechanisms, AAAI Press, Menlo
Park, CA, 1995, pp. 22–30. Available as Technical Report SS-95-08.
[45] M.T. Cox, An empirical study of computational introspection: Evaluating introspective multistrategy learn-
ing in the meta-AQUA system, in: R.S. Michalski, J. Wnek (Eds.), Proceedings of the Third International
Workshop on Multistrategy Learning, AAAI Press/MIT Press, Menlo Park, CA, 1996, pp. 135–146.
[46] M.T. Cox, Introspective multistrategy learning: Constructing a learning strategy under reasoning failure, Technical Report, GIT-CC-96-06. Ph.D. Dissertation, College of Computing, Georgia Institute of Technol-
ogy, Atlanta, 1996, hcs.bbn.com/cox/thesis/.
[47] M.T. Cox, An explicit representation of reasoning failures, in: D.B. Leake, E. Plaza (Eds.), Case-Based Rea-
soning Research and Development: Second International Conference on Case-Based Reasoning, Springer, Berlin, 1997, pp. 211–222.
134 M.T. Cox / Artificial Intelligence 169 (2005) 104–141
[48] M.T. Cox, Loose coupling of failure explanation and repair: Using learning goals to sequence learning methods, in: D.B. Leake, E. Plaza (Eds.), Case-Based Reasoning Research and Development: Second In- ternational Conference on Case-Based Reasoning, Springer, Berlin, 1997, pp. 425–434.
[49] M.T. Cox, Perpetual self-aware cognitive agents, in: M. Anderson, T. Oates (Eds.), Metacognition in Com- putation: Papers from 2005 AAAI Spring Symposium, AAAI Press, Menlo Park, CA, 2005, pp. 42–48, Technical Report SS-05-04.
[50] M.T. Cox, M. Freed, Using knowledge from cognitive behavior to learn from failure, in: J.W. Brahan, G.E. Lasker (Eds.), Proceedings of the Seventh International Conference on Systems Research, Informatics and Cybernetics, vol. 2, Advances in Artificial Intelligence—Theory and Application II, The International Institute for Advanced Studies in Systems Research and Cybernetics, Windsor, Ontario, Canada, 1994, pp. 142–147.
[51] M.T. Cox, M. Freed (Eds.), Proceedings of the 1995 AAAI Spring Symposium on Representing Mental States and Mechanisms, AAAI Press, Menlo Park, CA, 1995, Technical Report SS-95-08.
[52] M.T. Cox, A. Ram, Using introspective reasoning to select learning strategies, in: R.S. Michalski, G. Tecuci (Eds.), Proceedings of the First International Workshop on Multistrategy Learning, George Mason Univer- sity, Artificial Intelligence Center, Washington, DC, 1991, pp. 217–230.
[53] M.T. Cox, A. Ram, Multistrategy learning with introspective meta-explanations, in: D. Sleeman, P. Edwards (Eds.), Machine Learning: Ninth International Conference, Morgan Kaufmann, San Mateo, CA, 1992, pp. 123–128.
[54] M.T. Cox, A. Ram, Interacting learning-goals: Treating learning as a planning task, in: J.-P. Haton, M. Keane, M. Manago (Eds.), Advances in Case-Based Reasoning, Springer, Berlin, 1995, pp. 60–74.
[55] M.T. Cox, A. Ram, Introspective multistrategy learning: On the construction of learning strategies, Artifi-
cial Intelligence 112 (1999) 1–55.
[56] L. Coyle, P. Cunningham, Improving recommendation rankings by learning personal feature weights, Tech-
nical Report TCD-CS-2004-21. The University of Dublin, Trinity College, Ireland, 2004.
[57] J.E. Davidson, R. Deuser, R.J. Sternberg, The role of metacognition in problem solving, in: J. Metcalfe,
A.P. Shimamura (Eds.), Metacognition, The MIT Press, Cambridge, MA, 1994, pp. 207–226.
[58] D.N. Davis, Visions of Mind: Architectures for Cognition and Affect, Idea Group Inc, Hershey, PA, in
press.
[59] R. Davis, Applications of meta-level knowledge to the construction, maintenance, and use of large knowl-
edge bases, Stanford HPP Memo 76-7, Stanford University, 1976.
[60] R. Davis, Interactive transfer of expertise: Acquisition of new inference rules, Artificial Intelligence 12
(1979) 121–157.
[61] R. Davis, Meta-rules: Reasoning about control, Artificial Intelligence 15 (1980) 179–222.
[62] R. Davis, B. Buchanan, Meta-level knowledge: Overview and applications, in: Proceedings of the Fifth
International Joint Conference on Artificial Intelligence, Morgan Kaufmann, Los Altos, CA, 1977, pp. 920–
927.
[63] T. Dean, M. Boddy, An analysis of time-dependent planning, in: T.M. Mitchell, R.G. Smith (Eds.), Pro-
ceedings of the Seventh National Conference on Artificial Intelligence, AAAI Press, Menlo Park, CA,
1988, pp. 49–54.
[64] J. de Kleer, J.S. Brown, Assumptions and ambiguities in mechanistic mental models, in: A. Collins,
E.E. Smith (Eds.), Readings in Cognitive Science: A Perspective from Psychology and Artificial Intel-
ligence, Morgan Kaufmann, San Mateo, CA, 1988, pp. 49–54. Original work published 1983.
[65] J. de Kleer, How circuits work, Artificial Intelligence 24 (1984) 205–280.
[66] J. de Kleer, J. Doyle, G.L. Steele, G.J. Sussman, Explicit control of reasoning, SIGPLAN Notices 12
(1977).
[67] V.R. Delclos, C. Harrington, Effects of strategy monitoring and proactive instruction on children’s problem-
solving performance, J. Educational Psychology 83 (1) (1991) 35–42.
[68] D.C. Dennett, Brainstorms: Philosophical Essays on Mind and Psychology, MIT Press/Bradford Books,
Cambridge, MA, 1978.
[69] S.J. Derry, Strategy and expertise in solving word problems, in: C.B. McCormick, G.E. Miller, M. Pressley
(Eds.), Cognitive Strategy Research: From Basic Research to Educational Applications, Springer, Berlin, 1989, pp. 269–302.
M.T. Cox / Artificial Intelligence 169 (2005) 104–141 135
[70] R.L. Dominowski, Verbalization and problem solving, in: D.L. Hacker, J. Dunlosky, A. Graesser (Eds.), Metacognition in Educational Theory and Practice, Lawrence Erlbaum Associates, Mahwah, NJ, 1998, pp. 25–45.
[71] D. Dörner, Self-reflection and problem-solving, in: F. Klix (Ed.), Human and Artificial Intelligence, North- Holland, Amsterdam, 1979, pp. 101–107.
[72] J. Doyle, A truth maintenance system, Artificial Intelligence 12 (1979) 231–272.
[73] J. Doyle, A model for deliberation, action, and introspection, Technical Report, TR-581, Ph.D. Dissertation,
Department of Computer Science, Massachusetts Institute of Technology, Cambridge, MA, 1980.
[74] A. Dunlosky, Metacognition, in: A. Hunt, A. Ellis (Eds.), Fundamentals of Cognitive Psychology, seventh
ed., McGraw-Hill, New York, 2004, pp. 232–262.
[75] J. Elgot-Drapkin, D. Perlis, Reasoning situated in time I: Basic concepts, J. Experiment. Theoret. Artificial
Intelligence 2 (1990) 75–98.
[76] R.L. Epstein, W.A. Carnielli, Computability: Computable Functions, Logic, and the Foundations of Math-
ematics, Wadsworth and Brooks, Pacific Grove, CA, 1989.
[77] O. Etzioni, Embedding decision-analytic control in a learning architecture, Artificial Intelligence 49 (1991)
129–159.
[78] E. Fink, Automatic representation changes in problem solving, Technical Report, CMU-CS-99-150, Ph.D.
Thesis, Computer Science Department, Carnegie Mellon University, 1999.
[79] E. Fink, How to solve it automatically: Selection among problem-solving methods, in: Proceedings of the
Fourth International Conference on Artificial Intelligence Planning Systems, 1998, pp. 128–136.
[80] J.H. Flavell, First discussant’s comments: What is memory development the development of?, Human
Development 14 (1971) 272–278.
[81] J.H. Flavell, Metacognitive aspects of problem solving, in: A. Resnick (Ed.), The Nature of Intelligence,
LEA, Hillsdale, NJ, 1976, pp. 231–235.
[82] J.H. Flavell, H.M. Wellman, Metamemory, in: R.V. Kail, J.W. Hagen (Eds.), Perspectives on the Develop-
ment of Memory and Cognition, LEA, Hillsdale, NJ, 1977, pp. 3–33.
[83] K. Forbus, T. Hinrichs, Companion cognitive systems: A step towards human-level AI, in: AAAI Fall
Symposium on Achieving Human-level Intelligence through Integrated Systems and Research, Washing-
ton, DC, October 2004.
[84] D.L. Forrest-Pressley, G.E. MacKinnon, T.G. Waller (Eds.), Metacognition, Cognition and Human Perfor-
mance (vol. 2, Instructional Practices), Academic Press, New York, 1985.
[85] S. Fox, Introspective learning for case-based planning, Unpublished, Ph.D. Dissertation, Department of
Computer Science, Indiana University, Bloomington, IN, 1995.
[86] S. Fox, D. Leake, Modeling case-based planning for repairing reasoning failures, in: M.T. Cox, M. Freed
(Eds.), Proceedings of the 1995 AAAI Spring Symposium on Representing Mental States and Mechanisms,
AAAI Press, Menlo Park, CA, 1995, pp. 31–38. Available as Technical Report SS-95-08.
[87] S. Fox, D. Leake, Using introspective reasoning to refine indexing, in: C.S. Mellish (Ed.), Proceedings of the Fourteenth International Joint Conference on Artificial Intelligence, Morgan Kaufmann, San Mateo,
CA, 1995, pp. 391–397.
[88] S. Fox, D. Leake, Introspective reasoning for index refinement in case-based reasoning, J. Experiment.
Theoret. Artificial Intelligence 13 (2001) 63–88.
[89] M. Freed, G. Collins, Learning to cope with task interactions, in: A. Ram, M. desJardins (Eds.), Proceedings
of the 1994 AAAI Spring Symposium on Goal-Driven Learning, AAAI Press, Menlo Park, CA, 1994,
pp. 28–35.
[90] M. Freed, B. Krulwich, L. Birnbaum, G. Collins, Reasoning about performance intentions, in: Proceedings
of Fourteenth Annual Conference of the Cognitive Science Society, LEA, Hillsdale, NJ, 1992, pp. 7–12.
[91] B. Fischhoff, P. Slovic, S. Lichtenstein, Knowing with certainty: The appropriateness of extreme confi-
dence, J. Experimental Psychol.: Human Perception and Performance 3 (4) (1977) 552–564.
[92] R. Garner, Metacognition and Reading Comprehension, Ablex Publishing Corporation, Norwood, NJ,
1987.
[93] J.R. Gavelek, T.E. Raphael, Metacognition, instruction, and the role of questioning activities, in:
D.L. Forrest-Pressley, G.E. MacKinnon, T.G. Waller (Eds.), Metacognition, Cognition and Human Per- formance (vol. 2, Instructional Practices), Academic Press, New York, 1987, pp. 103–136.
136 M.T. Cox / Artificial Intelligence 169 (2005) 104–141
[94] M.R. Genesereth, An overview of meta-level architecture, in: Proceedings of the Third National Conference on Artificial Intelligence, William Kaufmann, Los Altos, CA, 1983, pp. 119–123.
[95] A.M. Glenberg, A.C. Wilkinson, W. Epstein, The illusion of knowing: Failure in the self-assessment of comprehension, in: T.O. Nelson (Ed.), Metacognition: Core Readings, Allyn and Bacon, Boston, 1992, pp. 185–195. Original work published 1982.
[96] S. Ghetti, Memory for nonoccurrences: The role of metacognition, J. Memory and Language 48 (4) (2003) 722–739.
[97] J.E. Gombert, Metalinguistic Development, University of Chicago Press, Chicago, 1992.
[98] I.J. Good, Twenty-seven principles of rationality, in: V.P. Godambe, D.A. Sprott (Eds.), Foundations of
Statistical Inference, Hold, Rinehart, Winston, Toronto, 1971.
[99] A.S. Gordon, Strategy Representation: An Analysis of Planning Knowledge, LEA, Mahwah, NJ, 2004.
[100] A.S. Gordon, J.R. Hobbs, Formalizations of commonsense psychology, AI Magazine 25 (4) (2004) 49–62.
[101] K.J. Hammond, Case-based Planning: Viewing Planning as a Memory Task, vol. 1, Perspectives in Artifi-
cial Intelligence, Academic Press, San Diego, CA, 1989.
[102] K.J. Hammond, Explaining and repairing plans that fail, Artificial Intelligence 45 (1990) 173–228.
[103] E.A. Hansen, S. Zilberstein, Monitoring anytime algorithms, ACM SIGART Bull. 7 (2) (1996) 28–33.
[104] E.A. Hansen, S. Zilberstein, Monitoring and control of anytime algorithms: A dynamic programming ap-
proach, Artificial Intelligence 126 (1–2) (2001) 139–157.
[105] D. Harada, S.J. Russell, Extended abstract: Learning search strategies, in: W. Zhang, S. Koenig (Eds.),
Search Techniques for Problem Solving under Uncertainty and Incomplete Information: Papers from the AAAI Spring Symposium, AAAI Press, Menlo Park, CA, 1999, pp. 48–52, AAAI Technical Report SS- 99-07.
[106] J. Haugeland (Ed.), Artificial Intelligence: The Very Idea, MIT Press, Cambridge, MA, 1985.
[107] P.J. Hayes, The logic of frames, in: B.L. Webber, N.J. Nilsson (Eds.), Readings in Artificial Intelligence,
Morgan Kaufmann, Los Altos, CA, 1981, pp. 451–458. Original work published 1979.
[108] F. Hayes-Roth, D.A. Waterman, D.B. Lenat (Eds.), Building Expert Systems, Addison-Wesley, London,
1983.
[109] J.R. Hobbs, A.S. Gordon, Toward a large-scale formal theory of commonsense psychology for metacog-
nition, in: M. Anderson, T. Oates (Eds.), Metacognition in Computation: Papers from 2005 AAAI Spring
Symposium, AAAI Press, Menlo Park, CA, 2005, pp. 49–54, Technical Report SS-05-04.
[110] D.R. Hofstadter, Gödel, Escher, Bach: An Eternal Golden Braid, Vintage Books, New York, 1989. Original
work published in 1979.
[111] J. Horty, Y. Shoham (Eds.), Proceedings of the 1993 AAAI Spring Symposium on Reasoning about Mental
States: Formal Theories and Applications, AAAI Press, Menlo Park, CA, 1993.
[112] E. Horvitz, Reasoning about beliefs and actions under computational resource constraints, in: Proceedings of the Third Workshop on Uncertainty in Artificial Intelligence, Seattle, Washington, 1987, pp. 429–444. Also in: L. Kanal, T. Levitt, J. Lemmer (Eds.), Uncertainty in Artificial Intelligence 3, Elsevier, Amsterdam,
1990, pp. 301–324.
[113] E.J. Horvitz, G. Cooper, D. Heckerman, Reflection and action under scarce resources: Theoretical prin-
ciples and empirical study, in: Proceedings of the Eleventh International Joint Conference on Artificial
Intelligence, Morgan Kaufmann, Los Altos, CA, 1989.
[114] E. Horvitz, S. Zilberstein, Special issue on computational tradeoffs under bounded resources, Artificial
Intelligence 126 (1–2) (2001).
[115] E. Hudlicka, Modeling interaction between metacognition and emotion in cognitive architectures, in:
M. Anderson, T. Oates (Eds.), Metacognition in Computation: Papers from 2005 AAAI Spring Sympo-
sium, AAAI Press, Menlo Park, CA, 2005, pp. 55–61, Technical Report SS-05-04.
[116] P.N. Johnson-Laird, Mental Models: Toward a Cognitive Science of Language, Inference, and Conscious-
ness, Cambridge University Press, Cambridge, 1983.
[117] P.N. Johnson-Laird, The Computer and the Mind: An Introduction to Cognitive Science, Harvard Univer-
sity Press, Cambridge, MA, 1988.
[118] A. Kass, Developing creative hypotheses by adapting explanations, Ph.D. Dissertation, The Institute for
the Learning Sciences, Northwestern University, Evanston, IL, 1990.
[119] F. Keil, L. Rosenblit, C.M. Mills, What lies beneath? Understanding the limits of understanding, in:
D.T. Levin (Ed.), Thinking and Seeing, MIT Press, Cambridge, MA, 2004, pp. 227–249.
[120] [121]
[122] [123]
[124]
[125]
[126]
[127]
[128] [129]
[130]
[131] [132] [133]
[134] [135]
[136] [137]
[138] [139]
[140] [141]
[142]
[143] [144] [145] [146]
M.T. Cox / Artificial Intelligence 169 (2005) 104–141 137
J.L. Kolodner, Case-Based Reasoning, Morgan Kaufmann, San Mateo, CA, 1993.
K. Konolige, A Computational theory of belief introspection, in: Proceedings of the Ninth International Joint Conference on Artificial Intelligence, Morgan Kaufmann, Los Altos, CA, 1985, pp. 502–508.
K. Konolige, A Deduction Model of Belief, Morgan Kaufmann, Los Altos, CA, 1986.
K. Konolige, Reasoning by introspection, in: P. Maes, D. Nardi (Eds.), Meta-Level Architectures and Re- flection, North-Holland, Amsterdam, 1988, pp. 61–74.
B. Krulwich, Determining what to learn in a multi-component planning system, in: Proceedings of the Thirteenth Annual Conference of the Cognitive Science Society, Chicago, IL, August 7–10, 1991, pp. 102–107.
B. Krulwich, Flexible learning in a multicomponent planning system, Technical Report, 46, Ph.D. Disser- tation, The Institute for the Learning Sciences, Northwestern University, Evanston, IL, 1993.
D.R. Kuokka, The deliberative integration of planning, execution, and learning, Technical Report, CMU- CS-90-135, Ph.D. Dissertation, Computer Science Dept., Carnegie Mellon University, Pittsburgh, 1990. J.L. Lachman, R. Lachman, C. Thronesbery, Metamemory through the adult life span, Developmental Psychology 15 (5) (1979) 543–551.
R. Laddaga, Self-adaptive software, DARPA Solicitation BAA 98-12, 1998.
M.G. Lagoudakis, M.L. Littman, R. Parr, Selecting the right algorithm, in: C. Gomes, T. Walsh (Eds.), Proceedings of the 2001 AAAI Fall Symposium Series: Using Uncertainty within Computation, AAAI Press, Menlo Park, CA, 2001.
M.G. Lagoudakis, R. Parr, M.L. Littman, Least-squares methods in reinforcement learning for control, in: Proceedings of the 2nd Hellenic Conference on Artificial Intelligence, in: Lecture Notes on Artificial Intelligence, vol. 2308, Springer, Berlin, 2002, pp. 249–260.
D.B. Leake, Case-Based Reasoning: Experiences, Lessons, & Future Directions, AAAI Press/MIT Press, Menlo Park, CA, 1996.
D.B. Leake, Experience, introspection, and expertise: Learning to refine the case-based reasoning process, J. Experiment. Theoret. Artificial Intelligence 8 (3–4) (1996) 319–339.
D.B. Lenat, R. Davis, J. Doyle, M. Genesereth, I. Goldstein, H. Schrobe, Reasoning about reasoning, in: F. Hayes-Roth, D.A. Waterman, D.B. Lenat (Eds.), Building Expert Systems, Addison-Wesley, London, 1983, pp. 219–239.
D.T. Levin (Ed.), Thinking and Seeing, MIT Press, Cambridge, MA, 2004.
D.T. Levin, M.R. Beck, Thinking about seeing: spanning the difference between metacognitive failure and success, in: D.T. Levin (Ed.), Thinking and Seeing, MIT Press, Cambridge, MA, 2004, pp. 121–143.
W. Lyons, The Disappearance of Introspection, Bradford Books/MIT Press, Cambridge, MA, 1986.
P. Maes, Computational reflection, Technical Report, 87-2, Ph.D. Dissertation, Artificial Intelligence Lab- oratory, Vrije Universiteit Brussels, Belgium, 1987.
P. Maes, Introspection in knowledge representation, in: B. Du Boulay, D. Hogg, L. Steels (Eds.), Advances in Artificial Intelligence—II, North-Holland, Amsterdam, 1987, pp. 249–262.
P. Maes, Issues in computational reflection, in: P. Maes, D. Nardi (Eds.), Meta-Level Architectures and Reflection, North-Holland, Amsterdam, 1988, pp. 21–35.
P. Maes, D. Nardi (Eds.), Meta-Level Architectures and Reflection, North-Holland, Amsterdam, 1988.
J. Marshall, Metacat: A self-watching cognitive architecture for analogy-making and high-level perception, Ph.D. Dissertation, Indiana University, Bloomington, 1999.
J. Marshall, D. Hofstadter, Making sense of analogies in Metacat, in: K. Holyoak, D. Gentner, B. Kokinov (Eds.), Advances in Analogy Research: Integration of Theory and Data from the Cognitive, Computational, and Neural Sciences, Springer, Berlin, 1998.
C. Mason, Introspection as control in result-sharing assumption-based reasoning agents, in: International Workshop on Distributed Artificial Intelligence, Lake Quinalt, WA, 1994.
J. McCarthy, Programs with common sense, in: Symposium Proceedings on Mechanisation of Thought Processes, vol. 1, Her Majesty’s Stationary Office, London, 1959, pp. 77–84.
J. McCarthy, Programs with common sense, in: M.L. Minsky (Ed.), Semantic Information Processing, MIT Press, Cambridge, MA, 1968, pp. 403–418.
J. McCarthy, Ascribing mental qualities to machines, in: M. Ringle (Ed.), Philosophical Perspectives in Artificial Intelligence, Humanities Press, Atlantic Highlands, NJ, 1979, pp. 161–195.
138
[147] [148]
[149] [150] [151] [152]
[153] [154]
[155] [156]
[157]
[158] [159] [160]
[161] [162] [163]
[164] [165]
[166] [167]
[168] [169] [170]
[171]
M.T. Cox / Artificial Intelligence 169 (2005) 104–141
J. McCarthy, Notes on formalizing context, in: R. Bajcsy (Ed.), Proceedings of the Thirteenth International Joint Conference on Artificial Intelligence, vol. 1, Morgan Kaufmann, San Mateo, CA, 1993, pp. 555–560. J. McCarthy, Making robots conscious of their mental states, in: M.T. Cox, M. Freed (Eds.), Proceedings of the 1995 AAAI Spring Symposium on Representing Mental States and Mechanisms, AAAI Press, Menlo Park, CA, 1995, pp. 89–96. Available as Technical Report SS-95-08.
J. McCarthy (chair), V. Chaudri (co-chair), DARPA Workshop on Self Aware Computer Systems, SRI Headquarters, Arlington, VA, April 27–28, 2004.
J. McCarthy, P. Hayes, Some philosophical problems from the standpoint of artificial intelligence, Machine Intelligence 4 (1969) 463–502.
J. McCarthy, M. Minsky, A. Sloman, L. Gong, T. Lau, L. Morgenstern, E. Meuller, D. Riecken, M. Singh, P. Singh, An architecture of diversity for commonsense reasoning, IBM Systems J. 41 (3) (2002) 530–539. T.P. McNamara, D.L. Miller, J.D. Bransford, Mental models and reading comprehension, in: R. Barr, M.L. Kamil, P. Mosenthal, P.D. Pearson (Eds.), Handbook of Reading Research, vol. 2, Longman, New York, 1991, pp. 490–511.
J. Metcalfe, Metamemory: Theory and data, in: E. Tulving, F.I.M. Craik (Eds.), The Oxford Handbook of Memory, Oxford University Press, New York, 2000, pp. 197–211.
J. Metcalfe, Cognitive optimism: self-deception or memory-based processing heuristics?, in: J. Metcalfe (Ed.), Personality and Social Psychology Review 2 (2) (1998) 100–110, special issue: Metacognition.
J. Metcalfe (Ed.), Special issue: Metacognition, Personality and Social Psychology Review 2 (2) (1998). T. Metzinger, D.J. Chalmers, Selected Bibliography, Consciousness in Philosophy, Cognitive Science and Neuroscience: 1970–1995, Imprint Academic, Schoning, UK, 1995, Appendix I in: T. Metzinger (Ed.), Conscious Experience.
A.C. Miner, L.M. Reder, A new look at feeling of knowing: Its metacognitive role in regulating ques- tion answering, in: J. Metcalfe, A.P. Shimamura (Eds.), Metacognition: Knowing about Knowing, MIT Press/Bradford Books, Cambridge, MA, 1994, pp. 47–70.
M.L. Minsky, Steps towards artificial intelligence, in: E.A. Feigenbaum, J. Feldman (Eds.), Computers and Thought, McGraw-Hill, New York, 1963, pp. 406–450. Original work published 1961.
M.L. Minsky, Matter, mind, and models, in: Proceedings of the International Federation of Information Processing Congress, vol. 1, 1965, pp. 45–49.
M.L. Minsky, Matter, mind, and models, in: M.L. Minsky (Ed.), Semantic Information Processing, MIT Press, Cambridge, MA, 1968, pp. 425–432.
M.L. Minsky (Ed.), Semantic Information Processing, MIT Press, Cambridge, MA, 1968.
M.L. Minsky, The Society of Mind, Simon and Schuster, New York, 1985.
M. Minsky, P. Singh, A. Sloman, The St. Thomas common sense symposium: Designing architectures for human-level intelligence, AI Magazine (2004) 113–124.
S. Minton, Learning Search Control Knowledge: A Explanation-Based Approach, Kluwer Academic, Boston, 1988.
T.M. Mitchell, J. Allen, P. Chalasani, J. Cheng, O. Etzioni, M. Ringuette, J.C. Schlimmer, Theo: A frame- work for self-improving systems, in: K. VanLehn (Ed.), Architectures of Cognition: The 22nd Carnegie Mellon Symposium on Cognition, LEA, Hillsdale, NJ, 1991, pp. 323–355.
T.M. Mitchell, R. Keller, S. Kedar-Cabelli, Explanation-based generalization: A unifying view, Machine Learning 1 (1) (1986) 47–80.
R. Mooney, D. Ourston, A multistrategy approach to theory refinement, in: R.S. Michalski, G. Tecuci (Eds.), Machine Learning IV: A Multistrategy Approach, Morgan Kaufmann, San Francisco, CA, 1994, pp. 141–164.
R.C. Moore, Semantical considerations on nonmonotonic logic, Artificial Intelligence 25 (1) (1985) 75–94. R.C. Moore, Logic and Representation, CSLI Publications, Stanford, CA, 1995.
J.W. Murdock, A theory of reflective agent evolution, Technical Report, GIT-CC-98-27, Ph.D. Proposal, College of Computing, Georgia Institute of Technology, Atlanta, 1998.
J.W. Murdock, A. Goel, Meta-case-based reasoning: Using functional models to adapt case-based agents, in: D.W. Aha, I. Watson, Q. Yang (Eds.), Case-Based Reasoning Research and Development: Proceed- ings of the 4th International Conference on Case-Based Reasoning, ICCBR-2001, Springer, Berlin, 2001, pp. 407–421.
[172]
[173] [174] [175] [176]
[177] [178]
[179]
[180]
[181] [182]
[183] [184]
[185] [186]
[187] [188] [189] [190] [191] [192]
[193] [194] [195] [196]
[197] [198]
[199]
M.T. Cox / Artificial Intelligence 169 (2005) 104–141 139
T.O. Nelson, L. Narens, Metamemory: A theoretical framework and new findings, in: T.O. Nelson (Ed.), Metacognition: Core Readings, Allyn and Bacon, Boston, 1992, pp. 9–24. Originally published in 1990. A. Newell, The knowledge level, Artificial Intelligence 18 (1982) 87–127.
A. Newell, Unified Theories of Cognition, Harvard University Press, Cambridge, MA, 1990.
N. Nilsson, Principles of Artificial Intelligence, Morgan Kaufmann, Los Altos, CA, 1980.
R.E. Nisbett, T. Wilson, Telling more than we can know: Verbal reports on mental processes, Psychological Rev. 84 (3) (1977) 231–259.
R. Oehlmann, Metacognitive and computational aspects of chance discovery, New Gen. Comput. 21 (1) (2003) 3–12.
R. Oehlmann, P. Edwards, D. Sleeman, Changing the viewpoint: Re-indexing by introspective questioning, in: A. Ram, K. Eiselt (Eds.), Proceedings of the Sixteenth Annual Conference of the Cognitive Science Society, LEA, Hillsdale, NJ, 1994, pp. 675–680.
R. Oehlmann, P. Edwards, D. Sleeman, Introspection planning: Representing metacognitive experience, in: M.T. Cox, M. Freed (Eds.), Proceedings of the 1995 AAAI Spring Symposium on Representing Mental States and Mechanisms, AAAI Press, Menlo Park, CA, 1995, pp. 102–110. Available as Technical Report SS-95-08.
C. Owens, Indexing and retrieving abstract planning knowledge, Ph.D. Dissertation, Department of Com- puter Science, Yale University, New Haven, 1990.
D. Perlis, Languages with self-reference I: Foundations, Artificial Intelligence 25 (1985) 301–322.
D. Perlis, Languages with self-reference II: Knowledge, belief and modality, Artificial Intelligence 34 (2) (1988) 179–212.
D. Perlis, Theory and application of self-reference: Logic and beyond, CSLI, in press.
P. Pirolli, M. Recker, Learning strategies and transfer in the domain of programming, Cognition and In- struction 12 (3) (1994) 235–275.
J.L. Pollock, How to Build a Person, MIT Press/Bradford Books, Cambridge, MA, 1989.
J.L. Pollock, OSCAR: A general theory of rationality, J. Experiment. Theoret. Artificial Intelligence 1 (1989) 209–226.
M. Pressley, D. Forrest-Pressley, Questions and children’s cognitive processing, in: A.C. Graesser, J.B. Black (Eds.), The Psychology of Questions, LEA, Hillsdale, NJ, 1985, pp. 277–296.
A. Raja, Meta-level control in multi-agent systems, Ph.D. Dissertation, Department of Computer Science, University of Massachusetts, Amherst, MA, 2003.
A. Raja, V. Lessor, Meta-level reasoning in deliberative agents, in: Proceedings of the International Con- ference on Intelligent Agent Technology, IEEE Computer Society, Piscataway, NJ, 2004, pp. 141–147.
A. Ram, Indexing, elaboration and refinement: Incremental learning of explanatory cases, Machine Learn- ing 10 (1993) 201–248.
A. Ram, AQUA: Questions that drive the understanding process, in: R.C. Schank, A. Kass, C.K. Riesbeck (Eds.), Inside Case-Based Explanation, LEA, Hillsdale, NJ, 1994, pp. 207–261.
A. Ram, M.T. Cox, Introspective reasoning using meta-explanations for multistrategy learning, in: R.S. Michalski, G. Tecuci (Eds.), Machine Learning: A Multistrategy Approach IV, Morgan Kaufmann, San Mateo, CA, 1994, pp. 349–377.
A. Ram, D. Leake, Learning, goals, and learning goals, in: A. Ram, D. Leake (Eds.), Goal-Driven Learning, MIT Press/Bradford Books, Cambridge, MA, 1995, pp. 1–37.
M. Recker, P. Pirolli, Modeling individual differences in student’s learning, J. Learning Sci. 4 (1) (1995) 1–38.
L.M. Reder, F. Ritter, What determines initial feeling of knowing? Familiarity with question terms, not with the answer, J. Experimental Psychology 18 (3) (1992) 435–451.
L.M. Reder, C.D. Schunn, Metacognition does not imply awareness: Strategy choice is governed by im- plicit learning and memory, in: L. Reder (Ed.), Implicit Memory and Metacognition, LEA, Mahwah, NJ, 1996, pp. 45–77.
J.R. Rice, The algorithm selection problem, Advances in Computers 15 (1976) 65–118.
P. Robertson, Confidence from self knowledge and domain knowledge, in: Self-Adaptive Software: Appli- cations, in: Lecture Notes in Comput. Sci., vol. 2614, Springer, Berlin, 2003.
P.S. Rosenbloom, J.E. Laird, A. Newell, Metalevels in SOAR, in: P. Maes, D. Nardi (Eds.), Meta-Level Architectures and Reflection, North-Holland, Amsterdam, 1989, pp. 227–240.
140
[200]
[201] [202]
[203] [204]
[205] [206]
[207] [208]
[209]
[210]
[211]
[212]
[213] [214]
[215]
[216] [217]
[218] [219]
[220]
[221] [222]
[223] [224]
[225]
[226] [227]
M.T. Cox / Artificial Intelligence 169 (2005) 104–141
P.S. Rosenbloom, J.E. Laird, A. Newell (Eds.), The Soar Papers: Research on Integrated Intelligence, MIT Press, Cambridge, MA, 1993.
S.J. Russell, Rationality and intelligence, Artificial Intelligence 94 (1997) 57–77.
S.J. Russell, Metareasoning, in: R.A. Wilson, F.C. Keil (Eds.), The MIT Encyclopedia of the Cognitive Sci- ences (MITECS), Bradford Books/MIT Press, Cambridge, 1999. Also available at http://cognet.mit.edu/. S.J. Russell, D. Subramanian, Provably bounded-optimal agents, J. Artificial Intelligence Res. 2 (1995) 575–609.
S.J. Russell, E. Wefald, Do the Right Thing: Studies in Limited Rationality, MIT Press, Cambridge, MA, 1991.
S.J. Russell, E. Wefald, Principles of metareasoning, Artificial Intelligence 49 (1991) 361–395.
R.C. Schank, N. Goldman, C. Rieger, C.K. Riesbeck, Primitive concepts underlying verbs of thought, Stanford Artificial Intelligence Project Memo No. 162, Stanford University, Computer Science Department, Stanford, CA, 1972, NTIS No. AD744634.
R.C. Schank, A. Kass, C.K. Riesbeck, Inside Case-Based Explanation, LEA, Hillsdale, NJ, 1994.
W. Schneider, Developmental trends in the metamemory-memory behavior relationship: An integrative re- view, in: D.L. Forrest-Pressley, G.E. MacKinnon, T.G. Waller (Eds.), Metacognition, Cognition and Human Performance, vol. 1, Theoretical Perspectives, Academic Press, New York, 2005, pp. 57–109.
L.K. Schubert, Some KR&R requirements for self-awareness, in: M. Anderson, T. Oates (Eds.), Metacog- nition in Computation: Papers from 2005 AAAI Spring Symposium, AAAI Press, Menlo Park, CA, 2005, pp. 106–113, Technical Report SS-05-04.
M. Schut, M. Wooldridge, Principles of intention reconsideration, in: Proceedings of the 5th International Conference on Autonomous Agents, Montreal, Quebec, Canada, 2001, pp. 340–347.
M.C. Schut, M.J. Wooldridge, S.D. Parsons, The theory and practice of intention reconsideration, J. Exper- iment. Theoret. Artificial Intelligence 6 (4) (2004) 261–293.
P.J. Schwanenflugel, W.V. Fabricius, C.R. Noyes, K.D. Bigler, J.M. Alexander, The organization of mental verbs and folk theories of knowing, J. Memory and Language 33 (1994) 376–395.
H.A. Simon, A behavioral model of rational choice, Quarterly J. Econom. 69 (1955) 99–118.
H.A. Simon, Models of Bounded Rationality: Behavioral Economics and Business Organization, vol. 2, MIT Press, Cambridge, MA, 1982.
P. Singh, EM-ONE: An architecture for reflective commonsense thinking, Ph.D. Dissertation, Department of Electrical Engineering and Computer Science, Massachusetts Institute of Technology, Boston, MA, 2005.
B.F. Skinner, Are theories of learning necessary?, Psychological Rev. 57 (1950) 193–216.
B.F. Skinner, What is psychotic behavior?, in: F. Gildea (Ed.), Theory and Treatment of the Psychoses: Some Newer Aspects, Washington University Press, St. Louis, 1956.
A. Sloman, Beyond shallow models of emotion, Cognitive Processing 1 (1) (2001).
B.C. Smith, Prologue to Reflection and semantics in a procedural language, in: R.J. Brachman, H.J. Levesque (Eds.), Readings in Knowledge Representation, Morgan Kaufmann, San Mateo, CA, 1985, pp. 31–40. Original work published 1982.
G. Stein, J.A. Barnden, Towards more flexible and common-sensical reasoning about beliefs, in: M.T. Cox, M. Freed (Eds.), Proceedings of the 1995 AAAI Spring Symposium on Representing Mental States and Mechanisms, AAAI Press, Menlo Park, CA, 1995, pp. 127–135. Available as Technical Report SS-95-08. E. Stroulia, Failure-driven learning as model-based self-redesign, Ph.D. Dissertation, College of Comput- ing, Georgia Institute of Technology, Atlanta, 1994.
E. Stroulia, A.K. Goel, Functional representation and reasoning in reflective systems, Applied Intelli- gence 9 (1) (1995) 101–124, special issue on Functional Reasoning.
G.J. Sussman, A Computer Model of Skill Acquisition, American Elsevier, New York, 1975.
H.L. Swanson, Influence of metacognitive knowledge and aptitude on problem solving, J. Educational Psychol. 82 (2) (1990) 306–314.
J. Tash, S. Russell, Control strategies for a stochastic planner, in: Proceedings of the Twelfth National Conference on Artificial Intelligence, II, MIT Press, Cambridge, MA, 1994, pp. 1079–1085.
E.B. Titchener, The schema of introspection, Amer. J. Psychol. 23 (4) (1912) 485–508.
K. VanLehn, W. Ball, B. Kowalski, Explanation-based learning of correctness: Towards a model of the self-explanation effect, in: Proceedings of the 12th Annual Conference of the Cognitive Science Society, LEA, Hillsdale, NJ, 1990.
[228]
[229]
[230]
[231]
[232] [233]
[234]
[235] [236]
[237] [238]
[239] [240]
M.T. Cox / Artificial Intelligence 169 (2005) 104–141 141
K. VanLehn, R.M. Jones, M.T.H. Chi, A model of the self-explanation effect, J. Learning Sci. 2 (1) (1992) 1–60.
M. Veloso, J.G. Carbonell, Case-based reasoning in PRODIGY, in: R.S. Michalski, G. Tecuci (Eds.), Ma- chine Learning IV: A Multistrategy Approach, Morgan Kaufmann, San Francisco, CA, 1994, pp. 523–548. M. Veloso, J.G. Carbonell, A. Perez, E. Borrajo, D. Fink, J. Blythe, Integrating planning and learning: The PRODIGY architecture, J. Theoret. Experiment. Artificial Intelligence 7 (1) (1995) 81–120.
J. Von Neumann, O. Morgenstern, Theory of Games and Economic Behavior, John Wiley and Sons, New York, 1944.
J.B. Watson, Psychology from the Standpoint of the Behaviorist, J.B. Lippincott, Philadelphia, PA, 1919. H.M. Wellman, Metamemory revisited, in: M.T.H. Chi (Ed.), Contributions to Human Development, vol. 9, Trends in memory development research, S. Karger, AG, Basel, Switzerland, 1983.
H.M. Wellman, The origins of metacognition, in: D.L. Forrest-Pressley, G.E. MacKinnon, T.G. Waller (Eds.), Metacognition, Cognition and Human Performance, vol. 1, Theoretical Perspectives, Academic Press, New York, 1985, pp. 1–31.
H.M. Wellman, The Child’s Theory of Mind, MIT Press, Cambridge, MA, 1992.
T.D. Wilson, J.W. Schooler, Thinking too much: Introspection can reduce the quality of preferences and decisions, J. Personality Social Psychol. 60 (2) (1991) 181–192.
S.R. Yussen (Ed.), The Growth of Reflection in Children, Academic Press, New York, 1985.
Z. Zhang, Q. Yang, Feature weight maintenance in case bases using introspective learning, J. Intelligent Inform. Syst. 16 (2001) 95–116.
S. Zilberstein, Operational rationality through compilation of anytime algorithms, Ph.D. Dissertation, Uni- versity of California at Berkeley, 1993.
S. Zilberstein, S.J. Russell, Optimal composition of real-time systems, Artificial Intelligence 82 (1–2) (1996) 181–213.