leff@smu.UUCP (Laurence Leff) (04/20/88)
The following technical reports are from The Robotics Institute of Carnegie Mellon University, and may be ordered from Nancy Serviou@fas.ri.cmu.edu Inspecting Money: How to Avoid Negative Bucks Robert Thibadeau January 1987 CMU-RI-TR-87-1 The focus of the activity of the Inspection Laboratory in the past several years has been high-speed inspection of patterned surfaces. The Bureau of Engraving prints money on a high-speed "web," which means that large sheets of money are being produced very fast. The question is raised of how to inspect for the print quality at those speeds. People will see either a blur or only a sample of the print. In this report, we use our past experiences to attempt to detail the inspection methods, hardware, etcetera, which would be needed to construct a hypothetical "inspect-a-buck" system, and the problems that might be encountered along the way. @i<(12 pages)> Problems of Automatic Vectorization of Artwork Robert Thibadeau January l987 CMU-RI-TR-87-2 A number of attempts have been made to scan printed wiring artwork, or drawings of circuit layouts, for automatic entry into computer aided design systems. Several commercial machines are available which accomplish forms of artwork vectorization. The Inspection Laboratory, under the sponsorship of Visual Understanding Systems, Inc., has worked on the problem of vectorization. Most recently this work is based on a small, relatively inexpensive, vectorization system composed of an IBM/XT, custom electronics hardware, and 300 DPI scanner. This report will summarize our findings to date and indicate the capability of current "vectorization" technology. @i<(13 pages)> Prototype Software for Automatic Generation of On-Line Control Programs for Discrete Manufacturing Processes Gregg Ekberg and Bruce H. Krogh February l987 CMU-RI-TR-87-3 This report describes prototype software for automatically generating control programs for discrete manufacturing processes from a high-level description of the system control logic. The control logic is synthesized from a specification of the physical resource states required for each operation in the process. The software described in this report allows the user to specify interactively the operation sequencing logic and the actuators and sensors for each stage of the process. This information is then used to automatically generate code for on-line control computers. The current implementation supports binary sensor and actuator signals. The methodology is illustrated for the automatic generation of instruction list (IL) code to control a conveyor system in an existing robotic assembly plant. @i<(32 pages)> Experimental Evaluation of Nonlinear Feedback and Feedforward Control Schemes for Manipulators Pradeep K. Khosla and Takeo Kanade March 1987 CMU-RI-TR-87-4 The manipulator trajectory tracking control problem revolves around computing the torques to be applied to achieve accurate tracking. While this problem has been extensively studied in simulations, the real-time results have been lacking in the robotics literature. In this paper, we present the experimental results of the real-time performance of model-based control algorithms. We compare the computed-torque control scheme with the feedforward dynamics compensation scheme. The feedforward scheme compensates for the manipulator dynamics in the feedforward path while the computed-torque scheme uses the dynamics in the feedback loop for linearization and decoupling. The manipulator control schemes have been implemented on the CMU DD Arm II with a sampling period of 2 @i<ms.> @i<(23 pages)> Choosing Sampling Rates for Robot Control Pradeep K. Khosla March 1987 CMU-RI-TR-87-5 In our previous research, we experimentally implemented and evaluated the effect of dynamics compensation in model-based control algorithms. In this paper, we evaluate the effect of changing the control sampling period on the performance of the computed-torque and independent joint control schemes. While the former utilizes the complete dynamics model of the manipulator, the latter assumes a decoupled and linear model of the manipulator dynamics. We discuss the design of controller gains for both the computed-torque and the independent joint control schemes and establish a framework for comparing their trajectory tracking performance. Our experiments show that within each scheme the trajectory tracking accuracy varies slightly with the change of the sampling rate. However, at low sampling rates the computed-torque scheme outperforms the independent joint control scheme. Based on our experimental results, we also conclusively establish the importance of high sampling rates as they result in an increased stiffness of the system. @i<(15 pages)> Real-Time Implementation and Evaluation of Computed-Torque Scheme Pradeep K. Khosla and Takeo Kanade March 1987 CMU-RI-TR-87-6 This paper presents the experimental results of the real-time performance of model-based control algorithms. We compare the computed-torque scheme which utilizes the complete dynamics model of the manipulator with the independent joint control scheme which assumes a decoupled and linear model of the manipulator dynamics. The two manipulator control schemes have been implemented on the CMU DD Arm II with a sampling period of 2 @i<ms.> We discuss the design of controller gains for both the computed-torque and the independent joint control schemes and establish a framework for comparing their trajectory tracking performance. Our investigation shows that the computed-torque scheme outperforms the independent joint control scheme as long as there is no torque saturation in the actuators. Based on our experimental results, we conclusively establish the importance of compensating for the nonlinear Coriolis and centrifugal forces even at low speeds of operation. This represents an important result because it serves to resolve the controversy about the need to compensate for these forces at low speeds of operation. @i<(24 pages)> An Algorithm to Estimate Manipulator Dynamics Parameters Pradeep K. Khosla and Takeo Kanade March 1987 CMU-RI-TR-87-7 This paper presents algorithms for identifying parameters of an @i<N> degrees-of-freedom robotic manipulator. First, we outline the fundamental properties of the Newton-Euler formulation of robot dynamics from the view point of parameter identification. We then show that the Newton-Euler model, which is nonlinear in the dynamic parameters, can be transformed into an equivalent modified model which is linear in dynamic parameters. We develop both on-line and off-line parameter estimation procedures. To illustrate our approach, we identify the dynamic parameters of the cylindrical robot, and the three degree-of-freedom positioning system of the CMU Direct-Drive Arm II. The experimental implementation of our algorithm to estimate the dynamics parameters of the six degrees-of-freedom CMU DD Arm II is also presented. @i<(24 pages)> Estimation of Robot Dynamics Parameters: Theory and Application Pradeep K. Khosla March 1987 CMU-RI-TR-87-8 This paper presents an algorithm for estimating the dynamics parameters of an @i<N> degrees-of-freedom robotic manipulator. In our previous work it was shown that the Newton-Euler model which is nonlinear in the dynamic parameters can be transformed into an equivalent @i<modified> model which is linear in dynamic parameters. To introduce our identification algorithm, we cast this @i<modified> Newton-Euler model in a form wherein the joint torques/forces are expressed as a product of a matrix and a vector of dynamics parameters. The elements of this matrix are a function of the joint variables and the kinematic parameters only. The dynamics parameters are then estimated from this linear (in dynamics parameters) formulation using the least squares estimation method. We have implemented our algorithm, and the results of this experimental implementation to estimate the dynamics parameters of the six degrees-of-freedom CMU DD Arm II are presented. The estimated dynamics parameters have also been used to evaluate the effect of dynamics compensation in model-based manipulator control methods. @i<(19 pages)> Automatic Robot Initialization Using a Planar Target Scanned by an Optical Reflection Sensor R. Q. Yang and M. W. Siegel April 1987 CMU-RI-TR-87-9 We describe an automatic initialization scheme for finding a point of coincidence between a robot's internal coordinate system and the coordinate system of its work space. Our method uses an optical transmitter-receiver pair mounted on the robot end effector to scan a T-shaped planar target mounted on the work surface. An automated iterative method for moving a point on the end effector into precise coincidence with the point of intersection between a sensed plane parallel to the work surface and a sensed line normal to the work surface is shown to converge rapidly. @i<(15 pages)> Using Goal Interactions to Guide Planning: The Program Model Caroline Hayes April 1987 CMU-RI-TR-87-10 The Machinist program uses a new planning method that is an extension to domain dependent planning technology. It is modeled after the behavior of human machinists, and makes plans for fabricating metal parts using machine tools. Many existing planning programs rely on a problem solving strategy that involves fixing problems in plans only after they occur. The result is that planning time may be wasted when a bad plan is unnecessarily generated and must be thrown out or modified. The Machinist program improves on these methods by looking for cues in the problem specification that may indicate potential difficulties or conflicting goal interactions, before generating any plans. It plans around those difficulties, greatly increasing the probability of producing a good plan on the first try. Planning efficiency is greatly increased when false starts can be eliminated. The machinist program contains about 180 OPS5 rules, and has been judged by experienced machinists to make plans that are, on the average, better than those of a 5 year journeyman. The knowledge that makes the technique effective is domain dependent, but the technique itself can be used in other domains. @i<(17 pages)> 1986 Year End Report for Road Following at Carnegie Mellon Charles Thorpe and Takeo Kanade Principal Investigators May 1987 CMU-RI-TR-87-11 This report describes progress in vision and navigation for outdoor mobile robots at the Carnegie Mellon Robotics Institute during 1986. This research was sponsored by @c(DARPA) as part of the Strategic Computing Initiative. Our work during 1986 culminated in two demonstration systems. The first system drives the Terregator, a desk-sized robot with six wheels, around the network of campus sidewalks. This system, named Sidewalk II, uses a video camera to follow sidewalks and a laser rangefinder to detect and avoid stairs. Sidewalk II makes extensive use of map data, for visual predictions and for path planning. The second system, Park Navigation, uses the Navlab, our new Chevrolet Van robot. The Park system concentrated on vision for following difficult roads, including curves, dirt and leaves, shadows, puddles, and both moving and fixed obstacles. We developed vision techniques for handling difficult roads, and built range finder programs for detecting and avoiding obstacles. Both the Sidewalk II and Park experiments were built into complete systems using @c(Codger), a novel whiteboard developed as part of the project. @c(Codger) provides tools for handling geometry, motion over time, multiple processes, multiple processors, and multiple languages. This report is divided into four main sections. Section 1 is an introduction and overview, including a chronology for the project and a list of 1986 publications. Section 2 describes the Sidewalk II system; section 3 describes the Park experiments, and section 4 is about @c(Codger). @i<(60 pages)> Optimal Design of Robotic Manipulator Trajectories: A Nonlinear Programming Approach Mark L. Nagurka and Vincent Yen April 1987 CMU-RI-TR-87-12 A nonlinear programming approach for the optimal motion planning of robotic manipulators is presented. In this approach, a standard optimal control problem of infinite dimensionality (in time) is converted into an optimization problem of finite dimensionality by approximating the manipulator trajectories by the sum of a polynomial and a set of appropriate eigenfunctions. The optimal control problem is then solved via a nonlinear programming numerical algorithm, given a performance index which is a continuous (explicit or implicit) function of time. This method can be used for trajectory planning of high degree-of-freedom manipulators, once motion specifications and constraints have been identified. Examples of trajectory planning of a planar robotic manipulator with free and constrained final time and states are presented. @i<(25 pages)> Management of Temporal Constraints for Factory Scheduling Claude Le Pape and Stephen F. Smith May 1987 CMU-RI-TR-87-13 In this paper, we present constraint propagation techniques used in the OPIS scheduling system to update schedule descriptions and detect introduced inconsistencies. Our approach is summarized as follows: @begin(itemize) A Hierarchical model is used to represent resources and operations to be performed. Schedules are developed and maintained at different levels of precision which are explicitly associated with resources and operations; constraint propagation is correspondingly performed at different levels. Various scheduling constraints are attached to resources and operations, and combined to derive time bound constraints. A description of the original constraints that collectively impose a bound is explicitly recorded. Time bound constraints are maintained by an object-oriented propagation process: through messages, resources and operations communicate constraints and cooperate to compute time bounds. When time bounds are inconsistent, their origins provide the information required to construct an appropriate description of the conflicting situation. This description provides OPIS with information needed to make reactive decisions. @i<(11 pages)> @end(itemize) LISP as a Rapid Prototyping Environment: The Chinese Tutor Dario Giuse June 1987 CMU-RI-TR-87-14 Conventional wisdom has maintained that while LISP is suitable for the development of experimental software, it does not support production-quality systems well. This report describes a building-block approach where a complex system (an intelligent Chinese language tutor) was built in a LISP environment out of a series of powerful tools. The resulting system does not in any way sacrifice performance for power and flexibility. @i<(14 pages)> End of Year Report for Parallel Vision Algorithm Design and Implementation January 15, 1986--January 14, 1987 Takeo Kanade and Jon A. Webb June 1987 CMU-RI-TR-87-15 The parallel vision algorithm design and implementation project was established to facilitate vision programming on parallel architectures, particularly low-level vision and robot vehicle control algorithms on the Carnegie Mellon Warp machine. To this end, we have (1) demonstrated the use of the Warp machine in several different algorithms; (2) developed a specialized programming language, called Apply, for low-level vision programming on parallel architectures in general, and Warp in particular; (3) used Warp as a research tool in vision, as opposed to using it only for research in parallel vision; (4) developed a significant library of low-level vision programs for use on Warp. @i<(24 pages)> Implementation and Performance of a Complex Vision System on a Systolic Array Machine Ed Clune, Jill D. Crisman, Gudrun J. Klinker, and Jon A. Webb June 1987 CMU-RI-TR-87-16 Complex vision systems are usually quite slow, requiring tens of seconds or minutes of computer time for each image. As the complexity and experimental nature of the system increases, the speed is especially low, since all components of the system must be optimized if the system is to show good performance. The FIDO system, a stereo vision system for controlling a robot vehicle, has existed for a number of years and has been implemented on a number of different computers. These computers have ranged from a DEC KL10 to the current implementation on the Warp machine, a 100 Million Floating-point Operations Per Seconds (MFLOPS) systolic array machine. FIDO has shown an enormous range in speed; its ancestor took 15 minutes per step, while the Warp implementation takes less than 5 seconds per step. Moreover, while early versions of FIDO moved in slow, start-and-stop steps, FIDO now runs continuously at 100 mm/second. We review the history of the FIDO system, discuss its implementation on different computers, and concentrate on its current Warp implementation. @i<(18 pages)> Low-Level Vision on Warp and the Apply Programming Model Leonard G. C. Hamey, Jon A. Webb, and I-Chen Wu July 1987 CMU-RI-TR-87-17 In the course of implementing low-level (image to image) vision algorithms on Warp, we have understood the mapping of this class of algorithms well enough so that the programming of these algorithms is now a straightforward and stereotypical task. The partitioning method used is input partitioning, which provides an efficient, natural implementation of this class of algorithms. We have developed a special programming language called Apply, which reduces the problem of writing the algorithm for this class of programs to the task of writing the function to be applied to a window around a single pixel. Apply provides a method for programming Warp in these applications which is easy, consistent, and efficient. Apply is application specific, but machine independent@y(M)it is possible to implement versions of Apply which run efficiently on a wide variety of computers. We describe implementations of Apply on Warp, UNIX and the Hughes HBA, and sketch implementation on bit-serial processor arrays and distributed memory machines. @i<(16 pages)> The Warp Computer: Architecture, Implementation, and Performance Marco Annaratone, Emmanuel Arnould, Thomas Gross, H. T. Kung, Monica Lam, Onat Menzilcioglu, Jon A. Webb July 1987 CMU-RI-TR-87-18 The Warp machine is a systolic array computer of linearly connected cells, each of which is a programmable processor capable of performing 10 million floating-point operations per second (10 MFLOPS). A typical Warp array includes 10 cells, thus having a peak computation rate of 100 MFLOPS. The Warp array can be extended to include more cells to accommodate applications capable of using the increased computational bandwidth. Warp is integrated as an attached processor into a @c(UNIX) host system. Programs for Warp are written in a high-level language supported by an optimizing compiler. The first 10-cell prototype was completed in February 1986; delivery of production machines started in April 1987. Extensive experimentation with both the prototype and production machines has demonstrated that the Warp architecture is effective in the application domain of robot navigation, as well as in other fields such as signal processing, scientific computation, and computer vision research. For these applications, Warp is typically several hundred times faster than a VAX 11/780 class computer. This paper describes the architecture, implementation and performance of the Warp machine. Each major architectural decision is discussed and evaluated with system, software and application considerations. The programming model and tools developed for the machine are also described. The paper concludes with performance data for a large number of applications. @i<(25 pages)> Learning Functions from Examples B. K. Natarajan August 1987 CMU-RI-TR-87-19 This paper concerns algorithms that "learn" functions from examples. Functions on strings of a finite alphabet are considered and the notion of dimensionality defined for families of such functions. Using this notion, a theorem is proved identifying the most general conditions under which a family of functions can be efficiently learned from examples. Turning to some familiar families, we present strong evidence against the existence of efficient algorithms for learning the regular functions and the polynomial time computable functions, even if the size of the encoding of the function to be learned is given. Our arguments hinge on a new complexity measure--the constraint complexity. @i<(14 pages)> The Metallurgical Database of Aladin--an Alloy Design System I. Hulthage, M. Przystupa, M. L. Farinacci, and M. D. Rychener August 1987 CMU-RI-TR-87-20 Aladin is an expert system that aids metallurgists in the design of new aluminum alloys. Declarative structured representations in the form of schemata are used for metallurgical data and concepts. The representation is very general: the goal has been to create a representation for all knowledge about aluminum alloys and metallurgy relevant to the design process. This article gives an overview of the alloy database and describes the architecture of the microstructure database in detail. The microstructure of alloys is described by an enumeration of the types of microstructural elements present along with their characteristics. @i<(14 pages)> Object Recognition on a Systolic Array Claire M. Bono and Jon A. Webb September 1987 CMU-RI-TR-87-21 Computer vision systems for recognition include both the extraction of features and the matching of those features with a known model. Traditionally, the most time consuming step has been feature extraction, but new parallel architectures are removing the bottleneck at this level. Once features have been extracted from an image, considerable geometric search is still necessary to form relationships between the extracted features and to match those features and feature aggregates with a model. One can take advantage of certain constraints about the appearance of an object, but with complex images or multiple models, intensive processing is still required. We have developed some algorithms for doing these geometric search operations in parallel on iWarp, a long linear array of VLSI processing elements currently being designed by Carnegie Mellon and Intel Corporation. We have simulated a system which uses these algorithms to do an object recognition task (after low-level vision) almost completely on a 72 processor iWarp array. An analysis of this system indicates a speedup by a factor of roughly 100 to 250 over a sequential version running on a VAX 8650. @i<(15 pages)> The Automated Craftsman, Preliminary Research David Alan Bourne November 1987 CMU-RI-TR-87-22 The Automated Craftsman is a combination of efforts that have resulted from our past work with Westinghouse, our new work with the Expert Machinist Consortium, and current support from the Air Force. The Air Force project is called the Intelligent Machining Workstation (IMW) and as such is the major research catalyst for our group. The IMW project's major goal is to replace the skills of the metal working craftsman in order to make the first part right. The chapters in this report outline the preliminary research of the IMW group to achieve this end, while integrating the results into the general objectives of the laboratory: The Automated Craftsman. The results reported here indicate a strong need to use hybrid qualitative and quantitative methods for process planning, process control, process monitoring (i.e., sensors) and workholding (i.e., fixtures and grippers). To accomplish this, we have knowledge engineered the methods of the human craftsman and as appropriate, encoded their methods. Finally, we review available workstations in consideration of the IMW's implementation. @i<(116 pages)> KR: An Efficient Knowledge Representation System Dario Giuse October 1987 CMU-RI-TR-87-23 KR is a very efficient semantic network knowledge representation language implemented in Common Lisp. It provides basic mechanisms for knowledge representation which include user-defined inheritance, relations, and the usual repertoire of knowledge manipulation functions. The system is simple and compact and does not include some of the more complex functionality often found in other knowledge representation systems. Because of its simplicity, however, KR is highly optimized and offers good performance. These qualities make it suitable for many applications which require a mixture of good performance and flexible knowledge representation. @i<(20 pages)> NAVLAB: An Autonomous Navigation Testbed Kevin Dowling, Rob Guzikowski, Jim Ladd Henning Pangels, Jeff Singh, and William Whittaker November 1987 CMU-RI-TR-87-24 The NavLab is a testbed for research in outdoor navigation, image understanding, and the role of human interaction with intelligent systems; it accommodates researchers and all computing onboard. The core of the NavLab is the vehicle controller, a multi-processor computer that controls all locomotion, actuation and physical sensing; it interacts with a computer host and human operator to implement varying degrees of autonomy. The chassis is a modified van with a computer-controllable, hydraulic drivetrain. The NavLab supports a choice of sensing to accommodate many types of navigation research. The technical report details the control computing and physical configuration of the NavLab vehicle. @i<(44 pages)> Two New Frameworks for Learning B. K. Natarajan November 1987 CMU-RI-TR-87-25 This paper presents two new formal frameworks for learning. The first framework requires the learner to approximate an unknown function, given examples for the function as well as some background information on it. It is shown that this framework is no more powerful than a framework that allows the learner to see examples but not background information. The second framework explores learning in the sense of improving computational efficiency as opposed to acquiring an unknown concept or function. Specifically, the framework concerns the acquisition of heuristics from examples over problem domains of special structure. A theorem is proved identifying some conditions sufficient to allow the efficient acquisition of heuristics over the aforementioned class of domains. @i<(14 pages)> Nancy Serviou@fas