DEVELOPMENT OF A COMPUTATIONAL COGNITIVE AGENT
Stuart C. Shapiro, Director
William J. Rapaport, Associate Director
SNePS Research Group
Department of Computer Science
State University of New York at Buffalo
Buffalo, NY 14260
shapiro@cs.buffalo.edu, rapaport@cs.buffalo.edu
December 15, 1993
The Principal Investigators in the SNePS Research Group are:
Stuart C. Shapiro, Ph.D. Professor Department of Computer Science State University of New York at Buffalo (716) 645-3935 shapiro@cs.buffalo.edu William J. Rapaport, Ph.D. Associate Professor Department of Computer Science State University of New York at Buffalo (716) 645-3193 rapaport@cs.buffalo.edu Jeannette G. Neal, Ph.D. Principal Scientist Calspan Advanced Technology Center Buffalo, NY 14225 (716) 631-6844 neal@cs.buffalo.edu
This interest has led to research in: (1) knowledge representation, especially in the representation of entities that tend to be discussed in natural language, such as objects of other agents' beliefs, impossible and fictitious entities, intensional entities, and collections, which maintain their individualities over changes in their members; (2) non-standard logics that are closer to commonsense reasoning than logics developed for the foundations of mathematics; (3) reasoning methods that are insensitive to order of rules or even to circularities, that act reasonably in the presence of inconsistencies, and that learn with experience; (4) methods of natural-language parsing, understanding, and production; and (5) the interface between reasoning and acting. This last interest has led to two large projects in which we have developed intelligent systems that act in the world. The first was an intelligent Human-Computer Interface that used speech, text, graphics, and pointing. The most recent is an intelligent robot that includes a camera for an eye, an arm, and a hand.
1. The SNePS Semantic Network Processing System, a knowledge- representation and reasoning system that allows one to design, implement, and use specific knowledge-representation constructs, and that easily supports nested beliefs, meta-knowledge, and meta-reasoning.
2. SNIP, the SNePS Inference Package, which interprets rules represented in SNePS, performing bi-directional inference, a mixture of forward chaining and backward chaining that focuses its attention on the topic at hand. SNIP can make use of universal, existential, and numerical quantifiers and a specially-designed set of propositional connectives that includes both true negation and negation-by-failure.
3. Path-Based Inference, a very general method of defining inheritance rules by specifying that the existence of an arc in a SNePS network may be inferred from the existence of a path of arcs specified by a sentence of a ``path language'' defined by a regular grammar. Path-based reasoning is fully integrated into SNIP.
4. SNeBR, the SNePS Belief Revision system, based on SWM, the only extant, worked-out logic of assumption-based belief revision.
5. A Generalized Augmented Transition Network inter- preter/compiler that allows the specification and use of a combined parsing-generation grammar, which can be used to parse a natural-language sentence into a SNePS network, generate a natural-language sentence from a SNePS network, and perform any needed reasoning along the way.
6. A theory of Fully Intensional Knowledge Representation, ac- cording to which we are developing knowledge-representation constructs and grammars for the Computational Cognitive Mind. This theory also affects the development of successive versions of SNePS and SNIP. For instance, the insight we developed into the intensional nature of rule variables led us to design a restricted form of unification that cuts down on the search space generated by SNIP during reasoning.
7. CASSIE, the Computational Cognitive Mind we are developing and experimenting with, successive versions of which represent an integration of all our current work.
1. Intelligent Multi-Media Interfaces:
The goal of this project is to develop techniques for the intelligent, integrated use of text, graphics, pointing, and speech for interactions between computer systems and humans. We are pursuing the notion that these modalities can be considered syntactic variations within the competance of a single language facility, similar to the choices represented by adjectives vs. relative clauses vs. separate sentences. This project is being carried out in cooperation with a team from the Calspan Advanced Technology Center under the auspices of the Calspan-UB Research Center (CUBRC), and has been supported in part by the Defense Advanced Research Projects Agency, monitored by the Rome Air Development Center.
2. Cognitive and Computer Systems for Understanding Narrative Text:
The goal of this project is to understand the use of deictic terms (e.g., me/you, here/there, now/then) in third-person narratives. We have proposed the existence of a ``deictic center'', from which the reader views the action of the narrative, and which the reader tracks as it moves across characters and through space and time during the course of the narrative. We are studying the linguistic devices that indicate changes in the deictic center, and how readers notice the changes and make use of the deictic center to understand the story. This is an interdisciplinary project involving linguistic analysis, psychological experimentation, and computer modeling, being pursued by members of the SUNY Buffalo Center for Cognitive Science, and has been supported in part by the National Science Foundation.
3. The Representation of Natural Category Systems and Their Role in Natural-Language Processing:
The goal of this project is to take seriously the unique nature of basic-level categories within natural category systems, as discovered by Eleanor Rosch and others, and to examine the implications of this for knowledge representation and natural-language processing. Issues affected by this distinction include choice of category name when generating descriptive phrases, inheritance within the category system, and implicit introduction of referents into a discourse.
4. Experience-Based Learning in Deductive Reasoning Systems:
We are developing schemes that allow deductive reasoning systems to learn from and exploit previous experience, and consequently to make future reasoning more efficient and more effective. Both the wide applicability of general knowledge and the speed of specific knowledge are achieved by managing a multi-level knowledge structure and developing techniques for ``migrating'' general knowledge to specific knowledge and preventing general knowledge from being used when specific knowledge migrated from it is available and applicable. By these techniques, the system is able to decide the best possible branch in a deduction tree by choosing an appropriate rule among many applicable rules. Learning and reasoning are integrated by managing learning modules as subcomponents of the inference engine in a reasoning system.
5. Interactive Generation of Plan Descriptions and Justifications:
This research concerns planning discourse to justify and describe domain plans in an interactive setting. Plan description is a task undertaken by a speaker to have a user know a plan. In contrast, plan justification is used to have a user accept a plan. The discourse plan that our system incrementally formulates and executes to try to achieve its discourse objective is represented uniformly in the same knowledge base with the plans that are under discussion. In this way, the discourse plan and the domain plan are both accessible for analyzing the user's responses. As a testbed for the model, we are implementing a system that interactively gives driving directions and route advice.
6. Grounded Layered Architecture with Integrated Reasoning:
(GLAIR) is an agent architecture that specifies general principles of organization of components for an autonomous agent that functions in the world. GLAIR specifies an integration of explicit representation and reasoning mechanisms, embodied semantics through grounding symbols in perception and action, mechanisms for finding and maintaining a correspondence between symbols and sensory- perceived objects, and implicit representations of special- purpose mechanisms of sensory processing, perception, and motor control for the agent. Several projects are underway for developing robotic autonomous agents as well as computer simulated agents. These agents are developed in accordance with the principles of the GLAIR architecture and display a variety of integrated behaviors and learning.
7. A Computational Model of Color Perception and Color Naming:
The immediate goal of this project is to define and implement a computational model of human color perception and color naming, which will allow an artificial cognitive agent equipped with such a model and a color camera to (1) name colors in its environment, (2) point out examples in its environment of colors named by an interlocutor, and (3) learn new names for colors in its environment. The focus is on basic color terms, but non-basic terms are of interest as well. The deeper motivation for the project is to study how perception can function as the grounding for symbolic concepts, or how symbolic concepts can be embodied in an agent's organism. Color was chosen as a promising domain to study these questions. The model being developed will be implemented in a robotic autonomous agent, the Robot Waiter, which conforms to the principles of a general architecture for autonomous agents, GLAIR (Grounded Layered Architecture with Integrated Reasoning).
8. ``Natural Logic'' for Natural Language Processing and Knowledge Representation:
We are specifying a knowledge- representation and inference formalism that is particularly well-suited to natural-language processing tasks. In this formalism, every term of a formula is closed. The need for this property is motivated by the observation that any language with (potentially) open sentences is an inappropriate medium for the representation of natural- language sentences. Open sentences in such languages are a consequence of the separation of quantifier and type constraints on variables from these variables, typically in the antecedents of rules. In contrast, variables in natural language are constructions, such as noun phrases, that are typed and quantified as they are used. A consequence of this is that variables in natural language may be freely re-used in dialog. In language, this leads to the use of pronouns and discourse phenomena such as ellipsis involving reuse of entire subformulas. We are augmenting the representation of variables so that variables are not atomic terms. These ``structured'' variables are typed and quantified as they are defined/used. This has three important consequences with respect to natural language. First, this leads to an extended, more ``natural'' formalism whose use and representations are consistent with the use of variables in natural language (e.g., allowing re-use phenomena such as pronouns and ellipsis). Secondly, the formalism allows the specification of terminological subsumption as a partial ordering on related concepts (variable nodes in a semantic network) that relates more general concepts to more specific instances of that concept, as is done in language. Finally, this structured variable representation simplifies the resolution of some representational difficulties with certain classes of natural language sentences: donkey sentences and sentences involving branching quantifiers.
9. From Beliefs and Goals to Intentions and Actions---An Amalgamated Model of Inference and Acting:
We are building an intelligent Belief-Desire-Intention architecture to model rational cognitive agents that are capable of representing and reasoning about beliefs, actions, and plans. The modeled agents are also capable of planning, acting, reacting, and natural-language interaction. A survey of AI systems capable of some of the above faculties reveals that it is somewhat awkward to do planning and acting in systems designed for reasoning about beliefs, and similarly it is awkward to study representational and reasoning issues in planning/acting systems. An investigation of the relationships among beliefs, plans, effective acts, and sensory acts, and between reasoning and acting, in the context of a rational cognitive agent underlies this research. We define a object-oriented, unified knowledge-representation formalism that includes special representations (called transformers) that are capable of representing reasoning rules, plan decompositions, reactions, and other beliefd$ act transformations. A rational engine (as opposed to an inference engine), responsible for the modeled agent's reasoning and acting behavior, is defined in terms of methods (or messages) over the representations. A message-passing model is employed to facilitate concurrency. As a result, this work also contributes to the emerging paradigm of concurrent object-oriented programming. For an implementation, we have extended the ontology of SNePS and enhanced the SNePS inference engine into SNeRE---the SNePS Rational Engine. The resulting integrated architecture is an intensional, propositional, semantic-network--based system that includes capabilities for path-based inference (a generalization of inheritance inference), logical reasoning, belief revision, acting, planning, plan decomposition and elaboration, reacting, and natural language interaction.
10. Issues of Semantics in a Semantic Network Representation of Belief:
We are investigating the application of non-well- founded set theory to the problem of providing a formal semantics for semantic-network knowledge representation systems (such as SNePS) that embrace circular meanings, or mutually dependent semantic influence, in the informal or presumed semantics of its representational structures. Non-well-founded sets are mathematical structures based on standard set theory to the degree that only one of the several axioms commonly used to define the notion of a ``set'' has to be replaced with a non-standard statement; thus, much of the mechanism of set theory is still available. Non-well-founded sets, however, can include themselves, as represented by graphs with cycles, and can analogously provide a way to model the meaning of a network node that depends on the meanings of others that, in turn, depend on it.
11. Representing and Reasoning about Collections:
The ability to represent plural entities, collections, is crucial for knowledge-representation formalisms, since descriptions of collections occur in natural-language utterances as often as descriptions of singular entities. The objective of this research is to provide intensional knowledge- representation schemata for collections of various types, in order to facilitate inferences about collections and their constituents. Collections are more difficult to deal with than singular entities in knowledge representation and reasoning, since a collection involves constituents that may or may not be specified. We are investigating different representational schemata for various types of collections and developing inference mechanisms associated with them. We examine the effectiveness of the representational schemata by illustrating representations of several propositions with collections, which demonstrate the ability to represent different interpretations of collection predicates, co-referential collections, collection sizes, and variable collections as used in planning. The inference mechanisms include inheritance of properties of a collection to its constituent, inheritance of properties through hierarchical structure, unification, handling the size of a collection, and numerous collection operations such as union and intersection.
12. Automatic Acquisition of Word Meanings from Natural-Language Contexts:
We are developing a computational theory of a cognitive agent's ability to acquire word meanings from natural-language contexts, especially from narrative. The meaning of a word as understood by such an agent is taken to be its relation to the meanings of other words in a highly interconnected network representing the agent's knowledge. However, because such knowledge is very idiosyncratic, we are researching the means by which an agent can abstract conventional definitions from its individual experiences with a word. We are investigating the nature of information necessary to the production of such conventional definitions, and the processes of revising hypothesized definitions in the light of successive encounters with a word. The theory is being tested by implementing it in a knowledge-representation and reasoning system with facilities both for parsing and generating fragments of natural language (English) and for reasoning and belief revision. Potential applications include education, computational lexicography, and cognitive science studies of narrative understanding.
13. Reasoning with Nested Beliefs:
The goal of this project is to develop a reasoning mechanism for the ascription of beliefs to cognitive agents that utilizes representations that explicitly describe some of their beliefs. The approach taken is that of simulative reasoning, in which a simulating agent (simulator) puts itself into the position of a simulated agent (simulee) by virtue of hypothetically assuming the beliefs it believes are held by the simulee. Having done so, the simulator can try to infer new information from the assumed beliefs by attributing its own reasoning abilities to the simulee, thus simulating the simulee's reasoning. The result of such a simulation can then be ascribed to the simulee as one of its beliefs, even though there might be no explicit evidence for the simulee holding that belief. The main problem to be addressed is that belief ascription is defeasible. In general, one can never be sure whether some cognitive agent actually holds a certain belief, even though it might follow from beliefs that are known to be held by that agent. As a consequence of that, the belief-ascription mechanism has to account for conflicts arising from differences between explicitly available (directly acquired) beliefs of cognitive agents and relevant simulation results, conflicts arising from inconsistent models of simulated agents, etc. Among other problems to be addressed are proper handling of arbitrary levels of belief nesting and smooth integration of the simulation process with the simulator's own reasoning. Application areas for a belief ascription mechanism of this kind include plan recognition, intelligent user interfaces, computer-aided instruction, and game playing.
14. A Cognitive Linguistics Approach to Natural Language Understanding:
We are investigating the applicability of Cognitive Linguistics to the field of computational natural-language understanding. In particular, we are developing a natural-language--understanding system based on major Cognitive Linguistic principles, concentrating particularly on the following important principles: (1) The grammatical elements of a sentence determine the majority of the structure of the mental representation of the sentence, while the lexical elements contribute the majority of the content of its mental representation. (2) Nevertheless, the separation of lexicon and grammar into different components is arbitrary. (3) Grammar, i.e., patterns for grouping meaning elements into progressively larger configurations, is itself meaningful. Furthermore, virtually all grammatical elements are meaningful. Thus, there can be no formal grammar (i.e., without respect to meaning) within the human mind. (4) Grammatical constructions of a given language encode meanings which are specific to that particular language.
------------ how to ftp bibliography files ------------
41 (hadar) > ftp ftp.cs.buffalo.edu Connected to talos.cs.buffalo.edu. 220 talos.cs.Buffalo.EDU FTP server (SunOS 4.1) ready. Name (ftp.cs.buffalo.edu:hans): anonymous 331 Guest login ok, send ident as password. Password:hans@cs.buffalo.edu 230 Guest login ok, access restrictions apply. ftp> cd pub/sneps1 250 CWD command successful. ftp> dir 200 PORT command successful. 150 ASCII data connection for /bin/ls (128.205.32.1,3836) (0 bytes). total 2056 -rw-r--r-- 1 612 3012 8714 Jan 19 20:38 GARNET -rw-r--r-- 1 612 3012 1877 Jan 19 20:56 INFO -rw-r--r-- 1 612 3012 11956 Jan 19 20:38 README -rw-r--r-- 1 612 3012 19146 Jan 19 20:39 bibliography.bib.Z -rw-r--r-- 1 612 3012 23094 Jan 19 20:39 bibliography.dvi.Z -rw-r--r-- 1 612 3012 44413 Jan 19 20:39 bibliography.ps.Z drwxr-xr-x 2 0 11 512 Jun 18 1991 bin drwxr-xr-x 2 0 11 512 Jun 18 1991 etc -rw-r--r-- 1 612 3012 904 Sep 6 1991 genbib.tex.Z -rw-r--r-- 1 612 3012 231011 Jan 19 20:40 manual.ps.Z -rw-r----- 1 612 310 1732906 Jan 19 20:41 rel-1-308.tar.Z 226 ASCII Transfer complete. 741 bytes received in 0.11 seconds (6.5 Kbytes/s) ftp> binary 200 Type set to I. ftp> mget bibliography* mget bibliography.bib.Z? y 200 PORT command successful. 150 Binary data connection for bibliography.bib.Z (128.205.32.1,3838) (19146 bytes). 226 Binary Transfer complete. local: bibliography.bib.Z remote: bibliography.bib.Z 19146 bytes received in 0.0074 seconds (2.5e+03 Kbytes/s) mget bibliography.dvi.Z? y 200 PORT command successful. 150 Binary data connection for bibliography.dvi.Z (128.205.32.1,3839) (23094 bytes). 226 Binary Transfer complete. local: bibliography.dvi.Z remote: bibliography.dvi.Z 23094 bytes received in 0.058 seconds (3.9e+02 Kbytes/s) mget bibliography.ps.Z? y 200 PORT command successful. 150 Binary data connection for bibliography.ps.Z (128.205.32.1,3840) (44413 bytes). 226 Binary Transfer complete. local: bibliography.ps.Z remote: bibliography.ps.Z 44413 bytes received in 0.038 seconds (1.1e+03 Kbytes/s) ftp> bye 221 Goodbye. 42 (hadar) >