This paper reviews the history of process-dependent reasoning in AI systems, and argues that it represents an essentially different approach to non-monotonic reasoning from other formalizations. Much of the paper is a basic level tutorial, explaining the issues and providing a framework for understanding the essential features of non-monotonic reasoning.

'Non-monotonic' logical systems are logics in which the introduction of new axioms can invalidate old theorems. Such logics are very important in modeling the benefits of active processes which, acting in the presence of incomplete information, must make and subsequently revise assumptions in light of new observations. We present the motivation and history of such logics. We develop model and proof theories, a proof procedure, and applications for one non-monotonic logic. In particular, we prove the completeness of the non-monotoic predicate calculus and the decidability of the non-monotonic sentential calculus. We also discuss characteristic properties of this logic and its relationship to stronger logics, logics of incomplete information, and truth maintenance systems. Artificial Intelligence 13:41-72.

This paper describes a model of cooperative behavior and describes how such a model can be applied in a natural language understanding system. We assume that agents attempt to recognize the plans of other agents and, then, use this plan when deciding what response to make. In particular, we show that, given a setting in which purposeful dialogues occur, this model can account for responses that provide more information that explicitly requested and for appropriate responses to both short sentence fragments and indirect speech acts.

In this paper we explore the number of tree search operations required to solve binary constraint satisfaction problems. We show analytically and experimentally that the two principles of first trying the places most likely to fail and remembering what has been done to avoid repeating the same mistake twice improve the standard backtracking search. We experimentally show that a lookahead procedure called forward checking (to anticipate the future) which employs the most likely to fail principle performs better than standard backtracking, Ullman's, Waltz's, Mackworth's, and Haralick's discrete relaxation in all cases tested, and better than Gaschnig's backmarking in the larger problems.

This paper explores the truism that people think about what they say. It proposes that, to satisfy their own goals, people often plan their speech acts to affect their listeners' beliefs, goals, and emotional states. Such language use can be modelled by viewing speech acts as operators in a planning system, thus allowing both physical and speech acts to be integrated into plans. Methodological issues of how speech acts should be defined in a plan-based theory are illustrated by defining operators for requesting and informing. Plans containing those operators are presented and comparisons are drawn with Searle's formulation.

How can we insure that knowledge embedded in a program is applied effectively? Traditionally the answer to this question has been sought in different problem solving paradigms and in different approaches to encoding and indexing knowledge. Each of these is useful with a certain variety of problem, but they all share a common problem: they become ineffective in the face of a sufficiently large knowledge base. How then can we make it possible for a system to continue to function in the face of a very large number of plausibly useful chunks of knowledge? In response to this question we propose a framework for viewing issues of knowledge indexing and retrieval, a framework that includes what appears to be a useful perspective on the concept of a strategy. We view strategies as a means of controlling invocation in situations where traditional selection mechanisms become ineffective. We examine ways to effect such control, and describe meta-rules, a means of specifying strategies which offers a number of advantages. We consider at some length how and when it is useful to reason about control, and explore the advantages meta-rules offer for doing this. Artificial Intellligence 15:179-222.

I am struck by how little is known about so much of cognition. One goal of this paper is to argue for the need to consider a rich set of interlocking issues in the study of cognition. Mainstream work in cognition—including my own—ignores many critical aspects of animate cognitive systems. Perhaps one reason that existing theories say so little relevant to real world activities is the neglect of social and cultural factors, of emotion, and of the major points that distinguish an animate cognitive system from an artificial one: the need to survive, to regulate its own operation, to maintain itself, to exist in the environment, to change from a small, uneducated, immature system to an adult, developed, knowledgeable one. Human cognition is not the same as artificial cognition, if only because the human organism must also be concerned with the problems of life, of development, of survival.

The problem of region segmentation includes issues varying from the preprocessing of the image to its semantic interpretation. Rather than surveying various research activities technique by technique (such as merge/split or semantic/nonsemantic), this paper tries to give a unified view of this problem. We first briefly present a model of image understanding to provide a paradigm in which the problem of region segmentation can be discussed. The model enables us to identify three levels of knowledge—signal, physical, and semantic—which play different roles in achieving the goals of region segmentation. For each level of knowledge, the development of research in that level is first reviewed, then its important issues are discussed. This paper emphasizes the importance of exploiting the physical level of knowledge, the bridge between a picture and a scene.

If a generation system is to produce text in response to a given communicative goal, it must be able to determine what to include in its text and how to organize this information so that it can be easily understood. In this paper, a computational model of discourse strategies is presented that can be used to guide the generation process in its decisions about what to say next. The model is based on an analysis of naturally occurring texts and represents strategies that can be used for three communicative goals: define, compare, and describe. We show how this model has been implemented in text, a system which generates paragraph-length responses to questions about database structure.

"The contract net protocol has been developed to specify problem-solving communication and control for nodes in a distributed problem solver. Task distribution is affected by a negotiation process, a discussion carried on between nodes with tasks to be executed and nodes that may be able to execute those tasks. We present the specification of the protocol and demonstrate its use in the solution of a problem in distributed sensing. The utility of negotiation as an interaction mechanism is discussed. It can be used to achieve different goals, such as distributing control and data to avoid bottlenecks and enabling a finer degree of control in making resource allocation and focus decisions than is possible with traditional mechanisms." IEEE Transactions on Computers C-29(12):1104-1113. PDF: http://www.reidgsmith.com/The_Contract_Net_Protocol_Dec-1980.pdf.