SECURITY CLASSIFICATION OF THIS PAGE (When Data Entered) _ REPORT DOCUMENTATION PAGE BREA INSTCCTI ORM BEFORE COMPLETING FORM I. REPORT NUMBER 2. GOVT ACCESSION NO. 3. RECIPIENT'S CATALOG NUMBER 4. TITLE (and Subtitle) 5. TYPE OF REPORT & PERIOD COVERED COORDINATED RESEARCH in ROBOTICS and Interim INTEGRATED MANUFACTURING August 1, 1982-July 31, 1983 INTEGRATED MANUFACTURING 6. PERFORMING 01G. REPORT NUMBER RSD-TR-17-83 7. AUTHOR(s) 8. CONTRACT OR GRANT NUMBER(s) D.E. Atkins Co-principal Investigator R.A. Volz Co-principal Investigator F49620-82-C-0089 (see attached list) 9. PERFORMING ORGANIZATION NAME AND ADDRESS 10. PROGRAM ELEMENT, PROJECT, TASK AREA & WORK UNIT NUMBERS College of Engineering The Univesity of Michigan 61102F Ann Arbor, Michigan 48109 2306/A3 11. CONTROLLING OFFICE NAME AND ADDRESS 12. REPORT DATE USAF, AFSC October 28, 1983 Air Force Office of Scientific Research 13. NUMBER OF PAGES Building 410, Bolling AFB, D.C. 20332 136 14. MONITORING AGENCY NAME & ADDRESS(f different from Controlling Office) 15. SECURITY CLASS. (of this report) unclassified 15a. DECLASSIFICATION/DOWNGRADING SCHEDULE 16. DISTRIBUTION STATEMENT (of this Report) Unlimited distribution 17. DISTRIBUTION STATEMENT (of the abstract entered in Block 20,.if different from Report) Unlimited distribution 18. SUPPLEMENTARY NOTES 19. KEY WORDS (Continue on reverse side if necessary and identify by block number) Manufacturing Science, Robotics, Artificial Intelligence, Sensors, Tactile Sensors, Robot Control, Machine Vision, Special Purpose Processors, Motion Planning, Knowledge Based Systems, Requirements Analysis, Robot Programming, Optical Processing, Manufacturing Database, Manufacturing Cell Architecture 20. ABSTRACT (Continue on reverse side if necessary and identify by block number) The research procured under this contract is oriented toward the understanding and development of the flexible robot based manufacturing cells or "islands" which will increasingly become basic blocks for the building of modern parts production and assembly facilities. Present work spans a hierarchy of sub-systems oriented toward the development and integration of (see reverse side) DD JAN 73 1473 EDITION OF 1 NOV 65 IS OBSOLETE SECURITY CLASSIFICATION OF THIS P AGE (When Dets Entered)

SECURITY CLASSIFICATION OF THIS PAGEf(Whan Data Entered) high performance manipulators into flexible manufacturing cells. These subsystems may be divided into several levels of abstraction: Level 1 * The mechanical structure and low-level (small time-constant) control of high-performance manipulators, ~ The sensor sub-systems (force, tactile, thermal, and vision), * Computer architecture and languages which form the basis of robot systems and manufacturing cells. Level 2 * Integration of mechanical structure, computer system and sensor to form flexible robot systems Level 3 * The integration of systems with production and assembly machines and information contained in the manufacturer's computer-aided design database. Level 4 Integration of the factory-wide distributed database which is central to the design, production and business functions of manufacturing. The following items have been accomplished during the first year: * Development of an extensive computing and experimental environment * Initial results in laying a firm theoretical foundation to robot control and the development of new algorithms for both nonlinear and adaptive controls * Design and prototype implementation of high performance tactile and noncontact temperature sensors * Development and implementation of new high performance algorithms for edge detection, motion prediction and dynamic scene analysis * Development of algorithms for and partial implementation of CAD driven robot/vision cell * Development of algorithms for determining gripping positions from geometric models of parts * Development of low cost graphic robot programming systems. Development of algorithms for distributed knowledgebase data assignment and heuristic problem solving * Design of systems to generate interface forms between users and manufacturing databases SECURITY CLASSIFcAT1U ra Tup a /r'.F__ n......

Authors (continued) PROFESSORS: Milton A. Chace Gideon Frieder Elmer G. Gilbert Robert M. Howe Keki B. Irani Yoram Koren Emmett N. Leith Arch W. Naylor N. Harris McClamroch Kennsal D. Wise ASSOCIATE PROFESSORS: Ramesh Jain Dev. S. Kochhar Trevor N. Mudge Toby Teorey Anthony C, Woo ASSISTANT PROFESSORS: Edward J. Delp C.S. George Lee Kang G. Shin A. Galip Ulsoy Joseph Whitesell Mohamed Zarrugh

EXECUTIVE SUMMARY ANNUAL REPORT ON COORDINATED RESEARCH IN ROBOTICS AND INTEGRATED MANUFACTURING THE UNIVERSITY OF MICHIGAN Background The Center for Robotics and Integrated Manufacturing (CRIM) within the College of Engineering at the University of Michigan was established by act of the Regents in October 1981. The broad goals of the Center are * to foster and coordinate research related to the understanding and development of computer integrated manufacturing (the "factory of the future"); * to facilitate course and curriculum development appropriate to the education of the future engineers and researchers required by the modern manufacturing industry; and * to plan and acquire facilities required for the above two activities. CRIM is especially committed to research partnerships with government and industry and to liaison with the Industrial Technology Institute recently established in Ann Arbor. It is also charged with the task of working with the College departments to recruit new faculty, at all academic ranks, to supplement, and expand research and instruction activities in "CRIM areas." Eight faculty have been added in the past two years in these areas and at least four per year will be added over the coming three years. Joint recruiting with the Industrial Technology Institute has also begun. As shown in Figure E-l, the Center is composed of three research divisions: Robot Systems, Management Systems, and Integrated Design and Manufacturing, and involves about 40 faculty spanning the following departments of the College: Electrical and Computer Engineering, Computer Science, Mechanical Engineering and Applied Mechanics, Industrial Operations Engineering, Aerospace Engineering, Materials and Metalurgy, and Naval Architecture and Marine Engineering. Research in the three divisions covers a broad spectrum of topics commensurate with the span of these disciplines and is sponsored by a combination of internal, the federal government, and industrial funding. In August 1982 the Air Force Office of Scientific Research awarded a contract to CRIM as a "center of excellence" in manufacturing sciences. The procurement was for research to be be conducted principally within the Robot Systems Division of CRIM and it has become the keystone of their program. A relatively smaller level of effort is being supported within the Management Systems Division. This is the first annual report on the research activities of CRIM which are being supported under this AFOSR contract. Overview of AFOSR Sponsored Component of CRIM The portion of the CRIM research program procured by AFOSR is oriented to the understanding and development of flexible manufacturing cells or "islands" which will increasingly become basic blocks for the building of modern parts production and assembly facilities. These cells consist of machine tools, material handlers, and inspection sub-systems, integrated under a distributed, computer-based command and control Annual Report i August 1, 1982-July 31, 1983

The University of nicnigan College of Engineering Center for Robotics and Intrtedrat Manufacturlng O. E. Atkins Robot Systems Management Integrated Design Division Systems Division & Manufacturlng R. A. VOlZ W. Hancoc E. Lenz * SENSOR BASED * INFORMATION * PROCESSING ROBOT SYSTEMS MANAGEMENT * DESIGN DATABASES * ROBOT-BASED * HUMAN FACTORS C MANUFACTURING C -t PRODUCTION CELL PRODUCTION INTEGRATION CL L APLANNING AVIA LOCAL AREA * LANGUAGE AND QUALITY SPEIA pURPOSE' QUALITY NETWORKS SPECIAL PURPOSE COMPUTER * ADAPTIVE SUPPORT CONTROL Figure E-1. Organization and Research Topics of CRIM. system. An important component of such a cell is a very general purpose material handler, i.e. a "smart" industrial robot. As depicted in Figure E-2, the present work of the Robot and Management Systems Divisions span a hierarchy of sub-systems oriented toward the development and integration of high performance manipulators into flexible manufacturing cells. These sub-systems may be divided into several tasks at several levels of abstraction: High-performance manipulators - the mechanical structure and low-level (small timeconstant) control of high performance manipulators. Senlsor sub.systems - force, tactile, thermal, and vision subsystems for integration with Annual Report ii August 1, 1982-July 3i, 1983

AFOSR SUPPORTED TASK AREAS Sensor i Hlt-Pefrfornance Special Purpose Susystem Manipulators: Computers & Structure Control Lanages nr \ Sensor Based l Roiot Systems.;..........; Knowledge y buteddatabasesystemandheuristicproblemsolvingappliedto manufacturing cell con System Sse " Figure E-2. AFOSR supported task areas. areaswith he hihly vrsatie assmblyobot.... manipulators and inspection subsystems. Special-Purpose computers and languages - custom processors and languages for robot and manufacturing cell command and control. KInowledge systems and problem solving - use of a knowledge-base for design of a distributed database system and heuristic problem-solving applied to manufacturing cell control. Sensor based robot structures - the integration of output from all of the above research areas with the highly versatile assembly robot. Annual Report iii August 1, 1982-July 31, 1983

Robot based manufacturing cell - the distributed computer command and control system for the cell including the language interface to the human programmer and/or monitor. Special emphasis on the integration of the cell control system with production and assembly specifications contained in the manufacturer's "computer-aided design base." Integrated factory information system - Still higher levels of integration with the factory-wide distributed database which is central to both the production and business functions of manufacturing. First Year Activities The first year of effort is characterized by the following: * Acquisition, installation, and building of complex hardware and software interfaces between computer, sensor, and manipulator sub-systems which support the experimental components of the research. * A pattern of support intended to orient and extend aspects of the generic research of twenty-two faculty to one or more of the above levels of the future manufacturing environment and to do so in an interdisciplinary way. * Building of thesupport staff and high-quality cadre of graduate student research assistants necessary, not only to the specific research goals of the project, but also to the important by-product: production of trained manpower in disciplines vital to enhancing our industrial productivity. * Significant interaction with industry to discuss their problems, help orient our research, describe our capabilities, and solicit their supplementary support. The remainder of this summary will expand upon each of these dimensions of the first year of effort. Development of facilities for experimentation In many ways the move toward computer integrated manufacturing is a natural evolution of the computer revolution now made more economically feasible by advances in microelectronics. Core computing facilities are required to support algorithm development and analysis, control of prototype subsystems of the manufacturing cell, and shared-file authoring systems and electronic mail to enhance group coordination. Year 1 of this effort involved the acquisition of two computers, a VAX 11/780 and a VAX 11/750, and the integration into an existing computing environment in order to share expensive peripherals and communication networks. The larger VAX 11/780 is being used in a time-sharing mode for algorithm development and analysis associated with robot simulation, control, and machine vision. The smaller VAX 11/750 is used as the front-end for sensor data processing and for real-time control of the experimental robots. Although a gift, and not purchased under the contract, an Intel iAPX 432 advanced, Ada "object-based" computer system is playing a key role in research related to the command and control system for a manufacturing cell. Contract funds have supported the development of special interfaces (software and hardware) between this machine, a vision system, and an ASEA RB 6 robot (also an industrial gift). Other equipment purchased and installed in the experimental environment include a PUMIA 600 robot arm with a wrist force sensor and servo driven hand, a DeAnza image processAnnual Report iv August.1, 1982-July 31, 1983

ing system to augment the vision research facilities, and three graphics terminals. Core Research The emphasis of the first year's activity was on enabling faculty with established credentials to focus their research efforts on important problems in robotics and manufacturing science. The specific important problems detailed in the proposal were each allocated funds (approximate area levels developed in conjunction with AFOSR at the time of awarding of the contract) for faculty and student support. This ensured broad interdisciplinary participation by both faculty and students. A particular emphasis was placed on providing sufficient student support to allow progress to be made in each area. The following sections briefly overview the progress in each of the major research areas. High-performance manipulators: structure and control The extension of robot applications from relatively simple tasks such as pick and place, painting, welding and machine loading to less structured and higher throughput structures requires more understanding of manipulator structure, dynamics, and control. Enhancements are required in accuracy, repeatability, speed and energy usage; all in the context of collision avoidance constraints. Higher fidelity mathematical models of the complete manipulator are needed for two different but related purposes: * as a tool to study the design of alternate mechanical structures, especially lightweight, fast arms, and * as the nucleus of the real-time controller for manipulators. During this first year, seven faculty have explored aspects of such models and their translation into computer programs suitable for rapid evaluation both for mechanical analysis and online control. Specific research tasks relate to the following: * Efficient robot arm kinematics and dynamics. * Dynamic simulation of robot motions. * Application of nonlinear systems theory to mechanical manipulators. * Optimal control techniques to enhance robot performance. * Adaptive control of robot arms. * Manipulator compliance. Achievements during the first year include * Formulation of the dynamic equations of motion in forms which are amenable to efficient computation. * Simulation of a 6 link robot including nonlinear friction effects. i Algorithms for optimal trajectory planning (in a minimum time sense). * New necessary conditions for robot optimization problems expressed in implicit differential equations. * New effective algorithms for adaptive (to load and position changes) control. * Dynamic modeling and simulation of a robot including flexibility (bending modes) in the final link. Annual Report v August 1, 1982-July 31, 1983

Sensor subsystems Among the many challenges confronting the realization of advanced robots and automated manufacturing facilities, the need for improved sensor sub systems is one of the most critical. Sensors represent the primary path by which data on the environment, activity, or process being performed is gathered, and in spite of increasingly powerful processors, they are only as capable as their input data allows. With increasing levels of automation, greater emphasis must be put on sensor accuracy and reliability as well as their simple existence. In many cases, the needed sensors do not now exist, and in most cases those that do are inadequate in performance, reliability, or both. Specific research topics in these areas include * High-performance tactile imagers * Silicon thermal imagers for process control applications * High Performance edge detection. * Dynamic scene analysis. * 3-D surface reconstruction via vision. * Optimal feature matching for visual recognition of objects. * Application of optical processing to robotic vision. Specific achievements during this reporting period include * Several 2 x 2 tactile cell arrays have been built and tested, and an 8 x 8 tactile array has been designed. * Several prototype thermal imagers have been built and preliminary tests indicate an ability to detect a 1 deg. C change in 1 sq. cm at a distance of 20 meters. * A new edge detector has been developed. Comparisons indicate that it is significantly superior to others. 9 A real-time motion parameter estimation system has been developed and used to track a moving object in a sequence of visual scenes. * The feasibility of obtaining motion information from characteristics of optical flow without computation of optical flow itself has been established. * A visual recognition system using an optimally weighted matching of boundary segments of an image against those of a model has been developed and used to recognize highly occluded parts. * A technique for projecting partially incoherent light fringes on a surface using a diffraction grating has been developed. From these fringes three dimensional surface information can be obtained. Special purpose computers and languages Vision, force and tactile sensors are being developed and incorporated into robot systems, more precise control schemes are under development and the interaction of robot systems with computer aided design and other computer aided engineering databases offer the potential of placing considerable intelligence in future robot systems. With these developments, however, comes greatly increased demands for computational capability and greatly increased complexity of both the hardware and software systems required. Future systems will certainly use multi-processing, with a number of them Annual Report vi August 1, 1982-July 31, 1983

being special purposes and devices designed to achieve needed processing speed for computationally intensive subtasks, and the software necessary to operate these systems will be very large and complex in comparison to today's systems. Topics in this context under investigation are * Special processors for vision processing. * Graphical programming of robots. * The use of Ada as the basis for a robot programming language. * The use of object based computer systems for robotics. Achievements in these areas during the first year include. * A case study has been performed on a vision procedure for occluded parts to study possible multiprocessor implementations. As a consequence, a specific implementation will be begun during the next year. * A prototype graphical robot programming system has been developed using an IBM personal computer. * As a test, a vision system was implemented in Ada on an Intel iAPX 432 and an Ada package structure to support simple robot programming designed. * A multiprocessor object based structure was designed and implemented to control a TV camera for a vision system and control an ASEA RB 6 robot. Sensor-based robot systems As shown earlier in Figure E-2, the generic research in the three task areas cited above provide underpinnings for sensor-based robot systems. Such systems are important components of the manufacturing cell - a building block of the integrated factory. During the first year, the majority of work has been in the predecessor areas, however, we do have a marriage of work in force feedback robot control for active compliance insertion processes. A control strategy based upon "learning machine" pattern recognition techniques Was developed to make decisions based upon wrist force sensor data. A PUMA robot arm has been equipped with such a sensor, and computer interfaces and calibration software were completed. Robot-based manufacturing cell The next level of integration in the model of Figure E-2 is the cell level. Task areas supporting this level include * Algorithms for extracting information from CAD/CAE databases to aid in planning and programming robot and sensor actions. * Multiprocessor computer architectures to support complex configurations of equipment in manufacturing cells. * Generalized problem-solving using heuristics Accomplishments during the first year include * Criteria for good gripping positions on objects have been developed and algorithms determined and implemented for extracting the gripping positions from (CAD generated) geometrical models of the objects. * A theoretical model has been developed for determining the probability of finding an object in a given stable position. Experimental results match those of the Annual Report vii August 1, 1982-July 31, 1983

model very closely (usually within 1%). * Vision, robot and CAD based control subsystems of an experimental robot cell have been completed. * A heuristic approach to generalized problem-solving has been devised which permits parallelism and simplification in evaluation of distance of a given problem state from the goal problem state. Integrated factory information system The highest level of integration, largely the domain of the CRIM Management Systems division, is conducting research in the areas of * Knowledge based systems * User interface to complex distributed manufacturing databases * Requirements analysis for complex distributed databases. First year effort has yielded: * A technique has been devised in which the semantics of data and user queries at each site in a distributed system are exploited as a means of partitioning the relations about the entities in the database, and in which a mathematical programming technique is used to optimally allocate the fragments across the network. * To assist unsophisticated users in accessing information in a complex database, a form specification/query language, similar to the relational calculus which produces a form schema has been designed. * A survey of manufacturing organizations has been conducted to determine the nature of the manufacturing related information and information dissemination methods currently in use. A summary of personnel directly supported under this program is shown in Figure E-3. Modes of interaction between CRIM and the outside include: * Joint woks with the Industrial Technology Institute * Industrial contracts * Industrial executive briefings * Industrial affiliates program * International seminar series * Scholarly publications and meetings. Plans for the Second Year The second year of effort will emphasize the migration of research results from the upper blocks of figure E-2 into the lower. Annual Report viii August 1, 1982-July 31, 1983

PERSONNEL Faculty * 8 Professors * 3 Associate Professors * 6 Assistant Professors Graduate Students * 24 PhD Students (4 started summer 1983) * 11 Master's Degree Candidates (4 started summer 1983) * 5 Undergraduate Students (3 started summer 1983) Staff * 1 FTE Research Engineer * 1 Systems Programmer * 1 Technician * 1 50%0 Administrative Assistant * 2.5 FTE secretaries Figure E-3. Annual Report ix August 1 1, 982-July 31, 1983

Annual Report x August 1, 1982-July 31, 1983

TABLE OF CONTENTS 1. Introduction and Summary.............................................................. 1 1.1. Introduction.............................................................. 1 1.2. Overview of First Year........................................................................... 2 1.3. Report Organization.................................................................... 3 2. Facility Development.............................................................. 5 2.1. Computer and Image Processing Research Network............................ 5 2.2. New Facilities.................................................................. 6 3. Research Activities.............................................................. 9 3.1. The Control of Mechanical Manipulators.............................................. 10 3.1.1. Efficient Robot Arm Kinematics and Dynamics....................... 11 3.1.2. Simulation......................................................... 17 3.1.2.1. Real Time Simulation.............................................. 18 3.1.2.2. General Dynamic Simulation.................................... 19 3.1.3. Application of Nonlinear Systems Theory to Mechanical Manipulators......................................................... 20 3.1.4. Optimal Control Techniques to Enhance Robot Performance.................................................................................................... 2 4 3.1.4.1. Automatic Generation of State and Costate............ 24 3.1.4.2. Optimal Control and Trajectory Planning............... 25 3.1.5. Adaptive Control......................................................... 28 3.1.6. Manipulator Compliance........................................................... 32 3.2. Integrated Solid-State Sensors for Closed-Loop Robot Control............ 33 3.2.1. A 256-Element High-Performance Tactile Imager..................... 34 3.2.2. A Silicon Thermal Imager for Process Control Applications.................................................................................................... 4 1 3.2.3. Force Feedback Control for Insertion Process.......................... 46 3.3. Vision for Robotics............................................................ 47 3.3.1. Edge Detection Using Contour Tracing.................................... 48 3.3.2. Dynamic Scene Analysis........................................ 51 xi

3.3.2.1. Motion Parameter Estimation.................................. 52 3.3.2.2. Motion Estimation by Optical Flow......................... 53 3.3.3. Surface Reconstruction.............................................................. 53 3.3.3.1. Photometric Stereo.............................................. 54 3.3.3.2. Laser Shutter Camera............................................... 54 3.3.4. Determining Distinguishing Features of an Object for Visual R ecognition........................................................................ 55 3.3.5. Application of Optical Processing to Robotic Vision and Intelligence ~~~~~.~e ~~~*~o~~~***XX * ~~0~*~~*~* ~~~0~~~***~*eXv* ~~~~~*~~~~~~~~~~~~~~~~~ 60 3.3.6. Special Processors for Vision..................................................... 65 3.4. Architecture of Robot-Based Manufacturing Cells................................ 67 3.5. Improved Robot Programming............................................................. 73 3.5.1. Automatic Determination of Gripping Positions.................. 74 3.5.2. Off-line Training of Vision System and Stable Position Modeling......................................................... 76 3.5.3. Graphical Programming of Robots............................................ 78 3.6. Knowledge Based Distributed Database Design;.................................... 82 3.7. Generalized Problem-Solving Using Heuristics............................... 83 3.8. Metaform Database Interface System.................................................... 88 3.9. User Needs for Information Display.90 3.9. User Needs for Information Display....................................................... 90 3.10. Requirem ents A nalysis............................................................................ 92 4. Publications..................................................................................................... 95 4.1. Journal publication................................................................................. 95 4.2. Under Review....................................................... 95 4.3. In Preparation........................................................................................ 97 4.4. Conference Presentations....................................................................... 98 4.5. T echnical R eports................................................................................... 100 5. Personnel............................................ 103 5.1. Faculty.................................................................................................. 103 5.2. Students.................................................................................................. 104 5.3. Degrees Awarded.........................................105 5.4. Permanent Staff.................................106 xii

6. Coupling Activities.......................................................................................... 107 6.1. Intra Project Interactions..................................................................... 107 6.2. University Interactions........................................................................... 109 6.3. Interactions with Industry...................................................................... 110 6.4. DoD Interaction................................................. 113 7 Distribution List.............................................................................................. 115 xiii

1. Introduction and Summary 1.1. Introduction The College of Engineering of The University of Michigan formed the Center for Robotics and Integrated Manufacturing (CRIM) in 1981 to address major technological problems facing United States industry and to help produce the trained engineers and researchers needed to revitalize American industry. Following initial support by the State of Michigan this contract provides the cornerstone of funding upon which the Center is being built. This report summarizes the activities of the first year of the contract and describes the directions to be pursued during the second year. Manufacturing science is not a single narrow discipline. Rather it is a synthesis of techniques from a broad range of areas, from materials and processes through computer science. The treatment of manufacturing science by researchers and academicians must be correspondingly broad. Indeed, some problems will only be solved by bringing together expertise from multiple areas. Moreover, the applied nature of the subject argues for a tight interaction among research, education and applications, for it is a synergism among these three that is necessary to achieve the technological advance and training so badly needed by U.S. industry. In accordance with this view of manufacturing science, there are three important aspects to the manufacturing science activity at Michigan, a broad multi-departmental approach to the research, a strong graduate educational component, and a close interaction with industry. The breadth of faculty excellence in areas related to manufacturing is a unique component of the project and the synergism which is resulting from drawing these activities together into a coordinated activity is beginning to yield significant results. The research is based on this broad range of existing excellence. Numerous faculty in the College have expertise pertinent to robotics and manufacturing, and a desire to direct their expertise toward these areas. The current project has provided a focus for these activities and has become the foundation upon which the Center is being built. Furthermore, the College and University have made a major commitment to faculty expansion in this area, including the hiring of top rate senior people. During the first annual contract period eight new faculty were brought to the College in robotics and manufacturing, several of whom are directly participating in the project. Research into a number of new areas (discussed in subsequent sections of the report) have been begun, and significant results are beginning to appear. The contract indirectly supports the academic activities in two ways. First, through the support of a large number of graduate research assistants, it ensures the existence of a graduate student body being trained in research and application of technology to manufacturing science. Second, the fact that the research is directed by faculty members leads to rapid assimilation of research results into the curriculum. This structure also facilitates the growth of an active academic program in manufacturing science that spans several departments and provides students substantial experience with research and development projects. The industrial interaction component of the Center is important in order to bring a relevance to real problems to the research. This interaction has been brought about through the development of an industrial affiliates programs in several subareas of Annual Report 1 August 1, 1982 - July 31, 1983

CRIM, such as Robotics, Adaptive Control, Surface Finish, and through an intensive effort to obtain major new funding from industrial sources. Simply the existence of the project strengthens these interactions. Research supported under the project is reported to the Affiliates, and ideas started under this project have received expanded support from industry. 1.2. Overview of First Year The activities of the first year included a mixture of: expanding subprojects initiated with our State startup funds, building the experimental facilities needed for many of the research areas, bringing faculty "up to speed" in the application of their expertise to the robotics and manufacturing science area, and building a base of graduate students who are involved in the area. In addition, since it is recognized that while this contract is the cornerstone of our efforts there must be significant research funding from other sources, considerable effort was spent seeking additional funding. There are two categories of accomplishments during the past year, those which are the direct consequence of AFOSR funding, and those which have not directly involved AFOSR funding, but whose occurrence was at least partially influenced by the existence of the project. The direct funding of the contract is focused on the Robotics and Management Systems activity of the Center. The following has been accomplished: * Building of an extensive computing and experimental environment * Initial results in laying a firm theoretical foundation to robot control and the development of new algorithms for both nonlinear and adaptive controls * Design of high performance tactile and noncontact temperature sensors * Development and implementation of new high performance algorithms for edge detection, motion prediction and dynamic scene analysis * Development for and partial implementation of CAD driven robot/vision cell * Development of preliminary graphic robot programming systems * Development of algorithms for distributed knowledge base data assignment and heuristic problem solving * Design of systems to generate interface forms between users and manufacturing databases * 29 papers presented at significant conferences * 6 papers appeared in or accepted for review journals (review cycles necessarily keep this number small during the first year) * 16 papers currently under review for journal publication * 2 Ph.D. graduates * 7 NMI.S. graduates (there will be a number of December 1983 graduates which do not appear in this total) * Participation in 4 national meetings and workshops (other than conferences) * Direct involvement of 40 graduate students in AFOSR research projects Annual Report 2 August 1, 1982 - July 31, 1983

(Again, the numbers above reflect AFOSR support, not totals for either GRIM or the Robot System Division) The first year's activities have also seen the beginning of collaborations among faculty with different backgrounds to address complex problems. Work on the formulation of equations of motion and control strategies has affected work on robot simulation, and in turn the simulation system developed will be used to test control strategies in the future. Computer architects are working with the vision group to produce more efficient vision systems. An expert in computer aided design and computational geometries is working with computer engineers to produce a model driven robot system. And various groups of people in the same area are working together. Further collaboration is expected during the second and third years of the contract. In the category of accomplishments that have been influenced by the AFOSR contract are the following: * 5 students have full or partial fellowship support from U.S. industry to work in our program * 21 students who have at least partial internal fellowship support, their own support or teaching assistant support are participating in our program * Membership in the Robotics Industrial Affiliate Program increased from 6 to 14 * Major research support has been obtained from two major industrial sponsors. 1.3. Report Organization Section 2 describes the computational and laboratory facilities which have been developed to support the GRIM research activities. Section 3 reviews all of the research activities support by the contract. Publications and conference papers are listed in section 4. Personnel supported by the project are given in section 5, and coupling activities among participants in the project and with other organizations are present in section 6. Annual Report 3 August 1, 1982 - July 31, 1983

Annual Report 4 August 1, 1982 - July 31, 1983

2. Facility Development A major part of the contract during the first year was for the acquisition and installation of a broad base of equipment to augment the facilities already available. As most of the facilities acquired either were computational themselves or attached to a computer, it was necessary to expend considerable effort in configuring the systems and making the facilities operational. To put the new facilities in proper perspective, Section 2.1 describes the previously existing facilities. Section 2.2 then describes the new facilities acquired under this contract. 2.1. Computer and Image Processing Research Network and Computing Center Facilities Shared facilities with other members of the Electrical and Computer Engineering Department and the Medical School are provided by the Computer and Image Processing Research Network (CIPRNET). CIPRNET was created by several research equipment grants from the National Science Foundation (over $300,000), internal funding from the Office of the Vice-President of the University (approximately $250,000), funding from the College of Engineering and funding from the Medical School. It serves the research needs of the founding units, with instructional activities permitted only when they require the unique facilities of CIPRNET. CIPRNET was established to provide badly needed research computing and image processing facilities. It has grown to provide a base for the robotics activity as well. The major facilities in CIPRNET are: * a VAX 11/780 with 4 megabytes main memory (soon to be 8 megabytes) running the UNIX operating system o 900 megabytes of disk * an 800/1600 bpi tape drive * a Printronix 600 Ipm printer/plotter * a Benson Varian 200 dot/inch printer/plotter * a Hamamatsu digitizing camera * a Ramtek color display system * a DeAnza image display and digitizer * a Cytocomputer image processing device * a PDP 11/60 (used as a communications computer) * a Unimation 560 robot arm The system has been operational since Spring of 1980 and is heavily used. Annual Report 5 August 1, 1982 - July 31, 1983

