 |
Technical Reports |  |
Work Products |  |
Historical Collections |  |
CSAIL Digital Archive - Artificial Intelligence
Laboratory Series
AITR-1204 Author[s]: David Chapman Vision, Instruction, and Action April 1990 ftp://publications.ai.mit.edu/ai-publications/1000-1499/AITR-1204.ps ftp://publications.ai.mit.edu/ai-publications/pdf/AITR-1204.pdf This thesis describes Sonja, a system which uses instructions in the course of visually- guided activity. The thesis explores an integration of research in vision, activity, and natural language pragmatics. Sonja's visual system demonstrates the use of several intermediate visual processes, particularly visual search and routines, previously proposed on psychophysical grounds. The computations Sonja performs are compatible with the constraints imposed by neuroscientifically plausible hardware. Although Sonja can operate autonomously, it can also make flexible use of instructions provided by a human advisor. The system grounds its understanding of these instructions in perception and action.
AITR-1205 Author[s]: Howard B. Reubenstein Automated Acquisition of Evolving Informal Descriptions June 1990 ftp://publications.ai.mit.edu/ai-publications/1000-1499/AITR-1205.ps ftp://publications.ai.mit.edu/ai-publications/pdf/AITR-1205.pdf The Listener is an automated system that unintrusively performs knowledge acquisition from informal input. The Listener develops a coherent internal representation of a description from an initial set of disorganized, imprecise, incomplete, ambiguous, and possibly inconsistent statements. The Listener can produce a summary document from its internal representation to facilitate communication, review, and validation. A special purpose Listener, called the Requirements Apprentice (RA), has been implemented in the software requirements acquisition domain. Unlike most other requirements analysis tools, which start from a formal description language, the focus of the RA is on the transition between informal and formal specifications.
AIM-1208 Author[s]: Manfred Fahle and Tom Troscianko Computation of Texture and Stereoscopic Depth in Humans October 1989 ftp://publications.ai.mit.edu/ai-publications/1000-1499/AIM-1208.ps ftp://publications.ai.mit.edu/ai-publications/pdf/AIM-1208.pdf The computation of texture and of stereoscopic depth is limited by a number of factors in the design of the optical front-end and subsequent processing stages in humans and machines. A number of limiting factors in the human visual system, such as resolution of the optics and opto-electronic interface, contrast, luminance, temporal resolution and eccentricity are reviewed and evaluated concerning their relevance for the recognition of texture and stereoscopic depth. The algorithms used by the human brain to discriminate between textures and to compute stereoscopic depth are very fast and efficient. Their study might be beneficial for the development of better algorithms in machine vision.
AIM-1209 Author[s]: Manfred Fahle Limits of Precision for Human Eye Motor Control November 1989 ftp://publications.ai.mit.edu/ai-publications/1000-1499/AIM-1209.ps ftp://publications.ai.mit.edu/ai-publications/pdf/AIM-1209.pdf Dichoptic presentation of vernier stimuli, i.e., one segment to each eye, yielded three times higher thresholds than binocular presentation, mainly due to uncorrelated movements of both eyes. Thresholds allow one to calculate an upper estimate for the amplitudes of uncorrelated eye movements during fixation. This estimate matches the best results from direct eye position recording, with the calculated mean amplitude of eye tremor corresponding to roughly one photoreceptor diameter. The combined amplitude of both correlated and uncorrelated eye movements was also measured by delaying one segment of the vernier relative to its partner under monocular or dichoptic conditions.
AIM-1210 Author[s]: Manfred Fahle Parallel Computation of Vernier Offsets, Curvature and Chevrons in Humans December 1989 ftp://publications.ai.mit.edu/ai-publications/1000-1499/AIM-1210.ps ftp://publications.ai.mit.edu/ai-publications/pdf/AIM-1210.pdf A vernier offset is detected at once among straight lines, and reaction times are almost independent of the number of simultaneously presented stimuli (distractors), indicating parallel processing of vernier offsets. Reaction times for identifying a vernier offset to one side among verniers offset to the opposite side increase with the number of distractors, indicating serial processing. Even deviations below a photoreceptor diameter can be detected at once. The visual system thus attains positional accuracy below the photoreceptor diameter simultaneously at different positions. I conclude that deviation from straightness, or change of orientation, is detected in parallel over the visual field. Discontinuities or gradients in orientation may represent an elementary feature of vision.
AITR-1214 Author[s]: Nancy S. Pollard The Grasping Problem: Toward Task-Level Programming for an Articulated Hand May 1990 ftp://publications.ai.mit.edu/ai-publications/1000-1499/AITR-1214.ps ftp://publications.ai.mit.edu/ai-publications/pdf/AITR-1214.pdf This report presents a system for generating a stable, feasible, and reachable grasp of a polyhedral object. A set of contact points on the object is found that can result in a stable grasp; a feasible grasp is found in which the robot contacts the object at those contact points; and a path is constructed from the initial configuration of the robot to the stable, feasible final grasp configuration. The algorithm described in the report is designed for the Salisbury hand mounted on a Puma 560 arm, but a similar approach could be used to develop grasping systems for other robots.
AIM-1215 Author[s]: David McAllester Automatic Recognition of Tractability in Inference Relations February 1990 ftp://publications.ai.mit.edu/ai-publications/1000-1499/AIM-1215.ps ftp://publications.ai.mit.edu/ai-publications/pdf/AIM-1215.pdf A procedure is given for recognizing sets of inference rules that generate polynomial time decidable inference relations. The procedure can automatically recognize the tractability of the inference rules underlying congruence closure. The recognition of tractability for that particular rule set constitutes mechanical verification of a theorem originally proved independently by Kozen and Shostak. The procedure is algorithmic, rather than heuristic, and the class of automatically recognizable tractable rule sets can be precisely characterized. A series of examples of rule sets whose tractability is non-trivial, yet machine recognizable, is also given. The technical framework developed here is viewed as a first step toward a general theory of tractable inference relations.
AIM-1216 Author[s]: Elizabeth Bradley Causes and Effects of Chaos December 1990 ftp://publications.ai.mit.edu/ai-publications/1000-1499/AIM-1216.ps ftp://publications.ai.mit.edu/ai-publications/pdf/AIM-126.pdf Most of the recent literature on chaos and nonlinear dynamics is written either for popular science magazine readers or for advanced mathematicians. This paper gives a broad introduction to this interesting and rapidly growing field at a level that is between the two. The graphical and analytical tools used in the literature are explained and demonstrated, the rudiments of the current theory are outlined and that theory is discussed in the context of several examples: an electronic circuit, a chemical reaction and a system of satellites in the solar system.
AIM-1218 Author[s]: J. Brian Subirana-Vilanova and Whitman Richards Perceptual Organization, Figure-Ground, Attention and Saliency August 1991 ftp://publications.ai.mit.edu/ai-publications/1000-1499/AIM-1218.ps ftp://publications.ai.mit.edu/ai-publications/pdf/AIM-1218.pdf Notions of figure-ground, inside-outside are difficult to define in a computational sense, yet seem intuitively meaningful. We propose that "figure" is an attention-directed region of visual information processing, and has a non- discrete boundary. Associated with "figure" is a coordinate frame and a "frame curve" which helps initiate the shape recognition process by selecting and grouping convex image chunks for later matching- to-model. We show that human perception is biased to see chunks outside the frame as more salient than those inside. Specific tasks, however, can reverse this bias. Near/far, top/bottom and expansion/contraction also behave similarly.
AIM-1220 Author[s]: Federico Girosi, Tomaso Poggio and Bruno Caprile Extensions of a Theory of Networks for Approximation and Learning: Outliers and Negative Examples July 1990 ftp://publications.ai.mit.edu/ai-publications/1000-1499/AIM-1220.ps ftp://publications.ai.mit.edu/ai-publications/pdf/AIM-1220.pdf Learning an input-output mapping from a set of examples can be regarded as synthesizing an approximation of a multi-dimensional function. From this point of view, this form of learning is closely related to regularization theory. In this note, we extend the theory by introducing ways of dealing with two aspects of learning: learning in the presence of unreliable examples and learning from positive and negative examples. The first extension corresponds to dealing with outliers among the sparse data. The second one corresponds to exploiting information about points or regions in the range of the function that are forbidden.
AIM-1223 Author[s]: William Singhose Shaping Inputs to Reduce Vibration: A Vector Diagram Approach March 1990 ftp://publications.ai.mit.edu/ai-publications/1000-1499/AIM-1223.ps ftp://publications.ai.mit.edu/ai-publications/pdf/AIM-1223.pdf This paper describes a method for limiting vibration in flexible systems by shaping the system inputs. Unlike most previous attempts at input shaping, this method does not require an extensive system model or lengthy numerical computation; only knowledge of the system natural frequency and damping ratio are required. The effectiveness of this method when there are errors in the system model is explored and quantified. An algorithm is presented which, given an upper bound on acceptable residual vibration amplitude, determines a shaping strategy that is insensitive to errors in the estimated natural frequency. A procedure for shaping inputs to systems with input constraints is outlined. The shaping method is evaluated by dynamic simulations and hardware experiments.
AITR-1224 Author[s]: Andre DeHon Fat-Tree Routing for Transit February 1990 ftp://publications.ai.mit.edu/ai-publications/1000-1499/AITR-1224.ps ftp://publications.ai.mit.edu/ai-publications/pdf/AITR-1224.pdf The Transit network provides high-speed, low-latency, fault-tolerant interconnect for high-performance, multiprocessor computers. The basic connection scheme for Transit uses bidelta style, multistage networks to support up to 256 processors. Scaling to larger machines by simply extending the bidelta network topology will result in a uniform degradation of network latency between all processors. By employing a fat- tree network structure in larger systems, the network provides locality and universality properties which can help minimize the impact of scaling on network latency. This report details the topology and construction issues associated with integrating Transit routing technology into fat-tree interconnect topologies.
AIM-1225 Author[s]: Andre DeHon, Tom Knight and Marvin Minsky Fault-Tolerant Design for Multistage Routing Networks April 1990 ftp://publications.ai.mit.edu/ai-publications/1000-1499/AIM-1225.ps ftp://publications.ai.mit.edu/ai-publications/pdf/AIM-1225.pdf As the size of digital systems increases, the mean time between single component failures diminishes. To avoid component related failures, large computers must be fault-tolerant. In this paper, we focus on methods for achieving a high degree of fault- tolerance in multistage routing networks. We describe a multipath scheme for providing end-to-end fault-tolerance on large networks. The scheme improves routing performance while keeping network latency low. We also describe the novel routing component, RN1, which implements this scheme, showing how it can be the basic building block for fault- tolerant multistage routing networks.
AIM-1226 Author[s]: W. Eric L. Grimson The Effect of Indexing on the Complexity of Object Recognition April 1990 ftp://publications.ai.mit.edu/ai-publications/1000-1499/AIM-1226.ps ftp://publications.ai.mit.edu/ai-publications/pdf/AIM-1226.pdf Many current recognition systems use constrained search to locate objects in cluttered environments. Previous formal analysis has shown that the expected amount of search is quadratic in the number of model and data features, if all the data is known to come from a sinlge object, but is exponential when spurious data is included. If one can group the data into subsets likely to have come from a single object, then terminating the search once a "good enough" interpretation is found reduces the expected search to cubic. Without successful grouping, terminated search is still exponential. These results apply to finding instances of a known object in the data. In this paper, we turn to the problem of selecting models from a library, and examine the combinatorics of determining that a candidate object is not present in the data. We show that the expected search is again exponential, implying that naïve approaches to indexing are likely to carry an expensive overhead, since an exponential amount of work is needed to week out each of the incorrect models. The analytic results are shown to be in agreement with empirical data for cluttered object recognition.
AIM-1227 Author[s]: Rodney A. Brooks The Behavior Language; User's Guide April 1990 ftp://publications.ai.mit.edu/ai-publications/1000-1499/AIM-1227.ps ftp://publications.ai.mit.edu/ai-publications/pdf/AIM-1227.pdf The Behavior Language is a rule-based real- time parallel robot programming language originally based on ideas from [Brooks 86], [Connell 89], and [Maes 89]. It compiles into a modified and extended version of the subsumption architecture [Brooks 86] and thus has backends for a number of processors including the Motorola 68000 and 68HCll, the Hitachi 6301, and Common Lisp. Behaviors are groups of rules which are activatable by a number of different schemes. There are no shared data structures across behaviors, but instead all communication is by explicit message passing. All rules are assumed to run in parallel and asynchronously. It includes the earlier notions of inhibition and suppression, along with a number of mechanisms for spreading of activation.
AITR-1228 Author[s]: Maja J. Mataric A Distributed Model for Mobile Robot Environment-Learning and Navigation May 1990 ftp://publications.ai.mit.edu/ai-publications/1000-1499/AITR-1228.ps ftp://publications.ai.mit.edu/ai-publications/pdf/AITR-1228.pdf A distributed method for mobile robot navigation, spatial learning, and path planning is presented. It is implemented on a sonar- based physical robot, Toto, consisting of three competence layers: 1) Low-level navigation: a collection of reflex-like rules resulting in emergent boundary-tracing. 2) Landmark detection: dynamically extracts landmarks from the robot's motion. 3) Map learning: constructs a distributed map of landmarks. The parallel implementation allows for localization in constant time. Spreading of activation computes both topological and physical shortest paths in linear time. The main issues addressed are: distributed, procedural, and qualitative representation and computation, emergent behaviors, dynamic landmarks, minimized communication.
AITR-1229 Author[s]: David Jerome Braunegg MARVEL: A System for Recognizing World Locations with Stereo Vision June 1990 ftp://publications.ai.mit.edu/ai-publications/1000-1499/AITR-1229.ps ftp://publications.ai.mit.edu/ai-publications/pdf/AITR-1229.pdf To use a world model, a mobile robot must be able to determine its own position in the world. To support truly autonomous navigation, I present MARVEL, 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. MARVEL is designed to be robust with respect to input errors and to respond to a gradually changing world by updating its world location models. I present results from real- world tests of the system that demonstrate its reliability. MARVEL fits into a world modeling system under development.
AIM-1230 Author[s]: Anita Flynn (editor) Olympic Robot Building Manual December 1988 ftp://publications.ai.mit.edu/ai-publications/1000-1499/AIM-1230.ps ftp://publications.ai.mit.edu/ai-publications/pdf/AIM-1230.pdf The 1989 AI Lab Winter Olympics will take a slightly different twist from previous Olympiads. Although there will still be a dozen or so athletic competitions, the annual talent show finale will now be a display not of human talent, but of robot talent. Spurred on by the question, "Why aren't there more robots running around the AI Lab?", Olympic Robot Building is an attempt to teach everyone how to build a robot and get them started. Robot kits will be given out the last week of classes before the Christmas break and teams have until the Robot Talent Show, January 27th, to build a machine that intelligently connects perception to action. There is no constraint on what can be built; participants are free to pick their own problems and solution implementations. As Olympic Robot Building is purposefully a talent show, there is no particular obstacle course to be traversed or specific feat to be demonstrated. The hope is that this format will promote creativity, freedom and imagination. This manual provides a guide to overcoming all the practical problems in building things. What follows are tutorials on the components supplied in the kits: a microprocessor circuit "brain", a variety of sensors and motors, a mechanical building block system, a complete software development environment, some example robots and a few tips on debugging and prototyping. Parts given out in the kits can be used, ignored or supplemented, as the kits are designed primarily to overcome the intertia of getting started. If all goes well, then come February, there should be all kinds of new members running around the AI Lab!
AIM-1231 Author[s]: Patrick H. Winston and Satayjit Rao Repairing Learned Knowledge Using Experience May 1990 ftp://publications.ai.mit.edu/ai-publications/1000-1499/AIM-1231.ps ftp://publications.ai.mit.edu/ai-publications/pdf/AIM-1231.pdf Explanation-based learning occurs when something useful is retained from an explanation, usually an account of how some particular problem can be solved given a sound theory. Many real-world explanations are not based on sound theory, however, and wrong things may be learned accidentally, as subsequent failures will likely demonstrate. In this paper, we describe ways to isolate the facts that cause failures, ways to explain why those facts cause problems, and ways to repair learning mistakes. In particular, our program learns to distinguish pails from cups after making a few mistakes.
AITR-1232 Author[s]: Jeff F. Tabor Noise Reduction Using Low Weight and Constant Weight Coding Techniques May 1990 ftp://publications.ai.mit.edu/ai-publications/1000-1499/AITR-1232.ps ftp://publications.ai.mit.edu/ai-publications/pdf/AITR-1232.pdf Signalling off-chip requires significant current. As a result, a chip's power-supply current changes drastically during certain output-bus transitions. These current fluctuations cause a voltage drop between the chip and circuit board due to the parasitic inductance of the power-supply package leads. Digital designers often go to great lengths to reduce this "transmitted" noise. Cray, for instance, carefully balances output signals using a technique called differential signalling to guarantee a chip has constant output current. Transmitted-noise reduction costs Cray a factor of two in output pins and wires. Coding achieves similar results at smaller costs.
AITR-1233 Author[s]: Ellen Spertus Dataflow Computation for the J-Machine May 1990 ftp://publications.ai.mit.edu/ai-publications/1000-1499/AITR-1233.ps ftp://publications.ai.mit.edu/ai-publications/pdf/AITR-1233.pdf The dataflow model of computation exposes and exploits parallelism in programs without requiring programmer annotation; however, instruction- level dataflow is too fine-grained to be efficient on general-purpose processors. A popular solution is to develop a "hybrid'' model of computation where regions of dataflow graphs are combined into sequential blocks of code. I have implemented such a system to allow the J- Machine to run Id programs, leaving exposed a high amount of parallelism --- such as among loop iterations. I describe this system and provide an analysis of its strengths and weaknesses and those of the J-Machine, along with ideas for improvement.
AITR-1234 Author[s]: David J. Bennett The Control of Human Arm Movement Models and Mechanical Constraints May 1990 ftp://publications.ai.mit.edu/ai-publications/1000-1499/AITR-1234.ps ftp://publications.ai.mit.edu/ai-publications/pdf/AITR-1234.pdf A serial-link manipulator may form a mobile closed kinematic chain when interacting with the environment, if it is redundant with respect to the task degrees of freedom (DOFs) at the endpoint. If the mobile closed chain assumes a number of configurations, then loop consistency equations permit the manipulator and task kinematics to be calibrated simultaneously using only the joint angle readings; endpoint sensing is not required. Example tasks include a fixed endpoint (0 DOF task), the opening of a door (1 DOF task), and point contact (3 DOF task). Identifiability conditions are derived for these various tasks.
AITR-1235 Author[s]: Helen Greiner Passive and Active Grasping with a Prehensile Robot End-Effector May 1990 ftp://publications.ai.mit.edu/ai-publications/1000-1499/AITR-1235.ps ftp://publications.ai.mit.edu/ai-publicaitons/pdf/AITR-1235.pdf This report presents a design of a new type of robot end-effector with inherent mechanical grasping capabilities. Concentrating on designing an end-effector to grasp a simple class of objects, cylindrical, allowed a design with only one degree of actuation. The key features of this design are high bandwidth response to forces, passive grasping capabilities, ease of control, and ability to wrap around objects with simple geometries providing form closure. A prototype of this mechanism was built to evaluate these features.
AIM-1236 Author[s]: Jonathan Amsterdam The Iterate Manual October 1990 ftp://publications.ai.mit.edu/ai-publications/1000-1499/AIM-1236.ps ftp://publications.ai.mit.edu/ai-publications/pdf/AIM-1236.pdf This is the manual for version 1.1 of Iterate, a powerful iteration macro for Common Lisp. Iterate is similar to Loop but provides numerous additional features, is well integrated with Lisp, and is extensible.
AITR-1237 Author[s]: Camille Z. Chammas Analysis and Implementation of Robust Grasping Behaviors May 1990 ftp://publications.ai.mit.edu/ai-publications/1000-1499/AITR-1237.ps ftp://publications.ai.mit.edu/ai-publications/pdf/AITR-1237.pdf This thesis addresses the problem of developing automatic grasping capabilities for robotic hands. Using a 2-jointed and a 4- jointed nmodel of the hand, we establish the geometric conditions necessary for achieving form closure grasps of cylindrical objects. We then define and show how to construct the grasping pre-image for quasi-static (friction dominated) and zero-G (inertia dominated) motions for sensorless and sensor-driven grasps with and without arm motions. While the approach does not rely on detailed modeling, it is computationally inexpensive, reliable, and easy to implement. Example behaviors were successfully implemented on the Salisbury hand and on a planar 2- fingered, 4 degree-of-freedom hand.
AIM-1238 Author[s]: Gary C. Borchardt Transition Space November 1990 ftp://publications.ai.mit.edu/ai-publications/1000-1499/AIM-1238.ps ftp://publications.ai.mit.edu/ai-publications/pdf/AIM-1238.pdf Informal causal descriptions of physical systems abound in sources such as encyclopedias, reports and user's manuals. Yet these descriptions remain largely opaque to computer processing. This paper proposes a representational framework in which such descriptions are viewed as providing partial specifications of paths in a space of possible transitions, or transition space. In this framework, the task of comprehending informal causal descriptions emerges as one of completing the specifications of paths in transition space---filling causal gaps and relating accounts of activity varied by analogy and abstraction. The use of the representation and its operations is illustrated in the context of a simple description concerning rocket propulsion.
AIM-1239 Author[s]: Shimon Edelman and Heinrich H. Bulthoff Viewpoint-Specific Representations in Three-Dimensional Object Recognition August 1990 ftp://publications.ai.mit.edu/ai-publications/1000-1499/AIM-1239.ps ftp://publications.ai.mit.edu/ai-publications/pdf/AIM-1239.pdf We report a series of psychophysical experiments that explore different aspects of the problem of object representation and recognition in human vision. Contrary to the paradigmatic view which holds that the representations are three-dimensional and object-centered, the results consistently support the notion of view-specific representations that include at most partial depth information. In simulated experiments that involved the same stimuli shown to the human subjects, computational models built around two-dimensional multiple-view representations replicated our main psychophysical results, including patterns of generalization errors and the time course of perceptual learning.
AIM-1240 Author[s]: Manfred Fahle and Gunther Palm A Model for Rivalry Between Cognitive Contours June 1990 ftp://publications.ai.mit.edu/ai-publications/1000-1499/AIM-1240.ps ftp://publications.ai.mit.edu/ai-publications/pdf/AIM-1240.pdf The interactions between illusory and real contours have been inves- tigated under monocular, binocular and dichoptic conditions. Results show that under all three presentation conditions, periodic alternations, generally called rivalry, occur during the perception of cognitive (or illusory) triangles, while earlier research had failed to find such rivalry (Bradley & Dumais, 1975). With line triangles, rivalry is experienced only under dichoptic conditions. A model is proposed to account for the observed phenomena, and the results of simulations are presented.
AIM-1242 Author[s]: Manfred Fahle On the Shifter Hyposthesis for the Elimination of Motion Blur August 1990 ftp://publications.ai.mit.edu/ai-publications/1000-1499/AIM-1242.ps ftp://publications.ai.mit.edu/ai-publications/pdf/AIM-1242.pdf Moving objects may stimulate many retinal photoreceptors within the integration time of the receptors without motion blur being experienced. Anderson and vanEssen (1987) suggested that the neuronal representation of retinal images is shifted on its way to the cortex, in an opposite direction to the motion. Thus, the cortical representation of objects would be stationary. I have measured thresholds for two vernier stimuli, moving simultaneously into opposite directions over identical positions. Motion blur for these stimuli is not stronger than with a single moving stimulus, and thresholds can be below a photoreceptor diameter. This result cannot be easily reconciled with the hypothesis of Tshifter circuitsU.
AITR-1244 Author[s]: Michael Dean Levin Design and Control of a Closed-Loop Brushless Torque Actuator May 1990 ftp://publications.ai.mit.edu/ai-publications/1000-1499/AITR-1244.ps ftp://publications.ai.mit.edu/ai-publications/pdf/AITR-1244.pdf This report explores the design and control issues associated with a brushless actuator capable of achieving extremely high torque accuracy. Models of several different motor - sensor configurations were studied to determine dynamic characteristics. A reaction torque sensor fixed to the motor stator was implemented to decouple the transmission dynamics from the sensor. This resulted in a compact actuator with higher bandwidth and precision than could be obtained with an inline or joint sensor. Testing demonstrated that closed-loop torque accuracy was within 0.1%, and the mechanical bandwidth approached 300 Hz.
AITR-1245 Author[s]: Donald Scott Wills Pi: A Parallel Architecture Interface for Multi-Model Execution May 1990 ftp://publications.ai.mit.edu/ai-publications/1000-1499/AITR-1245.ps ftp://publications.ai.mit.edu/ai-publications/pdf/AITR-1245.pdf This thesis defines Pi, a parallel architecture interface that separates model and machine issues, allowing them to be addressed independently. This provides greater flexibility for both the model and machine builder. Pi addresses a set of common parallel model requirements including low latency communication, fast task switching, low cost synchronization, efficient storage management, the ability to exploit locality, and efficient support for sequential code. Since Pi provides generic parallel operations, it can efficiently support many parallel programming models including hybrids of existing models. Pi also forms a basis of comparison for architectural components.
AITR-1247 Author[s]: Bruce R. Thompson The PHD: A Planar, Harmonic Drive Robot for Joint Torque Control May 1990 ftp://publications.ai.mit.edu/ai-publications/1000-1499/AITR-1247.ps ftp://publications.ai.mit.edu/ai-publications/pdf/AITR-1247.pdf This thesis details the development of a model of a seven degree of freedom manipulator for position control. Then, it goes on to discuss the design and construction of a the PHD, a robot built to serve two purposes: first, to perform research on joint torque control schemes, and second, to determine the important dynamic characteristics of the Harmonic Drive. The PHD, is a planar, three degree of freedom arm with torque sensors integral to each joint. Preliminary testing has shown that a simple linear spring model of the Harmonic Drive's flexibility is suitable in many situations.
AITR-1248 Author[s]: Andrew Andai Chien Concurrent Aggregates (CA): An Object-Oriented Language for Fine-Grained Message-Passing Machines July 1990 ftp://publications.ai.mit.edu/ai-publications/1000-1499/AITR-1248.ps ftp://publications.ai.mit.edu/ai-publications/pdf/AITR-1248.pdf Fine-grained parallel machines have the potential for very high speed computation. To program massively-concurrent MIMD machines, programmers need tools for managing complexity. These tools should not restrict program concurrency. Concurrent Aggregates (CA) provides multiple-access data abstraction tools, Aggregates, which can be used to implement abstractions with virtually unlimited potential for concurrency. Such tools allow programmers to modularize programs without reducing concurrency. I describe the design, motivation, implementation and evaluation of Concurrent Aggregates. CA has been used to construct a number of application programs. Multi-access data abstractions are found to be useful in constructing highly concurrent programs.
AIM-1249 Author[s]: Harold Abelson, Andrew A. Berlin, Jacob Katzenelson, William H. McAllister, Guillermo J. Rozas and Gerald Jay Sussman The Supercomputer Toolkit and Its Applications July 1990 ftp://publications.ai.mit.edu/ai-publications/1000-1499/AIM-1249.ps ftp://publications.ai.mit.edu/ai-publications/pdf/AIM-1249.pdf The Supercomputer Toolkit is a proposed family of standard hardware and software components from which special-purpose machines can be easily configured. Using the Toolkit, a scientist or an engineer, starting with a suitable computational problem, will be able to readily configure a special purpose multiprocessor that attains supercomputer- class performance on that problem, at a fraction of the cost of a general purpose supercomputer. The Toolkit is currently being built as a joint project between Hewlett- Packard and MIT. The software and the applications are in various stages of development and research.
AIM-1250 Author[s]: W. Eric L. Grimson, Daniel P. Huttenlocher and David W. Jacobs Affine Matching with Bounded Sensor Error: A Study of Geometric Hashing and Alignment August 1991 ftp://publications.ai.mit.edu/ai-publications/1000-1499/AIM-1250.ps ftp://publications.ai.mit.edu/ai-publications/pdf/AIM-1250.pdf Affine transformations are often used in recognition systems, to approximate the effects of perspective projection. The underlying mathematics is for exact feature data, with no positional uncertainty. In practice, heuristics are added to handle uncertainty. We provide a precise analysis of affine point matching, obtaining an expression for the range of affine-invariant values consistent with bounded uncertainty. This analysis reveals that the range of affine- invariant values depends on the actual $x$- $y$-positions of the features, i.e. with uncertainty, affine representations are not invariant with respect to the Cartesian coordinate system. We analyze the effect of this on geometric hashing and alignment recognition methods.
AITR-1251 Author[s]: Robert Joseph Hall Program Improvement by Automatic Redistribution of Intermediate Results February 1991 ftp://publications.ai.mit.edu/ai-publications/1000-1499/AITR-1251.ps ftp://publications.ai.mit.edu/ai-publications/pdf/AITR-1251.pdf Introducing function sharing into designs allows eliminating costly structure by adapting existing structure to perform its function. This can eliminate many inefficiencies of reusing general componentssin specific contexts. "Redistribution of intermediate results'' focuses on instances where adaptation requires only addition/deletion of data flow and unused code removal. I show that this approach unifies and extends several well- known optimization classes. The system performs search and screening by deriving, using a novel explanation-based generalization technique, operational filtering predicates from input teleological information. The key advantage is to focus the system's effort on optimizations that are easier to prove safe.
AIM-1252 Author[s]: Anita M. Flynn The 1990 AI Fair August 1990 ftp://publications.ai.mit.edu/ai-publications/1000-1499/AIM-1252.ps ftp://publications.ai.mit.edu/ai-publications/pdf/AIM-1252.pdf This year, as the finale to the Artificial Intelligence Laboratory’s annual Winter Olympics, the Lab staged an AI Fair – a night devoted to displaying the wide variety of talents and interests within the laboratory. The Fair provided an outlet for creativity and fun in a carnival-like atmosphere. Students organized events from robot boat races to face-recognition vision contests. Research groups came together to make posters and booths explaining their work. The robots rolled down out of the labs, networks were turned over to aerial combat computer games and walls were decorated with posters of zany ideas for the future. Everyone pitched in, and this photograph album is a pictorial account of the fun that night at the AI Fair.
AIM-1253 Author[s]: Tomaso Poggio A Theory of How the Brain Might Work December 1990 ftp://publications.ai.mit.edu/ai-publications/1000-1499/AIM-1253.ps ftp://publications.ai.mit.edu/ai-publications/pdf/AIM-1253.pdf I wish to propose a quite speculative new version of the grandmother cell theory to explain how the brain, or parts of it, may work. In particular, I discuss how the visual system may learn to recognize 3D objects. The model would apply directly to the cortical cells involved in visual face recognition. I will also outline the relation of our theory to existing models of the cerebellum and of motor control. Specific biophysical mechanisms can be readily suggested as part of a basic type of neural circuitry that can learn to approximate multidimensional input-output mappings from sets of examples and that is expected to be replicated in different regions of the brain and across modalities. The main points of the theory are: -the brain uses modules for multivariate function approximation as basic components of several of its information processing subsystems. -these modules are realized as HyperBF networks (Poggio and Girosi, 1990a,b). -HyperBF networks can be implemented in terms of biologically plausible mechanisms and circuitry. The theory predicts a specific type of population coding that represents an extension of schemes such as look-up tables. I will conclude with some speculations about the trade-off between memory and computation and the evolution of intelligence.
AIM-1254 Author[s]: Bruno Caprile and Federico Girosi A Nondeterministic Minimization Algorithm September 1990 ftp://publications.ai.mit.edu/ai-publications/1000-1499/AIM-1254.ps ftp://publications.ai.mit.edu/ai-publications/pdf/AIM-1254.pdf The problem of minimizing a multivariate function is recurrent in many disciplines as Physics, Mathematics, Engeneering and, of course, Computer Science. In this paper we describe a simple nondeterministic algorithm which is based on the idea of adaptive noise, and that proved to be particularly effective in the minimization of a class of multivariate, continuous valued, smooth functions, associated with some recent extension of regularization theory by Poggio and Girosi (1990). Results obtained by using this method and a more traditional gradient descent technique are also compared.
AIM-1255 Author[s]: Brian Eberman and David L. Brock Line Kinematics for Whole-Arm Manipulation January 1991 ftp://publications.ai.mit.edu/ai-publications/1000-1499/AIM-1255.ps ftp://publications.ai.mit.edu/ai-publications/pdf/AIM-1255.pdf A Whole-Arm Manipulator uses every surface to both sense and interact with the environment. To facilitate the analysis and control of a Whole-Arm Manipulator, line geometry is used to describe the location and trajectory of the links. Applications of line kinematics are described and implemented on the MIT Whole-Arm Manipulator (WAM-1).
AIM-1256 Author[s]: Yang Meng Tan Supporting Reuse and Evolution in Software Design October 1990 ftp://publications.ai.mit.edu/ai-publications/1000-1499/AIM-1256.ps ftp://publications.ai.mit.edu/ai-publications/pdf/AIM-1256.pdf Program design is an area of programming that can benefit significantly from machine-mediated assistance. A proposed tool, called the Design Apprentice (DA), can assist a programmer in the detailed design of programs. The DA supports software reuse through a library of commonly-used algorithmic fragments, or cliches, that codifies standard programming. The cliche library enables the programmer to describe the design of a program concisely. The DA can detect some kinds of inconsistencies and incompleteness in program descriptions. It automates detailed design by automatically selecting appropriate algorithms and data structures. It supports the evolution of program designs by keeping explicit dependencies between the design decisions made. These capabilities of the DA are underlaid bya model of programming, called programming by successive elaboration, which mimics the way programmers interact. Programming by successive elaboration is characterized by the use of breadth-first exposition of layered program descriptions and the successive modifications of descriptions. A scenario is presented to illustrate the concept of the DA. Technques for automating the detailed design process are described. A framework is given in which designs are incrementally augmented and modified by a succession of design steps. A library of cliches and a suite of design steps needed to support the scenario are presented.
AITR-1257 Author[s]: Choon P. Goh Model Selection for Solving Kinematics Problems September 1990 ftp://publications.ai.mit.edu/ai-publications/1000-1499/AITR-1257.ps ftp://publications.ai.mit.edu/ai-publications/pdf/AITR-1257.pdf There has been much interest in the area of model-based reasoning within the Artificial Intelligence community, particularly in its application to diagnosis and troubleshooting. The core issue in this thesis, simply put, is, model-based reasoning is fine, but whence the model? Where do the models come from? How do we know we have the right models? What does the right model mean anyway? Our work has three major components. The first component deals with how we determine whether a piece of information is relevant to solving a problem. We have three ways of determining relevance: derivational, situational and an order-of- magnitude reasoning process. The second component deals with the defining and building of models for solving problems. We identify these models, determine what we need to know about them, and importantly, determine when they are appropriate. Currently, the system has a collection of four basic models and two hybrid models. This collection of models has been successfully tested on a set of fifteen simple kinematics problems. The third major component of our work deals with how the models are selected.
AIM-1259 Author[s]: Thomas M. Breuel An Efficient Correspondence Based Algorithm for 2D and 3D Model Based Recognition October 1990 ftp://publications.ai.mit.edu/ai-publications/1000-1499/AIM-1259.ps ftp://publications.ai.mit.edu/ai-publications/pdf/AIM-1259.pdf A polynomial time algorithm (pruned correspondence search, PCS) with good average case performance for solving a wide class of geometric maximal matching problems, including the problem of recognizing 3D objects from a single 2D image, is presented. Efficient verification algorithms, based on a linear representation of location constraints, are given for the case of affine transformations among vector spaces and for the case of rigid 2D and 3D transformations with scale. Some preliminary experiments suggest that PCS is a practical algorithm. Its similarity to existing correspondence based algorithms means that a number of existing techniques for speedup can be incorporated into PCS to improve its performance.
AITR-1260 Author[s]: Eric Sven Ristad Computational Structure of Human Language October 1990 ftp://publications.ai.mit.edu/ai-publications/1000-1499/AITR-1260.ps ftp://publications.ai.mit.edu/ai-publications/pdf/AITR-1260.pdf The central thesis of this report is that human language is NP-complete. That is, the process of comprehending and producing utterances is bounded above by the class NP, and below by NP-hardness. This constructive complexity thesis has two empirical consequences. The first is to predict that a linguistic theory outside NP is unnaturally powerful. The second is to predict that a linguistic theory easier than NP-hard is descriptively inadequate. To prove the lower bound, I show that the following three subproblems of language comprehension are all NP-hard: decide whether a given sound is possible sound of a given language; disambiguate a sequence of words; and compute the antecedents of pronouns. The proofs are based directly on the empirical facts of the language user’s knowledge, under an appropriate idealization. Therefore, they are invariant across linguistic theories. (For this reason, no knowledge of linguistic theory is needed to understand the proofs, only knowledge of English.) To illustrate the usefulness of the upper bound, I show that two widely-accepted analyses of the language user’s knowledge (of syntactic ellipsis and phonological dependencies) lead to complexity outside of NP (PSPACE-hard and Undecidable, respectively). Next, guided by the complexity proofs, I construct alternate linguisitic analyses that are strictly superior on descriptive grounds, as well as being less complex computationally (in NP). The report also presents a new framework for linguistic theorizing, that resolves important puzzles in generative linguistics, and guides the mathematical investigation of human language.
AIM-1261 Author[s]: Claudio Melchiorri and J.K. Salisbury Exploiting the Redundancy of a Hand-Arm Robotic System October 1990 ftp://publications.ai.mit.edu/ai-publications/1000-1499/AIM-1261.ps ftp://publications.ai.mit.edu/ai-publications/pdf/AIM-1261.pdf In this report, a method for exploiting the redundancy of a hand-arm mechanical system for manipulation tasks is illustrated. The basic idea is to try to exploit the different intrinsic capabilities of the arm and hand subsystems. The Jacobian transpose technique is at the core of the method: different behaviors of the two subsystems are obtained by means of constraints in Null(J) generated by non-orthogonal projectors. Comments about the computation of the constraints are reported in the memo, as well as a description of some preliminary experiments on a robotic system at the A.I. Lab., M.I.T.
AIM-1262 Author[s]: Antonio Bicchi, J. Kenneth Salisbury and David L. Brock Contact Sensing from Force Measurements October 1990 ftp://publications.ai.mit.edu/ai-publications/1000-1499/AIM-1262.ps ftp://publications.ai.mit.edu/ai-publications/pdf/AIM-1262.pdf This paper addresses contact sensing, i.e. the problem of resolving the location of a contact, the force at the interface and the moment about the contact normals. Called "intrinsic'' contact sensing for the use of internal force and torque measurements, this method allows for practical devices which provide simple, relevant contact information in practical robotic applications. Such sensors have been used in conjunction with robot hands to identify objects, determine surface friction, detect slip, augment grasp stability, measure object mass, probe surfaces, control collision and a variety of other useful tasks. This paper describes the theoretical basis for their operation and provides a framework for future device design.
AIM-1263 Author[s]: Antionio Bicchi A Criterion for the Optimal Design of Multiaxis Force Sensors October 1990 ftp://publications.ai.mit.edu/ai-publications/1000-1499/AIM-1263.ps ftp://publications.ai.mit.edu/ai-publications/pdf/AIM-1263.pdf This paper deals with the design of multi-axis force (also known as force/torque) sensors, as considered within the framework of optimal design theory. The principal goal of this paper is to identify a mathematical objective function, whose minimization corresponds to the optimization of sensor accuracy. The methodology employed is derived from linear algebra and analysis of numerical stability. The problem of optimizing the number of basic transducers employed in a multi- component sensor is also addressed. Finally, applications of the proposed method to the design of a simple sensor as well as to the optimization of a novel, 6-axis miniaturized sensor are discussed.
AIM-1264 Author[s]: Daphna Weinshall The Shape of Shading October 1990 ftp://publications.ai.mit.edu/ai-publications/1000-1499/AIM-1264.ps ftp://publications.ai.mit.edu/ai-publications/pdf/AIM-1264.pdf This paper discusses the relationship between the shape of the shading, the surface whose depth at each point equals the brightness in the image, and the shape of the original surface. I suggest the shading as an initial local approximation to shape, and discuss the scope of this approximation and what it may be good for. In particular, qualitative surface features, such as the sign of the Gaussian curvature, can be computed in some cases directly from the shading. Finally, a method to compute the direction of the illuminant (assuming a single point light source) from shading on occluding contours is shown.
AIM-1265 Author[s]: Joachim Dengler Estimation of Discontinuous Displacement Vector Fields with the Minimum Description Length Criterion October 1990 ftp://publications.ai.mit.edu/ai-publications/1000-1499/AIM-1265.ps ftp://publications.ai.mit.edu/ai-publications/pdf/AIM-1265.pdf A new noniterative approach to determine displacement vector fields with discontinuities is described. In order to overcome the limitations of current methods, the problem is regarded as a general modelling problem. Starting from a family of regularized estimates, by measuring the difference in description length the compatibility between different levels of regularization is determined. This gives local but noisy evidence of possible model boundaries at multiple scales. With the two constraints of continous lines of discontinuities and the spatial coincidence assumption consistent boundary evidence is found. Based on this combined evidence the model is updated, now describing homogeneous regions with sharp discontinuities.
AIM-1266 Author[s]: David J. Beymer Finding Junctions Using the Image Gradient December 1991 ftp://publications.ai.mit.edu/ai-publications/1000-1499/AIM-1266.ps ftp://publications.ai.mit.edu/ai-publications/pdf/AIM-1266.pdf Junctions are the intersection points of three or more intensity surfaces in an image. An analysis of zero crossings and the gradient near junctions demonstrates that gradient- based edge detection schemes fragment edges at junctions. This fragmentation is caused by the intrinsic pairing of zero crossings and a destructive interference of edge gradients at junctions. Using the previous gradient analysis, we propose a junction detector that finds junctions in edge maps by following gradient ridges and using the minimum direction of saddle points in the gradient. The junction detector is demonstrated on real imagery and previous approaches to junction detection are discussed.
AIM-1269 Author[s]: Anita M. Flynn, Lee S. Tavrow, Stephen F. Bart and Rodney A. Brooks Piezoelectric Micromotors for Microrobots February 1991 ftp://publications.ai.mit.edu/ai-publications/1000-1499/AIM-1269.ps ftp://publications.ai.mit.edu/ai-publications/pdf/AIM-1269.pdf By combining new robot control systems with piezoelectric motors and micromechanics, we propose creating micromechanical systems which are small, cheap and completely autonomous. We have fabricated small - a few millimeters in diameter - piezoelectric motors using ferroelectric thin films and consisting of two pieces: a stator and a rotor. The stationary stator includes a piezoelectric film in which we induce bending in the form of a traveling wave. Anything which sits atop the stator is propelled by the wave. A small glass lens placed upon the stator becomes the spinning rotor. Using thin films of PZT on silicon nitride memebranes, various types of actuator structures have been fabricated.
AIM-1270 Author[s]: Tanveer Fathima Syeda-Mahmood Data and Model-Driven Selection Using Color Regions February 1992 ftp://publications.ai.mit.edu/ai-publications/1000-1499/AIM-1270.ps ftp://publications.ai.mit.edu/ai-publications/pdf/AIM-1270.pdf A key problem in model-based object recognition is selection, namely, the problem of determining which regions in the image are likely to come from a single object. In this paper we present an approach that extracts and uses color region information to perform selection either based solely on image- data (data-driven), or based on the knowledge of the color description of the model (model -driven). The paper presents a method of perceptual color specification by color categories to extract perceptual color regions. It also discusses the utility of color-based selection in reducing the search involved in recognition.
AIM-1271 Author[s]: Tomaso Poggio, Manfred Fahle and Shimon Edelman Synthesis of Visual Modules from Examples: Learning Hyperacuity January 1991 ftp://publications.ai.mit.edu/ai-publications/1000-1499/AIM-1271.ps ftp://publications.ai.mit.edu/ai-publications/pdf/AIM-1271.pdf Networks that solve specific visual tasks, such as the evaluation of spatial relations with hyperacuity precision, can be eastily synthesized from a small set of examples. This may have significant implications for the interpretation of many psychophysical results in terms of neuronal models.
AIM-1272 Author[s]: Ellen Spertus and William J. Dally Experiments with Dataflow on a General-Purpose Parallel Computer January 1991 ftp://publications.ai.mit.edu/ai-publications/1000-1499/AIM-1272.ps ftp://publications.ai.mit.edu/ai-publications/pdf/AIM-1272.pdf The MIT J-Machine, a massively-parallel computer, is an experiment in providing general-purpose mechanisms for communication, synchronization, and naming that will support a wide variety of parallel models of comptuation. We have developed two experimental dataflow programming systems for the J-Machine. For the first system, we adapted Papadopoulos' explicit token store to implement static and then dynamic dataflow. Our second system made use of Iannucci's hybrid execution model to combine several dataflow graph nodes into a single sequence, decreasing scheduling overhead. By combining the strengths of the two systems, it is possible to produce a system with competitive performance.
AIM-1274 Author[s]: Feng Zhao Extracting and Representing Qualitative Behaviors of Complex Systems in Phase Spaces March 1991 ftp://publications.ai.mit.edu/ai-publications/1000-1499/AIM-1274.ps ftp://publications.ai.mit.edu/ai-publications/pdf/AIM-1274.pdf We develop a qualitative method for understanding and representing phase space structures of complex systems and demonstrate the method with a program, MAPS --- Modeler and Analyzer for Phase Spaces, using deep domain knowledge of dynamical system theory. Given a dynamical system, the program generates a complete, high level symbolic description of the phase space structure sensible to human beings and manipulable by other programs. Using the phase space descriptions, we are developing a novel control synthesis strategy to automatically synthesize a controller for a nonlinear system in the phase space to achieve desired properties.
AITR-1275 Author[s]: Anselm Spoerri The Early Detection of Motion Boundaries May 1990 ftp://publications.ai.mit.edu/ai-publications/1000-1499/AITR-1275.ps ftp://publications.ai.mit.edu/ai-publications/pdf/AITR-1275.pdf This thesis shows how to detect boundaries on the basis of motion information alone. The detection is performed in two stages: (i) the local estimation of motion discontinuities and of the visual flowsfield; (ii) the extraction of complete boundaries belonging to differently moving objects. For the first stage, three new methods are presented: the "Bimodality Tests,'' the "Bi-distribution Test,'' and the "Dynamic Occlusion Method.'' The second stage consists of applying the "Structural Saliency Method,'' by Sha'ashua and Ullman to extract complete and unique boundaries from the output of the first stage. The developed methods can successfully segment complex motion sequences.
AIM-1277 Author[s]: Lynn Andrea Stein Imagination and Situated Cognition February 1991 ftp://publications.ai.mit.edu/ai-publications/1000-1499/AIM-1277.ps ftp://publications.ai.mit.edu/ai-publications/pdf/AIM-1277.pdf A subsumption-based mobile robot is extended to perform cognitive tasks. Following directions, the robot navigates directly to previously unexplored goals. This robot exploits a novel architecture based on the idea that cognition uses the underlying machinery of interaction, imagining sensations and actions.
AIM-1278 Author[s]: Elizabeth Bradley Control Algorithms for Chaotic Systems March 1991 ftp://publications.ai.mit.edu/ai-publications/1000-1499/AIM-1278.ps ftp://publications.ai.mit.edu/ai-publications/pdf/AIM-1278.pdf This paper presents techniques that actively exploit chaotic behavior to accomplish otherwise-impossible control tasks. The state space is mapped by numerical integration at different system parameter values and trajectory segments from several of these maps are automatically combined into a path between the desired system states. A fine- grained search and high computational accuracy are required to locate appropriate trajectory segments, piece them together and cause the system to follow this composite path. The sensitivity of a chaotic system's state-space topology to the parameters of its equations and of its trajectories to the initial conditions make this approach rewarding in spite of its computational demands.
AIM-1280 Author[s]: A. Lumsdaine, J.L. Wyatt, Jr. and I.M. Elfadel Nonlinear Analog Networks for Image Smoothing and Segmentation January 1991 ftp://publications.ai.mit.edu/ai-publications/1000-1499/AIM-1280.ps ftp://publications.ai.mit.edu/ai-publications/pdf/AIM-1280.pdf Image smoothing and segmentation algorithms are frequently formulatedsas optimization problems. Linear and nonlinear (reciprocal) resistivesnetworks have solutions characterized by an extremum principle. Thus,sappropriately designed networks can automatically solve certainssmoothing and segmentation problems in robot vision. This papersconsiders switched linear resistive networks and nonlinear resistivesnetworks for such tasks. The latter network type is derived from thesformer via an intermediate stochastic formulation, and a new resultsrelating the solution sets of the two is given for the "zerostermperature'' limit. We then present simulation studies of severalscontinuation methods that can be gracefully implemented in analog VLSIsand that seem to give "good'' results for these non- convexsoptimization problems.
AITR-1281 Author[s]: Chris Hanson MIT Scheme Reference Manual January 1991 ftp://publications.ai.mit.edu/ai-publications/1000-1499/AITR-1281.ps ftp://publications.ai.mit.edu/ai-publications/pdf/AITR-1281.pdf MIT Scheme is an implementation of the Scheme programming language that runs on many popular workstations. The MIT Scheme Reference Manual describes the special forms, procedures, and datatypes provided by the implementation for use by application programmers.
AIM-1282 Author[s]: Thomas Knight and Henry M. Wu A Method for Skew-free Distribution of Digital Signals Using Matched Variable Delay Lines March 1992 ftp://publications.ai.mit.edu/ai-publications/1000-1499/AIM-1282.ps.Z ftp://publications.ai.mit.edu/ai-publications/pdf/AIM-1282.pdf The ability to distribute signals everywhere in a circuit with controlled and known delays is essential in large, high-speed digital systems. We present a technique by which a signal driver can adjust the arrival time of the signal at the end of the wire using a pair of matched variable delay lines. We show an implemention of this idea requiring no extra wiring, and how it can be extended to distribute signals skew-free to receivers along the signal run. We demonstrate how this scheme fits into the boundary scan logic of a VLSI chip.
AITR-1283 Author[s]: Brian A. LaMacchia Basis Reduction Algorithms and Subset Sum Problems June 1991 ftp://publications.ai.mit.edu/ai-publications/1000-1499/AITR-1283.ps ftp://publications.ai.mit.edu/ai-publications/pdf/AITR-1283.pdf This thesis investigates a new approach to lattice basis reduction suggested by M. Seysen. Seysen's algorithm attempts to globally reduce a lattice basis, whereas the Lenstra, Lenstra, Lovasz (LLL) family of reduction algorithms concentrates on local reductions. We show that Seysen's algorithm is well suited for reducing certain classes of lattice bases, and often requires much less time in practice than the LLL algorithm. We also demonstrate how Seysen's algorithm for basis reduction may be applied to subset sum problems. Seysen's technique, used in combination with the LLL algorithm, and other heuristics, enables us to solve a much larger class of subset sum problems than was previously possible.
AITR-1284 Author[s]: Henry Minsky A Parallel Crossbar Routing Chip for a Shared Memory Multiprocessor March 1991 ftp://publications.ai.mit.edu/ai-publications/1000-1499/AITR-1284.ps ftp://publications.ai.mit.edu/ai-publications/pdf/AITR-1284.pdf This thesis describes the design and implementation of an integrated circuit and associated packaging to be used as the building block for the data routing network of a large scale shared memory multiprocessor system. A general purpose multiprocessor depends on high-bandwidth, low-latency communications between computing elements. This thesis describes the design and construction of RN1, a novel self-routing, enhanced crossbar switch as a CMOS VLSI chip. This chip provides the basic building block for a scalable pipelined routing network with byte- wide data channels. A series of RN1 chips can be cascaded with no additional internal network components to form a multistage fault-tolerant routing switch. The chip is designed to operate at clock frequencies up to 100Mhz using Hewlett- Packard's HP34 $1.2\mu$ process. This aggressive performance goal demands that special attention be paid to optimization of the logic architecture and circuit design.
AIM-1285 Author[s]: Daniel Kersten and Heinrich Bulthoff Apparent Opacity Affects Perception of Structure from Motion January 1991 ftp://publications.ai.mit.edu/ai-publications/1000-1499/AIM-1285.ps ftp://publications.ai.mit.edu/ai-publications/pdf/AIM-1285.pdf The judgment of surface attributes such as transparency or opacity is often considered to be a higher-level visual process that would make use of low-level stereo or motion information to tease apart the transparent from the opaque parts. In this study, we describe a new illusion and some results that question the above view by showing that depth from transparency and opacity can override the rigidity bias in perceiving depth from motion. This provides support for the idea that the brain's computation of the surface material attribute of transparency may have to be done either before, or in parallel with the computation of structure from motion.
AIM-1286 Author[s]: Feng Zhao Phase Space Navigator: Towards Automating Control Synthesis in Phase Spaces for Nonlinear Control Systems April 1991 ftp://publications.ai.mit.edu/ai-publications/1000-1499/AIM-1286.ps ftp://publications.ai.mit.edu/ai-publications/pdf/AIM-1286.pdf We develop a novel autonomous control synthesis strategy called Phase Space Navigator for the automatic synthesis of nonlinear control systems. The Phase Space Navigator generates global control laws by synthesizing flow shapes of dynamical systems and planning and navigating system trajectories in the phase spaces. Parsing phase spaces into trajectory flow pipes provide a way to efficiently reason about the phase space structures and search for global control paths. The strategy is particularly suitable for synthesizing high-performance control systems that do not lend themselves to traditional design and analysis techniques.
AIM-1287 Author[s]: Federico Girosi Models of Noise and Robust Estimates November 1991 ftp://publications.ai.mit.edu/ai-publications/1000-1499/AIM-1287.ps.Z ftp://publications.ai.mit.edu/ai-publications/pdf/AIM-1287.pdf Given n noisy observations g; of the same quantity f, it is common use to give an estimate of f by minimizing the function Eni=1(gi-f)2. From a statistical point of view this corresponds to computing the Maximum likelihood estimate, under the assumption of Gaussian noise. However, it is well known that this choice leads to results that are very sensitive to the presence of outliers in the data. For this reason it has been proposed to minimize the functions of the form Eni=1V(gi-f), where V is a function that increases less rapidly than the square. Several choices for V have been proposed and successfully used to obtain "robust" estimates. In this paper we show that, for a class of functions V, using these robust estimators corresponds to assuming that data are corrupted by Gaussian noise whose variance fluctuates according to some given probability distribution, that uniquely determines the shape of V.
AIM-1288 Author[s]: Federico Girosi and Gabriele Anzellotti Convergence Rates of Approximation by Translates March 1992 ftp://publications.ai.mit.edu/ai-publications/1000-1499/AIM-1288.ps.Z ftp://publications.ai.mit.edu/ai-publications/pdf/AIM-1288.pdf In this paper we consider the problem of approximating a function belonging to some funtion space ø by a linear comination of n translates of a given function G. Ussing a lemma by Jones (1990) and Barron (1991) we show that it is possible to define function spaces and functions G for which the rate of convergence to zero of the erro is 0(1/n) in any number of dimensions. The apparent avoidance of the "curse of dimensionality" is due to the fact that these function spaces are more and more constrained as the dimension increases. Examples include spaces of the Sobolev tpe, in which the number of weak derivatives is required to be larger than the number of dimensions. We give results both for approximation in the L2 norm and in the Lc norm. The interesting feature of these results is that, thanks to the constructive nature of Jones" and Barron"s lemma, an iterative procedure is defined that can achieve this rate.
AIM-1289 Author[s]: Tomaso Poggio, Allessandro Verri and Vincent Torre Green Theorems and Qualitative Properties of the Optical Flow April 1991 ftp://publications.ai.mit.edu/ai-publications/1000-1499/AIM-1289.ps ftp://publications.ai.mit.edu/ai-publications/pdf/AIM-1289.pdf How can one compute qualitative properties of the optical flow, such as expansion or rotation, in a way which is robust and invariant to the position of the focus of expansion or the center of rotation? We suggest a particularly simple algorithm, well-suited to VLSI implementations, that exploits well-known relations between the integral and differential properties of vector fields and their linear behaviour near singularities.
AIM-1291 Author[s]: Minoru Maruyama, Federico Girosi and Tomaso Poggio A Connection Between GRBF and MLP April 1992 ftp://publications.ai.mit.edu/ai-publications/1000-1499/AIM-1291.ps ftp://publications.ai.mit.edu/ai-publications/pdf/AIM-1291.pdf Both multilayer perceptrons (MLP) and Generalized Radial Basis Functions (GRBF) have good approximation properties, theoretically and experimentally. Are they related? The main point of this paper is to show that for normalized inputs, multilayer perceptron networks are radial function networks (albeit with a non-standard radial function). This provides an interpretation of the weights w as centers t of the radial function network, and therefore as equivalent to templates. This insight may be useful for practical applications, including better initialization procedures for MLP. In the remainder of the paper, we discuss the relation between the radial functions that correspond to the sigmoid for normalized inputs and well-behaved radial basis functions, such as the Gaussian. In particular, we observe that the radial function associated with the sigmoid is an activation function that is good approximation to Gaussian basis functions for a range of values of the bias parameter. The implication is that a MLP network can always simulate a Gaussian GRBF network (with the same number of units but less parameters); the converse is true only for certain values of the bias parameter. Numerical experiments indicate that this constraint is not always satisfied in practice by MLP networks trained with backpropagation. Multiscale GRBF networks, on the other hand, can approximate MLP networks with a similar number of parameters.
AIM-1293 Author[s]: Rodney A. Brooks Intelligence Without Reason April 1991 ftp://publications.ai.mit.edu/ai-publications/1000-1499/AIM-1293.ps ftp://publications.ai.mit.edu/ai-publications/pdf/AIM-1293.pdf Computers and Thought are the two categories that together define Artificial Intelligence as a discipline. It is generally accepted that work in Artificial Intelligence over the last thirty years has had a strong influence on aspects of computer architectures. In this paper we also make the converse claim; that the state of computer architecture has been a strong influence on our models of thought. The Von Neumann model of computation has lead Artificial Intelligence in particular directions. Intelligence in biological systems is completely different. Recent work in behavior-based Artificial Intelligenge has produced new models of intelligence that are much closer in spirit to biological systems. The non-Von Neumann computational models they use share many characteristics with biological computation.
AITR-1294 Author[s]: Larry R. Dennison Reliable Interconnection Networks for Parallel Computers October 1991 ftp://publications.ai.mit.edu/ai-publications/1000-1499/AITR-1294.ps ftp://publications.ai.mit.edu/ai-publications/pdf/AITR-1294.pdf This technical report describes a new protocol, the Unique Token Protocol, for reliable message communication. This protocol eliminates the need for end-to-end acknowledgments and minimizes the communication effort when no dynamic errors occur. Various properties of end-to-end protocols are presented. The unique token protocol solves the associated problems. It eliminates source buffering by maintaining in the network at least two copies of a message. A token is used to decide if a message was delivered to the destination exactly once. This technical report also presents a possible implementation of the protocol in a worm-hole routed, 3-D mesh network.
AITR-1295 Author[s]: James M. Hyde Multiple Mode Vibration Suppression in Controlled Flexible Systems May 1991 ftp://publications.ai.mit.edu/ai-publications/1000-1499/AITR-1295.ps ftp://publications.ai.mit.edu/ai-publications/pdf/AITR-1295.pdf Prior research has led to the development of input command shapers that can reduce residual vibration in single- or multiple-mode flexible systems. We present a method for the development of multiple-mode shapers which are simpler to implement and produce smaller response delays than previous designs. An MIT / NASA experimental flexible structure, MACE, is employed as a test article for the validation of the new shaping method. We examine the results of tests conducted on simulations of MACE. The new shapers are shown to be effective in suppressing multiple-mode vibration, even in the presence of mild kinematic and dynamic non-linearities.
AITR-1296 Author[s]: Joachim Heel Temporal Surface Reconstruction May 1991 ftp://publications.ai.mit.edu/ai-publications/1000-1499/AITR-1296.ps ftp://publications.ai.mit.edu/ai-publications/pdf/AITR-1296.pdf This thesis investigates the problem of estimating the three-dimensional structure of a scene from a sequence of images. Structure information is recovered from images continuously using shading, motion or other visual mechanisms. A Kalman filter represents structure in a dense depth map. With each new image, the filter first updates the current depth map by a minimum variance estimate that best fits the new image data and the previous estimate. Then the structure estimate is predicted for the next time step by a transformation that accounts for relative camera motion. Experimental evaluation shows the significant improvement in quality and computation time that can be achieved using this technique.
AIM-1297 Author[s]: Ellen C. Hildreth Recovering Heading for Visually-Guided Navigation June 1991 ftp://publications.ai.mit.edu/ai-publications/1000-1499/AIM-1297.ps ftp://publications.ai.mit.edu/ai-publications/pdf/AIM-1297.pdf We present a model for recovering the direction of heading of an observer who is moving relative to a scene that may contain self-moving objects. The model builds upon an algorithm proposed by Rieger and Lawton (1985), which is based on earlier work by Longuet-Higgens and Prazdny (1981). The algorithm uses velocity differences computed in regions of high depth variation to estimate the location of the focus of expansion, which indicates the observer’s heading direction. We relate the behavior of the proposed model to psychophysical observations regarding the ability of human observers to judge their heading direction, and show how the model can cope with self-moving objects in the environment. We also discuss this model in the broader context of a navigational system that performs tasks requiring rapid sensing and response through the interaction of simple task-specific routines.
|
|
