E1AR0002@SMUVM1.BITNET (11/12/86)
TECHNICAL NOTE: 264\hfill PRICE: \$10.00\\[-0.15in] \begin{tabbing} \noindent TITLE: \= THE ROLE OF LOGIC IN KNOWLEDGE REPRESENTATION AND \\ \> COMMONSENSE REASONING\\ AUTHOR: ROBERT C. MOORE\\ DATE: JUNE 1982\\[-0.15in] \end{tabbing} ABSTRACT: This paper examines the role that formal logic ought to play in representing and reasoning with commonsense knowledge. We take issue with the commonly held view (as expressed by Newell [1980]) that the use of representations based on formal logic is inappropriate in most applications of artificial intelligence. We argue to the contrary that there is an important set of issues, involving incomplete knowledge of a problem situation, that so far have been addressed only by systems based on formal logic and deductive inference, and that, in some sense, probably can be dealt with only by systems based on logic and deduction. We further argue that the experiments of the late 1960s on problem-solving by theorem-proving did not show that the use of logic and deduction in AI systems was necessarily inefficient, but rather that what was needed was better control of the deduction process, combined with more attention to the computational properties of axioms.\\ -------------------------------------------------------------------------------- -------------------------------------------------\\ TECHNICAL NOTE: 265\hfill PRICE: \$10.00\\[0.01in] \noindent TITLE: A VIEW OF THE FIFTH GENERATION AND ITS IMPACT\\ AUTHOR: DAVID H. D. WARREN\\ DATE: JULY 1982\\[0.01in] ABSTRACT: In October 1981, Japan announced a national project to develop highly innovative computer systems for the 1990s, with the title Fifth Generation Computer Systems.'' This paper is a personal view of that project, its significance, and reactions to it.\\ -------------------------------------------------------------------------------- -------------------------------------------------\\ TECHNICAL NOTE: 266R\hfill PRICE: \$10.00\\[-0.15in] \begin{tabbing} \noindent TITLE: \= DOMAIN INDEPENDENT PLANNING: REPRESENTATION AND \\ \> PLAN GENERATION\\ AUTHOR: DAVID WILKINS\\ DATE: MAY 5, 1983\\[-0.15in] \end{tabbing} ABSTRACT: A domain independent planning program that supports both automatic and interactive generation of hierarchical, partially ordered plans is described. An improved formalism makes extensive use of \underline{constraints} and \underline{resources} to represent domains and actions more powerfully. The formalism also offers efficient methods for representing properties of objects that do not change over time, allows specification of the plan rationale (which includes scoping of conditions and appropriately relating different levels in the hierarchy), and provides the ability to express deductive rules for deducing the effects of actions. The implications of allowing parallel actions in a plan or problem solution are discussed, and new techniques for efficiently detecting and remedying harmful parallel interactions are presented. The most important of these techniques, reasoning about resources, is emphasized and explained. The system supports concurrent exploration of different branches in the search, making best-first search easy to implement.\\ -------------------------------------------------------------------------------- -------------------------------------------------\\ TECHNICAL NOTE: 267\hfill PRICE: \$14.00\\[-0.15in] \begin{tabbing} \noindent TITLE: MODELING AND USING PHYSICAL CONSTRAINTS IN SCENE ANALYSIS\\ AUTHORS: \= MARTIN A. FISCHLER, STEPHEN T. BARNARD, ROBERT C. BOLLES,\\ \> MICHAEL LOWRY, LYNN QUAM, GRAHAME SMITH, and ANDREW WITKIN\\ DATE: SEPTEMBER 1982\\[-0.15in] \end{tabbing} ABSTRACT: This paper describes the results obtained in a research program ultimately concerned with deriving a physical sketch of a scene from one or more images. Our approach involves modeling physically meaningful information that can be used to constrain the interpretation process, as well as modeling the actual scene content. In particular, we address the problems of modeling the imaging process (camera and illumination), the scene geometry (edge classification and surface reconstruction), and elements of scene content (material composition and skyline delineation).\\ -------------------------------------------------------------------------------- -------------------------------------------------\\ TECHNICAL NOTE: 268\hfill PRICE: \$10.00\\[-0.15in] \begin{tabbing} \noindent TITLE: \= A NONCLAUSAL CONNECTION-GRAPH RESOLUTION\\ \> THEOREM-PROVING PROGRAM\\ AUTHOR: MARK E. STICKEL\\ DATE: OCTOBER 1982\\[-0.15in] \end{tabbing} ABSTRACT: A new theorem-proving program, combining the use of nonclausal resolution and connection graphs, is described. The use of nonclausal resolution as the inference system eliminates some of the redundancy and unreadability of clause-based systems. The use of a connection graph restricts the search space and facilitates graph searching for efficient deduction.\\ -------------------------------------------------------------------------------- -------------------------------------------------\\ TECHNICAL NOTE: 269\hfill PRICE: \$10.00\\[-0.15in] \begin{tabbing} \noindent TITLE: \= COMPLETE SYSTEMS OF REDUCTIONS USING ASSOCIATIVE AND/OR\\ \> COMMUTATIVE UNIFICATION\\ AUTHORS: GERALD E. PETERSON and MARK E. STICKEL\\ DATE: OCTOBER 1982\\[-0.15in] \end{tabbing} ABSTRACT: An extension to the Knuth-Bendix algorithm for finding complete systems of reductions is described. The extension permits the derivation of complete systems of reductions for theories which include functions which are associative and/or commutative. A few examples of the use of the extended Knuth-Bendix algorithm are presented for theories of groups, rings, lattices, Boolean algebras, and primitive recursive functions.\\ -------------------------------------------------------------------------------- -------------------------------------------------\\ TECHNICAL NOTE: 270\hfill PRICE: \$10.00\\[-0.15in] \begin{tabbing} \noindent TITLE: DIALOGIC: A CORE NATURAL-LANGUAGE PROCESSING SYSTEM\\ AUTHORS: \= BARBARA J. GROSZ, NORMAN HAAS, GARY HENDRIX, JERRY HOBBS,\\ \> PAUL MARTIN, ROBERT MOORE, JANE ROBINSON, and\\ \> STANLEY ROSENSCHEIN\\ DATE: NOVEMBER 9, 1982\\[-0.15in] \end{tabbing} ABSTRACT: The DIALOGIC system translates English sentences into representations of their literal meaning in the context of an utterance. These representations, or logical forms,'' are intended to be a purely formal language that is as close as possible to the structure of natural language, while providing the semantic compositionality necessary for meaning-dependent computational processing. The design of DIALOGIC (and of its constituent modules) was influenced by the goal of using it as the core language-processing component in a variety of systems, some of which are transportable to new domains of application.\\ -------------------------------------------------------------------------------- -------------------------------------------------\\ TECHNICAL NOTE: 271\hfill PRICE: \$16.00\\[0.01in] \noindent TITLE: INTERPRETING PERSPECTIVE IMAGES\\ AUTHOR: STEPHEN T. BARNARD\\ DATE: NOVEMBER 1982\\[0.01in] ABSTRACT: A fundamental problem in computer vision is how to determine the 3-D spatial orientation of curves and surfaces appearing in an image. The problem is generally under-constrained, and is complicated by the fact that metric properties, such as orientation and length, are not invariant under projection. Under perspective projection (the correct model for most real images) the transform is nonlinear, and therefore hard to invert. Two constructive methods are presented. The first finds the orientation of parallel lines and planes by locating vanishing points and vanishing lines. The second determines the orientation of plans by backprojection" of two intrinsic properties of contours: angle magnitude and curvature.\\ -------------------------------------------------------------------------------- -------------------------------------------------\\ TECHNICAL NOTE: 272\hfill PRICE: \$20.00\\[0.01in] \noindent TITLE: LOCAL SHADING ANALYSIS\\ AUTHOR: ALEX P. PENTLAND\\ DATE: NOVEMBER 1982\\[0.01in] ABSTRACT: Local analysis of image shading, in the absence of prior knowledge about the viewed scene, may be used to provide information about the scene. The following has been proved. \underline{Every} image point has the same image intensity and first and second derivatives as the image of an umbilical point (a point with equal principal curvatures) on a Lambertian surface; there is \underline{exactly one} combination of surface orientation, curvature, (overhead) illumination direction and albedo times illumination intensity that will produce a particular set of image intensity and first and second derivatives. A solution for the unique combination of surface orientation, etc., at umbilical points is presented. This solution has been extended by using general position and regional constraints to obtain estimates of the following: \begin{itemize} \item Surface orientation at each image point \item Whether the surface is planar, singly or doubly curved at each point \item The mean illuminant direction within a region \item Whether a region is convex, concave, or is a saddle surface. \end{itemize} Algorithms to recover illuminant direction, identify discontinuities, and estimate surface orientation have been evaluated on both natural and synthesized images, and have been found to produce useful information about the scene.\\ -------------------------------------------------------------------------------- -------------------------------------------------\\ TECHNICAL NOTE: 273\hfill PRICE: \$20.00\\[0.01in] \noindent TITLE: FROM IMAGE IRRADIANCE TO SURFACE ORIENTATION\\ AUTHOR: GRAHAME B. SMITH\\ DATE: DECEMBER 1982\\[0.01in] ABSTRACT: The image irradiance equation constrains the relationship between surface orientation in a scene and the irradiance of its image. This equation requires detailed knowledge of both the scene illumination and the reflectance of the surface material. For this equation to be used to recover surface orientation from image irradiance, additional constraints are necessary. The constraints usually employed require that the recovered surface be smooth. We demonstrate that smoothness is not sufficient for this task. A new formulation of shape from shading is presented in which surface orientation is related to image irradiance without requiring detailed knowledge of the scene illumination, or of the albedo of the surface material. This formulation, which assumes isotropic scattering, provides some interesting performance parallels to those exhibited by the human visual system.\\ -------------------------------------------------------------------------------- -------------------------------------------------\\ TECHNICAL NOTE: 275\hfill PRICE: \$20.00\\[0.01in] \noindent TITLE: LOGIC FOR NATURAL LANGUAGE ANALYSIS\\ AUTHOR: FERNANDO PEREIRA\\ DATE: JANUARY 1983\\[0.01in] ABSTRACT: This work investigates the use of formal logic as a practical tool for describing the syntax and semantics of a subset of English, and building a computer program to answer data base queries expressed in that subset. To achieve an intimate connection between logical descriptions and computer programs, all the descriptions given are in the definite clause subset of the predicate calculus, which is the basis of the programming language Prolog. The logical descriptions run directly as efficient Prolog programs. Three aspects of the use of logic in natural language analysis are covered: formal representation of syntactic rules by means of a grammar formalism based on logic, extraposition grammars; formal semantics for the chosen English subset, appropriate for data base queries; informal semantic and pragmatic rules to translate analyzed sentences into their formal semantics. On these three aspects, the work improves and extends earlier work by Colmerauer and others, where the use of computational logic in language analysis was first introduced.\\ -------------------------------------------------------------------------------- -------------------------------------------------\\ TECHNICAL NOTE: 276\hfill PRICE: \$16.00\\[-0.15in] \begin{tabbing} \noindent TITLE: \= A GENERAL APPROACH TO MACHINE PERCEPTION OF \\ \> LINEAR STRUCTURE IN IMAGED DATA\\ AUTHORS: MARTIN A. FISCHLER and HELEN C. WOLF\\ DATE: FEBRUARY 1983\\[-0.15in] \end{tabbing} ABSTRACT: In this paper we address a basic problem in machine perception: the tracing of line-like'' structures appearing in an image. It is shown that this problem can profitably be viewed as the process of finding skeletons in a gray scale image after observing (1) that line detection does not necessarily depend on gradient information, but rather is approachable from the standpoint of measuring total intensity variation, and (2) that smoothing the original image produces an approximate distance transform. An effective technique for extracting the delineating skeletons from an image is presented, and examples of this approach using aerial, industrial, and radiographic imagery are shown.\\ -------------------------------------------------------------------------------- -------------------------------------------------\\ TECHNICAL NOTE: 277\hfill PRICE: \$15.00\\[0.01in] \noindent TITLE: THE DARPA/DMA IMAGE UNDERSTANDING TESTBED USER'S MANUAL\\ AUTHOR: ANDREW J. HANSON\\ DATE: JANUARY 1984\\[0.01in] ABSTRACT: The primary purpose of the Image Understanding (IU) Testbed is to provide a means for transferring technology from the DARPA-sponsored IU research program to DMA and other organizations in the defense community. The approach taken to achieve this purpose has two components: \begin{enumerate} \item The establishment of a uniform environment that will be as compatible as possible with the environments of research centers at universities participating in the IU program. Thus, organizations obtaining copies of the Testbed can receive a flow of new results derived from ongoing research. \item The acquisition, integration, testing, and evaluation of selected scene analysis techniques that represent mature examples of generic areas of research activity. These contributions from participants in the IU program will allow organizations with Testbed copies to immediately begin investigating potential applications of IU technology to problems in automated cartography and other areas of scene analysis. \end{enumerate} The IU Testbed project was carried out under DARPA Contract No. MDA903-79-C-0588. The views and conclusions contained in this document are those of the author and should not be interpreted as necessarily representing the official policies, either expressed or implied, of the Defense Advanced Research Projects Agency or the United States government. This document presents a user's view of the IU Testbed and the facilities it provides. Many talented people, both at SRI and at each of the contributing institutions, must be acknowledged for their part in bringing the Testbed into existence. Special recognition is due to David Kashtan and Kenneth Laws for their essential contributions to the environment described here.\\ -------------------------------------------------------------------------------- -------------------------------------------------\\ TECHNICAL NOTE: 278\hfill PRICE: \$10.00\\[0.01in] \noindent TITLE: A REPRESENTATION OF TIME FOR PLANNING\\ AUTHOR: PETER CHEESEMAN\\ DATE: FEBRUARY 1983\\[0.01in] ABSTRACT: A new time representation is described that allows a continuously changing world to be represented, so that queries about the truth of a proposition at an instant or over an interval can be answered. The deduction mechanism used to answer the common queries necessary in planning is the same as that employed for deducing all other information, thereby avoiding the need for a specialized time expert. The representation allows any time information to be represented without forcing an over specification. The implementation of this representation requires mechanisms to detect the effects of world changes on previous deductions (truth maintenance).\\ -------------------------------------------------------------------------------- -------------------------------------------------\\ -------