2.2. New Facilities The facilities described above, while of great importance to the robotics research effort, are very heavily used and it is difficult to obtain adequate access to them. Further, they do not provide all of the special devices needed for the research activities of GRIM. The equipment acquired under this contract is intended to address these problems. It may be divided into the following categories: * general computing support * real time computing support * image processing and vision system * expanded robot facility * graphics display terminals for information processing In addition to the equipment purchased on this contract, significant equipment gifts have been obtained from Intel and ASEA, and a new contract with IBMf will bring an IBM 7565 robot to the laboratory. Figure 2.1 shows the combined facility. To support the general computing needs of CRIM, a DEC VAX 11/780 computer was purchased. Through internal support, it was possible to add 450 megabytes of disk to the system (the original purchase only was only sufficient to store the operating system, with no space for users). The new 780 has been networked to the CIPRNET 780 over a 1 mpbs network using the UNIX networking software provided by Purdue, thus making the facilities of CIPRNET available on line. Terminal access to the system is widespread. Most researchers have terminals on their desks, as do all of our secretaries and technical support personnel. All student office areas have terminals and public terminals and dial-up access are available. a The real time computing support acquired is in the form of a VAX 11/750. This system also runs UNIX and is networked to the two 11/780's. It is available for general use for CRIM personnel, except that it may be reserved for dedicated single user operation. It is interfaced to one of our Unimation PUMA robots and is used in single user mode for experiments with the PUMA. The image processing and vision systems include a fully configured DeAnza IP6400 image display/processor. This system is attached to the VAX 11/780 but is capable of various real-time processing tasks independent of the VAX. The facilities also include various hardware to acquire image sequences and digitize them with the DeAnza. The heart of the system is a Eigen video disk capable of storing 300 frames (10 seconds) of an image sequence. Each frame is individually addressable by the DeAnza/VAX. Two Fairchild CCD area cameras are also available for vision research. We have developed over five man-years worth of software for the DeAnza system. We also have over twenty man-years worth of image processing/machine vision software developed for the CIPRNET machine available on the CRIM VAX. The robot facilities were expanded to include a second PUMt.IA 600 series robot arm a wrist force sensor and a two degree of freedom servo driven hand for the robot is on order. The new robot has been fitted with the wrist sensor, and interfaced to the VAX 11/750 computer, and is being used, among other things, for experiments on active compliance using force feedback. In addition, ASEA has donated;n RB 6 Annual Report 6 August 1, 1982 - July 31, 1983

COMlPUTER & IMAGE ROBOTICS RESEARCH LABRATORY PROCESSING RESEARCH NETWORK (CIPRNET) LSI-ll/23 CSNET OOSSY~-~~fltflQf:I9 L 3 ]r Ii. " iiiiiii,. itl illll:!:!,~ ori^i'i: III_...l:.:j'':.~. 1, i...'*.. *......... 1... VAX-11/780. _ In,*. l 432:: VA X-11/75.i| i R iN'.'.STRX1.-6l *-|;;:::iii iiimi Ha tu~'.'..;..'.. ['...'.......P ) I I!im:~:~:.'.::aUW i:ii:i:'''.. "':''..... thelaboratory. The ASE robot has been interfacd to the Intel iAPuc pt. 6, tw Vi ion ~............... _3 AFOSR"E |] lililiiri igcn'i.t. li t oi Pafre Ql Vd ikr ajji Rob i Fiure ocr.1 robot to he Univesitygand n contract with n at6 Vrinideo 76 r equipment (see below) antd is being used for a variety of experiments. The IBM 7565 assembly. several significant aspects of the research effort. The terminal facilities for communi[^]] INOUS7RIAL CIFT CiCO\Cwkw; C mr cating both with vhe VAX computer systems and with the Uninersity Amdahl 5860 were explaboraed to include three high quA robot has been interfaced eto the Intel iAPX computertions. These are being used in a number of the research activities. Annual Report 7 August 1, 1982 - July 31, 1983

Intel Corporation has donated an iAPX 432 computer system consisting of four general data processors, 1.5 megabytes of memory, three interface processors, a series 3 development system, an 86/330 development system and components from which to construct several attached processors to the system. The system is Intel's new 32 bit multi-processing object based microcomputer system. Experiments are under way on the use of object based systems for implementing manufacturing cells and on the use of computer aided design (CAD) information for driving robot cells using this equipment. A frame grabber for a GE TN2500 camera has been designed, built and interfaced to the iAPX 432, and the ASEA RB 6 interfaced to the 432 as well. This effort was some of the first actual interfacing of equipment other than standard peripheral devices to the iAPX 432, and required extensive interaction with Intel to complete. The current version of the system uses the release 3 of the 432 hardware and version 2.0 of the Ada compiler scheduled Annual Report 8 August 1, 1982 - July 31, 1983

3. Research Activities The research supported by this contract involves two of the divisions of CRIM, the Robot Systems Division and the Management Systems Division, though in several cases there is joint work which spans the two divisions. The principal long term goal of the research in the Robot Systems Division of CRIM is the architecture of intelligent sensor based robot systems. This goal is interpreted in its broadest sense, encompassing comprehensive research on subsystems which will comprise advanced robot systems, algorithms for intelligent use of sensor information, and the implementation of robot systems of evolving complexity (beginning with enhancements to current robot systems). Important research topics range form highly sophisticated and accurate control algorithms for arm motion, development of new types of sensors, use of advanced sensor information, to higher level languages for robot control, and integration of robot systems with CAD databases. This comprehensive view of research is necessary to achieve our long term goals: there are many significant problems to be overcome. Figure 3.1 shows how individual subprojects relate to our long term goal. The Management System Division is principally concerned with the -use of computer based information systems in many areas in manufacturing: inventory and material control, purchasing, quality control and assurance, design, assembly control, routing, etc. These various applications are frequently carried out separately, on different computers, with programs in different languages, using various files and databases. The applications, however, are often related in that the outputs of one applications are the inputs of the others. It is generally accepted that further productivity gains could be made if the various systems including data from computer aided design, manufacturing and the decision support systems for the control and monitoring of processes were to be appropriately combined into an integrated information system. This integration is one of the principal concern of the Management System Division. Although hardware technology (including communication) is already available for such integration, there are significant other problem areas that need to be addressed before a fully integrated manufacturing information system can be developed. For example integration, in practice, may be difficult to achieve because there may be many alternatives whose consequences are difficult to predict, or, applications are often developed independently of each other and at different times. Experience in data processing applications, however, indicates that successful integration of computer based applications is possible through a logically integrated database and through proper choice of the optimum database structure (schema). This also is not easy even in relatively well understood and standard data processing applications partly because of the complexity of the real world that is being modeled by the database schema. In view of this, the objectives of the project are as follows. The general objectives of the Management System Division are to develop new knowledge and determine novel extensions of existing principles for the development of manufacturing information systems. These systems would support the informational handling and decision-making activities of both human supervisors and the integrated manufacturing system. The activities require that the human, machine utilization of these systems by manufacturing personnel at various levels within an organization be understood and specified. More specifically the objectives are to research specific issues Annual Report 9 August 1, 1982 - July 31, 1983

AFOSR SUPPORTED TASK AREAS Sensor Hl-g-Performance Special Purpose Subsystems m Manipulators: Computers &.1 Structure & Control Lan ue Sen\sor Based Rofnnot Systems....ioaost Knowle ge Iroolem g i- Rit TAsl, but yafrnacturdng Catl r glf e progra Integrated Factory Information System Figure 3.1 Relation of AFOSR supported task areas which would lead to the development of a methodology for the design and development of an integrated information system. The following section will review the specific problems addressed during the last year and the progress made. 3.1. The Control of Mechanical Manipulators Current manipulator applications such as material-handling (pick and place), spray painting, spot/arc welding and machine loading/unloading, place only moderate demands on control technology. Future tasks such as sensor driven small part assembly require that much more attention be given to manipulator structure, dynamics and control. Accuracy, rather than repeatability, will become one of the key performance measures. The current treatment of each joint as a simple servomechanism is inadequate because it neglects gravitational loading of the links, the dynamic interactions among the links and all sources of mechanical compliance. The result is reduced Annual Report 10 August 1, 1982 - July 31, 1983

servo response speed and damping, which in turn limits the precision and speed of the end-effector. Significant gains in manipulator performance require the consideration of structural dynamic models, sophisticated control techniques, and the exploitation of advanced computer technology. These problems are addressed on several different, but coordinated, fronts, including: * Accurate modelling of robot arm kinematics and dynamics: different formulations of rigid-body equations, vibrational dynamics, discontinuous nonlinearities, actuators effects. * Computer simulation: development of special software packages, utilization of ultra-high-speed computers, graphics display techniques. * Nonlinear multivariable control: decoupling methods, stability improvement treatment of discontinuous nonlinearities, computer-aided design. * Optimization of robot arm motion: constraints on control and state variables, different optimization criteria, numerical methods, practical implications, good suboptimal motions. * Adaptive control: feedback gain modifications. load sensing, process modelling and identification. * Mechanical compliance: characterization of the sources of mechanical compliance and control of their effects on manipulator motion control. Several other important problems in manipulator control, such as accurate modelling of robot arm motion and computational complexity, are embedded within the studies on the above problems. The following paragraphs will describe each of these activities. 3.1.1. Efficient Robot Arm Kinematics and Dynamics Professor C.S.G. Lee The Problem and Research Objectives The implementation of advanced control strategies for robots is dependent upon the existence of efficient robot arm kinematics and dynamic models. In general, a robot servo system requires the reference inputs to be in joint coordinates while a task is usually stated in terms of the Cartesian coordinate system. HIence, controlling the position and orientation of the end-effector of a robot arm to reach its object requires the understanding of the kinematic relationship between these two coordinate systems. Two fundamental questions of both theoretical and practical interest in robot arm kinematics are: (1) For a given manipulator, given the joint angle vector q(t) = (ql(t),qc(t).' q, (t))T and the geometric link parameters, where n is the number of degree-of-freedom, what is the position and orientation of the end-effector of the manipulator with respect to a reference coordinate system? Annual Report 11 August 1, 1982 - July 31, 1983

(2) Given a desired position and orientation of the end-effector of the manipulator and the geometric link parameters, can the manipulator reach the desired prescribed manipulator hand position and orientation? And if it can, how many different manipulator configurations will satisfy the same condition, and how should the the right configuration be selected? An integral part of this research is focused on the second problem, namely (inverse kinematics (or arm solution) problem, in finding a consistent closed-form joint solution for industrial robots with rotary joints. Correspondingly, a priori information needed for manipulator- control analysis and manipulator design is a set of closed form differential equations describing the dynamic behavior of the manipulator. The issues recur through most of the research efforts in simulation and control. The objective is to obtain an efficient set of closed form motion equations from which an appropriate controller can be designed to control the robot arm in real time. Approach and Status of the Research Effort Robot Arm Kinematics The joint solution problem can be solved by a matrix algebraic, iterative, or geometric approach. Several investigators have attempted to solve the problem for the PUMA1 and Stanford robot arms using the matrix algebraic approach [1-5]. Although the approach is general enough for most industrial robots, it suffers from the fact that the solution does not give a clear indication of how to select the correct solution from the several possible solutions for a particular arm configuration. The user often needs to rely on his/her intuition to pick the right answer. The iterative solution [6] often requires more computations and it does not guarantee convergence to the correct solution, especially in the sing-ular and degenerate cases. Furthermore, there is no indication on how to choose the correct solution for a particular arm configuration. If the manipulator under consideration is simple, that is the geometry of the first three joints has revolute or prismatic pairs and the last three joint axes intersect at a point, then the geometric approach presents a better approach for obtaining a closed form joint solution. Our research is directed toward obtaining a consistent closed form joint solution for industrial robots with six rotary joints using the geometric approach. The approach calls for the definition of various possible arm configurations based on the link coordinate systems and human arm geometry. These arm configurations are then expressed in an exact mathematical way to allow the construction of three arm configuration indicators (ARM, ELBOWV, and WRIST) and their corresponding decision equations. The arm configuration indicators are prespecified by a user for finding the joint solution. These indicators enable one to find a solution from the possible four solutions for the first three joints, and a solution from the possible two solutions for the last three joints. The solution is calculated in two stages. First a position vector pointing from the shoulder to the wrist is lerived. This is used to derive the solution of the first three joints by looking at the projection of the position vector onto the x,_-y,_ (i= 1,2,3) plane. The last three'PUMATlv[ is a trademark of Unimation Inc. Annual Report 12 August 1, 1982 - July 31, 1983

joints are solved using the calculated joint solution from the first three joints, the orientation matrices, and the projection of the link coordinate frames onto the x,1-y,-i (i = 4,5,6) plane. With the assistance of the configuration indicators and the arm geometry, one can easily find the arm solution consistently. The validity of the arm solution has been simulated and verified on a VAX-11/780 computer. With appropriate modification and adjustment, the user can generalize and extend the method to most present day industrial robots with rotary joints and obtain the arm solution easily. Details about the joint solution of a six-axis PUMA robot arm are given in [7]. Robot Arm Dynamics Various approaches are available for formulating the robot arm dynamics, such as Lagrange-Euler (L-E) [8-10], Newton-Euler (N-E) [11-16], and Recursive Lagrangian (R-L) [17], though mainly two approaches are used by most researchers - the Lagrange-Euler and the Newton-Euler formulations. The derivation of the dynamic model of a manipulator based on the LagrangeEuler method is simple and systematic. The dynamic equations of motion are obtained from known physical laws and physical measurements of link inertias and parameters. Assuming rigid body motion, the resulting dynamic equations of motion, excluding the gear friction and backlash, are a set of second order coupled nonlinear differential equations. Bejczy [9] has shown that the above dynamic equations of motion for a six-link Stanford arm are highly nonlinear and consist of inertia loading, coupling Coriolis and centrifugal reaction forces between joints, and gravity loading effects. Furthermore, these interaction torques/forces depend on the manipulator's physical parameters, instantaneous joint configuration, and the load it is carrying. Because of its explicit matrix structure, this formulation is appealing from a control viewpoint in that it gives a set of state equations. This form allows one to design a control law that compensates all the nonlinear effects easily. Computationally, however, these equations of motion are extremely inefficient for real-time closed-loop control as compared with other formulations [18-19], and real-time control based on the "complete" dynamic model has been found difficult to achieve if not impossible [18]. To improve the speed of computation of the control law, simplified sets of equations have been proposed by other investigators [9,10,20,21]. In general, these "approximate" models simplify the underlying physics by neglecting second order terms such as the Coriolis and centrifugal reaction terms. Bejczy and Paul have proposed a simplified model which neglects the Coriolis and centrifugal forces and the off-diagonal elements of the "mass" matrix [9,10], This approximate model greatly simplifies the computation, and real-time feedback control on a Stanford arm with a sampling frequency of 60 Hz was found feasible [9,10]. However, this only applies to a specific robot arm, and when used in control purposes for other types of robot arm, they give suboptimal dynamic performance restricting arm movement to low speeds. At high arm speeds the neglected terms become significant, making the accurate position control of the robot arm more difficult [22]. As an alternative to deriving more efficient equations of motion, several investigators turned to Newton's second law and developed various forms of Newton-Euler equations of motion [11-16]. The derivation was based mainly on the "moving coordinate systems" and d'Alembert's Principle. The resulting dynamic equations, excluding the gear friction and backlash, are a set of compact forward and backward Annual Report 13 August 1, 1982 - July 31, 1983

recursive equations. This set of recursive equations can be applied to the robot links sequentially. The forward recursion propagates kinematics information (such as angular velocities, angular accelerations, and linear accelerations) from the base reference frame (inertial frame) to the end-effector. The backward recursion propagates the forces exerted on each link from the end-effector of the manipulator to the base reference frame and the applied joint torques are computed from these forces. Because of the nature of the formulation and the method of systematically computing the joint torques, computations are much simpler. The most significant of this modification is that the computation time of the applied torques is found linearly proportional to the number of joints of the robot arm and independent of the robot arm configuration. This enables the implementation of simple real-time control algorithm for a robot arm in the joint-variable space. The inefficiency of the equations of motion as formulated by the L-E method comes mainly from the 4X4 homogeneous matrices describing the kinematic chain [18], while the efficiency of the N-E formulation can be seen from the vector formulation and its recursive nature. To further improve the computation time of the Lagrangian formulation, Hollerbach [17] exploited the recursive nature of the Lagrangian formulations. However, the recursive equations destroy the "structure" of the dynamic model which is quite useful in providing insight for the controller design and manipulator design. For control analysis, one would like to obtain an explicit set of closed form differential equations that describe the dynamic behavior of a manipulator and the interaction and coupling reaction forces in the equations can be easily Approach Lagrange-Euler Newton-Euler eneralized d'Alembert 128 n4 512 3 13 3 105n2 llultiplications 3 3 132n 6 2 + 739 2 160 268 + n + -n + +69 3 3 3 i98 n+34 - 4n3 + 44n2 Additions 3 6 1 1 1 n-4 3 559 2 245 146 + - n2 + --— n + -— n + 45 3 6 3 Kinematics 4x4 Homogeneous Rotation Matrices Rotation Matrices Representation Matrices and Position Vectors and Position Vectors Equations of Closed-form Recursive Closed-form Motion Differential Equations Equations Differential Equations where n = number of degrees-of-freedom of the robot arm Table 1 Comparison of Robot Arm Dynamics Computational Complexities Annual Report 14 August 1, 1982 - July 31, 1983

identified so that an appropriate controller can be designed to compensate ( or counter-balance ) their effects. To obtain such an efficient set of closed form equations of motion, an approach based on the generalized d'Alembert Principle is proposed. This research effort leads to the development of the generalized d'Alembert equations of motion (G-D) for mechanical manipulators with rotary joints. The method utilizes vector approach to increase the computational efficiency. It uses relative position vector and rotation matrix representation to describe each link's kinematics information, obtain the kinetic and potential energies of the robot arm to form the Lagrangian function and apply the Lagrange-Euler formulation to obtain the equations of motion. These equations, when applied to a robot arm, result in an efficient and explicit set of closed form second order nonlinear differential equations with vector cross product terms. They give fairly well "structured" equations of motion suitable for control analysis and manipulator design. The interaction and coupling reaction forces/torques between the neighboring joints of a manipulator can be easily identified as coming from the translational and rotational effects of the links. With this information, either a simplified dynamic model can be developed or an appropriate controller can be designed to compensate the nonlinear effects. Computational complexities of these three robot arm formulations are tabulated in Table 1. The main objective of developing the G-D equations of motion is to facilitate manipulator control analysis and manipulator design. Similar to the L-E equations of motion, the G-D equations of motion are explicitly expressed in matrix form and all the interaction and coupling reaction forces that are present in a manipulator can be easily identified. Furthermore the elements in the DiJ matrix (the acceleration-related terms), the Hwran, the Hot (the Coriolis and centrifugal terms), and the Gp (the gravity loading terms) vectors can be clearly identified as coming from the translational and the rotational motion of the links. This greatly aids the construction of simplified clynamic model for control purpose. For example, for a PUNMA or T32 robot arm, the elements of the Di, matrix come from the translational and rotational effects of the links. These effects depend on the joint variables and the inertial parameters of the manipulator. For the first three joints (0,,03,0J), because of their usually long link length for maximum reach and long distance traveled between the initial position and final position, the effects of translational motion will dominate the rotational motion. In contrast to the first three joints, the rotational effects will dominate for the last three joints. Hence, one can simplify the computation of the D,, matrix by considering only the translational effects for the first three joints and the rotational effects for the last three joints. Similarly, one can evaluate the contribution of'"ran and Iat^ and eliminate their computations if they are insignificant. The resulting simplified model retains all the major interaction and coupling reaction forces at a reduced computation time and greatly aids the design of an appropriate control laws for controlling the robot arm. Current industrial robots are designed kinematically to reach any given point in their specific workspace without considering the efficiency of the dynamics anid control strategies. Since physical link parameters play an important role in determinating its sphere of influence and the magnitude of the interaction and coupling reaction forces between joints, it is important to choose these parameter values Iproperly so -T3 is a trademark of Cincinnati Milacron Annual Report 15 August 1, 1982 - July 31, 1983

that the dynamic coefficients used in the controller can be computed rapidly to obtain the necessary applied torques to the joint actuators. The G-D equations of motion can be used extensively to verify the effects of the links' length, the link inertia, and location of the center of mass on the magnitude of the interaction and coupling reaction forces between joints. Based on these findings, one can design a robot arm with a simplified dynamic model for control purpose. The above research was performed with discussions with Professor M. A. Chace. Future Work Future research will be directed toward investigating consistent rules for obtaining simplified dynamic models from the generalized d'Alembert equations of motion for control purposes. The significance of this work can be demonstrated by designing sophisticated control laws based on the simplified motion equations. Furthermore, control laws based on simplified motion equations may be realized by present day low cost microprocessors such as Motorola MC68000 or Intel 8086/8087. References [1] Pieper, D. L., "The Kinematics of Manipulators Under Computer Control," Computer Science Department, Stanford University, Artificial Intelligence Project Memo No. 72, October 24, 1968. [2] Paul, R. P., B. E. Shimano, and G. Mayer, "Kinematic Control Equations for Simple Manipulators," IEEE Transactions of Systems, AMan, and Cybernetics, Vol. SMC-11, No. 6, June 1981, pp 449-455. [3] Lewis, R. A., "Autonomous Manipulation on a Robot: Summary of Manipulator Software Functions," Technical Memo 33-679, Jet Propulsion Lab, March 15, 1974. [4] Lee, C. S. G., "Robot Arm Kinematics, Dynamics, and Control," Computer, Vol. 15, No. 12, December 1982, pp 62-80. [5] Paul, R. P., Robot Manipulators: Mathematics, Programming and Control, M.I.T. Press, 1981, pp 50-84. [6] Uicker, J. J., Jr., J. Denavit, and R. S. Hartenberg, "An Iterative Method for the Displacement Analysis of Spatial Mechanisms," Trans. of ASME, Journal of Applied AMechanics, Vol. 31, Series E, 1964, pp. 309-314. [7] Lee, C. S. G. and M. Ziegler, "A Geometric Approach in Solving the Inverse Kinematics of PUMA Robots," Proceedings of the 13th International Symposium on Industrial Robots, April 17-19, 1983, Chicago, Illinois, pp 16-1 to 16-18. [8] Uicker, J. J., "On the Dynamic Analysis of Spatial Linkages using 4X4 Matrices," Ph. D. dissertation, Northwestern University, August 1965. [9] Paul, R. P., "Modeling, Trajectory Calculation, and Servoing of a Computer Controlled Arm," Stanford Artificial Intelligence Laboratory Memo AIM-177, November 1972. [10] Bejczy, A. 1K., "Robot Arm Dynamics and Control," Technical Memo 33-669, Jet Propulsion Laboratory, February 1974. Annual Report 16 August 1, 1982 - July 31, 1983

[11] Armstrong, W. M., "Recursive Solution to the Equations of Motion of an N-link Manipulator," Proceedings of the 5th World Congress, Theory of Machines, Mechanisms, Vol. 2, July 1979, pp 1343-1346. [12] Orin, D. E., R. B. McGhee, M. Vukobratovic, and G. Hartoch, "Kinematic and Kinetic Analysis of Open-Chain Linkages Utilizing Newton-Euler Methods," Math. Biosc., Vol. 43, 1979, pp 107-130. [13] Luh, J. Y. S., M. W. Walker, and R. P. C. Paul, "On-Line Computational Scheme for Mechanical Manipulators," Transactions of ASME, Journal of Dynamic Systems, Measurement, and Control, Vol. 120, June 1980, pp. 69-76. [14] Stepanenko Y., and M. Vukobratovic, "Dynamics of Articulated Open-Chain Active Mechanisms," Math. Biosc., Vol. 28, 1976, pp 137-170. [15] Huston, R. L., C. E. Passerello, and M. W. Iarlow, "Dynamics of MultirigidBody Systems," J. Appl. Mech., Vol. 45, 1978, pp 889-894. [16] Walker, M. W., and D. E. Orin, "Efficient Dynamic Computer Simulation of Robotic Mechanisms," Transactions of ASAIE, Journal of Dynamic Systems, Measurement, and Control, Vol. 104, Sept. 1982, pp. 205-211. [17] Hollerbach, J. M., "A Recursive Lagrangian Formulation of Manipulator Dynamics and a Comparative Study of Dynamics Formulation Complexity," IEEE Trans. on Systems, Man, and Cybernetics, Vol. SMC-10, No. 11, Nov. 1980, pp. 730-736. [18] Turney, J. L., T. N. Mudge, and C. S. G. Lee, "Equivalence of Two Formulations for Robot Arm Dynamics," SEL Report 142, ECE Department, University of Michigan, December 1980. [19] Turney, J. L., T. N. Mudge, and C. S. G. Lee, "Connection Between Formulations of Robot Arm Dynamics with Applications to Simulation and Control," CRIM Technical Report No. RSD-TR-4-82, the University of Michigan, April 1982. [20] Bejczy, A. K., "Dynamic Models and Control Equations for Manipulators," Technical Memo 715-19, Jet Propulsion Laboratory, November 1979. [21] Bejczy, A. K., and R. P. Paul, "Simplified Robot Arm Dynamics for Control," Proceedings of the 20th IEEE Conference on Decision and Control, San Diego, Dec. 1981, pp 261-262. [22] Chung, M. J., "Adaptive Control Strategies for Computer-Controlled NManipulators," Ph. D. Dissertation, the Computer, Information, and Control Engineering Program, the University of Michigan, Ann Arbor, August 1983. 3.1.2. Simulation Effective simulation of robots is an extremely important factor in the (lesign, checkout, and potentially, the operation of robot systems. A robot design, including the complete control system, can be tested using simulation and modified as necessary prior to commitment to prototype construction. Real time simulation can b)e used to test subsystems such as joint actuators in the simulated environment in which they will be operating. Real-time simulation can also form part of an actual Annual Report 17 August 1, 1982 - July 31, 1983

robot control system using feed-forward control. Faster-than-real-time simulation permits predictive display of robot performance, which could play an important role in remote manipulators. The simulation of complex robot structures has been approached from two points of view. One approach emphasizes the inclusion of nonlinear friction effects, control law dynamics and real time operation. The second emphasizes incorporation of the robot simulation in a general large displacement dynamics simulation system. Both include dynamic structural modes and the complete dynamic equations of motion. 3.1.2.1. Real Time Simulation Professor R.M. Howe Research Objectives The objective of this research activity is to develop improved methods for computer simulation of robots with particular emphasis on real-time simulation. It is planned eventually to use the real-time simulation for hardware-in-the-loop testing of robot components as well as mechanization of sophisticated digital control algorithms. The real time simulation will be carried out using an AD-10, which is an extremely fast pipelined, multiprocessor computer with architecture optimized for solving ordinary differential equations. It is planned to include dynamic structural modes in the simulation as well as nonlinear friction effects. Status of the Research Effort -- Real Time Simulation As prepartion for development of a real-time robot simulation on the AD 10, a nonreal-time simulation of a six-link robot has been successfully programmed and run on a PDP-11/34. This simulation provides not only solutions against which AD 10 solutions can be checked, but also allows study of various algorithms for inverting the inertia matrix. The program is based on the Newton-Euler formulation of manipulator dynamics and includes the mechanization of linear control laws for the joint actuators. Complete simulation of typical 1 second transient maneuver requires approximately 10 minutes of PDP 11 time. It is expected that this model will run faster than real time on the AD 10. To establish the reliability of the PDP 11 simulation the solutions were compared with other published results. To facilitate this comparison an algorithm based on a Lagrange formulation was also implemented. As a result of these efforts favorable comparisons have been demonstrated and confidence in the validity of the PDP 11 simulation has been established. A significant portion of the computational time for each numerical integration step in the simulation is required for the inversion of the inertia matrix. In the reference PDP 11 solution this was accomplished by Gaussian elimination. Two other approaches have been investigated with the objective of speeding up the computation. The first, based on table look-up and function fitting, proved to be Annual Report 18 August 1, 1982 - July 31, 1983

unsatisfactory due to insufficient accuracy in representation of some of the inverse matrix elements. The second, based on an iterative scheme derived from a difference equation formulation of the matrix inversion problem, has shown promise of speed improvement and is particularly suitable for mechanization on the AD-10. Familiarity with MPS 10, the AD-10 programming language, has been accomplished and the programming of the six-link simulation on the AD-10 has been initiated. Meanwhile, in anticipation of the inclusion of nonlinear friction in the robot joints, a nonlinear friction model which has different levels of breakaway and running friction has been demonstrated on the AD-10. Also, a very fast and highly accurate algorithm for simulating lightly damped structural modes has been demonstrated. The research described above is conducted by R.M. Howe and B. Morgowitz. The specific six-link robot benchmark simulation has involved collaboration with C.S. George Lee and M.J. Chung. Frequent discussions with E.G. Gilbert and D.W. Johnson have been helpful and the AD-10 robot simulation program, when completed, will be directly applicable to their control systems. 3.1.2.2. General Dynamic Simulation Professor M.A. Chace, Professor J. Whitesell Research Objectives -- General Dynamic Simulation General mechanical systems have parts which move through large angles and translations. When all parts are rigid the analysis is understood. When some or all of the parts are flexible however the analysis becomes more difficult. This research has been directed toward developing a computer code for simulating general mechanical systems composed of flexible elements undergoing large displacement motion. Status of the Research Effort -- General Dynamic Simulation At this point a code called DYMOS (DYnamic MOdal Simulation) has been developed which simulates planar mechanisms. The analytical approach utilizes a Lagrangian formation wherein rigid body modes and superposed free vibration modes serve as generalized coordinates. Lagrange multipliers are used to penalize violations of kinematic constraints for both rigid and flexible modes. This approach leads to sparse equations of motion which can be generated and numerically integrated automatically. The analysis itself is also applicable for general three dimensional motion. A computer program for simulation in three dimensions was begun, but not completed as yet. Annual Report 19 August 1, 1982 - July 31, 1983

3.1.3. Application of Nonlinear Systems Theory to Mechanical Manipulators Professor E.G. Gilbert Research Objectives The main objective has been to study the application of nonlinear systems theory to the control of mechanical manipulators. The work to date has emphasized: (1) a general approach to the design of nonlinear feedback laws which give small tracking errors during rapid, large-scale manipulator motions, (2) the investigation of nonlinear decoupling theory as a basis for control system design, (3) various ways for writing manipulator equations of motion and efficiently computing resulting nonlinear functions which are needed for nonlinear control and/or simulation and modelling, These topics, which are interrelated, are in various stages of progress. In the following paragraphs the nature and status of the research is described. Method and Status of the Research Effort Nonlinear Feedback Laws The approach to the design of nonlinear feedback laws is based on dynamic equations of the form M(q)qF + (q, q) = Pu, y = G(q) (1) where: q is a vector of joint angles, u is a vector of motor control voltages, y is a vector measuring end-effector location, AM(q) and P are nonsingular matrices, and F(q, q) is a vector function. Often, y has the same dimension as q and u; for example, in a conventional manipulator dimension q = 6 and the components of y may denote endeffector position (3 Cartesian coordinates) and orientation (3 Euler angles). But sometimes the dimension of y is greater; for example, if dimension q = 6 and orientation is measure by three unit vectors the dimension of y = 12. The desired motion is specified by yd and the error in motion by a vector function E(q, y') which has the same dimension as q. The function E may be fairly simple (e.g., joint errors give E(q, td) = Gl(y) - q) or quite complex (e.g., if E includes errors measured by sensors in the end effector). The basic question is the determination of an intermediate feedback controller u = K(q, q, y d, v d) (2) which causes the error e = Eq, yd) to satisfy 00 e = v. (3) Annual Report 20 August 1, 1982 - July 31, 1983

If such a controller can be found the overall control system design becomes simple. For instance a PID (proportional, integral, derivative) controller for the error would take the form v = KpEpq,yd) + KDED(q, y, q, yd) + KlfE(Aq, y)dt, (4) o where, ideally, Ep = El = E and ED = - E. Then the choice of the matrices Kp, KD, dt and IK is modified because the error differential equation is linear. The problem of finding K is discussed in [1]. Notation is set up and a condition is given on E. Then a formula is derived for K. In practice the functions K, Ep,ED, and El have errors which are due to a variety of sources such as inaccuracies in modelling the manipulator dynamics, simplification in the computation of ED and', and sensor errors. It is shown that such errors, if small, will not upset the stability of the feedback system or cause large steady-state errors. More specific results are also available. For example, if K, is nonsingular the steady state errors depend only on errors in Es. Errors in K, Ep, and ED produce no steady-state errors. Such results have important implications with respect to the engineering design of sensors and the computation of feedback functions. As an example of the preceding theory an error measure used by Luh, Walker, and Paul [4] is considered in [1]. A control law is derived from the theory. It is somewhat more complex than the one proposed in [4] but it provides better error performance and stability under large perturbations of q and q. Moreover, the control law obtained in [4] is shown to be an approximation to the exact law obtained from the general theory. Thus the general theory may be viewed as providing a rigorous and systematic approach to the result of [4], which was obtained heuristically. The example suggests that the theory will be useful in the design of control systems for future manipulators which have complex error measures based on end-effector error sensors. Mlinimal Sensitivity Another result, of rather general interest in control theory, was obtained in [2]. This paper gives conditions on a linear system such that its characteristic roots have minimal sensitivity. The conditions should be useful in improving the robustness of control-system stability to modelling errors. An example would be the choice of the matrices lip, KD,. and I, in (4). Decoupling Theory The design method described in [1] has limitations. It may not apply if there are additional actuator dynamics or dynamics representing structural flexibility. This has motivated a more general and deeper investigation into the theory of nonlinear control. One wvay of looking at the tracking problem is to view it as a problem in nonlinear decoupling control. A number of papers have been published in this area (see, for example, [5,6,7,8]) but the theory is both complex and incomplete. I.J. I-Ia has been working with E.G. Gilbert in this area and has obtained new theoretical results. Annual Report 21 August 1, 1982 - July 31, 1983

Since the research is in an active state of development, no written report has been prepared so far. Several aspects of the research will now be described. Suppose a nonlinear system, such as a manipulator with actuator dynamics is described by the equations 0 x= Af, u), y = h(x). (5) where x is an n vector and u (control) and y (output) are m vectors. A new (closedloop) system is obtained by using the nonlinear control law u = K(z, v); 0 = A, K(x, )), y = h(x). (6) This system, with input v (dimension = n), has different dynamics and inputoutput characteristics than (5). The system (5) is "decoupled" if the ith component of v effects only the ith component of y (there are several precise ways of saying this). The literature, which has strong connections to differential geometry, gives various conditions of f and h so that "decoupling" by some K is possible. However, little is said about the whole class of decoupling laws. This question has been pursued and some interesting facts have been discovered. For instance, the class of decoupling control laws may be more general then indicated by prior nonlinear theory and less general than would be expected from linear decoupling theory. For certain categories of systems (5) the whole class of nonlinear decoupling laws can be determined easily. Fortunately, it appears that many manipulator models (including some with actuator dynamics) fall in one of these categories. Thus, the entire class of nonlinear control laws which decouple a manipulator may be described. Practical implications of these results need to be explored more fully. This will be done in the coming year. Computational Complexity In implementing the nonlinear control laws for the simulation of manipulator systems it is necessary to compute various terms in [1]. This has been discussed extensively in the literature (see, e.g., [9,10,11,12]). For instance if a, v, q are given 6 vectors the vector function, W (a,, q) = M(q)a + F(q, v), (7) may be computed in various ways. The most efficient (least number of numerical operations) are variants of the so-called Newton-Euler method [9,10,12]. Efficiency is important because W' must be computed repeatedly in various nonlinear control schemes, including the one described [1]. However, for system simulation and other control schemes it may be necessary to determine the matrix M(q) explicitly. This may be done with reasonable efficiency using a modification the Newton-Euler method. Another, more efficient, approach has been described in [11]. During the last year D.W. Johnson has development several new methods for computing M(q). These methods are more efficient than the one described in [11]. Some of this research has been report in [3] and a more detailed paper will be prepared in the future. Some attention has also been given to the computation of Annual Report 22.August 1, 1982 - July 31, 1983

