CSAIL Publications and Digital Archive header
bullet Technical Reports bullet Work Products bullet Historical Collections bullet

link to publications.csail.mit.edu link to www.csail.mit.edu horizontal line

CSAIL Digital Archive - Artificial Intelligence Laboratory Series
Publications 600 through 699

AI PublicationsLast update Sun Mar 19 05:05:02 2006


Author[s]: James L. Stansfield

Conclusions from the Commodity Expert Project

November 1980



The goal of the commodity expert project was to develop a prototype program that would act as an intelligent assistant to a commodity market analyst. Since expert analysis must deal with very large, yet incomplete, data bases of unreliable facts about a complex world, the project would stringently test the applicability of Artificial Intelligence techniques. After a significant effort however, I am forced to the conclusion that an intelligent, real-world system of the kind envisioned is currently out of reach. Some of the difficulties were due to the size and complexity of the domain. As its true scale became evident, the available resources progressively appeared less adequate. The representation and reasoning problems that arose were persistently difficult and fundamental work is needed before the tools will be sufficient to engineer truly intelligent assistants. Despite these difficulties, perhaps even because of them, much can be learned from the project. To assist future applications projects, I explain in this report some of the reasons for the negative result, and also describe some positive ideas that were gained along the way. In doing so, I hope to convey the respect I have developed for the complexity of real- world domains, and the difficulty of describing the ways experts deal them.


Author[s]: Daniel Weinreb and David Moon

Flavors: Message Passing in the Lisp Machine

November 1980



The object oriented programming style used in the Smalltalk and Actor languages is available in Lisp Machine Lisp, and used by the Lisp Machine software system. It is used to perform generic operations on objects. Part of its implementation is simply a convention in procedure calling style; part is a powerful language feature, called Flavors, for defining abstract objects. This chapter attempts to explain what programming with objects and with message passing means, the various means of implementing these in Lisp Machine Lisp, and when you should use them. It assumes no prior knowledge of any other languages.


Author[s]: Marvin Minsky

Jokes and the Logic of the Cognitive Unconscious

November 1980



Freud’s theory of jokes explains how they overcome the mental “censors” that make it hard for us to think “forbidden” thoughts. But his theory did not work so well for humorous nonsense as for other comical subjects. In this essay I argue that the different forms of humor can be seen as much more similar, once we recognize the importance of knowledge about knowledge and, particularly, aspects of thinking concerned with recognizing and suppressing bugs – ineffective or destructive thought processes. When seen in this light, much humor that at first seems pointless, or mysterious, becomes more understandable.


Author[s]: Charles Rich

Inspection Methods in Programming

June 1981



The work reported here lies in the area of overlap between artificial intelligence software engineering. As research in artificial intelligence, it is a step towards a model of problem solving in the domain of programming. In particular, this work focuses on the routine aspects of programming which involve the application of previous experience with similar programs. I call this programming by inspection. Programming is viewed here as a kind of engineering activity. Analysis and synthesis by inspection area prominent part of expert problem solving in many other engineering disciplines, such as electrical and mechanical engineering. The notion of inspections methods in programming developed in this work is motivated by similar notions in other areas of engineering. This work is also motivated by current practical concerns in the area of software engineering. The inadequacy of current programming technology is universally recognized. Part of the solution to this problem will be to increase the level of automation in programming. I believe that the next major step in the evolution of more automated programming will be interactive systems which provide a mixture of partially automated program analysis, synthesis and verification. One such system being developed at MIT, called the programmer’s apprentice, is the immediate intended application of this work. This report concentrates on the knowledge are of the programmer’s apprentice, which is the form of a taxonomy of commonly used algorithms and data structures. To the extent that a programmer is able to construct and manipulate programs in terms of the forms in such a taxonomy, he may relieve himself of many details and generally raise the conceptual level of his interaction with the system, as compared with present day programming environments. Also, since it is practical to expand a great deal of effort pre- analyzing the entries in a library, the difficulty of verifying the correctness of programs constructed this way is correspondingly reduced. The feasibility of this approach is demonstrated by the design of an initial library of common techniques for manipulating symbolic data. This document also reports on the further development of a formalism called the plan calculus for specifying computations in a programming language independent manner. This formalism combines both data and control abstraction in a uniform framework that has facilities for representing multiple points of view and side effects.


Author[s]: Tomas Lozano-Perez

Spatial Planning: A Configuration Space Approach

December 1980



This paper presents algorithms for computing constraints on the position of an object due to the presence of obstacles. This problem arises in applications which require choosing how to arrange or move objects among other objects. The basis of the approach presented here is to characterize the position and orientation of the object of interest as a single point in a Configuration Space, in which each coordinate represents a degree of freedom in the position and/or orientation of the object. The configurations forbidden to this object, due to the presence of obstacles, can then be characterized as regions in the Configuration Space. The paper presents algorithms for computing these Configuration Space obstacles when the objects and obstacles are polygons or polyhedra. An approximation technique for high-dimensional Configuration Space obstacles, based on projections of obstacles slices, is described.


Author[s]: Tomas Lozano-Perez

Automatic Planning of Manipulator Transfer Movements

December 1980



This paper deals with the class of problems that involve finding where to place or how to move a solid object in the presence of obstacles. The solution to this class of problems is essential to the automatic planning of manipulator transfer movements, i.e. the motions to grasp a part and place it at some destination. This paper presents algorithms for planning manipulator paths that avoid collisions with objects in the workspace and for choosing safe grasp points on objects. These algorithms allow planning transfer movements for Cartesian manipulators. The approach is based on a method of computing an explicit representation of the manipulator configurations that would bring about a collision.


Author[s]: D.D. Hoffman and B.E. Flinchbaugh

The Interpretation of Biological Motion

December 1980



The term biological motion has been coined by G. Johansson (1973) to refer to the ambulatory patterns of terrestrial bipeds and quadripeds. In this paper a computational theory of the visual perception of biological motion is proposed. The specific problem addressed is how the three dimensional structure and motions of animal limbs may be computed from the two dimensional motions of their projected images. It is noted that the limbs of animals typically do not move arbitrarily during ambulation. Rather, for anatomical reasons, they typically move in single planes for extended periods of time. This simple anatomical constraint is exploited as the basis for utilizing a “planarity assumption” in the interpretation of biological motion. The analysis proposed is: (1) divide the image into groups of two or three elements each; (2) test each group for pairwise-rigid planar motion; (3) combine the results from (2). Fundamental to the analysis are two ‘structure from planar motion’ propositions. The first states that the structure and motion of two points rigidly linked and rotating in a plane is recoverable from three orthographic projections. The second states that the structure and motion of three points forming two hinged rods constrained to move in a plane is recoverable from two orthographic projections. The psychological relevance of the analysis and possible interactions with top down recognition processes are discussed.


Author[s]: Barbara S. Kerns

Towards a Better Definition of Transactions

December 1980



This paper builds on a technical report written by Carl Hewitt and Henry Baker called “Actors and Continuous Functionals”. What is called a “goal-oriented activity” in that paper will be referred to in this paper as a “transaction”. The word “transaction” brings to mind an object closer in function to what we wish to present than does the word “activity”. This memo, therefore, presents the definitions of a reply and a transaction as given in Hewitt and Baker’s paper and points out some discrepancies in their definitions. That is, that the properties of transactions and replies as they were defined did not correspond with our intuitions, and thus the definitions should be changed. The issues of what should constitute a transaction are discussed, and a new definition is presented which eliminates the discrepancies caused by the original definitions. Some properties of the newly defined transactions are discussed, and it is shown that the results of Hewitt and Baker’s paper still hold given the new definitions.


Author[s]: Richard Brown

Coherent Behavior from Incoherent Knowledge Sources in the Automatic Synthesis of Numerical Computer Programs

January 1981



A fundamental problem in artificial intelligence is obtaining coherent behavior in rule-based problem solving systems. A good quantitative measure of coherence is time behavior; a system that never, in retrospect, applied a rule needlessly is certainly coherent; a system suffering from combinatorial blowup is certainly behaving incoherently. This report describes a rule-based problem solving system for automatically writing and improving numerical computer programs from specifications. The specifications are in terms of “constraints” among inputs and outputs. The system has solved program synthesis problems involving systems of equations, determining that methods of successive approximation converge, transforming recursion to iteration, and manipulating power series (using differing organizations, control structures, and argument-passing techniques).


