%A Rodney A. Brooks %A Tomas Lozano-Perez %T A Subdivision Algorithm in Configuration Space for Findpath with Rotation %R AI Memo 684 %I Artificial Intelligence Laboratory, Massachusetts Institute of Technology %K mit aim ail %I Artificial Intelligence Laboratory, Massachusetts Institute of Technology %D December 1982 %P 41 %K mit aim ail %K configuration space, find-path, collision avoidance, robotics %X A hierarchical representation for configuration space is presented, along with an algorithm for searching that space for collision-free paths. The details of the algorithm are presented for polygonal obstacles and a moving object with two translational and one rotational degrees of freedom. %Y cost: $2.75, also available as NTIS report AD-A130565 %A Rodney A. Brooks %T Symbolic Error Analysis and Robot Planning %R AI Memo 685 %I Artificial Intelligence Laboratory, Massachusetts Institute of Technology %K mit aim ail %I Artificial Intelligence Laboratory, Massachusetts Institute of Technology %D September 1982 %P 85 %K mit aim ail %K robotics, error analysis, planning, symbolic algebra %X 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 data base 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 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 or as an aid to a human robot programmer. %Y cost: $3.00, also available as NTIS report AD-A121007 %A John M. Hollerbach %T Computers, Brains, and the Control of Movement %R AI Memo 686 %I Artificial Intelligence Laboratory, Massachusetts Institute of Technology %K mit aim ail %I Artificial Intelligence Laboratory, Massachusetts Institute of Technology %D June 1982 %P 12 %K mit aim ail %K motor control, robotics %X 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 movement, the role of feedback during arm movement, as well as plausible compensatory mechanisms for arm dynamics. %Y cost: $l.50 %A Tomaso Poggio %A B.L. Rosser %T The Computational Problem of Motor Control %R AI Memo 687 %I Artificial Intelligence Laboratory, Massachusetts Institute of Technology %K mit aim ail %I Artificial Intelligence Laboratory, Massachusetts Institute of Technology %D May 1983 %P 11 %K mit aim ail %K motor control, associative learning, look-up table %X 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. %Y cost: $1.50 %A Carl Hewitt %A Peter de\ Jong %T Open Systems %R AI Memo 691 %I Artificial Intelligence Laboratory, Massachusetts Institute of Technology %K mit aim ail %I Artificial Intelligence Laboratory, Massachusetts Institute of Technology %D December 1982 %P 28 %K mit aim ail %K open systems, conceptual modeling, actors, sprites, description, semantics, problem solving %X 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 program to explore issues in the semantics of communication in parallel systems such as negotiation, transaction management, problem solving, change, and self-knowledge. %Y cost: $2.25 %A C.J.Barter %T Policy-Protocol Interaction in Composite Processes %R AI Memo 692 %I Artificial Intelligence Laboratory, Massachusetts Institute of Technology %K mit aim ail %I Artificial Intelligence Laboratory, Massachusetts Institute of Technology %D September 1982 %P 22 %K mit aim ail %X 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 posssible 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. %Y cost: $1.50, also available as NTIS report AD-A135733 %A W.E.L. Grimson %T Binocular Shading And Visual Surface Reconstruction %R AI Memo 697 %I Artificial Intelligence Laboratory, Massachusetts Institute of Technology %K mit aim ail %I Artificial Intelligence Laboratory, Massachusetts Institute of Technology %D August 1982 %P 24 %K mit aim ail %K shading, visual surface reconstruction, reflection properties, photometric stereo %X Zero-crossing or feature-point based stereo algorithms can, by definition, determine explicit depth information only at particular points in 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. %Y cost: $2.25, also available as NTIS report AD-A127058 %A Tomas Lozano-Perez %T Robot Programming %R AI Memo 698 %I Artificial Intelligence Laboratory, Massachusetts Institute of Technology %K mit aim ail %I Artificial Intelligence Laboratory, Massachusetts Institute of Technology %D December 1982 %P 57 %K mit aim ail %K robotics, robot programming %X 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 objects. A representative sample of systems in each of these categories is surveyed in the paper. %Y cost: $2.75, also available as NTIS report AD-A127233 %A Ellen C. Hildreth and Shimon Ullman %T The Measurement of Visual Motion %R AI Memo 699 %I Artificial Intelligence Laboratory, Massachusetts Institute of Technology %K mit aim ail %I Artificial Intelligence Laboratory, Massachusetts Institute of Technology %D December 1982 %P 26 %K mit aim ail %K motion measurement, velocity field, optical flow, zero crossings, motion perception %X 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 possible 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. %Y cost: $2.25, also available as NTIS report AD-A128398 %A John M. Hollerbach %T Dynamic Scaling of Manipulator Trajectories %R AI Memo 700 %I Artificial Intelligence Laboratory, Massachusetts Institute of Technology %K mit aim ail %I Artificial Intelligence Laboratory, Massachusetts Institute of Technology %D January 1983 %P 13 %K mit aim ail %K manipulators, robotics, trajectory planning, manipulator dynamics %X A fundamental time-scaling property of manipulator dynamics has been identified that allows modification of movement speed without complete dynamics recalculation. By exploiting this property, it can be determined whether a planned trajectory is dynamically realizable given actuator torque limits, and if not, how to modify the trajectory to bring it within dynamic and actuating constraints. %Y cost: $1.50, also available as NTIS report AD-A127074 %A John Batali %T Computational Introspection %R AI Memo 701 %I Artificial Intelligence Laboratory, Massachusetts Institute of Technology %K mit aim ail %I Artificial Intelligence Laboratory, Massachusetts Institute of Technology %D February 1983 %P 68 %K mit aim ail %K problem solving, reflection, action, philosophy of mind, introspection, LISP, representation %X Introspection is the process of thinking about one's own thoughts and feelings. In this paper, I discuss recent attempts to make computational systems that exhibit introspective behavior: [Smith, 1982], [Weyhrauch, 1978], and [Doyle, 1980]. Each presents a system capable of manipulating representations of its own program and current context. I argue that introspective ability is crucial for intelligent systems -- without it an agent cannot represent certain problems that it must be able to solve. A theory of intelligent action would describe how and why certain actions intelligently achieve an agent's goals. The agent would both embody and represent this theory: it would be implemented as the program for the agent; and the importance of introspection suggests that the agent represent its theory of action to itself. %Y cost: $3.00, also available as NTIS report AD-A127132 %A Reid G. Simmons %A Randall Davis %T Representations for Reasoning About Change %R AI Memo 702 %I Artificial Intelligence Laboratory, Massachusetts Institute of Technology %K mit aim ail %I Artificial Intelligence Laboratory, Massachusetts Institute of Technology %D April 1983 %P 54 %K mit aim ail %K processes, action, knowledge representation, expert systems, qualitative reasoning %O See SIGART Proceedings, April 1983, Workshop on Motion, Toronto, Canada, %X This paper explores representations used to reason about objects which change over time and the processes which cause changes. Specifically, we are interested in solving a problem known as geologic interpretation. To help solve this problem, we have developed a simulation technique, which we call ``imagining''. Imagining takes a sequence of events and simulates them by drawing diagrams In order to do this imagining, we have developed two representations of objects, one involving ``histories'' and the other involving ``diagrams'' and two corresponding representations of physical processes, each suited to reasoning about one of the object representations. These representations facilitate both spatial and temporal reasoning. %Y cost: $2.75, also available as NTIS report AD-A131649 %A Peter C. Gaston %A Tomas Lozano-Perez %T Tactile Recognition and Localization Using Object Models: The Case of Po lyhedra on a Plane %R AI Memo 705 %I Artificial Intelligence Laboratory, Massachusetts Institute of Technology %K mit aim ail %I Artificial Intelligence Laboratory, Massachusetts Institute of Technology %D March 1983 %P 22 %K mit aim ail %K tactile sensing, robotics %X This paper discusses how data from multiple tactile sensors may be used to identify and locate one object, from among a set of known objects. We use only local information from sensors:(1)the position of contact points, and (2)ranges of surface normals at the contact points. The recognition and localization process is structured as the development and pruning of a tree of consistent hypotheses about pairings between contact points and object surfaces. In this paper, we deal with polyhedral objects constrained to lie on a known plane, i.e., having three degrees of positioning freedom relative to the sensors. %Y cost: $2.25, also available as NTIS report AD-A127228 %A Shimon Ullman %T Computational Studies in the Interpretation of Structure and Motion: Summary and Extension %R AI Memo 706 %I Artificial Intelligence Laboratory, Massachusetts Institute of Technology %K mit aim ail %I Artificial Intelligence Laboratory, Massachusetts Institute of Technology %D March 1983 %P 26 %K mit aim ail %K motion perception, visual motion, optical flow, structure from motion %X Computational studies of the interpretation of structure from motion examine the conditions under which three-dimensional structure can be recovered from motion in the image. The first part of this paper summarizes the main results obtained to date in these studies. The second part examines two issues: the robustness of the 3-D interpretation of perspective velocity fields, and the 3-D information contained in orthographic velocity fields. The two are related because, under local analysis, limitations on the interpretation of orthographic velocity fields also apply to perspective projection. The following results are established: (1) When the interpretation is applied locally, the 3-D interpretation of the perspective velocity field is unstable. (2) The orthographic velocity field determines the structure of the inducing object exactly up to a depth-scaling. (3) For planar objects, the orthographic velocity field always admits two distinct solutions up to depth-scaling. (4) The 3-D Structure is determined uniquely by a "view and a half" of the orthographic velocity field. %Y cost: $2.25, also available as NTIS report AD-A131598 %A David McAllester %T Solving Uninterpreted Equations with Context Free Expression Grammars %R AI Memo 708 %I Artificial Intelligence Laboratory, Massachusetts Institute of Technology %K mit aim ail %I Artificial Intelligence Laboratory, Massachusetts Institute of Technology %D May 1983 %P 31 %K mit aim ail %K theorem proving, congruence closure, simplification, automated deduction, context free grammar %X It is shown here that the equivalence class of an expression under the congruence closure of any finite set of equations between ground terms is a context free expression language. An expression is either a symbol or an n-tuple of expressions; the difference between expressions and strings is that expressions have inherent phrase structure. The Downey, Sethi, and Tarjan algorithm for computing congruence closures can be used to convert a finite set of equations $sigma$ to a context free expression grammar $G$ such that for any expression $u$ the equivalence class of $u$ under $sigma$ is precisely the language generated by an expression form $gamma(u)$ under the grammar $G$. The fact that context free ``expression'' languages are closed under intersection is used to derive an algorithm for computing a grammar for the equivalence class of a given expression under any finite disjunction of finite sets of equations between ground expressions. This algorithm can also be used to derive a grammar representing the equivalence class of conditional expressions of the form ``if P then $u$ else $v$''. The description of an equivalence class by a context free expression grammar can also be used to simplify expressions under "well behaved" simplicity orders. Specifically if $G$ is a context free expression grammar which generates an equivalence class of expressions then for any well behaved simplicity order there is a subset $G'$ of the productions of $G$ such that the expressions generated by $G$ are exactly those expressions of the equivalence class which are simplicity bounds and whose subterms are also simplicity bounds. Furthermore $G'$ can be computed from $G$ in order $n.log(n)$ comparisons between expressions where $n$ is the size of $G$. %Y cost: $2.25, also available as NTIS report AD-A133613 %A David Allen McAllester %T Symmetric Set Theory: A General Theory of Isomorphism, Abstraction, and Representation %R AI Memo 710 %I Artificial Intelligence Laboratory, Massachusetts Institute of Technology %K mit aim ail %I Artificial Intelligence Laboratory, Massachusetts Institute of Technology %D August 1983 %P 30 %K mit aim ail %X It is possible to represent a finite set of points (atoms) by a finite sequence of points. However a finite set of points has no distinguished member and therefore it is impossible to define a function which takes a finite set of points and returns a "first" point in that set. Thus it is impossible to represent a finite sequence of points by a finite set of points. The theory of symmetric sets provides a framework in which this observation about sets and sequences can be proven. The theory of symmetric sets is similar to classical (Zermello-Fraenkel) set theory with the exception that the universe of symmetric sets includes points (ur-elements). Points provide a basis for general notions of isomorphism and symmetry. The general notions of isomorphism and symmetry in turn provide a basis for natural, simple, and universal definitions of abstractness, essential properties and functions, canonicality, and representations. It is expected that these notions will play an important role in the theory of data structures and in the construction of general techniques for reasoning about data structures. %Y cost: $2.25, also available as NTIS report AD-A133630 %A Michael Brady and Alan Yuille %T An Extremum Principle for Shape from Contour %R AI Memo 711 %I Artificial Intelligence Laboratory, Massachusetts Institute of Technology %K mit aim ail %I Artificial Intelligence Laboratory, Massachusetts Institute of Technology %D June 1983 %P 35 %K mit aim ail %K shape from contour, image understanding, 3-D vision %X An extremum principle is developed that determines three-dimensional surface orientation from a two-dimensional contour. The principle maximizes the ratio of the area to the square of the perimeter, a measure of the compactness or symmetry of the three-dimensional surface. The principle interprets regular figures correctly and it interprets skew symmetries as oriented real symmetries. The maximum likelihood method approximates the principle on irregular figures, but we show that it consistently overestimates the slant of an ellipse. %Y cost: $2.25, also available as NTIS report AD-A131321 %A C. Koch and T. Poggio %T Information Processing in Dendritic Spines %R AI Memo 712 %I Artificial Intelligence Laboratory, Massachusetts Institute of Technology %K mit aim ail %I Artificial Intelligence Laboratory, Massachusetts Institute of Technology %D March 1983 %P 11 %K mit aim ail %K spines, memory, connectivity, neural hardware %X Dendritic spines are small twigs on the dendrites of very large class of neurons in the central nervous system. There are between 10/3 and 10/5 spines per neuron, each one including at least one synapse, i.e a connection with other neurons. Thus, spines are usually associated with an important feature of neurons - their high degree of connectivity - one of the most obvious differences between present computers and brains. We have analysed the electrical properties of a cortical (spiny) pyramidal cell on the basis of passive cable theory, from measurements made on histological material, using the solution of the cable equation for an arbitrary branched dendritic tree. As postulated by Rall, we found that the somatic potential induced by a firing synapse on a spine is a very sensitive function of the dimension of the spine. This observation leads to several hypotheses concerning the electrical functions of spines, especially with respect to their role in memory. %Y cost: $1.50 %A C. Koch and T. Poggio %T A Theoretical Analysis of Electrical Properties of Spines %R AI Memo 713 %I Artificial Intelligence Laboratory, Massachusetts Institute of Technology %K mit aim ail %I Artificial Intelligence Laboratory, Massachusetts Institute of Technology %D April 1983 %P 27 %K mit aim ail %K dendritic spines, nerve cells, information processing, memory %X The electrical properties of a cortical (spiny) pyramidal cell were analyzed on the basis of passive cable theory from measurements made on histological material (Koch, Poggio and Torre 1982). The basis of this analysis is the solution of the cable equation for an arbitrary branched dendritic tree. We determined the potential at the soma as a function of the spine neck dimensions. From our investigation four major points emerge: 1. Spines may effectively compress the effect of each single excitatory synapse on the soma, mapping a wide range of inputs onto a limited range of outputs (nonlinear saturation). This is also true for very fast transient inputs, in sharp contrast with the case of a synapse on a dendrite. 2. The somatic depolarization due to an excitatory synapse on a spine is a very sensitive function of the spine neck length and diameter. Thus the spine can effectively control the attenuation of its input via the dimensions of the neck, thereby setting the shape of the resulting saturation curve. This might be the basic mechanism underlying ultra-short memory, long-term potentiation in the hippocampus or learning in the cerebellum. 3. Spines with shunting inhibitory synapses on them are ineffective in reducing the somatic depolarization due to excitatory inputs on the dendritic shaft or on other spines. Thus isolated inhibitory synapses on a spine are not expected to occur. 4. The conjunction of an excitatory synapse with a shunting inhibitory synapse on the same spine may result in a time-discrimination circuit with a temporal resolution of around 100. %Y cost: $2.25 %A Katsushi Ikeuchi %T Determining Attitude of Object From Needle Map Using Extended Gaussian Image %R AI Memo 714 %I Artificial Intelligence Laboratory, Massachusetts Institute of Technology %K mit aim ail %I Artificial Intelligence Laboratory, Massachusetts Institute of Technology %D April 1983 %P 26 %K mit aim ail %K computer vision, object attitude, bin picking, Gauss map, least inertia axis, tessellated dome, look-up table %X An extended Gaussian image (EGI) is constructed by mapping the surface normals of an object onto the Gaussian sphere. The attitude of an object is greatly constrained by the global distribution of EGI mass over the visible Gaussian hemisphere. Constraints on viewer direction are derived from the position of the EGI mass center, and from the direction of the EGI inertia axis. The algorithm embodying these constraints and the EGI mass distribution are implemented using a lookup table. A function for matching an observed EGI with the prototypical EGIS is also proposed. The algorithm determines the attitude of an object successfully both from a synthesized needle map and a real needle map. %Y cost: $2.25, also available as NTIS report AD-A131617 %A Graziella Tonfoni %A Richard J. Doyle %T Understanding Text through Summarization and Analogy %R AI Memo 716 %I Artificial Intelligence Laboratory, Massachusetts Institute of Technology %K mit aim ail %I Artificial Intelligence Laboratory, Massachusetts Institute of Technology %D April 1983 %P 37 %K mit aim ail %K plot units, analogy, summary, text-production %X Understanding a text exactly in the way that the Text Producer meant the text to be understood is highly unlikely unless the text interpretation process is constrained. Specific understanding-directing criteria are given in the form of a Premise which is a configuration of plot-units. After performing a Premise-directed text summarization, the Text Receiver will have understood the text as the Text Producer intended and will then be able to replace missing relations within the exercises and produce new texts by applying analogy. %Y cost: $2.25 %A John M. Hollerbach %A Gideon Sahar %T Wrist-Partitioned Inverse Kinematic Acceleration and Manipulator Dynamics %R AI Memo 717 %I Artificial Intelligence Laboratory, Massachusetts Institute of Technology %K mit aim ail %I Artificial Intelligence Laboratory, Massachusetts Institute of Technology %D April 1983 %P 25 %K mit aim ail %K robotics, kinematics, dynamics, control %X An efficient algorithm is presented for the calculation of the inverse kinematic accelerations for a 6 degree-of-freedom manipulator with a spherical wrist. The inverse kinematic calculation is shown to work synergistically with the inverse dynamic calculation, producing kinematic parameters needed in the recursive Newton-Euler dynamics formulation. Additional savings in the dynamics computation are noted for a class of kinematically well-structured manipulators such as spherical-wrist arms and for manipulators with simply-structured inertial parameters. %Y cost: $2.25 %A A. Yuille %T Zero-Crossings on Lines of Curvature %R AI Memo 718 %I Artificial Intelligence Laboratory, Massachusetts Institute of Technology %K mit aim ail %I Artificial Intelligence Laboratory, Massachusetts Institute of Technology %D December 1984 %P 23 %K mit aim ail %K photometric invariants, zero crossings, lines of curvature, parabolic lines %X We investigate the relations between the structure of the image and events in the geometry of the underlying surface. We introduce some elementary differential geometry and use it to define a coordinate system on the object based on the lines of curvature. Using this coordinate system we can prove results connecting the extrema, ridges and zero-crossings in the image to geometrical features of the object. We show that extrema of the image typically correspond to points on the surface with zero Gaussian curvature and that parabolic lines often give rise to ridges, or valleys, in the image intensity. We show that directional zero-crossings of the image along the lines of curvature generally correspond to extrema of curvature along such lines. %Y cost: $2.25, also available as NTIS report AD-A150171 %A Gerald Barber %A Peter de Jong %A Carl Hewitt %T Semantic Support for Work in Organizations %R AI Memo 719 %I Artificial Intelligence Laboratory, Massachusetts Institute of Technology %K mit aim ail %I Artificial Intelligence Laboratory, Massachusetts Institute of Technology %D April 1983 %P 14 %K mit aim ail %K problem solving, office systems, open systems, actors, application systems, message passing semantics, OMEGA, sprites %X Present day computer systems cannot implement much of the work carried out in organizations such as: planning, decision making, analysis, and dealing with unanticipated situations. Such organizational activities have traditionally been considered too unstructured to be suitable for automation by computer. We are working on the development of a computer system which is capable of the following: describing the semantics of applications as well as the structure of the organization carrying out the work, aiding workers in carrying out the applications using these descriptions, and acquiring these capabilities in the course of the daily work through a process which is analogous to apprenticeship. %Y cost: $1.50, also available as NTIS report AD-A130457 %A Shimon Ullman %T Maximizing Rigidity: The Incremental Recovery of 3-D Structure From Rigid and Rubbery Motion %R AI Memo 721 %I Artificial Intelligence Laboratory, Massachusetts Institute of Technology %K mit aim ail %I Artificial Intelligence Laboratory, Massachusetts Institute of Technology %D June 1983 %P 30 %K mit aim ail %K motion perception, structure from motion, rigidity, rubbery motion, kinetic depth effect %X The human visual system can extract 3-D shape information of unfamiliar moving objects from their projected transformations. Computational studies of this capacity have established that 3-D shape can be extracted correctly from a brief presentation, provided that the moving objects are rigid. The human visual system requires a longer temporal extension, but it can cope, however, with considerable deviations from rigidity. It is shown how the 3-D structure of rigid and non-rigid objects can be recovered by maintaining an internal model of the viewed object and modifying it at each instant by the minimal non-rigid change that is sufficient to account for the observed transformation. The results of applying this incremental rigidity scheme to rigid and non-rigid objects in motion are described and compared with human perceptions. %Y cost: $2.25 %A A.L. Yuille %A T. Poggio %T Scaling Theorems for Zero-Crossings %R AI Memo 722 %I Artificial Intelligence Laboratory, Massachusetts Institute of Technology %K mit aim ail %I Artificial Intelligence Laboratory, Massachusetts Institute of Technology %D June 1983 %P 25 %K mit aim ail %X We characterize some properties of the zero-crossings of the laplacian of signals - in particular images - filtered with linear filters, as a function of the scale of the filter (following recent work by A. Witkin, 1983). We prove that in any dimension the only filter that does not create zero-crossings as the scale increases is the gaussian. This result can be generalized to apply to level-crossings of any linear differential operator: it applies in particular to ridges and ravines in the image intensity. In the case of the second derivative along the gradient we prove that there is no filter that avoids creation of zero-crossings. %Y cost: $2.25, also available as NTIS report AD-A131599 %A Shimon Ullman %T Visual Routines %R AI Memo 723 %I Artificial Intelligence Laboratory, Massachusetts Institute of Technology %K mit aim ail %I Artificial Intelligence Laboratory, Massachusetts Institute of Technology %D June 1983 %P 66 %K mit aim ail %K vision, visual routines, pattern recognition, space perception, spatial information processing %X This paper examines the processing of visual information beyond the creation of the early representations. A fundamental requirement at this level is the capacity to establish visually abstract shape properties and spatial relations. This capacity plays a major role in object recognition, visually guided manipulation, and more abstract visual thinking. For the human visual system, the perception of spatial properties and relations that are complex from a computational standpoint, nevertheless often appears immediate and effortless. This apparent immediateness and ease of perceiving spatial relations is, however deceiving. It conceals in fact a complex array of processes highly specialized for the task. The proficiency of the human system in analyzing spatial information far surpasses the capacities of current artificial systems. The study of the computations that underlie this competence may therefore lead to the development of new more efficient processors for the spatial analysis of visual information. It is suggested that the perception of spatial relations is achieved by the application to the base representations of visual routines that are composed of sequences of elemental operations. Routines for different properties and relations share elemental operations. Using a fixed set of basic operations, the visual system can assemble different routines to extract an unbounded variety of shape properties and spatial relations. At a more detailed level, a number of pausible basic operations are suggested, based primarily on their potential usefulness, and supported in part by empirical evidence. The operations discussed include shifting of the processing focus, indexing to an odd-man-out location, bounded activation, boundary tracing, and marking. The problem of assembling such elemental operations into meaningful visual routines is discussed briefly. %Y cost: $2.75, also available as NTIS report AD-A133634 %A A.L. Yuille %T The Smoothest Velocity Field and Token Matching %R AI Memo 724 %I Artificial Intelligence Laboratory, Massachusetts Institute of Technology %K mit aim ail %I Artificial Intelligence Laboratory, Massachusetts Institute of Technology %D August 1983 %P 10 %K mit aim ail %K motion measurement, velocity field, optical flow, zero crossings, motion perception %X This paper presents some mathematical results concerning the measurement of motion of contours. A fundamental problem of motion measurement in general is that the velocity field is not determined uniquely from the changing intensity patterns. Recently Hildreth \& Ullman have studied a solution to this problem based on an Extremum Principle [Hildreth (1983), Ullman & Hildreth (1983)]. That is, they formulate the measurement of motion as the computation of the smoothest velocity field consistent with the changing contour. We analyze this Extremum Principle and prove that it is closely related to a matching scheme for motion measurement which matches points on the moving contour that have similar tangent vectors. We then derive necessary and sufficient conditions for the principle to yield the correct velocity field. These results have possible implications for the design of computer vision systems, and for the study of human vision. %Y cost: $1.50, also available as NTIS report AD-A133633 %A Rodney A. Brooks %T Planning Collision Free Motions for Pick and Place Operations %R AI Memo 725 %I Artificial Intelligence Laboratory, Massachusetts Institute of Technology %K mit aim ail %I Artificial Intelligence Laboratory, Massachusetts Institute of Technology %D May 1983 %P 49 %K mit aim ail %K find-path, collision free paths, pick and place, collision avoidance %X An efficient algorithm which finds collision free paths for a manipulator with 5 or 6 revolute joints is described. It solves the problem for four degree of freedom pick and place operations Examples are given of paths found by the algorithm in tightly cluttered workspaces. The algorithm first describes free space in two ways: as freeways for the hand and payload ensemble and as freeways for the upperarm. Freeways match volumes swept out by manipulator motions and can be "inverted" to find a class of topologically equivalent path segments. The two freeway spaces are searched concurrently under vprojection of constraints determined by motion of the forearm. %Y cost: $2.75, also available as NTIS report AD-A130448 %A Katsushi Ikeuchi %A Berthold K.P. Horn %A Shigemi Nagata %A Tom Callahan, and Oded Feingold %T Picking up an Object from a Pile of Objects %R AI Memo 726 %I Artificial Intelligence Laboratory, Massachusetts Institute of Technology %K mit aim ail %I Artificial Intelligence Laboratory, Massachusetts Institute of Technology %D May 1983 %P 27 %K mit aim ail %K photometric stereo, Puma arm, hand-eye system, extended Gaussian image, bin picking, visual guidance %X This paper describes a hand-eye system we developed to perform the bin-picking task. Two basic tools are employed: the photometric stereo method and the extended Gaussian image. The photometric stereo method generates the surface normal distribution of a scene. The extended Gaussian image allows us to determine the attitude of the object based on the normal distribution. Visual analysis of an image consists of two stages. The first stage segments the image into regions and determines the target region. The photometric stereo system provides the surface normal distribution of the scene. The system segments the scene into isolated regions using the surface normal distribution rather than the brightness distribution. The second stage determines the object attitude and position by comparing the surface normal distribution with the extended Gaussian image. Fingers, with LED sensor, mounted on the Puma arm can successfully pick an object from a pile based on the information from the vision part. %Y cost: $2.25, also available as NTIS report AD-A133631 %A Carl Hewitt %A Peter de\ Jong %T Analyzing the Roles of Descriptions and Actions in Open Systems %R AI Memo 727 %I Artificial Intelligence Laboratory, Massachusetts Institute of Technology %K mit aim ail %I Artificial Intelligence Laboratory, Massachusetts Institute of Technology %D April 1983 %P 15 %K mit aim ail %K open systems, concurrent system, message passing semantics, distributed systems, lambda calculus, first order logic, actor theory, description and action %X This paper analyzes relationships between the roles of descriptions and actions in large scale, open ended, geographically distributed, concurrent systems. Rather than attempt to deal with the complexities and ambiguities of currently implemented descriptive languages, we concentrate our analysis on what can be expressed in the underlying frameworks such as the lambda calculus and first order logic. By this means we conclude that descriptions and actions complement one another; neither being sufficient unto itself. This paper provides a basis to begin the analysis of the very subtle relationships that hold between descriptions and actions in Open Systems. %Y cost: $1.50, also available as NTIS report AD-A133614 %A A.L. Yuille %A T. Poggio %T Fingerprints Theorems for Zero-Crossings %R AI Memo 730 %I Artificial Intelligence Laboratory, Massachusetts Institute of Technology %K mit aim ail %I Artificial Intelligence Laboratory, Massachusetts Institute of Technology %D October 1983 %P 28 %K mit aim ail %K zero crossings, scales, signal reconstruction %X We prove that the scale map of the zero-crossings of almost all signals filtered by the second derivative of a gaussian of variable size determines the signal uniquely, up to a constant scaling and a harmonic function. Our proof provides a method for reconstructing almost all signals from knowledge of how the zero-crossing contours of the signal, filtered by a gaussian filter, change with the size of the filter. The proof assumes that the filtered signal can be represented as a polynomial of finite, albeit possibly very high, order. An argument suggests that this restriction is not essential. Stability of the reconstruction scheme is briefly discussed. The result applies to zero- and level-crossings of linear differential operators of gaussian filters. The theorem is extended to two dimensions, that is to images. These results are reminiscent of Logan's theorem. They imply that extrema of derivatives at different scales are a complete representation of a signal. %Y cost: $2.25, also available as NTIS report AD-A139181 %A Whitman Richards %T Structure From Stereo and Motion %R AI Memo 731 %I Artificial Intelligence Laboratory, Massachusetts Institute of Technology %K mit aim ail %I Artificial Intelligence Laboratory, Massachusetts Institute of Technology %D September 1983 %P 19 %K mit aim ail %X Stereopsis and motion parallax are two methods for recovering three dimensional shape. Theoretical analyses of each method show that neither alone can recover rigid 3D shapes correctly unless other information, such as perspective, is included. The solutions for recovering rigid structure from motion have a reflection ambiguity; the depth scale of the stereoscopic solution will not be known unless the fixation distance is specified in units of interpupil separation. (Hence the configuation will appear distorted.) However, the correct configuration and disposition of a rigid 3D shape can be recovered if stereopsis and motion are integrated, for then a unique solution follows from a set of linear equations. The correct interpretation requires only three points and two stereo views. %Y cost: $1.50 %A D.D. Hoffman %A Whitman Richards %T Parts of Recognition %R AI Memo 732 %I Artificial Intelligence Laboratory, Massachusetts Institute of Technology %K mit aim ail %I Artificial Intelligence Laboratory, Massachusetts Institute of Technology %D December 1983 %P 35 %K mit aim ail %X A complete theory of object recognition is an impossibility -- not simply because of the multiplicity of visual cues we exploit in elegant coordination to identify an object, but primarily because recognition involves fixation of belief, and anything one knows may be relevant. We finesse this obstacle with two moves. The first restricts attention to one visual cue, the shapes of objects; the second restricts attention to one problem, the initial guess at the identity of an object. We propose that the visual system decomposes a shape into parts, that it does so using a rule defining part boundaries rather than part shapes, that the rule exploits a uniformity of nature -- transversality, and that parts with their descriptions and spatial relations provide a first index into a memory of shapes. These rules lead to a more comprehensive explanation of several visual illusions. The role of inductive inference is stressed in our theory. We conclude with a precis of unsolved problems. %Y cost: $2.25 %A Ellen C. Hildreth %T The Computation of the Velocity Field %R AI Memo 734 %I Artificial Intelligence Laboratory, Massachusetts Institute of Technology %K mit aim ail %I Artificial Intelligence Laboratory, Massachusetts Institute of Technology %D September 1983 %P 40 %K mit aim ail %K motion analysis, motion perception, computer vision, image processing, velocity field %X The organization of movement in the changing retinal image provides a valuable source of information for analyzing the environment in terms of objects, their motion in space, and their three-dimensional structure. A description of this movement is not provided to our visual system directly, however; it must be inferred from the pattern of changing intensity that reaches the eye. This paper examines the problem of motion measurement, which we formulate as the computation of an instantaneous two-dimensional velocity field from the changing image. Initial measurements of motion take place at the location of significant intensity changes as suggested by Marr and Ullman (1981). These measurements provide only one component of local velocity, and must be integrated to compute the two-dimensional velocity field. A fundamental problem for this integration stage is that the velocity field is not determined uniquely from information available in the changing image. We formulate an additional constraint of smoothness of the velocity field, based on the physical assumption that surfaces are generally smooth, which allows the computation of a unique velocity field. A theoretical analysis of the conditions under which this computation yields the correct velocity field suggests that the solution is physically plausible. Empirical studies show the predictions of this computation to be consistent with human motion perception. %Y cost: $2.25 %A Bruce R. Donald %T Hypothesizing Channels Through Free-Space In Solving the Findpath Problem %R AI Memo 736 %I Artificial Intelligence Laboratory, Massachusetts Institute of Technology %K mit aim ail %I Artificial Intelligence Laboratory, Massachusetts Institute of Technology %D June 1983 %P 58 %K mit aim ail %K geometric modelling, robotics, obstacle avoidance, spatial reasoning, computational geometry %X Given a polyhedral environment, a technique is presented for hypothesizing a channel volume through the free space containing a class of successful collision-free paths. A set of geometric constructions between obstacle faces is proposed, and we define a mapping from a field of view analysis to a direct local construction of free space. The algorithm has the control structure of a search which propagates construction of a connected channel towards a goal along a frontier of exterior free faces. Thus a channel volume starts out by surrounding the moving object in the initial configuration and "grows" towards the goal. Finally, we show techniques for analyzing the channel decomposition of free space and suggesting a path. %Y cost: $2.75, also available as NTIS report AD-A133632 %A H.K. Nishihara and T. Poggio %T Hidden Clues in Random Line Stereograms %R AI Memo 737 %I Artificial Intelligence Laboratory, Massachusetts Institute of Technology %K mit aim ail %I Artificial Intelligence Laboratory, Massachusetts Institute of Technology %D August 1983 %P 9 %K mit aim ail %K random line stereograms, stereo matching, vision, vernier acuity, frequency tuned channels, parallel processing, computer vision, psychophysics %X Successful fusion of random-line stereograms with breaks in the vernier acuity range has been previously interpreted to suggest that the interpolation process underlying hyperacuity is parallel and preliminary to stereomatching. In this paper (a) we demonstrate with computer experiments that vernier cues are not needed to solve the stereomatching problem posed by these stereograms and (b) we provide psychophysical evidence that human stereopsis probably does not use vernier cues alone to achieve fusion of these random-line stereograms. %Y cost: $1.50 %A W. Eric Grimson and Tomas Lozano-Perez %T Model-Based Recognition and Localization From Sparse Range or Tactile Data %R AI Memo 738 %I Artificial Intelligence Laboratory, Massachusetts Institute of Technology %K mit aim ail %I Artificial Intelligence Laboratory, Massachusetts Institute of Technology %D August 1983 %P 54 %K mit aim ail %K tactile recognition, robotics, range data %X This paper discusses how local measurements of three-dimensional positions and surface normals (recorded by a set of tactile sensors, or by three-dimensional range sensors), may be used to identify and locate objects, from among a set of known objects. The objects are modeled as polyhedra having up to six degrees of freedom relative to the sensors. We show that inconsistent hypotheses about pairings between sensed points and object surfaces can be discarded efficiently by using local constraints on: distances between faces, angles between face normals, and angles (relative to the surface normals) of vectors between sensed points. We show by simulation and by mathematical bounds that the number of hypotheses consistent with these constraints is small. We also show how to recover the position and orientation of the object from the sense data. The algorithm's performance on data obtained from a triangulation range sensor is illustrated. %Y cost: $2.75, also available as NTIS report AD-A135791 %A Randall Davis %T Diagnostic Reasoning Based On Structure and Behavior %R AI Memo 739 %I Artificial Intelligence Laboratory, Massachusetts Institute of Technology %K mit aim ail %I Artificial Intelligence Laboratory, Massachusetts Institute of Technology %D June 1984 %P 54 %K mit aim ail %X We describe a system that reasons from first principles, i.e., using knowledge of structure and behavior. The system has been implemented and tested on several examples in the domain of troubleshooting digital electronic circuits. We give an example of the system in operation, illustrating that this approach provides several advantages, including a significant degree of device independence, the ability to constrain the hypotheses it considers at the outset, yet deal with a progressively wider range of problems, and the ability to deal with situations that are novel in the sense that their outward manifestations may not have been encountered previously. As background we review our basic approach to describing structure and behavior, then explore some of the technologies used previously in troubleshooting. Difficulties encountered there lead us to a number of new contributions, four of which make up the central focus of this paper. We describe a technique we call ``constraint suspension'' that provides a powerful tool for troubleshooting. We point out the importance of making explicit the assumptions underlying reasoning and describe a technique that helps enumerate assumptions methodically. The result is an overall strategy for troubleshooting based on the progressive relaxation of underlying assumptions. The system can focus its efforts initially, yet will methodically expand its focus to include a broad range of faults. Finally, abstracting from our examples, we find the concept of ``adjacency'' proves to be useful in understanding why some faults are especially difficult and why multiple different representations are useful. %Y cost: $2.75 %A Berthold K.P. Horn %T Extended Gaussian Images %R AI Memo 740 %I Artificial Intelligence Laboratory, Massachusetts Institute of Technology %K mit aim ail %I Artificial Intelligence Laboratory, Massachusetts Institute of Technology %D July 1983 %K mit aim ail %K machine vision, attitude in space, shape representation, object recognition, Gaussian image %X This is a primer on extended gaussian images. Extended gaussian images are useful for representing the shapes of surfaces. They can be computed easily from: (1) needle maps obtained using photometric stereo, or (2) depth maps generated by ranging devices or stereo. importantly, they can also be determined from geometric models of the objects. Extended gaussian images can be of use in at least two of the tasks facing a machine vision system: (1) recognition, and (2) determining the attitude in space of an object. Here, the extended gaussian image is defined and some of its properties discussed. An elaboration for non-convex objects is presented and several examples are shown. %Y cost: $2.75, also available as NTIS report AD-A135747 %A K.R.K. Nielsen %A T. Poggio %T Vertical Image Registration in Stereopsis %R AI Memo 743 %I Artificial Intelligence Laboratory, Massachusetts Institute of Technology %K mit aim ail %I Artificial Intelligence Laboratory, Massachusetts Institute of Technology %D October 1983 %P 13 %K mit aim ail %K stereopsis, image registration, vertical disparity %X Most computational theories of stereopsis require a registration stage prior to matching to reduce the matching to a one-dimensional search. Even after registration, it is critical that the stereo matching process tolerate some degree of residual misalignment. In this paper, we study with psychophysical techniques the tolerance to vertical disparity in situations in which false targets abound - as in random dot stereograms - and eye movements are eliminated. Our results show that small amounts of vertical disparity significantly impair depth discrimination in a forced-choice task. %Y cost: $1.50 %A Katsushi Ikeuchi %T Reconstructing a Depth Map from Intensity Maps %R AI Memo 744 %I Artificial Intelligence Laboratory, Massachusetts Institute of Technology %K mit aim ail %I Artificial Intelligence Laboratory, Massachusetts Institute of Technology %D August 1983 %P 19 %K mit aim ail %K shape from shading, Marr-Poggio-Grimson stereo, needle map, photometric stereo, depth map, intensity map %X This paper describes two methods for constructing a depth map from images. Each method has two stages. First, one or more needle maps are determined using a pair images. This process employs either the Marr-Poggio-Grimson stereo and shape-from-shading, or, instead, photometric stereo. Secondly, a depth map is constructed from the needle map or needle maps computed by the first stage. Both methods make use of an iterative relaxation method to obtain the final depth map. %Y cost: $1.50, also available as NTIS report AD-A135679 %A Berthold K.P. Horn and Katsushi Ikeuchi %T Picking Parts out of a Bin %R AI Memo 746 %I Artificial Intelligence Laboratory, Massachusetts Institute of Technology %K mit aim ail %I Artificial Intelligence Laboratory, Massachusetts Institute of Technology %D October 1983 %P 48 %K mit aim ail %K machine vision, bin picking, shape representation, object recognition, hand-eye system, attitude in space, extended Gaussian image %X One of the remaining obstacles to the widespread application of industrial robots is their inability to deal with parts that are not precisely positioned. In the case of manual assembly, components are often presented in bins. Current automated systems, on the other hand, require separate feeders which present the parts with carefully controlled position and attitude. Here we show how results in machine vision provide techniques for automatically directing a mechanical manipulator to pick one object at a time out of a pile. The attitude of the object to be picked up is determined using a histogram of the orientations of visible surface patches. Surface orientation, in turn, is determined using photometric stereo applied to multiple images. These images are taken with the same camera but differing lighting. The resulting needle map, giving the orientations of surface patches, is used to create an orientation histogram which is a discrete approximation to the extended Gaussian image. This can be matched against a synthetic orientation histogram obtained from prototypical models of the objects to be manipulated. Such models may be obtained from computer aided design (CAD) databases. The method thus requires that the shape of the objects be described, but it is not restricted to particular types of objects. %Y cost: $2.75, also available as NTIS report AD-A139257 %A Hormoz Mansour %T A Structural Approach to Analogy %R AI Memo 747 %I Artificial Intelligence Laboratory, Massachusetts Institute of Technology %K mit aim ail %I Artificial Intelligence Laboratory, Massachusetts Institute of Technology %D November 1983 %P 28 %K mit aim ail %K structural analogy, contextual analogy, knowledge acquisition, nested frames, automatic acquisition %Y unavailable %A Carl Hewitt %A Henry Lieberman %T Design Issues in Parallel Architecture for Artificial Intelligence %R AI Memo 750 %I Artificial Intelligence Laboratory, Massachusetts Institute of Technology %K mit aim ail %I Artificial Intelligence Laboratory, Massachusetts Institute of Technology %D November 1983 %P 15 %K mit aim ail %K architecture, parallelism, actors, Act2, artificial intelligence, Apiary, message passing, reasoning %X Development of highly intelligent computers requires a conceptual foundation that will overcome the limitations of the von Neumann architecture. Architectures for such a foundation should meet the following design goals: *) Address the fundamental organizational issues of large-scale parallelism and sharing in a fully integrated way. This means attention to organizational principles, as well as hardware and software. *) Serve as an experimental apparatus for testing large-scale artificial intelligence systems. *) Explore the feasibility of an architecture based on abstractions, which serve as natural computational primitives for parallel processing. Such abstractions should be logically independent of their software and hardware host implementations. In this paper we lay out some of the fundamental design issues in parallel architectures for Artificial Intelligence, delineate limitations of previous parallel architectures, and outline a new approach that we are pursuing. %Y cost: $1.50, also available as NTIS report AD-A142482 %A Christof Koch %A Jose Marroquin %A Alan Yuille %T Analog "Neuronal" Networks in Early Vision %R AI Memo 751 %I Artificial Intelligence Laboratory, Massachusetts Institute of Technology %K mit aim ail %I Artificial Intelligence Laboratory, Massachusetts Institute of Technology %D June 1985 %P 17 %K mit aim ail %K analogy networks, analog-digital hardware, parallel computers, surface interpolation, surface reconstruction, optimization problem, regularization theory, early vision %X Many problems in early vision can be formulated in terms of minimizing an energy or cost function. Examples are shape-from-shading, edge detection, motion analysis, structure from motion and surface inter- polation (Poggio, Torre and Koch, 1985). It has been shown that all quadratic variational problems, an important subset of early vision tasks, can be "solved" by linear, analog electrical or chemical networks (Poggio and Koch, 1985). In a variety of situations the cost function is non-quadratic, however, for instance in the presence of discontinuities. The use of non- quadratic cost functions raises the question of designing efficient algorithms for computing the optimal solution. Recently, Hopfield and Tank (1985) have shown that networks of nonlinear analog "neurons" can be effective in computing the solution of optimization problems. In this paper, we show how these networks can be generalized to solve the non-convex energy functionals of early vision. We illustrate this approach by implementing a specific network solving the problem of reconstructing a smooth surface while preserving its discontinuities from sparsely sampled data (Geman and Geman, 1984; Terzopoulos, 1984). These results suggest a novel computational strategy for solving such problems for both biological and artificial vision systems. %Y cost: $1.50 %A A. Yuille %T A Method for Computing Spectral Reflectance %R AI Memo 752 %I Artificial Intelligence Laboratory, Massachusetts Institute of Technology %K mit aim ail %I Artificial Intelligence Laboratory, Massachusetts Institute of Technology %D December 1984 %P 12 %K mit aim ail %K color, material edges, basis functions, mondrians %X Psychophysical experiments show that the perceived color of an object is relatively independent of the spectrum of the incident illumination and depends only on the surface reflectance. We demonstrate a possible solution to this underdetermined problem by expanding the illumination and surface reflectance in terms of a finite number of basis functions. This yields a number of nonlinear equations for each color patch. We show that given a sufficient number of surface patches with the same illumination it is possible to solve these equations up to an overall scaling factor. Generalizations to the spatial dependent situation are discussed. We define a method for detecting material changes and illustrate a way of detecting the color of a material at its boundaries and propagating it inwards. %Y cost: $1.50, also available as NTIS report AD-A150172 %A Douglas Hofstadter %T The Copycat Project: An Experiment in Nondeterminism and Creative Analogies %R AI Memo 755 %I Artificial Intelligence Laboratory, Massachusetts Institute of Technology %K mit aim ail %I Artificial Intelligence Laboratory, Massachusetts Institute of Technology %D January 1984 %P 47 %K mit aim ail %K analogy, nondeterminism, parallelism, randomness, statistically emergent mentality, semanticity, slippability, computational temperature %X A microworld is described, in which many analogies involving strikingly different concepts and levels of subtlety can be made. The question "What differentiates the good ones from the bad ones?" is discussed, and then the problem of how to implement a computational model of the human ability to come up with such analogies (and to have a sense for their quality) is considered. A key part of the proposed system, now under development, is its dependence on statistically emergent properties of stochastically interacting "codelets" (small pieces of ready-to-run code created by the system, and selected at random to run with probability proportional to heuristically assigned "urgencies"). Another key element is a network of linked concepts of varying levels of "semanticity", in which activation spreads and indirectly controls the urgencies of new codelets. There is pressure in the system toward maximizing the degree of "semanticity" or "intensionality" of descriptions of structures, but many such pressures, often conflicting, must interact with one another, and compromises must be made. The shifting of (1) perceived boundaries inside structures, (2) descriptive concepts chosen to apply to structures, and (3) features perceived as "salient" or not, is called "slippage". What can slip, and how, are emergent consequences of the interaction of (1) the temporary ("cytoplasmic") structures involved in the analogy with (2) the permanent ("Platonic") concepts and links in the conceptual proximity network, or "slippability network". The architecture of this system is postulated as a general architecture suitable for dealing not only with fluid analogies, but also with other types of abstract perception and categorization tasks, such as musical perception, scientific theorizing, Bongard problems and others. %Y cost: $2.75, also available as NTIS report AD-A142744 %A Michael Brady %T Artificial Intelligence and Robotics %R AI Memo 756 %I Artificial Intelligence Laboratory, Massachusetts Institute of Technology %K mit aim ail %I Artificial Intelligence Laboratory, Massachusetts Institute of Technology %D February 1984 %P 44 %K mit aim ail %K robotics, artificial intelligence %X Since Robotics is the field concerned with the connection of perception to action, Artificial Intelligence must have a central role in Robotics if the connection is to be ``intelligent''. Artificial Intelligence addresses the crucial questions of: what knowledge is required in any aspect of thinking: how that knowledge should be represented; and how that knowledge should be used. Robotics challenges AI by forcing it to deal with real objects in the real world. Techniques and representations developed for purely cognitive problems, often in toy domains, do not necessarily extend to meet the challenge. Robots combine mechanical effectors, sensors, and computers. AI has made significant contributions to each component. We review AI contributions to perception and object oriented reasoning. Object oriented reasoning includes reasoning about space, path-planning, uncertainty, and compliance. We conclude with three examples that illustrate the kinds of reasoning or problem solving abilities we would endow robots with and that we believe are worthy goals of both Robotics and Artificial Intelligence, being within reach of both. %Y cost: $2.75, also available as NTIS report AD-A142488 %A Michael Brady %A Haruo Asada %T Smoothed Local Symmetries and Their Implementation %R AI Memo 757 %I Artificial Intelligence Laboratory, Massachusetts Institute of Technology %K mit aim ail %I Artificial Intelligence Laboratory, Massachusetts Institute of Technology %D February 1984 %P 44 %K mit aim ail %X We introduce a novel representation of two-dimensional shape that we call ``smoothed local symmetries'' (SLS). Smoothed local symmetries represent both the bounding contour of a shape fragment and the region that it occupies. In this paper we develop the main features of the SLS representation and describe an implemented algorithm that computes it. The performance of the algorithm is illustrated for a set of tools. We conclude by sketching a method for determining the articulation of a shape into subshapes. %Y cost: $2.75, also available as NTIS report AD-A142489 %A Haruo Asada %A Michael Bradey %T The Curvature Primal Sketch %R AI Memo 758 %I Artificial Intelligence Laboratory, Massachusetts Institute of Technology %K mit aim ail %I Artificial Intelligence Laboratory, Massachusetts Institute of Technology %D February 1984 %P 22 %K mit aim ail %K image understanding, vision, shape %X In this paper we introduce a novel representation of the significant changes in curvature along the bounding contour of planar shape. We call the representation the ``curvature primal sketch'' and illustrate its performance on a set of tool shapes. The curvature primal sketch derives its name from the close analogy to the primal sketch representation advocated by Marr for describing significant intensity changes. We define a set of primitive parameterized curvature discontinuities, and derive expressions for their convolutions with the first and second derivatives of a Gaussian. The convolved primitives, sorted according to the scale at which they are detected, provide us with a multi-scaled interpretation of the contour of a shape. %Y cost: $2.25, also available as NTIS report AD-A142460 %A Tomas Lozano-Perez %A Matthew T. Mason %A Russell H. Taylor %T Automatic Synthesis of Fine-Motion Strategies for Robots %R AI Memo 759 %I Artificial Intelligence Laboratory, Massachusetts Institute of Technology %K mit aim ail %I Artificial Intelligence Laboratory, Massachusetts Institute of Technology %D December 1983 %P 34 %K mit aim ail %K robotics, compliance, task planning, automatic programming %X The use of active compliance enables robots to carry out tasks in the presence of significant sensing and control errors. Compliant motions are quite difficult for humans to specify, however. Furthermore, robot programs are quite sensitive to details of geometry and to error characteristics and must, therefore, be constructed anew for each task. These factors motivate the need for automatic synthesis tools for robot programming, especially for compliant motion. This paper describes a formal approach to the synthesis of compliant motion strategies from geometric descriptions of assembly operations and explicit estimates of errors in sensing and control. A key aspect of the approach is that it provides correctness criteria for compliant motion strategies. %Y cost: $2.25, also available as NTIS report AD-A139532 %A Van-Duc Nguyen %T The Find-Path Problem in the Plane %R AI Memo 760 %I Artificial Intelligence Laboratory, Massachusetts Institute of Technology %K mit aim ail %I Artificial Intelligence Laboratory, Massachusetts Institute of Technology %D February 1984 %P 70 %K mit aim ail %X This paper presents a fast heuristic algorithm for planning collision-free paths of a moving robot in a cluttered planar workspace. The algorithm is based on describing the free space between the obstacles as a ``network of linked cones''. Cones capture the ``freeways'' and the ``bottlenecks'' between the obstacles. Links capture the ``connectivity'' of the free space. Paths are computed by intersecting the valid ``configuration volumes'' of the moving robot inside these cones and inside the regions described by the links. %Y cost: $3.00, also available as NTIS report AD-A142549 %A Ellen C. Hildreth %T Computations Underlying the Measurement of Visual Motion %R AI Memo 761 %I Artificial Intelligence Laboratory, Massachusetts Institute of Technology %K mit aim ail %I Artificial Intelligence Laboratory, Massachusetts Institute of Technology %D March 1984 %P 53 %K mit aim ail %X The organization of movement in a changing image provides a valuable source of information for analyzing the environment in terms of objects, their motion in space, and their three-dimensional structure. This movement may be represented by a two-dimensional velocity field that assigns a direction and magnitude of velocity to elements in the image. This paper presents a method for computing the velocity field, with three main components. First, initial measurements of motion in the image take place at the location of significant intensity changes, which give rise to zero-crossings in the output of the convolution of the image with a $\nabla_2 G$ operator. The initial motion measurements provide the component of velocity in the direction perpendicular to the local orientation of the zero-crossing contours. Second, these initial measurements are integrated along contours to compute the two-dimensional velocity field. Third, an additional constraint of smoothness of the velocity field, based on the physical constraint that surfaces are generally smooth, allows the computation of a unique velocity field. The details of an algorithm are presented, with results of the algorithm applied to artificial and natural image sequences. %Y cost: $2.75 %A W. Eric L. Grimson %T Computational Experiments with a Feature Based Stereo Algorithm %R AI Memo 762 %I Artificial Intelligence Laboratory, Massachusetts Institute of Technology %K mit aim ail %I Artificial Intelligence Laboratory, Massachusetts Institute of Technology %D January 1984 %P 39 %K mit aim ail %X Computational models of the human stereo system can provide insight into general information processing constraints that apply to any stereo system, either artificial or biological. In 1977, Marr and Poggio proposed one such computational model, that was characterized as matching certain feature points in difference-of-Gaussian filtered images, and using the information obtained by matching coarser resolution representations to restrict the search space for matching finer resolution representations. An implementation of the algorithm and its testing on a range of images was reported in 1980. Since then a number of psychophysical experiments have suggested possible refinements to the model and modifications to the algorithm. As well, recent computational experiments applying the algorithm to a variety of natural images, especially aerial photographs, have led to a number of modifications. In this article, we present a version of the Marr-Poggio-Grimson algorithm that embodies these modifications and illustrate its performance on a series of natural images. %Y cost: $2.25, also available as NTIS report AD-A142549 %A W. Eric L. Grimson %T The Combinatorics of Local Constraints in Model-Based Recognition and Localization From Sparse Data %R AI Memo 763 %I Artificial Intelligence Laboratory, Massachusetts Institute of Technology %K mit aim ail %I Artificial Intelligence Laboratory, Massachusetts Institute of Technology %D April 1984 %P 38 %K mit aim ail %K object recognition, model-based recognition, constraint propagation, constrained relaxation, combinatorial analysis %X The problem of recognizing what objects are where in the workspace of a robot can be cast as one of searching for a consistent matching between sensory data elements and equivalent model elements. In principle, this search space is enormous and to contain the potential explosion, constraints between the data and model elements are needed. We derive a set of constraints for sparse sensory data that are applicable to a wide variety of sensors and examine their completeness and exhaustiveness. We then derive general theoretical bounds on the number of interpretations expected to be consistent with the data under the effects of local constraints. These bounds are applicable to many types of local constraints, other than the specific examples used here. For the case of sparse, noisy three-dimensional sensory data, explicit values for the bounds are computed and are shown to be consistent with empirical results obtained earlier in [Grimson and Lozano-Perez 1984]. The results are used to demonstrate the graceful degradation of the recognition technique with the presence of noise in the data, and to predict the number of data points needed in general to uniquely determine the object being sensed. %Y cost: $2.25, also available as NTIS report AD-A148338 %A John M. Rubin %A W.A. Richards %T Color Vision: Representing Material Categories %R AI Memo 764 %I Artificial Intelligence Laboratory, Massachusetts Institute of Technology %K mit aim ail %I Artificial Intelligence Laboratory, Massachusetts Institute of Technology %D May 1984 %P 37 %K mit aim ail %X We argue that one of the early goals of color vision is to distinguish one kind of material from another. Accordingly, we show that when a pair of image regions is such that one region has greater intensity at one wavelength than at another wavelength, and the second region has the opposite property, then the two regions are likely to have arisen from distinct materials in the scene. We call this material change circumstance the "opposite slope sign condition." With this criterion as a foundation, we construct a representation of spectral information that facilitates the recognition of material changes. Our theory has implications for both psychology and neurophysiology. In particular, Hering's notion of opponent colors and psychologically unique primaries, and Land's results in two-color projection can be interpreted as different aspects of the visual system's goal of categorizing materials. Also, the theory provides two basic interpretations of the the function of double-opponent color cells described by neurophysiologists. %Y cost: $2.25 %A V. Torre %A T. Poggio %T On Edge Detection %R AI Memo 768 %I Artificial Intelligence Laboratory, Massachusetts Institute of Technology %K mit aim ail %I Artificial Intelligence Laboratory, Massachusetts Institute of Technology %D August 1984 %P 41 %K mit aim ail %K numerical differentiation, zero crossings, regularization %X Edge detection is the process that attempts to characterize the intensity changes in the image in terms of the physical processes that have originated them. A critical, intermediate goal of edge detection is the detection and characterization of significant intensity changes. This paper discusses this part of the edge detection problem. To characterize the types of intensity changes derivatives of different types, and possibly different scales, are needed. Thus, we consider this part of edge detection as a problem in numerical differentiation. We show that numerical differentiation of images is an ill-posed problem in the sense of Hadamard. Differentiation needs to be `regularized' by a regularizing filtering operation before differentiation. This shows that this part of edge detection consists of two steps, a `filtering' step and a `differentiation' step. Following this perspective, the paper discusses in detail the following theoretical aspects of edge detection: (1) The properties of different types of filters are derived. (2) Relationships among several 2-D differential operators are established. (3) Geometrical and topological properties of the zero crossings of differential operators are studied in terms of transversality and Morse theory. We discuss recent results on the behavior and the information content of zero crossings obtained with filters of different sizes. Finally, some of the existing local edge detector schemes are briefly outlined in the perspective of our theoretical results. %Y cost: $2.25, also available as NTIS report AD-A148573 %A Whitman Richards %A Donald D. Hoffman %T Codon Constraints on Closed 2D Shapes %R AI Memo 769 %I Artificial Intelligence Laboratory, Massachusetts Institute of Technology %K mit aim ail %I Artificial Intelligence Laboratory, Massachusetts Institute of Technology %D May 1984 %P 24 %K mit aim ail %K vision, recognition, transversality, visual representation, object perception, figure-ground %X Codons are simple primitives for describing plane curves. They thus are primarily image-based descriptors. Yet they have the power to capture important information about the 3D world, such as making part boundaries explicit. The codon description is highlty redundant (useful for error-correction). This redundancy can be viewed as a constraint on the number of possible codon strings. For smooth closed strings that represent the bounding contour (silhouette) of many smooth 3D objects, the constraints are so strong that sequences containing 6 elements yield only 33 generic shapes as compared with a possible number of 15,625 combinations. %Y cost: $2.25 %A Christof Koch %A Shimon Ullman %T Selecting One Among the Many: A Simple Network Implementing Shifts in Selective Visual Attention %R AI Memo 770 %I Artificial Intelligence Laboratory, Massachusetts Institute of Technology %K mit aim ail %I Artificial Intelligence Laboratory, Massachusetts Institute of Technology %D January 1984 %P 19 %K mit aim ail %K attention, lateral inhibition, selective visual attention, winner-take-all network, visual perception, lateral geniculate nucleus, hierarchical networks, cortical anatomy/physiology %O see also C.B.I.P. Paper 003 %X This study addresses the question of how simple networks can account for a variety of phenomena associated with the shift of a specialized processing focus across the visual scene. We address in particular aspects of the dichotomy between the preattentive-parallel and the attentive-serial modes of visual perception and their hypothetical neuronal implementations. Specifically, we propose the following: (1) A number of elementary features, such as color, orientation, direction of movement, disparity etc. are represented in parallel in different topographical maps, called the early representation. (2) There exists a selective mapping from this early representation into a more central representation, such that at any instant the central representation contains the properties of only a single location in the visual scene, the ``selected'' location. (3) We discuss some selection rules that determine which location will be mapped into the central representation. The major rule, using the saliency or conspicuity of locations in the early representation, is implemented using a so-called Winner-Take-All network. A hierarchical pyramid-like architecture is proposed for this network. We suggest possible implementations in neuronal hardware, including a possible role for the extensive back-projection from the cortex to the LGN. %Y cost: $1.50, also available as NTIS report AD-A148989 %A Ronald S. Fearing %A John M. Hollerbach %T Basic Solid Mechanics for Tactile Sensing %R AI Memo 771 %I Artificial Intelligence Laboratory, Massachusetts Institute of Technology %K mit aim ail %I Artificial Intelligence Laboratory, Massachusetts Institute of Technology %D March 1984 %P 23 %K mit aim ail %K robotics, tactile sensing, force sensing, contact sensing, end effectors, robot hands, feature extraction %X In order to stable grasp objects without using object models, tactile feedback from the fingers is sometimes necessary. This feedback can be used to adjust grasping forces to prevent a part from slipping from a hand. If the angle of force at the object finger contact can be determined, slip can be prevented by the proper adjustment of finger forces. Another important tactile sensing task is finding the edges and corners of an object, since they are usually feasible grasping locations. This paper describes how this information can be extracted from the finger-object contact using train sensors beneath a compliant skin. For determining contact forces, strain measurements are easier to use than the surface deformation profile. The finger is modelled as an infinite linear elastic half plane to predict the measured strain for several contact types and forces. The number of sensors required is less than has been proposed for other tactile recognition tasks. A rough upper bound on sensor density requirements for a specific depth is presented that is based on the frequence response of the elastic medium. The effects of different sensor stiffnesses on sensor performance are discussed. %Y cost: $2.25 %A Katsushi Ikeuchi %A H. Keith Nishihara %A Berthold K.P. Horn %A Patrick Sobalvarro %A Shigemi Nagata %T Determining Grasp Points Using Photometric Stereo and the PRISM Binocular Stereo System %R AI Memo 772 %I Artificial Intelligence Laboratory, Massachusetts Institute of Technology %K mit aim ail %I Artificial Intelligence Laboratory, Massachusetts Institute of Technology %D August 1984 %P 38 %K mit aim ail %X This paper describes a system which locates and grasps doughnut shaped parts from a pile. The system uses photometric stereo and binocular stereo as vision input tools. Photometric stereo is used to make surface orientation measurements. With this information the camera field is segmented into isolated regions of continuous smooth surface. One of these regions is then selected as the target region. The attitude of the physical object associated with the target region is determined by histograming surface orientations over that region and comparing with stored histograms obtained from prototypical objects. Range information, not available from photometric stereo is obtained by the PRISM binocular stereo system. A collision-free grasp configuration and approach trajectory is computed and executed using the attitude, and range data. %Y cost: $2.25, also available as NTIS report AD-A147782 %A Tomaso Poggio %A Vincent Torre %T Ill-Posed Problems and Regularization Analysis in Early Vision %R AI Memo 773 %I Artificial Intelligence Laboratory, Massachusetts Institute of Technology %K mit aim ail %I Artificial Intelligence Laboratory, Massachusetts Institute of Technology %D April 1984 %P 14 %K mit aim ail %K early vision, regularization theory, edge detection, ill-posed problems, motion analysis, variational problems %O see also C.B.I.P. Paper 001 %X One of the best definitions of early vision is that it is inverse optics -- a set of computational problems that both machines and biological organisms have to solve. While in classical optics the problem is to determine the images of physical objects, vision is confronted with the inverse problem of recovering three-dimensional shape from the light distribution in the image. Most processes of early vision such as stereomatching, computation of motion and all the "structure from" processes can be regarded as solutions to inverse problems. This common characteristic of early vision can be formalized - ``most early vision problems are "ill-posed problems" in the sense of Hadamard''. We will show that a mathematical theory developed for regularizing ill-posed problems leads in a natural way to the solution of early vision problems in terms of variational principles of a certain class. This is a new theoretical framework for some of the variational solutions already obtained in the analysis of early vision processes. It also shows how several other problems in early vision can be approached and solved. %Y cost: $1.50, also available as NTIS report AD-A147753 %A Gerald Roylance %T Some Scientific Subroutines in LISP %R AI Memo 774 %I Artificial Intelligence Laboratory, Massachusetts Institute of Technology %K mit aim ail %I Artificial Intelligence Laboratory, Massachusetts Institute of Technology %D September 1984 %P 12 %K mit aim ail %X Here's a LISP Library of Mathematical functions that calculate hyperbolic and inverse hyperbolic functions. Bessel functions, elliptic integrals, the gamma and beta functions, and the incomplete gamma and beta functions. There are probability density functions, cumulative distributions, and random number generators for the normal, Poisson, chi-square, Student's T, and Snedecor's F functions. Multiple linear regression, Fletcher-Powell unconstrained minimization, numerical integration, root finding, and convergence. Code to factor numbers and to do the Solovay-Strassen probabilistic prime test. %Y cost: $1.50, also available as NTIS report AD-A147889 %A Tomaso Poggio %T Vision by Man and Machine: How the brain processes visual information may be suggested by studies in computer vision (and vice versa) %R AI Memo 776 %I Artificial Intelligence Laboratory, Massachusetts Institute of Technology %K mit aim ail %I Artificial Intelligence Laboratory, Massachusetts Institute of Technology %D March 1984 %P 12 %K mit aim ail %K computer vision, human vision, stereo, computational approach %X The development of increasingly sophisticated and powerful computers in the last few decades has frequently stimulated comparisons between them and the human brain. Such comparisons will become more earnest as computers are applied more and more to tasks formerly associated with essentially human activities and capabilities. The expectation of a coming generation of 'intelligent' computers and robots with sensory, motor and even 'intellectual' skills comparable in quality to (and quantitatively surpassing) our own is becoming more widespread and is, I believe, leading to a new and potentially productive analytical science of 'information processing'. In no field has this new approach been so precisely formulated and so thoroughly exemplified as in the field of vision. As the dominant sensory modality of man, vision is one of the major keys to our mastery of the environment, to our understanding and control of the objects which surround us. If we wish to create robots capable of performing complex manipulative tasks in a changing environment, we must surely endow them with (among other things) adequate visual powers. How can we set about designing such flexible and adaptive robots? In designing them, can we make use of our rapidly growing knowledge of the human brain, and if so, how at the same time, can our experience in designing artificial vision systems help us to understand how the brain analyzes visual information? %Y cost: $1.50, also available as NTIS report AD-A147890 %A A.L. Yuille %A T. Poggio %T A Generalized Ordering Constraint for Stereo Correspondence %R AI Memo 777 %I Artificial Intelligence Laboratory, Massachusetts Institute of Technology %K mit aim ail %I Artificial Intelligence Laboratory, Massachusetts Institute of Technology %D May 1984 %P 25 %K mit aim ail %O see also C.B.I.P. Paper 005 %X The ordering constraint along epipolar lines is a powerful constraint that has been expoited by some recent stereomatching algorithms. We formulate a ``generalized ordering constraint'', not restricted to epipolar lines. We prove several properties of the generalized ordering constraint and of the "forbidden zone", the set of matches that would violate the constraint. We consider both the orthographic and the perspective projection case, the latter for a simplified but standard stereo geometry. The disparity gradient limit found in the human stereo system may be related to a form of the ordering constraint. To illustrate our analysis we outline a simple algorithm that exploits the generalized ordering constraint for matching contours of wireframe objects. We also show that the use of the generalized ordering constraint implies several other stereo matching constraints: a) the ordering constraint along epipolar lines, b) figural continuity, c) Binford's cross-product constraint, d) Mayhew and Frisby's figural continuity constraint. We finally discuss ways of extending the algorithm to arbitrary 3-D objects. %Y cost: $2.25, also available as NTIS report AD-A149182 %A Hugh Robinson %A Christof Koch %T An Information Storage Mechanism: Calcium and Spines %R AI Memo 779 %I Artificial Intelligence Laboratory, Massachusetts Institute of Technology %K mit aim ail %I Artificial Intelligence Laboratory, Massachusetts Institute of Technology %D April 1984 %P 15 %K mit aim ail %K information storage, short-term memory, biological hardware, dendritic spines, calcium, calmodulin, actin %O see also C.B.I.P. Paper 004 %X This proposal addresses some of the biophysical events possibly underlying fast activity-dependent changes in synaptic efficiency. Dendritic spines in the cortex have attracted increased attention over the last years as a possible locus of cellular plasticity, given the large number of studies reporting a close correlation between presynaptic activity (or lack of thereof) and changes in spine shape. This is highlighted by recent reports, showing that the spine cytoplasm contains high levels of actin. Moreover, it has been demonstrated that a high level of intracellular free calcium, $Ca^{2+''$, is a prerequisite for various forms of synaptic potentiation. We propose a series of plausible steps, linking presynaptic electrical activity at dendritic spines with a short-lasting change in spine geometry. Specifically, we conjecture that the spike-induced excitatory postsynaptic potential triggers an influx of $Ca^{2+''$ into the spine, where it will rapidly bind to intracellular calcium buffers such as calmodulin and calcineurin. However, for prolonged or intense presynaptic electrical activity, these buffers will saturate. The free $Ca^{2+''$ will then activate the actin/myosin network in the spine neck, reversibly shortening the length of the neck and increasing its diameter. This change in the geometry of the spine will lead to an increase in the synaptic efficiency of the synapse. We will discuss the implications of our proposal for the control of cellular plasticity and its relation to generalized attention and arousal. %Y cost: $1.50 %A H.K. Nishihara %T PRISM: A Practical Real-Time Imaging Stereo Matcher %R AI Memo 780 %I Artificial Intelligence Laboratory, Massachusetts Institute of Technology %K mit aim ail %I Artificial Intelligence Laboratory, Massachusetts Institute of Technology %D May 1984 %P 32 %K mit aim ail %K binocular stereo, noise tolerance, zero crossings, computer vision, stereo matching, correlation, binarization, robotics, obstacle avoidance, proximity sensors, structured light %X A binocular-stereo-matching algorithm for making rapid range measurements in noisy images is described. This technique is developed for applications to problems in robotics where noise tolerance, reliability, and speed are predominant issues. A high speed pipelined convolver for preprocessing images and an ``unstructured light'' technique for improving signal quality are introduced to help enhance performance to meet the demands of this task domain. These optimizations, however, are not sufficient. A closer examination of the problems encountered suggests that broader interpretations of both the objective of binocular stereo and of the zero-crossing theory of Marr and Poggio are required. In this paper, we restrict ourselves to the problem of making a single primitive surface measurement. For example, to determine whether or not a specified volume of space is occupied, to measure the range to a surface at an indicated image location, or to determine the elevation gradient at that position. In this framework we make a subtle but important shift from the explicit use of zero-crossing contours (in band-pass filtered images) as the elements matched between left and right images, to the use of the signs between zero-crossings. With this change, we obtain a simpler algorithm with a reduced sensitivity to noise and a more predictable behavior. The PRISM system incorporated this algorithm with the unstructured light technique and a high speed digital convolver. It has been used successfully by others as a sensor in a path planning system and a bin picking system. %Y cost: $2.25, also available as NTIS report AD-A142532 %A Carl Hewitt %A Tom Reinhardt %A Gul Agha %A Giuseppe Attardi %T Linguistic Support of Receptionists for Shared Resources %R AI Memo 781 %I Artificial Intelligence Laboratory, Massachusetts Institute of Technology %K mit aim ail %I Artificial Intelligence Laboratory, Massachusetts Institute of Technology %D May 1984 %P 30 %K mit aim ail %K parallel problem solving, guardian, actors, message passing, guarantee of service, serializers, transaction marker, concurrent system %X This paper addresses linguistic issues that arise in providing support for shared resources in large scale concurrent systems. Our work is based on the Actor Model of computation which unifies the lambda calculus, the sequential stored-program and the object-oriented models of computation. We show how ``receptionists'' can be used to regulate the use of shared resources by scheduling their access and providing protection against unauthorized or accidental access. A shared financial account is an example of the kind of resource that needs a receptionist. Issues involved in the implementation of scheduling policies for shared resources are also addressed. The modularity problems involved in implementing servers which multiplex the use of physical devices illustrate how delegation aids in the implementation of parallel problem solving systems for communities of actors. %Y cost: $2.25 %A Tomaso Poggio %A Christof Koch %T An Analog Model of Computation for the Ill-Posed Problems of Early Vision %R AI Memo 783 %I Artificial Intelligence Laboratory, Massachusetts Institute of Technology %K mit aim ail %I Artificial Intelligence Laboratory, Massachusetts Institute of Technology %D May 1984 %P 16 %K mit aim ail %K early vision, parallel processing, electrical chemical neuronal networks, regularization analysis, neural hardware, analog computation, motion analysis, variational problems %O see also Also C.B.I.P. Paper 002 %X A large gap exists at present between computational theories of vision and their possible implementation in neural hardware. The model of computation provided by the digital computer is clearly unsatisfactory for the neurobiologist, given the increasing evidence that neurons are complex devices, very different from simple digital switches. It is especially difficult to imagine how networks of neurons may solve the equations involved in vision algorithms in a way similar to digital computers. In this paper, we suggest an analog model of computation in electrical or chemical networks for a large class of vision problems, that maps more easily into biologically plausible mechanisms. Poggio and Torre (1984) have recently recognized that early vision problems such as motion analysis (Horn and Schunck, 1981; Hildreth, 1984a,b), edge detection (Torre and Poggio, 1984), surface interpolation (Grimson, 1981; Terzopoulos, 1984), shape-from-shading (Ikeuchi and Horn, 1981) and stereomatching can be characterized as mathematically ill-posed problems in the sense of Hadamard (1923). Ill-posed problems can be "solved", according to regularization theories, by variational principles of a specific type. A natural way of implementing variational problems are electrical, chemical or neuronal networks. We present specific networks for solving several low-level vision problems, such as the computation of visual motion and edge detection. %Y cost: $1.50, also available as NTIS report AD-A147726 %A Tamar Flash %T The Coordination of Arm Movements: An Experimentally Confirmed Mathematical Model %R AI Memo 786 %I Artificial Intelligence Laboratory, Massachusetts Institute of Technology %K mit aim ail %I Artificial Intelligence Laboratory, Massachusetts Institute of Technology %D November 1984 %P 32 %K mit aim ail %K Cartesian trajectory planning, jerk minimization, human multi-joint movements, end-effector trajectory planning, obstacle avoidance %X This paper presents studies of the coordination of voluntary human arm movements. A mathematical model is formulated which is shown to predict both the qualitative features and the quantitative details observed experimentally in planar, multi-joint arm movements. Coordination is modelled mathematically by defining an objective function, a measure of performance for any possible movement. The unique trajectory which yields the best performance is determined using dynamic optimization theory. In the work presented here the objective function is the square of the magnitude of jerk (rate of change of acceleration) of the hand integrated over the entire movement. This is equivalent to assuming that a major goal of motor coordination is the production of the smoothest possible movement of the hand. The theoretical analysis is based solely on the kinematics of movement independent of the dynamics of the musculoskeletal system, and is successful only when formulated in terms of the motion of the hand in extracorporal space. The implications with respect to movement organization are discussed. %Y cost: $2.25 %A Christof Koch %T A Theoretical Analysis of the Electrical Properties of a X-cell in the Cat's LGN: Does the Interneuron Gate the Visual Input to the X-System %R AI Memo 787 %I Artificial Intelligence Laboratory, Massachusetts Institute of Technology %K mit aim ail %I Artificial Intelligence Laboratory, Massachusetts Institute of Technology %D March 1984 %P 45 %K mit aim ail %K information processing, visual system, local circuits, geniculate nucleus, AND-NOT logic %O see also C.B.I.P. Paper 006 %X Electron-microscopic studies of relay cells in the lateral geniculate nucleus of the cat have shown that the retinal input of X-cells is associated with a special synaptic circuitry, termed the spine-triad complex. The retinal afferents make an asymmetrical synapse with both a dendritic appendage of the X-cell and a geniculate interneuron. The interneuron contacts in turn the same dendritic appendage with a symmetrical synaptic profile. The retinal input to geniculate Y-cells is predominately found on dendritic shafts without any triadic arrangement. We explore the integrative properties of X- and Y-cells resulting from this striking dichotomy in synaptic architecture. The basis of our analysis is the solution of the cable equation for a branched dendritic tree with a known somatic input resistance. Under the assumption that the geniculate interneuron mediates a shunting inhibition, activation of the interneuron reduces very efficiently the excitatory post-synaptic potential induced by the retinal afferent ``without'' affecting the electrical activity in the rest of the cell. Therefore, the spine-triad circuit implements the analog of an AND-NOT gate, unique to the X-system. Functionally, this corresponds to a presynaptic, feed-forward type of inhibition of the optic tract terminal. Since Y-cells lack this structure, inhibition acts globally, reducing the general electrical activity of the cell. We propose that geniculate interneurons gate the flow of visual information into the X-system as a function of the behavioral state of the animal, enhancing the center-surround antagonism and possibly mediating reciprocal lateral inhibition, eye-movement related suppression and selective visual attention. %Y cost: $2.75 %A G. Edward Barton\ Jr. %T Toward A Principle-Based Parser %R AI Memo 788 %I Artificial Intelligence Laboratory, Massachusetts Institute of Technology %K mit aim ail %I Artificial Intelligence Laboratory, Massachusetts Institute of Technology %D July 1984 %P 47 %K mit aim ail %K natural language, parsing, syntax, linguistics, generative grammar, GB-theory, metarules, modularity %X Parser design lags behind linguistic theory. While modern transformational grammar has largely abandoned complex, language-specific rules systems in favor of modular subsystems of principles and parameters, the rule systems that underlie existing natural-language parsers are still large, detailed, and complicated. The shift to modular theories in linguistics took place because of the scientific disadvantages of such rule systems. Those scientific ills translate into engineering maladies that make building natural-language systems difficult. The cure for these problems should be the same in parser design as it was in linguistic theory. The shift to modular theories of syntax should be replicated in parsing practice; a parser should base its actions on interacting modules of principles and parameters rather than a complex, monolithic rule system. If it can be successfully carried out, the shift will make it easier to build natural-language systems because it will shorten and simplify the language descriptions that are needed for parsing. It will also allow parser design to track new developments in linguistic theory. %Y cost: $2.75, also available as NTIS report AD-A147637 %A Christopher G. Atkeson %A John M. Hollerbach %T Kinematic Feature of Unrestrained Arm Movements %R AI Memo 790 %I Artificial Intelligence Laboratory, Massachusetts Institute of Technology %K mit aim ail %I Artificial Intelligence Laboratory, Massachusetts Institute of Technology %D July 1984 %P 26 %K mit aim ail %K control of limb movement, human motor control, dynamics of limb movement, kinematics of limb movement, 3-D movement monitoring, selspot system %O see also C.B.I.P Paper 007 %X Unrestrained human arm trajectories between point targets have been investigated using a three dimensional tracking apparatus, the Selspot system. Movements were executed between different points in a vertical plane under varying conditions of speed and hand-held load. In contrast to past results which emphasized the straightness of hand paths, movement regions were discovered in which the hand paths were curved. All movements, whether curved or straight, showed an invariant tangential velocity profile when normalized for speed and distance. The velocity profile invariance with speed and load is interpreted in terms of simplification of the underlying arm dynamics, extending the results of Hollerbach and Flash (1982). %Y cost: $2.25 %A J.L. Marroquin %T Surface Reconstruction Preserving Discontinuities %R AI Memo 792 %I Artificial Intelligence Laboratory, Massachusetts Institute of Technology %K mit aim ail %I Artificial Intelligence Laboratory, Massachusetts Institute of Technology %D August 1984 %P 25 %K mit aim ail %K surface reconstruction, discontinuity detection, Markov random fields, Bayesian estimation %X This paper presents some experimental results that indicate the plausibility of using non-convex variational principles to reconstruct piecewise smooth surfaces from sparse and noisy data. This method uses prior generic knowledge about the geometry of the discontinuities to prevent the blurring of the boundaries between continuous subregions. We include examples of the application of this approach to the reconstruction of synthetic surfaces, and to the interpolation of disparity data from the stereo processing of real images. %Y cost: $2.25, also available as NTIS report AD-A146741 %A Christof Koch and Tomaso Poggio %T Biophysics of Computation: Neurons, Synapses and Membranes %R AI Memo 795 %I Artificial Intelligence Laboratory, Massachusetts Institute of Technology %K mit aim ail %I Artificial Intelligence Laboratory, Massachusetts Institute of Technology %D October 1984 %P 73 %K mit aim ail %K computational systems, biophysics, information processing, biological implementation of logical gates, AND-NOT, spikes, spines, active processes %O see also C.B.I.P. Paper 008 %X Synapses, membranes and neurotransmitter play an important role in processing information in the nervous system. We do not know, however, what biophysical mechanisms are critical for neuronal computations, what elementary information processing operations they implement, and which sensory or motor computations they underlie. In this paper, we outline an approach to these problems. We review a number of different biophysical mechanisms, such as synaptic interactions between excitation and inhibition, dendritic spines, non-impulse generating membrane nonlinearities and transmitter-regulated voltage channels. For each one, we discuss the information processing operations that may be implemented. All of these mechanisms act either within a few milliseconds, such as the action potential or synaptic transmission, or over several hundred milliseconds or even seconds, modulating some property of the circuit. In some cases we will suggest specific examples where a biophysical mechanism underlies a given computation. In particular, we will discuss the neuronal operation, and their implementation, underlying direction selectivity in the vertebrate retina. %Y cost: $3.00 %A Alan Bawden %A Philip E. Agre %T What a parallel programming language has to let you say %R AI Memo 796 %I Artificial Intelligence Laboratory, Massachusetts Institute of Technology %K mit aim ail %I Artificial Intelligence Laboratory, Massachusetts Institute of Technology %D September 1984 %P 26 %K mit aim ail %K Connection Machine, programming languages, parallel computers, compiler theory, message passing %X We have implemented in simulation a prototype language for the Connection Machine called CL1. CL1 is an extrapolation of serial machine programming language technology: in CL1 one programs the individual processors to perform local computations and talk to the communications network. We present details of the largest of our experiments with CL1, an interpreter for Scheme (a dialect of LISP) that allows a large number of different Scheme programs to be run in parallel on the otherwise SIMD Connection Machine. Our aim was not to propose Scheme as a language for Connection Machine programming, but to gain experience using CL1 to implement an interesting and familiar algorithm. Consideration of the difficulties we encountered led us to the conclusion that CL1 programs do not capture enough of the causal structure of the processes they describe. Starting from this observation, we have designed a successor language call CGL (for Connection Graph Language). %Y cost: $2.25, also available as NTIS report AD-A147854 %A Demetri Terzopoulos %T Computing Visible-Surface Representations %R AI Memo 800 %I Artificial Intelligence Laboratory, Massachusetts Institute of Technology %K mit aim ail %I Artificial Intelligence Laboratory, Massachusetts Institute of Technology %D March 1985 %P 61 %K mit aim ail %K vision, multiresolution reconstruction, finite elements, discontinuities, surface representation, variational principles, generalized splines, regularization %X The low-level interpretation of images provides contraints on 3-D surface shape at multiple resolutions, but typically only at scattered locations over the visual field. Subsequent visual processing can be facilitated substantially if the scattered shape constraints are immediately transformed into visible-surface representations that unambiguously specify surface shape at every image point. The required transformation is shown to lead to an ill-posed surface reconstruction problem. A well posed variational principle formulation is obtained by invoking "controlled continuity," a physically nonrestrictive (generic) assumption about surfaces which is nonetheless strong enough to guarantee unique solutions. The variational principle, which admits an appealing physical interpretation, is locally discretized by applying the finite element method to a piecewise, finite element representation of surfaces. This forms the mathematical basis of a unified and general framework for computing visible-surface representations. An efficient surface reconstruction algorithm is developed. %Y cost: $2.75, also available as NTIS report AD-A160602 %A Kent Pitman %T The Description of Large Systems %R AI Memo 801 %I Artificial Intelligence Laboratory, Massachusetts Institute of Technology %K mit aim ail %I Artificial Intelligence Laboratory, Massachusetts Institute of Technology %D September 1984 %P 32 %K mit aim ail %K compilation, large systems, LISP, system maintenance %X In this paper, we discuss the problems associated with the description and manipulation of large systems when their sources are not maintained as single files. We show why and how tools that address these issues, such as Unix MAKE and Lisp Machine DEFSYSTEM, have evolved. %Y cost: $2.25, also available as NTIS report AD-A148072 %A Demetri Terzopoulos %T Multigrid Relaxation Methods and the Analysis of Lightness, Shading and Flow %R AI Memo 803 %I Artificial Intelligence Laboratory, Massachusetts Institute of Technology %K mit aim ail %I Artificial Intelligence Laboratory, Massachusetts Institute of Technology %D October 1984 %P 23 %K mit aim ail %K computer vision, lightness, optical flow, partial differential equations, multigrid relaxation, shape from shading, variational principles, parallel algorithms %X Image analysis problems posed mathematically as variational principles or as partial differential equations, are amenable to numerical solution by relaxation algorithms that are local, iterative, and often parallel. Although they are well suited structurally for implementation on massively parallel, locally-interconnected computational architectures, such distributed algorithms are seriously handicapped by an inherent inefficiency at propagating constraints between widely separated processing elements. Hence, they converge extremely slowly when confronted by the large representation necessary for low-level vision. Application of multigrid methods can overcome this drawback, as we established in previous work on 3-D surface reconstruction. In this paper, we develop efficient multiresolution iterative algorithms for computing lightness, shape-from-shading, and optical flow, and we evaluate the performance of these algorithms on synthetic images. The multigrid methodology that we describe is broadly applicable in low-level vision. Notably, it is an appealing strategy to use in conjunction with regularization analysis for the efficient solution of a wide range of ill-posed visual reconstruction problems. %Y cost: $2.25, also available as NTIS report AD-A158173 %A Gideon Sahar and John M. Hollerbach %T Planning of Minimum-Time Trajectories for Robot Arms %R AI Memo 804 %I Artificial Intelligence Laboratory, Massachusetts Institute of Technology %K mit aim ail %I Artificial Intelligence Laboratory, Massachusetts Institute of Technology %D November 1984 %P 25 %K mit aim ail %K robotics, manipulators, optimal paths, minimum-time paths, trajectory planning, path planning %X The minimum-time path for a robot arm has been a long-standing and unsolved problem of considerable interest. We present a general solution to this problem that involves joint-space tesselation, a dynamic time-scaling algorithm, and graph search. The solution incorporates full dynamics of movement and actuator constraints, and can be easily extended for joint limits and workspace obstacles, but is subject to the particular tesselation scheme used. The results presented show that, in general, the optimal paths are not straight lines, but rather curves in joint-space that utilize the dynamics of the arm and gravity to help in moving the arm faster to its destination. Implementation difficulties due to the tesselation and to combinatorial proliferation of paths are discussed. %Y cost: $2.25, also available as NTIS report AD-A148956 %A Michael A. Gennert %T Any Dimensional Reconstruction from Hyperplanar Projections %R AI Memo 805 %I Artificial Intelligence Laboratory, Massachusetts Institute of Technology %K mit aim ail %I Artificial Intelligence Laboratory, Massachusetts Institute of Technology %D October 1984 %P 18 %K mit aim ail %K tomography, nuclear magnetic resonance, medical imaging, density reconstruction %X In this paper we examine the reconstruction of functions of any dimension from hyperplanar projection. This is a generalization of a problem that has generated much interest recently, especially in the field of medical imaging. Computed Axial Tomography (CAT) and Nuclear Magnetic Resonance (NMR) are two medical techniques that fall in this framework. CAT scans measure the hydrogen density along planes through the body. Here we will examine reconstruction methods that involve backprojecting the projection data and summing this over the entire region of interest. There are two methods for doing this. One method is to filter the projection data first, and then backproject this filtered data and sum over all projection directions. The other method is to backproject and sum the projection data first, and then filter. The two methods are mathematically equivalent, producing very similar equations. We will derive the reconstruction formulas for both methods for any number of dimensions. We will examine the cases of two and three dimensions, since these are the only ones encountered in practice. The equations are very different for these cases. In general, the equations are very different for even and odd dimensionality. We will discuss why this is so, and show that the equations for even and odd dimensionality are related by the Hilbert Transform. %Y cost: $1.50 %A John Canny %T Collision Detection for Moving Polyhedra %R AI Memo 806 %I Artificial Intelligence Laboratory, Massachusetts Institute of Technology %K mit aim ail %I Artificial Intelligence Laboratory, Massachusetts Institute of Technology %D October 1984 %P 17 %K mit aim ail %K collision detection, collision avoidance, motion planning, robotics, geometric modelling %X We consider the problem of moving a three dimensional solid object among polyhedral obstacles. The traditional formulation of configuration space for this problem uses three translational parameters and three ``angles'' (typically Euler angles), and the constraints between the object and obstacles involve transcendental functions. We show that a quaternion representation of rotation yields constraints which are purely algebraic in a higher-dimensional space. By simple manipulation, the constraints may be projected down into a six dimensional space with no increase in complexity. Using this formulation, we derive an efficient ``exact'' intersection test for an object which is translating and rotating among obstacles. %Y cost: $2.25, also available as NTIS report AD-A148961 %A Ronald S. Fearing %T Simplified Grasping and Manipulation with Dextrous Robot Hands %R AI Memo 809 %I Artificial Intelligence Laboratory, Massachusetts Institute of Technology %K mit aim ail %I Artificial Intelligence Laboratory, Massachusetts Institute of Technology %D November 1984 %P 17 %K mit aim ail %K automatic grasping, force control, stable grasping, robot hands, regrasping objects, re-orienting objects, dextrous hands %X A method is presented for stably grasping two-dimensional polygonal objects with a dextrous hand when object models are not available. Basic constraints on object vertex angles are found for feasible grasping with two fingers. Local tactile information can be used to determine the finger motion that will reach feasible grasping locations. With an appropriate choice of finger stiffnesses, a hand can automatically grasp these objects with two fingers. The bounded slip of a part in a hand is shown to be valuable for adapting the fingers and object to a stable situation. Examples are given to show the ability of this grasping method to accommodate disturbance forces and to perform simple part reorientations and regrasping operations. %Y cost: $1.50, also available as NTIS report AD-A148962 %A Richard J. Doyle %T Hypothesizing and Refining Causal Models %R AI Memo 811 %I Artificial Intelligence Laboratory, Massachusetts Institute of Technology %K mit aim ail %I Artificial Intelligence Laboratory, Massachusetts Institute of Technology %D December 1984 %P 108 %K mit aim ail %K learning, causal reasoning, qualitative reasoning, telelogical reasoning, theory formation, planning, analogy, quantities. %X An important common sense competence is the ability to hypothesize causal relations. This paper presents a set of constraints which make the problem of formulating causal hypotheses about simple physical systems a tractable one. The constraints include: 1) a temporal and physical proximity requirement, 2) a set of abstract causal explanations for changes in physical systems in terms of dependences between quantities, 3) a teleological assumption that dependences in designed physical systems are functions. These constraints were embedded in a learning system which was tested in two domains: a sink and a toaster. The learning system successfully generated and refined naive causal models of these simple physical systems. The causal models which emerge from the learning process support causal reasoning - explanation, prediction, and planning. Inaccurate predictions and failed plans in turn indicate deficiencies in the causal models and the need to rehypothesize. Thus learning supports reasoning which leads to further learning. The learning system makes use of standard inductive rules of inference as well as the constraints on causal hypotheses to generalize its causal models. Finally, a simple example involving an analogy illustrates another way to repair incomplete causal models. %Y cost: $3.00, also available as NTIS report AD-A158165 %A G. Edward Barton\ Jr. %T On the Complexity of ID/LP Parsing %R AI Memo 812 %I Artificial Intelligence Laboratory, Massachusetts Institute of Technology %K mit aim ail %I Artificial Intelligence Laboratory, Massachusetts Institute of Technology %D December 1984 %P 22 %K mit aim ail %K parsing, ID/LP grammars, context free grammar, NP-completeness, natural language, Earley's algorithm, GPSG, UCFG parsing. %X Recent linguistic theories cast surface complexity as the result of interacting subsystems of constraints. For instance, the ID/LP grammar formalism separates constraints on immediate dominance from those on linear order. Shieber (1983) has shown how to carry out direct parsing of ID/LP grammars. His algorithm uses ID and LP constraints directly in language processing, without expanding them into a context-free object grammar. This report examines the computational difficulty of ID/LP parsing. %Y cost: $2.25, also available as NTIS report AD-A158211 %A Berthold K.P. Horn and Michael J. Brooks %T The Variational Approach to Shape from Shading %R AI Memo 813 %I Artificial Intelligence Laboratory, Massachusetts Institute of Technology %K mit aim ail %I Artificial Intelligence Laboratory, Massachusetts Institute of Technology %D March 1985 %P 33 %K mit aim ail %K calculus of variations, parallel iteration, regularization, shading, shape, shape from shading %X We develop a systematic approach to the discovery of parallel iterative schemes for solving the shape-from-shading problem on a grid. A standard procedure for finding such schemes is outlined, and subsequently used to derive several new ones. The shape-from-shading problem is known to be mathematically equivalent to a nonlinear first-order partial differential equation in surface elevation. To avoid the problems inherent in methods used to solve such equations, we follow previous work in reformulating the problem as one of finding a surface orientation field that minimizes the integral of the brightness error. The calculus of variations is then employed to derive the appropriate Euler equations on which iterative schemes can be based. Different schemes result if one uses different parameters to describe surface orientation. We derive two new schemes, using unit surface normals, that facilitate the incorporation of the occluding boundary information. These schemes, while more complex, have several advantages over previous ones. %Y cost: $2.25 %A Kenneth Man-Kam Yip %T Tense, Aspect and Cognitive Representation of Time %R AI Memo 815 %I Artificial Intelligence Laboratory, Massachusetts Institute of Technology %K mit aim ail %I Artificial Intelligence Laboratory, Massachusetts Institute of Technology %D December 1984 %P 26 %K mit aim ail %K temporal logic, linguistic constraints, learnability, tense and aspect, processing constraints, markedness %X This paper explores the relationships between a computational theory of temporal representation (as develped by James Allen) and a formal linguistic theory of tense (as developed by Norbert Hornstein) and aspect. It aims to provide explicit answers to four fundamental questions: (1) what is the computational justification for the primitives of a linguistic theory; (2) what is the computational explanation of the formal grammatical constraints; (3) what are the processing constraints imposed on the learnability and markedness of these theoretical constructs; and (4) what are the constraints that a linguistic theory imposes on representation. We show that one can effectively exploit the interface between the language faculty and the cognitive faculties by using linguistic constraints to determine restrictions on the cognitive representations and ``vice versa''. Three main results are obtained: (1) We derive an explanation of an observed grammatical constraint on tense -- the Linear Order Constraint -- from the information monotonicity property of the constraint propagation algorithm of Allen's temporal system: (2) We formulate a principle of markedness for the basic tense structures based on the computational efficiency of the temporal representations; and (3) We show Allen's interval-based temporal system is not arbitrary, but it can be used to explain independently motivated linguistic constraints on tense and aspect interpretations. We also claim that the methodology of research developed in this study -- "cross-level" investigation of independently motivated formal grammatical theory and computational models -- is a powerful paradigm with which to attack representational problems in basic cognitive domains, e.g. space, time, causality, etc. %Y cost: $2.25, also available as NTIS report AD-A159306 %A Richard C. Waters %T PP: A Lisp Pretty Printing System %R AI Memo 816 %I Artificial Intelligence Laboratory, Massachusetts Institute of Technology %K mit aim ail %I Artificial Intelligence Laboratory, Massachusetts Institute of Technology %D December 1984 %P 37 %K mit aim ail %K pretty printing, formatted output, abbreviated output, LISP %X The PP system provides an efficient implementation of the Common Lisp pretty printing function PPRINT. In addition, PP goes beyond ordinary pretty printers by providing mechanisms which allow the user to control the exact form of pretty printed output. This is done by extending Lisp in two ways. First, several new FORMAT directives are provided which support dynamic decisions about the placement of newlines based on the line width available for output. Second, the concept of print-self methods is extended so that it can be applied to lists as well as to objects which can receive messages. Together, these extensions support pretty printing of both programs and data structures. The PP system also modifies the way that the Lisp printer handles the abbreviation of output. The traditional mechanisms for abbreviating lists based on nesting depth and length are extended so that they automatically apply to every kind of structure without the user having to take any explicit action when writing print-self methods. A new abbreviation mechanism is introduced which can be used to limit the total number of lines printed. %Y cost: $2.25, also available as NTIS report A157092 %A A. Hurlbert and T. Poggio %T Spotlight on Attention %R AI Memo 817 %I Artificial Intelligence Laboratory, Massachusetts Institute of Technology %K mit aim ail %I Artificial Intelligence Laboratory, Massachusetts Institute of Technology %D April, 1985 %P 6 %K mit aim ail %X We review some recent psychophysical, physiological and anatomical data which highlight the important role of attention in visual information processing, and discuss the evidence for a serial spotlight of attention. We point out the connections between the questions raised by the spotlight model and computational results on the intrinsic parallelism of several tasks in vision. %Y cost: $1.50 %A Michael J. Brooks and Berthold K.P. Horn %T Shape and Source from Shading %R AI Memo 820 %I Artificial Intelligence Laboratory, Massachusetts Institute of Technology %K mit aim ail %I Artificial Intelligence Laboratory, Massachusetts Institute of Technology %D January 1985 %P 12 %K mit aim ail %K computer vision, source detection, shape from shading, Lambertian surface %X Well-known methods for solving the shape-from-shading problem require knowledge of the reflectance map. Here we show how the shape-from-shading problem can be solved when the reflectance map is not available, but is known to have a given form with some unknown parameters. This happens, for example when the surface is known to be Lambertian, but the direction to the light source is not known. We display an iterative algorithm which alternately estimates the surface shape and the light source direction. Use of the unit normal in the parameterization of the reflectance map, rather than the gradient or stereographic coordinates, simplifies the analysis. Our approach also leads to an iterative scheme for computing shape from shading that adjusts the current estimates of the local normals toward or away from the direction of the light source. The amount of adjustment is proportional to the current difference between the predicted and the observed brightness. Generalizations to less constrained forms of reflectance maps are also developed. %Y cost: $1.50 %A Shahriar Negahdaripour and Berthold K.P. Horn %T Direct Passive Navigation %R AI Memo 821 %I Artificial Intelligence Laboratory, Massachusetts Institute of Technology %K mit aim ail %I Artificial Intelligence Laboratory, Massachusetts Institute of Technology %D February 1984 %P 19 %K mit aim ail %K passive navigation, optical flow, structure and motion, least squares, planar surfaces, non-linear equations, dual solution, planar motion, field equations %X In this paper, we show how to recover the motion of an observer relative to a planar surface directly from image brightness derivatives. We do not compute the optical flow as an intermediate step. We derive a set of nine non-linear equations using a least-squares formulation. A simple iterative scheme allows us to find either of two possible solutions of these equations. An initial pass over the relevant image region is used to accumulate a number of moments of the image brightness derivatives. All of the quantities used in the iteration can be efficiently computed from these totals, without the need to refer back to the image. A new, compact notation allows us to show easily that there are at most two planar solutions. %Y cost: $1.50 %A Michael Brady %A Jean Ponce %A Alan Yuille %A Haruo Asada %T Describing Surfaces %R AI Memo 822 %I Artificial Intelligence Laboratory, Massachusetts Institute of Technology %K mit aim ail %I Artificial Intelligence Laboratory, Massachusetts Institute of Technology %D January 1985 %P 33 %K mit aim ail %K computer vision, robotics, 3-D vision, surface description, computer aided design, object recognition %X This paper continues our work on visual representations of three-dimensional surfaces [Brady and Yuille 1984b]. The theoretical component of our work is a study of classes of surface curves as a source of constraint on the surface on which they lie, and as a basis for describing it. We analyze bounding contours, surface intersections, lines of curvature, and asymptotes. Our experimental work investigates whether the information suggested by our theoretical study can be computed reliably and efficiently. We demonstrate algorithms that compute lines of curvature of a (Gaussian smoothed) surface; determine planar patches and umbilic regions; extract axes of surfaces of revolution and tube surfaces. We report preliminary results on adapting the curvature primal sketch algorithms of Asada and Brady [1984] to detect and describe surface intersections. %Y cost: $2.25, also available as NTIS report AD-A158940 %A Jonathan H. Connell %A Michael Brady %T Generating and Generalizing Models of Visual Objects %R AI Memo 823 %I Artificial Intelligence Laboratory, Massachusetts Institute of Technology %K mit aim ail %I Artificial Intelligence Laboratory, Massachusetts Institute of Technology %D July 1985 %P 24 %K mit aim ail %K vision, learning, shape description, representation of shape %X We report on initial experiments with an implemented learning system whose inputs are images of two dimensional shapes. The system first builds semantic network descriptions of shapes based on Brady's {\it smoothed local symmetry'' representation. It learns shape models from them using a substantially modified version of Winston's ANALOGY program. A generalization of Gray coding enables the representation to be extended and allows a single operation, called ``ablation'', to achieve the effects of many standard induction heuristics. The program can learn disjunctions, and learn concepts using only positive examples. We discuss learnability and the pervasive importance of representational hierarchies. %Y cost: $2.25 %A Jean Ponce %A Michael Brady %T Toward a Surface Primal Sketch %R AI Memo 824 %I Artificial Intelligence Laboratory, Massachusetts Institute of Technology %K mit aim ail %I Artificial Intelligence Laboratory, Massachusetts Institute of Technology %D April 1985 %P 30 %K mit aim ail %K vision, edge detection, 3-D vision, robotics, surface representation. %X This paper reports progress toward the development of a representation of significant surface changes in dense depth maps. We call the representation the ``surface primal sketch'' by analogy with representations of intensity change, image structure, and changes in curvature of planar curves. We describe an implemented program that detects, localizes, and symbolically describes: ``steps'', where the surface height function is discontinuous; ``roofs'', where the surface is continuous but the surface normal is discontinuous; ``smooth joins'', where the surface normal is continuous but a principal curvature is discontinuous and changes sign; and ``shoulders'', which consist of two roofs and correspond to a STEP viewed obliquely. We illustrate the performance of the program on range maps of objects of varying complexity. %Y cost: $2.25, also available as NTIS report AD-A159693 %A S. Murray Sherman %A Christof Koch %T The Anatomy and Physiology of Gating Retinal Signals in the Mammalian Lateral Geniculate Nucleus %R AI Memo 825 %I Artificial Intelligence Laboratory, Massachusetts Institute of Technology %K mit aim ail %I Artificial Intelligence Laboratory, Massachusetts Institute of Technology %D June 1985 %P 34 %K mit aim ail %K visual system, lateral geniculate nucleus, gating signals, visual attention, top-down processing. %X In the mammalian visual system, the lateral geniculate nucleus is commonly thought to act merely as a relay for the transmission of visual information from the retina to the visual cortex, a relay without significant elaboration in receptive field properties or signal strength. In this paper, we will review the different anatomical pathways and biophysical mechanisms possibly implementing a selective gating of visual information flow from the retina to the visual cortex. We will argue that the lateral geniculate nucleus in mammals is one of the earliest sites where selective, visual attention operates and where general changes in neuronal excitability as a function of the behavioral states of the animal, for instance sleep, paradoxical sleep, arousal, etc., occur. %Y cost: $2.25 %A Michael Drumheller %T Mobile Robot Localization Using Sonar %R AI Memo 826 %I Artificial Intelligence Laboratory, Massachusetts Institute of Technology %K mit aim ail %I Artificial Intelligence Laboratory, Massachusetts Institute of Technology %D January 1985 %P 25 %K mit aim ail %K mobile robot, robot navigation, sonar, ultrasonic rangefinding, rangefinding, robot localization, robot positioning, contour matching %X This paper describes a method by which range data from a sonar or other type of rangefinder can be used to determine the two-dimensional position and orientation of a mobile robot inside a room. The plan of the room is modeled as a list of segments indicating the positions of walls. The method works by extracting straight segments from the range data and examining all hypotheses about pairings between the segments and walls in the model of the room. Inconsistent pairings are discarded efficiently by using local constraints based on distances between walls, angles between walls, and ranges between walls along their normal vectors. These constraints are used to obtain a small set of possible positions, which is further pruned using a test for physical consistency. The approach is extremely tolerant of noise and clutter. Transient objects such as furniture and people need not be included in the room model, and very noisy, low-resolution sensors can be used. The algorithm's performance is demonstrated using a Polaroid Ultrasonic Rangefinder, which is a low-resolution, high-noise sensor. %Y cost: $2.25, also available as NTIS report AD-A158819 %A Philip E. Agre %T Routines %R AI Memo 828 %I Artificial Intelligence Laboratory, Massachusetts Institute of Technology %K mit aim ail %I Artificial Intelligence Laboratory, Massachusetts Institute of Technology %D May 1985 %P 27 %K mit aim ail %K routines, planning, process representation %X Regularities in the world give rise to regularities in the way in which we deal with the world. That is to say, we fall into routines. I have been studying the phenomena of routinization, the process by which institutionalized patterns of interaction with the world arise and evolve in everyday life. Underlying this evolution is a dialectical process of ``internalization'': First you build a model of some previosly unarticulated emergent aspect of an existing routine. Armed with an incrementally more global view of the interaction, you can often formulate an incrementally better informed plan of attack. A routine is NOT a plan in the sense of the classical planning literature, except in theoretical limit of the process. I am implementing this theory using ``running arguments'', a technique for writing rule-based programs for intelligent agents. Because a running argument is compiled into TMS networks as it proceeds, incremental changes in the world require only incremental recomputation of the reasoning about what actions to take next. The system supports a style of programming, ``dialectical argumentation'', that has many important properties that recommend it as a substrate for large AI systems. One of these might be called ``additivity'': an agent can modify it's reasoning in a class of situations by adducing arguments as to why it's previous arguments were incorrect in those cases. Because no side-effects are ever required, reflexive systems based on dialectical argumentation ought to be less fragile than intuition and experience might suggest. I outline the remaining implementation problems. %Y cost: $2.25, also available as NTIS report AD-A160481 %A Kent M. Pitman %T CREF: An Editing Facility for Managing Structured Text %R AI Memo 829 %I Artificial Intelligence Laboratory, Massachusetts Institute of Technology %K mit aim ail %I Artificial Intelligence Laboratory, Massachusetts Institute of Technology %D February 1985 %P 23 %K mit aim ail %K browsing, document preparation, editing environments, information management, knowledge engineering, mail reading, non-linear text, protocol parsing, structured text, text editing %X This paper reports work in progress on an experimental text editor called CREF, the Cross Referenced Editing Facility. CREF deals with chunks of text, called segments, which may have associated features such as keywords or various kinds of links to other segments. Text in CREF is organized into linear collections for normal browsing. The use of summary and cross-reference links in CREF allows the imposition of an auxiliary network structure upon the text which can be useful for ``zooming in and out'' or ``non-local transitions''. Although it was designed as a tool for use in complex protocol analysis by a Knowledge Engineer's Assistant, CREF has many interesting features which should make it suitable for a wide variety of applications, including browsing, program editing, document preparation, and mail reading. %Y cost: $2.25, also available as NTIS report AD-A158155 %A T. Poggio %A H. Voorhees %A A. Yuille %T A Regularized Solution to Edge Detection %R AI Memo 833 %I Artificial Intelligence Laboratory, Massachusetts Institute of Technology %K mit aim ail %I Artificial Intelligence Laboratory, Massachusetts Institute of Technology %D April 1985 %P 22 %K mit aim ail %X We consider edge detection as the problem of measuring and localizing changes of light intensity in the image. As discussed by Torre and Poggio (1984), edge detection, when defined in this way, is an ill-posed problem in the sense of Hadamard. The regularized solution that arises is then the solution to a variational principle. In the case of exact data, one of the standard regularization methods (see Poggio and Torre, 1984) leads to cubic spline interpolation before differentiation. We show that in the case of regularly-spaced data this solution corresponds to a convolution filter -- to be applied to the signal before differentiation -- which is a cubic spline. In the case of non-exact data, we use another regularization method that leads to a different variational principle. We prove (1) that this variational principle leads to a convolution filter for the problem of one-dimensional edge detection, (2) that the form of this filter is very similar to the gaussian filter, and (3) that the regularizing parameter $lambda$ in the variational principle effectively controls the scale of the filter. %Y cost: $2.25, also available as NTIS report AD-A159349 %A John M. Rubin %A W.A. Richards %T Boundaries of Visual Motion %R AI Memo 835 %I Artificial Intelligence Laboratory, Massachusetts Institute of Technology %K mit aim ail %I Artificial Intelligence Laboratory, Massachusetts Institute of Technology %D April 1985 %P 29 %K mit aim ail %K vision, visual motion, motion recognition, event perception, motion representation, motion perception, motion boundaries. %X A representation of visual motion convenient for recognition should make prominent the qualitative differences among simple motions. We argue that the first stage in such a motion representation is to make explicit boundaries that we define as starts, stops and force discontinuities. When one of these boundaries occurs in motion, human observers have the subjective impression that some fleeting, significant event has occurred. We go farther and hypothesize that one of the subjective motion boundaries is seen if and only if one of our defined boundaries occurs. We enumerate all possible motion boundaries and provide evidence that they are psychologically real. %Y cost: $2.25 %A Robert C. Berwick %A Amy S. Weinberg %T Parsing and Linguistic Explanation %R AI Memo 836 %I Artificial Intelligence Laboratory, Massachusetts Institute of Technology %K mit aim ail %I Artificial Intelligence Laboratory, Massachusetts Institute of Technology %D April 1985 %P 32 %K mit aim ail %K natural language processing, cognitive modeling, parsing %X This article summarizes and extends recent results linking deterministic parsing to observed "locality principles" in syntax. It also argues that grammatical theories based on explicit phrase structure rules are unlikely to provide comparable explanations of why natural languages are built the way they are. %Y cost: $2.25, also available as NTIS report AD-A159233 %A Eric Sven Ristad %T GPSG-Recognition is NP-Hard %R AI Memo 837 %I Artificial Intelligence Laboratory, Massachusetts Institute of Technology %K mit aim ail %I Artificial Intelligence Laboratory, Massachusetts Institute of Technology %D March 1985 %P 11 %K mit aim ail %X Proponents of Generalized Phrase Structure Grammar (GPSG) often cite its weak context-free generative power as proof of the computational tractability of GPSG-Recognition. It is well known that context-free languages can be parsed by a wide range of algorithms. Hence, it might be thought that GPSG's weak context-free generative power should guarantee that it, too, is efficiently parsible. This widely-assumed GPSG efficient parsibility" result is false: A reduction from 3-Satisfiability proves that GPSG-Recognition is in the class NP-hard, and likely to be intractable. %Y cost: $1.50 %A Jean Ponce %T Prism Trees: An Efficient Representation for Manipulating and Displaying Polyhedra With Many Faces %R AI Memo 838 %I Artificial Intelligence Laboratory, Massachusetts Institute of Technology %K mit aim ail %I Artificial Intelligence Laboratory, Massachusetts Institute of Technology %D April 1985 %P 22 %K mit aim ail %K computer graphics, hierarchical structures, set operations between solids, geometric modelling, ray casting display. %X Computing surface and/or object intersections is a corner-stone of many algorithms in geometric modeling and computer graphics, for example set operations between solids, or surfaces ray casting display. We present an object centered, information preserving, hierarchial representation for polyhedra called ``Prism Tree''. We use the representation to decompose the intersection algorithms into two steps: the ``localization'' of intersections, and their {\it processing''. When dealing with polyhedra with many faces (typically more than one thousand), the first step is by far the most expensive. The ``Prism Tree'' structure is used to compute efficiently this localization step. A preliminary implementation of the set operations and ray casting algorithims has been constructed. %Y cost: $2.25 %A J.L.Marroquin %T Optimal Bayesian Estimators For Image Segmentation and Surface Reconstruction %R AI Memo 839 %I Artificial Intelligence Laboratory, Massachusetts Institute of Technology %K mit aim ail %I Artificial Intelligence Laboratory, Massachusetts Institute of Technology %D April 1985 %P 17 %K mit aim ail %K Bayesian estimation, Markov random fields, image segmentation, surface reconstruction, image restoration. %X A very fruitful approach to the solution of image segmentation and surface reconstruction tasks is their formulation as estimation problems via the use of Markov random field models and Bayes theory. However, the Maximuma Posteriori (MAP) estimate, which is the one most frequently used, is suboptimal in these cases. We show that for segmentation problems the optimal Bayesian estimator is the maximizer of the posterior marginals, while for reconstruction tasks, the threshold posterior mean has the best possible performance. We present efficient distributed algorithms for approximating these estimates in the general case. Based on these results, we develop a maximum likelihood that leads to a parameter-free distributed algorithm for restoring piecewise constant images. To illustrate these ideas, the reconstruction of binary patterns is discussed in detail. %Y cost: $1.50 %A Whitman Richards %A Jan J. Koenderink %A D.D. Hoffman %T Inferring 3D Shapes from 2D Codons %R AI Memo 840 %I Artificial Intelligence Laboratory, Massachusetts Institute of Technology %K mit aim ail %I Artificial Intelligence Laboratory, Massachusetts Institute of Technology %D April 1985 %P 19 %K mit aim ail %K vision, recognition, visual representation, object perception, figure-ground, 3-D shape %X All plane curves can be described at an abstract level by a sequence of five primitive elemental shapes, called "codons", which capture the sequential relations between the singular points of curvature. The codon description provides a basis for enumerating all smooth 2D curves. Let each of these smooth plane curves be considered as the silhouette of an opaque object. Clearly an infinity of 3D objects can generate any one of our "codon" silhouettes. How then can we predict which 3D object corresponds to a given 2D silhouette? To restrict the infinity of choices, we impose three math- matical properties of smooth surfaces plus one simple viewing constraint. The constraint is an extension of the notion of general position, and seems to drive our preferred inferences of 3D shapes, given only the 2D contour. %Y cost: $1.50 %A W. Eric L. Grimson and Tomas Lozano-Perez %T Recognition and Localization of Overlapping Parts From Sparse Data %R AI Memo 841 %I Artificial Intelligence Laboratory, Massachusetts Institute of Technology %K mit aim ail %I Artificial Intelligence Laboratory, Massachusetts Institute of Technology %D June 1985 %P 41 %K mit aim ail %K object recognition, sensor interpretations %X This paper discusses how sparse local measurements of positions and surface normals may be used to identify and locate overlapping objects. The objects are modeled as polyhedra (or polygons) having up to six degrees of positional freedom relative to the sensors. The approach operates by examining all hypotheses about pairings between sensed data and object surfaces and efficiently discarding inconsistent ones by using local constraints on: distances between faces, angles between face normals, and angles (relative to the surface normals) of vectors between sensed points. The method described here is an extension of a method for recognition and localization of non-overlapping parts previously described in [Grimson and Lozano-Perez 84] and [Gaston and Lozano-Perez 84]. %Y cost: $2.50, also available as NTIS report AD-A158394 %A Tomas Lozano-Perez and Rodney A. Brooks %T An Approach To Automatic Robot Programming %R AI Memo 842 %I Artificial Intelligence Laboratory, Massachusetts Institute of Technology %K mit aim ail %I Artificial Intelligence Laboratory, Massachusetts Institute of Technology %D April 1985 %P 35 %K mit aim ail %K robotics, task planning, robot programming %X In this paper we propose an architecture for a new task level system, which we call TWAIN. Task-level programming attempts to simplify the robot programming process by requiring that the user specify only goals for the physical relationships among objects, rather than the motions needed to achieve those goals. A task-level specification is meant to be completely robot independent; no positions or paths that depend on the robot geometry or kinematics are specified by the user. We have two goals for this paper. The first is to present a more unified treatment of some individual pieces of research in task planning, whose relationship has not previously been described. The second is to provide a new framework for further research in task-planning. This is a slightly modified version of a paper that appeared in ``Proceedings of Solid Modeling by Computers: From Theory to Applications'', Research Laboratories Symposium Series, sponsored by General Motors, Warren, MI, September, 1983. %Y cost: $2.25, also available as NTIS report AD-A161120 %A Norberto M. Grzywacz %A Ellen C. Hildreth %T The Incremental Rigidity Scheme for Recovering Structure from Motion: Position vs. Velocity Based Formulations %R AI Memo 845 %I Artificial Intelligence Laboratory, Massachusetts Institute of Technology %K mit aim ail %I Artificial Intelligence Laboratory, Massachusetts Institute of Technology %D October 1985 %P 53 %K mit aim ail %K motion analysis, structure from motion, image analysis, 3-d analysis, velocity field, rigidity assumption. %X Perceptual studies suggest that the visual system uses the "rigidity" assumption to recover three-dimensional structure from motion. Ullman (1984) recently proposed a computational scheme, the ``incremental rigidity scheme'', which uses the rigidity assumption to recover the structure of rigid and non-rigid objects in motion. The scheme assumes the input to be discrete positions of elements in motion, under orthographic projection. We present formulations of Ullman's method that use velocity information and perspective projection in the recovery of structure. Theoretical and computer analysis show that the velocity based formulations provide a rough estimate of structure quickly, but are not robust over an extended time period. The stable long term recovery of structure requires disparate views of moving objects. Our analysis raises interesting questions regarding the recovery of structure from motion in the human visual system. %Y cost: $2.75 %A Ellen C. Hildreth %A John M. Hollerbach %T The Computational Approach to Vision and Motor Control %R AI Memo 846 %I Artificial Intelligence Laboratory, Massachusetts Institute of Technology %K mit aim ail %I Artificial Intelligence Laboratory, Massachusetts Institute of Technology %D August 1985 %P 84 %K mit aim ail %K vision, robotics, motor control, natural computation, computational approach, artificial intelligence %O also as C.B.I.P. Memo 014 %X Over the past decade, it has become increasingly clear that to understand the brain, we must study not only its biochemical and biophysical mechanisms and its outward perceptual and physical behavior. We must also study the brain at a theoretical level that investigates the ``computations'' that are necessary to perform its functions. The control of movements such as reaching, grasping and manipulating objects requires complex mechanisms that elaborate information from many sensors and control the forces generated by a large number of muscles. The act of seeing, which intuitively seems so simple and effortless, requires information processing whose complexity we are just beginning to grasp. A ``computational approach'' to the study of vision and motor control has evolved within the field of Artificial Intelligence, which inquires directly into the nature of the information processing that is required to perform complex visual and motor tasks. This paper discusses a particular view of the computational approach and its relevance to experimental neuroscience. %Y cost: $3.00 %A Hal Abelson %A Norman Adams %A David Bartly %A Gary Brooks %A Dan Friedman %A Robert Halstead %A Chris Hanson %A Chris Haynes, %A Eugene Kohlbecker %A Don Oxley %A Kent Pitman %A Jonathan Rees %A Bill Rozas %A Gerald Jay Sussman %A Mitchell Wand %T The Revised Revised Report on Scheme or The Uncommon Lisp %E William Clinger %R AI Memo 848 %I Artificial Intelligence Laboratory, Massachusetts Institute of Technology %K mit aim ail %I Artificial Intelligence Laboratory, Massachusetts Institute of Technology %D August 1985 %P 76 %K mit aim ail %K SCHEME, LISP, functional programming, computer languages %O See Indiana University Computer Science Department, Technical Report 174, June, 1985 %X Data and procedures and the values they amass, Higher order functions to combine and mix and match, Objects with their local state, the messages they pass, A property, a package, the control point for a catch- In the Lambda Order they are all first-class. One Thing to name them all, One Thing to define them, One Thing to place them in environments and bind them, In the Lambda Order they are all first-class. %Y cost: $6.00 %A John M. Hollerbach %A Christopher G. Atkeson %T Characterization of Joint-Interpolated Arm Movements %R AI Memo 849 %I Artificial Intelligence Laboratory, Massachusetts Institute of Technology %K mit aim ail %I Artificial Intelligence Laboratory, Massachusetts Institute of Technology %D June,1985 %P 19 %K mit aim ail %K arm control, kinematics, trajectory planning %X Two possible sets of planning variables for human arm movement are joint angles and hand position. Although one might expect these possibilities to be mutually exclusive, recently an apparently contradictory set of data has appeared that indicates straight-line trajectories in both hand space and joint space at the same time. To assist in distinguishing between these viewpoints applied to the same data, we have theoretically characterized the set of trajectories derivable from a joint based planning strategy and have compared them to experimental measurements. We conclude that the apparent straight lines in joint space happen to be artifacts of movement kinematics near the workspace boundary. %Y cost: $1.50 %A Ellen C. Hildreth %T Edge Detection %R AI Memo 858 %I Artificial Intelligence Laboratory, Massachusetts Institute of Technology %K mit aim ail %I Artificial Intelligence Laboratory, Massachusetts Institute of Technology %D September 1985 %P 22 %K mit aim ail %K edge detection, computer vision, image processing, image filtering, intensity changes, Gaussian filtering, multi-resolution image analysis, zero crossings %X For both biological systems and machines, vision begins with a large and unwieldy array of measurements of the amount of light reflected from surfaces in the environment. The goal of vision is to recover physical properties of objects in the scene, such as the location of object boundaries and the structure, color and texture of object surfaces, from the two-dimensional image that is projected onto the eye or camera. This goal is not achieved in a single step; vision proceeds in stages, with each stage producing increasingly more useful descriptions of the image and then the scene. The first clues about the physical properties of the scene are provided by the ``changes of intensity'' in the image. The importance of intensity changes and edges in early visual processing has led to extensive research on their detection, description and use, both in computer and biological vision systems. This article reviews some of the theory that underlies the detection of edges, and the methods used to carry out this analysis. %Y cost: $2.25 %A Shahriar Negahdaripour %T Direct Passive Navigation: Analytical Solutions for Planes and Curved Surfaces %R AI Memo 863 %I Artificial Intelligence Laboratory, Massachusetts Institute of Technology %K mit aim ail %I Artificial Intelligence Laboratory, Massachusetts Institute of Technology %D August 1985 %P 17 %K mit aim ail %K passive navigation, optical flow, structure and motion, planar surfaces, least squares %X In this paper, we derive a closed form solution for recovering the motion of an observer relative to a planar surface directly from image brightness derivatives. We do not compute the optical flow as an intermediate step, only the spatial and temporal intensity gradients at a minimum of 9 points. We solve a linear matrix equation for the elements of a 3X3 matrix whose eigenvalue decomposition is used to compute the motion parameters and plane orientation. We also show how the procedure can be extended to curved surfaces that are locally approximatable by quadratic patches. In this case, a minimum of 18 independent points are required to uniquely determine the elements of two 3X3 matrices that are used to solve for the surface structure and motion parameters. %Y cost: $1.50 %A Rodney A. Brooks %T A Robust Layered Control System For A Mobile Robot %R AI Memo 864 %I Artificial Intelligence Laboratory, Massachusetts Institute of Technology %K mit aim ail %I Artificial Intelligence Laboratory, Massachusetts Institute of Technology %D September 1985 %P 25 %K mit aim ail %K mobile robot, robot control %X We describe a new architecture for controlling mobile robots. Layers of control system are built to let the robot operate at increasing levels of competence. Layers are made up of asynchronous modules which communicate over low bandwidth channels. Each module is an instance of a fairly simple computational machine. Higher level layers can subsume the roles of lower levels by suppressing their outputs. However, lower levels continue to function as higher levels are added. The result is a robust and flexible robot control system. The system is intended to control a robot that wanders the office areas of our laboratory, building maps of its surroundings. In this paper we demonstrate the system controlling a detailed simulation of the robot. %Y cost: $2.25, also available as NTIS report AD-A160833 %A Gul Agha %A Carl Hewitt %T Concurrent Programming Using Actors: Exploiting Large-Scale Parallelism %R AI Memo 865 %I Artificial Intelligence Laboratory, Massachusetts Institute of Technology %K mit aim ail %I Artificial Intelligence Laboratory, Massachusetts Institute of Technology %D October 1985 %P 20 %K mit aim ail %K concurrency, distributed computing, programming languages, object-oriented programming, actors, functional programming, parallel processing, open systems %X We argue that the ability to model shared objects with changing local states, dynamic reconfigurability, and inherent parallelism are desirable properties of any model of concurrency. The ``actor model'' addresses these issues in a uniform framework. This paper briefly describes the concurrent programming language ``Act3'' and the principles that have guided its development. ``Act3'' advances the state of the art in programming languages by combining the advantages of object-oriented programming with those of functional programming. We also discuss considerations relevant to large-scale parallelism in the context of ``open systems'', and define an abstract model which establishes the equivalence of systems defined by actor programs. %Y cost: $1.50, also available as NTIS report AD-A162422 %A Brian C. Williams %T Circumscribing Circumscription: A guide to Relevance and Incompleteness %R AI Memo 868 %I Artificial Intelligence Laboratory, Massachusetts Institute of Technology %K mit aim ail %I Artificial Intelligence Laboratory, Massachusetts Institute of Technology %D October 1985 %P 46 %K mit aim ail %K circumscription,commonsense reasoning,nonmonotonic reasoning, conjectural reasoning, resource limitations, relevance, completeness. %X Intelligent agentsin the physical world must work from incomplete information due to partial knowledge and limited resources. An agent copes with these limitations by applying rules of conjecture to make reasonable assumptions about wahata is known. Circumscription, proposed by McCarthy is the formalization of a particularly important rule of conjecture like- ned to Occam's razor. That is, the set of all objects satisfying a certain property is the smallest set of objects that is consistent with what is known. This paper examines closely the properties and the semantics underlying circumscription, considering both its expressive power and limitations. In addition we study circumscription's relationship to several related formalisms, such as negation by failure, the closed world assumption default reasoning and Planner's THNOT. In the discussion a number of ex- tensions to circumscription are proposed,allowing one to tightly focus its scope of applicability. In addition, several new rules of conjecture are proposed based on the notions of revelance and minimality. Finally, a synthesis between the approaches of McCarthy and Konoglie is used to extend circumscription, as well as several other rules of conjecture, to account for resource limitations. %Y cost: $2.75