other data concerning [1], for example, efficient procedures for computing the linearized equations of motion corresponding to [1]. While the research described above involves E.G. Gilbert, I.J. Ha, and D.W. Johnson there have been some fruitful interactions with other participants in the Grant. These include C.S.G. Lee and R.M. Howe and some of their students. References: [1] Gilbert, E.G., and I.J. Ha "An Approach to Nonlinear Feedback Control with Applications to Robotics," Center for Robotics and Integrated Manufacturing Technical Report RSD-TR-4-83, College of Engineering, University of Michigan, September 1983. Presented at 1983 Conference on Information Sciences and Systems, The Johns Hopkins University (pp 612-618 of Proceedings). To be presented at the 1983 IEEE Conference on Decision and Control. Submitted to IEEE Transactions on Systems, Alan and Cybernetics. [2] Gilbert, E.G., "Conditions for Minimizing the Norm Sensitivity of Characteristic Roots," Presented at 1983 Conference on Information Sciences and Systems, The Johns Hopkins University (pp 641-647 of Proceedings). To be presented at the 1983 IEEE Conference on Decision and Control. Accepted for publication in IEEE Transactions on Automatic Control. [3] Johnson, D.W., "Efficient Computational Schemes for the Control and Simulation of Robotic Mechanisms," Presented at 1983 Conference on Information Science and Systems, The Johns Hopkins University (p 619 of Proceedings). [4] Luh, J.Y.S., W.M. Walker, and R.P. Paul "Resolved Acceleration Control of Mechanical Manipulators," IEEE Trans. Auto. Control, vol AC-25, 1980, pp 468-474. [5] Singh, S.N., and W.J. Rugh, "Decoupling in a class of nonlinear systems by state variable feedback," J. Dynamic Syst. Ateasurement, Contr., Trans. A4SAlE vol 94, pp 323-329, 1972. [6] Hirschorn, R.M., "(A,B) - Invariant distributions and disturbance decoupling of nonlinear systems," SIAM J. Contr. Optimiz., Vol 19, pp 1-19, 1981. [7] Claude, D., "Decoupling of nonlinear systems," System & Control Letters, vol 1, no. 4, pp 242-248, 1982. [8] Nijmeijer, H., "Noninteracting control for nonlinear systems," To be presented at the 1983 IEEE Conference on Decision and Control. [9] Luh, et. al., "On-Line Computational Scheme for Mechanical Manipulators," Trans of the ASAIE, Journal of Dynamic Systems, Aleasurement and Con-trol, June 1908, pp 69-76. [10] Hollerbach, John M., "A Recursive Lagrangian Formulation of Manipulator Dynamics and a Comparative Study of Dynamics Formulation Complexity," IEEE Trans. on Systems, Mlan and Cybernetics, vol SMC-10, Nov. 1980, pp 730-736. [11] Walker, M.W. and D.E. Orin, "Efficient Dynamic Computer Simulation of Robotic Mechanisms," JACC, 1981. Annual Report 23 August 1, 1982 - July 31, 1983

[12] Turney, J.L., T.N. Mudge, and C.S.G. Lee, "Connection Between Formulations of Robot Arm Dynamics with Applications to Simulation and Control," Center for Robotics and Integrated Manufacturing, Technical Report RSD-TR-4-82, College of Engineering, The University of Michigan, November 1981. 3.1.4. Optimal Control Techniques to Enhance Robot Performance While productivity gains may be made using current robots, such robots are often under-utilized, and many future applications will depend upon high performance. The methods of optimal control and optimal design have demonstrated great potential for improving the efficiency and quality of robot and process behavior. The control problem for manipulators, is to determine the torques or forces which should be exerted at the joints of the robot so as to drive the robot in the most economical manner, while meeting certain constraints on the robot's position, velocity and actuator torques. There are several performance measures one can use, minimum time of flight of the robot arm, minimum energy consumption, or distance of the path from the obstacles. Further, the difficulty in setting up the correct equation for the problems and the excessive computer time required to find solutions has hampered optimal methods. The following subprojects address different aspects of these problems. 3.1.4.1. Automatic Generation of State and Costate Equation for Optimization of Mechanism Performance Professor J. Whitesell Problem and Objectives In principle methods of optimal control and optimal design have the potential to achieve such broad objectives as reduced weight, stresses, energy consumption or process cycle times. Unfortunately, the difficulty of setting up problems and the excessive computer time required to find solutions has reduced the attractiveness and limited the applicability of these methods. It is the objective of the current research to develop more effective methods for setting up and solving optimal control and optimal design problems. Approach and Status of the Research Effort In this work a commercially available simulation code known as ADA,'IS [Automatic Dynamic Analysis of Mechanical Systems] is used as an analysis co1mponent in the optimization scheme under development. ADAMS is able to automatically generate and numerically integrate differential equations of motions describing the dynamical performance of general mechanical systems or mechanisms. The differential equations formed by ADAMS are implicit equations of the form G(x, x, u, t) = 0 where the state vector and its derivative are algebraically coupled. Annual Report 24 August 1, 1982 - July 31, 1983

Numerical integration is carried out directly on G with a Gear method. The Gear method is a stiff integrator which involves a Newton-Raphson corrector stage requiring a Jacobian matrix related to G. In the ADAMS code tihe required Jacobian matrix is symbolically generated. Standard optimal control approaches which are designed for differential equations of the explicit form x = Af,u,t) are not well suited for use with implicit equations that arise naturally when mechanisms are modelled. To overcome this difficulty new necessary conditions for optimization problems involving implicit differential equations have been derived. These new results which may be applied to both control and design optimization problems offer several advantages: They are significantly more efficient since considerable numerical effort is avoided and they are well suited to automatic set up. The costate equations that arise in the new formulation are also implicit and they involve the same Jacobian matrix already formed for use in the Gear method. Thus the new approach is especially well suited to use with the Gear integration method. Future Example problems have been solved with a test code to verify the validity of the new approach. Future efforts will be directed toward developing an optimal control and an optimal design code wherein problem setup, equation generation and optimization are automatically carried out. Applications include robot paths planning for minimal cycle time (see sec.3.1.4), minimal joint load and minimal energy consumption. 3.1.4.2. Optimal Control and Trajectory Planning Professor E.G. Gilbert, Professor Kang G. Shin The Problem and Research Objectives In the optimal control and path problems identified above fixed costs often dominate, so that minimum cost is equivalent to minimum time; hence there is an interest in minimum-time robot control. Also, energy consumption and distance from obstacles are performance measures of interest. The objective in this project is to develop efficient robot control, algorithms and trajectory planning methods. Status of the Research Effort D.W. Johnson working with E.G. Gilbert is examing the role of optimal control in a very general approach to trajectory planning. A critical aspect of this research is obstacle avoidance and/or the cooperative, non-interfering operation of several manipulators. The general approach is to form a penalty function which measures the nearness of collisions on a specified manipulator path. This penalty function is included together with other measures of performance such as path smoothness, actuator effort, and energy consumed. The resulting optimization is likely to be very complex and attention is being given to computationally efficient methods for Annual Report 25 August 1, 1982 - July 31, 1983

evaluating the penalty cost and its functional gradient. Preliminary results in these directions show promise, but there are many unresolved questions. These will be explored and computational experiments will be performed in the coming months. Connections to the approached taken by K.G. Shin in [3] are also being explored. K.G. Shin, N.D. McKay, and B.K. Kim are examining minimum time trajectory calculations and minimum energy control. The minimum-time robot control problem has been approached in several different ways. The most common approaches to date are based on linear and/or nonlinear programming. Such approaches generally specify a path in terms of its endpoints and a few intermediate points, and assume fixed velocity and acceleration bounds along each segment of the curve. Since the moments of inertia of the joints of a robot may vary by a factor of three or more, such constant bounds may result in serious under-utilization of the robot. Another approach is to determine the minimum-time solution for sequentialaxis operation, i.e. moving the arm one joint at a time. Such solutions generally give path traversal times which are much longer than those obtained by other techniques. The approach taken in this project has been along entirely different lines from those described above. Since real robots are not constrained in their velocities and accelerations but in their joint torques/forces, we have converted limits on torques to limits on accelerations. Also, since the path that a robot must followhis usually predetermined, it has been assumed that the robot's path is described in terms of a parameterized curve. This converts a six-dimensional problem to a one-dimensional one. Positions, velocities, and accelerations can then be described using the curve's parameter and its first and second derivatives. Having done this, it is possible to determine the limits on the parameter's second derivative (the pseudo-acceleration) from the bounds on the joint torques. Additionally, it is possible to determine upper limits on the parameter's first derivative (the pseudo-velocity). Such velocity limits'arise because at high speeds, centrifugal and Coriolis forces become so large that the actuators cannot generate enough force to keep the manipulator (ne the proper path. (This is much like an automobile skidding off the road when going around a corner too fast.) The minimum-time solution to the control problem can then be shown to consist of a number of segments during which the robot undergoes the maximum and minimum accelerations allowable. The points at which the manipulator switches between acceleration and braking are then determined in such a way that the robot almost, but not quite, goes too fast to stay on its specified path. To date, the results of the project consist of algorithms for computing velocity limits, acceleration limits, and optimal trajectories given the dynamic equations of the robot, the actuator torque constraints, and a set of parametric equations which describe the desired path of the robot. These algorithms together form ACOT, the Algorithm for Computation of Optimal Trajectories [3]. It has been assumed that the torque bounds are constant, but the generalization to torque bounds which are position and velocity dependent is straightforward. In particular, if the torque bounds are at most quadratic in the velocity, then the equations already derived need only have a few subexpressions changed. Since direct-current motors driven from a constant voltage source have torque constraints which are linear in the velocity, the mathematics derived so far applies, with minimal modifications, to most electrically-driven robots. Annual Report 26 August 1, 1982 - July 31, 1983

The algorithms that have been developed generate a true minimum-time solution rather than an approximate one, but require more extensive computations than many approximate algorithms. This is due to the fact that other methods do not take robot dynamics into account except in a very general way, and hence sidestep all the difficulties of dealing with a set of nonlinear, highly coupled differential equations. Further research is needed to determine whether ACOT is computationally simple enough to be used in practical situations, and whether other algorithms in current use give path traversal times which are significantly longer than the true minimum-time solution. So far ACOT has only been applied to a two-degree-offreedom robot. With only two joints, the computations can be done quite quickly. Whether ACOT can run acceptably quickly for a six-degree-of-freedom arm remains to be seen. If other, simpler algorithms yield results which are not close to the true minimum-time solution as computed by ACOT, then better algorithms should be found, or ways should be found to make the ACOT algorithm more efficient; if not, then perhaps further research should be directed more towards finding computational simplifications for the currently-used off-line control algorithms. Note that ACOT does provide a standard against which other control algorithms may be judged. Future work will include a sensitivity analysis and the development of relationships between curvature of the parameterized path and the maximum velocity. Since the minimum-time algorithm will generate trajectories which move just slowly enough so that the robot does not leave the desired path, it will be necessary in practice to underestimate the amount of torque available; some torque must be kept "in reserve" for emergency situations. The sensitivity analysis should give some indication of just how much reserve torque is needed for given variations in such parameters as moments of inertia and friction coefficients. The relationships between curvature and maximum velocity will be useful for deciding what types of curves the robot should follow. The path planning algorithm assumes that the path is completely specified; however, at some point this path must be generateld and some criteria other than avoiding collisions with obstacles would be useful for deciding exactly what path to follow. A logical way to choose the path would be to choose the path which maximizes the upper bound on velocity while avoiding all obstacles in the robot's workspace. This approach differs from previous off-line control (path planning) methods in a number of ways. First, it deals with constraints on torques or forces rather than accelerations; since in practice constraints are on torques/forces and not on accelerations, this is highly desirable. Second, it gives an exact minimum-time solution rather than just an approximation. One minor disadvantage of the technique, shared by the other techniques previously described, is that the minimum-time control must be determined off-line. However, in an environment in which the same task will be performed many times it is not impractical to compute the required joint torques/forces off-line, even if the computations required are fairly extensive. Nevertheless, in order to overcome this drawback, we have attempted to derive an on-line minimum time fuel controller [1]. The controller is based on a very simple but innovative method called the averaying ldynamics to cope with the complexity and nonlinearity of manipulator dynamics —a major hurdle in the development of robot controls. The controller requires about 6 milli-seconds for one iteration Annual Report 27 August 1, 1982 - July 31, 1983

computation if a computer equivalent to the PDP-11/45 is used, indicating a strong possibility of real-time implementation on mini- or micro- computers. Another assumption that we used is the complete knowledge of manipulator dynamics. Although this may hold for most repetitive tasks, in general there are uncertainties in manipulator dynamics. Consequently, we have also investigated an adaptive control of manipulators [2]. The objective was to make (i) the controller able to handle the uncertainties in manipulator dynamics caused by changes in manipulator's payload and position. We used the concept of adaptive model following in which the controller changes both the feedback and feedforward gains in such a way that the outputs from both the reference model and the mranipulator itself become identical. Simulation of these two alternative controls has exhibited high performance. Future efforts will be directed toward refinements and possible implementation of these controllers. References [1] Kim, Byung K., and Kang G. Shin, "Suboptimal Control of Industrial Manipulators with a Weighted Minimum Time-Tuel Criterion", IEEE Trans. on Automatic Control. [2] Kim, Byung K., and Kang G. Shin, "An Adaptive Model Following Control of Industrial Manipulators", to appear in the 1984 January issue of IEEE Trans. on Aerospace and Electronics Systems. [3] Shin, Kang G., and Neil D. McKay, "Minimum-Time Control of Robotic Manipulators with Geometric Path Constraints", submitted to IEEE Trans. on Automatic Control, 3.1.5. Adaptive Control Professor C.S.G. Lee, Professor N.H. McClamroch Problem and Research Objectives The current approach to robot arm control system design treats each joint of the robot arm as a simple servomechanism. Such modeling is inadequate because it neglects the motion and configuration of the whole arm mechanism and the effects of the changes of the load in a task cycle. These changes in the parameters of the controlled system and the load it is carrying are significant enough to render conventional feedback control strategies ineffective. The result is reduced servo response speed and'damping, which limits the precision and speed of the end-effector. The objective of this research focuses on: (1) Various adaptive control schemes both in the joint-variable space and the Cartesian space that tracks a planned trajectory as closely as possible and minimizes the steady-state error of the manipulator hand, (2) Control and coordination schemes for two robot arms working cooperatively in an assembly station. Annual Report 28 August 1, 1982 - July 31, 1983

The long-term goal of this interrelated research, coupled with sensors and senor-guided control research, is to develop a robotic assembly station with two PUMA robot arms that perform highly accurate assembly tasks. Status of the Research Effort Adaptive Control for Computer-Based Manipulators: Joint Motion An adaptive control based on the perturbation equations in the vicinity of a desired trajectory has been studied [1-2]. The highly coupled nonlinear dynamic equations of a manipulator are expanded in the vicinity of a preplanned joint trajectory to obtain the linearized perturbation equations. A linear quadratic controller is then designed for the linearized perturbation equations about the desired trajectory. The joint torques consist of the nominal torques computed from the Newton-Euler equations of motion and the variational torques computed from the perturbation equations. An efficient recursive least square identification scheme is used to perform on-line parameter identification for the unknown parameters in the perturbation equations. The parameters of the perturbation equations and the feedback gains of the linear quadratic controller are updated and adjusted in each sampling period successively to obtain the necessary control effort. This adaptive control strategy reduces the manipulator control problem from a nonlinear control to controlling a linear control system about a desired trajectory. Furthermore, a clear advantage of such a formulation is that the nominal and variational torques can be computed separately and simultaneously. Computer simulation studies of a three-link PUMA robot arm have been performed on a VAX-11/780 computer to evaluate the validity of the use of the perturbation equations and the performance of the adaptive controller. A more detailed discussion and derivation of the adaptive control with computer simulation can be found in 12]. This was part of M.J. Chung's thesis work, co-supervised by Professor N.H. McClamroch and Professor C.S.G. Lee. Resolved Motion Adaptive Control for Mechanical Manipulators Most of the existing control schemes [3-8] control the arm at the joint level and emphasize nonlinear compensations of the interaction forces among the various joints. For most applications, resolved motion control, which commands the manipulator hand to move in a desired Cartesian direction in a coordinated position and rate control, may be more appropriate. As an extension of the above adaptive control, C.S.G. Lee and B.H. Lee have investigated an adaptive control in the Cartesian coordinates. Most existing resolved motion control algorithms [9-10] control the arm at the hand level without external sensory feedback information. The above joint motion and resolved motion control algorithms are inadequate because they neglect the changes of the load in a task cycle. This need prompts the development of a resolved motion adaptive control which adopts the ideas of resolved motion rate control and acceleration control and extends the above adaptive control using the linearized perturbation system to control the manipulator in Cartesian coordinates for various loading conditions. The proposed resolved motion adaptive control is performed at the hand level and is based on the Annual Report 29 August 1, 1982 - July 31; 1983