Author[s]: Richard C. Waters

GPRINT - A LISP Pretty Printer Providing Extensive User Format-Control Mechanism

October 1981



A pretty printer is presented which makes it easy for a user to control the format of the output produced. The printer can be used as a general mechanism for printing data structures as well as programs. It is divided into two parts: a set of formatting functions, and an output routine. Each formatting function creates a sequence of directions which specify how an object is to be formatted if it can fit on one line and how it is to be formatted if it must be broken up across multiple lines. Based on the line length available, the output routine decides what structures have to be broken up across multiple lines and produces the actual output following the directions created by the formatting functions. The directions passed from the formatting functions to the output routine form a well defined interface: a language for specifying formatting options. Three levels of user format-control are provided. A simple template mechanism makes it easy for a user to control certain aspects of the format produced. A user can exercise much more complete control over how a particular type of object is formatted by writing a special formatting function for it. He can make global changes in format by modifying the formatting process as a whole.


Author[s]: Richard C. Waters

GPRINT: A LISP Pretty Printer Providing Extensive User Format Control Mechanism

September 1982



A Lisp pretty printer is presented which makes it easy for a user to control the format of the output produced. The printer can be used as a general mechanism for printing data structures as well as programs. It is divided into two parts: a set of formatting functions and an output routine. The user specifies how a particular type of object should be formatted by creating a formatting function for the type. When passed an object of that type, the formatting function creates a sequence of directions which specify how the object should be printed if it can fit on one line and how it should be printed if it must be broken up across multiple lines. A simple template language makes it easy to specify these directions. Based on the line length available, the output routine decides what structures have to be broken up across multiple lines and produces the actual output following the directions created by the formatting functions. The paper concludes with a discussion of how the pretty printing method presented could be applied to languages other than Lisp.


Author[s]: B.K.P. Horn

The Curve of Least Energy

January 1981



Here we search for the curve which has the smallest integral of the square of curvature, while passing through two given points with given orientation. This is the true shape of a spline used in lofting. In computer-aided design, curves have been sought which maximize “smoothness”. The curve discussed here is the one arising in this way from a commonly used measure of smoothness. The human visual system may use such a curve when it constructs a subjective contour.


Author[s]: W.E.L. Grimson

A Computational Theory of Visual Surface Interpolation

June 1981



Computational theories of structure from motion [Ulman, 1979] and stereo vision [Marr and Poggio, 1979] only specify the computation of three-dimensional surface information at special points in the image. Yet, the visual perception is clearly of complete surfaces. In order to account for this, a computational theory of the interpolation of surfaces from visual information is presented.


Author[s]: W.A. Richards, J.M. Rubin and D.D. Hoffman

Equation Counting and the Interpretation of Sensory Data

June 1981



Many problems in biological information processing require the solution to a complex system of equations in many unknown variables. An equation-counting procedure is described for determining whether such a system of equations will indeed have a unique solution, and under what conditions the solution should be interpreted as “correct”. Three examples of the procedure are given for illustration, one for auditory signal processing and two from vision.


Author[s]: Kenneth D. Forbus

A Study of Qualitative and Geometric Knowledge in Reasoning about Motion

February 1981



Reasoning about motion is an important part of our commonsense knowledge, involving fluent spatial reasoning. This work studies the qualitative and geometric knowledge required to reason in a world that consists of balls moving through space constrained by collisions with surfaces, including dissipative forces and multiple moving objects. An analog geometry representation serves the program as a diagram, allowing many spatial questions to be answered by numeric calculation. It also provides the foundation for the construction and use of place vocabulary, the symbolic descriptions of space required to do qualitative reasoning about motion in the domain. The actual motion of a ball is described as a network consisting of descriptions of qualitatively distinct types of motion. Implementing the elements of these networks in a constraint language allows the same elements to be used for both analysis and simulation of motion. A qualitative description of the actual motion is also used to check the consistency of assumptions about motion. A process of qualitative simulation is used to describe the kinds of motion possible from some state. The ambiguity inherent in such a description can be reduced by assumptions about physical properties of the ball or assumptions about its motion. Each assumption directly rules out some kinds of motion, but other knowledge is required to determine the indirect consequences of making these assumptions. Some of this knowledge is domain dependent and relies heavily on spatial descriptions.


Author[s]: Marvin Minsky

Music, Mind and Meaning

February 1981



Speculating about cognitive aspects of listening to music, this essay discusses: how metric regularity and thematic repetition might involve representation frames and memory structures, how the result of listening might resemble space-models, how phrasing and expression might evoke innate responses and, finally, why we like music – or rather, what is the nature of liking itself.


Author[s]: Kuk Huang Lim

Control of a Tendon Arm

February 1981



The dynamics and control of tendon driven three degree of freedom shoulder joint are studied. A control scheme consisting of two phases has been developed. In the first phase, approximation of the time optimal control trajectory was applied open to the loop to the system. In the second phase a closed loop linear feedback law was employed to bring the system to the desired final state and to maintain it there.


Author[s]: Barbara Y. White

Designing Computer Games to Facilitate Learning

February 1981



The aim of this thesis was to explore the design of interactive computer learning environments. The particular learning domain selected was Newtonian dynamics. Newtonian dynamics was chosen because it is an important area of physics with which many students have difficulty and because controlling Newtonian motion takes advantage of the computer’s graphics and interactive capabilities. The learning environment involved games which simulated the motion of a spaceship on a display screen. The purpose of the games was to focus the students’ attention on various aspects of the implications of Newton’s laws.


Author[s]: Gerald R. Barber

Record of the Workshop on Research in Office Semantics

February 1981



This paper is a compendium of the ideas and issues presented at the Chatham Bars Workshop on Office Semantics. The intent of the workshop was to examine the state of the art in office systems and to elucidate the issues system designers were concerned with in developing next generation office systems. The workshop involved a cross- section of people from government, industry and academia. Presentations in the form of talks and video tapes were made of prototypical systems.


Author[s]: William M. Silver

On the Representation of Angular Velocity and Its Effect on the Efficiency of Manipulator Dynamics Computation

March 1981



Recently there has been considerable interest in efficient formulations of manipulator dynamics, mostly due to the desirability of real-time control or analysis of physical devices using modest computers. The inefficiency of the classical Lagrangian formulation is well known, and this has led researchers to seek alternative methods. Several authors have developed a highly efficient formulation of manipulator dynamics based on the Newton-Euler equations, and there may be some confusion as to the source of this efficiency. This paper shows that there is in fact no fundamental difference in computational efficiency between Lagrangian and Newton-Euler formulations. The efficiency of the above-mentioned Newton-Euler formulation is due to two factors: the recursive structure of the computation and the representation chosen of the rotational dynamics. Both of these factors can be achieved in the Lagrangian formulation, resulting in an algorithm identical to the Newton-Euler formulation. Recursive Lagrangian dynamics has been discussed previously by Hollerbach. This paper takes the final step by comparing in detail the representations that have been used for rotational dynamics and showing that with a proper choice of representation the Lagrangian formulation is indeed equivalent to the Newton-Euler formulation.


Author[s]: Anna R. Bruss

The Image Irradiance Equation: Its Solution and Application

June 1981



How much information about the shape of an object can be inferred from its image? In particular, can the shape of an object be reconstructed by measuring the light it reflects from points on its surface? These questions were raised by Horn [HO70] who formulated a set of conditions such that the image formation can be described in terms of a first order partial differential equation, the image irradiance equation. In general, an image irradiance equation has infinitely many solutions. Thus constraints necessary to find a unique solution need to be identified. First we study the continuous image irradiance equation. It is demonstrated when and how the knowledge of the position of edges on a surface can be used to reconstruct the surface. Furthermore we show how much about the shape of a surface can be deduced from so called singular points. At these points the surface orientation is uniquely determined by the measured brightness. Then we investigate images in which certain types of silhouettes, which we call b-silhouettes, can be detected. In particular we answer the following question in the affirmative: Is there a set of constraints which assure that if an image irradiance equation has a solution, it is unique? To this end we postulate three constraints upon the image irradiance equation and prove that they are sufficient to uniquely reconstruct the surface from its image. Furthermore it is shown that any two of these constraints are insufficient to assure a unique solution to an image irradiance equation. Examples are given which illustrate the different issues. Finally, an overview of known numerical methods for computing solutions to an image irradiance equation are presented.


