Relay-Version: version B 2.10 5/3/83; site utzoo.UUCP Path: utzoo!utgpu!water!watmath!clyde!rutgers!ames!ucbcad!ucbvax!nmsu.CSNET!yorick From: yorick@nmsu.CSNET.UUCP Newsgroups: comp.ai.digest Subject: Computer and Cognitive Science Abstracts (2 of 2) Message-ID: <8705130514.AA19923@ucbvax.Berkeley.EDU> Date: Sun, 10-May-87 18:07:45 EDT Article-I.D.: ucbvax.8705130514.AA19923 Posted: Sun May 10 18:07:45 1987 Date-Received: Fri, 15-May-87 07:16:23 EDT Sender: daemon@ucbvax.BERKELEY.EDU Distribution: world Organization: The ARPA Internet Lines: 347 Approved: ailist@stripe.sri.com Computing Research Laboratory New Mexico State University Box 30001 Las, Cruces, NM 88003. Krueger, W. (1986) Transverse Criticality and its Application to Image Processing, MCCS-85-61. The basis for investigation into visual recognition of objects is their representation. One appealing approach begins by replacing the objects themselves by their bounding surfaces. These then are represented by surfaces which have been smoothed according to various prescriptions. The resulting smoothed surfaces are subjected to geometric analysis in an attempt to find critical events which correspond to ``landmarks'' that serve to define the original object. Many vision researchers have used this outline, often incorporating it into a larger one that uses the critical events as constraints in surface generation programs. To deal with complex objects these investigators have proposed a number of candidates for the notion of critical event, most of which take the form of zero-crossings of some differentially defined quantity associated to surfaces (e.g. Gaussian curvature, etc.). Many of these require some a posteriori geometric conditioning (e.g. planarity) in order to be visually significant. In this report, we introduce the notion of a transverse critical line of a smooth function defined on a smooth surface. Transverse criticality attempts to capture the trough/crest behavior manifested by quantities which are globally defined on surfaces (e.g. curvature troughs and crests, irradiance troughs and crests). This notion can be used to study both topographic and photometric surface behavior and includes, as special cases, definitions proposed by other authors, among which notions are the regular edges of Phillips and Machuca [PM] and the interesting flutings of Marr [BPYA]. Applications are made to two classes of surfaces which are important in computer vision height surfaces and generalized cones. Graham, N. & Harary, F. (1986) Packing and Mispacking Subcubes into Hypercubes, MCCS-85-65. A node-disjoint packing of a graph G into a larger graph H is a largest collection of disjoint copies of G contained in H; an edge disjoint packing is defined similarly, but no two copies of G have a common edge. Two packing numbers of G into H are defined accordingly. It is easy to determine both of these numbers when G is a subcube of a hypercube H. A mispacking of G into H is a maximal collection of disjoint copies of G whose removal from H leaves no subgraph G, such that the cardinality of this collection is minimum. Two mispacking numbers of G into H are defined analogously. Their exact determination is quite difficult but we obtain upper bounds. Dietrich, E. & Fields, C. (1986), Creative Problem Solving Using Wanton Inference: It takes at least two to tango, MCCS-85-70. This paper introduces \fBwanton inference\fR, a problem solving strategy for creative problem solving. The central idea underlying wanton inference is that creative solutions to problems are often generated by ignoring boundaries between domains of knowledge and making new connections between previously unassociated elements of one's knowledge base. The major consequence of using the wanton inference strategy is that the size of search spaces is greatly increased. Hence, the wanton inference strategy is fundamentally at odds with the received view in AI that the essence of intelligent problem solving is limiting the search for solutions. Our view is that the problem of limiting search spaces is an artificial problem in AI, resulting from ignoring both the nature of creative problem solving and the social aspect of problem solving. We argue that this latter aspect of problem solving provides the key to dealing with the large search spaces generated by wanton inference. Ballim, A. (1986), The Subjective Ascription of Belief to Agents, MCCS-85-74. A computational model for determining an agent's beliefs from the viewpoint of an agent known as the system is described. The model is based on the earlier work of Wilks and Bien(1983) which argues for a method of dynamically constructing nested points of view from the beliefs that the system holds. This paper extends their work by examining problems involved in ascribing beliefs called meta-beliefs to agents, and by developing a representation to handle these problems. The representation is used in ViewGen, a computer program which generates viewpoints. Partridge, D. (1986), The Scope and Limitations of First Generation Expert Systems, MCCS-85-43. It is clear that expert system's technology is one of AI's greatest successes so far. Currently we see an ever increasing application of expert systems, with no obvious limits to their applicability. Yet there are also a number of well-recognized problems associated with this new technology. I shall argue that these problems are not the puzzles of normal science that will yield to advances within the current technology; on the contrary, they are symptoms of severe inherent limitations of this first generation technology. By reference to these problems I shall outline some important aspects of the scope and limitations of current expert system's technology. The recognition of these limitations is a prerequisite of overcoming them as well as of developing an awareness of the scope of applicability of this new technology. Gerber, M., Dearholt, D.W., Schvaneveldt, R.W., Sachania, V. & Esposito, C. (1987), Documentation for PATHFINDER: A Program to Generate PFNETs, MCCS-87-47. This documentation provides both user and programmer documentation for PATHFINDER, a program which generates PFNETs from symmetric distance matrices representing various aspects of human knowledge. User documentation includes instructions for input and output file formats, instructions for compiling and running the program, adjustments to incomplete or incompatable data sets, a general description of the algorithm, and a glossary of terms. Programmer documentation includes a detailed description of the algorithm with an explanation of each function and procedure, and hand execution examples of some of the more difficult to read code. Examples of input and output files are included. Ballim, A. (1986) Generating Points of View, MCCS-85-68. Modelling the beliefs of agents is normally done in a static manner. This paper describes a more flexible dynamic approach to generating nestings which represent what the system believes other agents believe. Such nestings have been described in Wilks and Bien (1983) as has their usefulness. The methods presented here are based upon those described in Wilks and Bien (ibid) but have been augmented to handle various problems. A system based on this paper is currently being written in Prolog. The Topological Cubical Dimension of a Graph Frank Harary MCCS-86-80 A cubical graph G is a subgraph of some hypercube $Q sub n$. The cubical dimension cd(G) is the smallest such n. We verify that the complete graph $K sub p$ is homeomorphic to a cubical graph H \(sb $Q sub p-1$. Hence every graph G has a subdivision which is a cubical graph. This enables us to define the topological cubical dimension tcd(G) as the minimum such n. When G is a full binary tree, the value of tcd is already known. Computer scientists, motivated by the use of the architecture of a hypercube for massively parallel supercomputers, defined the dilation of an edge e of G within a subdivision H of G as the lenth of the image of e in H, and the dilation of G as the maximum dilation of an edge of G. The two new invariants, tcd(G) and the minimum dilation of G among all cubical subdivisions H of G, are studied. CP: A Programming Environment for Conceptual Interpreters M.J. Coombs and R.T. Hartley MCCS-87-82 A conceptual approach to problem-solving is explored which we claim is much less brittle than logic-based methods. It also promises to support effective user/system interaction when applied to expert system design. Our approach is ``abductive'' gaining its power from the generation of good hypotheses rather than deductive inference, and seeks to emulate the robust cooperative problem-solving of multiple experts. Major characteristics include: (1) use of conceptual rather than syntactic representation of knowledge; (2) an empirical approach to reasoning by model generation and evaluation called Model Generative Reasoning; (3) dynamic composition of reasoning strategies from actors embedded in the conceptual structures; and (4) characterization of the reasoning cycle in terms of cooperating agents. Semantics and the Computational Paradigm in Cognitive Psychology Eric Dietrich MCCS-87-83 There is a prevalent notion among cognitive scientists and philosophers of mind that computers are merely formal symbol manipulators, performing the actions they do solely on the basis of the syntactic properties of the symbols they manipulate. This view of computers has allowed some philosophers to divorce semantics from computational explanations. Semantic content, then, becomes something one adds to computational explanations to get psychological explanations. Other philosophers, such as Stephen Stich have taken a stronger view, advocating doing away with semantics entirely. This paper argues that a correct account of computation requires us to attribute content to computational processes in order to explain which functions are being computed. This entails that computational psychology must countenance mental representations. Since anti-semantic positions are incompatible with computational psychology thus construed, they ought to be rejected. Lastly, I argue that in an important sense, computers are not formal symbol manipulators. Problem Solving in Multiple Task Environments Eric Dietrich and Chris Fields MCCS-87-84 We summarize a formal theory of multi-domain problem solving that provides a precise representation of the inferential dynamics of problem solving in multiple task environments. We describe a realization of the theory as an abstract virtual machine that can be implemented on standard architectures. We show that the behavior of such a machine can be described in terms of formally-specified analogs of mental models, and present a necessary condition for the use of analogical connections between such models in problem solving. An Automated Particulate Counting System for Cleanliness Verification of Aerospace Test Hardware \fIJeff Harris and Edward S. Plumer\fR MCCS-87-86 An automated, computerized particle counting system has been developed to verify the cleanliness of aerospace test hardware. This work was performed by the Computing Research Laboratory at New Mexico State University (CRL) under a contract with Lockheed Engineering and Management Services Company at the NASA Johnson Space Center, White Sands Test Facility. Aerospace components are thoroughly cleaned and residual particulate matter remaining on the components is rinsed onto 47 mm diameter test filters. The particulates on these filters are an indication of the contamination remaining on the components. These filters are examined under a microscope, and particles are sized and counted. Previously, the examination was performed manually; this operation has now been automated. Rather than purchasing a dedicated particle analysis system, a flexible system utilizing an IBM PC-AT was developed. The computer, combined with a digitizing board for image acquisition, controls a video-camera-equipped microscope and an X-Y stage to allow automated filter positioning and scanning. The system provides for complete analysis of each filter paper, generation of statistical data on particle size and quantity, and archival storage of this information for further evaluation. The system is able to identify particles down to 5 micrometers in diameter and discriminate between particles and fibers. A typical filter scan takes approximately 5 minutes to complete. Immediate operator feedback as to pass-fail for a particular cleanliness standard is also a feature. The system was designed to be operated by personnel working inside a class 100 clean room. Should it be required, a mechanism for more sophisticated recognition of particles based on shape and color may be implemented. Solving Problems by Expanding Search Graphs: Mathematical Foundations for a Theory of Open-world Reasoning Eric Dietrich and Chris Fields MCCS-87-88 We summarize a mathematical theory describing a virtual machine capable of expanding search graphs. This machine can, at least sometimes, solve problems where it is not possible to precisely and in detail specify the space it must search. The mechanism for expansion is called wanton inference. The theory specifies which wanton inferences have the greatest chance of producing solutions to given problems. The machine, using wanton inference, satisfies an intuitive definition of open-world reasoning. Software Engineering Constraints Imposed by Unstructured Task Environments Eric Dietrich and Chris Fields MCCS-87-91 We describe a software engineering methodology for building multi-domain (open-world) problem solvers which inhabit unstructured task environments. This methodology is based on a mathematical theory of such problem solving. When applied, the methodology results in a specification of program behavior that is independent of any architectural concerns. Thus the methodology produces a specification prior to implementation (unlike current AI software engineering methodology). The data for the specification are derived from experiments run on human experts. Multiple Agents and the Heuristic Ascription of Belief. Yorick Wilks and Afzal Ballim MCCS-86-75 A method for heuristically generating nested beliefs (what some agent believes that another agent believes ... about a topic) is described. Such nested beliefs (points of view) are esential to many processes such as discourse processing and reasoning about other agents' reasoning processes. Particular interest is paid to the class of beliefs known as \fIatypical beliefs\fR and to intensional descriptions. The heuristic methods described are emboddied in a program called \fIViewGen\fR which generates nested viewpoints from a set of beliefs held by the system. An Algorithm for Open-world Reasoning using Model Generation M.J. Coombs, E. Dietrich & R.T. Hartley MCCS-87-87 The closed-world assumption places an unacceptable constraint on a problem-solver by imposing an \fIa priori\fR notion of relevance on propositions in the knowledge-base. This accounts for much of the brittleness of expert systems, and their inability to model natural human reasoning in detail. This paper presents an algorithm for an open-world problem-solver. Termed Model Generative Reasoning, we replace deductive inference with a procedure based on the generation of alternative, intensional domain descriptions (models) to cover problem input, which are then evaluated against domain facts as alternative explanations. We also give an illustration of the workings of the algorithm using concepts from process control. Pronouns in mind: quasi-indexicals and the ``language of thought'' Yorick Wilks, Afzal Ballim, & Eric Dietrich MCCS-87-92 The paper examines the role of the natural-formal language distinction in connection with the "language of thought" (LOT) issue. In particular, it distinguishes a realist-uniform/attributist-uniform approach to LOT and seeks to link that distinction to the issue of whether artificial intelligence is fundamentally a science or engineering. In a second section, we examine a particular aspect of natural language in relation to LOT: pronouns/indexicals. The focus there is Rapaport's claims about indexicals in belief representations. We dispute these claims and argue that he confuses claims about English sentences and truth conditions, on the one hand, with claims about beliefs, on the other. In a final section we defend the representational capacity of the belief manipulation system of Wilks, Bien and Ballim against Rapaport's published criticisms.