linearized perturbation system along a desired hand trajectory. A recursive least square identification scheme is used to perform on-line parameter identification of the linearized perturbation system. The controlled system is characterized by feedforward and feedback components which can be computed separately and simultaneously. Such formulation has the advantage of employing parallel computation schemes in computing these components. The feedforward component resolves the specified positions, velocities, and accelerations of the hand into a set of values of joint positions, velocities, and accelerations from which the nominal joint torques are computed using the Newton-Euler equations of motion to compensate all the interaction forces among the various joints. The feedback component computes the variational joint torques which reduce the manipulator hand position and velocity errors along the nominal hand trajectory. This adaptive control strategy reduces the manipulator control problem from a nonlinear control to conrotrolling a linear control system about a desired hand trajectory. Considering the resolved motion adaptive control for a six-link manipulator and assuming that the desired hand positions, velocities and accelerations along a path/trajectory in Cartesian coordinates are given, a feasibility study of implementing the adaptive controller using present day low-cost microprocessors is conducted by looking at the computational requirements in terms of mathematical multiplication and addition operations. The study assumes that multi-processors are available for parallel computation of the proposed controller. The feedforward component which computes the nominal joint torques along a desired hand trajectory can be computed serially in four separate stages. Computational requirements in term of multiplications and additions for the feedfore ward component indicate the requirement of 1341 multiplications and 973 additions. The feedback control component which computes the variational joint torques can be conveniently computed serially in three separate stages. It requires about 3427 multiplications and 3037 additions. Since the feedforward and feedback components can be computed in parallel, the propbsed resolved motion adaptive control requires a total of 3427 multiplications and 3037 additions in each sampling period. Present day microprocessors still do not have the required speed to compute the proposed controller within 10 Ins. This may be solved by a high-performance attached processor or a custom designed VLSIC chip. The above analysis presented an ideal system study because it neglected such nonlinear effects as gear friction and backlash. The physical implementation of the proposed adaptive control may require further investigation on the effects of gear friction, backlash, control device dynamics, and flexible link structure to the controller. A more detailed discussion and derivation of the resolved motion adaptive control can be found in [11]. Future work will focus on computer simulation to verify the validity of the proposed resolved motion adaptive control scheme. Based on the simulation result, more efficient resolved motion control strategies will be proposed that can be implemented using present day low cost microprocessors. Control and C(oordination of Two Cooperative Robot Arrns i n an Assembly Station Significant gain in productivity can be achieved by automating batch assembly production. Efficient use of two or more robot arms in an assembly station will greatly improve productivity and quality of end-products. C.S.G Lee and B.H. Lee have begun looking at the problem of controlling and coordinating two cooperative Annual Report 30 August 1, 1982 - July 31, 1983

robot arms working in an assembly problems. Problems such as controlling each robot arm efficiently, synchronizing the control processes for each robot arm, avoiding manipulator hands' collision in the common workspace, force feedback control in fine motion, and time-space trajectory planning for two robot arms. Research to date has provided some solution to the above problems, in particular algorithms for avoiding manipulator hands' collision and efficient joint control of each robot robot. Future research will be directed solving the remaining problems in multirobot assembly systems. Computer simulation will be conducted to verify the validity of the research results. Later, actual implementation of the algorithms will be carried out on our PUMA robot arms. References [1] Lee, C. S. G., M. J. Chung, "An Adaptive Control Strategy for Computer-Based Manipulators," Proceedings of the 21st Conference on Decision and Control, Dec. 8-10 1982, Orlando, Florida, pp 95-100. Also issued as CRIM Technical Report RSD-TR-10-82, the University of Michigan, August 1982. [2] Chung, M. J., "Adaptive Control Strategies for Computer-Controlled Manipulators," Ph. D. Dissertation, the Computer, Information, and Control Engineering Program, the University of Michigan, Ann Arbor, August 1983. [3] Kahn, M. E., B. Roth, "The Near-Minimum-Time Control of Open-Loop Articulated Kinematic Chains," Transaction of the ASME, Journal of Dynamic Systems, Measurement and Control, Vol. 93, Sep. 1971, pp 164-172. [4] Paul, R. P., "Modeling, Trajectory Calculation and Servoing of a Computer Controlled Arm," Stanford Artificial Intelligence Laboratory, A.I. Memo 177, Sep. 1972. [5] Bejczy, A. K., "Robot Arm Dynamics and Control," Technical Memorandum 33-669, Jet Propulsion Laboratory, Feb. 1974. [6] Hemani, H., P. C. Camana, "Nonlinear Feedback in Simple Locomotion System," IEEE Transactions on Automatic Control, Vol. AC-19, Dec. 1976, pp 855-860. [7] Young, K. K. D., "Controller Design for a Manipulator Using Theory of Variable Structure Systems," IEEE Transactions on Systenms, Man, and Cybernetics, Vol. SMC-8, No. 2, Feb. 1978, pp. 101-109. [8] Luh, J.Y.S., M.W. Walker, and R.P. Paul "Resolved-Acceleration Control of Mechanical Manipulators," IEEE Transactions on Systems, MAan, and Cybernetics, Vol. 25, No. 3, June 1980, pp 468-474. [9] Whitney, D. E., "Resolved Motion Rate Control of Manipulators and I-Iuman Prostheses," IEEE Transactions on Man-Machine System, Vol. MMS-10, No. 2, June 1969, pp 47-53. [10] Luh, J. Y. S., M. W. Walker, and R. P. Paul, "Resolved-Acceleration Control of Mechanical Manipulators," IEEE Transactions on Automatic Control, Vol. AC25, No. 3, June 1980, pp 468-474. [Ii] Lee, C. S. G., M. J. Chung, J. L. Turney, and T. N. Mudge, "On the Control of Mechanical Manipulators," Proceedings of the Sixth IFA1C Conference in Estimation and Paramneter Identification, Washington D.C., June 1982, pp. 14541459. Annual Report 31 August 1, 1982 - July 31, 1983

3.1.6. Manipulator Compliance Professor N.H. McClamroch, Professor Y. Koren, Professor A.G. Ulsoy General Research Objectives The general objective is to characterize the sources of manipulator compliance and their effects on manipulator motion control. Sources of manipulator compliance include: 1. Link flexibility: ideally a robot should have a lightweight yet rigid structure. There is, however, a trade-off between these requirements and light weight robots can be flexible enough for arm vibrations to noticeably deteriorate accuracy. For a given robot structure there is, in general, also a trade-off between speed and accuracy. This is because high speed operation leads to high inertial forces which in turn cause vibrations and deteriorate accuracy. The purpose of this research is to investigate the possibility of improving the performance of a robot arm by taking the flexibility of the arm into account in the design of the controller. 2. The actuators' internal characteristics: some mechanical compliance arises from use of electrical servo motors as control actuators; substantial mechanical compliance occurs if either electrohydraulic or (especially) electropneumatic actuators are used to control manipulator motion. 3. Transmission of force/torques from the actuators to the links; mechanical compliance can arise if transmission is through either gear trains or cables, especially if the cables are elastic. The manipulator compliance effects lend extra complexity, to the equations of motion when link flexibility, actuator dynamics and transmission compliances are included; control design, taking such effects into account, is exceedingly difficult. Status of the Research Effort Control of a Flexible Robot Arm The flexible robot arm control problem is being investigated by Professor A.G. Ulsoy and Mr. N. Chalhoub using analytical methods, simulation, and laboratory experimentation. A spherical coordinate laboratory robot is being used as the focus of this study. A dynamic model of the robot, including the effects of the flexibility of the final link, is being formulated as the basis for analytical and simulation studies. The interrelationships between the robot structural flexibility and the controller designed is being investigated. These relationships will be used as the basis for designing and evaluating controllers for the flexible as well as the rigid body motions of the robot arm. The dynamic modeling and simulation of the laboratory robot, including the flexibility of the final link, has been completed. Also completed is a review of the literature on control of flexible robot arms. The modeling and simulations study describes and demonstrates several potential mechanisms by which the structural dynamics and controller design can interact. These include resonance, parametric excitation, excitation due to inertial forces, and the effects of constraints due to Annual Report 32 August 1, 1982 - July 31, 1983

transmission mechanisms such as leadscrews. The construction of a small laboratory robot for use in experimentally evaluating potential controller strategies is essentially complete. The remaining task is completion of the electronic interface required to connect the robot arm to a standard microcomputer. It is expected that this study will lead to a better understanding of the interaction between structural design and controller design for robot arms. In addition it is expected that one or more potential controller designs for rigid body and flexible motion will be developed and evaluated through simulation and experimental studies. Control of a Cable Actuated Manipulator The research has examined a two-link manipulator using dc servo motors on each link to control the torque transmitted to the links via elastic cables. The open loop (uncontrolled) manipulator has been evaluated in terms of its mechanical characteristics; attention has been given to the study of the effects of actuator dynamics and cable elasticities on the dynamics of the manipulator. This work is being carried out jointly by Professor N.H. McClamroch with Mri: H. P. Huang. Various feedback control strategies are being studied. Use of conventional joint displacement feedback control is feasible. But of more interest is the use of mechanical compliance information or electrical servo motor internal voltages or currents which indirectly yield information about the load forces; hence such easily instrumented signals may prove particularly effective for feedback control. Mathematical Aspects of Control of Flexible Structures To support the applied research on control of compliant manipulators several basic research topics have been investigated by Professor McClamroch. This includes the mathematical theory of sampled data controlled structures. The mathematical development is in terms of second order vector recursive equations, where the matrix coefficients depend on the system compliance. Since sampling introduces an effective delay into feedback controlled systems the research has focused on the development of conditions for closed loop stability. It is expected that such results will prove useful in taking sampling effects into account in control of manipulators. A related research topic has focused on the inclusion of actuator dynamic effects as part of the control of a flexible system. Motivated by robotic applications, both electrical d.c. servo motors and electrohydraulic servos have been studied as actuators for control of a flexible system. As increased speed and accuracy of manipulator motion is required the effects of the actuator dynamics became more important. Research to date has been concerned with the development of fundamental forms for models of the actuator and flexible structures, as well as some simple feedback control strategies. 3.2. Integrated Solid-State Sensors for Closed-Loop Robot Control Among the many challenges confronting the realization of advanced robots and automated manufacturing facilities, the need for improved sensors is one of the most critical. Sensors represent the primary path by which data on the environment, Annual Report 33 August 1, 1982 - July 31, 1983

activity, or process being performed is gathered, and in spite of increasingly powerful processors, they are only as capable as their input data allows. With increasing levels of automation, greater and greater emphasis must be put on sensor accuracy and reliability as well as their simple existence. In many cases, the needed sensors do not now exist, and in most cases those that do are inadequate in performance, reliability, or both. The sensor area has been increasingly active during the last few years as the result of needs in a broad array of application areas, especially in transportation and health care. Serious efforts in robotics and integrated manufacturing are relatively recent, however, with the first prototype devices only now emerging. While a variety of approaches have been used for sensor fabrication, most current structures are based on the use of solid-state batch process technology. The resulting integrated sensors allow the formation of both transducers and custom interface circuitry on the same chip. The result is improved performance and reliability [1-3]. Integrated sensors represent one principal thrust area for the Solid-State Electronics Laboratory at Michigan. Past work has concentrated on infrared [4], pl- [5], and pressure sensors [6-8] as well as on custom interface circuitry [9-11]. In the robotics area, two new sensing arrays have been targeted for our initial research efforts under this program: a linear thermal imaging array for process control applications, and an area tactile imager for use in robotic touch. Both of these devices are badly needed and are described in the sections below. These discussions are followed by comments on work to define control strategies capable of using sensor data in the parts insertion process. Machine recognition of the sensor data is the second half of the problem of developing any practical automated sensing system. Our initial work here is focused on data derived from a commercially-available wrist force sensor. Similar efforts to utilize data from the tactile imager are expected to begin during the second year of this contract as the first tactile arrays become available. Current work in machine vision, described in section 3.3 below, will also form a basis for handling the thermal imaging data. It must be emphasized that our goal is the development of practical high-performance sensing systems. In this context, work on sensing structures cannot be separated from work to develop improved machine recognition systems. Ultimately, these efforts are interrelated and interactive. 3.2.1. A 256-Element High-Performance Tactile Imager Professor K. Wise Problems and Objectives There is general agreement that tactile sensors are among the most criticallyneeded devices for future robot systems. While the appropriate requirements for such a device are not precisely known, the specifications listed in Figure 3.2.1.1 are typical initial goals. The devices should be rugged and stable in performance over time, with 100-300 elements spaced on 1-2 mm centers yielding a resolution equivalent to about 6 bits (1-2 percent of scale). To meet these goals, there are several possible approaches. Nearly all previous efforts have utilized conductive Annual Report 34 August 1, 1982 - July 31, 1983

* Resolution: 4 - 6 bits/pixel * Element Spacing: 1 - 2 mm * Array Size: 256 Elements * Response Time: 1 - 10 msec * Wide Dynamic Range * Bus-Compatible Output * Wide Operating Temperature Range * Stable Sensitivity * Environmentally Rugged * High Damage Threshold Figure 3.2.1.1 Tactile Image Requirements in Robotics rubber as the transducing medium together with an X-Y grid of wires for readout. This approach is relatively simple but suffers from a number of serious problems. The structural dimensions and wire positions are difficult to control and maintain. The rubber is unpredictably temperature sensitive, possesses significant hysteresis, and is no, particularly stable over time. Thus, while simple binary touch sensors can be realized with this approach, it does not appear capable of meeting the practical needs of a production system. The approach to tactile sensing we are pursuing is based on a silicon capacitive pressure transducer recently developed [7]. Such devices have been shown to offer roughly an order of magnitude greater pressure sensitivity and an order of magnitude less temperature sensitivity than their piezoresistive counterparts. The proposed tactile sensing cell is shown in Figure 3.2.1.2. A silicon wafer is selectively etched on the front side to form a recessed area approximately 4/Cm deep. The wafer is then subjected to a deep boron diffusion and is subsequently etched selectively from the back to form a thin (15,um) diaphragm behind the front recess. The silicon is then selectively metalized to form one plate of a parallel-plate capacitor. The second plate is formed by a metalization pattern on the glass to which the silicon is electrostatically bonded. With pressure (or force) applied from the top (Figure 3.2.1.2), the silicon diaphragm deflects proportional to the applied pressure, changing the capacitance. The thickness of the diaphragm is controlled by the depth of the boron diffusion to an absolute accuracy of about three percent and a uniformity of better than one percent. The electrostatic bond is free from deformation, hermetic, and irreversible. All dimensions are controlled by photolithography and are reproducible to 0.5gm. As pressure is applied, the capacitance shift at maximum pressure is more than the zero-pressure (undeflected) capacitance. When the plates touch, a natural strain Annual Report 35 August 1, 1982 - July 31, 1983

/DEFORMABLE PAD OUTER SKIN liA t?' 00*ACC ESS SEiL 3 REFERENCE CAVITY t GAP FOR LEAD PASSAGE GLASS PLATE / / / / / / / SUPPORT BASE 7 / / / / / A / Figure 3.2.1.2 Capacitive tactile sensing cell relief is provided, allowing overpressures of well over an order of magnitude above the maximum operating pressure. The capacitance has a very low temperature coefficient (30 ppm/~ C) and a pressure sensitivity which can be scaled over three orders of magnitude by adjusting the diaphragm thickness. Thus the transducer itself is a high-performance device which can be fabricated reproducibly in array form. The coupling medium between the outside world and the transducer is an important part of the structure and is an area where several questions remain. Polysilicon (or tantalum) row lines are formed on the The present approach uses a perforated plate over the silicon chip and an outer (replaceable) skin. Between these layers is a deformable contoured pad. Access holes filled with air or a semisolid (such as silastic) provide coupling to the transducer. Once full working arrays have been fabricated, various coupling materials and structures will be explored. Figure 3.2.1.3 shows how an array of these pressure cells can be configured to form an imager. silicon, each row joining a series of plates. On the glass are a series of orthogonal column lines, each composed of a series of plates aligned with the row plates. Thus an X-Y array of capacitors are formed, one at each row-column intersection. These transducers, on 2 mm centers, have a capacitance of only about 1 pF, so that readout circuitry must be compatible with row-column organization and capable of resolving capacitance shifts of 5f F or less. Results to Date Figure 3.2.1.4 showvs a section of an 8 x 8 tactile imager now being developed as a prototype device. The required process for such an array has been demonstrated and has been designed to minimize the possibility of row-substrate or row-column Annual Report 36 August 1, 1982 - July 31, 1983

CPO Coluns (Metallization on Glass) -, I I/ Iil''CoiTns (Metallization on Glass) f: T a b r * /' ----. —--' Figure 3.2.1.3 An 8x8 array of pressure cells making up a tactile image. T'he 9th row is a reference for differential outputs. shorts. This is essentially due to the large die size (2X2.2cm) of the sensor and the large amount of total capacitance involved (more than 10-OF per row). Test results on 22 cell arrays having diaphragms measuring 800x800x17Am have shown a capacitance change of about 20 percent at 15 psi when used with a 4,um capacitive gap. The maximum operating pressure (where the plates touch) is about 27 psi. The first full 8X8 arrays should be ready for testing in NoVember of 1983. The development of appropriate readout circuitry is vital to this sensor and has been the thrust of considerable effort during the past year. The circuit developed is shown in Figure 3.2.1.5. In operation, a selected row line is switched from a low voltage ( GND) to a high level ( VDo) while a second (dummy) row, without diaphragms, is switched between VoD and GND. In the case of zero applied pressure, the capacitances to the various column lines from the selected row and the dummy row are equal so there is no net charge transferred to the columns. However, when a given Annual Report 37 August 1, 1982 - July 31, 1983 The ~ O deeo men =faporaeraotcrutvi iult hssno n a

DE3 ][33l;!l I 1 I gIZZnIE1 Figure 3.2.1.4 Photomicrog-raphs of Sections of an 8x8 prototype tactile sensing array. Top: MNetallization pattern and recesses on silicon. (rows run horizontally) Bottom: Metalization on glass. (vertical columns) row-column capacitance changes due to applied pressure, a net charge appears as input to the integrating amplifier. The output voltage from this amplifier is Vo =-'DD " C - D where CR, CD, and CF are the row, dummy, and integrating feedback capacitances, respectively. The output voltage is largely independent of amplifier gain or shunt Annual Report 38 August 1, 1982 - July 31, 1983

RESET V = V M vpm DD 2 I — A — MID CR(row-column) (Z/L)2 I'5 1 A R 4,^-l.,, 2 v X C| V out out l Cc Ac o with the operating input waveforms and expected output response. i t c i, wi t m V (C c b out PM R F voltage at the integrator as well as reset noise from the reset switch can be cancelled using correlated double sampling. RESET - - 1 Figure 3.2.1.6 shows an integrated realization of this circuit approach in silicongate NMOS LOCOS technology. The chip shown realizes four readout circuits and or has been show capabctile of reoing capacitance chan. The general circuit fi-diagram is shown above ogeher planned in the opertactile input waveforms and expected output response. Figure 3.2.1.7 shows the cross-section of a proposed mounting arrangement for tance matrix on one chip and the pareadout circuitry oers V and C can two smaller chips which willset us contain correlated double sampling. The ro driver circuits, which must drive gate NMIOS LOCOS technology. The chip shown realizes four readout circuits and has been shown capable of resolving capacitance changes of IfF. The circuit configuration appears ideally suited to matrix transducer arrangements and its use is planned in the tactile imager. the imager. We currently plan to realize this sensor as a hybrid, with the capaciapproximately lnF, may be external since relatively standard commercial drivers appear adequate here. Annual Report 39 August 1, 1982 - July 31, 1983

RESET V C -CR = RESET t2 out CX-CR= 5.4 pF with a Tactile Sensing Array. Top views show the MOS circuitry in a die measuring 2x2.7 mm. Lower views show readouts from the circuit (10V/div except 2V/div output, 100/sec/div). In summary, we are exploring a tactile imager based on a silicon capacitive pressure transducer. Prototype cells have been developed and characterized along with a high-yield process for large arrays. Readout circuitry has been defined, integratecl, and tested. In coming months, complete 8x8 transducer arrays will be fabricated and characterized. An optimized quad readout chip will also be designed andl integrated so that by the end of the second year we hope to report test results on a complete 8x8 tactile sensor. Annual Report 40 August 1, 1982 - July 31, 1983

OUTER SKIN/,ACCESS HOLES ICOVER PLATE ////// /////GLASS 77 SUPPORT BASE \ IC SILICON TRANSDUCER ARRAY BASE PLATE SILICON TACTILE IMAGING ARRAY Figure 3.2.1.7 Proposed Mounting Arrangement for the Silicon Tactile Imaging Array. 3.2.2. A Silicon Thermal Imager for Process Control Applications Professor K. Wise Problems and Objectives As a second program in the robotic sensing area, we are developing a broadband infrared imaging array based on silicon technology. The goal is a 64-element line imager capable of operation at room temperature in the 8-14/im spectral band. The approach is based on the thermopile shown in Figure 3.2.2.1. Silicon is selectively removed from a silicon wafer to form windows which support the hot junctions of a series-connected thermocouple array. Incident infrared radiation heats the thin window, and the thermopile converts the temperature rise into an electrical output signal. Previous efforts [4] in this area concentrated on single-point detectors employing thin (0.5-1-um) silicon windows 2x2 mm in size. In order to realize a practical line imager, the vertical element separation must be reduced considerably while maximizing detectivity. Analysis has shown that a thermopile array consisting of 40 (p+) polysilicongold thermocouples and dielectric windows (no underlying silicon) can produce a detectivity of about 5X10 cm \/hz/, a responsivity of 17.1 V/W, and a response time of 7.1 msec using a window size of 0.4x0.8 mm. Using two staggered columns of these detectors, an effective vertical spacing of 0.25 mm can be realized. In an imaging mode with a 5 cm lens diameter, this sensor would realize a noise equivalent temperature difference (NETD) of about 1~ C and MRTD of 2-3~ C at fr= 0.2 cycle/mrad. This spatial frequency corresponds to a pattern repetition length of 5 cm at a distance from the detector of 20 meters. The performance is computed at room temperature in the 8-14 gam band. Annual Report 41 August 1, 1982 - July 31, 1983

Cold Junctions Interconnecting Leads Hot Junctions Thick Supporting -Rim - Thin Window', I iArea Top View Silicon Metal Absorber (Bi Black) Dioxide Interconnect Metal B Metal A _______\ ______ X Silicon;-:_ i Rim Cross Section Case Figure 3.2.2.1 Structure of a Silicon-Based Thermopile Infrared Detector. The hot junctions of the series-connected thermocouples are supported on a selectively-formed thin window. For applications in a thermal imager, the silicon membrane shown in the window has been eliminated, allowing higher levels of detectivity to be obtained at reduced window dimensions. This thermal imager is being developed for use in automated process control applications where moderate levels of resolution are acceptable and cooling to 77 ~ is undesirable. In such applications, the above performance should be quite adequate. While photon-based devices in HgCdTe or silicon can produce higher detectivity and spatial resolution, they require cooling and offer a considerably reduced spectral bandwidth. In the case of non-silicon arrays, the material technologies required are as yet immature. In contrast, the thermopile approach is based on low-cost silicon technology and is compatible with on-chip MOS circuitry for signal multiplexing and amplification. When used in a purely imaging (scanning) mode, as opposed to a staring mode for process characterization, it is expected that such a sensor will be used as an adjunct to a visible area imager. Annual Report 42 August 1, 1982 - July 31, 1983

uIIIIIIIIIIB111111111111111i1 Figure 3.2.2.2 Formation of Thin Dielectric Windows in a Silicon Wafer for us in a Thermal Imager. The windows are formed using CVD silicon oxynitride layers and will support thermopile infrared detectors for a line imager. Results to Date Following the above analysis of the tradeoffs between performance and structure, work was initiated to develop a fabrication sequence capable of realizing the desired array. A major challenge was the development of a practical technique for window formation using CVD layers of silicon dioxide and silicon nitride. The dielectric film must be strong and in moderate tension at room temperature. Such a process has been developed. Figure 3.2.2.2 shows several window arrays recently fabricated. As noted above, the window dimensions are 0.4mmx0.8 mm. While some window breakage during Annual Report 43 August 1, 1982 - July 31, 1983

Figure 3.2.2.3 View from the Back Side of the Wafer of Windows for a Thermopile Infrared Line Imager. The dielectric windows have dimensions of 0.4x0.8mm with a surrounding rim of boron-doped silicon. The windows are formed using selective anisotropic etching. processing has occurred, initial window yields have nonetheless been above 97 percent and we feel can still be improved significantly. Figure 3.2.2.3 shows one series of these windows. The supporting ribs between adjacent windows are formed from boron-doped silicon and are 15Mm thick. The yield on this process is very high. Figure 3.2.2.4 shows a series of detectors being fabricated as a prototype thermal imager. The thermopiles are composed of 42 polysilicon-goi4d thermocouples. Silicon-gate MIDS devices are included to assess process compatibility with on chip multiplexing circuitry. VWe believe the process technology for the thermal imager to be in-place at this time. During the coming year we hope to complete the characterization of the detector elements and to fabricate 64-element linear imaging arrays with on-chip readout circuitry. These arrays will then be evaluated for applications in automated manufacturing and robotics. Annual Report 44 August 1, 1982 - July 31, 1983

iII Figure 3.2.2.4 Photomicrographs of a Prototype Thermopile Infrared Line Imager. A 40-thermocouple detector is supported on each window. Feature size is 10jtm. References [1] \Wise, K.D., "Integrated Sensors; Interfacing Electronics to a Non-Electric NW-orld," Sensors and Actuators, 3, pp 229-237, July 1982. [2] Wise, IK.D., "Integrated Biomedical Sensors," Proc. Fotrth Brazilian 1Wlorkshop on Microelectronics, Campenas, pp 237-243, February 198.3. [:3] Wise, IK.D., ed., "Special Issue on Solid-State Sensors, Actuators, and interface Electronics," IEEE Trans. Electron Devices, 29, January 1982. Annual Report 45 August 1, 1982 - July 31, 1983

[4] Lahiji, G.R. and K.D. Wise, "A Batch-Fabrication Silicon Thermopile Infrared Detector," IEEE Transactions on Electron Devices, 29, pp 34-41, January 1982. [5] Huang, J.C.M., and K.D. Wise, "A Monolithic Pressure-pH Sensor for Esophageal Studies," Digest of Technical Papers, 1982 Int. Electron Devices Meeting, pp 316-319, December 1982. [6] Lee, K.W. and K.D. Wise, "SENSIM; A Simulation Program for Solid-State Pressure Sensors," IEEE Transactions on Electron Devices, 29, pp 14-22, January 1982. [7] Lee, Y.S. and K.D. Wise, "A Batch Fabrication Silicon Capacitive Pressure Transducer with Low Temperature Sensitivity," IEEE Transactions on Electron Devices, 29, pp 42-47, January 1982. [8] Kim, S.C. and K.D. Wise, "Temperature Sensitivity in Silicon Piezoresistive Pressure Transducers," IEEE Trans, Electron Dvices, 30, pp 802-810, July 1983. [9] Borkey, J.M. and K.D. Wise, "Integrated Signal Conditioning for Silicon Pressure Sensors," IEEE Transactions on Electron Devices, 26, pp 1906-1910, December 1979. [10] Park, Y.E. and K.D. Wise, "An MOS Switch-Capacitor Readout Amplifier for Capacitive Pressure Sensors," Proc. IEEE Custom IC Conference, pp 380-384, May 1083. [11] Wise, K.D. "Circuit Techniques for Integrated Solid-State Sensors," Proc. IEEE Custom IC Conference, pp 380-384, May 1983. 3.2.3. Force Feedback Control for Insertion Process Professor C.S.G. Lee Research Objectives The primary objectives of force feedback control focus on designing an active compliance control strategy that (i) effectively utilizes the force sensory feedback information to control the arm in fine motion, and (ii) incorporates pattern recognition methods for force recognition and guidance control so that the manipulator can improve its performance in fine motion. Status of the Research Effort The pattern recognition techniques embedded in the force control strategy require that the control space be partitioned into groups of "control situations" in which appropriate best control law will be used to control the arm's end-effector. The guidance control then improves the performance of the arm by updating/modifying the feedback gains of the appropriate control law in each of the control situation. Similar approach of using a combination of pattern recognition and modern control theory has been used successfully in other areas. The pattern recognition method for force recognition is based on a structural approach to estimate the probability density function of the force readings to be used for recognizing various contact configurations in insertion process. This can be Annual Report 46 August 1, 1982 - July 31, 1983

accomplished by generating a random contact configuration of the type belonging to a class w, and this will in turn generate "admissible" random contact reaction forces. Then the resolved force sensor vectors can be calculated based on the geometric constraints and the quasi-static equilibrium conditions. This process can be repeated for a large number of times and the probability density function of the force readings can be found from the synthetic sampling technique. At this time, we are at the stage of performing computer simulation of the insertion process on our VAX-11/780 computer. (i.e. try to verify the validity of using pattern recognition method for recognizing resolved force vectors for various contact situations.) We have completed instrumenting our PUMA robot arm with a wrist force sensor from Robot Technology Inc. Sensor calibration and the related software are being written. A more detailed discussion of force feedback control for insertion process can be found in [2]. Our major efforts for the next year will be in the following areas: * Continue our modeling and computer simulation of the insertion-process for various contact configurations and implement the proposed pattern recognition method for force recognition on our PUMA robot arms equipped with wrist force sensors. The objective is to verify experimentally the equations governing the geometric force constraints and the quasi-equilibrium conditions of the insertion process and the use of pattern recognition for recognizing these configurations. * Continue to investigate the guidance control for insertion process for PUMA robot arms. References [1] Lee, C.S.G. Lee, M.J. Chung "An Adaptive Control Strategy for Computer Based Manipulators," Proceedings of the 21st Conference on Decision and Control, Dec. 8-10, 1982, Orlando, Florida, pp 95-10. [2] Luh, J.Y.S., M.W. Walker, R.P. Paul, "Resolved-Acceleration Control of Mechanical Manipulators," IEEE Transactions on Automatic Control, Vo. AC025, No. 3, June 1980 pp 468-474. 3.3. Vision for Robotics Vision is of such importance to robotics and manufacturing that is reported separately from other sensing research. Vision will be used extensively for all manner of inspection and as a key component in automated assembly, welding and sorting operations. While commercial vision systems have recently been introduced to the marketplace they are relatively crude devices incapable of adequately handling many important problems. The use of grey level information is rudimentary at best. The acquisition and use of range or depth data exists only in research labs, and still requires more research. Little has been done with moving objects. The "bin of parts" problem remains inadequately solved, and the processing time for many algorithms remains unusably long. Several aspects of these problems are being addressed by CRIM, including Annual Report 47 August 1, 1982 - July 31, 1983

* The development of enchanced edge detection algorithms: this is at the heart of many vision algorithms * The development of vision algorithms for tracking and identifying moving objects (also problems involving moving cameras or movement of both object and camera). * The reconstruction of three dimensional surfaces from visual inputs: among the goals here are dimensional part inspection * The development of new more effective algorithms for the recognition of occluded parts * The direct optical processing of images: the goal here is to reduce processing time dramatically * The analysis of vision operations to determine the class of special computer architecture best suited for implementing the operation. The following sections describe the status of the AFOSR funded work in each of there areas. 3.3.1. Edge Detection Using Contour Tracing Professor E. Delp Problem Description and Research Objectives The fundamental step of image analysis is segmentation, which partitions an image into individual objects. One method of segmentation is gray level edge detection. The output of edge detectors are usually linked together to form continuous boundaries for further processing, such as shape analysis. Hence, besides the accuracy in edge location, desirable features of the output should also include thinness and continuity of edge segments. We have developed a new edge detection algorithm and have compared its performance with various other algorithms. An approach to edge detection using the direction information provided by both the gradient masks and template masks operators has been examined. The edge direction is used to trace an edge segment. Five edge operators developed using this approach have been investigated. An evaluation of their performances compared to conventional operators like the Sobel operator, three-level template matching operator and the Frei-Chen operator indicates they produce better connected edge segments and thinner edges. Results of applying these edge detectors to real-world images have also been investigated. Edge Detection by Contour Tracing We shall assume that the edge direction at any point is perpendicular to the gradient dlirection. In general terms, to be classified as an edge point, a pixel must be at the appropriate spatial location relative to a previously found edge point, have an edge direction that provides good continuation with previously found edge points, and have edge strength above a certain threshold. The gray level of the point and its neighbors can be used to vary this threshold from pixel to pixel. This is useful when correcting for illumination variance effects. Annual Report 48 August 1, 1982 - July 31, 1983

In our decision strategy, the picture is scanned row by row. Our criterion for a good starting point is for the edge strength value to be above a preset threshold. Two criteria that use both the strength value and the edge direction for determining the next edge point have been considered. The algorithm has two modes: a search mode that searches for a contour start point and a trace mode that traces an edge segment. The algorithm starts in the search mode. Starting at the upper left corner, it searches for a pixel with edge strength above a preset contour start threshold and which is not already an edge point. This contour start point is classified as an edge point, and the algorithm enters the trace mode and begins to trace an edge segment. Consider a 3 X 3 window centered on an edge point that has just been found. If the edge direction at the center pixel points in the direction d ( d E {0,1,...,7} ) then only the 3 neighbors corresponding to (d- 1), d, and (d + 1) (mod 8) are considered as candidates for the next point on the edge. Two criteria for determining the next point have been considered: one emphasizing the edge strength value and the other emphasizing the edge direction value. After determining the next edge point, the window is moved to that pixel and another edge point is searched for. If no next point can be found, the edge segment is terminated. The newly found contour is merged with any previously found contours if they are connected to each other. If the contour length is below a minimum value, the contour is rejected. The algorithm then returns to the search mode at the neighbor of the original contour start point to search for the next start point. The algorithm terminates when the lower right corner is reached. Edge Detectors Implemented From the above discussion, different edge detectors can be developed using various combinations of spatial operators (which produce edge strength and edge direction information), next-point criteria, and threshold selection methods. The spatial operators, which can be gradient masks or template masks, are used to generate an edge strength map and an edge direction map. The edge strength map is then scanned row-by-row from the top left corner for a contour start point that has strength value above a contour start threshold and is not already an edge point. This start point is then classified as an edge point. Once we are on an edge segment, either of the two next point criteria that use both strength and direction information can be used to search for the next point on the contour. If no next point can be found, the contour is terminated and it is merged with any previously found contours that are connected to it. If a contour is too short, it is rejected. After finding a contour, the edge detector returns to look for another contour start point until it reachers the lower right corner of the image. Five edge detectors have been implemented: (1) isotropic gradient masks, the strength based next-point criterion, and fixed threshold. (2) isotropic gradient masks, the strength based next-point criterion, and FreiChen classification rule. (3) 3-level template masks, the strength based next-point criterion, and fixed threshold. Annual Report 49 August 1, 1982 - July 31, 1983

(4) 3-level template masks, the strength based next-point criterion, and locally adaptive thresholds. (5) isotropic gradient masks, the direction based next-point criterion, and fixed threshold. Performance The desirable features of the output of an edge detector include accuracy of edge location, good continuation and thinness of edge segments. The new edge detectors that were presented above were evaluated using Pratt's Figure of Merit and Kitchen and Rosenfeld's Measure. These figures of merit have been widely used to test edge detector performance. Also included in the test for comparison are: (1) Sobel operator (2) Isotropic gradient operator (3) Frei-Chen operator (4) 3-level template machining operator (5) 3-level template matching operator with Locally-Adaptive Thresholds The above operators do not use direction information. Robinson proposed an edge detection algorithm that uses spatial operators to enhance a picture to form a magnitude map and an edge direction map. Both magnitude and direction value are then used to decide if a pixel is an edge point. The following operators are implemented with the Robinson's connectivity test and are included in our tests: (1) Sobel operator with Robinson's connectivity test (2) Isotropic gradient operator with Robinson's connectivity test (3) Frei-Chen operator with Robinson's connectivity test (4) 3-level template matching operator with Robinson's connectivity test (4) 3-level template matching operator with Locally-Adaptive Thresholds and Robinson's connectivity test Independent Gaussian noise was added to test images at signal to noise rations of 100, 50, 20, 10 5 and 2. The test image used for Pratt's measure was 128 x 128 pixels and consisted of a left panel with gray level 115, a right panel with gray level 140, and a single central column of gray level 127. The thresholds for the operators were chosen so that the Figure of Merit is maximized at the lowest noise level. This is more realistic because in real life we rarely have control over the degradation of the picture that we are processing. The test image used for the Kitchen and Rosenfeld Measure was a "rings" image. This image consisted of concentric rings with alternate pixel values of 115 and 140. The image was generated as a 512 X 512 image and then reduced to 128 X 128 pixels by replacing 4 X 4 blocks with the average pixel value of the block. This test image provides edges at all possible orientations. Discussion The results of the tests provides a quantitative measurement of the capabilities of various operators to produce well-formed edges. Our tests show the difference in Annual Report 50 August 1, 1982 - July 31, 1983

performance between the operators with and those without edge direction information can be quite distinct for all noise levels. Pratt's Figure of Merit does not always give sufficient information about the resulting edge pictures, especially when the edges are broken. While the Kitchen-Rosenfeld Measure supplements this by measuring the continuation and thinness of the resulting edges, other problems can arise. When more edge points than ideal edge points were detected, Pratt's Figure of Merit can be viewed as the average of the weighted deviation values of the actual edge points. Since false edge points closer to the ideal edge have higher weights than those farther away, eliminating those false edge points with higher weights can result in a decrease of Pratt's Figure of Merit. This is especially significant when the false edge points are not evenly distributed across the image, such as in the form of artifact segments. We have used two thresholds for the strength value in our algorithm: the contour start threshold in the search mode and the edge point threshold in the trace mode. The contour start threshold that is used to determine if a contour should be started should be fairly high to assure that a true edge segment is being traced and to avoid generating artifacts. Using a much lower edge point threshold in contour tracing is consistent with our philosophy that the edge direction is primarily responsible for tracing edge segments. Besides the different ways for selecting the threshold for strength values, there are other thresholds in our algorithm that can affect the output. These are the minimum contour length threshold and the continuity threshold. Since the connectivity analysis used in contour tracing is a local operation, it is sensitive to noise and artifacts can be generated. The minimum contour length value can be used to reject isolated points and short contours that frequently are generated by noise. In most of our tests, we have used 18 for the minimum length threshold. When applying the edge detectors to typical real world pictures, this threshold can vary from 8 to 18. The continuity threshold can be adjusted to control the angle that an edge segment can turn. Depending on the input picture, the various thresholds can, be adjusted accordingly to minimize unwanted background noise and to produce well-formed edges. Wre now plan to use this edge detection algorithm in our work in shape analysis (and shape change analysis) with applications to object recognition and parts occlusion. 3.3.2. Dynamic Scene Analysis Professor E. Delp, Professor R. Jain Several aspects of dynamic scene analysis are under investigation. In the first work described below the estimation of motion parameters of moving objects in temporal sequences of images is examined. Motion in two dimensions coupled with zooming of the camera are considered. The second aspect described is the concept of optical flow and is built upon previous work by Professor.Jain. As Professor Jain joined our staff during the project, only those aspects being funded by AFOSR are reported here. Annual Report 51 August 1, 1982 - July 31, 1983

3.3.2.1. Motion Parameter Estimation Professor E. Delp Problem Description and Research Objective Estimating the motion parameters of moving objects in temporal sequences of images is an important problem in time-varying imagery. Applications include object tracking in parts handling and robot guidance. Because of its computational simplicity, the method of linear least squares is attractive for the case of twodimensional motion with scale change i.e. rigid objects moving in a plane parallel to the image plane plus zooming. We have studied various algorithms for motion parameter estimation and have implemented one of them in real-time. Results The method of linear least squares has been applied to the problem of estimating motion parameters for the case of two-dimensional motion plus scale change. The object(s) to be tracked may translate and rotate in a plane parallel to the image plane and translate along an axis perpendicular to the image plane (scale d2 change or zooming). We have shown that two other motion detectors, the -t2 dt operator of Marr and Ullman, and difference pictures, are mathematically similar to spatial-gradient detectors with respect to the information they furnish regarding the local velocity field. The least squares method of estimating the four motion parameters proceeds in an identical fashion regardless of the specific motion detector used. We furthermore have shown that the scale change parameter may be decoupled from the other three parameters. The scale change parameter may be rapidly'estimated independently of the rotation and translation parameters by integrating the motion detector output around a closed path (e.g. the target object's boundary). In the case of the difference picture motion detector, this may be approximated by merely summing the areas of the difference regions. Having estimated the scale change parameter in this way, the other three parameters are then estimated by a three-dimensional linear least squares projection. Thus the four dimensional linear least squares problem may be decomposed into the one dimensional problem of estimating the scale change and the three dimensional problem of finding the parameters of translation and rotation in the plane. This result has important implications regarding the speed and accuracy of the calculations. We have implemented a difference picture based motion parameter estimation algorithm in realtime on our DeAnza IP6400 and have been able to track an object as it moves in a scene. We are in the process of extending this work to include the use of a new detection-theoretic based edge detector for dynamic scenes to increase the accuracy of the edge locations found by the edge detector. Annual Report 52 August 1, 1982 - July 31, 1983

