 |
Technical Reports |  |
Work Products |  |
Historical Collections |  |
CSAIL Digital Archive - Artificial Intelligence
Laboratory Series
AIM-1100 Author[s]: Charles Rich and Richard C. Waters Intelligent Assistance for Program Recognition, Design, Optimization, and Debugging January 1989 ftp://publications.ai.mit.edu/ai-publications/1000-1499/AIM-1100.ps ftp://publications.ai.mit.edu/ai-publications/pdf/AIM-1100.pdf A recognition assistant will help reconstruct the design of a program, given only its source code. A design assistant will assist a programmer by detecting errors and inconsistencies in his design choices and by automatically making many straightforward implementation decisions. An optimization assistant will help improve the performance of programs by identifying intermediate results that can be reused. A debugging assistant will aid in the detection, localization, and repair of errors in designs as well as completed programs.
AIM-1101 Author[s]: Thomas F. Knight, Jr. and Patrick G. Sobalvarro Routing Statistics for Unqueued Banyan Networks September 1990 ftp://publications.ai.mit.edu/ai-publications/1000-1499/AIM-1101.ps ftp://publications.ai.mit.edu/ai-publications/pdf/AIM-1101.pdf Banyan networks comprise a large class of networks that have been used for interconnection in large-scale multiprocessors and telephone switching systems. Regular variants of Banyan networks, such as delta and butterfly networks, have been used in multiprocessors such as the IBM RP3 and the BBN Butterfly. Analysis of the performance of Banyan networks has typically focused on these regular variants. We present a methodology for performance analysis of unbuffered Banyan multistage interconnection networks. The methodology has two novel features: it allows analysis of networks where some inputs are more likely to be active than others, and allows analysis of Banyan networks of arbitrary topology.
AIM-1102A Author[s]: Richard C. Waters XP. A Common Lisp Pretty Printing System August 1989 ftp://publications.ai.mit.edu/ai-publications/1000-1499/AIM-1102a.ps ftp://publications.ai.mit.edu/ai-publications/pdf/AIM-1102a.pdf XP provides efficient and flexible support for pretty printing in Common Lisp. Its single greatest advantage is that it allows the full benefits of pretty printing to be obtained when printing data structures, as well as when printing program code. XP is efficient, because it is based on a linear time algorithm that uses a small fixed amount of storage. XP is flexible, because users can control the exact form of the output via a set of special format directives. XP can operate on arbitrary data structures, because facilities are provided for specifying pretty printing methods for any type of object.
AIM-1102 Author[s]: Richard C. Waters XP. A Common Lisp Pretty Printing System March 1989 ftp://publications.ai.mit.edu/ai-publications/1000-1499/AIM-1102.ps ftp://publications.ai.mit.edu/ai-publications/pdf/AIM-1102.pdf XP provides efficient and flexible support for pretty printing in Common Lisp. Its single greatest advantage is that it allows the full benefits of pretty printing to be obtained when printing data structures, as well as when printing program code. XP is efficient, because it is based on a linear time algorithm that uses only a small fixed amount of storage. XP is flexible, because users can control the exact form of the output via a set of special format directives. XP can operate on arbitrary data structures, because facilities are provided for specifying pretty printing methods for any type of object. XP also modifies the way abbreviation based on length, nesting depth, and circularity is supported so that they automatically apply to user-defined functions that perform output – e.g., print functions for structures. In addition, a new abbreviation mechanism is introduced that can be used to limit the total numbers of lines printed.
AITR-1103 Author[s]: Henry M. Wu Performance Evaluation of the Scheme 86 and HP Precision Architecture April 1989 ftp://publications.ai.mit.edu/ai-publications/1000-1499/AITR-1103.ps ftp://publications.ai.mit.edu/ai-publications/pdf/AITR-1103.pdf The Scheme86 and the HP Precision Architectures represent different trends in computer processor design. The former uses wide micro-instructions, parallel hardware, and a low latency memory interface. The latter encourages pipelined implementation and visible interlocks. To compare the merits of these approaches, algorithms frequently encountered in numerical and symbolic computation were hand-coded for each architecture. Timings were done in simulators and the results were evaluated to determine the speed of each design. Based on these measurements, conclusions were drawn as to which aspects of each architecture are suitable for a high- performance computer.
AIM-1105 Author[s]: Berthold K.P. Horn Height and Gradient from Shading May 1989 ftp://publications.ai.mit.edu/ai-publications/1000-1499/AIM-1105.ps ftp://publications.ai.mit.edu/ai-publications/pdf/AIM-1105.pdf The method described here for recovering the shape of a surface from a shaded image can deal with complex, wrinkled surfaces. Integrability can be enforced easily because both surface height and gradient are represented. The robustness of the method stems in part from linearization of the reflectance map about the current estimate of the surface orientation at each picture cell. The new scheme can find an exact solution of a given shape-from-shading problem even though a regularizing term is included. This is a reflection of the fact that shape-from- shading problems are not ill-posed when boundary conditions are available or when the image contains singular points.
AIM-1106 Author[s]: Jeff Palmucci, Carl Waldsburger, David Duis and Paul Krause Experience with Acore: Implementing GHC with Actors August 1990 ftp://publications.ai.mit.edu/ai-publications/1000-1499/AIM-1106.ps ftp://publications.ai.mit.edu/ai-publications/pdf/AIM-1106.pdf This paper presents a concurrent interpreter for a general-purpose concurrent logic programming language, Guarded Horn Clauses (GHC). Unlike typical implementations of GHC in logic programming languages, the interpreter is implemented in the Actor language Acore. The primary motivation for this work was to probe the strengths and weaknesses of Acore as a platform for developing sophisticated programs. The GHC interpreter provided a rich testbed for exploring Actor programming methodology. The interpreter is a pedagogical investigation of the mapping of GHC constructs onto the Actor model. Since we opted for simplicity over optimization, the interpreter is somewhat inefficient.
AIM-1108 Author[s]: Thomas M. Breuel Indexing for Visual Recognition from a Large Model Base August 1990 ftp://publications.ai.mit.edu/ai-publications/1000-1499/AIM-1108.ps ftp://publications.ai.mit.edu/ai-publications/pdf/AIM-1108.pdf This paper describes a new approach to the model base indexing stage of visual object recognition. Fast model base indexing of 3D objects is achieved by accessing a database of encoded 2D views of the objects using a fast 2D matching algorithm. The algorithm is specifically intended as a plausible solution for the problem of indexing into very large model bases that general purpose vision systems and robots will have to deal with in the future. Other properties that make the indexing algorithm attractive are that it can take advantage of most geometric and non- geometric properties of features without modification, and that it addresses the incremental model acquisition problem for 3D objects.
AITR-1109 Author[s]: Jeremy M. Wertheimer Derivation of an Efficient Rule System Pattern Matcher February 1989 ftp://publications.ai.mit.edu/ai-publications/1000-1499/AITR-1109.ps ftp://publications.ai.mit.edu/ai-publications/pdf/AITR-1109.pdf Formalizing algorithm derivations is a necessary prerequisite for developing automated algorithm design systems. This report describes a derivation of an algorithm for incrementally matching conjunctive patterns against a growing database. This algorithm, which is modeled on the Rete matcher used in the OPS5 production system, forms a basis for efficiently implementing a rule system. The highlights of this derivation are: (1) a formal specification for the rule system matching problem, (2) derivation of an algorithm for this task using a lattice-theoretic model of conjunctive and disjunctive variable substitutions, and (3) optimization of this algorithm, using finite differencing, for incrementally processing new data.
AIM-1110 Author[s]: W. Eric L. Grimson and Daniel P. Huttenlocher On the Verification of Hypothesized Matches in Model-Based Recognition May 1989 ftp://publications.ai.mit.edu/ai-publications/1000-1499/AIM-1110.ps ftp://publications.ai.mit.edu/ai-publications/pdf/AIM-1110.pdf In model-based recognition, ad hoc techniques are used to decide if a match of data to model is correct. Generally an empirically determined threshold is placed on the fraction of model features that must be matched. We rigorously derive conditions under which to accept a match, relating the probability of a random match to the fraction of model features accounted for, as a function of the number of model features, number of image features and the sensor noise. We analyze some existing recognition systems and show that our method yields results comparable with experimental data.
AIM-1111 Author[s]: W. Eric L. Grimson The Combinatorics of Heuristic Search Termination for Object Recognition in Cluttered Environments May 1989 ftp://publications.ai.mit.edu/ai-publications/1000-1499/AIM-1111.ps ftp://publications.ai.mit.edu/ai-publications/pdf/AIM-1111.pdf Many recognition systems use constrained search to locate objects in cluttered environments. Earlier analysis showed that the expected search is quadratic in the number of model and data features, if all the data comes from one object, but is exponential when spurious data is included. To overcome this, many methods terminate search once an interpretation that is "good enough" is found. We formally examine the combinatorics of this, showing that correct termination procedures dramatically reduce search. We provide conditions on the object model and the scene clutter such that the expected search is quartic. These results are shown to agree with empirical data for cluttered object recognition.
AITR-1112 Author[s]: Richard P. Wildes On Interpreting Stereo Disparity February 1989 ftp://publications.ai.mit.edu/ai-publications/1000-1499/AITR-1112.ps ftp://publications.ai.mit.edu/ai-publications/pdf/AITR-1112.pdf The problems under consideration center around the interpretation of binocular stereo disparity. In particular, the goal is to establish a set of mappings from stereo disparity to corresponding three-dimensional scene geometry. An analysis has been developed that shows how disparity information can be interpreted in terms of three-dimensional scene properties, such as surface depth, discontinuities, and orientation. These theoretical developments have been embodied in a set of computer algorithms for the recovery of scene geometry from input stereo disparity. The results of applying these algorithms to several disparity maps are presented. Comparisons are made to the interpretation of stereo disparity by biological systems.
AITR-1113 Author[s]: Karen Beth Sarachik Visual Navigation: Constructing and Utilizing Simple Maps of an Indoor Environment March 1989 ftp://publications.ai.mit.edu/ai-publications/1000-1499/AITR-1113.ps ftp://publications.ai.mit.edu/ai-publications/pdf/AITR-1113.pdf The goal of this work is to navigate through an office environmentsusing only visual information gathered from four cameras placed onboard a mobile robot. The method is insensitive to physical changes within the room it is inspecting, such as moving objects. Forward and rotational motion vision are used to find doors and rooms, and these can be used to build topological maps. The map is built without the use of odometry or trajectory integration. The long term goal of the project described here is for the robot to build simple maps of its environment and to localize itself within this framework.
AIM-1114 Author[s]: Davi Geiger and Federico Girosi Parallel and Deterministic Algorithms for MRFs: Surface Reconstruction and Integration May 1989 ftp://publications.ai.mit.edu/ai-publications/1000-1499/AIM-1114.ps ftp://publications.ai.mit.edu/ai-publications/pdf/AIM-1114.pdf In recent years many researchers have investigated the use of Markov random fields (MRFs) for computer vision. The computational complexity of the implementation has been a drawback of MRFs. In this paper we derive deterministic approximations to MRFs models. All the theoretical results are obtained in the framework of the mean field theory from statistical mechanics. Because we use MRFs models the mean field equations lead to parallel and iterative algorithms. One of the considered models for image reconstruction is shown to give in a natural way the graduate non-convexity algorithm proposed by Blake and Zisserman.
AIM-1115 Author[s]: Andrew Christian Design Considerations for an Earth-Based Flexible Robotic System March 1989 ftp://publications.ai.mit.edu/ai-publications/1000-1499/AIM-1115.ps ftp://publications.ai.mit.edu/ai-publications/pdf/AIM-1115.pdf This paper provides insights into the problems of designing a robot with joint and link flexibility. The relationship between the deflection of the robot under gravity is correlated with the fundamental frequency of vibration. We consider different types of link geometry and evaluate the flexibility potential of different materials. Some general conclusions and guidelines for constructing a flexible robot are given.
AITR-1117 Author[s]: Bror V. H. Saxberg A Modern Differential Geometric Approach to Shape from Shading June 1989 ftp://publications.ai.mit.edu/ai-publications/1000-1499/AITR-1117.ps ftp://publications.ai.mit.edu/ai-publications/pdf/AITR-1117.pdf How the visual system extracts shape information from a single grey-level image can be approached by examining how the information about shape is contained in the image. This technical report considers the characteristic equations derived by Horn as a dynamical system. Certain image critical points generate dynamical system critical points. The stable and unstable manifolds of these critical points correspond to convex and concave solution surfaces, giving more general existence and uniqueness results. A new kind of highly parallel, robust shape from shading algorithm is suggested on neighborhoods of these critical points. The information at bounding contours in the image is also analyzed.
AIM-1118 Author[s]: Michael D. Monegan An Object-Oriented Software Reuse Tool April 1989 ftp://publications.ai.mit.edu/ai-publications/1000-1499/AIM-1118.ps ftp://publications.ai.mit.edu/ai-publications/pdf/AIM-1118.pdf The Object-oriented Reuse Tool (ORT) supports the reuse of object-oriented software by maintaining a library of reusable classes and recording information about their reusability as well as information associated with their design and verification. In the early design phases of object-oriented development, ORT facilitates reuse by providing a flexible way to navigate the library, thereby aiding in the process of refining a design to maximally reuse existing classes. A collection of extensions to ORT have also been identified. These extensions would compose the remainder of a system useful in increasing reuse in object-oriented software production.
AIM-1119 Author[s]: Henry M. Wu A Multiprocessor Architecture Using Modular Arithmetic for Very High Precision Computation April 1989 ftp://publications.ai.mit.edu/ai-publications/1000-1499/AIM-1119.ps ftp://publications.ai.mit.edu/ai-publications/pdf/AIM-1119.pdf We outline a multiprocessor architecture that uses modular arithmetic to implement numerical computation with 900 bits of intermediate precision. A proposed prototype, to be implemented with off-the-shelf parts, will perform high-precision arithmetic as fast as some workstations and mini- computers can perform IEEE double-precision arithmetic. We discuss how the structure of modular arithmetic conveniently maps into a simple, pipelined multiprocessor architecture. We present techniques we developed to overcome a few classical drawbacks of modular arithmetic. Our architecture is suitable to and essential for the study of chaotic dynamical systems.
AIM-1120 Author[s]: Anita M. Flynn, Rodney A. Brooks, William M. Wells III and David S. Barrett SQUIRT: The Prototypical Mobile Robot for Autonomous Graduate Students July 1989 ftp://publications.ai.mit.edu/ai-publications/1000-1499/AIM-1120.ps ftp://publications.ai.mit.edu/ai-publications/pdf/AIM-1120.pdf This paper describes an exercise in building a complete robot aimed at being as small as possible but using off-the-shelf components exclusively. The result is an autonomous mobile robot slightly larger than one cubic inch which incorporates sensing, actuation, onboard computation, and onboard power supplies. Nicknamed Squirt, this robot acts as a 'bug', hiding in dark corners and venturing out in the direction of last heard noises, only moving after the noises are long gone.
AIM-1122 Author[s]: Michael R. Brent Causal/Temporal Connectives: Syntax and Lexicon September 1989 ftp://publications.ai.mit.edu/ai-publications/1000-1499/AIM-1122.ps ftp://publications.ai.mit.edu/ai-publications/pdf/AIM-1122.pdf This report elucidates the linguistic representation of temporal relations among events. This involves examining sentences that contain two clauses connected by words like once, by the time, when, and before. Specifically, the effect of the tenses of the connected clauses on the acceptability of sentences are examined. For example, Rachel disappeared once Jon had fallen asleep is fine, but *Rachel had disappeared once Jon fell asleep is unacceptable. A theory of acceptability is developed and its implications for interpretation discussed. Factoring of the linguisitic knowledge into a general, syntactic component and a lexical component clarifies the interpretation problem. Finally, a computer model of the theory is demonstrated.
AITR-1125 Author[s]: Michelle Kwok Lee Summarizing Qualitative Behavior from Measurements of NonlinearsCircuits May 1989 ftp://publications.ai.mit.edu/ai-publications/1000-1499/AITR-1125.ps ftp://publications.ai.mit.edu/ai-publications/pdf/AITR-1125.pdf This report describes a program which automatically characterizes the behavior of any driven, nonlinear, electrical circuit. To do this, the program autonomously selects interesting input parameters, drives the circuit, measures its response, performs a set of numeric computations on the measured data, interprets the results, and decomposes the circuit's parameter space into regions of qualitatively distinct behavior. The output is a two-dimensional portrait summarizing the high-level, qualitative behavior of the circuit for every point in the graph, an accompanying textual explanation describing any interesting patterns observed in the diagram, and a symbolic description of the circuit's behavior which can be passed on to other programs for further analysis.
AIM-1126 Author[s]: Anita M. Flynn, Rodney A. Brooks and Lee S. Tavrow Twilight Zones and Cornerstones: A Gnat Robot Double Feature July 1989 ftp://publications.ai.mit.edu/ai-publications/1000-1499/AIM-1126.ps ftp://publications.ai.mit.edu/ai-publications/pdf/AIM-1126.pdf We want to build tiny gnat-sized robots, a millimeter or two in diameter. They will be cheap, disposable, totally self-contained autonomous agents able to do useful things in the world. This paper consists of two parts. The first describes why we want to build them. The second is a technical outline of how to go about it. Gnat robots are going to change the world.
AITR-1128 Author[s]: Jeffrey Van Baalen Toward a Theory of Representation Design May 1989 ftp://publications.ai.mit.edu/ai-publications/1000-1499/AITR-1128.ps ftp://publications.ai.mit.edu/ai-publications/pdf/AITR-1128.pdf This research is concerned with designing representations for analytical reasoning problems (of the sort found on the GRE and LSAT). These problems test the ability to draw logical conclusions. A computer program was developed that takes as input a straightforward predicate calculus translation of a problem, requests additional information if necessary, decides what to represent and how, designs representations capturing the constraints of the problem, and creates and executes a LISP program that uses those representations to produce a solution. Even though these problems are typically difficult for theorem provers to solve, the LISP program that uses the designed representations is very efficient.
AIM-1131 Author[s]: Daphna Weinshall Direct Computation of 3D Shape Invariants and the Focus of Expansion May 1989 ftp://publications.ai.mit.edu/ai-publications/1000-1499/AIM-1131.ps ftp://publications.ai.mit.edu/ai-publications/pdf/AIM-1131.pdf Structure from motion often refers to the computation of 3D structure from a matched sequence of images. However, a depth map of a surface is difficult to compute and may not be a good representation for storage and recognition. Given matched images, I will first show that the sign of the normal curvature in a given direction at a given point in the image can be computed from a simple difference of slopes of line-segments in one image. Using this result, local surface patches can be classified as convex, concave, parabolic (cylindrical), hyperbolic (saddle point) or planar. At the same time the translational component of the optical flow is obtained, from which the focus of expansion can be computed.
AITR-1132 Author[s]: Todd A. Cass Robust 2-D Model-Based Object Recognition May 1988 ftp://publications.ai.mit.edu/ai-publications/1000-1499/AITR-1132.ps ftp://publications.ai.mit.edu/ai-publications/pdf/AITR-1132.pdf Techniques, suitable for parallel implementation, for robust 2D model-based object recognition in the presence of sensor error are studied. Models and scene data are represented as local geometric features and robust hypothesis of feature matchings and transformations is considered. Bounds on the error in the image feature geometry are assumed constraining possible matchings and transformations. Transformation sampling is introduced as a simple, robust, polynomial-time, and highly parallel method of searching the space of transformations to hypothesize feature matchings. Key to the approach is that error in image feature measurement is explicitly accounted for. A Connection Machine implementation and experiments on real images are presented.
AIM-1133 Author[s]: Todd Anthony Cass Feature Matching for Object Localization in the Presence of Uncertainty May 1990 ftp://publications.ai.mit.edu/ai-publications/1000-1499/AIM-1133.ps ftp://publications.ai.mit.edu/ai-publications/pdf/AIM-1133.pdf We consider the problem of matching model and sensory data features in the presence of geometric uncertainty, for the purpose of object localization and identification. The problem is to construct sets of model feature and sensory data feature pairs that are geometrically consistent given that there is uncertainty in the geometry of the sensory data features. If there is no geometric uncertainty, polynomial-time algorithms are possible for feature matching, yet these approaches can fail when there is uncertainty in the geometry of data features. Existing matching and recognition techniques which account for the geometric uncertainty in features either cannot guarantee finding a correct solution, or can construct geometrically consistent sets of feature pairs yet have worst case exponential complexity in terms of the number of features. The major new contribution of this work is to demonstrate a polynomial-time algorithm for constructing sets of geometrically consistent feature pairs given uncertainty in the geometry of the data features. We show that under a certain model of geometric uncertainty the feature matching problem in the presence of uncertainty is of polynomial complexity. This has important theoretical implications by demonstrating an upper bound on the complexity of the matching problem, an by offering insight into the nature of the matching problem itself. These insights prove useful in the solution to the matching problem in higher dimensional cases as well, such as matching three-dimensional models to either two or three-dimensional sensory data. The approach is based on an analysis of the space of feasible transformation parameters. This paper outlines the mathematical basis for the method, and describes the implementation of an algorithm for the procedure. Experiments demonstrating the method are reported.
AIM-1134 Author[s]: David McAllester and Robert Givan Taxonomic Syntax for First-Order Inference June 1989 ftp://publications.ai.mit.edu/ai-publications/1000-1499/AIM-1134.ps ftp://publications.ai.mit.edu/ai-publications/pdf/AIM-1134.pdf Most knowledge representation languages are based on classes and taxonomic relationships between classes. Taxonomic hierarchies without defaults or exceptions are semantically equivalent to a collection of formulas in first order predicate calculus. Although designers of knowledge representation languages often express an intuitive feeling that there must be some advantage to representing facts as taxonomic relationships rather than first order formulas, there are few, if any, technical results supporting this intuition. We attempt to remedy this situation by presenting a taxonomic syntax for first order predicate calculus and a series of theorems that support the claim that taxonomic syntax is superior to classical syntax.
AIM-1136 Author[s]: Thomas Marill Computer Perception of Three-Dimensional Objects August 1989 ftp://publications.ai.mit.edu/ai-publications/1000-1499/AIM-1136.ps ftp://publications.ai.mit.edu/ai-publications/pdf/AIM-1136.pdf We first pose the following problem: to develop a program which takes line-drawings as input and constructs three-dimensional objects as output, such that the output objects are the same as the ones we see when we look at the input line-drawing. We then introduce the principle of minimum standard- deviation of angles (MSDA) and discuss a program based on MSDA. We present the results of testing this program with a variety of line- drawings and show that the program constitutes a solution to the stated problem over the range of line-drawings tested. Finally, we relate this work to its historical antecedents in the psychological and computer-vision literature.
AIM-1137 Author[s]: J. Brian Subirana-Vilanova Curved Inertia Frames: Visual Attention and Perceptual Organization Using Convexity and Symmetry October 1991 ftp://publications.ai.mit.edu/ai-publications/1000-1499/AIM-1137.ps ftp://publications.ai.mit.edu/ai-publications/pdf/AIM-1137.pdf In this paper we present an approach to perceptual organization and attention based on Curved Inertia Frames (C.I.F.), a novel definition of "curved axis of inertia'' tolerant to noisy and spurious data. The definition is useful because it can find frames that correspond to large, smooth, convex, symmetric and central parts. It is novel because it is global and can detect curved axes. We discuss briefly the relation to human perception, the recognition of non-rigid objects, shape description, and extensions to finding "features", inside/outside relations, and long- smooth ridges in arbitrary surfaces.
AIM-1138 Author[s]: Shimon Edelman, Heinrich Bulthoff and Daphna Weinshall Stimulus Familiarity Determines Recognition Strategy for Novel 3-D Objects July 1989 ftp://publications.ai.mit.edu/ai-publications/1000-1499/AIM-1138.ps ftp://publications.ai.mit.edu/ai-publications/pdf/AIM-1138.pdf We describe a psychophysical investigation of the effects of object complexity and familiarity on the variation of recognition time and recognition accuracy over different views of novel 3D objects. Our findings indicate that with practice the response times for different views become more uniform and the initially orderly dependency of the response time on the distance to a "good" view disappears. One possible interpretation of our results is in terms of a tradeoff between memory needed for storing specific-view representations of objects and time spent in recognizing the objects.
AITR-1139 Author[s]: Jason Nieh Using Special-Purpose Computing to Examine Chaotic Behavior in Nonlinear Mappings September 1989 ftp://publications.ai.mit.edu/ai-publications/1000-1499/AITR-1139.ps ftp://publications.ai.mit.edu/ai-publications/pdf/AITR-1139.pdf Studying chaotic behavior in nonlinear systems requires numerous computations in order to simulate the behavior of such systems. The Standard Map Machine was designed and implemented as a special computer for performing these intensive computations with high-speed and high- precision. Its impressive performance is due to its simple architecture specialized to the numerical computations required of nonlinear systems. This report discusses the design and implementation of the Standard Map Machine and its use in the study of nonlinear mappings; in particular, the study of the standard map.
AIM-1140 Author[s]: Tomaso Poggio and Federico Girosi A Theory of Networks for Appxoimation and Learning July 1989 ftp://publications.ai.mit.edu/ai-publications/1000-1499/AIM-1140.ps.Z ftp://publications.ai.mit.edu/ai-publications/pdf/AIM-1140.pdf Learning an input-output mapping from a set of examples, of the type that many neural networks have been constructed to perform, can be regarded as synthesizing an approximation of a multi-dimensional function, that is solving the problem of hypersurface reconstruction. From this point of view, this form of learning is closely related to classical approximation techniques, such as generalized splines and regularization theory. This paper considers the problems of an exact representation and, in more detail, of the approximation of linear and nolinear mappings in terms of simpler functions of fewer variables. Kolmogorov's theorem concerning the representation of functions of several variables in terms of functions of one variable turns out to be almost irrelevant in the context of networks for learning. We develop a theoretical framework for approximation based on regularization techniques that leads to a class of three-layer networks that we call Generalized Radial Basis Functions (GRBF), since they are mathematically related to the well-known Radial Basis Functions, mainly used for strict interpolation tasks. GRBF networks are not only equivalent to generalized splines, but are also closely related to pattern recognition methods such as Parzen windows and potential functions and to several neural network algorithms, such as Kanerva's associative memory, backpropagation and Kohonen's topology preserving map. They also have an interesting interpretation in terms of prototypes that are synthesized and optimally combined during the learning stage. The paper introduces several extensions and applications of the technique and discusses intriguing analogies with neurobiological data.
AIM-1141 Author[s]: Ellen C. Hildreth, Norberto M. Grzywacz, Edward H. Adelson and Victor K. Inada The Perceptual Buildup of Three-Dimensional Structure from Motion August 1989 ftp://publications.ai.mit.edu/ai-publications/1000-1499/AIM-1141.ps ftp://publications.ai.mit.edu/ai-publications/pdf/AIM-1141.pdf We present psychophysical experiments that measure the accuracy of perceived 3D structure derived from relative image motion. The experiments are motivated by Ullman's incremental rigidity scheme, which builds up 3D structure incrementally over an extended time. Our main conclusions are: first, the human system derives an accurate model of the relative depths of moving points, even in the presence of noise; second, the accuracy of 3D structure improves with time, eventually reaching a plateau; and third, the 3D structure currently perceived depends on previous 3D models. Through computer simulations, we relate the psychophysical observations to the behavior of Ullman's model.
AITR-1143 Author[s]: W. Kenneth Stewart, Jr. Multisensor Modeling Underwater with Uncertain Information July 1988 ftp://publications.ai.mit.edu/ai-publications/1000-1499/AITR-1143.ps ftp://publications.ai.mit.edu/ai-publications/pdf/AITR-1143.pdf This thesis develops an approach to the construction of multidimensional stochastic models for intelligent systems exploring an underwater environment. It describes methods for building models by a three- dimensional spatial decomposition of stochastic, multisensor feature vectors. New sensor information is incrementally incorporated into the model by stochastic backprojection. Error and ambiguity are explicitly accounted for by blurring a spatial projection of remote sensor data before incorporation. The stochastic models can be used to derive surface maps or other representations of the environment. The methods are demonstrated on data sets from multibeam bathymetric surveying, towed sidescan bathymetry, towed sidescan acoustic imagery, and high-resolution scanning sonar aboard a remotely operated vehicle.
AITR-1144 Author[s]: Andrew A. Berlin A Compilation Strategy for Numerical Programs Based on Partial Evaluation February 1989 ftp://publications.ai.mit.edu/ai-publications/1000-1499/AITR-1144.ps ftp://publications.ai.mit.edu/ai-publications/pdf/AITR-1144.pdf This work demonstrates how partial evaluation can be put to practical use in the domain of high-performance numerical computation. I have developed a technique for performing partial evaluation by using placeholders to propagate intermediate results. For an important class of numerical programs, a compiler based on this technique improves performance by an order of magnitude over conventional compilation techniques. I show that by eliminating inherently sequential data-structure references, partial evaluation exposes the low-level parallelism inherent in a computation. I have implemented several parallel scheduling and analysis programs that study the tradeoffs involved in the design of an architecture that can effectively utilize this parallelism. I present these results using the 9- body gravitational attraction problem as an example.
AIM-1145 Author[s]: Andrew Berlin and Daniel Weise Compiling Scientific Code Using Partial Evaluation July 1989 ftp://publications.ai.mit.edu/ai-publications/1000-1499/AIM-1145.ps ftp://publications.ai.mit.edu/ai-publications/pdf/AIM-1145.pdf Scientists are faced with a dilemma: either they can write abstract programs that express their understanding of a problem, but which do not execute efficiently; or they can write programs that computers can execute efficiently, but which are difficult to write and difficult to understand. We have developed a compiler that uses partial evaluation and scheduling techniques to provide a solution to this dilemma.
AIM-1146 Author[s]: Shimon Edelman and Daphna Weinshall A Self-Organizing Multiple-View Representation of 3D Objects August 1989 ftp://publications.ai.mit.edu/ai-publications/1000-1499/AIM-1146.ps ftp://publications.ai.mit.edu/ai-publications/pdf/AIM-1146.pdf We explore representation of 3D objects in which several distinct 2D views are stored for each object. We demonstrate the ability of a two-layer network of thresholded summation units to support such representations. Using unsupervised Hebbian relaxation, we trained the network to recognise ten objects from different viewpoints. The training process led to the emergence of compact representations of the specific input views. When tested on novel views of the same objects, the network exhibited a substantial generalisation capability. In simulated psychophysical experiments, the network's behavior was qualitatively similar to that of human subjects.
AIM-1148 Author[s]: Anita M. Flynn and Rodney A. Brooks Battling Reality October 1989 ftp://publications.ai.mit.edu/ai-publications/1000-1499/AIM-1148.ps ftp://publications.ai.mit.edu/ai-publications/pdf/AIM-1148.pdf In the four years that the MIT Mobile Robot Project has benn in existence, we have built ten robots that focus research in various areas concerned with building intelligent systems. Towards this end, we have embarked on trying to build useful autonomous creatures that live and work in the real world. Many of the preconceived notions entertained before we started building our robots turned out to be misguided. Some issues we thought would be hard have worked successfully from day one and subsystems we imagined to be trivial have become tremendous time sinks. Oddly enough, one of our biggest failures has led to some of our favorite successes. This paper describes the changing paths our research has taken due to the lessons learned from the practical realities of building robots.
AITR-1151 Author[s]: Jonathan Connell A Colony Architecture for an Artificial Creature September 1989 ftp://publications.ai.mit.edu/ai-publications/1000-1499/AITR-1151.ps ftp://publications.ai.mit.edu/ai-publications/pdf/AITR-1151.pdf This report describes a working autonomous mobile robot whose only goal is to collect and return empty soda cans. It operates in an unmodified office environment occupied by moving people. The robot is controlled by a collection of over 40 independent "behaviors'' distributed over a loosely coupled network of 24 processors. Together this ensemble helps the robot locate cans with its laser rangefinder, collect them with its on-board manipulator, and bring them home using a compass and an array of proximity sensors. We discuss the advantages of using such a multi-agent control system and show how to decompose the required tasks into component activities. We also examine the benefits and limitations of spatially local, stateless, and independent computation by the agents.
AIM-1152 Author[s]: Shimon Ullman and Ronen Basri Recognition by Linear Combinations of Models August 1989 ftp://publications.ai.mit.edu/ai-publications/1000-1499/AIM-1152.ps ftp://publications.ai.mit.edu/ai-publications/pdf/AIM-1152.pdf Visual object recognition requires the matching of an image with a set of models stored in memory. In this paper we propose an approach to recognition in which a 3-D object is represented by the linear combination of 2-D images of the object. If M = {M1,…Mk} is the set of pictures representing a given object, and P is the 2-D image of an object to be recognized, then P is considered an instance of M if P = Eki=aiMi for some constants ai. We show that this approach handles correctly rigid 3-D transformations of objects with sharp as well as smooth boundaries, and can also handle non-rigid transformations. The paper is divided into two parts. In the first part we show that the variety of views depicting the same object under different transformations can often be expressed as the linear combinations of a small number of views. In the second part we suggest how this linear combinatino property may be used in the recognition process.
AITR-1153 Author[s]: Andrew Dean Christian Design and Implementation of a Flexible Robot August 1989 ftp://publications.ai.mit.edu/ai-publications/1000-1499/AITR-1153.ps ftp://publications.ai.mit.edu/ai-publications/pdf/AITR-1153.pdf This robot has low natural frequencies of vibration. Insights into the problems of designing joint and link flexibility are discussed. The robot has three flexible rotary actuators and two flexible, interchangeable links, and is controlled by three independent processors on a VMEbus. Results from experiments on the control of residual vibration for different types of robot motion are presented. Impulse prefiltering and slowly accelerating moves are compared and shown to be effective at reducing residual vibration.
AITR-1154 Author[s]: Anya C. Hurlbert The Computation of Color September 1989 ftp://publications.ai.mit.edu/ai-publications/1000-1499/AITR-1154.ps ftp://publications.ai.mit.edu/ai-publications/pdf/AITR-1154.pdf This thesis takes an interdisciplinary approach to the study of color vision, focussing on the phenomenon of color constancy formulated as a computational problem. The primary contributions of the thesis are (1) the demonstration of a formal framework for lightness algorithms; (2) the derivation of a new lightness algorithm based on regularization theory; (3) the synthesis of an adaptive lightness algorithm using "learning" techniques; (4) the development of an image segmentation algorithm that uses luminance and color information to mark material boundaries; and (5) an experimental investigation into the cues that human observers use to judge the color of the illuminant. Other computational approaches to color are reviewed and some of their links to psychophysics and physiology are explored.
AITR-1155 Author[s]: Michael A. Erdmann On Probabilistic Strategies for Robot Tasks August 1989 ftp://publications.ai.mit.edu/ai-publications/1000-1499/AITR-1155.ps ftp://publications.ai.mit.edu/ai-publications/pdf/AITR-1155.pdf Robots must act purposefully and successfully in an uncertain world. Sensory information is inaccurate or noisy, actions may have a range of effects, and the robot’s environment is only partially and imprecisely modeled. This thesis introduces active randomization by a robot, both in selecting actions to execute and in focusing on sensory information to interpret, as a basic tool for overcoming uncertainty. An example of randomization is given by the strategy of shaking a bin containing a part in order to orient the part in a desired stable state with some high probability. Another example consists of first using reliable sensory information to bring two parts close together, then relying on short random motions to actually mate the two parts, once the part motions lie below the available sensing resolution. Further examples include tapping parts that are tightly wedged, twirling gears before trying to mesh them, and vibrating parts to facilitate a mating operation.
AIM-1156 Author[s]: Sandiway Fong Free Indexation: Combinatorial Analysis and a Compositional Algorithm December 1989 ftp://publications.ai.mit.edu/ai-publications/1000-1499/AIM-1156.ps ftp://publications.ai.mit.edu/ai-publications/pdf/AIM-1156.pdf In the principles-and-parameters model of language, the principle known as "free indexation'' plays an important part in determining the referential properties of elements such as anaphors and pronominals. This paper addresses two issues. (1) We investigate the combinatorics of free indexation. In particular, we show that free indexation must produce an exponential number of referentially distinct structures. (2) We introduce a compositional free indexation algorithm. We prove that the algorithm is "optimal.'' More precisely, by relating the compositional structure of the formulation to the combinatorial analysis, we show that the algorithm enumerates precisely all possible indexings, without duplicates.
AIM-1157 Author[s]: Thomas Marill Recognizing Three-Dimensional Objects without the Use of Models September 1989 ftp://publications.ai.mit.edu/ai-publications/1000-1499/AIM-1157.ps ftp://publications.ai.mit.edu/ai-publications/pdf/AIM-1157.pdf We present an approach to the problem of recognizing three-dimensional objects from line-drawings. In this approach there are no models. The system needs only to be given a single picture of an object; it can then recognize the object in arbitrary orientations.
AIM-1158 Author[s]: Shimon Edelman and Daphna Weinshall Computational Vision: A Critical Review October 1989 ftp://publications.ai.mit.edu/ai-publications/1000-1499/AIM-1158.ps ftp://publications.ai.mit.edu/ai-publications/pdf/AIM-1158.pdf We review the progress made in computational vision, as represented by Marr's approach, in the last fifteen years. First, we briefly outline computational theories developed for low, middle and high-level vision. We then discuss in more detail solutions proposed to three representative problems in vision, each dealing with a different level of visual processing. Finally, we discuss modifications to the currently established computational paradigm that appear to be dictated by the recent developments in vision.
AIM-1160 Author[s]: Bonnie J. Dorr Lexical Conceptual Structure and Generation in Machine Translation June 1989 ftp://publications.ai.mit.edu/ai-publications/1000-1499/AIM-1160.ps ftp://publications.ai.mit.edu/ai-publications/pdf/AIM-1160.pdf This report introduces an implemented scheme for generating target- language sentences using a compositional representation of meaning called lexical conceptual structure. Lexical conceptual structure facilitates two crucial operations associated with generation: lexical selection and syntactic realization. The compositional nature of the representation is particularly valuable for these two operations when semantically equivalent source-and-target-language words and phrases are structurally or thematically divergent. To determine the correct lexical items and syntactic realization associated with the surface form in such cases, the underlying lexical-semantic forms are systematically mapped to the target-language syntactic structures. The model described constitutes a lexical-semantic extension to UNITRAN.
AITR-1161 Author[s]: Lyle J. Borg-Graham Modelling the Somantic Electrical Response of Hippocampal Pyramidal Neurons September 1989 ftp://publications.ai.mit.edu/ai-publications/1000-1499/AITR-1161.ps ftp://publications.ai.mit.edu/ai-publications/pdf/AITR-1161.pdf A modeling study of hippocampal pyramidal neurons is described. This study is based on simulations using HIPPO, a program which simulates the somatic electrical activity of these cells. HIPPO is based on a) descriptions of eleven non-linear conductances that have been either reported for this class of cell in the literature or postulated in the present study, and b) an approximation of the electrotonic structure of the cell that is derived in this thesis, based on data for the linear properties of these cells. HIPPO is used a) to integrate empirical data from a variety of sources on the electrical characteristics of this type of cell, b) to investigate the functional significance of the various elements that underly the electrical behavior, and c) to provide a tool for the electrophysiologist to supplement direct observation of these cells and provide a method of testing speculations regarding parameters that are not accessible.
AITR-1162 Author[s]: Jean-Pierre Schott Three-Dimensional Motion Estimation Using Shading Information in Multiple Frames September 1989 ftp://publications.ai.mit.edu/ai-publications/1000-1499/AITR-1162.ps ftp://publications.ai.mit.edu/ai-publications/pdf/AITR-1162.pdf A new formulation for recovering the structure and motion parameters of a moving patch using both motion and shading information is presented. It is based on a new differential constraint equation (FICE) that links the spatiotemporal gradients of irradiance to the motion and structure parameters and the temporal variations of the surface shading. The FICE separates the contribution to the irradiance spatiotemporal gradients of the gradients due to texture from those due to shading and allows the FICE to be used for textured and textureless surface. The new approach, combining motion and shading information, leads directly to two different contributions: it can compensate for the effects of shading variations in recovering the shape and motion; and it can exploit the shading/illumination effects to recover motion and shape when they cannot be recovered without it. The FICE formulation is also extended to multiple frames.
AITR-1163 Author[s]: Kenneth Man-Kam Yip KAM: Automatic Planning and Interpretation of Numerical Experiments Using Geometrical Methods August 1989 ftp://publications.ai.mit.edu/ai-publications/1000-1499/AITR-1163.ps ftp://publications.ai.mit.edu/ai-publications/pdf/AITR-1163.pdf KAM is a computer program that can automatically plan, monitor, and interpret numerical experiments with Hamiltonian systems with two degrees of freedom. The program has recently helped solve an open problem in hydrodynamics. Unlike other approaches to qualitative reasoning about physical system dynamics, KAM embodies a significant amount of knowledge about nonlinear dynamics. KAM's ability to control numerical experiments arises from the fact that it not only produces pictures for us to see, but also looks at (sic---in its mind's eye) the pictures it draws to guide its own actions. KAM is organized in three semantic levels: orbit recognition, phase space searching, and parameter space searching. Within each level spatial properties and relationships that are not explicitly represented in the initial representation are extracted by applying three operations ---(1) aggregation, (2) partition, and (3) classification--- iteratively.
AIM-1164 Author[s]: Federico Girosi and Tomaso Poggio Networks and the Best Approximation Property October 1989 ftp://publications.ai.mit.edu/ai-publications/1000-1499/AIM-1164.ps.Z ftp://publications.ai.mit.edu/ai-publications/pdf/AIM-1164.pdf Networks can be considered as approximation schemes. Multilayer networks of the backpropagation type can approximate arbitrarily well continuous functions (Cybenko, 1989; Funahashi, 1989; Stinchcombe and White, 1989). We prove that networks derived from regularization theory and including Radial Basis Function (Poggio and Girosi, 1989), have a similar property. From the point of view of approximation theory, however, the property of approximating continous functions arbitrarily well is not sufficient for characterizing good approximation schemes. More critical is the property of best approximation. The main result of this paper is that multilayer networks, of the type used in backpropagation, are not best approximation. For regularization networks (in particular Radial Basis Function networks) we prove existence and uniqueness of best approximation.
AIM-1165 Author[s]: Brian LaMacchia and Jason Nieh The Standard Map Machine September 1989 ftp://publications.ai.mit.edu/ai-publications/1000-1499/AIM-1165.ps ftp://publications.ai.mit.edu/ai-publications/pdf/AIM-1165.pdf We have designed the Standard Map Machine(SMM) as an answer to the intensive computational requirements involved in the study of chaotic behavior in nonlinear systems. The high-speed and high-precision performance of this computer is due to its simple architecture specialized to the numerical computations required of nonlinear systems. In this report, we discuss the design and implementation of this special-purpose machine.
AIM-1166 Author[s]: Bonnie J. Dorr Conceptual Basis of the Lexicon in Machine Translation August 1989 ftp://publications.ai.mit.edu/ai-publications/1000-1499/AIM-1166.ps ftp://publications.ai.mit.edu/ai-publications/pdf/AIM-1166.pdf This report describes the organization and content of lexical information required for the task of machine translation. In particular, the lexical-conceptual basis for UNITRAN, an implemented machine translation system, will be described. UNITRAN uses an underlying form called lexical conceptual structure to perform lexical selection and syntactic realization. Lexical word entries have two levels of description: the first is an underlying lexical-semantic representation that is derived from hierarchically organized primitives, and the second is a mapping from this representation to a corresponding syntactic structure. The interaction of these two levels will be discussed and the lexical selection and syntactic realization processes will be described.
AIM-1167 Author[s]: Tomaso Poggio and Federico Girosi Extensions of a Theory of Networks for Approximation and Learning: Dimensionality Reduction and Clustering April 1990 ftp://publications.ai.mit.edu/ai-publications/1000-1499/AIM-1167.ps ftp://publications.ai.mit.edu/ai-publications/pdf/AIM-1167.pdf The theory developed in Poggio and Girosi (1989) shows the equivalence between regularization and a class of three-layer networks that we call regularization networks or Hyper Basis Functions. These networks are also closely related to the classical Radial Basis Functions used for interpolation tasks and to several pattern recognition and neural network algorithms. In this note, we extend the theory by defining a general form of these networks with two sets of modifiable parameters in addition to the coefficients $c_\ alpha$: moving centers and adjustable norm- weight.
AIM-1168 Author[s]: Tomaso Poggio and Federico Girosi Continuous Stochastic Cellular Automata that Have a Stationary Distribution and No Detailed Balance December 1990 ftp://publications.ai.mit.edu/ai-publications/1000-1499/AIM-1168.ps.Z ftp://publications.ai.mit.edu/ai-publications/pdf/AIM-1168.pdf Marroquin and Ramirez (1990) have recently discovered a class of discrete stochastic cellular automata with Gibbsian invariant measures that have a non-reversible dynamic behavior. Practical applications include more powerful algorithms than the Metropolis algorithm to compute MRF models. In this paper we describe a large class of stochastic dynamical systems that has a Gibbs asymptotic distribution but does not satisfy reversibility. We characterize sufficient properties of a sub-class of stochastic differential equations in terms of the associated Fokker-Planck equation for the existence of an asymptotic probability distribution in the system of coordinates which is given. Practical implications include VLSI analog circuits to compute coupled MRF models.
AITR-1170 Author[s]: Eric Sven Ristad Computational Structure of GPSG Models: Revised Generalized Phrase Structure Grammar September 1989 ftp://publications.ai.mit.edu/ai-publications/1000-1499/AITR-1170.ps ftp://publications.ai.mit.edu/ai-publications/pdf/AITR-1170.pdf The primary goal of this report is to demonstrate how considerations from computational complexity theory can inform grammatical theorizing. To this end, generalized phrase structure grammar (GPSG) linguistic theory is revised so that its power more closely matches the limited ability of an ideal speaker--hearer: GPSG Recognition is EXP-POLY time hard, while Revised GPSG Recognition is NP-complete. A second goal is to provide a theoretical framework within which to better understand the wide range of existing GPSG models, embodied in formal definitions as well as in implemented computer programs. A grammar for English and an informal explanation of the GPSG/RGPSG syntactic features are included in appendices.
AIM-1171 Author[s]: Michael Eisenberg Descriptive Simulation: Combining Symbolic and Numerical Methods in the Analysis of Chemical Reaction Mechanisms September 1989 ftp://publications.ai.mit.edu/ai-publications/1000-1499/AIM-1171.ps ftp://publications.ai.mit.edu/ai-publications/pdf/AIM-1171.pdf The Kineticist's Workbench is a computer program currently under development whose purpose is to help chemists understand, analyze, and simplify complex chemical reaction mechanisms. This paper discusses one module of the program that numerically simulates mechanisms and constructs qualitative descriptions of the simulation results. These descriptions are given in terms that are meaningful to the working chemist (e.g., steady states, stable oscillations, and so on); and the descriptions (as well as the data structures used to construct them) are accessible as input to other programs.
AIM-1173 Author[s]: Ed Gamble A Comparison of Hardware Implementations for Low-Level Vision Algorithms November 1989 ftp://publications.ai.mit.edu/ai-publications/1000-1499/AIM-1173.ps ftp://publications.ai.mit.edu/ai-publications/pdf/AIM-1173.pdf Early and intermediate vision algorithms, such as smoothing and discontinuity detection, are often implemented on general- purpose serial, and more recently, parallel computers. Special-purpose hardware implementations of low-level vision algorithms may be needed to achieve real- time processing. This memo reviews and analyzes some hardware implementations of low-level vision algorithms. Two types of hardware implementations are considered: the digital signal processing chips of Ruetz (and Broderson) and the analog VLSI circuits of Carver Mead. The advantages and disadvantages of these two approaches for producing a general, real-time vision system are considered.
AIM-1174 Author[s]: Harold Abelson The Bifurcation Interpreter: A Step Towards the Automatic Analysis of Dynamical Systems September 1989 ftp://publications.ai.mit.edu/ai-publications/1000-1499/AIM-1174.ps ftp://publications.ai.mit.edu/ai-publications/pdf/AIM-1174.pdf The Bifurcation Interpreter is a computer program that autonomously explores the steady-state orbits of one-parameter families of periodically- driven oscillators. To report its findings, the Interpreter generates schematic diagrams and English text descriptions similar to those appearing in the science and engineering research literature. Given a system of equations as input, the Interpreter uses symbolic algebra to automatically generate numerical procedures that simulate the system. The Interpreter incorporates knowledge about dynamical systems theory, which it uses to guide the simulations, to interpret the results, and to minimize the effects of numerical error.
AIM-1175 Author[s]: Henrich Bulthoff and Manfred Fahle Disparity Gradients and Depth Scaling September 1989 ftp://publications.ai.mit.edu/ai-publications/1000-1499/AIM-1175.ps ftp://publications.ai.mit.edu/ai-publications/pdf/AIM-1175.pdf The binocular perception of shape and depth relations between objects can change considerably if the viewing direction is changed only by a small angle. We explored this effect psychophysically and found a strong depth reduction effect for large disparity gradients. The effect is found to be strongest for horizontally oriented stimuli, and stronger for line stimuli than for points. This depth scaling effect is discussed in a computational framework of stereo based on a Baysian approach which allows integration of information from different types of matching primitives weighted according to their robustness.
AIM-1176 Author[s]: David McAllester and Robert Givan Natural Language Syntax and First Order Preference October 1989 ftp://publications.ai.mit.edu/ai-publications/1000-1499/AIM-1176.ps ftp://publications.ai.mit.edu/ai-publications/pdf/AIM-1176.pdf We have argued elsewhere that first order inference can be made more efficient by using non-standard syntax for first order logic. In this paper we show how a fragment of English syntax under Montague semantics provides the foundation of a new inference procedure. This procedure seems more effective than corresponding procedures based on either classical syntax of our previously proposed taxonomic syntax. This observation may provide a functional explanation for some of the syntactic structure of English.
AIM-1177 Author[s]: David W. Jacobs Grouping For Recognition November 1989 ftp://publications.ai.mit.edu/ai-publications/1000-1499/AIM-1177.ps ftp://publications.ai.mit.edu/ai-publications/pdf/AIM-1177.pdf This paper presents a new method of grouping edges in order to recognize objects. This grouping method succeeds on images of both two- and three- dimensional objects. So that the recognition system can consider first the collections of edges most likely to lead to the correct recognition of objects, we order groups of edges based on the likelihood that a single object produced them. The grouping module estimates this likelihood using the distance that separates edges and their relative orientation. This ordering greatly reduces the amount of computation required to locate objects and improves the system's robustness to error.
AIM-1178 Author[s]: Eric Sven Ristad and Robert C. Berwick Computational Consequences of Agreement and Ambiguity in Natural Language November 1988 ftp://publications.ai.mit.edu/ai-publications/1000-1499/AIM-1178.ps ftp://publications.ai.mit.edu/ai-publications/pdf/AIM-1178.pdf The computer science technique of computational complexity analysis can provide powerful insights into the algorithm- neutral analysis of information processing tasks. Here we show that a simple, theory- neutral linguistic model of syntactic agreement and ambiguity demonstrates that natural language parsing may be computationally intractable. Significantly, we show that it may be syntactic features rather than rules that can cause this difficulty. Informally, human languages and the computationally intractable Satisfiability (SAT) problem share two costly computional mechanisms: both enforce agreement among symbols across unbounded distances (Subject-Verb agreement) and both allow ambiguity (is a word a Noun or a Verb?).
AITR-1179 Author[s]: Marc H. Raibert, H. Benjamin Brown, Jr., Michael Chepponis, Jeff Koechling, Jessica K. Hodgins, Diane Dustman, W. Kevin Brennan, David S. Barrett, Clay M. Thompson, John Daniell Hebert, Woojin Lee and Lance Borvansky Dynamically Stable Legged Locomotion (September 1985-Septembers1989) September 1989 ftp://publications.ai.mit.edu/ai-publications/1000-1499/AITR-1179.ps ftp://publications.ai.mit.edu/ai-publications/pdf/AITR-1179.pdf This report documents our work in exploring active balance for dynamic legged systems for the period from September 1985 through September 1989. The purpose of this research is to build a foundation of knowledge that can lead both to the construction of useful legged vehicles and to a better understanding of animal locomotion. In this report we focus on the control of biped locomotion, the use of terrain footholds, running at high speed, biped gymnastics, symmetry in running, and the mechanical design of articulated legs.
AIM-1180 Author[s]: Pattie Maes How to Do the Right Thing October 1989 ftp://publications.ai.mit.edu/ai-publications/1000-1499/AIM-1180.ps ftp://publications.ai.mit.edu/ai-publications/pdf/AIM-1180.pdf This paper presents a novel approach to the problem of action selection for an autonomous agent. An agent is viewed as a collection of competence modules. Action selection is modeled as an emergent property of an activation/inhibition dynamics among these modules. A concrete action selection algorithm is presented and a detailed account of the results is given. This algorithm combines characteristics of both traditional planners and reactive systems: it produces fast and robust activity in a tight interaction loop with the environment, while at the same time allowing for some prediction and planning to take place.
AIM-1181 Author[s]: Shimon Edelman and Tomaso Poggio Bringing the Grandmother Back into the Picture: A Memory-Based View of Object Recognition April 1990 ftp://publications.ai.mit.edu/ai-publications/1000-1499/AIM-1181.ps ftp://publications.ai.mit.edu/ai-publications/pdf/AIM-1181.pdf We describe experiments with a versatile pictorial prototype based learning scheme for 3D object recognition. The GRBF scheme seems to be amenable to realization in biophysical hardware because the only kind of computation it involves can be effectively carried out by combining receptive fields. Furthermore, the scheme is computationally attractive because it brings together the old notion of a "grandmother'' cell and the rigorous approximation methods of regularization and splines.
AIM-1182 Author[s]: Rodney A. Brooks and Anita M. Flynn Fast, Cheap and Out of Control December 1989 ftp://publications.ai.mit.edu/ai-publications/1000-1499/AIM-1182.ps ftp://publications.ai.mit.edu/ai-publications/pdf/AIM-1182.pdf Spur-of-the-moment planetary exploration missions are within our reach. Complex systems and complex missions usually take years of planning and force launches to become incredibly expensive. We argue here for cheap, fast missions using large numbers of mass produced simple autonomous robots that are small by today's standards, perhaps 1 to 2kg. We suggest that within a few years it will be possible, at modest cost, to invade a planet with millions of tiny robots.
AIM-1183 Author[s]: Andrew Trice and Randall Davis Consensus Knowledge Acquisition December 1989 ftp://publications.ai.mit.edu/ai-publications/1000-1499/AIM-1183.ps ftp://publications.ai.mit.edu/ai-publications/pdf/AIM-1183.pdf We have developed a method and prototype program for assisting two experts in their attempts to construct a single, consensus knowledge base. We show that consensus building can be effectively facilitated by a debugging approach that identifies, explains, and resolves discrepancies in their knowledge. To implement this approach we identify and use recognition and repair procedures for a variety of discrepancies. Examples of this knowledge are illustrated\ with sample transcripts from CARTER, a system for reconciling two rule-based systems. Implications for resolving other kinds of knowledge representations are also examined.
AIM-1184 Author[s]: David J. Braunegg Stereo Feature Matching in Disparity Space September 1989 ftp://publications.ai.mit.edu/ai-publications/1000-1499/AIM-1184.ps ftp://publications.ai.mit.edu/ai-publications/pdf/AIM-1184.pdf This paper describes a new method for matching, validating, and disambiguating features for stereo vision. It is based on the Marr-Poggio- Grimson stereo matching algorithm which uses zero-crossing contours in difference-of-Gaussian filtered images as features. The matched contours are represented in disparity space, which makes the information needed for matched contour validation and disambiguation easily accessible. The use of disparity space also makes the algorithm conceptually cleaner than previous implementations of the Marr- Poggio-Grimson algorithm and yields a more efficient matching process.
AIM-1185 Author[s]: David J. Braunegg An Alternative to Using the 3D Delaunay Tessellation for Representing Freespace September 1989 ftp://publications.ai.mit.edu/ai-publications/1000-1499/AIM-1185.ps ftp://publications.ai.mit.edu/ai-publications/pdf/AIM-1185.pdf Representing the world in terms of visible surfaces and the freespacesexisting between these surfaces and the viewer is an important problemsin robotics. Recently, researchers have proposed using the 3DsDelaunay Tessellation for representing 3D stereo vision data and thesfreespace determined therefrom. We discuss problems with using thes3D Delaunay Tessellation as the basis of the representation andspropose an alternative representation that we are currentlysinvestigating. This new representation is appropriate for planningsmobile robot navigation and promises to be robust when using stereosdata that has errors and uncertainty.
AIM-1186 Author[s]: David J. Braunegg Location Recognition Using Stereo Vision October 1989 ftp://publications.ai.mit.edu/ai-publications/1000-1499/AIM-1186.ps ftp://publications.ai.mit.edu/ai-publications/pdf/AIM-1186.pdf A mobile robot must be able to determine its own position in the world. To support truly autonomous navigation, we present a system that builds and maintains its own models of world locations and uses these models to recognize its world position from stereo vision input. The system is designed to be robust with respect to input errors and to respond to a gradually changing world by updating the world location models. We present results from tests of the system that demonstrate its reliability. The model builder and recognition system fit into a planned world modeling system that we describe.
AIM-1187 Author[s]: M. Ali Taalebinezhaad Direct Recovery of Motion and Shape in the General Case by Fixation March 1990 ftp://publications.ai.mit.edu/ai-publications/1000-1499/AIM-1187.ps ftp://publications.ai.mit.edu/ai-publications/pdf/AIM-1187.pdf This work introduces a direct method called FIXATION for solving the general motion vision problem. This Fixation method results in a constraint equation between translational and rotational velocities that in combination with the Brightness-Change Constraint Equation (BCCE) solves the general motion vision problem, arbitrary motion with respect to an arbitrary rigid environment. Neither Correspondence nor Optical Flow has been used here. Recently Direct Motion Vision methods have used the BCCE for solving the motion vision problem of special motions or environments. In contrast to those solutions, the Fixation method does not put such severe restrictions on the motion or the environment.
AIM-1189 Author[s]: Feng Zhao Machine Recognition as Representation and Search December 1989 ftp://publications.ai.mit.edu/ai-publications/1000-1499/AIM-1189.ps ftp://publications.ai.mit.edu/ai-publications/pdf/AIM-1189.pdf Generality, representation, and control have been the central issues in machine recognition. Model-based recognition is the search for consistent matches of the model and image features. We present a comparative framework for the evaluation of different approaches, particularly those of ACRONYM, RAF, and Ikeuchi et al. The strengths and weaknesses of these approaches are discussed and compared and the remedies are suggested. Various tradeoffs made in the implementations are analyzed with respect to the systems' intended task-domains. The requirements for a versatile recognition system are motivated. Several directions for future research are pointed out.
AIM-1190 Author[s]: Joachim Heel Direct Estimation of Structure and Motion from Multiple Frames March 1990 ftp://publications.ai.mit.edu/ai-publications/1000-1499/AIM-1190.ps ftp://publications.ai.mit.edu/ai-publications/pdf/AIM-1190.pdf This paper presents a method for the estimation of scene structure and camera motion from a sequence of images. This approach is fundamentally new. No computation of optical flow or feature correspondences is required. The method processes image sequences of arbitrary length and exploits the redundancy for a significant reduction in error over time. No assumptions are made about camera motion or surface structure. Both quantities are fully recovered. Our method combines the "direct'' motion vision approach with the theory of recursive estimation. Each step is illustrated and evaluated with results from real images.
|
|