Author[s]: Randall Davis and Reid G. Smith

Negotiation as a Metaphor for Distributed Problem Solving

May 1981



We describe the concept of distributed problem solving and define it as the cooperative solution of problems by a decentralized and loosely coupled collection of problem solvers. This approach to problem solving offers the promise of increased performance and provides a useful medium for exploring and developing new problem- solving techniques. We present a framework called the contract net that specifies communication and control in a distributed problem solver. Task distribution is viewed as an interactive process, a discussion carried on between a node with a task to be executed and a group of nodes that may be able to execute the task. We describe the kinds of information that must be passed between nodes during the discussion in order to obtain effective problem-solving behavior. This discussion is the origin of the negotiation metaphor: Task distribution is viewed as a form of contract negotiation. We emphasize that protocols for distributed problem solving should help determine the content of the information transmitted, rather than simply provide a means of sending bits from one node to another. The use of the contract net framework is demonstrated in the solution of a simulated problem in area surveillance, of the sort encountered in ship or air traffic control. We discuss the mode of operation of a distributed sensing system, a network of nodes extending throughout a relatively large geographic area, whose primary aim is the formation of a dynamic map of traffic in the area. From the results of this preliminary study we abstract features of the framework applicable to problem solving in general, examining in particular transfer of control. Comparisons with PLANNER, CONNIVER, HEARSAY-II, and PUP6 are used to demonstrate that negotiation – the two-way transfer of information – is a natural extension to the transfer of control mechanisms used in earlier problem-solving systems.


Author[s]: Henry Lieberman

A Preview of Act 1

June 1981



The next generation of artificial intelligence programs will require the ability to organize knowledge as groups of active objects. Each object should have only its own local expertise, the ability to operate in parallel with other objects, and the ability to communicate with other objects. Artificial Intelligence programs will also require a great deal of flexibility, including the ability to support multiple representations of objects, and to incrementally and transparently replace objects with new, upward-compatible versions. To realize this, we propose a model of computation based on the notion of an actor, an active object that communicates by message passing. Actors blur the conventional distinction between data and procedures. The actor philosophy is illustrated by a description of our prototype actor interpreter Act 1.


Author[s]: Henry Lieberman

Thinking About Lots of Things at Once without Getting Confused: Parallelism in Act 1

May 1981



As advances in computer architecture and changing economics make feasible machines with large-scale parallelism, Artificial Intelligence will require new ways of thinking about computation that can exploit parallelism effectively. We present the actor model of computation as being appropriate for parallel systems, since it organizes knowledge as active objects acting independently, and communicating by message passing. We describe the parallel constructs in our experimental actor interpreter Act 1. Futures create concurrency, by dynamically allocating processing resources much as Lisp dynamically allocates passive storage. Serializers restrict concurrency by constraining the order in which events take place, and have changeable local state. Using the actor model allows parallelism and synchronization to be implemented transparently, so that parallel or synchronized resources can be used as easily as their serial counterparts.


Author[s]: William A. Kornfeld

The Use of Parallelism to Implement a Heuristic Search

March 1981



The role of parallel processing in heuristic search is examined by means of an example (cryptarithmetic addition). A problem solver is constructed that combines the metaphors of constraint propagation and hypothesize-and- test. The system is capable of working on many incompatible hypotheses at one time. Furthermore, it is capable of allocating different amounts of processing power to running activities and and changing these allocations as computation proceeds. It is empirically found that the parallel algorithm is, on the average, more efficient than a corresponding sequential one. Implications of this for problem solving in general are discussed.


Author[s]: David A. Moon


June 1981



Chaosnet is a local network, that is, a system for communication among a group of computers located within about 1000 meters of each other. Originally developed by the Artificial Intelligence Laboratory as the internal communications medium of the Lisp Machine system, it has since come to be used to link a variey of machines around MIT and elsewhere.


Author[s]: William Daniel Hillis

Active Touch Sensing

April 1981



The mechanical hand of the future will roll a screw between its fingers and sense, by touch, which end is which. This paper describes a step toward such a manipulator – a robot finger that is used to recognize small objects by touch. The device incorporates a novel imaging tactile sensor – an artificial skin with hundreds of pressure sensors in a space the size of a finger tip. The sensor is mounted on a tendon-actuated mechanical finger, similar in size and range of motion to a human index finger. A program controls the finger, using it to press and probe the object placed in front of it. Based on how the object feels, the program guesses its shape and orientation and then uses the finger to test and refine the hypothesis. The device is programmed to recognize commonly used fastening devices – nuts, bolts, flats, washers, lock washers, dowel pins, cotter pins and set screws.


Author[s]: John M. Rubin and W.A. Richards

Color Vision and Image Intensities: When Are Changes Material?

May 1981



Marr has emphasized the difficulty in understanding a biological system or its components without some idea of its goals. In this paper, a preliminary goal for color vision is proposed and analyzed. That goal is to determine where changes of material occur in a scene (using only spectral information). This goal is challenging for two reasons. First, the effects of many processes (shadowing, shading from surface orientation changes, highlights, variations in pigment density) are confounded with the effects of material changes in the available image intensities. Second, material changes are essentially arbitrary. We are consequently led to a strategy of rejecting the presence of such confounding processes. We show there is a unique condition, the spectral crosspoint, that allows rejection of the hypothesis that measured image intensities arise from one of the confounding processes. (If plots are made of image intensity versus wavelength from two image regions, and the plots intersect, we say that there is a spectral crosspoint.) We restrict our attention to image intensities measured from regions on opposite sides of an edge because material changes almost always cause edges. Also, by restricting our attention to luminance discontinuities, we can avoid peculiar conspiracies of confounding processes that might mimic a material change. Our crosspoint conjecture is that biological visual systems interpret spectral crosspoints across edges as material changes. A circularly symmetric operator is designed to detect crosspoints: it turns out to resemble the double-opponent cell which is commonplace in biological color vision systems.


Author[s]: Patrick H. Winston

Learning New Principles from Precedents and Exercises: The Details

November 1981



Much Learning is done by way of studying precedents and exercises. A teacher supplies a story, gives a problem, and expects a student both to solve a problem and to discover a principle. The student must find the correspondence between the story and the problem, apply the knowledge in the story to solve the problem, generalize to form a principle, and index the principle so that it can be retrieved when appropriate. This sort of learning pervades Management, Political science, Economics, Law, and Medicine as well as the development of common-sense knowledge about life in general. This paper presents a theory of how it is possible to learn by precedents and exercises and describes an implemented system that exploits the theory. The theory holds that causal relations identify the regularities that can be exploited from past experience, given a satisfactory representation for situations. The representation used stresses actors and objects which are taken from English-like input and arranged into a kind of semantic network. Principles emerge in the form of production rules which are expressed in the same way situations are.


Author[s]: William Douglas Clinger

Foundations of Actor Semantics

May 1981



The actor message-passing model of concurrent computation has inspired new ideas in the areas of knowledge-based systems, programming languages and their semantics, and computer systems architecture. The model itself grew out of computer languages such as Planner, Smalltalk, and Simula, and out of the use of continuations to interpret imperative constructs within A-calculus. The mathematical content of the model has been developed by Carl Hewitt, Irene Greif, Henry Baker, and Giuseppe Attardi. This thesis extends and unifies their work through the following observations. The ordering laws postulated by Hewitt and Baker can be proved using a notion of global time. The most general ordering laws are in fact equivalent to an axiom of realizability in global time. Independence results suggest that some notion of global time is essential to any model of concurrent computation. Since nondeterministic concurrency is more fundamental than deterministic sequential computation, there may be no need to take fixed points in the underlying domain of a power domain. Power domains built from incomplete domains can solve the problem of providing a fixed point semantics for a class of nondeterministic programming languages in which a fair merge can be written. The event diagrams of Greif's behavioral semantics, augmented by Baker's pending events, form an incomplete domain. Its power domain is the semantic domain in which programs written in actor-based languages are assigned meanings. This denotational semantics is compatible with behavioral semantics. The locality laws postulated by Hewitt and Baker may be proved for the semantics of an actor-based language. Altering the semantics slightly can falsify the locality laws. The locality laws thus constrain what counts as an actor semantics.