3.3.2.2. Motion Estimation by Optical Flow Professor R. Jain We are studying feasibility of estimating 3-D motion parameters of objects and camera using methods based on optical flow, but without computing optical flow. We are convinced that there is motion information in optical flow. It appears, however, that the computation of optical flow is a difficult problem. Some algorithms have been proposed for computation of the optical flow using the relationship between the temporal and spatial derivative of intensity values. These methods work well with synthetic scenes; the optical flow for real scenes is not of good quality. Considering the fact that recovery of information from optical flow may require Herculean computational efforts, Jain started exploring the feasibility of recovery based on the characteristics of optical flow but without computing them. Some early results by Jain, and Jerian and Jain have shown feasibility of such a recovery in constrained cases. Application of their work to real scenes requires robust techniques for feature detection, and integration of feature detection with the optimization process used in the recovery. We are investigating integration of feature extraction and recovery processes for real scenes. Status of the Research Effort The support of this effort under AFOSR has begun only shortly before the end of the annual reporting period. The primary effort to date has been the setting of directions for the next year's work. Our efforts will be directed to the recovery of information without computation of the optical flow. Jerian and Jain have done some experiments in this direction. During next year, we will be studying feasibility of 3-D motion parameter estimation in real scenes using optimization approaches. 3.3.3. Surface Reconstruction Two techniques for the recovery of three dimensional information about an object from multiple images from a single camera are under investigation. The first employs multiple images under different lighting conditions. The corresponding differences in shading can be used to determine shape. The second approach utilizes a laser-shutter-camera system in which essentially different views are obtained from different openings of a shutter array. Annual Report 53 August 1, 1982 - July 31, 1983

3.3.3.1. Photometric Stereo Professor R. Jain The Problem and Research Objectives Many industrial applications require 3-dimensional information about the surface of an object. This information may be required for inspection of the surface or for the recognition of an object based on it's structure. Different approaches have been proposed for the recovery of 3-D information using one or more images of a scene. Stereo, using two cameras has faced a very difficult problem of establishing correspondence. Range-based methods require integration of range data obtained using a laser with intensity data. Methods using structured light are good in binary vision. We believe that the photometric stereo offers certain advantages in industrial environment, that make it more attractive as compared to other methods. Approach and Status of Research Objective Photometric stereo exploits the theory of shape from shading. Using more than two images of a surface, obtained using a fixed camera but a different position of light source for each image, the shape of the surface can be obtained using a look-up table. WVe implemented the photometric stereo algorithm of Coleman and Jain in our laboratory. We have a setup to change position of the light source to obtain desired images for the computation. Currently, we are trying to improve the performance of the Coleman and Jain algorithm by using better interpolation techniques to obtain the structure of the surface. Our efforts in this area are directed towards development of a powerful photometric stereo method that will allow recovery of the structure of arbitrary surfaces using only local computation. Our emphasis on local computation stems from our desire to implement such algorithms using SIMD architecture for real time performance. 3.3.3.2. Laser Shutter Camera Professor G. Frieder Goal of the Project The goal of the project is to find in real time the spatial constraints of a large number of points on a surface. By real time we mean "within the expectation of a typical user," which in our case translates to some small number of seconds. By large number we mean no less than 10,000, and the currently developed system assures 16K (K=1024) points. The experimental setup consists of a laser-shutter system which projects 16K light points simultaneously on the surface. A digitizing camera records the image of these light points and a set of programs then computers the three-dimensional coorAnnual Report 54 August 1, 1982 - July 31, 1983

dinates of these points. The Development Procedure The experimental setup is currently developed in an Air Force laboratory (The Avionics Laboratory, WPAFB) under separate contract. The mathematics developed is now well understood (see original proposal) and the programs are being developed. Summary of Preliminary Results We found that using the methodology we can compute the surface points, and we developed the programs to do it. We found that the quantization error is very high and intend to continue to study it. We found that the self calibration procedures that were originally proposed do not work in practice due to the instability of the system of equations that define calibration. We found that a least-square method can be used to define position in space, and we are now using it for calibration. We have to attack the question of the dependence of the accuracy of measurement as a function of camera resolution. We also have to introduce noise to the phantom programs and to deal with faculty data. These two subjects will be addressed during the upcoming year. 3.3.4. Determining Distinguishing Features of an Object for Visual Recognition Professor T. N. Mudge, Professor R. A. Volz Problem and Objectives Part of our effort in the area of image processing has been directed toward developing an automated vision module for real time robotics applications. An important problem in automated visual recognition is the recognition of objects whose boundaries can not be completely determined. Fairly robust algorithms have been developed which can recognize an object if its boundary is unbroken [1], however, only specialized approaches have worked well when the boundary is fragmented. Boundary fragmentation generally occurs either because the object is partially hidden or because the lighting is poor. While it is possible to employ custom lighting to improve the recognition process or to employ custom machinery to separate and otherwise prearrange the objects so that the complete boundary is found, a more flexible approach is to employ a vision system which can recognize objects by their partial boundaries. Such a vision system can be reprogrammed for new objects that might appear on the assembly line, but systems utilizing custom lighting and or custom machinery are less flexible and must often be redesigned to handle a new object. The developed algorithm recognizes objects from partial boundaries. It accomplishes this feat by determining the distinguishing boundary features of one object with respect to other objects that might be present in the scene and then using these Annual Report 55 August 1, 1982 - July 31, 1983

"salient" features to determine the orientation and location of the object. Approach The scene in which the objects appear is called the application scene. In order to reduce the amount of information needed to recognize industrial objects, only the edges of objects in the application scene are considered. Edge points and their angles of slope extracted from the scene [2],[3] are thinned [4] so that only the strongest edge points which maintain boundary continuity remain. The strategy used for object recognition is weighted template matching of boundaries. The boundary of a object is obtained during a training phase or from a database representation [see sec.3.5.2] and employed as a template to locate the object in the application scene. Template matching can be treated digitally by partitioning the application scene into a two dimensional array of cells and associating with each cell an accumulator whose purpose is to record template matches. The two dimensional array of accumulators is assumed to be initially zero. A template point is overlayed on a edge point of the image (See Figure 3.3.4.1). If the template point matches the edge point, the accumulator array at the location of the template center is incremented. After all the template points have been matched to the edge points, the location in the accumulator with the highest accumulation is taken to be the center of the object. This procedure is similar to the Generalized Hough [5] transformation. The decision as to whether the template point matches the edge point or not depends on the restrictions placed on the match. In normal template matching there are no restrictions. The template point is assumed to always matched the edge point it overlaps. By not restricting the matching, many unnecessary matches are recorded in the accumulator array making it difficult to determined the correct location of the part.''" J~ I:,.- n i / C \;./ ra ^ 17 Figure 3.3.4.1 Normal template matching Annual Report 56 August 1, 1982 - July 31, 1983

The approach taken here is to match the template and edge point only if a subtemplate centered at the template point matches a section of the edge image centered at the edge point. (See Figure 3.3.4.2.) Matching subtemplates is a form of local template matching. This process decreases the probability of false matches since it relies on a neighborhood of points around the template point matching a neighborhood of points around the edge image point, an important constraint for hidden objects where boundary edges tend to consist of a concatenation of fragments from different boundaries. Another difficulty with normal template matching is that the template must be matched at all possible orientations. With subtemplate matching, the subtemplates can be matched in rotationally invariant space completely avoiding the computations needed for rotating. The angle at which the subtemplate matches the edge section is recorded in the accumulator along with the strength of the match. The orientation of the object is taken as the average of the angles stored at the determined location of the object's center (i.e. an intrinsic coordinate system is used). In order to better locate the desired object the subtemplates are weighted [6]. An optimization algorithm computes the weight of subtemplate based on the dissimilarity of the subtemplate to sections of the boundary of the other objects in the database. Those subtemplates of the boundary which are dissimilar to other sections of other boundaries are weighted more heavily. A group of heavily weighted subtemplates makes a larger contribution to the accumulator array and therefore plays a more significant role in determining the potential location of the object when the boundary is fragmented. Weighting the subtemplates can also be viewed as a method of decorrelating the complete template of the object with the boundaries of other objects. Since more weight is given to those subtemplates which fail to match sections of the boundaries of other objects, the matching response of a template composed of the weighted subtemplate will respond poorly to the boundaries of other objects. While it is still possible to give a false result, the techniques mentioned above reduce the uncertainty associated with locating an object significantly. J J 5f f.1j Figure 3.3.4.2 Subtemplate matching Annual Report 57 August 1', 1982 - July 31, 1983

Results to Date Figure 3.3.4.3 shows the results of applying this algorithm to a scene in which objects are overlapping. Parts are found without the need of rotating a template since the subtemplate matches are matched in a rotationally invariant space. A considerable amount of computation is saved by this approach. Also by searching for distinguishing features one can locate the object more quickly if a sufficient amount of the features are visible. The code is written is the language "C" and runs on the VAX 780. The average time to recognize an object is 45 CPU seconds. However, no effort has been made as yet to optimize the code. / /.. —-,-_ J 1\I t: ( r. ~.-'l.i r\ - ////f~~~~~~~~~~,.,'-'., Annual Report 58 August 1, 1982 - July 31, 1983 A.nnual eport 58 August 1, 1982>- July' 1, 83

Future Activities The new algorithm is suitable for parallel processing since the task of template matching can be broken into separate subtasks of subtemplate matching. Each processor could match a subtemplate and all matching can be attempted in parallel with the accumulator as common memory. With several fast processors running in parallel and a restructuring of the code real time operation is expected to be achieved. To test this hypothesis the algorithm will be reprogrammed in the ADA language and incorporated into the database driven machine cell run by the iAPX432 multiprocessor, as an alternate vision system to the present vision module. (The present module based on a geometric database is discussed elsewhere in this document.) Finally, this algorithm can be extended to three dimensions. Using the same method as the two dimensional case one can determined the surface features of objects which most distinguish them, and use these distinguishing features to search through a depth map of an image scene in order to find the desired object. Preliminary work will be begun on this approach during the coming year. References [1] Gleason, G.J., "Vision Module Development," Ninth Report, NSF Grants APR75-139074 and DAR78-27128, SRI Projects 4391 and 8487, Standford Research Institute, Menlo Park, CA. August 1979, pp 9-16. [2] Frei and Chen, "Fast Boundary Detection, A Generalization and a New Algorithm", IEEE Trans of Computers, Vol. C-26, No 10, Oct. 1977. [3] Delp, E.J. and H. Chu, "Edge Detection Using Contour Tracing", Submitted to IEEE Systems, Man and Cybernetics. [4] Stefanelli and Rosenfeld, Journ. of ACM, Vol. 18, No.2, April 1971, pp 255-264. In particular, examine Appendix A. [5] Turney, J.L., T.N. Mudge, and R.A. Volz, "Experiments in Occluded Parts Recognition Using the Generalized Hough Transform," Proceedings of the Conference on Artificial Intelligence, Oakland University, Rochester, MI, April 1983. [6] Mudge, T.N., J.L. Turney, and R.A. Volz, "Experiments in Occluded Parts Recognition," Proceedings of the Society of Photo-optical Instrumentation Engineers Cambridge Symposium on Optical and Electro-optical Engineering, Submitted to IEEE Pattern Analysis and Machine Recognition. Annual Report 59 August 1, 1982 - July 31, 1983

3.3.5. Application of Optical Processing to Robotic Vision and Intelligence Professor E.N. Leith Objectives To use optical processing techniques to help reduce some of the computational overhead required to perform the vision tasks was proposed. There are several potentially fruitful ways to apply optical processing to the robotic vision and intelligence problem: (1) the use of incoherent light for the optical processing (2) the use of hybrid optical-digital processors (3) the use of more sophisticated recognition and classification algorithms than the matched filter. To meet these objectives, the following program was proposed: (1) to apply the previous results of optical processing with incoherent light to the problem of robotic vision and intelligence. (2) to develop architectures for the combined use of optical and digital processing in robotic systems (3) to develop for robotics systems complex spatial filtering techniques that are more general than the conventional matched filtering methods, and that can overcome the basic limitations of the matched filter. Status of the research effort This year the emphasis was on items 1 and 2 of the proposed program. The greatest effort and the most significant results are on item 2, the development of architectures for combined optical and digital processing. The ideas described here are two-fold; to match the imaging system to the object distribution in an optimum way, and to do some preprocessing on an image while forming it, thereby reducing the processing to be done digitally. One method of obtaining information about an object surface is to project fringes on it. Commonly, one obtains information about the three-dimensional structure of the surface. The information may pertain to the micro-3D, which is surface roughness, or the macro-3D which is the surface contour. For example, Lippincott and Stark [1] have recently described an optical-digital method for detection of dents and scratches on metal surfaces. They project a grid pattern on the surface, which is then read off by a TV system and stored in a digital computer, which calculates the surface contour. The initial concern has been with the generation, projection, manipulation, and detection of fringes. In particular, the concern is with fringes of high quality, high contrast, and low noise. For high quality fringes, it is best to form fringes in light that is somewhat incoherent, or at least of considerably reduced coherence. An interferometer formed from diffraction gratings has been found to bl)e an excellent way to produce fringes. Such an interferometer is easy to align, forms non localized fringes in light, monochromatic or polychromatic, from and extended source. such an interferometer is Annual Report 60 August 1, 1982 - July 31, 1983

do ~ dl Figure 3.3.5.1 Interferometer formed from diffraction gratings shown in Figure 3.3.5.1. A first grating G1, receives a beam of light, diffracting it into 2 orders. Figure 3.3.5.1 shows these to be the +1 and -1 orders, but other possibilities exist, such as the +1 and 0 orders. A second grating, G2, brings these beams back together. The grating interferometer has been analyzed elsewhere (2). An interesting and useful way of interpreting the fringe formation process is to like it to an imaging process, much as a lens forms an image. Here the second grating is considered as imaging the first grating. The condition for fringe formation can be written in the form 1 1 1 d0 d, F, where Fg is the focal length of the second grating and is given by qF - fl/f21 -m Where f, and f2 are, respectively, the spatial frequencies of the first and second gratings, n is the order used for the upper beam in diffracting from G1, ri' is the same, but for the lower beam, and m and mi are the corresponding quantities for grating G6. In summary, the grating imaging method allows for the placement of numerous. high contrast, low noise fringes on an object surface, in a very convenient way. The fringes can be highly localized or completely non-localized. The fringe depth and spacing can easily be controlled. In addition, other kinds of fringes, such as circular or elliptical, can be formed. The focal length varies with grating separation and also with the spatial frequency f, of the grant being imaged, so it is indeed a rather special kind of imaging process. Further, the image is not formed in a geometrical sense, where all rays from an object point are brought together again at the image, indeed, only rays produced by one element of the source are recombined; sets of rays emanating from the same object point, but emanating from different elements of the source are in general not recombined at all. Annual Report 61 August 1, 1982 - July 31, 1983

Imaging processes can be achromatized, and such is the case here. For fringes to occur in broad spectrum illumination, we require the fringes to be X-independent. Analysis shows the fringe spacing is already X-independent which is not the usual case for interferometers. For white light fringes, the fringes must be in registry for all wave lengths. Analysis shows that this can readily be done. As an imaging device, the grating has a number of significant characteristics relative to a lens. First, the phases of the Fourier components are in general altered, so that for a multiple-Fourier-component object, the image does not resemble the object. Second, different Fourier components are imaged to different planes. For most object distributions, these effects are disastrous. For some object distributions, all of the periodic type, these characteristics may not matter. For example, to image a simple, sinusoidal fringe pattern, the grating is quite satisfactory, and is indeed far better than a lens. This imaging process can be described in part by the consideration that the imaging process is narrow-band with the MTF consisting of a few discrete lines, or 6 functions. Thus, the grating system MTF is a well matched spectrum of periodic objects, whereas the lens MTF is highly mismatched. Also, the grating imaging process is space invariant, that is rays from one part of the object undergo exactly the alteration as rays from any other part of the object. This effect sharply distinguishes the grating from a lens, and leads to some interesting conclusions. First, the off-axis Seidel aberrations of a lens, such as soma, astigmatism, and distortion, which are tied to the space-variant characteristic of a lens, could in some circumstances be inherently absent from the grating imaging process. Second, one ought to be able to realize extremely low F-number values for an imaging grating, since the grating can be arbitrarily large compared to the focal length, and the larger aperture should not increase either the required tolerances or the aberrations. Hence, it seems clear that if the object is periodic, such as a sinusoidal distribution, a grating is generally superior to a lens. Experiments confirm this conclusion. The fringes are to imaged onto a three-dimensional object arising in such applications as metrology and robotic vision. Suppose the number of fringes to be large, say several thousand. The fringes are to be high in contrast and as noise-free as possible. Of the many ways to accomplish this, two are considered for comparison. In each case grating G1, is to be imaged onto the object. Let the aperture of G1, is to be imaged onto the object. Let the aperture of G1 be L and the spatial frequency be fA. For simplicity, suppose the grating to be sinusoidal, i.e. rulings of the form + cos27rfix. Consider first a magnification of unity, then consider fringe enlargement. Figure 3.3.5.2 shows the two configurations, (a) with a lens, and (b), with a second grating G2 in the place of the lens. For perfectly coherent illumination, the fringe will in each case have perfect contrast provided the aperture is sufficiently great to collect both the +1 and -1 orders, and the fringe depth will be considerable i.e. the fringes will not be localized, but will form wherever the beams overlap. It is desirable to magnify the fringes while retaining at the image all of the fringes of G1. Therefore, the beam must enlarge in proportion to the fringe spacing. The grating G2 does not do this; instead, we must form the fringes with diverging rather than collimated beams, in such a way that the ratio of beam width, at the output plane to those at G1 is just the fringe magnification on Annual Report 62 August 1, 1982 - July 31, 1983

( ^^'(a) Figure 3.3.5.2 Two configurations, (a) with a lens, and (b) with a second grating G, in the place of the lens. Figure 3.3.5.3 Required beam magnification IM. As shown in Figure 3.3.5.3 the required beam magnification occurs when G1 is illuminated with a converging beam with center of curvature at G.). Under this condition, the number of fringes is preserved. Annual Report 63 August 1, 1982 - July 31, 1983

Suppose the beam diverges more, so that the beam magnification is greater than the fringe magnification. Will there be more fringes than exist at G1? Since fringes form wherever the beams overlap, there must indeed be more. From the imaging viewpoint, this seems enigmatic, since we seem to have created some additional fringes beyond those supplied by the object. To make the beam diverge more, the focal point is brought back to a position between G, and G2. The beam is then somewhat expanded when it intercepts Gn. A rather straight-forward geometrical analysis shows that the number of fringes at the output is just the number of rulings on G1 plus the number of rulings intercepted by each beam at G2. Thus, the total number of fringes at the output is just the number each beam intercepts along its travels, and thus have a conservation of fringes. The grating imaging process has aberrations, the analysis of which are rather involved. However, some interesting observations can be made for unity magnification, (e.g. for d, = do and f2 = 2f1), the process is aberration -free. Aberrations arise when we depart from this symmetrical situation. The aberrations are manifested as a loss of fringe contrast under broad source illumination. The aberrations are space invariant in that the loss of contrast is the same over the entire field, and the fringe spacing remain uniform over the field. On another task, the basic concept is to use a matched spatial filter for recognition of an object, its position, and orientation. The spatial matched filter method works extremely well, but its implementation is fairly expensive because of the need for an incoherent to coherent transducer. Such a device, which could be formed from a liquid crystal, can convert an image distribution formed with incoherent light into a like image distribution with coherent light. It is desirable to find a way to carry out the matches filter synthesis without the need for coherent light. We have devised a method for doing this which appears to be promising. This method, (developed on a different project) works with monochromatic spatially incoherent light, yet operates much as if the light were coherent. For example, the optical system is linear in amplitude, or field, rather than intensity, as would be the case if the illumination were incoherent. The phase is totally preserved, so that information about the depth of the object is preserved. In short, the system has all the attributes of a coherent system, although the illumination is actually incoherent. This situation seems contradictory. One problem with this method is that, like other coherent systems, it preserves the surface roughness pattern of the object. This is a quantity that varies from one object sample to another, and a spatial matched filter for one object could be used only for that same object, and would be totally useless against a different object that is to all appearances exactly the same. To avoid this problem, the object should be imaged through a TV system. The TV system would receive polychromatic, spatially incoherent light from the object, and convert it into an image formed with highly monochromatic spatially incoherent light. The monochromaticity requirement is generally not extreme, so could possibly be met with a conventional CRT with perhaps a filter place over it. Alternatively, the use of a laser TV system should be explored. The TV system, because of its use of white light from the object, will completely eliminate the problem of the surface roughness function that prevents correlation from one object specimen to another. Annual Report 64 August 1, 1982 - July 31, 1983

Another problem is that the system, as currently conceived, works with images that have only two dimensions, i.e. depth and one lateral dimension. The extension to three dimensions is a goal for the coming year. Reference [1] Lippincott, H.W. and H. Stark, "Optical-digital Detection of Dents and Scratches in Specular Metal Surfaces," Appl. Opt. 21, p. 2875 (1982). Potentially patenable items (1) The grating imaging system with arbitrary magnification. (2) The incoherent matched filter method in combination with a polychromatic to monochromatic transducer. 3.3.6. Special Processors for Vision Professor T.N. Mudge The Problem and Objectives Image processing by computers has made considerable advances in making available algorithms that enhance and understand images of industrial parts. However, the application of these algorithms in factory environments has been limited mainly because of the large amount of processing time required making ordinary general purpose computers impractical to use. This is due to the massive amount of data needed to represent the image. Typical real-time image processing would require about 8 million bits of information updated every 30th of a second [1]. Hence, it is essential to use special purpose computers that are capable of handling such large data sizes at high speeds. VLSI technology has continued the decline in computer hardware costs and made it feasible to build multiprocessor systems at reasonable costs that are capable of performing image processing applications at high speeds. Parallel computer architectures for image processing can be classified into four major categories: Single Instruction stream Multiple Data stream (SIMD), Multiple Instruction stream Multiple Data stream (MIMD), Pipelined processors and Special Function Units. In real life application, it is important to characterize the set of algorithms used to find the most suitable architectures(s) to process these algorithms. This is necessary in order to improve the efficiency and utilization of the computer system used. For example, SIMD architectures are more suitable for low level image enhancing where identical operations are performed on a large number of pixels. MIMD architectures, on the other hand, are more suitable for high level image analysis where more complex computations are involved. The process of choosing an optimal architecture to best suit a class of algorithms is generally an involved process. Many factors should be taken into consideration [2,3]. The type of problems considered in this study involve the investigation of the effect of the algorithm characteristics, data characteristics and the processor design on the performance of the image processing system and how Annual Report 65 August 1, 1982 - July 31, 1983

that performance can be improved. Status of Research Effort Image processing algorithms, generally, fall into two major classes: feature independent algorithms and feature dependent algorithms. Feature independent algorithms are characterized by a fixed set of operations applied to all pixels of the image. Feature dependent algorithms, on the other hand, are characterized by unequal amounts of processing per pixel of the image. This might arise when a pixel is part of a feature of interest and because of that requires a separate treatment. A simple example of a feature dependent algorithm is contour tracing; only edge pixels are involved in the algorithm. Pixels that are part of a feature of interest are defined as pixels of interest. A natural architecture for many of image processing algorithms is a multiprocessor system with equal size subimages assigned to separate processors. Such processors may be classified as Multiple Subimage Processors (NISP's). A block diagram of an MSP is shown in Figure 3.3.6.1. While MSP's are quite efficient for feature independent algorithms, this not the case for feature dependent algorithms. If the image is divided among the processing elements of the MSP into subimages of equal size, some processing elements receive less number of pixels of interest than other processing elements. This uneven distribution of work will result in some processing elements being idle during part of the algorithm. Consequently, the performance of the system, measured by its efficiency, decreases. This argument is verified by assuming a Binomial model for the probability distribution of pixels of interest in an binary edge image. The model is used to quantify the efficiency of the MSP system. The efficiency is shown to drop considerably as the number of processing elements increases [4]. In order to improve the efficiency, the image should be redistributed among the processing elements into subimages of equal interest. i.e., into subimages of equal number of pixels of interest. The redistribution of the image on equal interest requires the the distribution of pixels of interest over the image be known. PE1 PE2 PE... PE I C N1 (Interconnect ion Ne twork) Figure 3.3.6.1 Generic MSP Annual Report 66 August 1, 1982 - July 31, 1983

This is not always possible, and even if it is, the redistribution of the image on equal interest may involve more computation than that lost through having some processing elements idle during part of the algorithm A case study is being performed on a program for the recognition of occluded industrial parts [5]. The objective of the study is to investigate possible multiprocessor implementations of the program and select the most suitable implementation. The study will aid in pointing out algorithm and data characteristics that affect the image processing system performance. Plans are being made to implement portions of the algorithm on an Intel iAPX 432. Future Work Near future work includes: (1) Further investigation of other algorithm characteristics and image data models and how they affect the performance of the image processing system; and (2) Investigation of performance improvement techniques such as image redistribution on an equal interest basis. References [1] Reinhold, A.G. and G.J. Vanderbrug, "The Autovision System," Robotics Age, Fall, 1983, pp 22-28. [2] Delp, E.J., T.N. Mudge, L. Siegel and H. Siegel, "Parallel Processing for Computer Vision," Proceedings of the Society of Photo-optical Instrumentation Engineers Technical Symposium East, Volume 336 (Robot Vision), May 1982, pp 161-167. [3] Mudge, T.N. and E.J. Delp, "Special Purpose Architectures for Computer Vision," Proceedings of the 15th Hawaii International Conference on System Science, January 1982, pp 378-387. [4] Mudge, T.N. and T.S. Abdel-Rahman, "Efficiency of Feature Dependent Algorithms for the Parallel Processing of Image," Proc. ICPP, Balliare, Mlichigan, August 25-28, 1983. [5] Mudge, T.N. and T.S. Abdel-Rahman, "Case Study of a Program for the Recognition of Occluded Parts," Proc. CAPAIDM, October 1983. 3.4. Architecture of Robot-Based Manufacturing Cells Professor R.A. Volz, Professor T.N. Mudge The Problem and Needs The robots of today are computationally relatively simple devices. Their servo control algorithms are unsophisticated, the level of sensor integration is relatively low, and their on line interaction with management and engineering databases is minimal. This situation is changing rapidly. Vision, force and tactile sensors are being developed and incorporated into robot systems, more precise control schemes are under development and the interaction of robot systems with computer aided design Annual Report 67 August 1, 1982 - July 31, 1983

and other computer aided engineering databases offers the potential of placing considerable intelligence in future robot systems. With these developments, however, comes greatly increased demands for computational capability and greatly increased complexity of both the hardware and software systems required. Future systems will certainly use multi-processing, with a number of the processors being special purposes devices designed to achieve needed processing speed for computationally intensive subtasks, and the software necessary to operate these systems will be very large and complex in comparison to today's systems. Therein lies a major problem for the future intelligent robot based manufacturing cells, managing the hardware/software complexity. The problem and needs are depicted in Figure 3.4.1. The top part of the figure identifies three major issues contributing to the problem, and the bottom, a requisite to resolving the problem. In the process of achieving the necessary unified system, several specific goals must be achieved: * adequate computation capacity * reliability * maintainability * transportability * extensibility * hardware/software transparency The desirability of the first four of these is clear. The extensibility and hardware/software transparency are important so that the system may adapt to new capabilities as they arise and so that special purpose hardware to replace slower software may be readily incorporated. ROBOT-BASED MANUFACTURING CELLS MULTIPLE REAL-TIME TASKS COMPLEX SOFTWARE SYSTEMS EVOLVING REQUIREMENTS MULTIPLE SPECIAL PURPOSE PROCESSORS INTEGRATION AND UNIFIED MANAGEMENT OF SPECIAL PURPOSE HARDWARE AND EVOLVING COMPLEX SOFTWARE Figure 3.4.1 Annual Report 68 August 1, 1982 - July 31, 1983

Approach The key to solving the major problem identified above is the development of a technique for dealing with all of the complexities involved in a large system in a unified manner that supports encapsulation of the individual subsystems involved and effective communication between them. The central idea to the approach being taken is the use of object based systems and object level design at both the hardware and software level. Concept Object-based computer architectures are a synthesis of two parallel developments in the fields of language and operating systems research. While language researchers were studying the problem of program decomposition, their counterparts in operating systems research were studying problems associated with data integrity and security. A consensus of opinion from language research directed at program decomposition emerged in favor of information hiding (also referred to as data encapsulation or package-based decomposition) as the major criterion for the modular decomposition of computer programs [1]. This methodology employs the concept of a type manager to manage and effectively hide the implementation of abstract data types from the other modules in the system [2], [3]. Meanwhile, in operating systems research, a consensus emerged that favored the concept of protection domains as a solution to the data integrity and security problem. This concept is analogous to the package-based decomposition model [3]. More information on object-based systems and programs may be found in [4]. A number of advantages follow from the use of object-based programming and object-based systems: * data/program integrity * "clean" modularization of both hardware and software * unified conceptual view of whole system. Data and program integrity are achieved because the hardware capability addressing mechanisms make it physically impossible for a program module to accidentally execute data or code in another module. Similarly, it is impossible for a module to access data to which it has not been explicitly been given access. These features, in turn, help improve the reliability of the system. Objects and their associated functions and procedures form natural boundaries along which to subdivide systems. This natural subdivision often occurs in a hierarchical fashion. Unified views of the entire system in varying levels of detail may be obtained by viewing only the specifications of the appropriate higher levels of the hierarchy. This clean top down view of the system will aid in its understandability, and correspondingly in its maintainability. Experimental Systemn The concepts described above are being tested on an experimental system which includes both object-based hardware and object-based software. The system is an Intel iAPX 432 microprocessor system which is programmed using Ada. The iAPX 432 system supports multiple main processors, considerable memory and attached special purpose processors. Further, it has high level message passing mechanisms for handling communication both among processes executing on the main processors and Annual Report 69 August 1, 1982 - July 31, 1983

between processes on the main processors and the attached processors. The specific system available can have up to four general data processors, 1.5 megabytes of memory and three interfaces to attached processors. Figure 3.4.2 shows a block diagram of the experimental system. It includes an interface to an ASEA RB 6 robot, an interface to a GE TN2500 TV camera and an attached preprocessor for the visual data. Relation to other parts of the project Since the problem being addressed concerns large complex robot systems several other subprojects are being strongly coupled to the work. Two aspects of machine vision (see secs. 3.3.1 and 3.3.4) and the automatic determination of gripping positions for objects (see sec. 3.5.1) are being integrated into the system. Another major reason for including this work in the experimental system is that it will demonstrate the feasibility of a very important idea, that the robot cell can perform a set of operations on any of a group (in the sense of group technology) of inputs without reprogramming. The combination of the vision system, the off line training of the system and the automatic determination of gripping positions of objects makes it possible to write a robot program which performs a certain operation, say sorting or machine loading, without any explicit geometric information about the objects to be manipulated appearing in the program. For a given set of parts, or stable positions of parts, which might be encountered the vision system obtains its decision information from the database and combines this with calculations on the image from the TV camera to determine the identity and location of an object position of the object relative to its CDP GDP MEMORY IP IP IP Series HIT VAX 8o/30Development 11/780 Development with Systems li..' o 8087 86/330 SYSTEM - h.d coFigure 3.4.2 Annual Report 70 August 1, 1982- Juloppy disk1, 1983 hardisk 4x256x258 534 disk FRAME (88/45) GRABBER ---- VAX 11/790 ASEA TN 2500 TV monitor Figure 3.4.2 Annual Report 70 August 1, 1982 - July 31, 1983

coordinate system. With the identity information, the program then extracts from the database the gripping position of the object relative to its coordinate system. Combining this with the position information from the vision system, the program knows where to go to pick up the object. If an entirely new set of objects is designed for which the same operation is required, the information is simply placed in the CAD database at design time, and the robot cell program told the identity (names) of the new objects, whereupon it is ready to go. No reprogramming or manual training of either the vision system or the robot is ever necessary. Status of the Research Effort Much of the effort during the first year was spend in developing the experimental facilities. In the process, some preliminary results have been obtained on the use of object systems. Briefly, the following has been accomplished: * install two operational versions of the iAPX 432 system. * implement communications protocol for ASEA robot and coordinate conversions on attached processor * build frame grabber for GE TN2500 camera * implement attached preprocessor to perform thresholding and run length encoding for raw vision data * implement binary vision system in Ada on the iAPX 432 The installation of the iAPX 432 system has not been as straightforward as one might expect. Throughout, advanced, unreleased versions of the software have been in use to obtain features not available in the released versions, and the attached processor work exercised hardware features previously untested. Several errors, both hardware and software were discovered, reported to Intel which corrected them, and eliminated,by field updates. In June, 1983 revision 3 of the 432 hardware and version 2.0 of the Ada compiler were installed. The hardware upgrade is supposed to provide approximately a speed improvement of 2.5. Tests to verify this will be performed during the coming year. The new version of the compiler added important features of Ada which had been kludged in the early version, the most important being floating point numbers and tasking. The work with Ada on experimental system being built has led to some preliminary opinions about the use of Ada for robot and sensor system programming. From the view points of managing complex software, providing an application specific programming environment to the user, and achieving language standardization, Ada provides a number of advantages. These include: * "system" packages can be provided to the user which create new robot and sensor specific data types and give the feeling of programming in a language tailored to the robot system. * The use of data abstraction and operator overloading to create well modularized application specific code helps usability, readabilty and maintainability. * The strong type checking significantly aids debugging. * The separate compilation features in conjunction with the other features cited above aids flexibility and helps portability. Annual Report 71 August 1, 1982 - July 31, 1983

* The expressive power of the language is excellent. These advantages are not surprising. They are exactly what computer scientists have been predicting for several years. Having these capabilities widely available in a standardized language, however, is very significant. Indeed, it is this expected standardization of Ada that can greatly aid in standardizing application specific "languages" and giving them portability. The portability can be inherited, to a large measure, from Ada. Further discussion of both advantages and disadvantages of Ada may be found in [5]. Expected Future Accomplishments Work over the next year should accomplish the following: * The link of the system to the CAD database for off line training of the vision system and automatic determination of gripping positions should become operational. * Preliminary work on performance measurement in the system should be available. * Further studies on the effectiveness of parallelism for advanced vision algorithms and hardware/software transparency should in progress. The availability of an operational system with the use of CAD as described above will demonstrate the feasibility of an important mode of operation for future robot systems. Also, it will form the basis for expanded work in robot languages. Consideration will be given to including additional sensors in the system, and mechanisms for handling exceptional conditions will be investigated. One of the subprojects discussed in section 3.3 deals with new techniques for visual recognition by template matching and the use of these techniques for recognizing. occluded parts. It has recently been discovered that these techniques are amenable to a decomposition into parallel tasks. The parallel structure of the iAPX 432 system will be exploited for this purpose during the next year. Further, consideration will be given to using this work as a test on the software/hardware transparency achievable with object oriented systems. A preliminary design of implementation of the algorithms in special purpose hardware and an estimate of the cost and effort in building the special device will be made. References [1] Parnas, D.L., "On the criteria to be used in decomposing systems into modules," Comm. ACMI, Vol. 15, No. 12, December 1972. [2] Shaw, M., "The impact of abstraction concerns on modern programming languages," Proc. of the IEEE, Vol. 68, No. 9, pp 1119-1130. [3] Introduction to the IAPX 432 architecture, Santa Clara, Ca 95051: Intel Corporation, 1981. [4] Mudge, T.N., R.A. Volz, D.E. Atkins, "Hardware/Software Transparency in Robotics Through Object Level Design," Proc. of the SPIE Tech. Sym. West, August, 1982. Annual Report 72 August 1, 1982 - July 31, 1983

[5] Volz, R.A., T.N. Mudge, D. Gal, "Using ADA as a Robot System Programming Language," Proc of 1Sth Symp. on Industrial Robot and Robot 7 Conf. and Exposition, Chicago, Illinois, April 1983. 3.5. Improved Robot Programming Robot system programming of today, whether performed in teach mode or off line, is characterized by the need to specify geometric data explicitly and the need to tie up production equipment for significant periods of time (for training or debugging). The first is a task not well suited to humans. In teach mode it becomes tedious or difficult for repetitive or complex motions, and nearly impossible if sensor inputs such as vision or force are involved. In off line programming the explicit entry of geometric data becomes a severe problem unless coupled to a teach mode, which can reintroduce some of the problems mentioned above. The second characteristic, tying up production equipment, is likely to be costly since most process machinery is quite expensive. This portion of the project seeks techniques to alleviate these problems through the use of computer aided design (CAD). It is presumed that all objects to be manipulated and the robot itself are modelled with a suitable CAD system and that this data is available for manipulation by support programs for the robot programming system. Three subprojects are currently underway: 1. Development of algorithms to automatically determine gripping positions of objects from their CAD model. 2. Extraction of the training information for certain vision systems from the CAD models of the parts to be recognized, and modelling the probability of finding a randomly dropped object in a particular stable state. 4. Developing a graphical programming system for robots using widely available inexpensive hardware. The first of these will help reduce the amount of data which must be explicitly provided by the programmer, and is a step toward allowing programs to be written in terms of the objects to be manipulated and the operations to be performed rather explicit geometries and motion. The second can eliminate production downtime for certain training operations. Also, knowing the stable position probabilities is important to provide an ordering (most probable first) for searching for the identity and stable position of an object. Automatic vision training and gripping position determination are being integrated into the experimental robot system described in the previous section. Graphics has proven to be a natural method of human interaction with computers in many areas. Subproject 3 is investigating the viability of a graphical approach to robot programming and the feasibility of incorporating the nongeometric aspects of programming into a graphics programming system. The following sections describe each of the subprojects in greater detail. Annual Report 73 August 1, 1982 - July 31, 1983

3.5.1. Automatic Determination of Gripping Positions Professor R. Volz, Professor T. Woo Problem Definition The distinguishing characteristic of robot manipulators in manufacturing is their versatility. Unlike special purpose machines, a robot is capable of handling a large variety of objects in a broad spectrum of tasks. Because of this, robot programming techniques must take advantage of the robot's full range of capabilities. Currently, those robot programming methodologies which do not restrict the flexibility of the system require long development times even by skilled programmers. This is especially true when sensors are coupled with the robot. The solution to this problem is to program the robot at a higher level of abstraction. All actions should be specified in terms of their effects on objects in the workspace. Instead of telling the robot to move through a particular point in space, to given position, and close the hand, it should be possible to simply instruct the robot to pick up the part. Such task level instructions allow flexibility without making the programming process unduly complex. To interpret task level instructions is difficult. Such instructions assume factual knowledge about the part, the work area, and the robot plus procedural knowledge on how to find a sequence of motions which will accomplish the objective without violating any constraints. A critical component of a task level programming system is an algorithm to automatically determine acceptable gripping positions for the objects to be manipulated. To be acceptable, the method must * be able to find a solution in most situations where one exists. * avoid object slippage in the gripper. * avoid object dislocation while gripping. * avoid collision between the robot, the object and other objects in the workspace. * be able to produce results in real time. While a few schemes have been suggested, there is no available technique that adequately achieves all of these objectives. The goal of this work is twofold: (1) to develop techniques to meet the above objectives; and (2) to integrate the resulting methods with the experimental system described in Section 3.4 to produce a CAD driven robot system. Approach The approach being taken in this project is characterized by the following key aspects. (1) Extraction of geometric information about the part from a Computer Aided Design (CAD) system. (2) Development of quantifiable criteria for a good grip and use of the criteria to judge the relative quality of gripping positions. Annual Report 74 August 1, 1982 - July 31, 1983

(3) Use of extensive off-line preprocessing to generate a grip-list which can be used to select a grip at with minimal run-time computation. (4) Use of a simple learning mechanism to improve preformance with experience. A prerequisite for finding gripping positions is the availability of detailed geometric information about the part and the robot gripper. Part information is assumed to be polyhedral and is derived from a description generated on a Computer Aided Design system. This information takes the form of a topological and geometrical description of the surfaces of the object in terms of faces, vertices, and edges. To be able to chose a grip intelligently one must be able to judge the relative quality of two gripping positions. For this a quantitative method of rating grips is needed. Grips must not cause interference between the robot, the object and the surroundings. Among these potential grips satisfying this condition,the likelihood of the part slipping in the gripper, or being displaced while the gripper is closing on the part is used as a cost of the grip. In order to minimize delays caused by decision making while the robot is operating, as much computation as possible is done ahead of time. However, it is not always possible to compute everything off-line because some of the information needed may not be available until run time. For example, if the task is to remove an object from a bin of parts, the object's description and the geometry of the robot will be known in advance, but the exact positions of the object and the surrounding obstacles will be unknown until run-time. Thus, the approach used consists of two stages: one off-line, one on-line. First, a large selection of possible grips on the part is found and sorted by quality. Since this is done off-line, it is reasonable to go through a fairly complex procedure to ensure that the list is a good as possible. This is done by proposing a large, diverse set of grips, and then successively refining and resorting it to take into accolunt all known constraints. All grips which produce interference between the hand and pad are eliminated. The remaining potential grip positions are evaluated by criteria measuring slipping and twisting. During on-line operation a single grip is selected from the off-line generated grip list. Starting from the highest-rated grip on the list, each grip is tested to see if it is usable without causing interference with objects in the workspace in the actual situation. The first usable one found is used. Further improvements can be made in the preformance of the system if we record which grip was chosen each time a selection is made. We can then periodically re-sort the list to bring the most used grips to the top of the list. The effect of this is to reduce decision time by testing the most commonly used grips first. In this way the theoretical rating of grips by quality can be augmented with a practical rating of grips by usefulness. Status of the Research Effort Implementation of an initial version of the gripping program is now nearing completion. In the program, a series of filters is applied to produce a list of grips on the part. The part is analyzed for pairs of surfaces which are appropriate to grip on. Such surfaces mIust be parallel, opposite each other and have a spacing compatible with the gripper. Then, a variety of specific grips are proposed on both surfaces. Annual Report 75 August 1, 1982 - July 31, 1983

These are spaced uniformly around the boundary of the gripped surface. Using a two-dimensional projection of the obstacles around the surface, each of these proposed grips is tested to make sure that there are no intersections between the hand and the part. Finally, each grip is evaluated for vulnerability to two kinds of slippage, translation and rotational, and to twisting of the part during the application of the gripper. Vulnerability to slippage depends, firstly, on the forces and torques which are applied to the object. Though exact magnitude of the torques cannot be accurately predicted, torques due to acceleration and gravity increase with the distance of the grip from the center of mass of the object. Translational slippage depends only upon the gripping force, the coefficient of friction and the gripping force. The first two are generally fixed by the part and the robot while the third depends on the gravitational loading. The resistance to rotation between the fingers depends on the size and shape of the contact area as well as distance from the center of mass. The resistance to twisting out of the fingers while being grasped depends on how far the fingers must be forced apart. These measures are computed and the results are combined with the distance from the center of mass to produce a single rating for each grip. This rating is then used to sort the grip list. In applications where parts appear only in their stable positions, the concept of stable positions is used to further refine the grip lists. The stable positions of the part are found. Those grips which would force the hand to intersect the work surface are culled out. This results in one grip list per stable position, instead of one grip list per object. Future This system will soon be integrated with an experimental manufacturing cell. This will result in a system which can train itself to recognize, locate and retrieve parts on the work surface, based entirely on information derived from CAD model. When this has been done, its performance on typical mechanical parts will be studied and refinements to increase its speed and reliability will be made. Further studies will be initiated to study further constraints (on motions as well as gripping) when assembly is to take place and one has a sequence of geometric model states to work with. 3.5.2. Off-line Training of Vision System and Stable Position Modeling Professor R.A. Volz, Professor A.C. Woo Problem Definition Most robot vision systems recognize parts by measuring various features on an image and comparing them with known features for the candidate parts. In order to formulate an optimal strategy to identify each part it would be useful for the recognition system to know what range of values each feature of each part typically takes and how likely each stable position of a part is to appear. Annual Report 76 August 1, 1982 - July 31, 1983

Feature information can be obtained by presenting the vision system with several images of each part, and by allowing the system to calculate the feature distributions for each one. This process is known as training and is currently done by physically placing sample parts beneath the camera. This ties up the manufacturing cell and forces some production down-time. Knowledge about the likelihood of parts appearing in different positions can be used to improve the overall preformance of a vision system. While it is clear that, for example, a nail will be found laying on its side more often than standing on its head, it is difficult to make good quantitative estimates of the relative probabilities of these eveiits. Most existing vision systems make simplifying or erroneous assumptions, such as that all positions are equally likely. Modeling a mechanical object probabilistically provides a quantitative measure and improves the effectiveness of the vision system. Approach The alternative being studied here is to train the vision system from computergenerated images of the parts. These images would be based on descriptions of the parts which are generated on a standard Computer-Aided Design (CAD) system. This approach would allow the vision system to be trained completely automatically, without any down-time for training or skilled programmers for off-line programming. Secondly, from the complete description of each part the stable positions of the part and the relative likelihood with which each position occurs are computed. The likelihood of a position depends not only on the shape of the part and on the location of its center of mass, but on the physical parameters of the surfaces on which it is dropped, and on the manner in which it is dropped. Status of the Research Project A system which generates images of parts in various positions and orientations has been constructed. The images simulate distortion arising from perspective and from quantization error. Perspective distortion arises when the part is seen from a slight angle rather than directly from above. Quantization error arises when the image in encoded into a grid of black and white pixels. These types of distortion must be modeled in order to simulate the variation that will be encountered in actual images. An algorithm has been developed which predicts the likelihood of each position of a part by statistically simulating the rolling process. Initially, the probability that the part first lands on each face is computed. If the part is dropped randomly, this is proportional to the angular area of the face. The probability that the part will tip from each face to each other face is found next, and this is used repeatedly to simulate a roll. The duration of the roll depends on the initial energy of the part. In hindsight, it is intuitive that if the initial energy is very low, the part will always remain in the position in which it was originally set down. Otherwise, the rolling continues until the remaining energy is insufficient to tip the part. The main results are nevertheless surprising in many regards. First, mechanical objects of complex geometries have stable positions that are difficult to visualize and time Annual Report 77 August 1, 1982 - July 31, 1983

consuming to experiment with. This algorithm computes all possibilities, no matter how small the probabilities. Second, the stable positions correspond to faces of the convex hull, i.e. the smallest convex body that encases the given object. It should be noted the faces of the convex hull are not necessarily the faces of the object, as in the case of a chair. Third, not all the faces of the convex hull are stable. To validate the results, actual experiments consisting of 400 to 1000 rolls with a variety of parts, on a variety of surfaces were carried out. The probabilities computed by this algorithm are remarkably close agreement with those determined experimentally generally within 0.01. Future Both of the described subsystems have passed initial tests. The next stage will be to integrate them with a vision system currently being developed. A demonstration of a vision system trained from a computer-aided design system is anticipated. 3.5.3. Graphical Programming of Robots Professor A.W. Naylor, Professor R.A. Volz Motivation, Goals and Problems A key problem of the factory of the future is the time and effort needed for the development, debugging, and the maintenance of software. Currently even mediumsized, highly automated manufacturing facilities require programming measured in person-years. One of the goals of the total research program, not just this project, is to reduce the time and effort necessary for this programming and to make it easy for the user to understand the system being developed. This theme can be noted throughout this section and all of the parts of this report. One component of the factory of the future programming is the programming of robots [5]. Currently, robots are almost universally programmed using teaching. This is unsatisfactory for several reasons, primarily because of the time required for programming can be a serious cost to the manufacturer[l]. Almost as important, this mode of programming does not fit with the other kinds of programming needed for the manufacturing facility. One wants a uniform, efficient and simple method of programming for the entire manufacturing facility, not many different programming systems that are difficult to interrelate [3]. With this in mind, this project is concentrating on the offline, graphical programming of robots. Graphical methods will be one of the keys to efficient userfriendly methods of programming the factory of the future. as they will allow users to avoid tedious programming and will allow them to understand the programs being developed more easily. These methods will largely obviate the need for learning elaborate programming languages. While the advantages of interactive graphical methods are widely appreciated, the problem is to realize them in a practical way [1]. Therefore, one of the special characteristics of our project is to concentrate on developing a robot graphical programming system that is based on simple, inexpensive hardware and relatively small software systems. This is crucial because most of Annual Report. 78 August 1, 1982 - July 31, 1983

the manufacturing done today is carried out by small to medium size firms. These firms are more likely to purchase inexpensive, general purpose computers that can be applied to many of their problems, among them robot programming, part programming, process planning, material transport programming, etc., than they are to invest in large, expensive systems. For this reason this project focuses on the use of personal computers. With careful, innovative, and new methods of programming, it will be possible to develop sufficient functionality to have a realistic and practical system that is useful to the small manufacturer. Such an approach is not just applicable to robot programming but also to other programming areas of the factory of the future. Each of these areas are envisioned as having an offline, graphical programming system running on a small computer.'What requirements are needed in a graphical system for robot programming? Obviously, one wants to see a robot in the scene and to manipulate the robot and its environment [4] to carry out the programming without learning any specific language or details about the robot. This is the essence and the value of a graphical programming tool. However, there are additional requirements unique to this project. First this project attempts to develop a practical tool based on very limited hardware capabilities. Second, this project tries to develop tools in such a way that they can be eventually used in the larger context of the total programming of the manufacturing facility. Thirdly, and perhaps the most difficult and potentially the most important, this project attempts to incorporate tools which allow us to approach nongraphical aspects of robot programming in a graphical manner [1]. For example, much of the robot program has to do with logical conditions and utilization of sensor data [2,3]. Neither of which is usually represented graphically. Moreover, the solutions to these problems will obviously carry over to the more general programming of the total manufacturing facility. Approach A high level of graphical interaction is used so that the system requires no knowledge of specific robot languages and allows graphical or geometrical thinking. Graphical interaction is required for most of the commands. It is used in the system for menu selection for 3D rotations and.translations, for 3D point selections and for movements of the robot. Several graphical interaction devices are possible including: * 2D and 3D joysticks, o mice, and * 2D and 3D digitizing tablet. Currently, only a 2D joystick is used as this provides a minimal hardware configuration found on most personal computers. The system will allow these other graphical devices to be easily incorporated. The commands available in the system are chosen from the displayed menu. Similar commands are grouped into a single menu. These menus are arranged in a, hierarchal fashion forming a tree of system commands. As the user selects a command using the joystick, the system displays and manipulates the graphical representation of the parts and the robot. Annual Report 79 August 1, 1982 - July 31, 1983

Simple wireframe CAD models of the parts and robot are used in our approach. The user selects parts previously defined by a CAD system and places them into the robot's workspace. Once parts have been loaded, the user may manipulate the graphical representation of these parts to define the desired programming environment of the robot's workspace. A simplified, scaled graphical representation of the robot is used to avoid confusing and intimidating the user. Once the programming environment has been defined, the user manipulates the graphical representation of the robot. These manipulations are in essence, robot programming commands. The desired user's manipulations are recorded by the system and translated into a specific robot program at the conclusion of the programming session The initial system produces VAL code for the Unimation PUMA 600 series robot arm. Simple, low cost, off-the-shelf hardware was used for the system. An IBM PC Personal Computer was chosen for the initial implementation of the offline programming system. This microcomputer was chosen because it: * was expected to occupy a large market share, * has color graphic support, * has a large memory capacity, o has high-level language support, and * utilizes 16 bit, state-of-art microprocessor. The expectation that IBM PC would dominate the small business market was the most significant reason that this system was chosen. Almost as significant, was the fact that this microcomputer had all hardware capabilities that were needed. The offline programming system should be transportable to other computer systems and robots. the system depends only on simple move operations in the robot controller, avoiding special operations of individual robots. As much of the system software as possible is written in a popular high-level language in a careful manner, so that it can be easily transferred to other microcomputer systems. In addition, the system is written in such a way that it should be easy to support additional robot systems and languages. Results to Date The basic framework has been completed, debugged and demonstrated since May 1983. This framework includes the graphical or geometrical abilities and simple robot programming abilities. * to display and manipulate graphical representation of the objects and the robot in the workspace, * to join representations of individual objects to form composite objects, or to break apart composite objects, * to view from different perspectives with different scales, and * to generate robot code corresponding to the manipulation of a graphical representation of the robot. Annual Report 80 August 1, 1982 - July 31, 1983

Currently, many of the users interactions will be carried out using the 2D joystick with either very intuitive use of cursor movements or some utilization of menus. Many of the commands now entered from the keyboard are now in the process of being moved to the joystick. Ideally, user should rarely move his eyes from the screen and rarely utilize the keyboard. Currently, the system takes several seconds to redraw the screen, but a completed analysis of our software indicates that the problem is the floating point software in the complier. An 8087 floating point processor for the IBM PC has been acquired. This floating point processor along with a new version of the compiler should decrease the execution time of the system allowing real-time operation of the system. Future Issues In the future the use of graphical input devices in the system will be fully incorporated. A considerable effort must be made in developing efficient, usable techniques for selecting a three-dimensional point using two-dimensional input devices [1]. Repetitive, non-geometrical operations such as the loop, task and logical constructs must be defined and implemented. Sensory inputs must be effectively incorporated into the system. These may be particularly troublesome, as these inputs are often specific to the application. The real task here is to develop mechanisms which provides for these inputs but does not specifically bind information about the application into the programming system. In our second year we propose to finish the geometrically functionality of the system and plan the concepts needed for the non-geometric issues. Our third year will be spent implementing these non-geometrical concepts. References [1] Ambler, A.P., (Dept. of Art. Intelligence, University of Edinburg.) "Languages for Programming Robots," Nato Advanced Studies Institute on Artificial Intelligence and Robotics, June 1983, Barga, Italy. [2] Bauman, E.W., "Model-Based Vision and MCL Languages," 1981 International Conference on Cybernetics and Society, October 26-28, 1981, Atlanta, Georgia. [3] Kretch, S.J., "CAD/Cam for Robotics" paper, Robot VI Conference, March 2-4, 1982, SME, Detroit, Michigan. [4] Kretch, S.J., "Robot Animation," Mechanical Engineering, Vol. 104, No. 8, pp 32,35, August 1982. [5] Lozano-Perez, T., "Robot Programming," AI Memo No. 698, December, 1982, MIT Offshoots As an offshoot of the targeted system we have developed a program which downloads on IBM PC file into a VAL program on the robot controller. The program runs independently of the graphic programming system, but is used to transfer the generated offline program to the robot. While the robot controller does not Annual Report' 81 August 1, 1982 - July 31, 1983

permit the usage of a specific communication protocol, the developed program checks most of the data received against the transmitted data, allowing for virtually errorfree transmission. 3.6. Knowledge Based Distributed Database Design; Professor K.B. Irani Motivation, Problem and Objectives The current trend in the integrated manufacturing environment is to interconnect, by means of local networks, computers used in manufacturing. One of the major issues in such environment is the appropriate distribution of data among the various nodes of the network. The advantage of assigning fragments of relations over a network in a distributed database system is well understood. With the appropriate replication of fragments, total network flow is reduced, and the probability of parallelism in distributed query processing is increased, while the update cost induced by replication is confined to the replicated fragments. We consider the problem of designing a distributed database system, in which each local database is a collection of the horizontally partitioned fragments of relations. It consists of two subproblems: 1) the problem of horizontal partitioning of each relation, and 2) the problem of distributing the fragments over a network. The latter is a matter of quantitative optimization which has been discussed in various file allocation problems. The former is, therefore, the principal issue of our work, for which we propose to establish a theoretical framework for partitioning relations horizontally. Approach In our work, the semantics of data and user queries at each site is exploited as a means of partitioning relations horizontally. In other words, a knowledge base which stores semantics is first constructed and then user queries are applied to the knowledge base in order to determine the unit objects, namely the fragments of relations, to be dispersed. The major issues addressed are knowledge identification, knowledge representation, and knowledge application. Once the unit objects to be dispersed have been determined with the application of the knowledge base, a mathematical programming technique is employed to derive the optimum allocation of the fragments. Results So far in our research, the three major issues, knowledge identification, knowledge representation, knowledge application, have been covered. The useful knowledge for our intended purpose is classified into two types; structural knowledge and intrinsic knowledge. The former is the collection of the semantics which is usually captured in logical schema and the latter is the collection of the Annual Report 82 August 1, 1982 - July 31, 1983

semantics which is inherent in the real world, but which is not expressed in any type of logical schematic representation. As a linguistic vehicle to represent both types of knowledge, a first order language LE called many sorted language with aggregate variable, is developed. A sufficient class of knowledge which has been identified useful is then expressed in certain types of sentences of L., called E-Horn sentences. The user queries which are also expressed in LE are applied to the knowledge base of E-Horn sentences via an inference procedure called IM, which has been proved sound. From this the unit objects to be dispersed are obtained. Future Study To determine the optimum allocation of the unit objects, cost optimization model is required to be developed in which storage and network data flow are considered major cost factors. 3.7. Generalized Problem-Solving Using Heuristics Professor K.B. Irani Problems and Objectives A generalized planning of robot actions from the current state to the desired state can be viewed as a generalized problem-solving through a state-space approach. A generalized heuristic algorithm to compute an evaluation function for problemstates (or simply states) is the key to a generalized heuristic search for problem-solving [2], [3], [4]. The evaluation function for the robot planning problem can be the measure of the most effective path from the current robot state to its desired state. We develop a generalized problem-solving process based on admissible heuristic search with the evaluation function for problem-states. This work consists of the following. (1) Generation of heuristics as the basis of algorithms to compute evaluation functions for problem-states. (2) Description of a problem in which heuristics are structured and embedded. (3) Formulation of a generalized algorithm, based on heuristics, to compute the evaluation function for problem-states. (4) Formulation of a generalized admissible search for problem-solving based on the evaluation function for problem-states. (5) Modification of the heuristic algorithm constructed for the evaluation function to improve the efficiency of the resulting heuristic search for problem-solving. Status of the Research Effort Generation of Heuristics: The problem-domain independent heuristics, as the basis of the generalized algorithm to compute the evaluation functions for the problem-states, are devised as Annual Report 83 August 1, 1982 - July 31, 1983