Author[s]: Charles Rich and Richard C. Waters

Abstraction, Inspection and Debugging in Programming

June 1981



We believe that software engineering has much to learn from other mature engineering disciplines, such as electrical engineering, and that the problem solving behaviors of engineers in different disciplines have many similarities. Three key ideas in current artificial intelligence theories of engineering problem solving are: Abstraction – using a simplified view of the problem to guide the problem solving process. Inspection – problem solving by recognizing the form (“plan”) of a solution. Debugging – incremental modification of an almost satisfactory solution to a more satisfactory one. These three techniques are typically used together in a paradigm which we call AID (for Abstraction, Inspection, Debugging): First an abstract model of the problem is constructed in which some important details are not intentionally omitted. In this simplified view inspection methods are more likely to succeed, yielding the initial form of a solution. Further details of the problem are then added one at a time with corresponding incremental modifications to the solution. This paper states the goals and milestones of the remaining three years of a five year research project to study the fundamental principles underlying the design and construction of large software systems and to demonstrate the feasibility of a computer aided design tool for this purpose, called the programmer’s apprentice.


Author[s]: John M. Hollerbach and Tamar Flash

Dynamic Interactions Between Limb Segments During Planar Arm Movement

November 1981



Movement of multiple segment limbs requires generation of appropriate joint torques which include terms arising from dynamic interactions among the moving segments as well as from such external forces as gravity. The interaction torques, arising from inertial, centripetal, and Coriolis forces, are not present for single joint movements. The significance of the individual interaction forces during reaching movements in a horizontal plane involving only the shoulder and elbow joints has been assessed for different movement paths and movement speeds. Trajectory formation strategies which simplify the dynamics computation are presented.


Author[s]: Barbara Sue Kerne Steele

An Accountable Source-To-Source Transformation System

June 1981



Though one is led to believe that program transformation systems which perform source-to-source transformations enable the user to understand and appreciate the resulting source program, this is not always the case. Transformations are capable of behaving and/or interacting in unexpected ways. The user who is interested in understanding the whats, whys, wheres, and hows of the transformation process is left without tools for discovering them. I provide an initial step towards the solution of this problem in the form of an accountable source- to-source transformation system. It carefully records the information necessary to answer such questions, and provides mechanisms for the retrieval of this information. It is observed that though this accountable system allows the user access to relevant facts from which he may draw conclusions, further study is necessary to make the system capable of analyzing these facts itself.


Author[s]: Kent A. Stevens

Evidence Relating Subjective Contours and Interpretations Involving Occlusion

June 1981



Subjective contours, according to one theory, outline surfaces that are apparently interposed between the viewer and background (because of the disruption of background figures, sudden termination of lines, and other occlusion “cues”) but are not explicitly outlined by intensity discontinuities. This theory predicts that if occlusion cures are not interpreted as evidence of occlusion, no intervening surface need be postulated, hence no subjective contours would be seen. This prediction, however, is difficult to test because observers normally interpret the cues as occlusion evidence and normally see the subjective contours. This article describes a patient with visual agnosia who is both unable to make the usual occlusion interpretations and is unable to see subjective contours. He has, however, normal ability to interpret standard visual illusions, stereograms, and in particular, stereogram versions of the standard subjective contour figures, which elicit to him strong subjective edges in depth (corresponding to the subjective contours viewed in the monocular versions of the figures).


Author[s]: Daniel G. Shapiro

Sniffer: A System that Understands Bugs

June 1981



This paper presents a bug understanding system, called sniffer, which applies inspection methods to generate a deep understanding of a narrow class of errors. Sniffer is an interactive debugging aide. It can locate and identify error-containing implementations of typical programming clichés, and it can describe them using the terminology employed by expert programmers.


Author[s]: Laurence Miller

Natural Learning

October 1981



This memo reports the results of a case study into how children learn in the absence of explicit teaching. The three subjects, an eight year old, a ten year old and a thirteen year old were observed in both of two experimental micro-worlds. The first of these micro-worlds, called the Chemicals World, included a large table, a collection of laboratory and household chemicals, and apparatus for conducting experiments with chemicals; the second, called the Mork and Mindy World included a collection of video taped episodes of the television series Mork and Mindy, a video-tape machine and experimenter with whom the subjects could discuss the episodes. The main result of the study is a theory of how children’s interests interact with knowledge embodied in their environment causing them to learn new powerful ideas. An early version of this theory is presented in chapter five.


Author[s]: William A. Kornfeld and Carl Hewitt

The Scientific Community Metaphor

January 1981



Scientific communnities have proven to be extremely successful at solving problems. They are inherently parallel systems and their macroscopic nature makes them amenable to careful study. In this paper the character of scientific research is examined drawing on sources in the philosophy and history of science. We maintain that the success of scientific research depends critically on its concurrency and pluralism. A variant of the language Ether is developed that embodies notions of concurrency necessary to emulate some of the problem solving behavior of scientific communities. Capabilities of scientific communities are discussed in parallel with simplified models of these capabilities in this language.


Author[s]: Giuseppe Attardi and Maria Simi

Semantics of Inheritance and Attributions in the Description System Omega

August 1981



Omega is a description system for knowledge embedding which incorporates some of the attractive modes of expression in common sense reasoning such as descriptions, inheritance, quantification, negation, attributions and multiple viewpoints. A formalization of Omega is developed as a framework for investigations on the foundations of knowledge representation. As a logic, Omega achieves the goal of an intuitively sound and consistent theory of classes which permits unrestricted abstraction within a powerful logic system. Description abstraction is the construct provided in Omega corresponding to set abstraction. Attributions and inheritance are the basic mechanisms for knowledge structuring. To achieve flexibility and incrementality, the language allows descriptions with an arbitrary number of attributions, rather than predicates with a fixed number of arguments as in predicate logic. This requires a peculiar interpretation for instance descriptions, which in turn provides insights into the use and meaning of several kinds of attributions. The formal treatment consists in presenting semantic models for Omega, deriving an axiomatization and establishing the consistency and completeness of the logic.


Author[s]: Richard M. Stallman

A Local Front End for Remote Editing

February 1982



The Local Editing Protocol allows a local programmable terminal to execute the most common editing commands on behalf of an extensible text editor on a remote system, thus greatly improving speed of response without reducing flexibility. The Line Saving Protocol allows the local system to save text which is not displayed, and display it again later when it is needed, under the control of the remote editor. Both protocols are substantially system and editor independent.


Author[s]: Richard M. Stallman

The SUPDUP Protocol

July 1983



The SUPDUP protocol provides for login to a remote system over a network with terminal- independent output, so that only the local system need know how to handle the user’s terminal. It offers facilities for graphics and for local assistance to remote text editors. This memo contains a complete description of the SUPDUP protocol in fullest possible detail.


Author[s]: Tomaso Poggio

Marr's Approach to Vision

August 1981



In the last seven years a new computational approach has led to promising advances in the understanding of biological visual perception. The foundations of the approach are largely due to the work of a single man, David Marr at M.I.T. Now, after his death in Boston on November 17th 1980, research in vision will not be the same for the growing number of those who are following his lead.


Author[s]: W. Daniel Hillis

The Connection Machine

September 1981



This paper describes the connection memory, a machine for concurrently manipulating knowledge stored in semantic networks. We need the connection memory because conventional serial computers cannot move through such networks fast enough. The connection memory sidesteps the problem by providing processing power proportional to the size of the network. Each node and link in the network has its own simple processor. These connect to form a uniform locally-connected network of perhaps a million processor/memory cells


Author[s]: Marvin Minsky

Nature Abhors an Empty Vacuum

August 1981



Imagine a crystalline world of tiny, discrete “cells”, each knowing only what its nearest neighbors do. Each volume of space contains only a finite amount of information, because space and time come in discrete units. In such a universe, we’ll construct analogs of particles and fields – and ask what it would mean for these to satisfy constraints like conservation of momentum. In each case classical mechanics will break down – on scales both small and large, and strange phenomena emerge: a maximal velocity, a slowing of internal clocks, a bound on simultaneous measurement, and quantum- like effects in very weak or intense fields. This fantasy about conservation in cellular arrays was inspired by this first conference on computation and physics, a subject destined to produce profound and powerful theories. I wish this essay could include one such; alas, it only portrays images of what such theories might be like. The “cellular array” idea is popular already in such forms as Ising models, renormalization theories, the “Game of Life” and Von Neumann’s work on self- producing machines. This essay exploits many unpublished ideas I got from Edward Fredkin. The ideas about field and particle are original; Richard Feynman persuaded me to consider fields instead of forces, but is not responsible for my compromise on potential surfaces. I also thank Danny Hillis and Richard Stallman for other ideas.


Author[s]: W.A. Richards

A Lightness Scale from Image Intensity Distributions

August 1981



A lightness scale is derived from a theoretical estimate of the probability distribution of image intensities for natural scenes. The derived image intensity distribution considers three factors: reflectance, surface orientation and illumination, and surface texture (or roughness). The convolution of the effects of these three factors yields the theoretical probability distribution of image intensities. A useful lightness scale should be the integral of this probability density function for then equal intervals along the scale are equally probable and carry equal information. The result is a scale similar to that used in photography, or by the nervous system as its transfer function.


Author[s]: Michael Dennis Riley

The Representation of Image Texture

September 1981



This thesis explores how to represent image texture in order to obtain information about the geometry and structure of surfaces, with particular emphasis on locating surface discontinuities. Theoretical and psychophysical results lead to the following conclusions for the representation of image texture: (1) A texture edge primitive is needed to identify texture change contours, which are formed by an abrupt change in the 2-D organization of similar items in an image. The texture edge can be used for locating discontinuities in surface structure and surface geometry and for establishing motion correspondence. (2) Abrupt changes in attributes that vary with changing surface geometry – orientation, density, length, and width – should be used to identify discontinuities in surface geometry and surface structure. (3) Texture tokens are needed to separate the effects of different physical processes operating on a surface. They represent the local structure of the image texture. Their spatial variation can be used in the detection of texture discontinuities and texture gradients, and their temporal variation may be used for establishing motion correspondence. What precisely constitutes the texture tokens is unknown; it appears, however, that the intensity changes alone will not suffice, but local groupings of them may. (4) The above primitives need to be assigned rapidly over a large range in an image.


Author[s]: T. Poggio and V. Torre

Microelectronics In Nerve Cells: Dendritic Morphology and Information Processing

October 1981



The electrical properties of the different anatomical types of retinal ganglion cells in the cat were calculated on the basis of passive cable theory from measurements made on histological material provided by Boycott and Wassle (1974). The interactions between excitation and inhibition when the inhibitory battery is near the resting potential can be strongly nonlinear in these cells. We analyse some of the integrative properties of an arbitrary passive dendritic tree and we then derive the functional properties which are characteristic for the various types of ganglion cells. In particular, we derive several general results concerning the spatial specificity of shunting inhibition in “vetoing” an excitatory input (the “on path” property) and its dependence on the geometrical and electric properties of the dendritic tree. Our main conclusion is that specific branching patterns coupled with a suitable distribution of synapses are able to support complex information processing operations on the incoming signals. Thus, a neuron seems likely to resemble an (analog) ISI circuit with thousands of elementary processing units – the synapses – rather than a single logical gate. A dendritic tree would be near to the ultimate in microelectronics with little patches of postsynaptic membrane representing the fundamental units for several elementary computations.


Author[s]: David Chapman

A Program Testing Assistant

November 1981



This paper describes the design and implementation of a program testing assistant which aids a programmer in the definition, execution, and modification of test cases during incremental program development. The testing assistant helps in the interactive definition of test cases and executes them automatically when appropriate. It modifies test cases to preserve their usefulness when the program they test undergoes certain types of design changes. The testing assistant acts as a fully integrated part of the programming environment and cooperates with existing programming tools, including a display editor, compiler, interpreter, and debugger.


Author[s]: Robert Lawler

Some Powerful Ideas

December 1981



Here is a set of problem solving ideas (absorbed by and developed through the MIT Logo project over many years) presented in such a way as to useful to someone with a Logo computer. With the ideas on unbound, single sheets, you can easily pick out those you like and set aside the others. The ideas vary in sophistication and accessibility: no threshold, no ceiling.


Author[s]: Michael Brady

Computational Approaches to Image Understanding

October 1981



Recent theoretical developments in Image Understanding are surveyed. Among the issues discussed are: edge finding, region finding, texture, shape from shading, shape from texture, shape from contour, and the representations of surfaces and objects. Much of the work described was developed in the DARPA Image Understanding project.


Author[s]: Michael Brady and Berthold K.P. Horn

Rotationally Symmetric Operators for Surface Interpolation

November 1981



The use of rotationally symmetric operators in vision is reviewed and conditions for rotational symmetry are derived for linear and quadratic forms in the first and second partial directional derivatives of a function f(x,y). Surface interpolation is considered to be the process of computing the most conservative solution consistent with boundary conditions. The “most conservative” solution is modeled using the calculus of variations to find the minimum function that satisfies a given performance index. To guarantee the existence of a minimum function, Grimson has recently suggested that the performance index should be a semi-norm. It is shown that all quadratic forms in the second partial derivatives of the surface satisfy this criterion. The seminorms that are, in addition, rotationally symmetric form a vector space whose basis is the square Laplacian and the quadratic variation. Whereas both seminorms give rise to the same Euler condition in the interior, the quadratic variation offers the tighter constraint at the boundary and is to be preferred for surface interpolation.


Author[s]: Henry Lieberman

Seeing What Your Programs Are Doing

February 1982



An important skill in programming is being able to visualize the operation of procedures, both for constructing programs and debugging them. Tinker is a programming environment for Lisp that enables the programmer to “see what the program is doing” while the program is being constructed, by displaying the result of each step in the program on representative examples. To help the reader visualize the operation of Tinker itself, an example is presented of how he or she might use Tinker to construct an alpha-beta tree search program.


Author[s]: T. Poggio and C. Koch

Nonlinear Interactions in a Dendritic Tree: Localization, Timing and Role in Information Processing

September 1981



In a dendritic tree transient synaptic inputs activating ionic conductances with an equilibrium potential near the resting potential can veto very effectively other excitatory inputs. Analog operations of this type can be very specific with respect to relative locations of the inputs and their timing. We examine with computer experiments the precise conditions underlying this effect in the case of b-like cat retinal ganglion cell. The critical condition required for strong and specific interactions is that the peak inhibitory conductance change must be sufficiently large almost independently of other electrical parameters. In this case, a passive dendritic tree may perform hundreds of independent analog operations on its synaptic inputs, without requiring any threshold mechanism.


Author[s]: Whitman Richards

How to Play Twenty Questions with Nature and Win

December 1982



The 20 Questions Game played by children has an impressive record of rapidly guessing an arbitrarily selected object with rather few, well-chosen questions. This same strategy can be used to drive the perceptual process, likewise beginning the search with the intent of deciding whether the object is Animal- Vegetable-or-Mineral. For a perceptual system, however, several simple questions are required even to make this first judgment as to the Kingdom the object belongs. Nevertheless, the answers to these first simple questions, or their modular outputs, provide a rich data base which can serve to classify objects or events in much more detail than one might expect, thanks to constraints and laws imposed upon natural processes and things. The questions, then, suggest a useful set of primitive modules for initializing perception.


Author[s]: John M. Hollerbach

Workshop on the Design and Control of Dextrous Hands

April 1982



The Workshop for the Design and Control of Dexterous Hands was held at the MIT Artificial Intelligence Laboratory on November 5-6, 1981. Outside experts were brought together to discuss four topics: kinematics of hands, actuation and materials, touch sensing and control. This report summarizes the discussions of the participants and attempts to identify a consensus on applications, mechanical design, and control.


Author[s]: Anna R. Bruss and Berthold K.P. Horn

Passive Navigation

November 1981



A method is proposed for determining the motion of a body relative to a fixed environment using the changing image seen by a camera attached to the body. The optical flow in the image plane is the input, while the instantaneous rotation and translation of the body are the output. If optical flow could be determined precisely, it would only have to be known at a few places to compute the parameters of the motion. In practice, however, the measured optical flow will be somewhat inaccurate. It is therefore advantageous to consider methods which use as much of the available information as possible. We employ a least-squares approach which minimizes some measure of the discrepancy between the measured flow and that predicted from the computed motion parameters. Several different error norms are investigated. In general, our algorithm leads to a system of nonlinear equations from which the motion parameters may be computed numerically. However, in the special cases where the motion of the camera is purely translational or purely rotational, use of the appropriate norm leads to a system of equations from which these parameters can be determined in closed form.