follows. Simplification: The distance for the problem-state is estimated over the simplified version of the problem. Parallelism: The distance for the problem-state is estimated as the sum of the sub-distances for object elements contained in the problem-state. The sub-distances are estimated independently by means of parallel operations. Description of A Problem. A state-space formulation, which is used to represent most of the problems in AI [1], is transformed into a formulation in which the above heuristics are easily structured and embedded. We formally define a state-space problem and its transformed version. Definition 2.1 A (state-space) problem D is a quadruple, D =(E,., e, ee) where - E is a set of problem-states Q- is a set of operators (rules) en is an initial problem-state in E ef is a final (goal) problem-state in E Definition 2.2: A transformed problem Dt is a nine-tuple, D = (Ob,1H, 0,property, R, COND, cost, e:n, e,) where - Ob is a set of object elements; Ob = {a,: i=, n}, - is a cartesian product of Z,'s for i E {1, 2,, m} such that E is a sub set of IH; E C = xZ=l Z, where Z, is a set derived from Ob, - is a set of functions, E,: Ob X Z, -t Q, such that the function,,': Z, - (Q,)!obl defined by Annual Report 84 August 1, 1982 - July 31, 1983

77 (lk) = <,(al, Ztk), e,(a, Zik), ~* *, e. (alo0^, Zk)>' is one one; = { e,: (e: Ob X Z, - Q,) A (Z, e Al) A (Q, is a characteristic set ) A (i = 1, 2,, m)} property is a mapping, property Ob X E - z Q,, defined by property (at, e) =property (at, <zl, X, * * *,mk>) = <1.(at, z,), 62 (at, Z2, *, em (at, Zmk)>, R is a set of (transformed) rules r, for i = 1, 2,, 1 where each r, is represented by a p-tuple, <a,, a2,', ap>; R = { r, = <al, ~ *, ap>: (r, E Ob) A GEN-COND (r,)} where GEN-COND (r,) is a predicate describing the set R, COND is an ordered tri-tuple; COND = <GEN-COND, PRE-COND, TER-COND> where GEN-COND (r,): A predicate describing a set R where r, E R PRE-COND (r, e): A predicate describing pre-condition of r, in e. under which r, is applicable to ewhere (r, E R) and (e, E E) TER-COND (r,, e,, ey): A predicate describing terminal condition of r, with respect to e, and eY, such that 1. TER-COND(r, e1, ey) -- (ey = r (e,)) 2. given (r, <al, a,, a,>), TER-COND(<a1, a2,, ap>, e, ey)(lYna)(((a, E 06) A (a, {al, a,,,ap})) - (property(a, e,)= property(a,, ey ))) (13at) ((ak E {al, a2,..*, ap})A (property(a;, e,) 7 property(ak, ey)))) where (r, E R) and (e E E ) and (ey E ), 1 b06 is a carclinality of a set Ob. Annual Report 85 August 1, 1982 - July 31, 1983

cost is a mapping, cost: R X E-, N where N is a cost-value set, - e, is an initial problem-state in E, - e is a final (goal) problem-state in E. The formulation of the transformed problem is illustrated by a simple example. Eight-puzzle problem, a well-known problem in AI [NIL 80], is considered. In this problem, object elements denote nine tiles including one blank tile. Ob = {t1, t2, t3, t4, t5, t6, t7, t8, t}. From the mapping of PERMUTATION on these object elements, a set of nine-tile permutations, n, is derived in which each problem-state is represented by some ninetile permutation. A property function, providing the property of the object element in the problem-state, maps the object element and problem-state (the tile and nine-tile permutation) onto the position of the tile in the nine-tile permutation. Each rule r, in R is represented by an ordered pair of two object elements but one of which is blank tile and other other is not. R= {< al,a2>: (<al,a2> E Ob) A GEN-COND (< a1, a>)} where GEN-COND(< a, a2>) - ((a1 7 a2) A (a- =tb})). Pre-condition. under which a rule <a1,a2> is applicable to a problem-state e,, is described by PRE-COND, PRE- COND( < al, a>, e,) = (((property(an,e,)= (property(a,,ez) + 1)) V (property(al,en) = (property(a^, e) - 1)) V (property(al,e) = (property(a2, e) + 3)) V (property(al, e) = (property(a^, e) - 3))) A (< property( al, ee), property( a, e)> { <3,4>, <4,3>, <6,7>, <7,6> })). Terminal condition describing rule-mapping is given by TER-COND, TER-COND(<a1,a2>, e,, ey) ((property(al, e) = property( a, e)) A (property(al,ey) = property(a,e,))). Annual Report 88 August 1, 1982 - July 31, 1983

The cost function, providing cost of a rule when applied to some problem-state, maps the rule and its applicable problem-state onto unit value, 1. Heuristic Algorithm to Compute Evaluation Function: The evaluation function on the problem-state is, more precisely, related to computing the distance from the given problem-state to the goal problem state. Our heuristic approach which permits parallelism and simplification, and which is to be formally developed, is roughly as follows. As shown in the transformed problem-description, a problem-state is formed on a set of object elements, and a unique set of properties of all the object elements derived from one problem-state distinguishes that problem-state from any other problem-state. When two problem-states, the current and the goal, are given, a unique set of properties of object elements is derived from each of the two problem-states. Then by comparing those two sets some object elements, each of which has different properties in the two states, are selected. For each of these selected object elements the required sub-distance for achieving its property in the goal state is computed independently, which is a parallel operation. The existence of dependency between sub-distances in some cases, which is not known in advance, may not make the estimated distance, which is the sum of all the sub-distances, be less than or equal to the actual distance. Further, the computation of a sub-distance itself may not be easy. These difficulties are resolved by introducing heuristic mechanism to compute a sub-distance, which makes the problem simpler. Future Work Formal construction of the generalized algorithm to compute the evaluation function on problem-states is currently being developed. Formulation of the generalized admissible search and modification of the algorithm for the evaluation function in order to meet the required efficiency are considered as the next steps to be developed. References [1] Barr, A. and E. Feigenbaum The Handbook of Artificial Intelligence, Vol. 1,3 William Kaufamann, Inc., Los Altons, CA, 1981. [2] Gaschnig, J., "A problem similarity approach to devising heuristics: First results", Proc. IJCAI., 1979. [3] Guida, G. and M. Somalvico, "A method for computing heuristics in problem solving", Information Sciences 19 (251-259), 1979. [4] Pearl, J., "On the discovery and generation of certain heuristics", AI Magazine, Vol. 4, No. 1, Winter-Spring, 1983. Annual Report 87 August 1, 1982 - July 31, 1983

3.8. Metaform Database Interface System Professor T. Teorey Problem and Objectives The Research consists of designing an easy to use, updatable database interface system called Metaform for an entity-relationship database which automatically produces customized form interface screens for users doing particular tasks. This system - when given an entity type - produces a form screen for that entity. Such a form screen along with several form operations such as "insert", "delete", "select", can be used as a database interface by a user doing a task related to that entity. This type of system is to be used by people who have limited query needs, who only need a few different views or perspectives of the data, and who are unable or unwilling to take the time to learn a more powerful interface system. With such a language a user can - with a minimal amount of training - both query and update the database without having to know about the database schema. Another major advantage of the Metaform system is that it will automatically generate the needed form screens. One major problem facing the MIS departments of major manufacturing companies these days is the large backlog of needed database interface applications. Metaform can be used to automatically implement easy to use form screens. No programmer time will be needed. Metaform will also be very useful in quickly and inexpensively developing prototypes of database designs. -This allows designs to be quickly tested and revised. Status of the Research Effort (1) A pilot user interface study was conducted to determine whether the form screen interface system could be learned by a wide variety of users. Another objective was to find problem areas in the language design so that they could be corrected before the formal analysis was done, and help develop teaching methods for such database interface languages which will be used with the actual test. The pilot study was completed in February 1983. The results obtained indicated that the form screen interface language could be learned in only about 20 minutes, error rates were low and query times were excellent. (2) An entity relationship normal form for the relational data model was developed which in essence allows an entity relationship database to be embedded in the relational model. (3) A formal definition of a form schema and a form based on logic and set theory was developed. (4) A form specification/query language, similar to the relational calculus which produces a form schema and a set of forms expressing any query result, was designed. This is the target language for the algorithms which automatically generate a form schema given an entity type. Thus an algorithm for automatically producing a form schema given an entity type and a relational database schema in entity relationship normal form, was developed and implemented (6) Form operations and their semantics were defined which may be used in conjunction with the form schema to query and update the database through the form screens. The users do not have to know about the actual structure of the Annual Report 88 August 1, 1982 - July 31, 1983

database schema; they only see the data in terms of the form screens. This greatly simplifies the interface for the users. Also, functions which translate the form query and update operations into relational database query and update operations were developed. Future Research We plan to conduct the formal user interface analysis of the form screen database query and update system, using a personal computer implementation. The design of this test is based on the results of the pilot study. In general the experiment will involve teaching a group of subjects how to use the form screen and then testing their knowledge. Times for learning, doing query tasks, and the number of errors made in doing query tasks will be collected. Specific applications in manufacturing systems, such as the computer-based build information broadcast system used in the automotive industry (D. Kochhar), will be investigated. Associated Projects in Database Systems Several additional unsponsored projects related to AFOSR objectives produced interesting results in the area of database design, data allocation, and database migration. These were guided and reviewed by T. Teorey under AFOSR sponsorship: Usage Dependency Model Logical database design derives an accurate and efficient DBMS-processible schema from a set of end user database system requirements. Traditional logical database design, while effectively dividing the process into conceptual (processindependent) design and DBMS-schema (process-dependent) design, has not been able to make use of computer automated techniques to produce schema designs. A well known technique for satisfying the accuracy requirement for a DBMS schema, that is, accurately representing the real world organization where data is to be defined, is the functional dependency model of normalization theory. This model has been extended to encompass "usage dependency", that is, specifying the probability of joint data usage based on process and data correspondence identified in the user requirements. The combined application of usage dependency and functional dependency provides efficiency in a DBMS schema, both for the short term based on current processing requirements and for the long term flexibility for future processing requirements. The proposed future work involves formally defining the usage dependency concept, developing an extended relational theory for logical database design based on the combined concepts of functional dependency and usage dependency, and finally defining a canonical form that will permit transforming normalized relations into DBMSprocessible schemas. Annual Report 89 August 1, 1982 - July 31, 1983

A Method for Database Record Clustering Record clustering is one of the important problems in physical database design. A heuristic method is demonstrated for identifying the record types in a database that are to be clustered together so that the total access time is minimized for the designed database. A paging environment is assumed. The clustering result, while known to be optimal for hierarchical databases, is shown to be at least near optimal for network databases. Performance of Concurrency Control and Data Allocation in Distributed Database Systemns One of the most important reasons for using a distributed database system is to achieve good performance. The objective of this research is to analyze different concurrency control algorithms and the joint effects which data allocation and concurrency control mechanisms have on the response time performance of a distributed database system. Response time can be decomposed into well-defined components such as request transmission time, data manager (DM) waiting time, data manager service time, and result transmission time. A spectrum of user transactions is defined and, for each class of transaction, DM queuing disciplines are defined. Well-known concurrency control mechanisms are defined, and specifically their DM service times are modeled. A mathematical model is developed which uses the DM service time and transaction arrival rate to predict the expected DM waiting time, leading to a detailed computation of response time. A number of conclusions can be drawn from the findings: Data allocation schemes have a significant effect on communication delays and DM service times for both retrieval and update transactions, and in turn, influence the DM waiting time. Concurrency control algorithms also help determine DM service time and waiting time. Because these are major components of response time, a data allocation scheme that does not take concurrency control into consideration could result in nonoptimal performance. The two phase locking protocol is characterized by a large variance of DM service time, which results in longer expected lock holding times than would be obtained with another concurrency control mechanism with small variance of DM service time. Even if the system remains unsaturated, this holding delay will result in a longer transaction response time. Thus, in performance evaluation of any data allocation scheme, it is necessary to consider not only the expected communication delay and expected data processing time but also the variances of these time periods. 3.9. User Needs for Information Display Professor D.S. Kochhar Problem Statement When designing an integrated manufacturing system, it is necessary to understand, specify and incorporate the human, machine and other organizational factors Annual Report 90 August 1, 1982 - July 31, 1983

that are likely to affect the adaptation and effective utilization of such systems by manufacturing, assembly or other production personnel. Many examples can be cited from the literature and from actual manufacturing sites that refer to the common problems that one can encounter if the end user or users have little or poor education about the information system, or when the interface between the hardware and the human operator at positions of information disply, interaction and operator response is not compatible with expected user behavior and expected user actions. At the interface level, the most primary requirements are for data and information display. Whether on information sheets, on a display panel or on a CRT, data and information on machinery status and functioning, on build orders or build status must be indicated in a manner that is conducive to the system being well received and being acceptable by those who need to use it. As such, the problem is to develop a methodology for the design and evaluation of the system-user interface at two levels: the process engineer who interacts with databases on parts information, and the operator on the line where the displayed information is utilized. Objectives The issues of data display at the interface level require that interface problems be examined and resolved. The objectives of the research are to: (1) determine date requirements for the initiation, monitoring, control and evaluation of manufacturing and assembly processes, (2) establish criteria for the design of interactive access capabilities for measurement, display, analysis and reporting of manufacturing data and (3) propose and evaluate the extent to which the developed criteria can be used in actual situations. It is not intended to restrict the investigation to interactive data base systems for viewing on a CRT only. Rather, other displays that are used with automated machinery, such as control and display panels for manual override and line status indication, are also examined. Status of Research Efforts Research to date has progressed along several dimensions. A research protocol has been established. It was initially necessary to obtain a working knowledge and understanding of the various facets of manufacturing and assembly in a variety of industries. Several manufacturing organizations were contacted and visited with a view to determining the nature of manufacturing related information and information dissemination methods that are either presently in use or being considered as the "next stage" of use. Plants visited included a major machine tool and jig mill manufacturer, other job shop operations engaged in the manufacture of precision tool bits, holders and cutters, production oriented parts manufacturers, a large engine manufacture and assembly operation, several automobile assembly operations, and several robot assembly distribution centers. A local company engaged in the development of software for manufacturing was also contacted. On the basis of these visits, observations and study, several facets of manufacturing and assembly information have been recorded. Annual Report 91 August 1, 1982 - July 31,'1983

As a next step in the investigation, attention and resources are being focussed on one manufacturer, namely automobile manufacture and assembly. As such, a working relationship has been developed with the Ford Motor Company. Informational needs for manufacturing and assembly are being reviewed in some detail for two distinct segments of the overall operations, namely (1) for the automated body shop assembly processes where information is displayed and operator interaction is primarily via large control and display panels located along the entire assembly fixture sequence; and (2) for the entire build area that uses a company wide, computer based parts broadcast system. For example, automated body shop assembly requirements for information are for various types of control panels that display the status and functioning of indexing machines, body construction fixtures and the function and sequencing of spot weld machinery. In addition, a computer based diagnostic system provides back-up support for troubleshooting complex machinery. Troubleshooting, maintenance, line status indication and manual override of any part of the line require human intervention. The objectives are to determine how the task of the line and maintenance operators can be made easier. A computer based build information broadcast system, in hard copy form, is commonly used by industries engaged in continuous or batch production. Coded information on individual parts is itemized at various co-ordinate locations on a hard copy broadcast sheet. For example, a part information needs to be broadcast when (i) all options need to be identified (ii) all high warranty cost items for which repair costs are high need to be identified (iii) all engineering mandated items need to be identified (iv) all government mandated items need to be identified and (v) all complex parts with a potential for misbuild need to be identified. A review of the present methods of parts specification for hard copy broadcast is currently in progress. To aid the review, a computer simulation of the conventional hard copy display has been developed. The purpose of the simulation is to provide the flexibility to evaluate alternative displays for human operators on the line. The investigation focuses on determining how needed build information could be provided on-line at the assembler workstation using an electronic display such that a full broadcast is used on a main assembly line and a reduced and more specific broadcast is used on the sub-assembly lines. This effort is being coordinated with other researchers who are working on the development and use of metaform query languages for on-line selection and choice (Teorey). 3.10. Requirements Analysis Dr. Louis Boydstun Problems and Objectives It is widely accepted that the success of an information system is highly dependent upon the initial description of systems requirements. Based on this observation there have been many attempts to develop methodologies for producing and analyzing information systems requirements. One approach to this problem is based on the observation that the development of information processing systems is itself an information processing activity that can be enhanced by a computer aided information Annual Report 92 August 1, 1982 - July 31, 1983

processing system, and while a methodology can never be completely automated, it can be computer aided. Many methodologies have been proposed to aid in the development of systems requirements ranging from data flow or input/output requirements to detailed software specification methodologies. A comparison of various approaches indicates that a methodology can be considered as consisting of four major parts: * A method that specifies the activities performed, control functions exercised and documentation to be produced. The method may be divided into two components: the activities or tasks and the order or sequence in which they are undertaken. The activities or tasks may be further subdivided into those tasks. Each activity or task is described by the steps or subactivities that must be carried out, the data that is used, the results that are obtained and the tools that procedure used. * A model or conceptual formulation that is the basis for creating a particular target system instance. e A system description language or notation that is to be used to represent a particular target system. * The aids and tools, manual or computer aided, that are used in creating a target system instance. These four components are common to all methodologies. However, there are major differences between the various methodologies. These differences result from the variety of target systems and environments encountered in the real world. Manufacturing information systems, which have characteristics similar to other information processing systems, contain a number of activities occurring simultaneously at geographically dispersed locations. Thus a manufacturing information system requirements methodology should include procedures for describing the interaction requirements between highly concurrent activities and data flows. An objective of this research is to extend current methodologies to include real time manufacturing information systems aspects not addressed by current requirements analysis methodologies. Approach Experience in data processing applications indicates that the key to successful integration of computer based applications is through a logically integrated database. Choosing the optimum database structure (schema) however is not easy even in relatively well understood and standard data processing applications. Part of the reason for this is the complexity of the real world that is being modelled by the database schema. One of the tools to aid in modelling is the computer itself. Computer aided system modelling techniques such as PSL/PSA have been used in a wide variety of data processing applications including the aerospace industry by companies such as Boeing, McDonnell Douglas, Grumman and General Dynamics. The approach being take is to extend current capabilities is to explore the issues via an extensive realworld example. Annual Report 93 August 1, 1982 - July 31, 1983

Status of the Research Effort The use of a System Description Language/System Description Analyzer (SDL/SDA) capability for modelling a real-world problem and the evaluation of the feasibility of generating simulation models from an SDA database has been started. The real-world problem selected for the evaluation is a military network system development project, currently in progress in a major company. The network described consists of 8 consoles, 4 cabinets or processors, 2 system buses, and 5 sensing device interfaces. The consoles process operator requests and performs those processes which are required for system reporting and analysis functions. The cabinets contain multiple processors which perform general purpose and signal processing functions. The sensing devices process various types of analog information and convert this information into digital data streams at the device interfaces. The network has over 400 message types. These have described in detail using SDL statements. The SDL descriptions are sufficiently detailed to generate simulation models from the SDA database. A preliminary analysis, however, indicates that the database is too large to generate simulation models. Future Dr. Boydstun, who led this project has left the University and the funding of this activity will be redirected to strengthen other activities in the coming year. Annual Report 94 August 1, 1982 - July 31, 1983

4. Publications 4.1. Journal publication Control of Mechanical Manipulators [1] Gilbert, E.G., "Conditions for Minimizing the Norm Sensitivity of Characteristic Roots," Accepted for publication in IEEE Transactions on Automatic Control. [2] Kim, Byung K., and Kang G. Shin, "An Adaptive Model Following Control of Industrial Manipulators", to appear in the 1984 January issue of IEEE Trans. on Aerospace and Electronics Systems. [3] Lee, C.S.G., "Robot Arm Kinematics, Dynamics, and Control," Computer, vol 15, no 12, December 1982, pp 62-80. [4] McClamroch, N.H., "Sampled Data Control of Flexible Structures Using Constant Gain Velocity Feedback", to appear as CRIM report, accepted for publication by AIAA J. Guidance, Control, Dynamics. Architecture of Robot-Based Manufacturing Cells [1] T.N. Mudge and J.L. Turney "Unifying Robot Arm Control," Proceedings of the 1982 Annual Meeting of the Industry Applications Society, October 1982, pp 1315-1324. Also to appear in IEEE Transactions on Industry Applications. Metaform Database Interface System [1] Chen, David D., "Performance of Concurrency Control and Data Allocation in Distributed Database Systems," Ph.D. Thesis, University of Mlichigan, CICE Program, April 1983. 4.2. Under Review Control of Mechanical Manipulators [1] Gilbert, E.G. and I.J. Ha, "An Approach to Nonlinear Feedback Control with Applications to Robotics," Submitted to IEEE Transactions on Systems, llan and Cybernetics. [2] Kim, Byung K. and Kang G. Shin, "Minimum-Time Path Planning for Robot Arms with Their Dynamics Included", submitted to IEEE Trans. on System, Alan, and Cybernetics. [3] Lee, C.S.G. and M. Ziegler, "A Geometric Approach in Solving the Inverse Kinematics of PUMA Robots," Submitted for publication to the IEEE Transactions on Aerospace Engineerinlg, (First revision) for publication. Annual Report 95 August 1, 1982 - July 31, 1983

[4] Lee, C.S.G. and M.J. Chung, "An Adaptive Control Strategy for ComputerBased Manipulators," Submitted to the IEEE Transactions on Automatic Control (first revision) for publication. [5] Lee, C.S.G. and B.H. Lee, "Resolved Motion Adaptive Control for Mechanical Manipulators," Submitted to the Transaction of ASIE, Journal of Dynamical Systems, Measurement, and Control for publication. [6] Lee, C.S.G., B.H. Lee, and R. Nigam, "Development of the Generalized d'Alembert Equations of Motion for Mechanical Manipulators," Submitted to the International Journal of Robotics Research for publication. [7] McClamroch, N.H., "Vibration Control of Flexible Structures using Electromechanical Transmission Type Actuators," to appear as CRIM report, submitted to AIAA J.Guidance, Control, Dynamics. [8] McClamroch, N.H., "Displacement Control of Flexible Structures using Electrohydraulic Servo Actuators," to appear as CRIM report, submitted to ASME J. Dynamic Systems, Measurement, Control. [9] Shin, Kang G. and Neil D. McKay, "Minimum-Time Control of Robotic Manipulators with Geometric Path Constraints", submitted to IEEE Trans. on Automatic Control, [10] Shin, Kang G., and Stuart B. Malin, "A Structured Framework for the Control of Industrial Manipulators," submitted to IEEE Trans. on System, Alan, and Cybernetics. [11] Shin. Kang G., and Stuart B. Malin, "A Hierarchical System Structure for Coordinated Control of Industrial Manipulators," submitted to International Conference on Robotics. [12] Shin, Kang G., and Neil D. McKay "Open-Loop Minimum-Time Control of Mechanical Manipulators and Its Applications," submitted to 1984 American Control Conference. [13] Kim, Byung K. and King G. Shin, "An Efficient Minimum-Time Robot Path Planning Under Realistic Conditions," submitted to 1983 Amerrican Control Conference. Vision for Robots [1] Delp, Edward J. and Paul Eichel "Motion Parameters Estimation: Decoupling the Scale Change Parameter,: submitted to IEEE Trans. on ASSP. [2] Delp, E.J. and H. Chu, "Edge Detection Using Contour Tracing," Submitted to IEEE Trans on PAMlI. Architecture of Robot-Based Manufacturing Cells [1] Volz, R.A., T.N. Mudge and D. Gal "Using Ada as a Robot System Programming Languages" Submitted to IEEE Transactions of Systemn, Alan, and Cybernetics Annual Report 96 August 1, 1982 - July 31, 1983

4.3. In Preparation Control of Mechanical Manipulators [i] Chung, M.J., "Adaptive Control Strategies for Computer-Controlled Manipulators," Ph. D. Dissertation, the Computer, Information, and Control Engineering Program, the University of Michigan, Ann Arbor, August 1983. [2] Howe, R.M., "Special Algorithms for Simulation of Lightly-Damped Structural Modes," To be submitted to Transactions of the Society for Computer Simulation. [3] Kim, Byung K. and Kang G. Shin, "Suboptimal Control of Industrial Manipulators with a Weighted Minimum Time-Tuel Criterion", IEEE Trans. on Automatic Control. [4] Whitesell, J. and M. Steigerwald, "Automatic Generation of State and Costate Equation for Optimization of Mechanism Performance" Vision for Robots [1] Mudge, T.N., J.L. Turney, and R.A. Volz "Experiments in Occluded Parts Recognition," Proceedings of the Society of Photo-optical Instrumentation Engineers Cambridge Symposium on Optical and Electro-optical Engineering, To be submitted to IEEE Pattern Analysis and Machine Recognition. [2] Leith, E.N., G.W. Swanson and D. Angell Fringe projection systems using grating imaging," (to be submitted to Appl. Opt. ) [3] Leith, E.N., D. Angell (to be submitted to "An incoherent spatial matched filter system for robotic vision," Appl. Opt. ). Improved Robot Programming [1] Wolter, J., R.A. Volz and A.C. Woo "On the Automatic Determination of Gripping Positions" to be submitted to the IEEE Transactions in Industrial Applications [2] Volz, R.A., A.W. Naylor, and R. Jungclas, "The Graphical Programming of Robots," Technical Report Center for Robotics and Integrated Mianufacturing, College of Engineering, University of Michigan, October 1983. Metaform Database Interface System [1] Beard, D.V. and M.M. Mantei, "A Human Factors Benchmark of a Form Screen Database Interface System," (to be submitted to Communications of the ACMl 10/83). [2] Beard, D.V. and T.J. Teorey, "A Practical Solution to the Database Form Update Problem," (to be submitted to ACM TODS 12/83). Annual Report 97 August 1, 1982 - July 31, 1983

[3] Beard, D.V. and T.J. Teorey, "Automatically Generated Form Screen Interfaces for Entray-Relationship Databases (to be submitted to ACMI-SIGMOD 1984 Conference 1/84). [4] Hevia, E., and T.J. Teorey, "The Usage Dependency Model for Logical Database Design," (to be submitted to ACM-TODS 10/83). 4.4. Conference Presentations Control of Mechanical Manipulators [1] Gilbert, E.G., and I.J. Ha, "An Approach to Nonlinear Feedback Control with Applications to Robotics," Center for Robotics and Integrated Afanufacturing Technical Report RSD-TR-4-83, College of Engineering, University of Michigan September 1983. Presented at 1983 Conference on Information Sciences and Systems, The Johns Hopkins University (pp 612-618 of Proceedings). To be presented at the 1983 IEEE Conference on Decision and Control. [2] Gilbert, E.G., "Conditions for Minimizing the Norm Sensitivity of Characteristic Roots," Presented at 1983 Conference on Information Sciences and Systems, The Johns Hopkins University (pp 641-647 of Proceedings). To be presented at the 1983 IEEE Conference on Decision and Control. [3] Howe, R.M., "Special Considerations in Real Time Digital Simulation," Proc. 1983 Summer Simulation Conference Vancouver, Canada July 11-13, 1983 pp 66-71. The analytical methods were presented at a NASA sponsored Advanced Study Institute for Computer Aided Analysis and Optimization of Mechanical Systems Dynamics on August 1 thru August 12, 1983. [4] Johnson, D.W., "Efficient Computational Schemes for the Control and Simulation of Robotic Mechanisms," Presented at 1983 Conference on Information Science and Systems, The Johns Hopkins University (p 619 of Proceedings). [5] Kim, Byung K. and Kang G. Shin, "Suboptimal Control of Industrial Manipulators with a Weighted Minimum Time-Tuel Criterion", Proc. 22n9d CDC (to appear in December 1983). [6] Lee, C.S.G. and M.J. Chung, "An Adaptive Control Strategy for ComputerBased Manipulators," Proceedings of the 21st Conference on Decision and Control, Dec. 8-10 1982, Orlando, Florida, pp 95-100. [7] Lee, C.S.G. and B.H. Lee, "Resolved Motion Adaptive Control for Mechanical Manipulators," Proceedings of the third Yale Workshop on Applications of Adaptive Systems Theory, June 15-17, 1983, pp 190-196. [8] Lee, C.S.G. and M. Ziegler, "A Geometric Approach in Solving the Inverse Kinematics of PUMA Robots," Proceedings of the 13th International Symposium on Industrial Robots, April 17-19, 1983, Chicago, Illinois, pp 16-1 to 16-18. [9] Lee, C.S.G., B.H. Lee, and R. Nigam, "Development of the Generalized d'Alembert Equations of Motion for Mechanical Manipulators," Proceedings of Annual Report 98 August 1, 1982 - July 31, 1983

the 22nd Conference on Decision and Control, Dec. 14-16 1983, San Antonio, Texas. [10] McClamroch, N.H., "Sampled Data Control of Large Space Structures Using Constant Gain Output Feedback: A Negative View", presented at 21st Conference on Decisions and Control, Orlando, Fla. Dec. 1982. [11] Shin, Kang G. and Neil D. McKay, "Minimum-Time Control of Robotic Manipulators with Geometric Path Constraints", to appear in Proc. 22nd CDC (to appear in December 1983). [12] Shin, Kang G., Richard A. Volz, and Vaclav Rajlich, "A Holistic Approach to the Design and Analysis of Versatile Robot Languages", Proc. COMIPSAC'83 (to appear in November 1983). [13] Whitesell, J. "A Modified Costate Variable in Optimal Control of Mechanisms" presented at the NATO-NSF Advanced Student Institute on "Computer Aided Analysis and Optimization of Mechanical System Dynamics. [14] Lee, C.S.G, "Adaptive Controller for Mechanical Manipulation" 15th Southwestern Symposium on System Theory" Huntsville, Ala., April 1983. [15] McClamroch, N.H., "Control of Structures using Electromechanical Actuators," Oakland, University, Rochester, MI, November 1982. Integrated Solid-State Sensors for Closed-Loop Robot Control [1] Park Y.E., and K.D. Wise, "An MOS Switch-Capacitor Read Amplifier for Capacitive Pressure Sensors," Proc. IEEE Custom IC Conf., pp. 380-384, May 1983. [2] Wise, K.D., "Distribution of Intelligence in Integrated Sensing Systems" 2nd Int. Conference on Solid-State Transducers" Delft, Netherlands, June 1983. Vision for Robots [1] De!p, E.J. and H. Chu, "Edge Detection'Using Contour Tracing," Presented at 20th Allerton Conference on Computers, Communications, and Control, October 1982. [2] Delp, E.J. and P.H. Eichel, "Estimating Motion Parameters from Local leasurements of Normal Velocity Components," Presented at 10th Allerton Conference on Computers, Communication, and Control, Oct. 1982. [3] Leith, E.N., "Incoherent optical processing methods," Presented at SPIE Symposium, Los Angeles, January 1983. [4] Mudge, T.N. and T.S. Abdel-Rahman "Case Study of a Program for the Recognition of Occluded Parts," Proceedings of the 2nd Annual IEEE Computer Society TWorkshop on Computer Architecture for Pattern Analysis and [Image Data Base Alanagement [5] Mudge, T.N. and T.S. Abdel-Rahman "Efficiency of Feature Dependent Algorithms for the Parallel Processing of Images," Proceedings of the International Conference on Parallel Processing, August 1983, 369-373. Annual Report 99 August 1, 1982 - July 31, 1983