Author[s]: W.E.L Grimson

The Implicit Constraints of the Primal Sketch

October 1981



Computational theories of structure-from- motion and stereo vision only specify the computation of three-dimensional surface information at points in the image at which the irradiance changes. Yet, the visual perception is clearly of complete surfaces, and this perception is consistent for different observers. Since mathematically the class of surfaces which could pass through the known boundary points provided by the stereo system is infinite and contains widely varying surfaces, the visual system must incorporate some additional constraints besides the known points in order to compute the complete surface. Using the image irradiance equation, we derive the surface consistency constraint, informally referred to as no news is good news. The constraint implies that the surface must agree with the information from stereo or motion correspondence, and not vary radically between these points. An explicit form of this surface consistency constraint is derived, by relating the probability of a zero- crossing in a region of the image to the variation in the local surface orientation of the surface, provided that the surface albedo and the illumination are roughly constant. The surface consistency constraint can be used to derive an algorithm for reconstructing the surface that “best” fits the surface information provided by stereo or motion correspondence.


Author[s]: Kenneth D. Forbus

Qualitative Process Theory

May 1983



Things move, collide, flow, bend, heat up, cool down, stretch, break and boil. These and other things that happen to cause changes in objects over time are intuitively characterized as processes. To understand common sense physical reasoning and make machines that interact significantly with the physical world we must understand the qualitative reasoning about processes, their effects, and their limits. Qualitative Process theory defines a simple notion of physical process that appears quite useful as a language in which to write physical theories. Reasoning about processes also motivates a new qualitative representation for quantity, the Quantity Space. This paper includes the basic definitions of Qualitative Process theory, describes several different kinds of reasoning that can be performed with them, and discusses its implications for causal reasoning. The use of the theory is illustrated by several examples, including figuring out that a boiler can blow up, that an oscillator with friction will eventually stop, and how to say that you can pull with a string, but not push with it.


Author[s]: Randall Davis

Expert Systems: Where Are We? And Where Do We Go from Here?

June 1982



Work on Expert Systems has received extensive attention recently, prompting growing interest in a range of environments. Much has been made of the basic concept and the rule-based system approach typically used to construct the programs. Perhaps this is a good time then to review what we know, assess the current prospects, and suggest directions appropriate for the next steps of basic research. I’d like to do that today and propose to do it by taking you on a journey of sorts, a metaphorical trip through the State of the Art of Expert Systems. We’ll wander about the landscape, ranging from the familiar territory of the Land of Accepted Wisdom, to the vast unknowns at the Frontiers of Knowledge. I guarantee we’ll all return safely, so come along…


Author[s]: Michael Brady and W. Eric L. Grimson

The Perception of Subjective Surfaces

November 1981



It is proposed that subjective contours are an artifact of the perception of natural three- dimensional surfaces. A recent theory of surface interpolation implies that “subjective surfaces” are constructed in the visual system by interpolation between three-dimensional values arising from interpretation of a variety of surface cues. We show that subjective surfaces can take any form, including singly and doubly curved surfaces, as well as the commonly discussed fronto-parallel planes. In addition, it is necessary in the context of computational vision to make explicit the discontinuities, both in depth and in surface orientation, in the surfaces constructed by interpolation. It is proposed that subjective surfaces and subjective contours are demonstrated. The role played by figure completion and enhanced brightness contrast in the determination of subjective surfaces is discussed. All considerations of surface perception apply equally to subjective surfaces.


Author[s]: David Allen McAllester

Reasoning Utility Package User's Manual, Version One

April 1982



RUP (Reasoning Utility Package) is a collection of procedures for performing various computations relevant to automated reasoning. RUP contains a truth maintenance system (TMS) which can be used to perform simple propositional deduction (unit clause resolution) to record justifications, to track down underlying assumptions and to perform incremental modifications when premises are changed. This TMS can be used with an automatic premise controller which automatically retracts “assumptions” before “solid facts” when contradictions arise and searches for the most solid proof of an assertion. RUP also contains a procedure for efficiently computing all the relevant consequences of any set of equalities between ground terms. A related utility computes “substitution simplifications” of terms under an arbitrary set of unquantified equalities and a user defined simplicity order. RUP also contains demon writing macros which allow one to write PLANNER like demons that trigger on various types of events in the data base. Finally there is a utility for reasoning about partial orders and arbitrary transitive relations. In writing all of these utilities an attempt has been made to provide a maximally flexible environment for automated reasoning.


Author[s]: W. Richards, H.K. Nishihara and B. Dawson

CARTOON: A Biologically Motivated Edge Detection Algorithm

June 1982



Caricatures demonstrate that only a few significant “edges” need to be captured to convey the meaning of a complex pattern of image intensities. The most important of these “edges” are image intensity changes arising from surface discontinuities or occluding boundaries. The CARTOON algorithm is an attempt to locate these special intensity changes using a modification of the zero-crossing coincidence scheme suggested by Marr and Hildreth (1980).


Author[s]: Steven W. Zucker, Kent A. Stevens and Peter T. Sander

The Relation Between Proximity and Brightness Similarity in Dot Patterns

May 1982



The Gestalt studies demonstrated the tendency to visually organize dots on the basis of similarity, proximity, and global properties such as closure, good continuation, and symmetry. The particular organization imposed on a collection of dots is thus determined by many factors, some local, some global. We discuss computational reasons for expecting the initial stages of grouping to be achieved by processes with purely local support. In the case of dot patterns, the expectation is that neighboring dots are grouped on the basis of proximity and similarity of contrast, by processes that are independent of the overall organization and the various global factors. We describe experiments that suggest a purely local relationship between proximity and brightness similarity in perceptual grouping.


Author[s]: Demetri Terzopoulos

Multi-Level Reconstruction of Visual Surfaces: Variational Principles and Finite Element Representations

April 1982



Computational modules early in the human vision system typically generate sparse information about the shapes of visible surfaces in the scene. Moreover, visual processes such as stereopsis can provide such information at a number of levels spanning a range of resolutions. In this paper, we extend this multi-level structure to encompass the subsequent task of reconstructing full surface descriptions from the sparse information. The mathematical development proceeds in three steps. First, the surface most consistent with the sparse constraints is characterized as the solution to an equilibrium state of a thin flexible plate. Second, local, finite element representations of surfaces are introduced and, by applying the finite element method, the continuous variational principle is transformed into a discrete problem in the form of a large system of linear algebraic equations whose solution is computable by local-support, cooperative mechanisms. Third, to exploit the information available at each level of resolution, a hierarchy of discrete problems is formulated and a highly efficient multi-level algorithm, involving both intra-level relaxation processes and bi-directional inter-level algorithm, involving both intra-level relaxation processes and bidirectional inter-level local interpolation processes is applied to their simultaneous solution.. Examples of the generation of hierarchies of surface representations from stereo constraints are given. Finally, the basic surface approximation problem is revisited in a broader mathematical context whose implications are of relevance to vision.


Author[s]: Daniel G. Theriault

A Primer for the Act-1 Language

April 1982



This paper describes the current design for the Act-1 computer programming language and describes the Actor computational model, which the language was designed to support. It provides a perspective from which to view the language, with respect to existing computer language systems and to the computer system and environment under development for support of the language. The language is informally introduced in a tutorial fashion and demonstrated through examples. A programming strategy for the language is described, further illustrating its use.


Author[s]: Ken Haase

CAULDRONS: An Abstraction for Concurrent Problem Solving

September 1986



This research extends a tradition of distributed theories of mind into the implementation of a distributed problem solver. In this problem solver a number of ideas from Minsky's Society of Mind are implemented and are found to provide powerful abstractions for the programming of distributed systems. These abstractions are the cauldron, a mechanism for instantiating reasoning contexts, the frame, a way of modularly describing those contexts and the goal-node, a mechanism for bringing a particular context to bear on a specific task. The implementation of both these abstractions and the distributed problem solver in which they run is described, accompanied by examples of their application to various domains.


Author[s]: Rodney A. Brooks

Solving the Find-Path Problem by Representing Free Space as Generalized Cones

May 1982



Free space is represented as a union of (possibly overlapping) generalized cones. An algorithm is presented which efficiently finds good collision free paths for convex polygonal bodies through space littered with obstacle polygons. The paths are good in the sense that the distance of closest approach to an obstacle over the path is usually far from minimal over the class of topologically equivalent collision free paths. The algorithm is based on characterizing the volume swept by a body as it is translated and rotated as a generalized cone and determining under what conditions generalized cone is a subset of another.


Author[s]: Tomaso Poggio, Kenneth Nielsen and Keith Nishihara

Zero-Crossings and Spatiotemporal Interpretation in Vision

May 1982



We will briefly outline a computational theory of the first stages of human vision according to which (a) the retinal image is filtered by a set of centre-surround receptive fields (of about 5 different spatial sizes) which are approximately bandpass in spatial frequency and (b) zero-crossings are detected independently in the output of each of these channels. Zero-crossings in each channel are then a set of discrete symbols which may be used for later processing such as contour extraction and stereopsis. A formulation of Logan’s zero-crossing results is proved for the case of Fourier polynomials and an extension of Logan’s theorem to 2- dimentsional functions is also approved. Within this framework, we shall describe an experimental and theoretical approach (developed by one of us with M. Fahle) to the problem of visual acuity and hyperacuity of human vision. The positional accuracy achieved, for instance, in reading a vernier is astonishingly high, corresponding to a fraction of the spacing between adjacent photoreceptors in the fovea. Stroboscopic presentation of a moving object can be interpolated by our visual system into the perception of continuous motion; and this “spatio-temporal” interpolation also can be very accurate. It is suggested that the known spatiotemporal properties of the channels envisaged by the theory of visual processing outlined above implement an interpolation scheme which can explain human vernier acuity for moving targets.


Author[s]: Kent A. Stevens

Implementation of a Theory for Inferring Surface Shape from Contours

August 1982



Human vision is adept at inferring the shape of a surface from the image of curves lying across the surface. The strongest impression of 3-D shape derives from parallel (but not necessarily equally spaced) contours. In [Stevens 1981a] the computational problem of inferring 3-D shape from image configurations is examined, and a theory is given for how the visual system constrains the problem by certain assumptions. The assumptions are three: that neither the viewpoint not the placement of the physical curves on the surface is misleading, and that the physical curves are lines of curvature across the surface. These assumptions imply that parallel image contours correspond to parallel curves lying across an approximately cylindrical surface. Moreover, lines of curvature on a cylinder are geodesic and planar. These properties provide strong constraint on the local surface orientation. We describe a computational method embodying these geometric constraints that is able to determine the surface orientation even in places where locally it is very weakly constrained, by extrapolating from places where it is strongly constrained. This computation has been implemented, and predicts local surface orientation that closely matches the apparent orientation. Experiments with the implementation support the theory that our visual interpretation of surface shape from contour assumes the image contours correspond to lines of curvature.


Author[s]: Boris Katz and Patrick H. Winston

Parsing and Generating English Using Commutative Transformations

May 1982



This paper is about an implemented natural language interface that translates from English into semantic net relations and from semantic net relations back into English. The parser and companion generator were implemented for two reasons: (a) to enable experimental work in support of a theory of learning by analogy; (b) to demonstrate the viability of a theory of parsing and generation built on commutative transformations. The learning theory was shaped to a great degree by experiments that would have been extraordinarily tedious to perform without the English interface with which the experimental data base was prepared, revise, and revised again. Inasmuch as current work on the learning theory is moving toward a tenfold increase in data-base size, the English interface is moving from a facilitating role to an enabling one. The parsing and generation theory has two particularly important features: (a) the same grammar is used for both parsing and generation; (b) the transformations of the grammar are commutative. The language generation procedure converts a semantic network fragment into kernel frames, chooses the set of transformations that should be performed upon each frame, executes the specified transformations, combines the altered kernels into a sentence, performs a pronominalization process, and finally produces the appropriate English word string. Parsing is essentially the reverse of generation. The first step in the parsing process is splitting a given sentence into a set of kernel clauses along with a description of how those clauses hierarchically related to each other. The clauses are hierarchically related to each other. The clauses are used to produce a matrix embedded kernel frames, which in turn supply arguments to relation- creating functions. The evaluation of the relation-creating functions results in the construction of the semantic net fragments.


Author[s]: Patrick H. Winston

Learning by Augmenting Rules and Accumulating Censors

May 1982



This paper is a synthesis of several sets of ideas: ideas about learning from precedents and exercises, ideas about learning using near misses, ideas about generalizing if-then rules, and ideas about using censors to prevent procedure misapplication. The synthesis enables two extensions to an implemented system that solves problems involving precedents and exercises and that generates if-then rules as a byproduct . These extensions are as follows: If-then rules are augmented by unless conditions, creating augmented if-then rules. An augmented if- then rule is blocked whenever facts in hand directly demonstrate the truth of an unless condition, the rule is called a censor. Like ordinary augmented if-then rules, censors can be learned. Definition rules are introduced that facilitate graceful refinement. The definition rules are also augmented if-then rules. They work by virtue of unless entries that capture certain nuances of meaning different from those expressible by necessary conditions. Like ordinary augmented if-then rules, definition rules can be learned. The strength of the ideas is illustrated by way of representative experiments. All of these experiments have been performed with an implemented system.


Author[s]: Patrick H. Winston, Thomas O. Binford, Boris Katz and Michael Lowry

Learning Physical Descriptions from Functional Definitions, Examples, and Precedents

November 1982



It is too hard to tell vision systems what things look like. It is easier to talk about purpose and what things are for. Consequently, we want vision systems to use functional descriptions to identify things when necessary, and we want them to learn physical descriptions for themselves, when possible. This paper describes a theory that explains how to make such systems work. The theory is a synthesis of two sets of ideas: ideas about learning from precedents and exercises developed at MIT and ideas about physical description developed at Stanford. The strength of the synthesis is illustrated by way of representative experiments. All of these experiments have been performed with an implemented system.


Author[s]: Richard C. Waters

LetS: An Expressional Loop Notation

February 1983



Many loops can be more easily understood and manipulated if they are viewed as being built up out of operations on sequences of values. A notation is introduced which makes this viewpoint explicit. Using it, loops can be represented as compositions of functions operating on sequences of values. A library of standard sequence functions is provided along with facilities for defining additional ones. The notation is not intended to be applicable to every kind of loop. Rather, it has been simplified wherever possible so that straightforward loops can be represented extremely easily. The expressional form of the notation makes it possible to construct and modify such loops rapidly and accurately. The implementation of the notation does not actually use sequences but rather compiles loop expressions into iterative loop code. As a result, using the notation leads to no reduction in run time efficiency.


Author[s]: Gerald Barber

Supporting Organizational Problem Solving with a Workstation

July 1982



This paper describes an approach to supporting work in the office. Using and extending ideas from the field of Artificial Intelligence (AI) we describe office work as a problem solving activity. A knowledge embedding language called Omega is used to embed knowledge of the organization into an office worker’s workstation in order to support the office worker in his or her problem solving. A particular approach to reasoning about change and contradiction is discussed. This approach uses Omega’s viewpoint mechanism. Omega’s viewpoint mechanism is a general contradiction handling facility. Unlike other Knowledge Representation systems, when a contradiction is reached the reasons for the contradiction can be analyzed by the deduction mechanism without having to resort to a backtracking mechanism. The Viewpoint mechanism is the heart of the Problem Solving Support Paradigm. This paradigm supplements the classical AI view of problem solving. Office workers are supported using the Problem Solving Support Paradigm. An example is presented where Omega’s facilities are used to support an office worker’s problem solving activities. The example illustrates the use of viewpoints and of Omega’s capabilities to reason about it’s own reasoning process.


Author[s]: Tomaso Poggio

Visual Algorithms

May 1982