Architecture of Robot-Based Manufacturing Cells [1] Volz, R.A., T.N. Mudge and D. Atkins "Hardware/Software Transparency in Robotics Through Object Level Design" Proceedings of the Society of Photooptical Instrumentation Engineers Technical Symposium West, SPIE, Vol 360, August, 1982., pp 216-223. [2] Volz, R.A., T.N. Mudge and D. Gal "Using Ada as a Robot System Programming Language", Proceedings of the 13th International Symposium on Robots and Robot 7 Conference, Chicago, April 1983 pp 12-42 —12-57. [3] Turney, J., T.N. Mudge, R. Volz, and M. Diamond "Experiments in Occluded Parts Recognition Using the Generalized Hough Transform," Conference on Artificial Intelligence, Oakland University, Michigan April 1983. [4] Volz, R.A., J. Wolter, and A.C. Woo, "Gripping Position for 3-D Objects," Industrial Applications Society Mleeting, San Francisco, October 1982. [5] Volz, R.A., "CAD Assisted Robot Programming and Ada" NATO Conference on Robotics and Artificial Intelligence, Barga, Italy, June 26-July 8, 1983. [6] Mudge, T.N., and J.L. Turney "Unifying Robot Arm Control;" Proceedings of the 1982 Annual AMIeeting of the Industry Applications Society, October 1982, pp 1315-1324. Also to appear in IEEE Transactions on Industry Applications. Metaform Database Interface System [1] Chiang, W.P. and T.J. Teorey, "A Method for Database Record Clustering," Pro. 3rd Int'l Conf. on Info. Systems, Ann Arbor, Michigan, Dec. 13-15, 1982, pp 57-73. 4.5. Technical Reports (Topics not covered in technical paper or conference only listed) Integrated Solid-State Sensors for Closed-Loop Robot Control [1] Chalhoub, N. and A.G. Ulsoy "Dynamic Simulation of a Flexible Robot Arm and Controller" Center for Robotics and Integrated Manufacturing Technical Report RSD-TR-13-83, College of Engineering, University of Michigan. September 1983. [2] Gilbert, E.G., "An Approach to Nonlinear Feedback Control with Applications to Robotics," Center for Robotics and Integrated Manufacturing Technical Report RSD-TR-4-83, College of Engineering, University of Michigan, September 1983. Presented at 1983 Conference on Information Sciences and Systems, The Johns Hopkins University (pp 612-618 of Proceedings). To be presented at the 1983 IEEE Conference on Decision and Control. [3] Lee, C.S.G. and S. Nemazie, "Pattern Recognition Methods for Force Recognition in Insertion Processes," Technical report, Center for Robotics and Integrated NMIanufacturing, the University of Michlgan. (in preparation) [4] McClamroch, N.H., "Sampled Data Control of Flexible Structures Using Constant Gain Velocity Feedback", to appear as CRIM report, accepted for Annual Report 100 August 1, 1982 - July 31, 1983

publication by AIAA J. Guidance, Control, Dynamics. [5] McClamroch, N.H., "Vibration Control of Flexible Structures using Electromechanical Transmission Type Actuators," to appear as CRIM report, submitted to AIAA J.Guidance, Control, Dynamics. [6] McClamroch, N.H., "Displacement Control of Flexible Structures using Electrohydraulic Servo Actuators," to appear as CRIM report, submitted to ASME J. Dynamic Systems, Measurement, Control. Annual Report 101 August 1, 1982 - July 31, 1983

Annual Report 102 August 1, 1982 - July 31, 1983

5. Personnel 5.1. Faculty There are many ways in which a faculty member or student may be supported by a contract of this type. The names listed on the form DD1473 include only those faculty who received direct salary support from the contract. However, in addition, some faculty received support indirectly through support of their graduate or post doctoral students. This section lists faculty who have either directly received support for a portion of their salaries or received support for one or more of their graduate students. Professors Daniel E. Atkins -- Electrical and Computer Engineering Milton A. Chace -- Mechanical Engineering and Applied Mechanics Gideon Frieder -- Computer and Communication Sciences Elmer G. Gilbert -- Aerospace Engineering Robert NM1. Howe -- Aerospace Engineering Keki B. Irani -- Electrical and Computer Engineering Yoram Koren -- Mechanical Engineering and Applied Mechanics Emmett N. Leith -- Electrical and Computer Engineering Arch W. Naylor -- Electrical and Computer Engineering N. Harris McClamroch -- Aerospace Engineering Richard A. Volz -- Electrical and Computer Engineering;Kensall D. Wise -- Electrical and Computer Engineering Associate Professors Ramesh Jain - Electrical and Computer Engineering Dev S. Kochhar -- Industrial and Operations Engineering Trevor N. Mudge -- Electrical and Computer Engineering Toby Teorey -- Electrical and Computer Engineering Anthony C. Woo -- Industrial and Operations Engineering — Assistant Professors Edward J. Delp -- Electrical and Computer Engineering C. S. George Lee -- Electrical and Computer Engineering (Kang G. Shin -- Electrical and Computer Engineering A. Galip Ulsoy -- Mechanical Engineering and Applied Mechanics Joseph Whitesell -- Mechanical Engineering and Applied Mechanics Mohamed Zarrugh -- Mechanical Engineering and Applied Mechanics Annual Report 103 August 1, 1982 - July 31, 1983

5.2. Students The number of students who have received support during the first year of the contract significantly exceeds the number of "standard" student appointments indicated in the proposal. There are two primary reasons for this. First, and most importantly, we were able to leverage the student funding to increase the student involvement. In number of cases we were able to obtain partial fellowship support for the student from internal funds, thus reducing the cost per student and increasing the number of students we could involve in the project. Similarly some students had partial outside fellowship support and only needed supplementary support to be able to participate in the project. The involvement of students with fellowship support in the project is deemed an acceptable activity since the work being performed is generally part of the student's dissertation work. Secondly, through natural attrition, graduation, and staff changeover, some replacement of the students supported occurred during the year. The students listed below, then, include all of the students who have received support during the contract year. T. S. Abdel-Rahman ECE1 Ph.D. expected 1984 Nirwan Ansari CICE2 M.S. expected 1983 Dean Askounis IOE3 MS 1982 Dan Barash IOE Ph.D. expected 1984 David V. Beard CICE Ph.D. expected 1984 Nabil Chalhoub ME&AM4 Ph.D. expected 1984 II Hyun Choi ECE Ph.D. expected 1984 Henry Chu CICE Ph.D. expected 1984-85 IKukjin Chun ECE Ph.D. expected 1985 Myrung J. Chung CICE Ph. D. degree expected 1983. Brian J. Dent ME&sAMI M.S. 1983. Paul Eichel CICE Ph.D. expected 1985 Mark Epstein CICE MS expected 1984 Paul Firehammer CICE MS expected 1984 David Gal CCS5 M.S. expected 1983 In-Joong Ha CICE Ph.D. expected 1984-5 Glenn Healey ECE B.S. expected 1984 H.P. Huang ECE Ph.D. expect 1985-86 Y-F Jeng Ph.D. ME&AM expected 1985 1Computer and Electrical Engineering Computer Information and Control Engineering 3industrial Operations Engineering 4Mechanical Engineering and Applied Mechanics SComputer and Communication Sciences Annual Report 104 August 1, 1982 - July 31, 1983

Charles Jerian CICE Ph.D. expected 1985 Richard Jungclas CICE Ph.D. expected 1985 Byung K. Kim Visiting scholar H-S Kim CICE Ph.D expected 1985 Jehkwan Lah ECE Ph.D. expected 1984 Bum. H. Lee, CICE Ph.D. expected 1984 M. Lee CCS Ph.D. expected 1986 Stacey Leon ECE M.S. expected 1983 D. McCubbrey ECE M.S. expected 1983 Neil D. McKay ECE Ph.D. expected 1984 Bernard Morgowitz Aerospace Engineering Ph.D expected 1984-5. Neil Nathanson CCS M.S. expected 1984 G. Quadah ECE Ph.D. expected 1983 Mubarak Shah CICE Ph.D expected 1985-86 Dong G. Shin CICE Ph.D. expected 1984 S-Y Shin IOE Ph.D expected 1985 M. Steigerwald ME&AM Ph.D. expected 1986 Gary Swanson Ph.D. Physics 1983 Reiko Tanese B.S. expected 1983 H-N Tong ECE BS expected 1983 Shi-Chen Tsang IOE M.S. expected 1983 Jan Wolter CICE Ph.D. expected 1985 S. I. Yoo CICE Ph.D. expected 1985-86 5.3. Degrees Awarded Dean Askounis M.S. in IOE 1982 Henry Chu M.S.in CICE 1983 M. J. Chung, Ph. D. in CICE 1983 Paul Eichel M.S. in CICE 1983 Brian Dent M.S. in MIE&AM 1.983 Stacey Leon M.S. in ECE 1983 Mfichael Steigerwald M.S. in ME&AM 1983 Gary Swanson Ph.D. Physics 1983 Jan Wolter M.S. in CICE 1983 Annual Report 105 August 1, 1982 - July 31, 1983

5.4. Permanent Staff Research Engineer John Caldwell Jerry Turney Sy.tems Progruatmcr Charles Lake Technician Rob Giles A dminist rative Ass istant Jerry L. Jackson Secretarie s Frances Bourdas Virginia Folsom Mary Ann Pruder Shirine Repucci Annual Report 108 August 1, 1982 - July 31, 1983

6. Coupling Activities An important aspect of a large viable program in manufacturing science is the presence of strong coupling activities both within and without the —program. Four categories of interaction are being pursued: * interaction among people participating in the project * interactions with other university scientific groups * interactions with industry * interactions with the Air Force As significant effort was expended during the first year in developing facilities and in project start up, less emphasis was placed on coupling activities than is planned for subsequent years of the project. Interaction with the Air Force and other units receiving AFOSR support, in particular, will be emphasized. The following sections describe the interactions which have taken place during the past year. 6.1. Intra Project Interactions Interactions among faculty, staff and students participating the program have occurred in several different forms: seminars, discussions and joint projects. A regular weekly seminar program provided a means of keeping everyone generally aware of other aspects of work on the project. Occasional speakers from other institutions provided a source of fresh viewpoints on important problems. This year the seminar program is being expanded to include biweekly seminars by outstanding researchers from around the country. Significant financial support is being provided jointly by the College of Engineering and the Industrial Technology Institute. Informal discussions take place on a continuing basis among a wide spectrum of participants in the program. This is particularly true among the graduate students and has led to cross fertilization of ideas. This form of interaction is expected to grow during the next year, and possibly be formalized to include regular discussions on topics of interest to subgroups within the project. As described in section 3, one of the long term goals of CRIM research is the development of intelligent robot system which can function in flexible manufacturing systems. To achieve this goal, these are several subgroups working on individual aspects of the problem, as depicted in Figure 3.1. While the interaction among the subgroups is far from being totally connected, there are a number of significant interactions. These are depicted in Figure 6.1. A detailed description of the nature of these interactions is distributed throughout section 3 of the report, and summarized briefly here. Interactions in the control, kinematics, dynamics and simulation areas have been primarily at the discussion level. These discussions have been quite important in framing some of the work performed, however, as there is a strong technical coupling between the areas. The interactions between the control and sensor areas has been at a higher level. To date, it has been primarily at a discussion level between those who will use the sensors and those who are developing them. As the sensors themselves become available during the next year of the project, the level of technical interaction will increase. Annual Report 107 August 1, 1982 - July 31, 1983

KinematlcT C ntro a Dynamics Figure.1 Technical interac i ama ution ps on the project. grammg ad CD ares re sng and moderately complex As escribe in secgress which will merge some of these subprojects into more global working units. The ri detrmin Visi Sensi ion training programming and Architectre are being built into a working system. The graphic programming of robots work Figure.1 Technical interactio on resoccluded part recognition thille project.ised in gramming and CAD areas are strong and moderately complex. As described in sections 3.3, 3.4 and 3.5, there are several subprojects which involve joint work among individuals into use the superiorre are some demonstration projects in yrogress which will merge some of these subprojects into more global working units. The grip determination work, simple vision training, programming and architecture work Annual Report 108 August 1, 1982 - July 31, 1983

Prof. Delp and his students, and will be coupled with the architecture and programming work through exploration of parallel structures for implementation. There are regular technical discussion meetings between members of these groups (several different subsets of the people involved) occurring on a weekly basis. These interactions will grow during subsequent work on the project as more of the technical results being achieved are integrated into composite working systems. 6.2. University Interactions Interactions with people from other universities have taken place at three levels, seminars by others at the University of Michigan, seminars by Michigan people at other universities and private technical discussions with people at other schools. Outside Seminar Speakers Among those presenting seminars at Michigan are: * Professor Donald W. Sweeney, School of Mechanical Engineering, Purdue University "Optical Sensors in Robotics Systems" * Professor Thom J. Hodgson - Industrial & Systems Engineering, University of Florida "A Combined Approach to Pallet Loading Problems * Mr. Steve Shafer, Carneige Mellon "Using Shadow in Finding Surface Orientations" * Dr. Peter Bier, Technical University of Berlin "An"Approach Towards Integrated Design and Manufacturing Systems" * Professor Y.H. Luh, Purdue University "Minimum Time Scheduling for Industrial Robots Along Cartesian Paths and Joint Trajectories" * Dr. Thomas S. Huang, Coordinate Science Lab "3-D Motion Estimation from Image Sequences" * Dr. Michael A. Melkanoff, Computer Sicence Department, University of California, Los Angles "CAD/CAM at UCLA" * Professor K.S. Fu, Electrical Engineering, Purdue University "A Step Towards Unification of Syntatic and Statistical Pattern Recognition" * Nam Suh from MIT, "Manufacturing Science" * John Tsotsos from University of Toronto "Motion Understanding" * Professor Azriel Rosenfeld, Computer Vision Lab, University of Maryland "Computer Vision" * Anthony Reeves, Cornell University "Massively Parallel Processor" Annual Report 109 August 1, 1982 - July 31, 1983

* Dr. Nils J. Nilsson Artificial Intelligence Center, SRI International, Menlo Park, California "Artificial Intelligence Research" The outside seminar program is being expanded substantially this year. A copy of the seminar schedule for the Fall term is attached in Appendix A. Seminars at other Universities given by Michigan faculty * Northwestern University - C.S.G. Lee "Adaptive Control for Robot Manipulators" * University of Rhode Island - C.S.G. Lee "Control and Force Feedback Control" * Sweden- R. Jain, "Dynamic Scene Analysis" * University of Massachusetts - N.H. McClamroch "Survey of Control Systems" Private Technical Discussions with Outside Faculty Numerous technical discussions have taken place with faculty and research students at other universities during the past year. These are identified here briefly: * D. E. Atkins met with R. Cannon and David Nitzen from Standford and SRI at an AFOSR sponsored project review meeting. * R. A. Volz had discussions at a NATO Advanced Studies Institute with: R. Nagel from Lehigh, L. IHarmon from Case Western Reserve, E. Freund from Germany (currently on sabatical at USC), J. Skrzypek from Northeastern, P. Davey from Science and Engineering Research Council, Great Briain, M. Raibert from Carnegie Mellon, M. Gini, M. Donath from Minnesota. * K. Shin and R. A. Volz participated in an NSF sponsored workshop on robotics and Computer Science 6.3. Interactions with Industry Interactions with industry have taken place in three forms, seminars presented to industry, private technical discussions, and acquisition of industrial funding for expanded projects. The latter is not directly part of the AFOSR sponsored activity, but is, nevertheless, positively influenced by the existence of AFOSR support and is therefore listed for reference. Seminars and Briefings for Industry Two industrial Affiliates reviews were held during the year. Each was a one day technical conference presenting recent research results to the affiliate members. Annual Report 110 August 1, 1982 - July 31, 1983

Appendix B contains the current membership list in the Affiliates. Major technical briefings were held at the University for the following firms: General Motors IBM Whirlpool United Technologies Northern Telecom Semiconductor Research Corp. Westinghouse Research General Electric & Development Center Gould Laboratories Weldon International Chrysler Corporation Volvo of America TRW Inc. Harris Corporation C.S. Draper Laboratory Michigan Bell Sperry Vickers * A. Galip Ulsoy presented an invited seminar entitled "Machine Tool Adaptive Control" at the Scientific Research Laboratory at Ford Motor Company during August 1983. Professor C.S.G. Lee gave the following tutorials on Robotics: Summer Conference Course At Michigan (chairman and organizer) August 1-5, 1983, July 19,23, 1982 COMPSAC 82 in Chicago (chairman and organizer) November 7, 1982 Orlando, Florida (chairman) April 5, 1983 Berlin, West Germany (chairman) April 11-13, 1983. IEEE Computer Society, Distinguished Visitor Program * Professor R. A. Volz presented the following seminars during the past year RIA Research Workshop "Manufacturing Cell Control and for Users Washington, D.C. Model Drive Vision" IBM - Kingston "Robotics Research at the University of M\ichigan" IBM-Boca Raton "Robotics Research at the University of Michigan" Intel "Robotics Research at the University of Michigan" AFOSR/DARPA "Robotics Research at the University of Michigan" ISA Chapter Midland "Robotics Research at the University of Michigan" Member of a panel on "Product Innovation: Robots and Automation," Product Development and Management Assoc. EMU/UM-IST. Annual Report 111 August 1, 1982 - July 31, 1983

* Professor T. N. Mudge presented an invited talk to: General Motors Research Labs, Warren, Michigan entitled "Parallel Processing and VLSI" * Professor N.H. McClamroch made presentations to: United Technologies Corporation entitled "Survey of control Systems" and to Sperry-Vickers, Troy, Michigan entitled "Identification and Adaptive Control". Seminars at Michigan by Industrial People Dr. Chi-Haur Wu, Unimation, "Robot Control" Dr. Michael A.Wesley, IBM "Geometric Modelling; the Link Between CAD and CAM" John Check, Raycon Corporation "Control Systems for Laser Applications in Flexible Manufacturing Systems". Dr. Hisaaki Hirabaryashi (H-itachi, Ltd.) "Robotics Research At Hitachi". Joseph Possinger, Bodo Dreisbach, Horst Becker and Reimer Hann Representatives from Siemens Corporation, Munich, Germany, "Research Work at Siemens". Private technical discussions with industry R. Volz, E. Delp, K. Chen, G. Lee, 1K. Shin, R. Jain held repeated discussions with I(MS Fusion on the use of robots for space applications. A. G. Ulsoy had discussions with researchers at Cincinnati Milacron related structural flexibility problems in robots. Hie also visited Caterpillar Tractor Company in E. Peoria, Illinois and discussed robotcs applications and adaptive control with the manufacturing development engineering staff. C.S.G Lee had discussions with Aerospace Corporation, General Motors Research Labs, and Ford Motor Company R.A. Volz met with Harris Corporation regarding computer requirements to support research activities. R. Jain meets regularly with General Motors regarding machine vision. New Industrial Contracts During the past year, the following team of people have received research support from the indicated industries: Profs. Stein and Ulsoy General Motors Profs. Volz and Mudge General Motors Annual Report 112 August 1, 1982 - July 31, 1983

Profs. Irani and Teorey General Motors Profs. Volz, Papalambros, Ulsoy, Woo IBM Profs. Delp and Jain IBM Prof. Woo Computer-Aided Manufacturing-International Prof. Whitesell Evans and Sutherland Computer Corporation 6.4. DoD Interaction Interactions between project personnel and Air Force personnel have not been at the level which would have been desired during the past year. It is hoped that this interaction will increase significantly in the future. The following interactions have taken place. D. Atkins and R. Volz met with Gordon Mayer and Mickey Hitchcock from Wright Patterson Air Force Base at the AFOSR sponsored review meeting. Mickey Hitchcock attended the Industrial Affiliates Review in May of 1983. Mickey Hitchcock attended a summer course in robotics at Michigan in August of 1983. Private correspondence and meetings between M. Hitchcock and R. Volz have taken place regarding the establishment of an in house robotics capability at WPAFB. Col. H. Winsor visited Michigan in August of 1983 for an informal project review. G. Lee visited the David Taylor Naval Ship Research and Development Center, Department of the Navy. R. Jain attended Navy Automated Manufacturing Research Workshop in Washington. Annual Report 113 August 1, 1982 - July 31, 1983

Annual Report 114 August 1, 1982 - July 31, 1983

7. Distribution List University and Research Institutes Professor Robert Cannon Dr. David Whitney Professor Thomas Binford Draper Laboratories Computer Science Dept. 555 Technology Square Stanford University Massachusetts Institute of Technology Stanford, CA 94305 Cambridge, MA 02139 Professor Robert McGhee Dr. David Nitzen Dept. of Electrical Engineering Director of Robotics Research Ohio State University Stanford Research Institute 2015 Neil Avenue 333 Ravenswood Avenue Columbus, OH 43210 Menlo Park, CA 94025 Professor Raj Reddy Dr. William Brown Computer Science Dept. & Robotics ERIM Carnegie Mellon Univesity P.O. Box 8618 Schenley Park Ann Arbor, MI 48107 Pittsburgh, PA 15213 Government Professor Nam Suh Professor Michael Brady Dr. James Albus 545 Technology Square Labs Room A127 Bldg 220 Massachusetts Institute of Technology National Bureau of Standards Cambridge, MA 02139 Washington D.C. 20234 Professor Richard Paul Dr. George Brosseau School of Electrical Engineering Room 1121 Purdue University NSF West Lafayette, IN 47907 Washington D.C. 20550 Professor Roger Nagel Mr. Norman Caplan Lehigh University Deputy Division Director Bethlehem, PA 18015 Division of Electrical, Computer & Systems Engineering Professor Georges Saridis NSF ECSE 1800 G. Street N.W. Rensselaer Polytechnical Institute Washington D.C. 20550 Troy, NY 12181 Mr. Bernie Chern Professor Delbert Tesar Division of Electrical, Computer & Dept. of NMechanical Engineering System Engineering University of Florida Room 1101 Gainsville, FL 32611 NSF W\ashington D.C. 20550 Annual Report 115 August 1, 1982 - July 31, 1983

Captain Robert Delyser Mr. Stelio DeMark DFEE ASEA U.S. Air Force Academy Industrial Robot Division Colorado 80840 16250 W. Glendale New Berlin, WI 53151 Dr. James Gault Electronics Division Mr. John Doddridge Dept. of the Army Dana Corporation U.S. Army Research Office Technical Center P.O. Box 12211 8000 Yankee Road Research Triangle Park, NC 27709 Ottawa Lake, MI 49267 Dr. Ernie Glauberson Mr. William Gauthier Dept. of Navy DeVilbiss Company Information Sciences Dept. Industrial Robot Operations Office of Naval Research 837 Airport Boulevard 800 N. Quincy Ann Arbor, MI 48104 Arlington, VA 22217 Mr. R. Gary Diaz Dr. Allen Rosenstein General Dynamics AFOSR Land Systems Division Dept. of the Air Force P.O. Box 1901 Air Force Office of Scientific Research Warren, MI 48090 Bolling Air Force Base Washington D.C. 20332 Mr. William Little General Electric Dr. Vincent Russo P.O. Box 17500 Mr. Micky Hitchcock Orlando, FL 32860-7500 Wright Patterson Air Force Base AFWAL/NLBE Mr. Steve Holland Wright Patterson, OH 45433 General Motors General Motors Research Laboratories Mr. William M. Spurgeon Warren, MI 48090 Program Director Production Research Mr. Donald A. McMillan Division of Mechanical Engineering & Helfrecht Machine Company Applied Mechanics 414 S. Hamilton Street NSF Saginaw, MI 48605 1800 G. Street N.W. Washington D.C. 20550 Mr. Pete Matheson Intel Corporation Industry 26500 Horthwestern Highway Southfield, MI 48075 Mr. Mike Gedeon Army Tank Automotive Command Mr. J.L. Escover DRSTA-ZCS Lockheed WVarren, MI 48090 Missiles and Space Company, Inc. P.O. Box 1700 Austin, TX 78760 Annual Report 116 August 1, 1982 - July 31, 1983

Mr. Richard Barron Northern Telecom Inc. P.O. Box 1222 Minneapolis, MN 55440 Mr. Dwight Carlson Perceptron 23920 Freeway Park Drive Farmington Hills, MI 48024 Mr. Clifford T. Anglewicz Volvo of America Corporation Volvo Automated Systems Division 40712 Brentwood Drive Sterling Heights, MI 48078 Dr. Gale Cutler Whlirlpool Monte Road Benton Harbor, MI 49022 Dr. James MacDonald IBM 1798 NW 40th Street Boca Raton, FL 33432 Dr. Michael Wesley IBM T.J. Watson Research Center P.O. Box 218 Yorktown Heights, NY 10598 Mr. William Hollenback IBM Neighborhood Rd. Kingston, NY 12401 Mr. James Lowrie Advanced Automation Technology Section Martin Marietta Aerospace P.O. Box 179 Denver, CO 80209 Honeywell, Inc. Annual Report 117 August 1, 1982 - July 31, 1983

APPENDIX A INDUSTRIAL TECHNOLOGY INSTITUTE AND CENTER FOR ROBOTICS AND INTEGRATED MANUFACTURING SEMINAR SERIES Chrysler Center Auditorium 2121 Bonisteel Blvd, Ann Arbor, MI 3:30 p.m. September 29 John E. Hopcroft Department of Computer Science Cornell University Mathematical Problems Arising in Robotics October 6 Russell Taylor Manager, Robot Systems & Technology Automation Research Department IBM Thomas J. Watson Research Center Automation Research at IBM October 20 David Alan Bourne Research Scientist The Robotics Institute Carnegie-Mellon University Computational View of Flexible Manufacturing Systems November 3 K.K. Wang Professor of Mechanical and Aerospace Engineering Cornell University Computer Aided Injection Molding System A-1

November 17 John G. Bollinger Dean, College of Engineering University of Wisconsin-Madison Automated CAD Programming of Commercial Robots December 1 Shimon Y. Nof Associate Professor of Industrial Engineering and Editor of forthcoming Handbook of Industrial Robots (published by John Wiley & Sons) New Tools for Planning Robotic Assembly Systems December 15 Leon D. Harmon Professor of Biomedical Engineering Case Western Reserve Touch Sensing for Robots A-2

APPENDIX B ROBOTICS INDUSTRIAL AFFILIATES MEMBERS Army Tank Automotive Command DRSTA-ZCS Warren, Michigan 48090 Company Contact: Mr. Mike Gedeon Telephone: (313) 574-5090 ASEA Industrial Robot Division 16250 W. Glendale New Berlin, W\isconsin 53151 Company Contact: Stelio DeMark General Manager Telephone: (414)785-3400 Dana Corporation Technical Center 8000 Yankee Road Ottawa Lake, Michigan 49267 Company Contact: John Doddridge Director of Technical Services Telephone: (313) 856-5111 DeVilbiss Company Industrial Robot Operations 837 Airport Boulevard Ann Arbor, Michigan 48104 Company Contact: Mr. William Gauthier Director Telephone: (313) 668-6765 General Dynamics Land Systems Division P.O. Box 1901 Warren, Michigan 48090 Company Contact: R. CGary Diaz Division Manager Telephone: (313) 362-0211, ext. 8096 B-l

General Electric P.O. Box 17500 Orlando, Florida 32860-7500 Company Contact: Mr. William Little Telephone: (305) 889-1200 General Motors General Motors Research Laboratories Warren, Michigan 48090 Company Contact: Steven W. Holland Asst. Head Computer Science Department Telephone: (313) Helfrecht Machine Company 414 So. Hamilton Street Saginaw, Michigan 48605 Company Contact: Donald A. McMillan, Sr. President Telephone: (616) 941-4200 Intel 26500 Northwestern Hwy. Southfield, Michigan 48075 Company Contact: Pete Matheson Telephone: (313) 353-0920 Lockheed Missiles and Space Company, Inc. 2124 East St. Elino Street Austin. Texas 78744 Mail to: P.O. Box 1700 Austin, Texas 78760 Company Contact: J. L. Escover Manufacturing Engineering MIanager Telephone: (512) 448-5555 Lockheed Missiles and Space Company, Inc. Dept. 61-01 Bldg. 577 North 1111 Lockheed Way Sunnyvale, California 91088 Company Contact: MNlr. S. C. DeBrock (University Liason) B-2

UNIVERSITY OF MICHIGAN 3 9015 02493 8386 Northern Telecom Inc. P.O. Box 1'222 Minneapolis, Minnesota 55440 Company Contact: Richard C. Barron Director, Manufacturing Telephone: (612) 932-8000 Perceptron 23920 Freeway Park Drive Farmington Hills, Michigan 48024 Company Contact: Mr. Dwight Carlson President Telephone: (313) 478-7710 Volvo of America Corporation Volvo Automated Systems Division 40712 Brentwood Drive Sterling Heights, Michigan 48078 Company Contact: Mr. Clifford T. Anglewicz General Manager Telephone: (313) 978-0234 Whirlpool The Elisah Gray II Research and Engineering Center Nlonte Road Berton Harbor, Michigan 40022 Company Contact: Dr. Gale Cutler Redmond Sage Gerald Eisenbrandt J.W. Adams B-3