Nonlinear, local and highly parallel algorithms can perform several simple but important visual computations. Specific classes of algorithms can be considered in an abstract way. I study here the class of polynomial algorithms to exemplify some of the important issues for visual processing like linear vs. nonlinear and local vs. global. Polynomial algorithms are a natural extension of Perceptrons to time dependent grey level images.. Although they share most of the limitations of Perceptrons, they are powerful parallel computational devices. Several of their properties are characterized and especially (a) their equivalence with Perceptrons for geometrical figures and (b) the synthesis of non-linear algorithms (mappings) via associative learning. Finally, the paper considers how algorithms of this type could be implemented in nervous hardware, in terms of synaptic interactions strategically located in a dendritic tree.


Author[s]: Rodney A. Brooks and Tomas Lozano-Perez

A Subdivision Algorithm in Configuration Space for Findpath with Rotation

December 1982



A hierarchical representation for configuration space is presented, along with an algorithm for searching that space for collision-free paths. The detail of the algorithm are presented for polygonal obstacles and a moving object with two translational and one rotational degrees of freedom.


Author[s]: Rodney A. Brooks

Symbolic Error Analysis and Robot Planning

September 1982



A program to control a robot manipulator for industrial assembly operations must take into account possible errors in parts placement and tolerances of the parts themselves. Previous approaches to this problem have been to (1) engineer the situation so that the errors are small or (2) let the programmer analyze the errors and take explicit account of them. This paper gives the mathematical underpinnings for building programs (plan checkers) to carry out approach (2) automatically. The plan checker uses a geometric CAD-type database to infer the effects of actions and the propagation of errors. It does this symbolically rather than numerically, so that computations can be reversed and desired resultant tolerances can be used to infer required initial tolerances or the necessity for sensing. The checker modifies plans to include sensing and adds constraints to the plan which ensure that it will succeed. An implemented system is described and results of its execution are presented. The plan checker could be used as part of an automatic planning system of as an aid to a human robot programmer.


Author[s]: John M. Hollerbach

Computers, Brains, and the Control of Movement

June 1982



Many of the problems associated with the planning and execution of human arm trajectories are illuminated by planning and control strategies which have been developed for robotic manipulators. This comparison may provide explanations for the predominance of straight line trajectories in human reaching and pointing movements, the role of feedback during arm movement, as well as plausible compensatory mechanisms for arm dynamics.


Author[s]: Tomaso Poggio and B.L. Rosser

The Computational Problem of Motor Control

May 1983



We review some computational aspects of motor control. The problem of trajectory control is phrased in terms of an efficient representation of the operator connecting joint angles to joint torques. Efficient look-up table solutions of the inverse dynamics are related to some results on the decomposition of function of many variables. In a biological perspective, we emphasize the importance of the constraints coming from the properties of the biological hardware for determining the solution to the inverse dynamic problem.


Author[s]: Robert W. Sjoberg

Atmospheric Effects in Satellite Imaging of Mountainous Terrain

September 1982



Author[s]: Matthew Thomas Mason

Manipulator Grasping and Pushing Operations

June 1982



The primary goal of this research is to develop theoretical tools for analysis, synthesis, application of primitive manipulator operations. The primary method is to extend and apply traditional tools of classical mechanics. The results are of such a general nature that they address many different aspects of industrial robotics, including effector and sensor design, planning and programming tools and design of auxiliary equipment. Some of the manipulator operations studied are: (1) Grasping an object. The object will usually slide and rotate during the period between first contact and prehension. (2) Placing an object. The object may slip slightly in the fingers upon contact with the table as the base aligns with the table. (3) Pushing. Often the final stage of mating two parts involves pushing one object into the other.


Author[s]: Carl Hewitt and Peter de Jong

Open Systems

December 1982



This paper describes some problems and opportunities associated with conceptual modeling for the kind of “open systems” we foresee must and will be increasingly recognized as a central line of computer system development. Computer applications will be based on communication between sub-systems which will have been developed separately and independently. Some of the reasons for independent development are the following: competition, different goals and responsibilities, economics, and geographical distribution. We must deal with all the problems that arise from this conceptual disparity of sub-systems which have been independently developed. Sub- systems will be open-ended and incremental – undergoing continual evolution. There are no global objects. The only thing that all the various sub-systems hold in common is the ability to communicate with each other. In this paper we study Open Systems from the viewpoint of Message Passing Semantics, a research programme to explore issues in the semantics of communication in parallel systems such as negotiation, transaction management, problem solving, change, and self-knowledge.


Author[s]: C.J. Barter

Policy-Protocol Interaction in Composite Processes

September 1982



Message policy is defined to be the description of the disposition of messages of a single type, when received by a group of processes. Group policy applies to all the processes of a group, but for a single message type. It is proposed that group policy be specified in an expression which is separate from the code of the processes of the group, and in a separate notation. As a result, it is possible to write policy expressions which are independent of process state variables, and as well use a simpler control notation based on regular expressions. Input protocol, on the other hand, applies to single processes or a group as a whole for all message types. Encapsulation of processes is presented with an unusual emphasis on the transactions and resources which associate with an encapsulated process rather than the state space of the process environment. This is due to the notion of encapsulation without shared variables, and to the association between group policies, message sequences and transactions.


Author[s]: W.E.L. Grimson

Binocular Shading and Visual Surface Reconstruction

August 1982



Zero-crossing or feature-point based stereo algorithms can, by definition, determine explicit depth information only at particular points on the image. To compute a complete surface description, this sparse depth map must be interpolated. A computational theory of this interpolation or reconstruction process, based on a surface consistency constraint, has previously been proposed. In order to provide stronger boundary conditions for the interpolation process, other visual cues to surface shape are examined in this paper. In particular, it is shown that, in principle, shading information from the two views can be used to determine the orientation of the surface normal along the feature-point contours, as well as the parameters of the reflective properties of the surface material. The numerical stability of the resulting equations is also examined.


Author[s]: Tomas Lozano-Perez

Robot Programming

December 1982



The industrial robot’s principal advantage over traditional automation is programmability. Robots can perform arbitrary sequences of pre-stored motions or of motions computed as functions of sensory input. This paper reviews requirements for and developments in robot programming systems. The key requirements for robot programming systems examined in the paper are in the areas of sensing, world modeling, motion specification, flow of control, and programming support. Existing and proposed robot programming systems fall into three broad categories: guiding systems in which the user leads a robot through the motions to be performed, robot-level programming systems in which the user writes a computer program specifying motion and sensing, and task-level programming systems in which the user specifies operations by their desired effect on objects. A representative sample of systems in each of these categories is surveyed in the paper.


Author[s]: Tomas Lozano-Perez

Robot Programming

December 1982



The industrial robot’s principal advantage over traditional automation is programmability. Robots can perform arbitrary sequences of pre-stored motions or of motions computed as functions of sensory input. This paper reviews requirements for and developments in robot programming systems. The key requirements for robot programming systems examined in the paper are in the areas of sensing, world modeling, motion specification, flow of control, and programming support. Existing and proposed robot programming systems fall into three broad categories: guiding systems in which the user leads a robot through the motions to be performed, robot-level programming systems in which the user writes a computer program specifying motion and sensing, and task-level programming systems in which the user specifies operations by their desired effect on objects. A representative sample of systems in each of these categories is surveyed in the paper.


Author[s]: Ellen C. Hildreth and Shimon Ullman

The Measurement of Visual Motion

December 1982



The analysis of visual motion divides naturally into two stages: the first is the measurement of motion, for example, the assignment of direction and magnitude of velocity to elements in the image, on the basis of the changing intensity pattern; the second is the use of motion measurements, for example, to separate the scene into distinct objects, and infer their three-dimensional structure. In this paper, we present a computational study of the measurement of motion. Similar to other visual processes, the motion of elements is not determined uniquely by information in the changing image; additional constraint is required to compute a unique velocity field. Given this global ambiguity of motion, local measurements from the changing image, such as those provided by directionally- selective simple cells in primate visual cortex, cannot possibly specify a unique local velocity vector, and in fact, specify only one component of velocity. Computation of the full two- dimensional velocity field requires the integration of local motion measurements, either over an area, or along contours in the image. We will examine possible algorithms for computing motion, based on a range of additional constraints. Finally, we will present implications for the biological computation of motion.

horizontal line

MIT logo Computer Science and Artificial Intelligence Laboratory (CSAIL)
The Stata Center, Building 32 - 32 Vassar Street - Cambridge, MA 02139 - USA
tel:+1-617-253-0073 - publications@csail.mit.edu