COORDINATED RESEARCH IN ROBOTICS AND INTEGRATED MANUFACTURING ANNUAL REPORT August 1, 1983 - July 31, 1984 Co-Principal Investigators D. E. Atkins R. A. Volz Contract F49620-82-C-0089

SECURITY CLASSIFICATION OF THIS PAGE (When Data Entered) REPORT DOCUMENTATION PAGE READ INSTRUCTIONS REPORTRE DOCUENTAIONBBEFORE COMPLETING FORM 1. REPORT NUMBER 2. GOVT ACCESSION NO. 3. RECIPIENT'S CATALOG NUMBER 4. TITLE (and Subtitle) S. TYPE OF REPORT & PERIOD COVERED Interim COORDINATED RESEARCH in ROBOTICS and Aug. 1, 1983-July 31, 1984 INTEGRATED MANUFACTURING 6. PERFORMING ORG. REPORT NUMBER RSD-TR-12 -84 7. AUTHOR(a) 8. CONTRACT OR GRANT NUMBER(a) D.E. Atkins Co-principal Investigator F49620-82-C-0089 R.A. Volz Co-principal Investigator 9. PERFORMING ORGANIZATION NAME AND ADDRESS 10. PROGRAM ELEMENT. PROJECT, TASK ~~~College of Engineering -AREA & WORK UNIT NUMBERS College of Engineering The University of Michigan 61102F Ann Arbor, MI 48109 2306/A3 I. CONTROLLING OFFICE NAME AND ADDRESS 12. REPORT DATE USAF, AFSC _. October 30. 1984 Air Force Office of Scientific Research 13. NUMBER OF PAGES Building 410, Bolling AFB, D.C. 20332 14. MONITORING AGENCY NAME & ADDRESS(if 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 abetract entered in Block 20, if different from Report) Unlimited distribution 18. SUPPLEMENTARY NOTES 19. KEY WORDS (Continue on reveree aide i1 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 reveree aide if nece-eaay and Identify by blocI nambe) 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 high performance manipulators into flexible manufacturing cells. The following items have been accomplished during the past year. * The simulation of a 8 link robot has been ported to the AD-10 computer. Simulations faster than real time have been achieved, opening the way for possible ew studies in control al orithms. DO jN73 1473 EDITION OF 1 NOV 65 IS OBSOLETE -. c c: rATIrTu r-P TWin PAC(F (hUM, ne F.ntered.r'

SECURITY CLASSIFICATION OF THIS PAGtE(Whn Dat En tered) * The construction and modeling of a laboratory robot, including mechanisms by which the controller design and structural dynamics can interact (such as resonance, and parametric excitation due to inertial forces) together with a simulation have been completed. * General conditions for local closed loop stability of a cable driven manipulator have been obtained. * Conditions have been derived which relate the sampling times and feedback gains for which the closed loop flexible cable driven systems are stable. * Given a path in space, optimal control techniques have been applied to determine the optimum time history associated with movement along the given curve. * The path finding problem has been formulated as an optimal control problem with minimum distance constraints between the robot and obstacles, and conditions determined under which solutions exist. Two dimensional problems have been attempted and encouraging test results obtained. * Theoretical performance characteristics of capacitive based tactile sensing arrays have been calculated. Several 8x8 tactile arrays have been constructed in our laboratory. * Performance characterization of the 40 element thermal imagers developed during the previous year was completed. * A new sequential edge linking technique has been developed and compared with several other edge detection schemes. * It has been shown that by using axial motion stereo one can recover depth information from the scene. * The laser shutter technique for rapidly recovering surface maps has been developed to the point where it is ready for release to industry. * A coarse to fine sampling technique has been added to the salient boundary segment matching technique which has reduced significantly the number of attempted matches. e A technique has been developed for utilizing a grating interferometer for performing matched filtering operations on real object transparencies. * The graphic display subsystem of the graphical programming system for robots has been increased in speed by more than an order of magnitude. * A technique has been developed for optimally placing the microcode in microcoded special purpose processors. Significant improvements in operating speed have been obtained. * A simulation study of the active compliance control technique reported last year has been completed; preliminary results predict that the scheme should work well. * It has been shown that under suitable conditions simultaneous force (presuming a required contact between the end effector and a surface) and motion control can be achieved if a closed chain manipulator model is used. * The implementation of a basic experimental model driven system integrating a robot, vision system and CAD database via object oriented hardware (the Intel iPAX 432) and software (Ada) has been completed. * A preliminary study has been conducted on the analysis of communication requirements among different parts of a distributed sensor-based multi-robot system. * A heuristic problem solving technique developed during the first year of the contract was applied to a more real-life problem, the theorem proving problem. * A syntactic matching procedure was developed as an inference procedure which used the formatted structure of the knowledge expressed by Sigma-Horn formulae. * As an application, a front-end knowledge-based subsystem for the design of distributed database systems was described. * The logical design and formula analysis of the Metaform system was completed, including syntax and semantics of the form screen query and update language; algorithms for automatically generating form screens from entity-relationship database schemas were developed. SECURITY CLASSIFICATIOI OF tu'"c PAGE(Whan D — Entered)

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

EXECUTIVE SUMMARY ANNUAL REPORT ON COORDINATED RESEARCH IN ROBOTICS AND INTEGRATED MANUFACTURING THE UNIVERSITY OF MICHIGAN Background In August of 1982, the Air Force Office of Scientific Research awarded a contract to the Center for Robotics and Integrated Manufacturing (CRIM) at the University of Michigan as a "Center of Excellence" in manufacturing science. The work supported has been principally conducted in the Robot Systems Division of CRIM, with a relatively smaller level of effort being supported within the Management Systems Division. This is the second annual report on the research activities of CRIM which are supported research under this AFOSR contract. It should also be reported that there have been synergistic and leveraging effects of the contract, which, have gone far beyond the research directly supported. The award of this contract came at a time when the College of Engineering had made a commitment to focus its resources in certain key areas based upon its existing strengths and build world class research activities in these areas. The contract has been most helpful in indirect. as well as direct, ways in building toward these goals. The existence of this award played a role in the establishment of major research partnerships with industrial organizations such as General Motors, IBM, and General Dynamics. It has also helped us receive a major gift to assist in the establishment of a Computer Aided Engineering Network (CAEN), a prototype of the next generation distributed computing/communication environment. In the conviction that it is the "wave of the future", the College is also vigorously developing a powerful engineering computer workstation oriented environment for all of its students, faculty and staff; CAEN is the delivery mechanism for these workstations. Further, it has helped us in liaison activities with the Industrial Technology Institute (such as joint recruiting and a joint seminar series). These related accomplishments began to have a positive feedback on the AFOSR supported during this past year, and the effect will grow in the future. Overview of AFOSR Sponsored Component of CRIM In accord with original statement of work, the research program has been broadly oriented toward the understanding and development of intelligent, flexible manufacturing cells. The research topics being pursued range from highly sophisticated and accurate control algorithms for robot arm control, new types of sensors, analyst use of advanced sensor information, to higher level languages for robot control, integration of robot systems with CAD databases, development of shop floor oriented database interfaces, advanced distributed database techniques, and heuristic problem solving techniques. Figure E.1 shows how individual subproject areas relate to the overall project activity. This breadth of activity has been achieved through the participation of a substantial number of faculty supervising students in a wide range of areas. By mutual agreement, it was decided during the second year to develop a greater focus to the activities. While still a broad area, it was decided to focus on intelligent, model driven, sensor-based robots for discrete parts assembly and inspection. Within Annual Report i August 1, 1983-July 31, 1984

this area, greater attention will be given in the future to machine vision activities, model driven robot methodologies and path/trajectory planning techniques. and their integration in a manufacturing cell Second Year Activities The principal activities of the second year of the project can be classified into four categories: * There has been considerable progress in each of the research areas under investigation. * The research facilities available have seen continued growth during the past year, and plans have been laid for major new developments during the coming year. * An excellent well trained and mature support staff has been developed, together with a strong cadre of graduate research assistants. * Interaction and coupling activities have increased. The following sections will review these accomplishments briefly. Facility Development Our approach to research in sensors, robotics and manufacturing is heavily based upon experimental demonstration and simulation of the ideas developed. A strong laboratory environment is thus essential to the success of our endeavors. Of particular importance is the availability of adequate computational resources, both hardware and software, since advances in our areas of research are closely linked with the computa-'tional capabilities available. During the first year of the contract, we began the acquisition and installation of a substantial complement of robot, vision and computer equipment. Those installations have now been completed. The principal new developments during the contract year have arisen from industrial gifts. We have received an IBM 7565 robot which is now in active use within the Division, and the development of CAEN mentioned above will have a profound effect on the future of the laboratory. In particular, the laboratory will receive several Apollo workstations with a range of capabilities, with VAX 11/780 performance, and a bitmapped color display at the top end. Collectively, the workstations will be the equivalent of several VAX 11/780s in capability, thus more than doubling our computational capabilities. Furthermore, the color, bit-mapped display, and distributed computing capabilities of these systems will allow us to pursue areas of research which would previously have been difficult. Even though they have only been in operation in our laboratory for a few months, significant activities have been brought up on them. Furthermore, they have led to a sizable software gift from Structural Dynamics Research Corporation; SRDC has given us the GEOMOD solid geometric modeling package for use on the Apollo systems. August 1, 1983-July 31, 1984 ii Annual Report

Res earch Ac omplishmento The following paragraphs briefly overview the principal accomplishments in each of the major research areas. Simulation and Control of High-Performance Manipulatora This year of the project has seen the completion of some of the subprojects, the use of the results from some areas in others, and a shift in emphasis to activities essential for assembly operations. Specific research tasks investigated were the following: * Dynamic simulation of robots * Development of nonlinear decoupling theory for robot control * Analysis and control of manipulators with compliance and force constraints * Development of path/trajectory planning algorithms. Achievements during the second year include: * The simulation of a 6 link robot has been ported to the AD-10 computer. Simulations faster than real time have been achieved, opening the way for possible new studies in control algorithms. * The nonlinear systems decoupling work developed during the first year has been extended to include first order actuator dynamics. * The construction of a small laboratory robot for use in control studies has been com pleted. * The detailed model of the laboratory robot, including mechanisms by which the controller design and structural dynamics can interact (such as resonance, and parametric excitation due to inertial forces) together with a simulation have been completed. * General conditions for local closed loop stability of a cable driven manipulator have been obtained. * Conditions have been derived which relate the sampling times and feedback gains for which the closed loop flexible cable driven systems are stable. * Given a path in space, optimal control techniques have been applied to determine the optimum time history associated with movement along the given curve. From this, set points can be obtained for driving a control system. * The path finding problem has been formulated as an optimal control problem with minimum distance constraints between the robot and obstacles, and conditions determined under which solutions exist. Only two dimensional problems have been attempted thus far and, encouraging test results have been obtained. The method extends readily to 3-D. Annual Report iii August 1, 1983-July 31, 1984

Sensor and vision subaystems Among the many challenges confronting the realization of advanced robots, the need for improved sensor subsystems is one of the most critical. With increasing levels of automation, greater emphasis must be placed on sensor accuracy and reliability, as well as simple existence. Furthermore, great effort is yet required in analysis techniques for processing sensor derived data. Specific topics being investigated in sensor and vision subsystems include: * High performance tactile imagers * Silicon thermal imagers for process control or safety applications * High performance edge detection * Dynamic science analysis * 3-D surface reconstruction via vision * Optimal salient feature matching for (occluded) object recognition * Application of optical processing to robotic vision. Specific achievements during this reporting period are: * Theoretical performance characteristics of capacitive based tactile sensing arrays have been calculated. * Several 8x8 tactile arrays have been constructed in our laboratory and performance testing begun. * Performance characterization of the 40 element thermal imagers developed during the previous year was completed. * To improve performance a 32 element imager (16x2) has been designed and will be implemented during the next year. * A new sequential edge linking technique has been developed and compared with several other edge detection schemes. * Study of a new technique for recovering structure from motion in sequences of visual images using longer sequences of frames (not less than five and perhaps up to 30) has been begun. * It has been shown that by using axial motion stereo one can recover depth information from the scene. * The laser shutter technique for rapidly recovering surface maps has been developed to the point where it is ready for release to industry. * The optimal salient boundary segment matching technique has been installed on the interactive Apollo workstation for rapid development of vision algorithms. * A coarse to fine sampling technique has been added to the salient boundary segment matching technique which has reduced the number of attempted matches by an order of magnitude. Another modification to the routine has reduced the required storage for accumulator areas dramatically. * A technique has been developed for utilizing a grating interferometer for performing matched filtering operations on real object transparencies. August 1, 1983-July 31, 1984 iv Annual Report

Special purpose computers and languages The development of new sensors and sensor data processing techniques.bring with them the need for greatly increased computational capabilities of the robot systems upon which they will be installed. Both the hardware and software systems necessary to meet these requirements will have greatly increased complexity. Future systems will certainly use multi-processing, with a number of the processors being special purpose devices designed to achieve the needed processing speed, and the software systems necessary to operate these systems will be very large and complex in comparison to today's systems. To address these issues, the following topics are under investigation: * Special processors and microcoding techniques for robot systems * Graphical programming of robots * The use of object based (both hardware and software) computer systems for robotics. The accomplishments during the past project year include: * It has been shown that in the use of multiple subimage processors ( parallel computation) for feature dependent image processing (many common algorithms fall in this category) the most effective use of parallel processors best improves efficiency if the image is distributed among the processors in a manner which places approximately the same number of pixels of interest on each subimage processor. It is further shown that beyond a certain number of processors the distribution costs exceed the savings through parallel processing. * The graphic display subsystem of the graphical programming system for robots has been increased in speed by more than an order of magnitude. Several capabilities have been added to the system for more realistic object displays and selection of points in space. * A technique has been developed for optimally placing the microcode in microcoded special purpose processors. Significant improvements in operating speed have been obt ained. * The implementation of the multiprocessor object based system partially designed and implemented during the first year of the contract to test object based design concepts has been largely completed. The system consists of a vision system working in conjunction with an ASEA robot. The design has been significantly extended over initial design, and has been coupled to a CAD database. Sensor-based robot systems Once adequate sensors and sensing techniques have been developed there remains the problem of developing robot control techniques to effectively use the sensor information. This problem is particularly difficult when contact forces of one kind or another are involved. The work in this area has focused on joint force and motion control and the use of force cues in the insertion process. The work accomplished to date includes: * A simulation study of the active compliance control technique reported last year has been completed; preliminary results predict that the scheme should work well. Annual Report v August 1, 1983-July 31, 1984

* It has been shown that under suitable conditions simultaneous force (presuming a required contact between the end effector and a surface) and motion control can be achieved if a closed chain manipulator model is used. Robot-based manufacturing cell The ultimate goals of much of our research are to bring intelligence to sophisticated sensor-based robot systems. All of the sensors, sensing algorithms and controls described above are essential ingredients to achieving this goal. But, in addition there is a critical component of the research at a higher level. The activity at this level is a combination of systems integration, distributed computing system, planning and artificial intelligence research. Specific task areas being investigated include: e 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 past year include: * The implementation of a basic experimental model driven system integrating a robot. vision system and CAD database via object oriented hardware (the Intel iPAX 432) and software (Ada) has been completed. * Run-time interference testing between an object to be grasped and nearby obstacles has been partially completed. When completed this will be used to aid run time grip selection for automatically grasping objects. * Preliminary performance measurements on the experimental system have been made. While the performance of the system implemented is slower than would be desired in an industrial environment, there appears to be nothing intrinsic which would limit performance to that achieved with the current 432 system. Indeed, it appears that real time performance should be achievable. * The grip position criteria developed to date depend upon a constant pressure assumption which, in practice, will not be true. Studies of nonconstant pressure have been begun with the intent of ascertaining how good the constant pressure assumption is, and, possibly, determining better gripping algorithms. * A preliminary study has been begun on the analysis of communication requirements among different parts of a distributed sensor-based multi-robot system. Concepts of vertical and horizontal communication have been proposed for high speed and low speed communication, respectively. * The heuristic problem solving technique developed during the first year of the contract was applied to a more real-life problem, the theorem proving problem. * The tradeoffs between effilciency and complexity of the algorithm used to evaluate the heuristic function in the problem solving technique were investigated and a reasonable choice determined. August 1, 1983-July 31, 1984 vi Annual Report

Integrated factory information system The highest level of integration is in the area of factory database systems and integration across all levels of the factory, shop floor to business to design to management. Research at this level is directed towards distributed knowledge based systems and user interfaces to complex distributed manufacturing database systems. Among the results obtained this year are: * A syntactic matching procedure was developed as an inference procedure which used the formatted structure of the knowledge expressed by Sigma-Horn formulae. * As an application, a front-end knowledge-base subsystem for the design of distributed database systems was described. * The logical design and formal analysis of the Metaform system was completed, including syntax and semantics of the form screen query and update language; algorithms for automatically generating form screens from entity-relationship database schemas were developed. * Online human factors benchmarks of the metaform system were performed. * An experiment has been designed to investigate the human factors issues involved in the changeover from a paper based to a CRT based assembly parts broadcast system. Two databases have been developed to evaluate the human factors of the software and display design. Graduation, publication and staffing levels During the past year there has been a significant increase in the number of papers appearing in review journals while the number of papers presented at significant conferences has remained consistently high. Participation in national meetings and workshops has also remained about the same as the first year. The number of students supported by AFOSR funding decreased somewhat from the first year due to lower turnovers among students as project personnel stablized. There were fewer Ph.D. graduates than expected but a large number of doctoral students are expected to complete their degree requirements within the next six months. Summary statistics in the foregoing areas are as follows: * 35 papers presented at significant conferences * 8 papers appeared in review journals * 15 papers are currently under review or have been accepted for journal publication during the coming year. * participation in 23 national meetings and workshops * 1 Ph.D. graduate * 7 Ph.D. graduates expected within the next six months * 10 M.S. graduates.* Direct involvement of 33 students in AFOSR research projects. Annual Report vii August 1, 1983-July 31, 1984

ID the category of accomplishments that have been influenced by the AFOSR contract are the following: * 4 students have full or partial fellowship support from U.S. industry to work in our program. * 15 students who have at least partial internal fellowship support, their own support, or teaching assistant support are participating in our program. * 3 new members have been added to the Industrial Affiliates Program. * Major research support has been obtained from one industrial sponsor and additional major support obtained from a current industrial sponsor. August 1, 1983-July 31, 1984 viii Annual Report

TABLE OF CONTENTS 1. Introduction and Summary......................................................... 1 1. Introduction......................................................... 1 1.1 Organizational Advances......................................................... 1 1.2 Facilities..................................................................................................2 1.3 Interactions.............................................................................. 3 1.4 Research Activities.......................................................... 4 1.5 Report Organization.......................................................... 5 2. Facility Development.................................................... 7 2.1 Robotics Research Laboratory Facilities................................................ 7 2.2 Computer Aided Engineering Network(CAEN)..................................... 8 2.3 Construction Projects.......................................................... 9 3. Research Activities.................................................... 11 3.1 The Control of Mechanical Manipulators............................................... 11 3.1.1 Sim ulation......................................................................... 12 3.1.2 Application of Nonlinear System Theory to Mechanical M anipulators............................................................................... 14 3.1.3 Optimal Control Techniques to Enhance Robot Perform ance................................................................................ 15 3.1.3.1 Optimal Trajectory Planning......................................... 15 3.1.3.2 Optimal Path Planning in the Presence of O bstacles.......................................................................... 18 3.1.4 Adaptive Control..................................................... 21 3.1.5 Manipulator Compliance.............................................................. 21 3.1.5.1 Control of a Flexible Robot Arm.................................... 22 3.1.5.2 Control of Cable Actuated Manipulator........................ 24 3.1.5.3 Mathematical Aspects of Control of Flexible Systems..................................................... 25 3.1.5 Force Control of Manipulator................................. 26 3.1.6.1 Force Recognition in Peg-Hole Insertion Processes...................................... 27 Annual Report ix August 1, 1983-July 31, 1984

3.1.6.2 Motion and Force Control of the End Effector of a Manipulator in Contact with a Constraint.............. 34 3.1.7 Trajectory Planning, Obstacle Avoidance and Control of Two Co-operative Robots in an Assembly System................ 36 3.2 Integrated Solid-State Sensors for Closed-Loop Robot C ontrol................................................................................................... 39 3.2.1 A High-Performance Silicon Tactile Imager Based on a C apacitive Cell.......................................................................... 40 3.2.2 A Silicon-Based Thermal Imager......................................... 44 3.3 V ision for Robotics.................................................................................. 47 3.3.1 Edge Detection Using Contour Tracing....................................... 48 3.3.2 Using Extended Frame Sequences for Motion U nderstanding............................................................................ 50 3.3.3 Axial Motion Stereo.......................................................... 51 3.3.4 Rapid Surface Mapping................................................................ 53 3.3.5 Partially Occluded Part Recognition............................................ 54 3.3.6 Applications of Optical Processing to Robotic Vision.................. 59 3.3.7 On the Global Compaction of Microprograms............................. 62 3.3.8 Special Processors for Vision........................................................ 64 3.4 Architecture of Robot Based Manufacturing Cells............................... 68 3.4.1 Object Based Experimental Robot Cell........................................ 68 3.4.2 Status of Research Effort on Integrated Multi-Robot System s...................................................................................... 72 3.5 Improved Robot Programming.......................................................... 75 3.5.1 Automatic Determination of Gripping Positions.......................... 75 3.5.2 Off-line Training of Vision Systems and Stable Position M odeling..................................................................................... 81 3.5.3 Graphical Programming of Robots............................................... 84 3.6 Knowledge Representation...................................................................... 91 3.7 A Generalized Problem-Solving Process Using Heuristics...................... 92 3.8 Metaform Database Interface System..................................................... 93 3.9 User Needs for Information Display....................................................... 95 4. P ub lication s............................................................................................ 99 4.1 Journal Publication................................................................................. 99 4.2 U nder Review.......................................................................................... 100 4.3 In Preparation......................................................................................... 101 4.4 Conference Presentations........................................................................ 101 4.5 Technical Reports................................................................................... 104 August 1, 1983-July 31, 1984 x Annual Report

5. P erso n n el.................................................................................................. 107 5.1 Faculty................................................................. 107 5.2 Students......................................................... 108 5.3 Degrees Awarded................................................................. 109 5.4 Graduate Student Placement................................................................. 110 5.5 Permanent Staff...................................................................................... 110 6. Coupling Activities............................................................................... 113 6.1 Intra Project Interactions...................................................................... 113 6.2 University Interactions........................................................................... 113 6.3 Interactions with Industry..................................................................... 115 6.4 DoD Interaction...................................................................................... 117 7. Distribution List....................................................... 119 Annual Report xi August 1, 1983-July 31, 1984

August 1, 1983-July 31, 1984 xii Annual Report

ANNUAL REPORT ON COORDINATED RESEARCH IN ROBOTICS AND INTEGRATED MANUFACTURING THE UNIVERSITY OF MICHIGAN 1. Introduction 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. It is in this spirit that the work on this contract is being conducted. The original AFOSR directives were to support a very broad set of activities in robotics and manufacturing with an emphasis on providing graduate student support. This breadth of activity has been achieved through the participation of a substantial number of faculty supervising students in a wide range of areas. Although the activities supported have involved broad participation, an active seminar program and joint projects have kept all of the participants generally informed on the total project and subgroups intimately involved with each other's work. This past year has seen advancements on several fronts, organizational, technical, facilities, and interactions. Organizationally, we have been given the freedom to focus the research more, while retaining the broad interdisciplinary approach. Technically, several individual research subprojects have been brought together into working demonstration systems, and several new important areas of investigation opened. The installation of research facilities begun during the first year of the contract have been largely completed and augmented by other acquisitions from industry. And a major new seminar series was instituted with joint sponsorship of the Industrial Technology Institute. 1.1. Organizational Advances Organizationally, we have had much closer interaction with the sponsor this past year than we did during the first year of the contract. That interaction has been very helpful, both in terms of a better mutual understanding of objectives and capabilities, and in terms of the specific guidance given on the directions of our work. In particular, we were given the freedom to re-examine the specific projects being conducted and realign them to provide greater focus to the research. After carefully examining the research being conducted within our laboratory and the particular talents and skills available, we have selected the development of intelligent, model driven, aensor-based robot systems for assembly and inspection as the focus for our research. While this is still a broad goal, it is much more focussed than the original activity and provides the basis for substantial changes in the internal funding pattern. As a consequence of our efforts to focus more tightly the research activity, three areas will receive greater attention in our future activities. First, there will be greater emphasis on vision activities, particularly those involving motion of the objects being Annual Report 1 August 1, 1983-July 31, 1984

viewed, the camera, or both. Second, activities in model driven robot activities will be expanded. This involves work on grip planning, robot motion planning, and planning of sensor motions (e.g. how to move a camera to obtain a second or third view to provide a complete view of a scene). Third, a new activity in path planning involving a new and highly promising approach to the problem has been started. The beginnings of these activities will appear in this report, with more fully developed results appearing in future reports. 1.2. Facilities The Robotics Research Laboratory facilities have seen continued growth during this past year. The major computer installations begun during the first year have reached a major milestone toward their completion. The IBM 7565 robot system anticipated in last year's report has arrived, been installed and brought into active use in the Division. The Intel iAPX 432 system interface to an ASEA iRB6 robot, a GE TN2500 camera and an off-line CAD system has been completed and experiments in its use are under way. A major new factor in the capabilities of the Laboratory is the College of Engineering Computer Aided Engineering Network. This is a College wide network of powerful personal workstations of varying capacities. Large clusters of workstations are available to students on an open shop basis. Similar workstations are being placed in faculty offices and research laboratories in the College. All of these systems are in the process of being networked together. In the case of the Robotics Research Laboratory, a number of AFOSR SLUPPORTED TASK AREAS Soff HPshter-pfornce Special Purpose Ssyso nlanipulators: Computers & I. Sayst r tcture & Control Lige Sensor Basd Knowledge ~S~~~~Rotystems Proolwem n eeu Tam i|n l us r a."et Solving Rooot BaseOd not rmooruti urr vMarifacturng cell 1 fo prori Integratd Factory infomrmUticn System Figure 1.1 August 1, 1983-July 31, 1984 2 Annual Report

Apollo workstations are in the process of being installed. The first of these systems was placed on an operational basis just shortly before the end of the contract year. The Apollo systems figure heavily in our plans for future research in the laboratory. Two new construction projects were begun during the year, and a major project is planned for the next year based upon the Apollo workstations mentioned above. A light stripping camera system is nearly complete which will be used in some three dimensional vision studies. A number of the new vision studies being initiated are dependent upon multiple images with different spatial relations between the camera and the scene being viewed. To allow us to obtain our own data, a servo controlled camera system is being developed. The servo system will be operated under computer control. Finally, a major rapid prototyping vision system is planned, based around the Apollo workstations. This will involve interfacing cameras to the Apollo system (possibly in a variety of ways) and developing a broad base of software for the system. 1.3. Interactions There were two principal areas in which we concentrated on improved interactions. First, we had much closer contact with the sponsor, an interaction which has been very helpful in a number of ways. Second, joint with the Industrial Technology Institute, a The Robot's World Manipulators Algorithms/ Sensors Heuristics " _ Computing [ - Structuresors World Knowledge World Human Application Manufacturing Model Knowledge Knowledge Databases Figure 1.2 Annual Report 3 August 1, 1983-July 31, 1984

major bi-weekly seminar series was instituted which brought top ranked researchers from both industry and other universities to Michigan throughout the year. 1.4. Research Activities This project year was begun by continuing nearly all of the projects described in our previous annual report. The goals of the project were very broad based, encompassing research topics ranging from 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, integration of robot systems with CAD databases, development of shop floor oriented database interfaces and advanced distributed database techniques. Figure 1.1 shows how individual subproject areas relate to the overall project activity. Significant progress has been made in each of these areas. The accomplishments in each of the areas of Figure 1.1 are described in this report. In addition to the progress in the individual areas, however, this year has seen a significant linking of several individual projects to form a demonstration system illustrating a model driven robot system that for a class of tasks needs no reprogramming. The system includes a robot, a vision system, and a link to a CAD database, and performs a part sorting operation. For the class of parts which can be handled by the gripper on the robot, no reprogramming of either the vision system or robot is required. All information, other than the identity of the objects to be manipulated, is obtained from the AFOSR SUPOR TED TASK AREAS Senso High-Performance Secial Purpose Sensor Subsyst em Manipulators Computers Structure & Control Languages Sensor Based Compliant/ Problem | \ Constrained Motion..-:...:::./ Solving | \ Robot System CAD/CAE: Related Task, btx \ Robot Based /not supported undr Manacturing Cell AFOSR program for Assembly/lnspection Figure 1.3 August 1, 1983-July 31, 1984 4 Annual Report

CAD database describing the objects. During the latter part of the year, the activities supported were subjected to an internal review for their focus within the project. The view of the robot's world shown in Figure 1.2 evolved, and it was decided to narrow the focus of the project somewhat in order to better concentrate on the complex problems in this realm, where the application knowledge involved is restricted primarily to assembly and inspection. In order to make funding available for increased future emphasis in the areas shown in Figure 1.2, work not in these areas was phased out over the last three months of the contract year. This phaseout modifies the work areas of Figure 1.1 to those of Figure 1.3. Finally, the initial work on the contract has spawned several new tasks with external funding to extend activities which were begun on this project at a low level. 1.5. Report Organization Section 2 describes the additions and modifications to the computational and laboratory facilities available within the Division. Section 3 reviews all of the research activities supported 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 presented in Section 6. Annual Report 5 August 1, 1983-July 31, 1984

August 1, 1983-July 31, 1984 6 Annual Report

2. Facility Development The Robotics Research Laboratory facilities have seen continued growth during this past year. Most of the computer installations begun during the first year have been completed, new equipment has been obtained from industry, and several new local construction projects have been begun. Of particular importance to the future research work in the Laboratory is the beginning development of the College of Engineering Computer Aided Engineering Network, which is adding major facilities to the Laboratory and will allow network access to even greater facilities throughout the College. Section 2.1 will review the current status of the equipment in the Robotics Research Laboratory. Section 2.2 will describe the College of Engineering Computer Aided Engineering Network (CAEN) and its relation to the Robotics Research Laboratory. Section 2.3 then describes the local construction projects under way within the laboratory. 2.1. Robotics Research Laboratory Facilities Figure 2.1 shows the major equipment in the Robotics Research Laboratory and its relation to the other principal facilities used by researchers in the Laboratory. Three major additions have occurred during the past year, an IBM 7565 robot together with its Series I control computer, two Apollo workstations, and the Structural Dynamics Research Corporation (SDRC) GEOMOD solid modeling Computer Aided Design software package. The IBM robot is not currently used on AFOSR sponsored projects. It is, however, used on a closely allied project which was spawned by earlier work under AFOSR sponsorship. It is also likely that this system will be used in the future on AFOSR sponsored projects. The two Apollo nodes are the beginning of a sizable addition to the computing resources of the Laboratory. The DN600 is a full color system with hardware floating point, a bit mapped screen and has the processing power of a VAX 750. The DN420 is similar, but has only a black and white screen. These two systems will be replaced by a DN660 (which will be a color system with the processing power of a VAX 780), three DN320s and several DSP80 nodes during the fall of this year. The DSP80's are similar to the DN320's but have no keyboard or screen; they are intended to be used as device servers. In our system the DSP80's will be used to control interfaces to various laboratory equipment and to operate an ethernet interface which will allow fast communications to the VAX systems in the laboratory. In addition, there are two Apollo workstations which are shared between researchers in the Laboratory and other researchers in Mechanical and Industrial Engineering. The GEOMOD solid modeling package donated by SDRC gives us a badly need CAD modeling capability. Without this system, the development of object models to support the research projects was very expensive and therefore severely limited. The GEOMOD system currently runs on three of the Apollo workstations supporting the laboratory, and is being rapidly assimilated into the research projects. Annual Report 7 August 1, 1083-July 31, 1984

ROBOTICS RESEARCH LABORATORY Ts ~~:z':.-..-.^ -':.r^:..................... acrrrr ~ - -e\Aa- Sfi0 ^"" 1 Rt'"~~'S"t"'"" Ii...... /.~.~' I F. | rauo*! 0 An.-S Ra{3~l:,-:;:::*?: ----—:-.:..:-::.:..:. P.G. ccrrrI' t I' -YIIQIP UikYw~o~' Procemor o__.!j.'i.~'.*.V.V.Yi.'~:!.' ____............ Figure 2.1 2.2. Computer Aided Engineering Network (CAEN) The College of Engineering is making the integration of significant engineering computer workstations into all phases of its activities one of its top priorities. Funded by student fee assessments, open clusters of workstations have been placed in all areas of the campus frequented by engineering students. Any student registered in engineering may use the clusters for whatever purpose he/she wishes. All clusters are being integrated into the campus wide computer network which will provide access from any large gift from General Motors Corporation, workstations are also being provided to all major research laboratories in the College. In addition, each faculty member in the College has been given a sizable allocation of funds from which he/she may purchase a workstation for his/her office. Three levels of workstations are being acquired, as appropriate for each individual need, IBM XTs, Apple Lisas and Maclntoshs, and various levels of Apollo workstations. August 1, 1983-July 31, 1984 8 Annual Report

The College is dedicated to upgrading the CAEN as necessary to keep state-of-the-art workstations available to all faculty and students, and to make them available in sufficient quantity that computing resources are not a bottleneck for general student and research computations. The current goals are to have the top level workstations of the 4M category (Million instructions per second, Megabyte of memory, bit Mapped display, and Megabit per second communications). The development of CAEN is important to the Robotics activity in a number of ways. First, it will significantly add to the computational resources of the laboratory in a direct way. Second, since the research students supported under the contract will have access to workstations in the open clusters as well and these are being networked together, they will be able to extend the domain in which they do their computations far beyond the Robotics Research Laboratory and yet maintain communication with the facilities within the laboratory. Third, the support staff of the CAEN will be acquiring and developing a large set of generally useful software which will be readily available to the research laboratory, e.g. the TEK text processing system, graphics software, etc. 2.3. Construction Projects One of the principal activities to be emphasized in our future work is machine vision. Two new construction projects were begun during the year, and a major project is planned for the next year based upon the Apollo workstations, mentioned above, to support this area of research. Three dimensional information and multiple images with different spatial relations between the camera and the objects being viewed are critical types of sensor data required for several of the research projects in progress. To provide 3D data, a laser light stripping source is being built to work with one of our existing area CCD cameras. The camera output will be connected to a Colorado Video frame grabber, which is in turn attached to one of the VAX computers. A servo controlled camera system is being built to allow a variety of multiple image sequences to be obtained. The camera will be under the computer control of one of the VAX computers, and will be capable of movement in 6 dimensions. Initially, it is being built around the pair of PUMA robots. The project was started late in the contract year and is expected to be completed around the middle of the next contract year. The introduction of powerful workstations, such as the Apollo, with bit-mapped displays and much improved price/performance ratios over current midsized computers opens new potentials for machine vision systems. In order to explore these potentials, a new computer vision facility will be started during the next year based around the Apollo systems. Initially, one of our area CCD cameras will be interfaced to the Apollo system to provide data acquisition. Both multibus connection and possible direct infusion of the data into the screen buffer will be investigated. In conjunction with this, an extensive set of computer vision software will be developed on the Apollo systems. Our goal is to develop a rapid prototyping system for the development of new vision algorithms. Annual Report 9 August 1, 1983-July 31, 1984

August 1, 1983-July 31, 1984 10 Annual Report

3. Research Activities The research objectives during the past year were the development of new techniques and methodologies in robotics and manufacturing databases' to enhance the capabilities of a broad range of industrial production processes. In robotics, the activity focused on the development of intelligent sensored based robots whose operation is driven by data contained in CAD databases. Specific subprojects involve sophisticated robot control and simulation, new sensor development, techniques for several aspects of machine vision, special computer architectures for robotics, the use of CAD to drive robot operations, programming languages for robotics, and artificial intelligence problem driving techniques. The database research had two principal components, the distribution of the data itself across distributed nodes, and the development of tools to allow shop floor users to have easy to use access to the data they needed to perform their jobs. The following section describes the progress in each of these areas during the past year. 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 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 modeling and simulation: of robot arm kinematics and dynamics: different formulations of rigid-body equations, vibrational dynamics, discontinuous nonlinearities, actuators effects, 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, obstacle avoidance issues. * Adaptive control: feedback gain modifications, load sensing, process modeling and identification. * Mechanical compliance: characterization of the sources of mechanical compliance and control of their effects on manipulator motion control. Annual Report 11 August 1, 1983-July 31, 1984

* Manipulator force control: insertion tasks and associated force control issues; formulation of force control problems using surface constraints. 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. Hence, 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. The results presented by Professor Lee in the 1982-83 report indicate key developments made in this area which have provided a foundation for research in several other areas, as presented in this report. 3.1.1. Simulation Investigator: Professor R.M. Howe Research Objectives Effective simulation of robots is an extremely important factor in the design, 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 be 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 robot control system using feedforward control. Faster-than-real-time simulation permits predictive display of robot performance, which could play an important role in remote manipulators. Status of the Research During the period encompassed in this report considerable progress has been made in the programming of the AD-10 computer for simulation of a six-degree-of-freedom manipulator arm. At this time a complete simulation of the manipulator dynamics has been successfully executed on the AD-10 and is undergoing verification. The execution times realized are faster than real-time and provide considerable margin for inclusion of additional computations in a real-time environment. The simulation of manipulator dynamics can be broken down into four main components. In order of the realized AD-10 execution times, these are: (1) Computation of the position-dependent matrix characterizing the inertia of the manipulator. The algorithm mechanized for this purpose on the AD-10 closely follows that given by Orin and Walker. Its execution requires 424 #sec. (2) Evaluation of the torque at each joint. The Newton-Euler algorithm was selected and implemented for this purpose. A pass through the required computations takes 375 psec. (3) Solution for the acceleration at each joint based on the computed values of the inertial matrix and adjusted control torques. This part of the simulation proved to be most efficient when the problem of solving a system of simultaneous equations was formulated and mechanized as a set of interactive difference equations. Sufficient accuracy is realized after one iteration, and the execution time is 62 psec. August 1, 1983-July 31, 1984 12 Annual Report

(4) Implementation of a PD controller for the computation of command accelerations. This portion, comprised mainly of table look-up for the desired position, velocity, and acceleration values and error computations, takes 41 ptsec to execute. In addition to the modules described above, auxiliary modules were also mechanized to allow for dynamic branching in the simulation program. This dynamic program flow control feature permits the modeling of sampled data controllers as part of the simulation. For the nominal case where the system was modelled with a torque sampling period of 10 msec and 10 state evaluations per sample interval, the effective execution time per integration frame was found to be 0.904 msec. This allowed the overall simulation to run 1.1 times faster than real-time. With the number of state evaluations reduced to 2 per sample interval, the fidelity of the simulation was found not to be reduced and solution speeds 5 times faster than real-time were realized. As a way of determining an upper bound on the speed with which the AD-10 simulation can be performed a continuous model of the system was also evaluated. With this modification the speed for the execution time per integration frame was found to be 1.30 msec and speeds up to 10 times faster than real-time were realized before deterioration of the quality of the solution occurred. Future Research A complete simulation using the AD-10 computer is currently being verified against results obtained from a nonreal-time simulation developed during the initial phase of this research and running on a PDP-11/34 computer. Comparisons made to date show very good agreement. The availability of a variety of numerical integration algorithms on the AD-10 are currently being used to evaluate the accuracy and efficiency attainable with these algorithms in the context of the six-degree-of-freedom manipulator simulation. Work has also begun on augmenting the AD-10 simulation program with graphics to enhance its data display capability. This effort will make possible a visual display of a simplified line segment replica of a manipulator undergoing the maneuver being simulated. Also planned as part of this enhancement is a simultaneous display of a set of keyboard selected simulation variables. After verification, the current model will be supplemented with a model of the dynamics associated with joint actuators. This will include a representation of the servomechanism dynamics and a model of nonlinear friction at each of the manipulator joints. It is also anticipated that simulation of lightly damped structural modes will become part of the overall model. Both the friction and structural mode models have been demonstrated on the AD-10. Their addition to the simulation will permit a detailed evaluation of the control algorithms being proposed for applications in robotics and control of flexible structures. Annual ReDort 13 August 1. 1983-July 31. 1984

3.1.2. Application of Nonlinear System Theory. To Mechanical Manipulators Investigator: Professor E.G. Gilbert Research Objective The research objective is to study the application of nonlinear feedback theory to the control of mechanical manipulators. Status of Research The research is being carried out with I.J. Ha, who is a doctoral student in the Computer, Information and Control Engineering program. As described in last year's report, the theory of nonlinear decoupling leads to a deeper understanding of what can be done with the nonlinear feedback control of multivariable systems and the fact that this understanding sheds light on manipulator control. The theoretical results of last year have been extended and now seem complete. In addition, the theory has now been applied to very general models of manipulator dynamics including first order actuator dynamics as reported in the recent conference paper by H. Nijmeijer[l]. For higher order actuator dynamics little progress has been made. This and the general complexity of the theory has led to an investigation of approximate decoupling. All of this research is being prepared in dissertation form by I.J. Ha. It is expected that it will lead to several journal articles. The paper [2], which is the result of work reported last year, sets up a method by which nonlinear feedback can be used to produce on-line end-effector tracking. For more specialized situations some authors (J. Slotine and S. Sastry, C. Sampson[3-4]) have proposed schemes, utilizing nonlinear controllers, which are robust in the sense that acceptable tracking control may still be achieved in the presence of significant plant modeling errors. A different approach to this type of control has been investigated. It starts with a more general model, which includes the one treated in [2]. Two concepts are used: the transformation, by feedback, of the nonlinear system to a linear system, and the idea of robust control introduced by M.Corless and G. Leitman[5]. When applied to manipulator control, the approach gives different and more general results than obtained by the previously mentioned authors. A paper describing the work is presently being completed [6]. Future Research The work described will be completed and papers and reports will be prepared. Based on some ideas of N.H. McClamroch for linear systems, I.J. Ha has developed a nonlinear observer for implementing feedback control of manipulators when the information of system state is incomplete. He, McClamroch and Gilbert will explore the idea further in the coming months. References [1] Nijmeijer, H., "Noninteracting Control of Nonlinear Systems," IEEE Conference on Decision and Control, San Antonio, December 1983. [2] Gilbert, E.G. and I.J. Ha, "An Approach to Nonlinear Feedback Control with Applications to Robotics," IEEE Transactions on Systems, Man, and Cybernetics, Vol SMC-14, August 1984. August 1, 1983-July 31, 1984 14 Annual Report

[3] Slotine, J.J. and S.S. Sastry, "Tracking control of nonlinear systems using sliding surfaces with application to robot manipulators," Int. J. Control, Vol. 38, pp. 465492, 1983. [4] Sampson, C., "Robust nonlinear control of robotic manipulators," Proc. IEEE Conf. on Decision Control, 1983. [5] Corless, M.J. and G. Leitmann, "Continuous state feedback guaranteeing uniform ultimate boundedness for uncertain dynamic systems," IEEE Trans. Automat. Control, Vol. AC-26, pp. 1139-1144, 1981. [6] Gilbert, E.G. and I.J. Ha, "Robust Tracking in Nonlinear Systems and Its Application to Robotics," RSD-TR-11-84, Center for Robotics and Integrated Manufacturing, University of Michigan, Ann Arbor, Michigan, September 1984. 3.1.3. Optimal Control Techniques to Enhance Robot Performance Research Objectives 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 motion of the robot arm, minimum energy consumption, or distance of the path from obstacles. Furthermore, there is recent evidence that an optimal control approach with minimum distance constraints between elements of the robot arm and obstacles may provide an effective means of path planning, which is usually approached purely geometrically and causes severe difficulties for more than two dimensions. The objectives in these areas are to determine effective methods for path and trajectory determination. Two aspects of the problem are being investigated. In the first, it is assumed that a curve in space (the path) is known a priori and the time history of movement along that path and the nominal control to minimize an appropriate cost function is sought. In the second, the path itself is sought as well. 3.1.3.1. Optimal Trajectory Planning Investigator: Professor K.G. Shin Status of the Research The 1982-83 annual report described a method of trajectory planning called the phase plane method, which used phase plane plots to generate a set of joint torques which would drive a robot along a given spatial path in minimum time[l]-[3]. This method has two drawbacks. First, it works only for minimum-time trajectory planning. If, for example, it is desired that energy be penalized as well as time, then the phase plane method does not apply. Second, if the robot's actuators interact, then the method will not work either. To correct these deficiencies, dynamic programming has been Annual Report 15 August 1, 1983-July 31, 1984

investigated as an alternative method of generating optimal phase plane trajectories. Separately from the above activities, we also have taken a different approach to the path planning problem, which is based on traditional nonlinear programming methods. TUnder moderate assumptions, we obtained path solutions with accuracy and computational efficiency. Dynamic Programming Approach: Dynamic programming is difficult to apply to robot path planning if the path is unspecified. Since most practical robots have five or six joints, and the state of the robot must be described by a position and velocity for each joint, the dynamic programming algorithm would have to be applied in a ten or twelve dimensional space, and one encounters the classic "curse of dimensionality" problem. If, however, the geometric path of the robot is specified in advance, then the robot's state can be described in terms of two quantities, the position of the robot on the path and the velocity along the path. The problem of finding an optimal set of velocities/accelerations/torques then becomes essentially two-dimensional regardless of the number of joints of the robot. Dynamic programming can then be applied with relative ease. Application of dynamic programming to the trajectory planning problem requires three steps: 1) discretization of the dynamic equations of the robot, 2) development of appropriate methods for connecting the points of the dynamic programming grid and updating the cost functions, 3) the generalization of the algorithm to handle joint torque limits. The first step, discretization of the dynamic equations, is straightforward. Deciding how to connect the points of the dynamic programming grid would appear to be a more difficult question. It has been shown, however, that as long as the connecting curves are smooth and monotonic the results will be the same in the limit as the dynamic programming grid becomes successively finer. With this result in mind, the curves were chosen to be curves of constant acceleration, since these curves make the mathematics particularly simple. The third problem, that of generalizing the algorithm to work with interacting joint actuators, also would appear to be fairly difficult. However, under certain reasonable conditions the interacting joint case can be handled in much the same way as the non-interacting case. The results obtained using the dynamic programming method have been tested on a simple two-degree-of-freedom robot, and results have been compared to those obtained by the phase plane method. The dynamic programming method gives results which are in good agreement with the phase plane method in those situations where the phase plane method is applicable. In other situations, such as when the objective function is something other than minimum time, the results are reasonable. See [4] for a detailed description of this work. Nonlinear Programming Approach: As an alternative to the above, we have developed a minimum-time path planning method in joint space including bounds on the prescribed path, i.e. a channel about the prescribed path which reflects the acceptable set of paths as well as the robot arm dynamics and other realistic constraints. This is a more realistic assumption then the August 1, 1983-July 31, 1984 18 Annual Report

previous single prescribed path. This method determines a minimum time traveling path in joint space that a robotic manipulator follows within the prescribed path deviation bounds subject to the limits on joint angular velocities as well as on joint torques/forces. The addition of possible deviations from a single prescribed path turns the problem into a complex nonlinear programming problem. We have solved the nonlinear programming problem efficiently by decomposing the global optimization problem into a set of local optimization problems -- one at each corner point in the given path - under the following assumption: each path segment consists of three parts; acceleration, cruise, and deceleration. Note that we are concerned only with gross motion planning for which the assumption is valid. If fine motion planning is the subject of concern, there are more important problems to be solved than the minimum-time path, e.g. compliant control, collision avoidance. The main differences between this method and others are that: (i) an absolute tolerance in the path deviation at each corner point can be specified, thus expressing the manufacturing reality more accurately and clearly than would be the case with implicit bounds (e.g. a fraction of a given path segment [7]), (ii) local upper bounds on joint accelerations are derived from the arm dynamics so as to almost fully utilize the robot's capabilities and eliminate the need for additional validation/modification of the planned path, and (iii) a set of local minimum-time path planning (LMTPP) problems - one at every local corner point -- are employed to replace the global minimum-time path planning (GMTPP) problem. As a demonstration example, we have applied the method to the path planning of the first three joints of the Unimation PUMA 600 series robot arm using a simulator on a VAX-11/780. The example has shown significant improvement in the total travel time in addition to the ease and simplicity obtained from the decomposition of the global problem into a set of local optimization problems. See [5], [6] for more on this alternative method. Future Research In order to make the trajectory planning results useful, the robot's controllers must be able to supply the torques requested by the trajectory planner. In the case of minimum-time paths, one joint of the robot is always driven at its maximum capability. If the dynamics of the robot are not exactly as modeled, then the requested torque may be inadequate. However, the controller will not be able to accommodate these changes, since the robot is already being driven at its maximum capabilities. One way to avoid this problem is to use restricted or conservative torque limits when doing trajectory planning. Then, if the controllers decide that more torque is required to keep the robot on the desired path, there is some "surplus" torque available to do it. This naturally gives rise to the question of how much to restrict the torques used at the trajectory planning stage. Since the largest variations in the dynamic characteristics of the robot will almost certainly be due to payload variations, the question becomes that of determining how the dynamic equations vary as the payload varies. NWork on this is in the preliminary stages; the eventual goal is to be able, given the characteristics of a grasped part, to determine which of a set of dynamic equations and torque bounds should be used during trajectory planning. It should be possible to perform the task of computing sets of dynamic equations and joint torques only once for a given robot and range of payload characteristics. Current work is aimed toward Annual Report 17 August 1, 1983-July 31, 1984

computation of torque errors from errors in the inertia tensors of grasped objects. Additionally, a computer program for generating trajectory planners is under construction and should be finished during the next year. This system will take as input a description of the robot's links and actuators, generate the robot's dynamic equations, and generate a trajectory planner of either the phase plane or the dynamic programming type. References [1] Shin, K.G. and N.D. McKay, "An Efficient Robot Arm Control Under Geometric Path Constraints," Proc. 22nd Conf. on Decisiion and Control, San Antonio, TX, pp. 1449-1457, December 1983. [2] Shin, K.G. and N.D. McKay, "Minimum-Time Control of Robotic Manipulators with Geometric Path Constraints," (with N. D. Mckay) accepted as a regular paper to IEEE Trans. on Automatic Control. [3] Shin, K.G. and N.D. McKay, "Open-Loop Minimum-Time Control of Mechanical Manipulators and Its Application," Proc. 1984 American Control Conference [4] Shin, K.G. and N.D. McKay, "Robot Path Planning Using Dynamic Programming," accepted for presentation at 23rd CDC. [5] Kim, B.K. and K.G. Shin, "An Efficient Minimum-Time Robot Path Planning under Realistic Conditions," Proc. 1984 American Control Conference [6] Shin, K.G. and N.D. McKay, "Minimum-Time Path Planning for Robot Arms with Their Dynamics Included," accepted subject to a minor revision to IEEE Trans. on System, Man, and Cybernetics. [7] Luh, J.Y.S. and C.S. Lin, "Optimum path planning for mechanical manipulators," Trans.ASME J. Dynamic Syst., Meas., Contr., vol. 102, pp. 142-151, June 1981. 3.1.3.2. Optimal Path Planning in the Presence of Obstacles Investigator: Professor E.G. Gilbert Research Objective The research objective is to develop a general computational methodology for offline determination of optimal robot motion in the presence of obstacles. The formulation takes into account: the dynamics of the robotic mechanism, constraints on actuator effort, suitable measures of performance such as energy expended by actuators or time of travel, general descriptions of initial and terminal positions and velocities (e.g., the interception of a moving object), and the avoidance of collisions between the parts of the mechanism and its surrounding spatial environment. This research is being carried out jointly with D.W. Johnson, who is a doctoral student in the Department of Aerospace Engineering. Status of the Research Last year it was shown that the path planning problem could be stated as a problem in optimal control. The obstacle avoidance constraints appear in the form of statevariable inequality constraints involving the distances between potentially colliding parts making up the structure of both the mechanism and the environment. It was proposed August 1, 1983-July 31, 1984 18 Annual Report

o X 00 2.00 4.00 I.00. 00 l'0- 12. 00 14.00 1. 00 18.00 20.00 X-AXIS Figure 3.1.3.2.1 The minimum energy path for a three-degree-of-freedom cartesian manipulator. that the optimal control problem be solved by penalty function methods, using spline functions to represent the time-dependent configuration variables. With this as a starting point good progress has been made this year. First, the distance between a pair of elemental parts as a function of their position and orientation was investigated. These functions have certain mathematical properties which are now fully characterized. In particular, the distance functions are continuously differentiable only if the parts have special shape properties (e.g., strict convexity). Differentability is important because it simplifies the application of descent algorithms to the solution of the optimal control problem. In addition, efficient methods for evaluating both the distance functions and their gradients for a variety of elemental shapes have been devised. Another related subject is the representation of complex shapes by a union of suitable elemental shapes. It should be emphasized that the full generality of the results on distance functions does not depend on the dimension of the object space. Thus, unlike other approaches to obstacle avoidance, the theory does not encounter difficulties when applied to objects in three-dimensional space. It should be noted that the theory of distance functions may also be useful in on-line collision avoidance schemes Second, the original problem statement and the penalty function approach were h refined. The revision was influenced by the distance function results and further thoughts about computational details. Annual Report 19 Augut 1, 1983-July 31, 1984 Ths, nieohrapoce oosal viacteter osnecutrdfi cliswhnapidtobetintr-dmninlsaeItsolbentdttte s uhsthsprpsdy.Kail]

Third, attention has been given to computational issues associated with the approach. Last year, an efficient scheme for computing the inertial matrix was obtained, but the derivation of the formulas was quite complex. This year a simpler derivation has been found. Moreover, a careful collecting of terms eliminates redundancy and yields recursive forms. A new and more difficult task is the computation of partial derivatives of the inertial matrix and of the gravitational, coriolis and centrifugal terms. Good progress has been made on this task. Finally, a major effort has involved the solution of some example problems. A computer program has been developed to test the basic ideas. It applies to a threedegree-of-freedom cartesian manipulator working in two-space and allows for some generality in specifying the work space, the type of integration procedures, the form of the penalty function, and other factors. From many numerical experiments a number of things have been learned. The penalty function approach seems to work reasonably well and the minimization algorithm converges reliably. The greatest difficulty has been the need for a fine time grid in the integration of the penalty function. Without it "collisions" occur between the grid points. Since the computation time grows with the number of grid points, methods have been arranged to compute only those obstacle distances which indicate near collisions. The preliminary results appear promising. Figure 3.1.3.2.1 shows a minimum energy path where the spline space has dimension 117 and the time grid has 320 subintervals. As might be expected, the solution is computationally expensive, taking approximately 18 minutes on a Harris 800 computer. The work to date appears in three reports. The conference paper [2] describes the problem formulation and underlying theory; the numerical results are preliminary. The report [3] gives, in addition, recent computation results. The conference paper [4] summarizes the results in [3]. a Future Research Many questions need further exploration. Some of the topics to be considered in the coming year include: new procedures for avoiding excessively small grid sizes, extension of the present computer program to solve minimum arc length and minimum time problems, the generation of admissible starting trajectories when the obstacle constraints are tight, the consideration of more complex mechanisms including manipulators in three space, the use of simplified dynamic models which insure that physical constraints are met and near optimal costs are achieved. It appears that task planning problems being considered by R.A. Volz and A.C. Woo may yield interesting applications of the work. Journal papers will be prepared. References [1] Khatib, O., "Dynamic Control of Manipulation in Operational Space," IFTOMM Congress on Theory of Machines Mechanisms, New Delhi, December 1983. [2] Gilbert, E.G. and D.W. Johnson, "Distance Functions and Their Applications to Robot Path Planning in the Presence of Obstacles," Proceedings of the 1984 Conference on Information Sciences and Systems, Princeton University, May 1984. [3] Gilbert, E.G. and D.W. Johnson, "Distance Functions and Their Applications to Robot Planning in the Presence of Obstacles," RSD-TR-7-84, Center for Robotics and Integrated Manufacturing, The University of Michigan, July 1984. August 1, 1983-July 31, 1984 20 Annual Report

[4] Gilbert, E.G. and D.W. Johnson, "Distance Functions and Their Applications to Robot Path Planning in the Presence of Obstacles," To be presented at the 1984 Conference on Decision and Control. 3.1.4. Adaptive Control 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 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. Status of the Research The results presented in the 1982-83 report indicate a completed set of research developments. The results presented there have provided a framework for application to other areas, as presented in this report. In particular, the notion of resolved motion adaptive control has been extended and applied to the control of two cooperative robots; the status of this research is indicated in Section 3.1.8 of this report. 3.1.5. Manipulator Compliance 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: * Link flexibility: this is due to the elasticity of the components of the robot arm structure. * 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. * 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. Annual Report 21 August 1, 1983-July 31, 1984

3.1.5.1. Control of a Flexible Robot Arm Investigator: Professor A.G. Ulsoy Ideally robots should have a lightweight yet rigid structure to meet the high performance requirements of demanding industrial applications such as the manufacture and assembly of precision parts. Applications requiring high speed and high accuracy of the robot arm require consideration of link flexibility effects in the mechanical design of the robot arm as well as in the design of the controller. The objective of this research project is to investigate the influence of link flexibility on performance, and to consider methods to improve the performance of flexible robot arms through the controller design. Status of the Research 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 three-degrees-of-freedom spherical coordinate laboratory robot is being used as the focus of this study where two-degrees-of-freedom are driven by leadscrews and the third is driven by a gear train. A dynamic model of the robot, including the effects of the flexibility of the final link and the transmission mechanism constraints, is being formulated as the basis for analytical and simulation studies. In the mathematical model, the leadscrew is assumed to be a self-locking drive. Such a drive, one which is not backdriveable, does not completely eliminate the interaction between rigid and flexible motions. This behavior arises from the axial force exerted on the leadscrew. The axial force would include, in general, gravitational and inertial terms due to the combined rigid and flexible motions. Therefore, to be consistent with the self locking assumption, in the absence of the control torque or force, the axial load, regardless of its magnitude. would not cause the leadscrew to rotate. However, the control torque supa plied by the actuator must still overcome the loading torque induced by the axial force. A detailed model of the leadscrew and its housing have been added to the dynamic model of the robot to simulate the nonbackdriveable behavior. This simulation is used to investigate the interrelationships between the robot structural flexibility and the controller design. 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 and the transmission mechanism constraints, have been completed. Also completed is a review of the literature on control of flexible robot arms. The modeling and simulation study describes and demonstrates several potential mechanisms by which the structural dynamics and controller design can interact. These include resonance, parametric excitation due to inertial forces, and the effects of constraints due to transmission mechanisms such as leadscrews. The simulation results are discussed in the paper (1], and for a detailed discussion, the reader is referred to the related technical report [2] and this study has led to a better understanding of the interaction between the structural design and controller design for robot arms. The controller design employed here, which is typical of current industrial practice, can be improved significantly by including the effect of the flexible motion in the control action. This can be done in three ways: August 1, 1983-July 31, 1984 22 Annual Report

(1) Design a controller based on a detailed dynamic model of the manipulator which includes the effect of flexibility. This is the simplest approach but has many drawbacks. The dynamic model would be very complex even for low order beam models. Any discrepancy in the dynamic model or disturbances in the system would considerably affect the overall performance of the robot, since no actual measurements are being fed back to the controller. In other words, the robot would behave as an open loop system as far as the flexible motion is concerned. This approach requires only software modifications. (2) A full kinematic state measurement at the end point of the robot arm is fed back to the controller. The latter activates the actuators at the joints to correct for the malpositioning of the end-effector. This approach compensates for the inaccuracy of the dynamic model as well as for any disturbances in the system. It does not require any additional actuators. The major drawback of this method is the difficulty of obtaining accurate measurements of the position and orientation of the end effector over a large operation volume. The controller design is also complex, and will require careful study. (3) Another approach is to sense and correct the flexible motion by using additional sensors and actuators. This is expected to improve the robot performance over the previous two controller designs, but at greater cost and complexity. This third approach is basically the micro-manipulator system that is being studied by Cannon and his co-workers at Stanford [3,4]. The construction of a small spherical coordinate laboratory robot is complete. Three DC servo motors driven by power amplifiers are used as actuators. The control torques are transmitted to the links using leadscrews and a gear train. One tachometer generator and one encoder are mounted on each link to measure its position and velocity. The encoder signals are read by the computer through digital counters. Each joint has a different number of counters associated with it according to their range. The contents of any counter can be strobed into a tri-state buffer. This buffer can be accessed by the computer through differential drivers. Differential receivers are also used for the same purpose on the control lines originating with the microcomputer which is an IBM PC. Future Research Having developed a detailed dynamic model, including leadscrew effects, we are in a position to evaluate the three controller design approaches described above using this simulation model. This study will be conducted to assess the potential benefits obtainable by each approach, as well as the potential difficulties. The first two control approaches will also be evaluated on the experimental system. For experimental evaluation we will extend the robot arm to reduce its natural' frequencies and we will instrument the arm to measure flexible as well as rigid body motion. It is expected that some reduction in the detrimental effects of link flexibility can be achieved by modification in the control software only, and perhaps more, improvement can be obtained by the addition of sensors but no additional actuators. This should provide a means to reduce the detrimental effects of link flexibility in many applications without the need for both additional sensors and actuators (i.e. micromanipulators). Annual Report 23 August 1, 1983-July 31, 1984

References [11] Chalhoub, N. and A.G. Ulsoy, "Dynamic Simulation of a Flexible Robot Arm and Controller", Proceedings of the 1984 American Control Conference, San Diego, CA. [2] Chalhoub, N. and A.G Ulsoy, "Dynamic Simulation of a Flexible Robot Arm and Controller," RSD-TR-13-83, Center for Robotics and Integrated Manufacturing, Ann Arbor, Michigan, September 1983. [3] Cannon, R.H., et al, First Annual Report of the Center for Automation and Manufacturing Science, Stanford, University, pp. 31-41, November 1983. [4] Cannon, R.H. and E. Schmitz, "Initial Experiments on The End-Point Control of a Flexible One Link Robot," International Journal of Robotics Research (submitted for publication), 1983. 3.1.5.2. Control of Cable Actuated Manipulator Investigator: Professor N.H. McClamroch Status of the Research A two link manipulator using DC servo motors on each link to control the torques transmitted to the links via elastic cables was studied, with support from Mr. H.P. Huang. This two link mechanical manipulator emulates, in part, the human biceps/triceps system for moving the arm. The manipulator consists of two rigid links, two tendon cables and two springs. Movement of the links are made possible by two tendon cables: one end is wound on a DC servo motor shaft. The servo motors with attached cables simulate the agonists and the elastic springs simulate the antagonist muscles. By controlling the voltage input of the motors, these two links can be caused to move in a plane. The configuration is shown in Figure 3.1.5.2.1. Our objective was to carefully analyze the influences of the motor inductances and cable elasticities on the motion of the manipulator. The elastic cables provide some flexible compliance to the manipulator, which may prove useful for achieving certain manufacturing tasks and for safety reasons. Since the equations of motion of the manipulator are highly nonlinear and complicated, we focused on developing mathematical models of the open-loop manipulator under various assumptions. For control purposes we considered simple displacement feedback of the links to regulate the motion. Based on a displacement control strategy, general conditions for local stability of the closed loop were obtained. Simulation studies were made for various reasonable parameter values. Our conclusions were that actuator inductance effects played a minor role in achieving accurate control of the manipulator, but the cable elasticities played a major role in achieving accurate control of the manipulator. This work has been completed and is described in [1]. It is intended that the manipulator model developed will be used in future research on manipulator control. References [1] Huang, H.P. and N.H. McClamroch, "Final Position Control of a Two Degree of Freedom Cable-driven Manipulator," RSD-MEMO-1-84, Center for Robotics and Integrated Manufacturing, The University of Michigan, January 1984. August 1, 1983-July 31, 1984 24 Annual Report

I~~ - el 3.1.5.3. Mathematical Aspects of Control of Flexible Systems Investigator: Professor N.H. McClamroch Status of the Research Motived by manipulator control issues generally, as illustrated by the cable driven manipulator mentioned previously, several issues related to control of flexible systems were studied. First, sampled data control issues, as they arise in use of digital feedback for control of manipulators, have been studied. The main emphasis has been on the evaluation of the effects of sampling time as related to the closed loop stabilization of a flexible system. Explicit conditions which relate the tradeoff between sampling time and feedback gains, for which the closed loop is guaranteed to be stable, have been developed. These results are reported in a short paper [1]. Similar results in the case where an observer constitutes a part of the controller are given in the conference proceedings article [2]. A related study, carried out with the support of A.I. Iskanderani, was concerned with the development of an effective approach to the statistical estimation of displacement and velocity data obtained from a flexible system. A new approach to such estimation problems has been developed; the basic approach is indicated in a conference proceedings article [3]. Preliminary applications of these general ideas have been made to the nonlinear manipulator control problem, in discussions with E.G. Gilbert and I.J. Ha, where a nonlinear estimator is used as a part of the feedback controller. It is expected that this research will be completed during the coming year so that a basic framework Annual Report 25 August 1, 1983-July 31, 1984

for control of flexible manipulators using nonlinear estimators or observers is established. Since another source of compliance in many manipulators is due to actuation effects, a study was made of the dynamics of manipulators controlled by electrohydraulic servo actuators. In particular, detailed mathematical models were developed for manipulators, taking into account the flexibility effects of electrohydraulic servo values and actuators. Closed loop stabilization issues have been addressed in the case where both displacement and force feedback to the servo valves are used; the results of this study represented in [4]. The effects of force feedback and load disturbances on the local compliance of a manipulator at the end-effector have long been recognized; a general mathematical treatment of these issues has been developed and will be written during the coming year. References [1] MhcClamroch, N.H., "Sampled Data Control of Flexible Structures using Constant Gain Velocity Feedback," AIAA J. Guidance, Control and Dynamics (to appear). [2] McClamroch, N.H., "Stabilization of Elastic Systems using Sampled Data Feedback," RSD-TR-4-84, Center for Robotics and Integrated Manufacturing, The University of Michigan, March 1984 (also to appear in Proceedings of 23rd Conference on Decision and Control, 1984). [3] Iskanderani, A.I. and N.H. McClamroch, "Single Estimation for Second Order Vector Difference Equations," IEEE Transactions on Automatic Control (accepted for publication), (also to appear in Proceedings of 23rd Conference on Decision and Control, 1984). [4] McClamroch, N.H., "Displacement Control of Flexible Structures using Electrohydraulic Servo Actuators," RSD-TR-9-83, Center for Robotics and Integrated Manufacturing, The University of Michigan, June 1983. 3.1.6. Force Control of Manipulator Research Objectives In many manipulator tasks the end-effector is in contact with an external fixed constraint, e.g. a tool, a machine or a constraint surface. Such contact issues are particularly important to consider in most assembly tasks such as the insertion of parts into a socket and tightening of bolts and screws. In such cases the basic manipulator dynamics are modified by the contact force. The basic problem is thus to control both the motion of the end-effector as well as the contact force at the end effector, subject to the imposed constraints. In some cases, sensing of the contact forces that develop between the end-effector of the manipulator and its assembly interface is possible and can provide vital feedback information to the servo control for guiding and controlling the manipulator in completing its tasks. August 1, 1983-July 31, 1984 26 Annual Report

3.1.6.1. Force Recognition In Peg-Hole Insertion Processes Investigator: C. S. G. Lee Status of the Research Loosely speaking, compliant motion may be defined as the ability to modify the manipulator motion based on sensed contact forces during the motion. Compliance may be classified as passive or active. Passive compliance is provided by the inherent mechanical compliance of the manipulator linkages, servos, or by special compliant fixturing devices such as the remote center compliance device. Active compliance provides the manipulator with a programmable capability to react to force or tactile stimuli. An integral part of our research is to design an active compliance control strategy that (i) effectively utilizes the force sensory feedback information to control the arm in carrying out a fine motion task, and (ii) incorporates pattern recognition methods for force recognition and guidance control so that the manipulator can improve its performance in the peg-hole insertion process. The proposed force feedback control strategy for an insertion process can be logically decomposed into two separate subsystems: (i) a pattern recognition system for recognizing the force vector at the assembly interface, and (ii) a guidance and control system for compliant motion control. The proposed force feedback control block diagram is shown in Figure 3.1.6.1.1. The pattern recognition techniques embedded in the force control strategy require that the control space be partitioned into groups of "control situations" in which an appropriate best control law is 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 situations. The combination of pattern recognition and modern control theory has been used successfully in other areas [1-3]. Research to date details the development of a parametric pattern recognition system for recognizing the contact configurations in the peg insertion task. Recognition is based on the resolved force vector at the assembly interface and classification of the peg-hole configurations into control regions. Analysis of the peg insertion task reveals that possible peg-hole contact configurations can be partitioned into six types (Figure 3.1.6.1.2). Details about the derivation of the equations generating a force/moment vector corresponding to each possible contact configuration can be found in [4]. These equations are used to generate training samples for learning the distribution parameters of the conditional probability density function for each peg-hole configuration. A Bayes' learning scheme is used to find the distribution parameters of the forces for each contact type. A decision rule, based on the minimum probability of error, is then developed for recognizing the contact configuration given the sensed force and the force distributions for each contact type. The equations for generating contact configuration forces, the learning technique, and the decision rule have been simulated on a VAX 11/780 computer to verify the validity of the technique. Tables 3.1.6.1.1 and 3.1.6.1.2 summarize the simulation results for the learning and recognition techniques respectively. Four simulation runs were performed for various force and random angles situations. Table 3.1.6.1.1 summarizes the number of learning repetitions required for mean convergence of each contact type. Table 3.1.6.1.2 summarizes the percentage of correct type recognitions for each set of simulation parameters. A typical convergence of the Euclidean norm of the mean force vectors, IIW+l-Wt ll2, learned for a contact type at successive values of training samples is shown in Figure Annual Report 27 August 1, 1983-July 31, 1984

3.1.6.1.3. The following results and conclusions may be drawn based on the simulation results. (1) The force distribution mean for each type converges at approximately 2000 learning repetitions. (2) Types 1, 2 and 3 always show greater than ninety percent recognition regardless of relaxation of force or angle variances. (3) Recognition of types 1, 2 and 3 (and to a lesser degree type 5) is relatively insensitive to relaxation of the force variance. Types 4 and 6 however are very much affected by the force variance. Misrecognition of type 4 and 6 is predominantly as type 2 and 5 respectively. The cause for this misrecognition is that the types have similar force distributions. Examination of the mean vectors for types 5 and 6 (at 2000 learning repetitions for angle variances relaxed) shows them to be nearly identical. Types 2 and 4 do not show as great an element by element correspondence but they do have some mean vector elements in common. (4) All types are relatively insensitive to relaxing the angle variation. Types 2 and 6 are the most significantly affected with a reduction in recognition of about 10 to 15 percent. Type 4 actually shows an increase of 15 percent in correct recognition when the angle variance is relaxed; presumably because it moves the force distributions of types 2 and 4 further apart. (5) Simulation of the recognition technique assumed a priori probability of P(c, ) = ~. Better recognition is likely when appropriate choices for P(,) are n determined. Choice of P(w, ) is predicated on the results of actual experimental data and prior knowledge of the geometry of the peg insertion task. Preliminary evaluation of the learning and recognition techniques indicates that these methods are entirely adequate for the proposed force recognition strategy. Future Research Ongoing research will provide experimental verification of the learning and recognition algorithms using a PUMA 560 robot with Scheinman force sensing wrist. Data will be obtained to aid in the appropriate choice of values for P(w, ). Guidance control algorithms will be developed and implemented on the PUMA robot for performance evaluation of these techniques for the peg insertion task. Furthermore, a non-parametric pattern recognition scheme will also be studied and compared with the above parametric approach. References [1] Fu, K.S., "Learning Control Systems -- Review and Outlook," IEEE Transactions on Automatic Control, pp. 210-221, April 1970. [2] Fu, K.S., "Learning Control Systems and Intelligent Control Systems: An Intersection of Artificial Intelligence and Automatic Control," IEEE Transactions on Automatic Control, vol. AC-15, pp. 70-72, February 1971. [3] Saridis, G.N., "Application of Pattern Recognition Methods to Control Systems,"' IEEE Trans. on Automatic Control, Vol. AC-26, no. 3, pp. 638-645, June 1981. August 1, 1983-July 31, 1984 28 Annual Report

[4] Lee, C.S.G., and R.H. Smith, "Force Feedback Control In Insertion Process Using Pattern Analysis Techniques," Proceedings of the American Control Conference, San Diego, CA, June 1984. TABLE 3.1.6.1.1 Simulation results for learning technique. Table entries represent the number of learning repetitions required for convergence of the mean vector of each configuration type force distribution. All Variables Force Variance Angle Variances Force and Angle Constrained Relaxed Relaxed Variances Relaxed (Sim.datl) (Sim.dat2) (Sim.dat3) (sim.dat4) Type 1 1800 1800 2000 2000 Type 2 2000 2000 2000 1900 Type 3 2000 2000 2000 2000 Type 4 2000 2000 2000 2000 Type 5 2000 2000 1800 1400 Type 6 2000 1800 1700 1800 Annual Report 29 August 1, 1983-July 31, 1984

TABLE 3.1.6.1.2. Simulation results for recognition scheme. Table entries represent the percentage of correct type recognitions. All Variables Force Variance Angle Variances Force and Angle Constrained Relaxed Relaxed Variances Relaxed (Sim.datl) (Sim.dat2) (Sim.dat3) (Sim.dat4) Type 1 100.00 100.00 99.59 99.59 Type 2 96.41 93.23 84.79 79.92 Type 3 98.30 97.55 98.19 95.98 Type 4 59.92 26.65 76.13 31.70 Type 5 98.75 87.50 94.57 85.92 Type 6 76.18 59.25 62.79 46.32 August 1, 1983-July 31, 1984 30 Annual Report

4...F —-- FORCE FEEDBACK CONTROLx BAYES LEARNING SCHEME TRAINING P(C) 02, f(xl i) _ ^^<^ r EVALUATE. -/ DETECTOR d(x) "^ C^x8 _ap~ ~.d and -- CONTROTRLX AP(Cn) f(x I c,) SELECTOR I=1,''',n FORCE RECOGNITION _ CONTROL _ GUIDANCE and SIGNALS CONTROL ARMS PHYSICAL PARAMTERS Figure 3.1.6.1.1 Force Feedback Control Structure Annual Report 31 August 1, 1983-July 31, 1984

I II III IV V VI Figure 3.1.6.1.2 Six Contact Configurations for Force Recognition August 1, 1983-July 31, 1984 32 Annual Report

3.063 2.690 2.316 t. 9 3 - I 1.569?.8220 -.0 7?8X, I 200 425 650 875 1100 325 1550 775 2000 nrepsl Figure 3.1.6.1.3 Convergence of Force Distribution Mean for Increasing Number of Training Samples Annual Report 33 August 1, 1983-July 31, 1984

3.1.6.2. Motion and Force Control of the End Effector of a Manipulator in Contact with a Constraint Investigator: Professor N.H. McClamroch Status of the Research: This research, carried out with Mr. H.P. Huang, has been concerned with control of a manipulator where the end-effector is in contact with a constraint surface. If the manipulator dynamics can be adequately modeled to take into account the effect of continuous contact, effective control may be achieved based on displacement sensors and/or use of force sensors. The question arises: can both force and motion be explicitly and simultaneously controlled? The answer is positive if we use a suitable closed chain manipulator model. A closed chain manipulator can be regarded as a series of linkage mechanisms where the tip of the manipulator is in contact with a fixed constraint manifold. The closed chain manipulator model provides a basis for the study of: * (force) sensor-based servo control * motion/force planning as well as task planning o the interface between manipulator and assembly tasks Suppose that the end-effector moves on a prescribed frictionless manifold; in addition, contact between the end-effector and the constraint manifold is maintained throughout the whole motion by a reaction force. The constraint reaction force is nor-.mal to the constraint manifold at the contact point, so that any virtual displacement involves only sliding along the manifold at that point. Hence no work is done by the constraint force in a virtual displacement. In the following, the dynamics of the closed chain manipulator are presented. Let T E R " be the generalized force vector, q E R" be the robot coordinate vector. M(q) denotes the inertial matrix which is symmetric and nonsingular. F(q,q) comprises Coriolis terms, centrifugal terms, and gravitational terms. We define p E R' as the position vector of the end effector in workspace coordinates. The relation between robot coordinates and workspace coordinates can be expressed as P = H(q) where H:R" -, R" is twice continuously differentiable. We also assume that the manipulator is nonredundant, viz., the Jacobian matrix -H(q) is square and nonsingular. Oq Now we impose the holonomic path constraints (P)- 0 ( =l,..,m) where:R" -. R" is twice continuously differentiable. These constraints define an m dimensional manifold, and hence the effective number of degrees of freedom of the manipulator is (n-m). Let ER" be the generalized reaction force vector required to maintain satisfaction of the path constraints; then the dynamic equations for a closed chain manipulator, taking into account the reaction force, are August 1, 1983-July 31, 1984 34 Annual Report

M(q)q + F(q,q)= T + r Since no work is done by the reaction force r in a virtual displacement it follows that - JT(q)Dr(p)X where XERm represents the multiplier vector required to maintain satisfaction of the constraints, and -(q) aH), D(p)- aO(P) Given a specified motion of the manipulator, satisfying the imposed path constraints, can we compute the torque vector T which would generate this specified motion and the corresponding reaction force? This problem is usually referred to as the direct dynamics problem. Similarly, the inverse dynamics problem considers the following: given the torque vector T, what is the manipulator motion, satisfying the imposed constraints, and the corresponding reaction force necessary to maintain satisfaction of the constraints? Calculation of the reaction forces plays an important role in these problems. We now make the following assumptions: (Al) The inertial matrix M:R" -, R" is nonsingular. F: R" X R" -* R" is bounded and Lipschitz continuous. (A2) 0:R" -, R " is twice continuously differentiable. (A3) J(q) is nonsingular for all qER". D(p) has full rank m for all pER". Two basic propositions which have been derived are now presented. Proposition 1: Suppose that the torque vector T(t)ER" is piecewise continuous on t < t. Given T(t) and initial values q(to)=go, q(to) =qo, satisfying H(qo) ES, J(qo)qoET(H(qo)). Then uith assumptions (Al), (AS) there exist. a unique reaction force f(t) such that the motion of the manipulator satisfies the path constraints assuming there is no finite escape time, for t o< t < t. Proposition 2: Given motion q(t), satisfying ((H(q(t)))=O, tot<t<t, which is twice continuously differentiable. Under assumptions (Al). (AS), there ezist torque vector T(t) and corresponding reaction force vector f(t) for which q(t)tlo<ttf, describes the manipulator motion. These results form the basis for our study of the control of both motion and contact force for such manipulators. Although there has been some previous research in this area our approach constitutes a unique and more fundamental approach to this important class of manipulator control problems. Annual Report 35 August 1, 1983-July 31, 1984

Future Research This fundamental theory forms the basis for the research in control of such manipulators both in terms of planning issues and also in terms of sensor based feedback control. Our current attention is focused on a class of optimal planning problems which should provide experience in understanding the trade-offs between simultaneous control of both motion of the end-effector and contact forces on the end-effector. Research in this area will continue during the coming year. We also hope to use the basic framework to begin a study of sensor based feedback control of the end-effector motion and contact force. 3.1.7. Trajectory Planning, Obstacle Avoidance and Control Of Two Co-operative Robots In An Assembly System Investigator: Professor C. S. G. Lee Research Objectives This research focuses on various issues in assembly task operations involving the control and coordination of two cooperative robots in an assembly system. The assembly systems as described by Whitney [13] are small size manufacturing systems in which there are sequences of time-coordinated operation; and these time-coordinated operations require the robot arms to coordinate their movements from one point in the Cartesian space to another in finite time. Current industrial practice employs simple time-space coordination which does not allow more than one robot working in a common workspace efficiently and effectively. Such coordination and control result in under utilization of robot arms. Any improvements in the performance of controlling two cooperative robot arms will require further investigation of sophisticated off-line straight line trajectory planning and control strategies, efficient obstacle detection and avoidance strategies. Thus, the principal objectives of this research are: * Off-line planning of straight line manipulator trajectory in Cartesian space with torque constraint * Hand collision avoidance by preplanning collision-free path using the above trajectory planning results * Controlling the manipulators to follow the preplanned trajectory faithfully so that two co-operative robots can assemble a workpiece correctly without any collision. The ultimate goal of the research is to provide solution for current industrial robots in performing more intelligent assembly tasks. Status of the Research The research to date indicates that the approach is promising in the areas of straight line trajectory planning and adaptive control for following a preplanned straight line trajectory. These results are briefly described below. Planning of Manipulator Trajectory in Cartesian Space with Torque Constrairnt: In this research, we are concerned with the formalism of describing the desired manipulator motion as sequences of points in space (position and orientation of the manipulator hand) through which the manipulator hand must pass. These movements August 1, 1983-July 31, 1984 36 Annual Report

based on a preplanned path are required for a manipulator to perform a task and avoid fixed obstacles in the workspace more efficiently. In general, trajectory planning in the joint-variable space is simpler than that in the Cartesian space because of degeneracies and dynamic constraints [1,10]. The degenerate case happens when a set point on the manipulator hand trajectory in the Cartesian space results in a singular Jacobian matrix. The dynamic constraints are composed of maximum allowable velocity and acceleration of each joint which yield torque constraints depending on instantaneous joint position and velocity. In addition to the dynamic constraints, each joint trajectory must maintain a smooth transition which yields velocity and acceleration continuity from a set point to another set point. Most of the existing off-line trajectory planning schemes focus on the requirements that the trajectory must be smooth and continuous [1,2,7,8-12]. Our research effort extends these concepts and includes the manipulator dynamics in the planning of straight line trajectory in the Cartesian space [7]. The planning of straight line trajectory is performed in the Cartesian space and requires optimization of two consecutive cartesian set points in the joint-variable space. Using the jerk bound' and torque constraint in the joint-variable space, an iterative forward and backward search technique, instead of a nonlinear quadratic programming, is developed to determine the joint values (position and its first two time derivatives) at each sampling instant or control interval on the straight line within the bounds imposed by the smoothness and the torque constraints. Real-time servo intervals instead of normalized time intervals are used for all n joint trajectories. These sets of joint position, velocity and acceleration will be used as referenced inputs to the manipulator controller (joint-variable space control [3,5]) or can be used to determine the corresponding Cartesian position, velocity, and acceleration on the straight line for the Cartesian space control [4,5]. The proposed straight line trajectory planning will be useful for obstacle avoidance and the resolved motion adaptive control [4,5]. More details about the optimization and the procedure for generating the set points on the given straight line trajectory is given in reference [6]. The proposed trajectory planning scheme is shown in Figure 3.1.7.1. Adaptitve Perturbation Control with Feedforward Compeneation in Joint and Cartesian Coordinates: Given the sequences of set points on the trajectory either in joint or Cartesian coordinates, an adaptive perturbation control with feedforward compensation can be designed to control the manipulator to track the set points as closely as possible for all times over a wide range of manipulator motion and payloads both in joint and Cartesian coordinates. The proposed adaptive control is based on the linearized perturbation equations in the vicinity of a nominal trajectory. The controlled system is characterized by feedforward and feedback components which can be computed separately and simultaneously. The feedforward component computes the nominal torques from the NewtonEuler equations of motion either using the resolved joint information or the joint information from the trajectory planning program. This computation can be completed in O(n) time [2]. The feedback component consisting of recursive least square identification and one-step optimal control algorithms for the linearized system computes the variational torques in O(n3) time. Because of the parallel structure, the computations of the adaptive control may be implemented in low-cost microprocessors. Details about'jerk is defined as the rate of change of acceleration. Annual Report 37 August 1, 1983-July 31, 1984

this adaptive control can be found in [6]. Future Research Future research will focus on development of hand collision avoidance strategies for two co-operative robots working in a common workspace. This problem can be tackled in two subproblems: (1) the static case and (2) the dynamic case. In the former case, we assume that one robot is stationary and holding a workpiece while the other is moving and may collide with it. In the latter case, we assume that both robots are moving and performing their respective tasks and that both may collide with each other. We intend to design collision avoidance strategies for both cases. References [1] Brady, M., et aL, Motion Planning, MIT Press, pp. 221-243, 1982. [2] Lee, C.S.G., R.C. Gonzalez and K.S. Fu, Tutorial on Robotics, IEEE Computer Society Press, New York, pp. 135-141, November 1983. [3] Lee C.S.G., M.J. Chung and B.H. Lee, "An Approach of Adaptive Control for Robot Manipulators," Journal of Robotic Systems, vol. 1, no. 1, pp. 27-57, Spring 1984. [4] Lee, C.S.G. and B.H. Lee, "Resolved Motion Adaptive Control for Mechanical Manipulators," Transactions of the ASME, Journal of Dynamic Systems, Measurement and Control, vol. 106, no. 2, pp. 134-142, June 1984. [5] Lee, C.S.G. and M.J. Chung, "An Adaptive Control Strategy for Computer-Based Manipulators," to appear in IEEE Transactions on Automatic Control, September 1984. [6] Lee, C.S.G. and B.H. Lee, "Planning of Straight Line Manipulator Trajectory in Cartesian Space with Torque Constraint," Proceedings of the 23rd Conference on Control and Decision, Las Vegas, December 12-14, 1984. [7] Lewis. R.A., "Autonomous Manipulation of a Robot: Summary of Manipulator Software Functions," Technical Memorandum 33-679, Jet Propulsion Lab., California Institute of Technology, Pasadena, CA [8] Paul, R.P., "Manipulator Cartesian Path Control" IEEE Trans. on System, Alan, and Cybernetics, vol. SMC-9, no. 11, pp. 702-711, November 1979. [9] Paul, R.P., Robot Manipulators: Mathematics, Programming, and Control, MIT Press, 1981. [10] Taylor, R.H., "Planning and Execution of Straight Line Manipulator Trajectories," IBM Journal of Research Development, vol. 23, no. 4, pp. 424-436, July 1979. [11] Whitney, D.E., "The Mathematics of Coordinated Control of Prosthetic Arms and Manipulators," Transactions of the ASME, Journal of Dynamic Systems, Measurement and Control, pp. 303-309, December 1972. [12] Whitney, D.E., et al., "Design and Control of Adaptable Programmable Assembly Systems," NSF First Report, R-1284, The Charles Stark Draper Lab., August 1979. August 1, 1983-July 31, 1984 38 Annual Report

0o) 62) l Forward Forward Acceleration Set Points In.ltlal $___ Set-Point Set Point8 I1 I Search Algorithm Of"^ ------- i ----- i --------- Deceleration Set Polnts P(to) Modlcd Kleati [a(*)] 3.2. Integrated SolidStte Sensors for Closed-Loop Robot Coelaxantrol The development etof imprPointsor s an essential key to the eventual realization Search S sor development represents a primary foc for research in tAlgorith he Solid-State Electronics Annual Report 3 August 1, 1983-July 31, 1984 Algorithm up - -— 1)vk J Jkq(k ))i(*> [%i] M 61t!1 - M. v; (kk t..Ifgae oi-tt esr o lsdLo oo oto Th eeomn fipoe snosi nzsnilky oteeeta elzto of robot~~~~~S aal promn ohsited as i otruchue nionet.S sordevlopentrepesets prmar fousforresarc intheSold-SateEletroiI Annual Reporf 39 Augusf i, 1983-July 31, 1984~~~~~~

Laboratory at Michigan, where most past and present work has concentrated on sensors based on solid-state process technology. These devices typically combine transducers and interface circuits on a single monolithic sensor chip which provide high-level buscompatible data to the host processor. As part of the total system, these sensors must be looked on as system elements and must be designed to allow the best in system-level performance. Thus, our approach to sensor development is increasingly aimed at the development of automated sensing systems. While the design of improved transducing structures and high-performance interface circuitry remains important, system development must also include features at the sensor to enhance its system role and must include the development of processor algorithms to allow machine interpretation of the measured data. Thus, sensor development is becoming a coordinated effort across several disciplines. Work to include self-test and remote-test capability on the sensor chip itself reflects this increasing emphasis on sensing systems. A primary emphasis for our work in sensor development is provided by applications in integrated manufacturing: specifically in sensors for robotics and, under a separate contract funded by the Semiconductor Research Corporation, for use in the automated manufacturing of VLSI semiconductor circuits. This section will summarize research conducted under the second year of the current Air Force contract. This research focuses on two specific robotic sensors: a tactile imaging array, and a broadband noncontact thermal imager. These two projects are described below. 3.2.1. A High-Performance Silicon Tactile Imager Based on a Capacitive Cell Investigator: Professor K.D. Wise While future robot systems are certain to utilize a broad range of sensors for feedback on actions performed and for information on their environment, many of these sensors will be adapted from other fields (e.g., transportation). A narrower group of devices will be developed specifically for robotics. Of these, sensors to impart a sense of touch to robot grippers are the best current example. It is generally agreed that such devices are badly needed. Application requirements vary widely, however, ranging from simple binary (one-bit) touch sensors to high-performance tactile imagers composed of 50-250 elements spaced on 1-2 mm centers and yielding a gray-scale resolution equivalent to about 6 bits in pressure per element. There are many possible approaches to the development of useful tactile imagers, and such devices are under development in several laboratories. Most approaches utilize a compliant pad as a key element in the array, measuring its compression as force is applied and converting the results to an electrical output signal capacitively or resistively. Since most such pads exhibit wear, hysteresis and long-term compression effects in use, the success of high-performance tactile imagers depends in large measure on how well the compliant pad characteristics can be separated from the transducer itself. A device using the pad as a simple force transmitter might thus be expected to exhibit higher performance than a device which measures pad compression in response to force. Nonetheless, several promising designs have been reported [1,2]. The approach we have taken in developing a tactile imager is based on a silicon capacitive pressure transducer [3,4]. This transducer is known to offer very high performance and is particularly well suited to array applications. The basic cell was described in the last annual report and is shown in Figure 3.2.1.1. A silicon wafer is etched from the front to form recesses 4pm deep. The wafer is then subjected to a deep boron August 1, 1983-July 31, 1984 40 Annual Report

TOP VIEW EXTERNAL PRESSURE 1 I 1 ~i + PPL / U 02 f /SILICON POLY r- -Ii TV I t GLASS REFERENCE CAVITY Si3N4 CROSS-SECTION VIEW Figure 3.2.1.1 Basic Structure of the Capacitive Tactile Imaging Cell (Shown with the overlaying protection plate and pad) diffusion and is subsequently etched from the back to form diaphragms about 15pm thick. The silicon is coated with silicon dioxide and selectively metalized to form rows of capacitor plates. The wafer is then bonded to a glass plate metalized with orthogonal columns of capacitor plates about 4pm from the rows. Thus, a matrix of capacitors is realized. The electrical equivalent circuit is shown in Figure 3.2.1.2. The structure is read out by simultaneously applying complementary clock signals to a selected row (e.g. R2) and the reference row (RD). Due to mismatch between the active row-column capacitance and the reference capacitors as the result of applied force and the associated deflection of the active plates, net charge is pumped onto the column lines as the rows are switched. This charge is integrated by the column amplifiers to provide an output voltage which is proportional to the force on the selected cell. This approach to tactile imaging has several advantages. The compliant pad over the array is used only to transmit force, not transduce it. All array dimensions can be precisely controlled. Finally the basic transducer is stable, free from hysteresis, and rugged. Results Achieved During the Second Year During the second year, work has focussed on a detailed analysis of this sensing structure in terms of its noise mechanisms and expected performance and on the Annual Report 41 August 1, 1983-July 31, 1984

Ao~ g 0 ~ I I_ U' —R2 I J ROW R A2 a2 SELECT -, AND 01 DRIVE #2__ CIRCUITS RN RD TACTILE TRANSDUCER ~~_______ _MATRIX. COLUMN DETECTION AMPLIFIERS C C C2 3 CN IMAGE OUTPUTS Figure 3.2.1.2 Electrical Equivalent Circuit of the Capacitive Tactile Imager realization and testing of 64-element (8X8) arrays. A summary of the operating array performance (calculated) is shown in Table 3.2.1 for three arrays occupying the same overall area. Since as the capacitor plates touch a natural strain relief is provided, the calculated rupture pressure is between one and two orders of magnitude greater than the maximum operating pressure (equivalent in Table 3.2.1 to about 10gm per element). The lowest plate resonance for dynamic operation of an 8X8 cell has also been calculated as about 170KHz. Noise sets the lower limit on the measurable applied force, while the transducer itself sets the upper limit. The maximum capacitance change in Table 3.2.1 is conservatively taken as about 70 percent of the zero-pressure capacitance. Noise to limit the minimum detectable capacitance change comes from three sources: interrogation of the array itself, noise in the readout circuitry, and temperature effects. Noise during readout of the array itself is dominated by crosstalk due to charge pumping to the August 1, 1983-July 31, 1984 42 Annual Report

substrate through the row-to-substrate capacitance. However, even in the worst case, these effects are very small with the induced voltages equivalent to about seven bits of resolution (30fC) 50 nSec after switching the 5V clocks. Since charge integration is typically performed several microseconds after switching and since substrate voltage bounce decays with time, such substrate coupling does not appear to pose a problem. For an 8X8 array, the overall minimum detectable signal change (MDSC) is about 17fC ( about 8 bits of resolution) operating over a 50~C span with no compensation. Without temperature effects (or with compensation), over 10 bits of resolution is possible. Several 8X8 tactile imaging arrays have now been fabricated and are being characterized. The process is now capable of producing such arrays with very high yield. Most problems encountered have been associated with row-substrate shorts, which are believed to have been due to dielectric breakdown under the row lines. This is possible since these lines are essentially floating prior to their connection to the drive circuitry. We are now in the process of adding protection diodes to the row lines to guard against such problems. Suitable wire-bonding techniques have also been developed for interconnecting the finished arrays. The first test of these 8X8 arrays will use commercial integrated circuits for both the row drivers and the column amplifiers. Such circuitry has been built up on a printed-circuit card and tested with one of our first 8X8 arrays. While detailed tests must still be performed, indications are that resolution equivalent to about four bits is possible using this circuitry. Nonetheless, this arrangement will enable us to characterize COMPARISON BETWEEN 4x4, 8x8, and 16 xl8 ARRAYS ARRAY SIZE 4x4 8x8 lx xi CELL SPACING (mm) 4 2 1 DIAPHRAGM (pm) 2400x 2400x43 1200x 1200x 17 400 x 400 x 3.9 ZERO PRESSURE CAPACITANCE(pF) 8.48 1.62 0.18 RUPTURE PRESSURE(PSI) 327(921g) 130(388g) 30(84g) CF(PF) 20 10 5 MAXIMUM OUTPUT VOLTAGE(V) 1.11 0.56 0.12 MDSC(fC) 30 17 4 MAXIMUM RESOLUTION(BIT) 9. 8 7 ***AREA -= 2.0x 2.2cm, MAX. PRESSURE - 175 mmHg (9.5)*** Table 3.2.1 Calculated Performance for Tactile Imaging Arrays Annual Report 43 August 1, 1983-July 31, 1984

full arrays and begin studying various pad materials. It will also allow these arrays to be interfaced to image processing equipment at an early date. Subsequently, we plan to integrate the column amplifiers on a single monolithic chip so that the full array performance can be realized. References [1] Raibert, M.H., "An All Digital VLSI Tactile Array Sensor," Proc. International Conference on Robotics, Atlanta, Ga. pp. 314-319, March 1984. [2] Boie. R.A., "Capacitive Impedance Readout Tactile Image Sensor," Proc. International Conference on Robotics, Atlanta, Ga., pp. 370-378, March 1984. [3] Lee. Y.S. and K.D. Wise, "A Batch-Fabricated Silicon Capacitive Pressure Transducer with Low Temperature Sensitivity," IEEE Trans. on Electron Devices, vol. ED-29, no. 1, pp. 42-48, January 1982. [4] Park. Y. and K.D. Wise, "An MOS Switched-Capacitor Readout Amplifier for Capacitive Pressure Transducer," Proc. Custom IC Conference, pp. 380-384, May 1983. 3.2.2. A Silicon-Based Thermal Imager Investigator: Professor K.D. Wise 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-14pm 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 [1] in this area concentrated on single-point detectors employing thin (0.5-lpm) silicon windows 2 X 2m in size. In order to realize a practical line imager, the vertical element separation must be reduced considerably while maximizing detectivity. cmvn'/h/ a responsivity of 17.1 V/W, and a response time of 7.1 msec using a window size of 0.4 X0.7mm. Using two staggered columns of these detectors, an effective vertical spacing of 0.25 mm can be realized. In an imaging mode with a 5cm 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.2cycle/mrad. This spatial frequency corresponds to a pattern repetition length of 5cm at a distance from the detector of 20 meters. The performance is computed at room temperature in the 8-14 pm band. This thermal imager is being developed for us in automated process control applications where moderate levels of resolution are acceptable and cooling to 77~ is undesirable. NWhile 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 contrast, the thermopile approach is based on low-cost silicon technology Analysis has shown that a thermopile array consisting of 40 (p+) polysilicon-gold thermocouples and dielectric windows (no underlying silicon) can produce a detectivity of about 5 X 107 August 1, 1983-July 31, 1984 44 Annual Report

r COLD 1 JUNCTIONSJ INTERCONNECTING r - LEADS L.. THICK SUPPORTING RIM TI- IN \N WINDOW I L_ 1 AREA TOP VIEW METAL SILICON INTERCONNECT ABSORBER (Bi BLACK) DIOXIDEl / _METAL B /A^^^^^C^^ //yJ^^^^ METAL A - - \ / SILICON RIM CROSS SECTION CASE Figure 3.2.2.1 A Silicon-Based Thermal Imaging Cell 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. Results During the Second Year During the first year of this program, the technology for producing dielectric windows in silicon with high yield was developed and the first 40-element thermopile detectors were realized. The window size was 400pmmX700pm. Two staggered detector columns gave an effective vertical element separation of 250ipm as noted above. During the past year, work has concentrated on characterizing the above structures and on the design of the first full prototype imager. Measurements on the 40-element detectors generally confirmed the above calculations. Time constants were less than 10msec, while responsivity was generally in the 10-12 V/W range. The small size of these detectors complicated characterization and made any assessment of the effects of blacking on the performance of the detectors difficult. Accordingly, a larger detector structure was designed and fabricated. This detector is shown in Figure 3.2.2.2. This detector uses a dielectric window 1.6mm in diameter and 1.3pm thick. The window Annual Report 45 August 1, 1983-July 31, 1984

Afeaaured Performance* Output Voltar Response Time No absorbing Black Unsealed 90OV 30m sec Black-side Blacking Unsealed 107 V 50 m sec Front-side Blacking Unsealed 174gV 80m sec Front-side Blacking Vacuum sealed 290OV 60 m sec *for an incident power of 0.8mW/cm2 on the detector front Table 3.2.2.1 Response Characteristics for a Single-Element Theromopile Detector The detector utilized a 1.6mm diameter dielectric window 1.3pm thick and is used with a IKBr window. A total of 32 polysilicon-gold thermocouples are used with a 15 pm feature. contains 32 polysilicon-gold thermocouples with 15pm features. These detectors were illuminated on the front at a power level of 0.8mW/cm2. A KBr window was used in front of the device. The measured performance is shown in Table 3.2.2.1. For no blacking, only a small fraction of the radiation is absorbed by the structure, most being either reflected or transmitted through it. Front side blacking is seen to be effective in preventing both reflection and transmission. Finally, based on the substantial improvement seen for vacuum-sealed devices, considerable conduction losses from the window to the header appear to be present it our present mounting structure. The vacuum sealed response is equivalent to a responsivity of more than 18 V/W. Based on these results, we are confident that our calculated array performance can be achieved or exceeded. We have recently completed the design of a 32 element prototype imager. The device consists of two lines of 16 detectors each, with each window measuring 0.4X0.8mm and with an effective vertical element separation (center-to-center) of 300pm. The overall die size is 5.4mm X 11.2mm. The process requires 7 masks (4 critical) and includes MhOS analog multiplexers to permit readout of the 32 detector outputs on two lines. During the next year, we plan to integrate and characterize the above arrays and incorporate them in imaging cameras. These cameras will then be interfaced with image processing and display equipment and used to explore a number of applications in robotics and integrated manufacturing. References [1] Lahiji, G.R. and K.D. Wise, "A Batch-Fabricated Silicon Thermopile Infrared Detector," IEEE Trans. Electron Devices, 29 pp. 14-22, January 1982. August 1, 1983-July 31, 1984 46 Annual Report

Figure 3.2,2.2 A Single-Point Broadband Infrared Detector 3.3. Vision for Robotics Vision is of such importance to robotics and manufacturing that it 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. Annual Report 47 August 1, 1983-July 31, 1984

Several aspects of these problems are being addressed by CRIM, including * 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 occuluded parts * The direct optical processing of images: the goal here is to reduce processing time dramatically 0 The analysis of vision operations to determine the class of special computer architecture best suited for implementing the operation. During this past year, we have begun some redirection of our work toward the vision area in response to a growing capability in this area, suggestions from our mid year review, and a desire to build this as one of our major areas of research. At the end of the first year, we began to support the work of one of our (at that time) new faculty members, Professor Jain. During this year, we have decided to expand that activity and will be further increasing support in this area during the third year of the contract. In conjunction with this, his work is being focused more on the use of multiple images in conjunction with motion for vision. 3.3.1. Edge Detection Using Contour Tracing Investigator: 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 outputs 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. In the past year we have finalized our work in this area by comparing our edge detectors, mentioned in last year's report to the V2 G operator of Marr and Hildreth and Haralick's directional second derivative edge detector. This will appear in a paper in the IEEE Transaction of Systems, Man, and Cyberneticst. Status of Research The problem of locating intensity edges in images has generated much interest in the literature. Many approaches to this problem involve the use of edge operators whose 2E.J. Delp and C.H. Chu, "Detection, Edge Segments," to appear in IEEE Transactions on System, Man. and Cybernetics. August 1, 1983-July 31, 1984 48 Annual Report

outputs are subsequently classified by the use of a threshold. We will consider the problem of linking image edge points without imposing a classification threshold. We will view this as a post-processing task to follow the application of an edge operator. For the present, we consider an edge operator to be any mathematical operator such that, when applied to a digital image, produces an estimate of the magnitude and direction of the intensity gradient at every point in the image. The gradient magnitude and direction information represents the input to our system. Our goal is to determine, with as much positional accuracy as possible, connected lines representing intensity edges in the original image while not responding to spurious effects of noise, etc. A crucial observation is that it is not desirable to quantize this gradient information any more coarsely than possible. We certainly do not want to threshold this data (quantize to one bit) globally, locally, adaptively, with hysteresis, or whatever; nor do we wish to non-maximum suppress it. The experience of detection theory, coding theory, and related disciplines states that coarse quantization of noisy, correlated observations independently of one another may be expedient or acceptable when the signal-to-noise ratio is high, but leads to poor performance when the signal quality deteriorates. Instead of making such hard decisions (thresholding) right away, experience dictates one "integrate" the soft information over many observations before concluding on a decision. Sequential Edge Linking (SEL) is one manner in which such integration may be performed in the context of image edge detection. Integrating edge information over a large set of pixels becomes increasingly difficult to do with long, directional edge operator masks as the number of pixels in the mask increases. This is because, for large operator masks, the number of possible edge configurations becomes enormous. It is tempting to suggest a maximum likelihood approach. To do this, one might hypothesize all possible edge paths of, say, n pixels in length, calculate their respective a-priori likelihoods, assuming some distribution on the gradient levels, and pick the largest. However, the exponential growth of the candidate configurations with n confounds this approach as well, regardless of the maximum likelihood algorithm used. The situation is exactly analagous to that of decoding convolutional codes in coding theory. There, one may use ML techniques such as Viterbi decoding as long as the constraint length is small (k < 8 or 9). Beyond this, the exponential growth of computation and memory requirements with constraint length make the algorithm too unwieldy. The solution to the decoding problem with large constraint lengths, sequential decoding, is the inspiration behind SEL. In both situations one does not attempt to explore all possible paths in the tree, picking the ML path, but rather one explores only a small subset of them with a high probability of including the correct one. This exploration is accomplished sequentially, extending only those paths which hold high promise of being the correct one. The procedure used is called sequential tree searching and is borrowed from coding theory. It presumes that a start or root node is given. This start node must be on an intensity edge but is otherwise arbitrary. The selection of start nodes will not be discussed here, but it is part of our continuing research for the next year. The root node defines a tree of semi-infinite paths in the random field. Because of the special structure of paths, there are precisely 3" paths of length n (or to depth n in the tree) beginning at the root node. The sequential searching algorithm begins at the root node and sequentially examines paths in the tree. The sequential behavior, however, is common to Annual Report 49 August 1, 1983-July 31, 1984

them all. At each iteration of the algorithm, one of the paths explored so far is extended by one node and the metric (the metric is a measure of now well the chosen path corresponds to a probabilistic model of the true path) for this new path is calculated. Decisions are made based on these metrics as to which path should be extended on the next iteration. This is in accord with the definition of a sequential tree decoder as defined by Forney. a decoder is sequential only if each new path hypothesized is an extension of a previously examined one and the decision as to which path to extend is based only on the set of paths visited thus far. Because long paths are built up node by node, it is entirely possible that the algorithm can be tricked by noise in the random field values into incorrectly following a non-edge path for some depth into the tree. The average tendency of the metric under these circumstances is to decrease with increasing length. These forays along incorrect paths will eventually be halted by the resulting decreases in metric. The algorithm at some point settles back onto the correct (edge) path for which the average tendency is for the metric to increase with length. There are a number of candidate algorithms for performing this tree searching. They include the Fano algorithm, the Zigangirov - Jelinek (Z-J) algorithm or stack algorithm, the A * algorithm, and various modifications of the above such as the stackbucket and multiple-stack algorithms. 3.3.2. Using Extended Frame Sequences for Motion Understanding Investigator: Ramesh Jain Most structure from motion research has been concerned with recovering structural information from a minimal number of points which have been corresponded over as few frames as possible. The motivation for this philosophy is that by minimizing points and frames one can avoid extensive computations for solving the difficult correspondence problem. Approaches developed make use of some elegant mathematics [see e.g., 1]. Unfortunately, by restricting the number of points, the points used take on a great deal of importance; sub-pixel precision is frequently called for and cannot be obtained without a great deal of effort, if at all. In general, these approaches are too sensitive to noise to be useful in pragmatic situations [2]. Research Objectives We have begun studying approaches which require longer frame sequences. With the improvements in memory technology it is not necessary to rigorously discard data down to only three or five points; instead we can attempt to take advantage of larger amounts of, admittedly imprecise, data. We desire techniques more robust to noise, and do not require extensive analysis if only two frames. Over a long frame sequence moving objects generally have consistent trajectories of motion. It is only relatively rarely that an object will change the motion parameters of acceleration and velocity. We note that this consistency of velocity and acceleration can be included with the already studied positional information [3] to provide considerable power for doing correspondence. If there is good support for certain motion characteristics, it is possible to predict the next location of the points. Extensive search is not necessary and because a longer frame sequence is used there is increased reliability. Our August 1, 1983-July 31, 1984 50 Annual Report

approach to obtaining motion parameters is to satisfy the constraint half-planes in the three space: acceleration, velocity, and initial position. Psychophysical research has shown the importance of trajectories for human visual perception. We plan to develop approaches for establishing correspondence using several frames. Status of Project An approach currently under investigation is to establish a number of provisional correspondences over several frames (we are currently using 5 frames as the minimum). Any correspondence having inconsistent motion parameters is immediately rejected. Because motion parameters are reasonably, accurately calculated when averaged over at least 5 frames, we can predict the next position of the object well. A veridical change in the motion parameters is termed an "event." An event can be caused by such things as collision, occlusion or by the object itself. The correspondence chosen may be the one which minimizes the number of events occurring in the trajectories. Alternatively, knowledge of object 3-D position or object characteristics will enable us to predict some collision and occlusion events (i.e. we will be predicting some discontinuities as well as the smooth parts of trajectories). This correspondence is obtained with considerably less effort than extensive search. Because it holds for a longer frame sequence, it is considerably more reliable. Interpolation can be performed to provide the accuracy needed for structure from motion calculations. The events are discontinuities in object motion. It appears that segmenting the trajectories will be a useful step for motion understanding. We are interested in the representation of complex movements; event and smooth trajectory representations will be helpful. References [1] Tsai. R.Y., T.S. Huang and W.L. Zhu, "Estimating three-dimensional motion parameters of a rigid planar patch," Part 1, IEEE Trans. ASSP, December 1981, Part 2 August 1982. [2] Roach, John W. and J.K. Aggarwal, "Determining the Movement of Objects from a Sequence of Images," IEEE Trans on PAMI, Vol PAMI-2, No. 6, November 1980. [3] Ullman, Shimon, The Interpretation of Visual Motion, MIT Press, Cambridge Massachusetts, 1979. 3.3.3. Axial Motion Stereo Professor Ramesh Jain Problems and Objectives Many passive and active methods have been developed for obtaining depth information in a scene. Active methods are useful only in constrained environment. Stereo methods face the problem of solving correspondence in two images. For dynamic scenes, many approaches have been developed for structure from motion (sec.3.3.2). It has been shown that optical flow carries information about the environment. Considering the difficulty of computing optical flow, we are trying to develop methods to use characteristics of optical flow without computing it. Annual Report 51 August 1, 1983-July 31, 1984

Status of Research We are developing a new stereo method for mobile robots. This method uses only one camera which moves in a known or determinable direction. Suppose that we have a mobile camera whose motion can be obtained using a sensor, or which is moving under computer control. If the displacements of the camera (dx, dy, and dz) are known, then the focus of expansion (fx, fy) can be computed using: fX = d and y - dzo' dz By applying complex logarithmic mapping to the images of a sequence about the focus of expansion. it can be shown that the horizontal displacement of points in the transformed space is determined by only the distance of the point from the camera. The image is represented as a complex plane c = + iy and we apply a logarithmic transformation to give w = u + iv = log(c) This is equivalent to u - logX + y2 and v = tan-l y/x It can be shown that, for a stationary point (x,y,z), du dv _= — and -- 0 dz z dz Thus, all stationary points will show only horizontal displacement in the transformation, and this displacement will be controlled by the depth of the point. This simplifies the correspondence problem since the search for corresponding points can then be confined to the scanlines. We developed an interpolation method for the complex logarithmic mapping of images. This method is an inverse mapping. We determine at which spot in the image each pixel in the mapping must originate. We then interpolate the intensities of a 3 X 3 pixel square around this spot to determine the intensity in the map. The result of this method is shown in figure 3.3.3.1. Using our interpolation mapping, we performed several experiments to study the efficacy of this approach for depth recovery. Our experiments with synthetic image data show that depth can be recovered quite accurately. Future Research We are mounting a camera on our PUMA arm to apply axial motion stereo to real world scenes. It should be mentioned here that there are many properties of complex logarithmic mapping which are favorable in computer vision systems. Using this transformation we will be able to obtain structure of surfaces in a scene as a by product. After a dynamic scene has been segmented, axial motion stereo will be applied to obtain structure and depth of surfaces. August 1, 1983-July 31, 1984 62 Annual Report

Figure 3.3.3.1 3.3.4. Rapid Surface Mapping Investigator: Professor G. Frieder Rapid surface mapping should be considered as part of the important area of quality control. In our approach, we developed a methodology which is capable of computing a high number of x, y, z points on a surface in a very short time. The points that we are considering are the traces of a projection of n X n matrix of laser dots, with n restricted to a binary power. We currently us n =. 129, providing 16384 surface points. The time that is necessary to acquire the information (i.e., digitize the points) is equal to (kl + log2n)d, where k is the digitization time, currently 1/30 of a second. The time required to do the computation is dependent on the processor and the degree of parallelism. Theoretically, all 16384 points can be computed in parallel. In practice, we use a VAX with 10 minutes of computabilty time to produce the values of x, y, z points. This year has seen the culmination of the effort in the area of rapid surface mapping. We consider this technology now mature enough to be transmitted to industry and used there to develop vision systems. The bulk of the programming effort was reported in Report RSD-TR-18-83, "Software Support for the Stereo Camera: Phantom and Measurement Programs", which is now available from the Center for Robotics and Integrated Manufacturing. The report comes complete with program listings and examples. The experimental setup which is necessary for the measurement of the laser-produced patterns is available for demonstration to AFOSR personnel in the Avionics Laboratories of Wright-Patterson Air Force Base. Please contact Lt. Col. Bruce Altschuler, AFWAL/AAAT-3, Bldg. 620, Dayton, Ohio 45433, (513) 255-7646. The mathematics, pattern description and further references are readily available in the aforementioned report. The rest of the work that has to be done on this subject is mainly in algorithmic robustness and in error analysis. Both areas are now being pursued by the WPAFB group.,While they proceed in the experimentation, we intend to proceed with the Annual Report 53 August 1, 1983-July 31, 1984

analytical approach, and try to find optimum ranges for the methodology. We do not intend, however, to continue to draw support for this effort from the current grant, and this work should, therefore, be considered complete. 3.3.5. Partially Occluded Part Recognition Investigators: Professor T.N. Mudge, Professor R.A. Volz The Problem and Objectives The goal of this project is to design a vision system that will recognize industrial parts in scenes where the parts are are either partially occluded or poorly lit. Fairly robust algorithms [1P2] exist for recognizing parts in specially arranged scenes, where the complete boundaries of the parts are available. These algorithms, however, call for special lighting conditions and the added constraint that none of the parts lie on top of one another or lie partially out of the scene. These constraints limit the flexibility and applicability of these algorithms. The vision system under construction recognizes parts under poor viewing conditions and is more flexible than previously developed algorithms. The central algorithm [3-4] of this new vision system recognizes parts from broken edge contours; hence, it is applicable when either the complete edge contours are unavailable due to poor lighting or when edge contours are broken due to partial occlusion. Approach The basic approach to the recognition problem has its origin in template matching but utilizes three principal concepts to achieve vastly improved performance: 1. The use of segments of a template for matching 2. The weighting of the segments to emphasize those which best distinguish one object from others which might be present 3. The use of an intrinsic coordinate system for representing template and image information. A brief discussion of the algorithm is given below: For each part that might appear before the camera, a template of its edge contours is extracted and stored. The template is stored in two representations. The first is a representation in cartesian space of the x and y location of each edge point from some reference point. The second is a representation in an intrinsic coordinate space (referred to here as 0-s space) of the slope angle, 0, together with the arc length distance along the contour, s, of each edge point. Figure 3.3.5.1a shows the two representations for a triangular part. The advantage of the 0-s representation is that rotations in the cartesian space correspond to offsets in the 0-8 space. Thus, as shown in Figure 3.3.5.1b, the 0-s representation of the rotated triangle is the same as the representation of the non rotated triangle except for an offset in the 0 direction. Matching can be accomplished more rapidly in the 0-s space than in cartesian space because of this simplification in dealing with rotations. A set of subtemplates are derived from each template. A subtemplate is taken to be a fixed length segment of the total template. Each subtemplate also has two August 1, 1983-July 31, 1984 54 Annual Report

A B 360 270I 270 20270 C 180 180 B 90 90 A 0 A0 A... I. a) b) Figure 3.3.5.1. representations, one in cartesian space and the other in 0-s space. Figure 3.3.5.2 illustrates a subtemplate of the triangle template in both the cartesian space and 0-s space representations. Subtemplates of a part are assigned weights according to their distinguishability or saliency. Subtemplates of one part which resemble those derived from other parts are assigned lower weights than those which are different from part to part. By assigning weights, the subtemplates of the edge contours which are unique to one part are emphasized while the subtemplates common to many parts are deemphasized. Figure 3.3.5.3 shows templates from several parts. Subtemplate 1 in Figure 3.3.5.3 would receive a larger weight than subtemplate 2 since straight templates such as subtemplate 2 are common in all the Darts. suttemplates Ae.-.. - ---- --------- theta subtemplate 1 subtemplate 1 arclength Figure 3.3.5.2. Annual Report 55 August 1, 1983-July 31, 1984

subtemplate 3 suntemplate 2 subtemplate 1 Figure 3.3.5.3. Determination of the subtemplates and assigning weights is done off-line using an optimization algorithm. To be a little more specific, the problem was posed as a quadratic optimization problem: Minimize: wt Cw Subject to: ltw = 1 and w> 0 Where wu is the weight associated with the itk subtemplate, and where w is a vector of these ui weights representing the weights for all the subtemplates. The matrix C captures the cross correlation of the template whose weights are to be chosen with the set of templates of all the parts that could appear in the scene [3] [4]. 1 is a vector of l's and 0 is a vector of 0's, both with same dimensions as w. The weights derived in solving this problem were used in emphasizing unique subtemplates during the matching process as discussed next. During run-time, a part is located in an image scene by matching subtemplates of the part to the edge contours of the parts in the image scene. Each pixel in the image scene has an associated accumulator, initially zero. The edge contours of all the parts in the image scene are extracted and are represented in both the cartesian and 0-s spaces. Segments of a fixed length are derived from these edge contours and matched to subtemplates of the desired part in 0-8 space (See Figure 3.3.5.4a) in the following way: The mean of the subtemplate was shifted in 0 to the mean of the image segment. During this past year we have proven that this provides a least squares fit of subtemplate to the August 1, 1983-July 31, 1984 5b Annual Report

image segment, where the shift in 0 is the single parameter of fit. The subtemplate is assumed to match the image segment if the sum of the squares of the differences in 0-8 space between the shifted subtemplate and the image segment is below a fixed threshold. A vector from the center of the subtemplate to the centroid of the whole template is stored with each subtemplate, as shown in Figure 3.3.5.2. If a match occurs, the vector associated with the subtemplate is rotated in cartesian space to the same orientation as the subtemplate so as to point to the relative location of the centroid of the template from the the subtemplate. The vector is attached to the edge contour at the location of match in the cartesian space representation and the subtemplate weight is added to the accumulator associated with the pixel pointed to by the vector (See Figure 3.3.5.4b.) In this way. if a subtemplate matched an image segment the subtemplate "voted" for a possible centroid of its parent template. Subtemplates unique to a part have larger weights and hence cast a larger "vote" than other more common subtemplates. The accumulator which receives the largest weight in votes is assumed to be the centroid of the template of the part sought. Status of the Research Effort Since the initial work, research effort has been in two areas. First, the original vision algorithms have been incorporated into an interactive vision system and second, several algorithmic improvements have been added to increase the performance of the algorithms. Also, as noted above, we have added to our understanding of the algorithm in that we have proven that the adjustment of subtemplates by the difference of mean values in 0 is actually a least squarer fit of the subtemplate to a boundary segment in 0. A. subtemplates f subterrc.:ae image boundary fth~ta Image boundary 0 Ax^^-s —~ti~ Imap% aw ay~vote for centrold stored here —'- suotemplate arclength a) b) Figure 3.3.5.4. Annual Report 57 August 1, 1983-July 31, 1984

The vision system runs on an Apollo workstation. The Apollo was chosen for its high resolution graphics and its extremely friendly development environment. All commands are selected from a screen displayed menu using a pick device. The templates and image contours are displayed in both cartesian and 8-s coordinate systems simultaneously as shown in Figure 3.3.5.4. The vision system is interactive in that it allows the user to manipulate the templates and the image contours to investigate different approaches. The vision system allows one to prototype different variations on the algorithms with visual feedback as to the degree of success of these algorithms. The programs, written in Pascal, makes calls upon Appllo's Core Graphics library and should prove portable. Using the interactive vision system several algorithmic improvements have been discovered. One of these is a new approach to matching the image segments to the subtemplates. Previously, each subtemplate was matched to each image segment. Presently, a coarse to fine approach is applied in which the image segment is first sampled coarsely in 0-s space. This coarse sampling is matched against coarse samplings of the subtemplates to eliminate a large number of impossible matches at little computational cost. A finer sampling of the image segment is then matched to finer samplings of those subtemplates which matched at the coarser sampling and so on. Another algorithmic improvement is the use of hash tables for the matching process. Previously, when a subtemplate matched an image segment, the vote for a centroid was stored in an array with the same dimensions as the image, i.e. 256 by 256. By using the hash tables to store the votes considerable memory can be saved with the result that several templates can be searched for simultaneously, more efficiently than before, since their accumulators can all remain in main memory at the same time. Future Work The work with coarse to fine matching is presently being extended to building a look up tree for subtemplates. The coarsely sampled image segment will be used to choose one of the possible branches of the tree originating from the root of the tree. Once on a branch, a finer sampling of the image segment will be use to choose the next subbranch and so on until the image segment is matched to subtemplates that are similar. A new weighting technique will be investigated. If two subtemplates with the same spatial relation in both the template and boundary image "vote" for the same location as a possible centroid of their parent template, the probability that the template has its centroid at that location should be more than just the sum of weights from the two subtemplates. A Bayesian approach will be employed to get a better estimate of the probability that the centroid of a part is located at a pixel which receives two or more votes". It should also be noted that the work accomplished in this area during the first year of the contract has led to receipt of a grant from ARO to pursue extensions to recognition based upon 3-D data and the relations between algorithms and architectures. August 1, 1983-July 31, 1984 58 Annual Report

References [I] Gleason, G.J., "Vision Module Development," Ninth Report, NSF Grants APR75139074 and DAR78-27128, SRI Projects 4391 and 8487, Stanford Research Institute, Menlo Park, CA., pp. 9-16, August 1979. [2] Wallace, T.P. and O.R. Mitchell, "Local and Global Shape Description of Two and Three Dimensional Objects," Technical Report TR-EE 79-43, School of Electrical Engineering, Purdue University, West Lafayette, IN, September 1979. [3] Turney, J.L., T.N. Mudge 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, Cambridge, MA, November 1983, [4] Turney, J.L., T.N. Mudge and R.A. Volz, "Recognizing Partially Occluded Parts," IEEE Pattern Analysis and Image Processing (to appear). 3.3.6. Applications of Optical Processing to Robotic Vision Investigator: Professor E. Leith Optical data processing techniques were investigated as a method of reducing computational overhead in specific robotic vision applications. The primary emphasis of our current research effort applies directly to the following applications: (1) Surface plane identification (2) Micro-3 dimensional surface inspection (3) Nacro-3 dimensional surface contouring. For optimum system performance the proposed optical data processing systems must contain the following essential features: (1) The use of incoherent light for optical processing (2) The ability to be implemented in a hybrid optical-digital computer architecture for quasi-real-time operation (3) The optical data processing system should possess the potential to be environmentally and dimensionally stable yielding reproducible, reliable output (4) The system should be easy to align and maintain alignment over the course of repeated measurements. In order to encompass all of the above mentioned features, the optical system should contain diffracting, as opposed to refracting elements. Possible optical data processing schemes would make use of diffraction gratings as optical elements. The grating imaging process, using the grating interferometer, incorporates the above mentioned characteristics and has other advantages over conventional refractive lens imaging. (1) The grating process is space invariant. Gratings do not suffer from off-axis Seidel abberations, such as, coma, astigmatism, and distortion, which are tied to the space-variant characteristics of lenses. (2) Imaging gratings should be able to realize low F-number values since the grating can be arbitrarily large as compared to the focal length. The smaller F-number does not increase the required tolerances or the aberrations. Annual Report 69 August 1, 1983-July 31, 1984

(3) The imaging process can be achromatized. In general, interferometers do not function effectively under broad spectrum illumination. Utilizing symmetric architectures the grating interferometer can be made to perform under broad spectrum illumination. Status of the Research Efforts Several systems incorporating the grating interferometer as a front end optical data processing system are being tested. These interferometric systems can be broken into the following general classes depending upon source type: (1) Monochromatic, point source (2) Monochromatic, extended source (3) Broad spectrum, point source (4) Broad spectrum, extended source. The major research efforts under the current contract period involve monochromatic extended source interferometers. We concentrated our efforts on performing monochromatic broad source matched filtering operations. Our goal was to circumvent some of the inherent system constraints encountered in conventional optical matched filtering using either coherent or incoherent source illumination. Some typical problems associated with conventional coherent matched filtering involve system alignment, system stability, the need for expensive incoherent to coherent converters, and increased scattering noise due to optical imperfections and surface part irregularities. Incoherent matched filtering suffers from an inherent bias buildup problem which makes the signal difficult to separate from the background. Extensive research has been done on methods which use complicated computer generated optical filters in the filter plane[ 1] or methods where the background is subtracted from the signal using a digital computer [2]. Both of these methods rely heavily on the use of digital processing for optical filter synthesis or for optical data processing of the output. Therefore, conventional optical matched filtering operations have drawbacks which make these methods unsuitable for industrial applications where large amounts of data are to be processed. Utilizing the grating interferometer, under monochromatic broad source illumination, the matched filtering operations can be performed on real object transparencies. The interferometric optical data processing system allows for a variety of interesting hybrid-digital configurations which do not suffer from the disadvantages detailed above. Figure 3.3.6.1 presents a generalized interferometric optical data processing system. The upper beam can be denoted as an object beam, while the lower beam is used as a reference beam. The object and reference transparency can be placed in different positions depending upon the mathematical operations to be performed. In a general sense the following mathematical operations can be performed. August 1, 1983-July 31, 1984 60 Annual Report

Object Reference General Plane Plane Operation P PI F 18 11218212} PI P2? P2 P2 82(82 P3 P3 82082 Placement of the transparency in other planes performs mathematical operations that are somewhat redundant. The operation of interest involves placement of the object and reference in planes P2 or P3. Analysis shows that the output intensity along the x' axis is of the form: I(x' ) = bias + cos(fx' ){ s3(X - fZ' )e j' }~ { 3(x o - f' )e i' } This is simply a cosine modulated autocorrelation function. In the laboratory we have recorded this one-dimensional autocorrelation on photographic film. In real time one could simply place a solid state detection array along the x' axis and do simple electronic signal processing to obtain an image of the autocorrelation functions. An identical match between object and reference maximizes the autocorrelation into a digital computer where simple, fast algorithms can determine the similarity between object and reference. P1 P2 PP PI p!~2 3 I s (X) I S (X) I(x) Quasi-mnochromatic 1 x spaially icoheret I s (x) I s (x) G G 2 G 2 3 f f f 1 1 1 Figure 3.3.8.1 Annual Report 61 August 1, 1983-July 31, 1984

Other potential interesting systems involve structuring the source by placing an object in PI and imaging this object plane to planes P2 or P3 containing a reference. Further research will determine if the output is linear in field amplitude or intensity, dictating the mathematical operations to be performed. This system has the advantage of using a narrow band cathode ray tube as a source which can be coupled to a solid state or video on camera as an object recording media providing a method of conveniently scaling the object electronically. Further research for the 1985 contract period involves investigating the system mentioned above, as well as investigating spectral source broadering effects, and folding the grating interferometer so that solid reflecting objects can be used directly. The folding grating interferometer would have a powerful advantage over other systems because the object and reference would be directly imaged instead of being, for example, imaged first onto a CRT. In summary, this interferometric method of optical pattern recognition has the following characteristics, in comparison with other systems employing either coherent or incoherent illumination: (1) Reduced bias buildup under incoherent illumination (2) Reduced coherence improves signal to noise ration. The system performance will not be degraded by optical quality or environmental factors. (3) Easily implemented hybrid optical systems with minimum digital computations. (4) Dimensional stability and insensitivity to mechanical vibrations (5) One dimensional operations. Rotation of object and reference yields twodimensional autocorrelation. (6) The potential to function effectively under broad source, broad spectrum conditions In a second project, we are investigating other incoherent optical processing systems. There have been about half-dozen basic systems proposed. We have some preliminary conclusions, which at this point are rather tentative. Basically, the various incoherent systems appear to give the same performance and are essentially the same, even though the implementations are rather different. However, the grating interferometer Fourier Transform method described above is an exception; it is basically different from the other techniques. It appears that these basic differences are, on the whole, advantageous. References [1] Lohmann, A., Appl. Opt. 16, 261 (1977). [2] George, N. and S. Wang, Appl. Opt. 23, 787 (1984). 3.3.7. On the Global Compaction of Microprograms Investigator: Professor Daniel E. Atkins Problem statement and objectives This research is an attempt to design and build a tool to better manage parallel resources available in special purpose processors for potential robotics application. For August 1, 1983-July 31, 1984 62 Annual Report

time critical robotics applications, for example vision algorithms, planning, or robot arm control, microprogrammed special purpose processors will serve as very cost-effective solutions to speed up computation. Furthermore, we can get even more speed up by exploiting parallel resources available in such special purpose processors. The hardware resources are controlled directly by microprograms which are composed by microoperations. The immediate goal of this research is to develop and implement a heuristic to schedule microoperations in order to speed up execution of microprograms by detecting available parallelism. Approach Microprogram compaction is the process of exploiting parallelism to schedule as many microoperations as possible at the same time to reduce the time and/or space needed for the execution of microprograms. Among the proposed microprogram compaction methods, the trace scheduling [1,21 is the most general and appears to give the fastest execution of compacted microcode. The trace scheduling selects the most likely path of execution among uncompacted blocks, which is called a trace, and compacts microoperations in the trace as if they form a single block. However, the growth of memory size by necessary copying of blocks in trace scheduling can be enormous, exponential in the worst case, and the complicated bookkeeping stage of the trace scheduling has been an obstacle to implementation. Status of the research effort A technique called beta compaction, based on trace scheduling, has been developed to mitigate the drawbacks of trace scheduling. Basically, it identifies the junction blocks (the blocks beginning with a join and ending with a conditional branch) as the major source of complication, and cut traces at those junction blocks. It achieves almost all the compaction of the trace scheduling except that which causes copying of blocks. Memory size after the beta compaction is usually smaller than the original. Even when the memory size grows in rare instances, it is bounded by O(n2) in the worst case. And the bookkeeping stage is very much simplified. The compacted microcode size variation as the source microcode changes is also very small. A loop-free version of both beta compaction and trace scheduling has been implemented. Comparison between the two was done using artificially generated microcodes and the above properties of the beta compaction were confirmed. The experimentation with the developed heuristics showed on the average two to three times speed up by parallelizing microoperations alone. Since microprograms are at the lowest level in the software hierarchy, everything which runs on top of these microprograms would speed up accordingly. A previous version of the heuristic was published in MICRO-16 [31 and the current result is reported in Jehkwan Lah's Ph. D. thesis [4]. A simple microprogrammable machine based on AM2900 components was designed and simulated with an interactive user-friendly interface. A realistic application program was written and hand-compiled into microcode. The microcode was executed on the simulator both before and after compaction, which demonstrated the applicability of the compaction technique and the correctness of the implementation. This simulator can be used as a design tool for building special purpose processors and microprograms can be written, compacted and tested before actual hardware is built so that the design time Annual Report 63 August 1, 1983-July 31, 1984

can be reduced significantly. Future work The tools developed to date will in the coming research phase be applied to a specific testbed for computational subsystems for robotics planning and control. References [1] Fisher, J.A., The Optimization of Horizontal Microcode Within and Beyond Basic Blocks: Application of Processor Scheduling with Resources, Ph.D. Dissertation, New York University, New York City, October 1979. [2] Fisher, J.A., "Trace Scheduling: A Technique for Global Microcode Compaction," IEEE Transactions on Computers, vol. C-30, no. 7, 478-490, July 1981. [3] Lab, J. and D. E. Atkins, "Tree Compaction of Microprograms," Proceedings the 16th Annual Microprogramming Workshop, pp. 11-22, October 1983. [4] Lab, J., On the Global Compaction of Microprograms, Ph.D. Thesis, The University of Michigan, 1984, to be published. 3.3.8. Special Processors for Vision Investigator: Professor T.N. Mudge The Problem and Research 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. A typical image 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 a real life application, it is important to characterize the set of algorithms used and find the most suitable architecture(s) to process these algorithms. This is necessary to improve the performance of the image processing 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 algorithm characteristics, data characteristics and processor design on the performance of the image processing system and how that performance can be improved. August 1, 1983-July 31, 1984 64 Annual Report

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 this, 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 pizela of interest. A natural architecture for many image processing algorithms is a multiprocessor system with equal size subimages assigned to separate processors. Such processors may be classified as Multiple Subimage Processors (MSP'}). A block diagram of an MSP is shown in Figure 3.3.8.1. While MSP's are quite efficient for feature independent algorithms, this is 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 MISP 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 that the distribution of pixels of interest over the image be known. 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. PE, PE2 PE ~. PE ICN (Interconnection Network) Figure 3.3.8.1. Generic MSP. Annual Report 85 August 1, 1983-July 31, 1984

The redistribution effort, measured in number of pixels of interest to be redistributed, is calculated assuming the above binomial model. The number of pixels to be redistributed is proportional to the deviation in the number of pixels of. interest from their mean at equilibrium, where all processing elements have the same number of pixels of interest. Figure 3.3.8.2 shows the redistribution effort as a function of the number of processing elements. The redistribution effort increases as the number of processing elements increases. This suggests that the redistribution of pixels of interest may not be efficient beyond a certain value for the number of the processing elements. The efficiency and the execution time for an image on an MSP system with and without redistribution of the pixels of interest are computed using the same binomial model. The results are shown versus the number of processing elements in Figure 3.3.8.3. The results are parametrized by the parameter Kf. The value of Kf depends on many factors such as: the topology of the interconnection network, the nature and implementation of the image processing algorithm, the implementation of the redistribution algorithm as well as the number of processing elements. The results are shown for k =10. In Figure 3.3.8.3(a), the efficiency of the system after distribution is larger than that before redistribution until a certain value for the number of processing elements is used. Beyond that value, the efficiency after redistribution is less than that before redistribution. In Figure 3.3.8.3(b), the execution time graph shows a similar result. The execution time after redistribution is less than that before redistribution again only until approximately the same value for the number of processing elements is used. Beyond that value. the execution time before redistribution is larger than that before redistribution. This is basically due to the increasing effort of redistribution as the number of processing elements increases. Hence, beyond that value for the number of processing elements, the redistribution process should not be conducted as the effort involved in that process exceeds the loss of having some processors idle during part of the algorithm..t - 0 Mr rumber ot:['5 ~ l-o' > Figure 3.3.8.2. Redistribution Effort. August 1, 1983-July 31, 1984 668 Annual Report

.e, Hucbe., of PE's ('Oq s Figure 3.3.8.3. Efficiency and Execution Time Before and After Redistribution. Several redistribution algorithms have been studied. Future Work Near future work includes: (1) further investigation of other algorithm characteristics and image data models and how they affect the performance of image processing systems'-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, pp. 22-28, Fall 1983. [2] Delp, E., T. 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), pp. 161-167, May 1982. [3] Mudge, T. and E. Delp, "Special Purpose Architectures for Computer Vision," Proceedings of the 15th Hawaii International Conference on System. Science, pp. 378-387, January 1982. [4] Mudge, T.N. and T.S. Abdel-Rahman, "Efficiency of Feature Dependent Algorithms for the Parallel Processing of Images," Proc. ICPP, Baliiare, Mfichigan, 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. Annual Report 86 August 1, 1983-July 31, 1984

3~4. Architecture of Robot Based Manufacturing Cells The ultimate goals of much of our research are to bring some level of intelligence to sophisticated sensor-based robot systems. All of the sensors, sensing algorithms and controls described above, and the CAD model linkages described below are essential ingredients in achieving these goals. But in addition, there is a critical factor, systems integration, i.e., the architecture of robot based manufacturing cells, without which these goals cannot be achieved. The research in this area is directed toward analysis and design of the distributed computing systems which can support complex distributed control and sensing algorithms, device controls, and database interaction, as well as the hardware and software tools which allow the systems designed to be implemented. 3.4.1. Object Based Experimental Robot Cell Investigators: Professors R.A. Volz and T.N. Mudge The Problem and Past Work The basic problem being addressed in this portion of our research is the hardware and software complexity expected in future intelligent sensor based robot systems. The approach being taken to manage the system complexities arising is the use of object based systems, at both the hardware and software levels [1], [2]. At the hardware level we have used the Intel iAPX 432 multiprocessor computer system. At the software level we have used the Ada programming language. During the first year of the project implementation of a multiprocessor based robot system consisting of an ASEA RB6 robot, GE TN-2500 camera and the iAPx 432 computer, as shown is Figure 3.4.1, was started. A standard binary vision system was implemented using this equipment. The implementation was distributed, however, with thresholding and data compression being performed via an attached processor, and the major feature extraction and recognition algorithms implemented in Ada on the 432. The control of the robot system was also distributed, with the world to joint coordinate transformations and communications protocol to the robot being handled on an attached processor. It was anticipated that during the second year of the project the implementation of the experimental system would be completed, a link to an off-line CAD system would be completed and some performance measurements on the system begun. Status of the Research Effort During the past year of the contract the following has been accomplished: * implementation of the basic experimental system has been completed. * a link to an off-line CAD system has been established, permitting CAD driven vision and automatic grip determination * run-time testing for interferences between the robot and objects in the work space partially implemented * some preliminary performance measurements have been obtained * greater experience with the use of Ada for programming such systems obtained. August 1, 1983-July 31, 1984 88 Annual Report

CDP CDOP M MEMORY APX 432 BUS IP IP IP VAX Serin IIi 88/30 11180 Development with The basic ^S -ystem snwcmltadsfrs 8 0 know7 fhard d, c t onsl d oito h I floppy disk( ] model data for training of the vision system, and grip determination. The models during d ~1monitor the second year of activity were generated using the BUILD software developed by Braid. However, the output from the modeler is converted to intermediate boundary representation form which is used in all of our work. It should, thus, be easy to build interfaces to a wide variety of modeling systems. Off-line programs then generate a set of training images for the vision system and generate a list of feasible grip positions (see Section 3.5.1). A video tape of the running system is available. The grip determination strategy (see Section 3.5.1) includes the capability of determining interferences between the robot hand and objects in the workspace of the robot at run-time. This aspect of the strategy is currently being implemented and should be completed sometime early during the third year of the project. Each time that the camera takes a picture of the workspace, each object in the workspace is identified using the vision system. If it is desired to pick up a given object, the set of grips generated offline from the CAD database for that object are examined for interference between the gripper and other objects in the workspace. Beginning with the highest rated potential grip position, the approach/deproach movement of the robot hand is checked for interference with each of the other objects in the field of view. The interference checking algorithms needed for this task are nearly identical to those used in the off-line grip determination program to check for interferences between the robot hand and the object to be gripped, and can be implemented efficiently on the run-time system. Annual Report 69 August 1, 1983-July 31, 1984

There are a number of factors which can affect the performance of the system, and performance can vary quite widely according to differences in these factors. The factors influencing performance are: the number and combined area of the parts being observed by the vision system, which set of Intel cpu chips is used, and whether or not the Ada pragma in line was used in compiling critical routines in the vision system. Our first set of tests were performed with the revision 2.1 cpu chips. With these chips performance was quite slow. Comparisons with a VAX 11/780 over a range of benchmark programs showed that the 432 varied between 1/16th and 1/80th of the VAX. The faster performance was obtained with integer programs and the slower performance with a test program which did little other than make recursive procedure calls to itself. The principal thing pointed to by this set of tests was the slowness of the 432 processor in context switching. This was borne out when the pragma in-line was used for critical routines in the vision system. Performance sometimes improved by as much as factor of four. Of course, the critical difference in code production with in-line as opposed to without it is the absence of large numbers of procedure calls. The purpose of the revision 3.0 chips was to implement more efficient mechanism for context switching and indirect addressing. With these chips installed performance of the vision system was much faster. (We have not yet rerun the performance tests against the VAX 11/780.) For a single object in the field of view, visual recognition time varies between 4 and 12 seconds, with a mean of 7.4 seconds. With the Ada pragma in lines not used in critical subroutines, the recognition times for a single object varied from 5 to 21 seconds with mean value of 11.3 seconds. Thus the performance improvement obtained with the newer chips by using pragma in-line was only 1.5 as compared to nearly 4 with the older chips. In evaluating these performance times, there are several other factors which should be considered. First, we are using a 256 by 256 camera. Most industrial systems use a lower resolution 128 by 128 camera for binary vision systems in order to reduce the computation times. Our use of a 256 by 256 camera thus introduces approximately a factor of 4 in computation time over what we would expect using a more standard 128 by 128 camera. Second, with respect to the Intel iAPX 432 architecture, there is strong evidence that the same cpu chips with better layouts on the PC boards can achieve much higher performance. High Integrity Systems of Great Britain markets a system which reportedly achieves approximately a 2.5 improvement factor (this number supplied by Intel) with the same chips over that obtained by Intel. We are currently negotiating with Intel regarding the possibility of acquiring a High Integrity Systems set of boards to try in our system. In addition, preliminary investigation of the code emitted by the Ada compiler suggests there are considerable inefficiencies in the code produced. The combination of these affect suggests strongly that there is nothing intrinsic in either the object based hardware or the object based software to preclude real-time operation of the system implemented. During the past year of work, our investigations into the use of Ada for programming complex sensor based robot systems has focused on interprocess communication. In our case much of this interprocess communication was in fact interprocessor communication, with the physical communication taking place via the interface processor chips as shown in Figure 3.4.1. It was this interprocessor communication that took by far the greatest amount of implementation time, as opposed to interprocess communication among processes executing wholly on the 432 processor. August 1, 1983-July 31, 1984 70 Annual Report

Communication via the interface processor chips did not use the synchronization mechanisms of Ada; the communication was necessarily handled through low level I/O drivers. This points to a major limitation in nearly all approaches to the integration of multiple smart devices, the need to deal with all devices via explicit I/O and program the devices in (often) different languages (PL/M and assembly language in our case). Often the processes with which one wants to communicate or synchronize exist on separate processors and the language communication and synchronization mechanisms do not extend across machine boundaries. Consequently, we feel there is a strong need for a systems integration language which can extend across machine boundaries. This latter aspect of our work has spawned an entirely new project under the sponsorship of General Dynamics which will investigate the use of Ada as a distributed programming language which will execute across multiple heterogeneous machines. Expected Future Accomplishments During the next year we expect to accomplish the following: * complete the run-time interference checking algorithms * continue performance benchmarks on the system, particularly if the High Integrity Systems set of boards can be obtained to achieve higher speed * upgrading the system performance as additional CAD capabilities become available. One of the objectives in using the object oriented systems was portability. In addition, we are considering an experiment of porting the software to a different system. We have been fortunate enough to acquire several Apollo workstations in the Robotics Laboratory (actually the first two have just arrived and the delivery of the remaining ones is scheduled over the next 4-5 months). We will have the Telesoft Ada compiler on one of the Apollo systems by early Fall, and are considering an experiment of porting the system to the Apollo. Unfortunately, however, the Telesoft Ada compiler currently available for the Apollo, is quite incomplete and missing some important constructs being used on the 432. Sometime during the year, we expect a full implementation of the compiler. Depending upon the timing of that compiler and other staffing considerations we may elect to perform this experiment. References [1] Volz, R.A., T.N. Mudge and D.A. Gal, "Using Ada as a Robot System Programming Language," to appear IEEE Transactions on Systems, Man and Cybernetics, 1984. [2] Volz, R.A., T.N. Mudge and D.A. Gal, "Using Ada as a Robot System Programming Language," Proceedings of the 13th International Symposium on Industrial Robots f Robot 7, pp. 12-42 to 12-57, April 1983. Annual Report 71 August 1, 1983-July 31, 1984

3.4.2. Status of Research Effort on Integrated Multi-Robot Systems Investigators: Professor K.G. Shin, Professor R.A. Volz Introduction Conventionally, multi-robot systems(MRS's) are centrally controlled; that is, control tasks for an MRS may be distributed over a network of processors or reside in a uniprocessor but are all executed under directives of one central task.3 Although almost all manufacturing processes can be accomplished using a central controller, communications bottlenecking and unreliability (that occurs at the central controller) become major problems. For this reason we need to develop a new architecture which can accommodate both centralized and decentralized controls. To differentiate this new architecture from the conventional MRS, define an integrated multi-robot system (IMRS) as a collection of two or more robots, sensors, and other computer controlled machinery, such that * each robot is controlled by its own set of dedicated tasks, which communicate to allow synchronization and concurrency between robot processes,5 * the tasks are executing in true parallelism, * both centralized and decentralized control concepts are used, and * tasks may be used for controlling other machinery, sensor I/O processing, communication handling, or general computations. WXe make no assumptions concerning the computers or robots used for an IMRS. There are numerous robot languages designed (see [2] for a survey) which can control more than one robot simultaneously, the most advanced being AL[8]. AL allows one program (and hence one task) to control two robots at once. By using Cobegin-Coend pairs, a programmer can initiate two pseudo-concurrent tasks. They can be synchronized using the EVENT data type (integer semaphores). The principal motive behind this'design was to allow cooperation via serializing each robot's motions by using EVENTS. This restricts the potential amount of parallelism that can be attained. It would be more efficient to let each robot process run under the control of its own tasks, with synchronization (or rendezvous) at designated points in the programs. Some work has been done on distributed industrial process control[10], but the results are not easily transportable to an IMRS. Steusloff[10] has described a distributed, fault-tolerant system used for controlling soaking pit furnaces. The furnace system is controlled by a real-time concurrent language called wMulticomputer PEARL." PEARL allows the transmission of information from one task to another by message passing and remote procedure calls. Each furnace is controlled by its own microcomputer system, and the microcomputer systems are logically paired so should one system fail, the corresponding mate computer system would control two furnaces. This system is reported to be highly fault-tolerant, having only 11 hours of down time in more than 24,000 hours of use. This figure is indeed impressive, but the classes of parallelism involved in the furnace application are far less complex than the classes of parallelism needed in an IMRS. The action of one IMRS process could completely alter the action 3 This is based on (i) several multi-robot systems that were recently displayed at the Robots 8 Exposition in Detroit and (ii) works pulished in open literature. 4 "Process" will be used to denote the industrial output of the IMRS, which is accomplished by a set of "tasks" executing on one or more processors. August 1, 1983-July 31, 1984 72 Annual Report

of another IN1RS process, or robots might have to work on one common process, requiring tightly coupled communication and synchronization. Obviously an IMRS needs a more intricate communications structure to handle this more dynamic environment. There has been considerably more research in the area of communicating concurrent tasks. Numerous languages have been designed which contain primitives that allow tasks to synchronize and communicate via various techniques. We will discuss the issues and ideal communication primitives for an IMRS in a future report. For some actual concurrent languages, see [3], [5], 61], [7], [9], [10], [11], and [12]. Our design approach consists of several distinct phases, beginning from the generic nature of an IMRS to the design and evaluation of the communications system based on process classes. Our current and future research conforms to these phases. Current Accomplishments During the past year we have, first, investigated the various communication demands brought about by all manufacturing processes, which we have classified into five different types of processes: independent, loosely coupled, tightly coupled, serialized motion, and work coupled processes. Then, we have developed a high-level architecture, called module architecture, for an INIRS that explores and integrates both the centralized and the decentralized control concepts. Emphasis is placed on flexibility to facilitate a wide spectrum of manufacturing applications, improved productivity by exploiting the inherent parallelism, and reliability/graceful degradation to provide non-stop operation of the IMRS. The module architecture is mainly concerned with the run-time relationship of tasks, including task creation, task destruction, and intertask communication channels. Two types of communications are needed, vertical communications to handle tightly coupled processes which require a parent task to control its child tasks in a master/slave relationship, and horizontal communications to handle communications directly between child tasks not requiring a central controller. See [1] for a detailed description of the IMRS module architecture. Future Work The general IMRS would encompass many areas of research, some of which includesensors, collisionle and obstacle avoidance, artiicial intelligence, and communications and concurrency. One of the most important steps is the design of the communication system that links the tasks of an IMRS. The design includes the high-level abstractions, i.e. the module architecture, as well as the low-level communication primitives. We feel that the work done during the past year forms a foundation for developing high performance, flexible, and fault-tolerant automation systems. However, there are several important topics to be studied before a complete IMRS system is developed. Following are the topics on which study will be begun during the next year. * Determining what to include in the specification sections of a module. * Choosing an appropriate set of communication primitives. They will be based on message and operation oriented languages [41 because of their applicability in distributed systems. Annual Report 73 August 1, 1983-July 31, 1984

* Determining how to handle the priorities of messages in the message handlers for each task. As discussed in [8], this will probably have to be an expert system, which can be easily modified if messages are not properly handled. * Evaluating the best way to define the communication topology in the source program. Port directed communication [11] may be a possibility. * Designing IMRS system programming constructs for simple and reliable programming of distributed robot and sensor processes * Design of primitives for the operating system kernel. The V System [3] has three major components, the interprocess communications (IPC), the kernel server, and the device server. Our discussion of horizontal communications has many similarities to Cheriton's IPC. The kernel will have to be designed along with the network implementation of horizontal communications, and will prove to be difficult, because of all the different devices and sensors which must be incorporated into the system along with the real-time communications. References [1] Shin. K.G., M.E. Epstein and R.A. Volz, "A Module Architecture for an Integrated Multi-Robot System," Submitted to 18th Annual International Conference on Syster Sciences, January 1985. [2] Bonner, S. and K. G. Shin, "A Comparative Study of Robot Languages," Computer, Vol. 15, No. 12, pp. 82-96, December 1982. [3] Cheriton, D.R., "The V Kernel: A Software Base for Distributed Systems," IEEE Trans. on Software, pp. 19-42, April 1984. [4] Gentleman, W.M., "Message Passing Between Sequential Processes: the Reply Primitive and the Administrator Concept," Software Practice and Experience, Vol. 11. pp. 435-446, 1981. [5] Hansen, P.B., The Architecture of Concurrent Programs, Prentice-Hall, Inc., 1977. [6] Hansen, P.B., "Distributed Processes: A Concurrent Programming Concept," Communications of the ACM, Vol. 21, No. 11, pp. 934-941, Nov. 1978. [7] Hoare, C.A.R., "Communicating Sequential Processes," Communications of the ACM, pp. 666-677, Aug. 1978. [8] Mujtaba, S. and R. Goldman, "AL Users' Manual," SAIL Report, Jan. 1979. [9] Silberschatz, A., "Cell: A Distributed Computing Modularization Concept," IEEE Transactions on Software Engineering, vol. SE-10, no.2, pp. 178-185, March 1984. [10] Steusloff, H.U., "Advanced Real-Time Languages for Distributed Industrial Process Control," Computer, pp. 37-46, Feb. 1984. [11] Wegner, P., and S. A. Smolka, "Processes, Tasks, and Monitors: A Comparative Study of Concurrent Programming Primitives," IEEE Transactions on Software Engineering, vol. SE-9, no. 4, pp. 446-462, July 1983. [12] Welsh, J. and A. Lister, "A Comparative Study of Task Communication in Ada," Software-Practice and E1perience, 1981, vol. 1, 1pp 257-290, Springer-Verlag, 1982. August 1, 1983-July 31, 1984 74 Annual Report

3.5. Improved Robot Programming Robot programming today is still done largely in teach mode. Teach mode programming is intuitive, easy to understand and easy to learn. However, it is very poor for the input of precise data points, inclusion of sensor and actuator interactions and the management of repetitive operations. Off-line programming via procedural languages is currently being introduced into the field. Off-line programming techniques (at least for the better languages) permit the definition of precise points (thought there may be accuracy problems on the part of the robot), and provide mechanisms for handling sensors, actuators and program control. However, they are far less intuitive, and are usually much more difficult to understand and use. Off-line programming will continue to make advances in the near future. There are two other aspects to the programming of robots, however, that offer very substantial gains in the effectiveness in programming robots. The first is the use of graphics as the basis for programming. This approach will have all of the intuitive characteristics of teach mode programming. The challenge is to develop techniques for including basically nongeometric concepts such as sensor/actuator interaction and program control. The second is the use of information derived from CAD database descriptions of the robot and objects to be manipulated as aids to programming. Ultimately, it may be possible to remove the human programmer altogether, at least for certain classes of programs. The research reported in this section is directed toward both of these advanced programming tools. 3.5.1. Automatic Determination of Gripping Positions Investigators: Professors R.A. Volz, Professor A.C. Woo The Problem and Past Efforts The fundamental problem area being investigated is that of task level programming for robot systems used in a manufacturing environment. The basic approach is based upon the assumption that all of the objects to be manipulated, and the robot itself, are adequately described in computer-aided design and other manufacturing databases. The interpretation of task level instructions will lead to a sequence of more primative instructions. We are seeking to relate these primative operations to model information in such a way that the robot program may be deduced from the geometrical and other manufacturing information. The first operation being investigated in detail is that of determining how to grip an object which is described in the database. Grip position determination requires consideration of several basic issues: definition of what constitutes a good grip; specification of the geometries involved; knowledge of the environment; and computational methods. Typical conditions for a"good grip" include the reachability, [1], [2] of the grip position by the robot without interference [3] between the robot and the object to be gripped, and the stability, [4] - [6] the nonmovability of the object being grasped under external forces. Asada [4] has given an alternate definition of stability: that a grip is stable if when a small relative displacement occurs between the part and the hand a restoring force is generated to bring the part back to its original situation. Both Asada [4] and Paul [1] have also suggested that a good heuristic for maintaining stability is to grip the object near its center of mass. Annual Report 75 August 1, 1983-July 31, 1984

The determination of grip positions cannot be accomplished based upon the object alone. Grip positions depend upon other objects in the vicinity which might interfere with a particular grasp point as well. During the first year of the project, the basic structure of a new algorithm for grip determination was developed, and partially implemented. It was expected that the new algorithm would reliably determine good grip positions, be computationally efficient, and be flexible with respect to the application for which the grip is required. Status of the Research Effort There are three aspects to the grip determination strategy and its incorporation into an operational system. These are: * a strategy for determining feasible grip positions. * a set of "quality" measures which can be calculated to compare potential grip positions. * a global strategy for splitting computations between on-line and off-line. The details of this strategy may be found in [7]. The strategy is reviewed just briefly here. Off-line t'. On-line Computation Interference calculations must be performed to assure that a proposed grip does not cause interference between the gripper and any other objects in the vicinity of either the initial or final positions. In a completely unstructured environment, all of the calculations for determining gripping positions are unknown until run-time and all processing must take place then. The manufacturing environment, however, is seldom completely unstructured, and one can use relevant knowledge about the environment to allow some of the computations to be performed off-line to improve run-time efficiency. To provide motivation for the computation strategy to be used one can classify the structuring of the environment in a way that naturally leads to succession of strategies for determining grip positions with the amount of off-line computation possible dependent upon the amount of a priori knowledge. As an example, the following table gives the amount of knowledge for some typical applications. In class CO, nothing is known in advance. Ttie part description itself must be derived by a vision or some type of sophisticated sensor system and none of the needed computations can be performed off-line. Clearly, no advance planning is possible. In all of the other cases at least the geometry of the parts and gripper are known before run-time. One can conceptually, at least, perform the interference test between the part and gripper off-line. For class C1 the obstacle positions at the initial and final location are not known a priori. It is presumed, however, that an external sensor system does exist to identify the obstacles and determine their pose. Consequently, the interference checks must be done at run-time. In class C2 it is assumed that the geometry and pose of some of the obstacles are known in advance. A common example of this would be the part lying in one of its stable positions on a table top (the table is the known obstacle) with other objects scattered about nearby. (The table positions can be found from the geometric model by computing the convex hull of the part, and testing each face for stability [8]). Then the interference calculations between the gripper and the potential obstacles might be August 1, 1983-July 31, 1984 76 Annual Report

performed off-line thus reducing the amount of run-time computation. If there are no obstacles, other than the table, near the part (class C3), then the single best grip for each stable position of the part can be chosen in advance. In class C4 the pose of the part in space is known in advance, as in machine unloading. The exact move command to position the gripper can then be generated in advance. These considerations motivate a computation strategy which is split between offline and on-line computation and in which grip selection is done in four stages. First, a set of grips is proposed and interference between the part and gripper is evaluated. Second, interference between the gripper and the potential obstacles is evaluated. Third, a single grip is selected and finally an exact move command is generated. Slippage and Twisting Criteria Ideally. if one had full knowledge of all physical parameters such as coefficient of friction, gripping force, and accelerations present, one could compute the forces and torques which would be necessary to cause slippage of the object being grasped. Further, if one had full knowledge of the trajectories to be followed, one could compute the acceleration forces and torques to which the object would be subjected during motion. Based upon these, one could determine whether or not a proposed grip would result in slippage or twisting of the object being grasped. Unfortunately, not all of the parameters which would be needed to operate in this ideal mode are readily calculable. Instead formulas are derived for related parameters which bear a monotonic relation to the force and torques required to cause slippage or twisting. These parameters can then be used as quality measures of a proposed grip, in which the higher rated grip positions are more resilient to slippage or twisting than lower rated positions. In particular, "quality" measures are developed for the following: /___ ~____ Advance Knowledge In Robotics Applications___ Off-line Knowled e Availability Part Part Local Part Typical Class Geometrles Configurations Obstacle Pose Application CO Unknown Unknown Unknown Unknown Unstructured C1 Known Unknown Unknown Unknown Bln-Picking C2 Known Known Partlally Known Pick part Known from Cluttered Table C3 Known Known Known Unknown Pick part from Clear Table C4 Known Known Known Known Machine Un_ loading Table 3.5.1.1 Annual Report 77 August 1, 1983-July 31, 1984

El A measure of the resilience of a grip to slippage of the object. E2 A measure of the resilience to twisting of the object during motion of the hand with the part in its grasp. E3 A measure of the resilience to twisting of the object during the closing of the gripper. These evaluation criteria are then used in the grip determination strategy. Strategy for Grip Determination Grip determination is generally an underconstrained problem in that there are usually many grip positions which would be adequate. This fact, together with the idea of being flexible in handling when the interference constraints are imposed (off-line or online), leads to the strategy for determining the grip. Rather than trying to directly obtain a unique grip, a set of geometrically feasible grips are computed. Since it would be desirable for this set to include grips which can be used for a large number of actual configurations of obstacles around the initial and final part, positions in this set should be reasonably dense on the part. Next, each grip in the set is tested against noninterference constraints. The computations can be performed in two stages, one off-line and one on-line. The intent, of course, is to push as much of the computation to the off-line stage as possible. The computations associated with the gripper and part can be performed off -line. Those associated with noninterference with obstacles depend on when the locations of the obstacles become known; in general, they may be split between on-line and off-line. This strategy can be summarized as follows Figure 3.6.1.1 August 1, 1983-July 31, 1984 78 Annual Report

Grip Determination Strategy S1 A set of grip positions for the part is determined such that each potential grip has no interference between the gripper and the part. S2 Evaluate these feasible grips according to criteria E1-E3. Discard those falling below some set of threshold values and sort those remaining in rank order according to a combination of these criteria El-E3. S3 Beginning with the highest ranked grip, apply the non-interference constraints with obstacles until a grip in the list is found which satisfies all constrains. Use this grip. This strategy provides a flexible way of handling constraints and a technique to minimize run-time computation. For several classes of problems most of the calculations can be done off-line. Once a single grip has been chosen, it remains only to generate the motion commands to move the hand into position. The gross movement of the hand into the vicinity of the part is handled by a separate subsystem. The final approach to the part is made along the approach vector. The hand model used in intersection testing below ensures that this is possible. Examples As an example, the part shown in Figure 3.5.1.1 was considered for two different hands used on robots in our laboratory. The part model has 44 faces, 132 edges and 88 vert ices. Steps S1 and S2 of Grip Determination Strategy are first performed off-line. Table 3.5.1.2 shows the time required for this computation. The result is a list of possible grips which cause no interference between the hand and the object together with values for the rating functions. The geometry of Hand 1 allows more potential grips to be reached, hence the larger number of grips in this case. The geometry of Hand 2 led to a larger number of obstacle calculation; hence the larger cpu time. Hand No. of Grips Found CPU Time (VAX 11/780) Hand 1 113 2.0 sec Hand 2 62 3.2 sec Table 3.5.1.2 Annual Report 79 August 1, 1983-July 31, 1984

The algorithm has been fully implemented on a VAX 11/780. It accepts as inputs boundary representations of the parts and obstacles to be considered. The output grip lists from the algorithm are transmitted to the experimental iAPX 432 system where they are used in a run-time system for automatically selecting gripping positions. Future Efforts The initial version of the interface to the grip lists determined by the algorithms described above did not include run-time interference checking. Work is being carried out in conjunction with the robot architecture group to incorporate the run-time interference checking portion of the algorithms. Secondly, the grip determination algorithms are based upon two assumptions which in general are not true, but only produce conservative approximations. These are that the gripper imposes uniform pressure upon the object being grasped and that the potential center of rotation within the grasp of the gripper is about the centroid of the contact area. Work has recently be started to examine both of these assumptions in greater detail to produce a more accurate version of the algorithm and provide a quantitative measure of how good the current approximations are. References [1] Paul, R.P., "Modelling, Trajectory Calculation, and Servoing of a Computer Controlled Arm," AIM 177, Artifical Intelligence Lab, Stanford University, November 1972. [2] Taylor, R.H., "The Synthesis of Manipulator Control Programs from Task-Level Specificiations," AIM-282, Artificial Intelligence Lab, Stanford University, July 1976. [3] Laugier, C. and J. Pertin, Automatic Grasping: A Case Study in Accessibility Analysis. Barga, Italy: NATO - Advaced Studies Institute on Robotics & Artificial Intelligence, June 1983. [4] Asada, H., Studies in Prehension and Handling by Robot Hands uith Elastic Fingers (Ph.D. dissertation), University of Kyoto, 1979. [5] Wolter, J.D., A.C. Woo and R.A. Volz, "Gripping Positions for 3-D Objects," Proceedings of the 1982 Meeting of the Industrial Applications Society, pp. 13091314, October 1982. [6] Laugier, C., "A Program for Automatic Grasping of Objects with a Robot Arm," Proceedings of 11 Int. Symp. on Industrial Robots, pp. 287-294, October 1981. [7] Wolter, J.D., R.A. Volz and A.C. Woo, "Automatic Generation of Gripping Positions," 4th Jerusalem Conference of Information Technology, May 1984. [8] Volz, R.A., A.C. Woo, J.D. Wolter, T.N. Mudge, J.L. Turney and D.A. Gal, CAD, Robot Programming and Ada, Barga, Italy: NATO - Advanced Studies Institute on Robotics & Artificial Intelligence, June 1983. August 1, 1983-July 31, 1984 80 Annual Report

3.5.2. Off-line Training of Vision Systems and Stable Position Modeling Investigators: Professor R.A. Volz, Professor A.C. Woo Problem Description During the past year an experimental, CAD-trained, robot assembly cell was developed (see Section 3.4.1). This is a system capable of recognizing and picking up parts, using information derived exclusively from geometric models of those parts. Section 3.5.1 of this report described work done on the grip selection subsystem [1]. In this section, work relating to the automatic training of the visual recognition system and stable position modeling will be discussed. Currently, a simple binary vision system is used to locate and recognize parts from their silhouettes. (See Section 3.3.4 for an advanced version system which will eventually replace the basic system described here). Vision systems of this type have the advantages of simplicity and speed, but their capabilities are limited. Overlapping parts cannot be handled and only a finite number of views of a part can be recognized. To completely train such a system we must, thus, be able to enumerate all the possible positions of a solitary part on a planar surface. The current system enumerates stable positions of polyhedra by testing each position for which three non-colinear vertices lie on the table top. This produces a complete list of every orientation in which the part can be stood on a table top. Once this has been done. silhouettes of the part which emulate image quantization and parallox for each position are synthesized from the CAD model and these are used to train the vision system. This procedure for enumerating stable positions may produce superfluous positions in two ways: (1) The list may include positions which are stable, but unlikely to occur. For example, a coin may be stood on its edge, but is likely to fall, so that position should be omitted. (2) The list may include positions which are different, but indistinguishable. For example, a cube, which may stand on each of its six faces, should only be listed with one distinct position. While the inclusion of such superfluous stable positions does not prevent the recognition system from operating correctly, it does slow it down. Consequently, we have investigated the determination of the probability of finding a part in a given stable position. The usefulness of knowing about the probability and similarity of positions is not confined to systems using binary vision. The performance of most vision systems may be improved if the a priori probabilities of different stable positions are available. If we wish to predict the performance of a vision system on a set of parts before its actual installation, knowledge of part probabilities and symmetries is necessary. Thus, there are two major problems to be addressed. (1) Given a part, what are the orientations it may stand in, and what are the probabilities with which these orientations occur. This is similar to rolling irregularly shaped dice. Annual Report 81 August 1, 1984-July 31, 1984

(2) Given a part, how may it be rotated or reflected, so that it still occupies the same spatial domain. To do this, we must locate its lines, planes, and points of symmet rv. Approach Stable Position Probability Estimating the probabilities of different outcomes of rolling an irregular polyhedron raises several difficulties. These probabilities depend not only on the shape of the part, and on the location of its center of mass, but also on the characteristics of the surface it is rolled on. For example, positions in which the part can be easily tipped are generally more likely to occur on an inelastic surface. Furthermore, the probabilities depend on the global geometry of the part because less stable faces tend to "feed" probability into adjacent faces as the part rolls. Because of these characteristics the probabilities cannot be directly computed from the geometry of the part. Instead a probabilistic simulation of the rolling process is used to estimate position probabilities. Stable Position Symmetry In testing for similarity between stable positions of a part, we are actually testing for rotational symmetry. It can be shown that all axes of rotational symmetry must pass through the centroid of the object. In two dimensions, this locates a unique center of rotation, but the 3D problem is more difficult. All possible axes of rotation for a 3D object must also be axes of rotation for both intersected faces, edges or vertices of the part's convex hull. Thus we can find all possible axes of symmetry by testing the axes formed b- the center of each edge, vertex and face, and the center of the object. This produces a set of candidates whose size is no more than a linear function of the number of vertices in the part. Status of Research Stable Position Probability Several algorithms for the estimation of position probabilities have been tested, some with very encouraging results [2], but no completely satisfactory one has yet been found. All have followed the same general scheme. Initial position probabilities are estimated for the point in time when the part first lands on the table. If it is dropped randomly, these are proportional to the solid angle subtended by the corresponding face of the convex hull about the center of mass. For each face, an estimate is made of initial distribution for the magnitude and direction of the part's kinetic energy if it lands first on that face. Using these energy distributions, probabilities of transitions to edgeadjacent positions are computed. These are then applied to estimate the new position probabilities and energy distributions. A fraction of the energy is dissipated with each iteration, so that the simulation terminates when the energy has fallen so low that there is no longer any chance of tipping. The best algorithm to date shows very good agreement with experimental results for elastic surfaces [Figure 3.5.2.1], but is somewhat less accurate when simulating rolls on more inelastic surfaces. It also shows several other desirable characteristics. First, the same energy distribution parameters can be used when different parts of the same material are rolled on the same surface. Second, the final probability is insensitive to August 1, 1984-July 31,1984 82 Annual Report

STABLE POSITION PROBABILITIES THEORETICAL vs. EXPERIMENTAL.83(.4).10(.09).0075(.01) 0(0).06(.06) 0(0) <' T <. ell.83(.83).09 (.12) 0(0).05 (.05),03(.01).37(.41).09(. 09) 0(0).46(.47).07(.04).84 (.31).10 ( 14).05 (.05) 0 (0) 77 (.77) 12(.16).0006(0).10(.07) Computed (experimental) probabilities Asterisks (*) mark unstable positions Figure 3.5.2.1 Annual Report 83 August 1, 1984-July 31, 1984

the amount of force with which the roll is started, so long as it is reasonably large. Stable Position Symmetry Work on symmetry algorithms has only recently begun. Efficient algorithms have been found for two dimensional objects, and for three dimensional objects being rotated around a given axis. These algorithms encode the object into a string so that standard linear pattern matching algorithms can be used to test for symmetry [3], [4]. Future Future experiments with modified algorithms for position probability are still necessary to find algorithms which work for a greater range of surfaces. The 2D symmetry algorithms will be improved to reduce sensitivity to errors in input data, and more general 3D algorithms will be formulated. The optimality of the symmetry algorithm remains to be determined. Finally, both of these sub-systems must be integrated with the manufacturing cell. References [1] Wolter, J.D., RoA.Volz and A.C. Woo, "Generation of Gripping Positions," 4th Jerusalem Conference on Information Technology, May 1984. [2] Woo, A.C., J.D. Wolter and R.A. Volz, "Probabilistic Stable Orientation of Mechanical Components," SIAM Summer Meeting, Seattle, Washington, July 20, 1984. [3] Knuth, D.E., J.H. Morris and V.R. Pratt, "Fast Pattern Matching in Strings," SL4M, J Comp, Vol. 6 No. 2, pp. 323-350, 1977. [4] Manacher, G.K., "An Application of Pattern Matching to a Problem in Geometrical Complexity," Inf Proc Lett, Vol. 5 No. 1, pp. 6-7, May 1976. 3.5.3. Graphical Programming of Robots Investigator: Professor A.W. Naylor, Professor R.A. Volz The Problem and Past Efforts One of the keys to successful factories of the future will be the timely development, debugging and maintenance of software. There are two ways in which to approach these problems. First, one can start with programming for the entire factory floor and move down to the programming of the individual machines. This is the "top down" approach. In the bottom up" approach one starts programming the individual machines and moves up to the entire factory floor. This project is based on the latter approach. Other researchers' work has resulted in the development of language systems [1, 9] and graphical simulation systems for robotics. The graphical simulations are generated from robot languages [6, 7] or CAD/CAM inputs [2, 3, 4, 5]. None of the CAD/CAM oriented graphical systems reported in the literature have actually generated robot pro gramming code from the graphical manipulations. In addition, early efforts in robot languages systems and graphical simulations have neglected adequate mechanisms for handling sensory input and control output [9,10]. That is, mechanisms to allow the user to understand the geometrical relationships between the robot, sensors and actuators August 1, 1984-July 31,1984 84 Annual Report

Figure 3.6.3.1 This figure shows the starting position for the arbitrary pick method. The location plane divides the scene into the foreground (blue) and the background (red) segments. The cursor moves in this plane. The point selected in this figure is the point at which the blue line segment intersects the red line segment. have been neglected in the past. Graphical programming methods will provide simple, efficient, user friendly methods of robot programming. These methods will obviate the need for learning elaborate programming languages. The purpose of this project is to develop an experimental testbed which can be used for the study and creation of tools, methods and techniques for the off-line graphical programming of robots. The emphasis is on the actual graphical programming of robots, and the integration of geometry with logic and the actuator interactions that can occur within the manufacturing cell. The project's approach is to associate conditions and actions with geometry in a natural manner allowing the user to think about them spatially. Such relationships and integration helps the user place the task of programming robots into perspective. As reported in the previous AFOSR annual report, the basic framework of the system has been completed, debugged and demonstrated. This framework included the abilities to * display and manipulate graphical representations of objects and robots, Annual Report 85 August 1, 1984-July 31, 1984

* join objects to form composite objects, or to break apart composite objects, * view from different perspectives with different scales, and to * generate robot code corresponding to the graphical manipulation of the robot. The original system, however, was considerably slower and less user friendly than envisioned in the desired system. It contained no mechanisms for interacting with sensors or actuators and only rudimentary mechanism for entering point locations. As an offshoot of past efforts, a modified PASCAL program -of a portion of the current user interface and PUMA routines were published in [8]. New Results Considerable effort has been spent in the last year increasing the efficiency of the graphical and inverse kinematics routines. In early versions of the systems, a reasonably complex scene was drawn in about 30 seconds. The current system displays the same scene in under two seconds. While this response isnot sufficient for real-time (machine to machine) applications, it is sufficient for the human oriented, off-line programming. Indeed a number of individuals have been favorably impressed by the speed of the system given the hardware and cost limitations. During the past year, the robot figure has been updated to realistically represent the PUIMA robot. The new figure is illustrated in figure 3.5.3.1. A program playback capability has been added to allow the simulation of the program being developed. Graphical Interactions Graphical interaction is required for most of the commands. Presently, the user's interactions are carried out using a two dimensional graphical input device with either a very intuitive use of cursor movements or some utilization of menus. The method of selecting three dimensional points and orientations in space is critical in any robot programming system. In graphical robot programming systems, the method of selection is particularly critical since the user interacts with a two dimensional display and often a two dimension graphical input device. Three methods have been developed to allow the user to select three dimensional points and orientations for the robot using the two dimensional input device. These methods have been termed the drag method, the arbitrary pick method and the line segment pick method. Similar methods are utilized to position objects in the robot's environment. In selecting a three dimensional point using the drag method, the graphical input device is used to move the end-effector of the robot around graphically while continually checking for valid robot positions. This method utilizes one of the buttons on the two dimensional graphical input device to change between the X-Y mode and Z mode. Presently while in the X-Y mode the robot hand is moved along the world X-Y axes, and while in the Z mode the robot hand is moved along the world Z axis, but any coordinate system could be used. When used in this manner, the graphical input device emulates off-line the teaching pendant. This method is also equivalent to defining a three dimensional cursor and allowing it to move though world space using the graphical input device. This method will naturally adapt to a three dimensional graphical input device. Similarly, in selecting an orientation the graphical input device is used as an off-line teaching pendant. August 1, 1984-July 31,1984 86 Annual Report

Figure 3.5.3.2. The location plane has been position to pass through the end effector of the robot. The cursor has been moved to the tip of the end-effector. The coordinates of this selected point are shown in Table 3.5.3.1. In the arbitrary pick method of selecting positions for the robot, the user "picks" an arbitrary three dimensional point directly from the screen. The cursor is considered to be moved in a plane called the active location plane. This plane is always parallel to the viewing plane or the screen. The user also has the ability to control the depth of the location plane in the scene. As this location plane moves though the scene it divides the scene into two parts; a foreground and a background. The foreground contains everything in "front of" the location plane. while the background contains everything "behind" the location plane. Anything which appears in the foreground is displayed in a light blue, while anything that appears in the background is displayed in red. This color scheme functions to give the user a natural sense of depth. This combination of the cursor position on the location plane and the depth of the plane functions to define a three dimensional point. In addition, this method allows the user to choose one of a set of orthogonal views or any arbitrary view and allows zooming. These features permit the three dimensional point to be more precisely chosen. This method is now illustrated by finding the position of the end effector of the robot. Figure 3.5.3.1 shows the starting position. In this figure the location plane separates the scene into the foreground (blue) and the background (red) segments. Since the cursor is on this plane, the three dimensional point selected in this figure is the point at which blue line segment intersects the red line segment. In figure 3.5.3.2 the location Annual Report 87 August 1, 1984-July 31, 1984

plane has been moved so that it passes though the end-effector. The cursor has been moved to the tip of robot's end-effector. The position of this selected point is shown in table 3.5.3.1. Table 3.5.3.1. Coordinate of the selected and target points. x y z initial pick 383.749 -241.186 128.875 refined pick 395.038 -210.796 128.892 target 399.999 -200.000 150.000 Note: Pick points were not best choices, but were choosen to illustrate the method more clearly in these photographs. Figure 3.5.3.3 shows the side view and the orthogonal refinement of the selected point. The position of this refined point is also shown in table 3.5.3.1. Finally, the known position of robot end-effector is shown in table 3.5.3.1. Using an approach similar to one illustrated. this method has yielded favorable preliminary results. Accuracies of 2 mm in the positions along the location plane and an accuracy of about 20 mm in the depth of location plane are easily obtained when viewing a single scene from a viewing distance of 1900 mm without zooming. Multiple views and zooming can vastly inprove these this accuracies. In the line segment pick method the user "picks" a point on the screen near a line segment, and the closest three dimensional point on the line segment is found. Work on this final method is still in progress and will be completed in the near future. Logical Programming with Binary Sensors and Activators One of the special characteristics of this project is the integration of geometry with logic conditions and actions within the robot program. Conditions and response actions are associated with the geometry of the workspace in a natural manner allowing the user to view them spatially. Consequently, the user is more easily able to understand the robot program being developed. The preliminary concepts for the use of binary sensors and actuators and logical programming have been developed. Basically, the system is extended allowing the user to load objects which can have attributes of being a binary sensor or binary actuator. Associated with each sensor and actuator object will be information describing the sense or activation signal. This information would describe, for example, the "active" state of the physical signal as being normally high or normally low permitting the user to view the "on" state of the signal in a consistent manner. These sensors and actuator objects may be manipulated like any other objects in the system. During programming involving conditions these sensor and actuator objects are displayed along with icons on the screen. Each sensor and actuator icon is displayed with two parts; an "on" part and "off" part. For sensors the user is allowed to graphically pick the set of sensors and the condition of each sensor to which he can then associate the desired response. A sensor and its desired state are graphically picked by choosing the appropriate part of the icon August 1, 1984-July 31,1984 88 Annual Report

Figure 3.5.3.3 The right side view of the robot and selected point from figure 3.5.3.4.b. The orthogonal refinement of the point is shown by moving the cursor to the center of the tool. This allows the depth of the point to be more accurately chosen. The coordinates of the selected point are also shown in Table 3.5.3.1. from the screen. Selecting all of the individual conditions which must be simultaneously satisfied specifies a composite condition. Composite conditions with same desired response can also be combined. For actuators, the user can select the set of actuators which are to be simultaneously activated or deactivated. Any condition for which a geometrical location can be defined is displayed on the scene and can be graphically selected. However, there are a variety of conditions to which no geometrical location can be assigned. For example, the condition "have five parts been built" can not be assigned any meaningful geometrical information. For these conditions, the user must initially enter these directly into the system. The last few of these conditions will be displayed along the edges of the scene so that future references to these non-geometric conditions can be graphically selected. Future Insues In the future the binary sensor and actuator concepts, and the logical programming concepts will be implemented. These concepts will utilize non-geometrical control constructs such as looping, branching, procedure and task features. Such features must be defined and implemented. In addition, a program editing mechanism will be implemented Annual Report 89 August 1, 1984-July 31, 1984

permitting the program modifications. This editing mechanism is envisioned as being coupled with the playback simulation capabilities. Analog sensors and actuators must be incorporated into system. Such devices must include at a minimum vision, force feedback and tactile sensors. One approach is to view these devices graphically as objects with classes of properties with each class represented by a separate icon. This approach provides for these devices but does not specifically bind information about the application into the programming system. The greater use of CAD data and relations between the CAD data must be incorporated. This includes the integration of the AFOSR projects for the determination the gripping position and the CAD training of vision systems. The gripping position project will allow the graphical programming system to automatically offer selections for grasping an object. From these selections the user would select the desired gripping position. The graphical programming system could provide information to the CAD vision training system describing the geometry affecting the camera, and describing which objects appear in the application and their desired configurations. In addition, it should be possible to make use of other relations from the CAD data to make inferences for automatically offering three dimensional point and orientation selections. Such uses should allow for the migration of the system toward task level programming instead of point-to-point programming. References [1] Ambler, A.P., "Languages for Programming Robots," NATO Advanced Studies Institute on Artificial Intelligence and Robotics, Barga, Italy, June 1983. [2] Bathor, M. and A. Sigler, "Graphic Simulation for Robot Programming," Proc. of the 4th British Robot Association: Annual Conference, Brighton, U.K., pp. 85-93, May 18-21, 1981. [3] Heginbotham, W.B., M. Dooner, and D.N. Kennedy, "Computer Graphics Simulation of Industrial Robot Interactions," Proc. of the 7th Int. Symp. on Ind. Robots, pp. 169-176, 1977. [4] Heginbotham, W.B., "Computer Graphics and Robots," Aust. Electronics Eng., Vol. 13, No. 1, pp. 14, 16, 18, 22, Jan. 1980. [5] Heginbotham, W.B., "How Computer Graphics Benefit Industrial Robot Technology," Systems (S. Africa) Vol. 9, No. 6, pp. 8, 10-12, June 1979. [6] Kretch, S.J., "CAD/CAM for Robotics," Robot VI Conference, March 2-4, 1982, SME, Detroit, Michigan. [7] Kretch, S.J., "Robot Animation", Mechanical Engineering, Vol. 104, No. 8, pp. 3253, August 1982. [8] Lee, C.S.G. and M. Ziegler, "A Geometric Approach in Solving the Inverse Kinematics of PUMA. Robots," RSD-TR-1-83, Center for Robotics and Integrated Manufacturing, December, 1983. [9] Lozano-Perez, T., "Robot Programming," MIT AI Memo No. 698, December 1982. [10] Rossol, Lothar, "Technological Barriers in Robotics: A Perspective from Industry," First International Symposium of Robotics Research, Bretton Woods, New Hampshire, August 28 - September 2, 1983. August 1, 1984-July 31,1984 90 Annual Report

3.6. Knowledge Representation Investigator: Professor K.B. Irani Problem Description and Previous Results 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 results obtained during the first year of the project are as follows: (1) An extension of the first order predicate language, L called many sorted language with aggregate variables was developed. (2) A sufficient class of knowledge was identified which was useful in expressing certain types of sentences of L, called S-Horn sentences. (3) As application of this form of knowledge representation, a model for horizontally partitioning and distributing database was proposed. New Research Results During the second year of the contract, the following new results have been obtained: (1) A simple syntactic matching procedure is developed as an inference procedure which uses the formatted structure of the knowledge expressed by the ~-Horn formulae. (2) As an application of language, we describe a front-end knowledge-base subsystem which is intended to support the design of a distributed database system. In this system, the L language takes its role as a procedural knowledge representation formalism. The knowledge useful for the knowledge-based system is identified in terms of five axioms schema in LE. (3) A paper entitled "Knowledge Representation Using an Extension of Many-Sorted Language" has been accepted for the First Conference on Artificial Intelligence Applications sponsored by the IEEE Computer Society. Annual Report 91 August 1, 1984-July 31, 1984

Future Research In order to provide greater focus to the research in other areas, future research in this area has been suspended. 3.7. A Generalized Problem-Solving Process Using Heuristics Professor K.B. Irani Previous Research Results: 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 problem-states (or simple states) is the key to a generalized heuristic search for problem-solving [11, [2], [3]. 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. The results obtained during the first year included: 1. Generation of an analytic model representing a general problem, 2. Generation of the algorithm to computer a heuristic of search algorithm A', 3. Illustration of our approach by some puzzle-like problems. New Research Results 1. Application of our approach to a more real-life problem: In addition to several puzzle-like problems illustrated previously, the theorem proving problem, a more complicated and realistic problem, was considered for the application of our problem-solving approach. The theorem proving problem based on resolution refutation is to produce contradiction or refutation from a set of premises and the negated goal formula. The application of our approach to this problem resulted in the fewest literal preference strategy, a well-known heuristic search strategy for the theorem proving problem. 2. Efficiency and complexity of the algorithm to compute the heuristic of A': An analytic model of the problem, from which the algorithm to compute the heuristic is developed, was formulated based on a set of objects of the problem. The August 1, 1984-July 31,1984 92 Annual Report

efficiency and the complexity of the algorithm to compute the heuristic is thus strongly dependent on how one defines a set of objects of the problem. As in the examples illustrated previously, each object of the problem may be defined to be each elementary component of the problem which is the smallest unit in the problem domain that can be described only by itself. On the other hand, an object of the problem may be defined to be a set of all elementary components of the problem. The latter provides the greatest efficiency but the worst complexity of the algorithm for computing the heuristic of A', while the former provides good efficiency and a reasonable complexity of the algorithm when illustrated for some problems. The efficiency and the complexity of the algorithm to compute the heuristic were examined when a set of objects of the problem was defined in various ways. Future Research Direction and Expected Results: As mentioned above, the efficiency and the complexity of the algorithm to compute the heuristic of A' vary with the set of defined objects of the problem. Sometimes, we need to improve the efficiency of search algorithm for the next problem at the expense of the complexity of the algorithm to compute the heuristic, or vice versa, if the present result does not meet the requirement. A methodology will be developed for the automated generation of the new algorithm to compute the heuristic in case the definition of a set of objects of the problem is modified from the current algorithm to compute the heuristic. References [1] Gaschnig, J., "A problem similarity approach to devising heuristics: First results," Proc. IJCAI., 1979. [2] Guida, G. and M. Somalvico, "A method for computing heuristics inproblem solving", Information Sciences 19(251-259), 1979. [3] Pearl, J., "On the discovery and generation of certain heuristics", AI Magazine, Vol. 4, No. 1, Winter-Spring, 1983. 3.8. Metaform Database Interface System Investigator: Professor T. Teorey Problem and Objectives This project involved the design and implementation of 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 particulartasks. This system, when given an entity type, produces a form screen for the 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 need only 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 minimal amount of training, both query and update the database without having to know about the database schema. Another major advantage of the Metaform Annual Report 93 August 1, 1984-July 31, 1984

system is that it automatically generates 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. During the past year the logical design and formal analysis of the Metaform system was completed, including the syntax and semantics of the form screen query and update language. Algorithms for automatically generating form screens from entity - relationship database schemas were developed. 2. Combined research on form screen interfaces was conducted with D. Kochhar resulting in a conference paper. 3. An on-line human factors benchmark of the metaform system was performed. Eighteen subjects were taught the system and then tested. These subjects were divided into three groups based on computer experience, e.g. experts, midrange, and novices. The tutorial was an on-line version of the pilot study's tutorial. Exercises were given periodically to reinforce learning. After the tutorial, an on-line test was administered. Information on the time to read the tutorial, the time to learn the query language, the time to answer the test questions, and the percentage of the test questions correct was gathered. While the experts and midrange subjects learned how to use the query language in an acceptable amount of time, there was a wild variation in the learning time of novices. Consequently, it is difficult to draw conclusions about the results for the novices. A possible reason for the wide variance in the novices is that logical reasoning might be a much more important factor than computer experience. (There are few problems, however, in separating these factors because subjects with more computer experience also had more education and very likely had greater logical reasoning ability). Novices with more education did better than those with less education. It seemed that many of the difficulties were caused by the tutorial and the teaching methods, and, therefore, for many novices, we cannot draw conclusions concerning the performance of novices with the Metaform query language. Part of the problem seemed to involve the tutorial which was designed to quickly teach everyone from novices to experts. Many of the tutorial's explanations, while being good for quickly training midrange people and experts, were insufficient for novices. Additionally, the change from the paper pilot test to an on-line test, while not affecting the midrange and experts enough to be noticed, did seem to effect negatively the novices' performance. August 1, 1984-July 31,1984 94 Annual Report

Future Work (not funded by AFOSR) AFOSR funded work on this project has led to an industrially funded project to continue the work. In order to provide greater focus to the AFOSR funded work, effort on this project is being totally transferred to the industrial project. A new on-line study of the metaform system concentrating on novices is planned. The subject's age, college education, and computer experience will be controlled; spacial memory, logical reasoning, and work speed information will be gathered. A new tutorial targeted especially for novices will be developed. 3.9. User Needs for Information Display Investigator: Professor D. Kochhar Problems and Objectives It is well recognized that from the perspective of the production worker on the assembly line or on the manufacturing floor, any factory information system, integrated or distributed, should be demonstrably easy to use, flexible and, above all, provide access to meaningful and relevant data. Ease of use is a desirable characteristic, but difficult to measure. specify and quantify. It can include any or all of the following: length of time for a user to reach a certain level of proficiency, errors per unit of time or number of operations, time required or number of operations taken to recover from an error, and user attitudes towards the system. It is also known that if users do not like a system, it will not work. An easy to use information and display system would be liked and used by production and shop level users. It is believed that ease of use is enhanced if the user interface is appropriately designed. This research project was initiated to determine what constitutes ease of use and how an appropriately designed display interface could enhance acceptability by the end user. Through a series of human factors experiments, it should be possible to determine how visual display and cognitive factors such as screen design, learning, understanding etc. can be specified for manufacturing and assembly data such that interpretation is error free and performed quickly. New research results obtained: Automobile assembly was selected as an example site where a large number of parts are assembled at many different assembly stations. Assembly parts are presently broadcast on paper forms that use fine grids and an elaborate, complex coding scheme that is often difficult to decipher and recall by the production worker. This results in misbuilds because of missing or incorrectly installed parts, largely because of human error in reading. decoding and interpretation of the parts broadcast. Research conducted to date has identified the human factors issues involved in the feasibility of changing over from a paper based broadcast to a CRT based parts broadcast that is specific to each of the assembly stations. For the experimental investigation that is to follow during 1984-85, two databases have been developed to evaluate the human factors of software and display design. These databases contain information on the coding and description of parts used in assembly. For the first database, the system reort withthe firmost database, the system record is consistent with most of the DBMS environments. This database is implemented using PASCAL/VS and consists of a single Annual Report 95 August 1, 1984-July 31, 1984

compilable module. A program is designed to load the database into memory and to retrieve information contained in it on to the screen according to user inputs. The program consists of two parts: a main part which handles all access to the database and provides the screen support routines, and a second independently compilable segment consisting of a single procedure which displays information on the screen according to the format selected by the programmer. It is this procedure which has to be changed and recompiled in order to try different display formats. When not loaded the database resides in three files: a file for automobile type and the codes describing them; a file for workstations and the locations associated with them; and a file for co-ordinate locations together with their description and permissible code. The database is loaded into memory when the system is started and is maintained there for the duration of the process. A conceptual schema is given in Figure 3.9.1. The second database developed uses the Integrated Graphic System (IGS) to mimic a given paper format on a CRT. Screen generation is automatic; it is only necessary to specify the visual dimensions of letter height and highlighting. In some of the generated formats, it is possible to also show a line drawing of the specific part that is to be assembled at the specific assembly station. Work planned for the ensuing year: (not funded by AFOSR) It is planned to conduct several on-site human factors experiments to resolve key issues in on-line broadcast usage and acceptance, and to determine how parts broadcast Loc.no Descrption iLocoI Loc no I Code no Loc i Code Coden.. Description Figure 3.9.1 August 1, 1984-July 31,1984 96 Annual Report

can best be done at each specific production workstation. An experimental setup has been devised in a local automobile assembly plant. A CRT is positioned at the production worker's station. It is hypothesized that such a parts broadcast system would lead to a decrease in the standard time required to perform a number of assembly jobs, would lead to a reduction in the number of misbuilds, and show a greater degree of user satisfaction among production workers and plant engineers. In this human factors study, the worker is advised to read all required information from the CRT rather than from the paper broadcast sheet. Independent variables in the experiments will include screen format, data redundancy, data highlighting with reverse video, and graphical parts drawings. Dependent variables will include improvements in the time spent in looking at or referring to the screen and (for comparison) the paper sheet, time spent to perform actions, errors in interpretation, and learning time required to reach an acceptable level of performance by a new hire. Subjective indications of user satisfaction will be obtained through the use of a questionnaire such as that developed by EGG Idaho, Inc. for the evaluation of CRT displays. Results obtained from these experiments will provide meaningful information to database and information system designers on what may or may not be assumed about the end user who is/may not be knowledgeable about computers, but has gained much familiarity about assembly or manufacturing operations. Funding for work planned for 1984-85 is being provided by the Ford Motor Company. Annual Report 97 August 1, 1984-July 31, 1984

August 1, 1984-July 31,1984 98 Annual Report

4. Publications 4.1. Journal publication Control of Mechanical Manipulators (1) Kim, B.K. and K.G. Shin, "An Adaptive Model Following Control of Industrial Manipulators," IEEE Transactions on Aerospace and Electronric Systems, Vol. AES-19, No. 6 pp. 805-814, November 1983. (2) Lee, C.S.G., M.J. Chung and B.H. Lee, "An Approach to Adaptive Control for Robot Manipulators," Journal of Robotic Systems, Vol. 1, No. 1, spring 1984. (3) Lee, C.S.G. and B.H. Lee, "Resolved Motion Adaptive Control for Mechanical Manipulators," Journal of Dynamic Systems, Measurement and Control, Vol 106, pp. 134-142, June 1984. (4) Lee. C.S.G., R.C. Gonzalez and K.S. Fu, Tutorial on Robotics, IEEE Computer Society, November 1983. (5) NhcClamroch, N.H., "Sampled Data Control of Flexible Structures Using Constant Gain Velocity Feedback," AIAA Journal Guidance, Control and Dynamics, 1984. (6) Ulsoy, A.G., "Vibration Control in Rotating on Translating Elastic Systems," ASME Journal of Dynamic Systems, Measurement, and Control, Vol. 106, No. 1, pp. 6-14, March 1984. Vision for Robots (1) Jerian, C.P. and R. Jain, "Determining Motion Parameters for Scenes with Translation and Rotation," IEEE Transactions on PAMI Vol. PAMI-6, No. 4, pp. 523-530, July 1984. Improved Robot Programming (1) Woo, A.C. and J.D. Wolter, "A Constant Expected Time, Linear Storage Data Structure for Representing 3D Objects," IEEE Transactions on Systems, Man and Cybernetics, Vol. SMC-14, No. 3, pp. 510-515, May 1984. Annual Report 99 August 1, 1984-July 31, 1984

4.2. Under Review Control of Mechanical Manipulators (1) Mudge. T.N. and J.L. Turney, "Unifying Robot Arm Control," accepted for publication in IEEE Transactions on Industry Applications, November 1984. (2) Kim. B.K. and K.G. Shin, "Minimum-Time Path Planning for Robot Arms with Their Dynamics Included," accepted subject to a minor revision to IEEE Transactions on System, Alan and Cybernetics. (3) Shin. K.G. and S.B. Malin, "A Structured Framework for the Control of Industrial Manipulators," accepted as a regular paper to IEEE Transactions on System, Man, and Cybernetices (4) Gilbert, E.G. and I.J. Ha, "An Approach to Nonlinear Feedback Control with Application to Robotics," accepted for publication in IEEE Transactions on Systems. Man, and Cybernetics, Vol. SMC-14, August 1984. (5) Kim. B.K. and K.G. Shin, "Suboptimal Control of Industrial Manipulators with a Weighted Minimum Time-Fuel Criterion," accepted for publication in IEEE Transactions on Automatic Control, Vol. AC-30, No. 1, January 1985 (to appear). (6) Shin. K. G. and N.D. McKay "Minimum-Time Control of Robotic Manipulators with Geometric Path Constraints," accepted as a regular paper to IEEE Transactions on Automatic Control. Vision for Robots (1) Turney, J.L., T.N. Mudge and R.A. Volz, "Recognizing Partially Occluded Parts," IEEE Transactions on Pattern Analysis and Machine Intelligence, accepted for publication 1985. Architecture of Robot-Based Manufacturing Cells (1) Volz, R.A.,. T.N. Mudge and D.A. Gal, "Using Ada as a Robot System Programming Language," accepted for publication IEEE Transactions on Systems, Man, and Cybernetics, October 1984. (2) Shin, K.G., M.E. Epstein and R.A. Volz, "A Module Architecture for an Integrated Multi-Robot System," submitted to the 18th Annual Hawaii International Conference on System Sciences and IEEE Transactions of Systems, Man and Cybernetics. (3) Volz, R.A., T.N. Mudge, A.C. Woo, J.L. Turney and D.A. Gal, "CAD, Robot Programming and Ada," to appear in book on NATO Advanced Studies Institute on Robotics and Artificial Intelligence, September 1984. August 1, 1984-July 31,1984 100 Annual Report

Improved Robot Programming (1) Wolter, J.D., R.A. Volz and T.C. Woo, "Automatic Generation of Gripping Positions,' accepted for publication in IEEE Systems, Man and Cybernetics, 1985. (2) Woo. A.C, "Interfacing Solid Modeling to CAD and CAM: Data Structures and Algorithms," IEEE Computer, to appear in December 1984. (3) Woo. T.C. and H.C. Lee, "On the Time Complexity of Circumscribing a Convex Polygon," Computer Vision, Graphics and Image Processing, 1985. (4) Woo. T.C. and S.Y. Shin, "A Linear Time Algorithm for Triangulating a PointVisible Polygon," A CM Transactions on Graphics, to appear in 1984. Metaform Database Interface System (1) Kochhar, D.S., D.D. Barash and D.V. Beard, "Display of Manufacturing and Assembly Information," Proceedings of the Conference on Intelligent Systems and Machines, Oakland University, April 24-25, 1984. 4.3. In Preparation Metaform Database Interface System (1) Beard, D.V. and T.J. Teorey, "Automatically Generated Updatable Form Screens as a Database Interface Language," to be submitted to Information Sciences, August 1984. (2) Kochhar, D.S., D. Barash and D. Pincu, "An On-Line Evaluation of Assembly Information," Journal of Manufacturing Systems. (in preparation). 4.4. Conference Presentations Control of Mechanical Manipulators (1) Ulsoy, A.G. and Y. Koren "State Model for Flank Wear in Metal Cutting," American Manufacturing Research Conference, Houghton, Michigan, July, 1984. (2) Chalhoub, N.G. and A.G. Ulsoy, "Dynamic Simulation of a Flexible Robot Arm and Controller," Proceedings of the American Control Concfrence, San Diego, California, June 1984. (3) DeVries, W.R., J.S. Raski and A.G. Ulsoy, "Microcomputer Applications in Manufacturing: A Senior Laboratory Course," American Society of Mechanical Engineers, International Computers in Engineering Conference Chicago, Illinois, August 1983. Annual Report 101 August 1, 1984-July 31, 1984

(4) l'lsoy, A.G., "Vibration Control in Rotating or Translating Elastic Systems," American Society of Mechanical Engineers, Winter Annual Meeting, Boston, Massachusetts, November 1983. (5) Gilbert, E.G. and D.W. Johnson, "The Application of Distance Functions to the Optimization of Robot Motion in the Presence of Obstacles," Conference on Decision and Control, December 12-14, 1984. (6) McClamroch, N.H., "Stabilization of Elastic Systems Using Sampled Data Feedback," Conference on Decision and Control, Las Vegas, Nevada, December 12-14, 1984. (7) Kim. B.K. and K.G. Shin, "An Efficient Minimum-Time Robot Path Planning Under Realistic Constraints," The 1984 American Control Conference, June 1984. (8) Kim. B.K. and K.G. Shin, "Suboptimal Control of Industrial Manipulators with a Weighted Minimum Time-Fuel Criterion," Proceedings of the 22nd Conference on Decision and Control, San Antonio, Texas pp. 1199-1204, December 1983. (9) Lee, C.S.G., B.H. Lee and R. Nigam, "Development of Generalized D'Alembert Equations of Motion for Mechanical Manipulators," Proceedings of the 22nd Conference on Decision and Control, San Antonio, Texas, pp. 1205-1210, December 1983. (10) Lee. C.S.G.. B.H. Lee and R. Nigam, "An Efficient Formulation of Robot Arm Dynamics for Control Analysis and Manipulator Design," Proceedings of the Robotics Intelligence and Productivity Conference, Wayne State University, pp. 82-90, November 17-18, 1983. (11) Lee, C.S.G. and R.H. Smith, "Force Feedback Control in Insertion Process Using Pattern Analysis Techniques," 1984 American Control Conference, San Diego, California, June 6, 1984. (12) Gilbert, E.G. and D.W. Johnson, "Distance Functions and Their Application to Robot Path Planning in the Presence of Obstacles," 18th Annual Conference on Information Sciences and Systems, Princeton University, March 14-16, 1984. (13) Shin, K.G. and S.B. Malin, "A Hierarchical System Structure for Coordinated Control of Industrial Manipulators," Conference on Robotics, Atlanta, Georgia, March 1984. (14) Shin, K.G. and N.D. McKay, "An Efficient Robot Arm Control Under Geometric Path Constraints," Proceedings of the 22nd Conference on Decision and Control, San Antonio, Texas, pp. 1449-1457, December 1983. August 1, 1984-July 31,1984 102 Annual Report

(15) Gilbert, E. and l.J. Ha, "An Approach to Nonlinear Feedback Control with Applications to Feedback," 22nd Conference on Decision and Control, San Antonio, Texas, December 1983. (16) Shin, K.G. and N.D. McKay, "Open-Loop Minimum-Time Control of Mechanical Manipulators and Its Application," 1984 American Control Conference, June 1984. (17) Shin, K.G. and N.D. McKay, "Robot Path Planning Using Dynamic Programming," accepted for presenting at 23rd Conference on Decision and Control, December 12-14, 1984. (18) Ulsoy, A.G. and L.K. Lauderbaugh, "High Performance Process Control Systems for Machine Tools," Proceedings of the 11th NSF Grantees Production Engineering and Technology Conference, May 1984. (19) Ulsoy, A.G., "Reduced Sensitivity Linear Controller Design Using State Rate Feedback," ASME Winter Annual Meeting, New Orleans, Louisiana, December 1984. Integrated Solid-State Sensors for Closed-Loop Robot Control (1) Chun. KI.J. and K.D. Wise, "A High-Performance Silicon Tactile Imager Based on a Capacitive Cell," The let World Conference on Robotics Research, Bethlehem, Pennsylvania, August 14-16, 1984. (2) \ise. K.D., "Recent Development in Solid-State Sensors," presented in Chicago and Pittsburgh. May, 1984. Vision for Robots (1) Healey, G. and R. Jain, "Depth Recovery From Surface Normals," Proceedings of the International Conference on Pattern Recognition, Montreal, Canada, JulyAugust 1984. (2) Shah, M., and R. Jain, "Detecting Time Varying Corners" Proceedings of the International Conference on Pattern Recognition, Montreal, Canada, July-August 1984. (3) Jain, R., "Architecture for Computer Vision Systems," IEEE Workshop on Computer Architecture for Patten Analysis and Image Data Bases, Pasadena, California, December, 1983. (4) Jain, R. "Matching Pyramids," IEEE Workshop on Computer Architecture for Pattern Analysis and Image Data Bases, Pasadena, California, December 1983. (5) 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 Workshop on Computer Architecture for Pattern Analysis and Image Data Base Management, pp. 56-60, October 1983. Annual Report 103 August 1, 1984-July 31, 1984

(6) Delp, E.J., "Adaptive Gray-Scale Mapping to Remove Registration Noise in Difference Images," Allerton Conference, University of Illinois, November, 1983. (7) Delp. E.J., "Analysis of Sequential Edge Operator," Allerton Conference, University of Illinois, November, 1983. (8) Mudge, T.N. and T.S. Abdel-Rahman, "Efficiency of Feature Dependent Algorithms for the Parallel Processings of Images," Proceedings of the International Conference on Parallel Processing, pp. 369-373, August 1983. (9) 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 Intelligent Robots, SPIE Vol. 449 (part 2), pp. 719-725, November 7-10, 1983. Improved Robot Programming (1) Wolter, J.D., R.A. Volz and A.C. Woo, "Automatic Generation of Gripping Positions." 4th Jerusalem Conference on Information Technology, May 1984. (2) WNoo. A.C., J.D. Wolter and R.A. Volz, "Probabilistic Stable Orientation of Mechanical Components," SIAM Summer Meeting, Seattle, Washington, July 20, 1984. (3) Shin. K.G., R.A. Volz and V. Rajlich, "A Holistic Approach to the Design and Analysis of Versatile Robot Languages," Proceedings of COMPSAC'83, pp. 250263. (4) Volz. R.A., "Robot Programming Languages and Program Complexity," presented at CAM-i Conference, St. Louis, Missouri, December 1983. Metaform Database Interface System (1) Kocchar, D.S., D.D. Barash and D.V. Beard, "Display of Manufacturing and Assembly Information," Proceedings of the Conference on Intelligent Systems and Machines, Oakland University, April 24-25, 1984. 4.5. Technical Reports (Topics not covered in technical paper or conference only listed) (1) Jain, R. "Complex Logarithmic Mapping and the Focus of Expansion", RSD-TR15-83, Center for Robotics and Integrated Manufacturing, University of Michigan, Ann Arbor, Michigan, November 1983. (2) Atkins, D.E., R.A. Volz & Staff, "First Annual AFOSR Report- Coordinated Research in Robotics and Integrated Manufacturing," RSD-TR-16-83, Center for Robotics and Integrated Manufacturing, University of Michigan, Ann Arbor, Michigan, October 1983. August 1, 1984-July 31,1984 104 Annual Report

(3) Frieder, G. and M.Lee, "Software Support for the Stereo Camera: Phantom and Measurment Programs", RSD-TR-17-83, Center for Robotics and Integrated Manufacturing, University of Michigan, Ann Arbor, Michigan, November 1983. (4) Zarrugh, M.Y. and Y-Jeng, "Structural Aspect of Robot Performance," RSD-TR18-83, Center for Robotics and Integrated Manufacturing, University of Michigan, Ann Arbor, Michigan, November 1983. (5) Delp. E.J. and N. Ansari, he Use of the DeAnza IP6400 Image Processor for Local Window Operations," RSD-TR-1-84, Center for Robotics and Integrated Manufacturing, University of Michigan, Ann Arbor, Michigan, January 1984. (6) Healey, G. and R. Jain, "Depth Recovery from Surface Normals," RSD-TR-3-84, Center for Robotics and Integrated Manuafacturing, University of Michigan, Ann Arbor, Michigan, March 1984. (7) McClamroch, N. Harris, "Stabilization of Elastic Systems Using Sampled Data Feedback," RSD-TR-4-84, Center for Robotics and Integrated Manufacturing, University of Michigan, Ann Arbor, Michigan, March 1984. (8) Khan, N.A. and R. Jain, "Component Correspondence for an Imprecise Object Description and its Model", RSD-TR-8-84, Center for Robotics and Integrated Manufacturing, University of Michigan, Ann Arbor, Michigan, March 1984. (9) Eichel, P.H. and E.J. Delp, "Quantitative Analysis of Moment Based Edge Operation." RSD-TR-5-84, Center for Robotics and Integrated Manufacturing, University of Michigan, Ann Arbor, Michigan, April 1984. (10) \Wielenga, T.J., "Simplifications in the Simulation of Mechanisms Containing Flexible Members," RSD-TR-6-84, Center for Robotics and Integrated Manufacturing, University of Michigan, Ann Arbor, Michigan, April 1984. (11) Gilbert, E.G. and D..W. Johnson, "Distance Functions and Their Application to Robot Path Planning in the Presence of Obstacles," RSD-TR-7-84, Center for Robotics and Integrated Manufacturing, University of Michigan, Ann Arbor, Michigan, April 1984. (12) Antonelli, C.J., R.A. Volz and T.N. Mudge, "Simulation Languages Suitable for Semi-Automatic Manufacturing Cell Modelling," RSD-TR-8-84, Center for Robotics and Integrated Manufacturing University of Michigan, Ann Arbor, Michigan, May 1984. (13) Shin, K.G., M.E. Epstein and R.A. Volz, Module Architecture for an Integrated Multi-Robot System," RSD-TR-9-84, Center for Robotics and Integrated Manufacturing, Univesity of Michigan, Ann Arbor, Michigan, July 1984. Annual Report 105 August 1, 1984-July 31, 1984

August 1, 1984-July 31,1984 106 Annual Report

5. Personnel 6.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 Engineering and Computer Science Gideon Frieder -- Electrical Engineering and Computer Science Elmer G. Gilbert -- Aerospace Engineering Robert M. Howe -- Aerospace Engineering Keki B. Irani -- Electrical Engineering and Computer Science Yoram Koren -- Mechanical Engineering and Applied Mechanics Emmett N. Leith -- Electrical Engineering and Computer Science Arch W. Naylor -- Electrical Engineering and Computer Science N. Harris McClamroch -- Aerospace Engineering Richard A. Volz -- Electrical Engineering and Computer Science Kensall D. Wise -- Electrical Engineering and Computer Science Associate Professors James Barber -- Mechanical Engineering and Applied Mechanics Ramesh Jain - Electrical Engineering and Computer Science Dev S. Kochhar -- Industrial and Operations Engineering Trevor N. Mudge -- Electrical Engineering and Computer Science Kang G. Shin o- Electrical Engineering and Computer Science Toby Teorey - Electrical Engineering and Computer Science Anthony C. Woo - Industrial and Operations Engineering Assistant Professors Edward J. Delp - Electrical Engineering and Computer Science C. S. George Lee -- Electrical Engineering and Computer Science A. Galip Ulsoy -- Mechanical Engineering and Applied Mechanics Joseph Whitesell - Mechanical Engineering and Applied Mechanics Mohamed Zarrugh - Mechanical Engineering and Applied Mechanics Annual Report 107 August 1, 1084-July 31, 1084

6.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 a 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 EECS1 Ph.D. expected 1984-85 Dan Angell EECS Ph.D. expected 1985-86 Dan Barash IOE2 Ph.D. expected 1984 David V. Beard CICE3 Ph.D. expected 1984 Paul Besl EECS Ph.D. expected 1985-86 Paul Bixel EECS B.S. expected 1984 Nabil Chalhoub ME&AM4 Ph.D. expected 1984 Ii Hyun Choi ECE Ph.D. expected 1984-85 Henry Chu CICE Ph.D. expected 1984-85 Kukjin Chun ECE Ph.D. expected 1985 Ari Covrigaru EECS M.S. expected 1984-85 Mark Epstein CICE M.S. 1984 David Gal CCS5 M.S. 1983 In-Joong Ha CICE Ph.D. expected 1984-85 Susan Haynes EECS Ph.D. expected 1986-87 Jeff Hill CICE M.S.E. 1983 H.P. Huang ECE Ph.D. expect 1985-86 Electrical Engineering and Computer Science 2Industrial Operations Engineering 3Computer Information and Control Engineering 4Mechanical Engineering and Applied Mechanics 6Computer and Communication Sciences August 1, 1984-July 31,1984 108 Annual Report

Charles Jerian CICE Ph.D. expected 1985 Dan Johnson AE6 Ph.D. expected 1984-85 Richard Jungclas CICE Ph.D. expected 1985 Hi-S Kim CICE Ph.D expected 1985 Jehkwan Lah ECE Ph.D. expected 1984 Bum. H. Lee, CICE Ph.D. expected 1984 G-H Lee CICE Ph.D. expected 1986 Kurt Lloyd B.S. expected 1984 Neil D. McKay ECE Ph.D. expected 1984 Andrew Meltzer CICE B.S. expected 1984 Bernard Morgowicz AE Ph.D expected 1984-5. Joseph Pincu IOE Ph.D. expected 1986-87 Ronitt Rubinfeld B.S. EECS expected 1986 Elesh Shah CICE M.S.E. expected 1984 Dong G. Shin CICE Ph.D. expected 1984 M. Steigerwald ME&AM Ph.D. expected 1986 S. I. Yoo CICE Ph.D. expected 1985-86 5.3. Degrees Awarded Jeff Hill M.S.E. in CICE 1983 Thomas Wielenga Ph.D. in ME&AM 1984 Joseph Pincu M.S.E. in IOE 1984 Dan Barash M.S.E. in IOE 1984 Paul Firehammer M.S.E. in CICE 1984 Nirwan Ansari M.S.E. in EECS 1984 David Gal M.S. in CCS 1983 Mark Epstein M.S.E. in CICE 1984 Neil Nathanson M.S. CCS 1984 Shi Chan Tsang M.S. in IOE 1984 Glen Healey B.S. in EECS 1984 Elesh Shah M.S.E. in CICE 1984 6Aerospace Engineering Annual Report 109 August 1, 1984-July 31, 1984

5.4. Graduate Student Placement 1982 - 1983 Gary Swanson, Ph.D. Lincoln Labs Henry Chu, M.S. U of M Ph.D. Program Paul Eichel, M.S. U of M Ph.D. Program Stacy Leon, M.S. U of M Ph.D. Program Mike Steigerwald, M.S. U of M Ph.D. Program Jan Wolter, M.S. U of M Ph.D. Program Brian Dent, M.S. ADAPCO, Melville, New York Myrung Chung Ph.D. Korean Institute of Technology Dean Askounis M.S. FMC Robots, Troy, Michigan 1983 - 1984 Thomas W\ielenga, Ph.D. M.D.I., Ann Arbor, Michigan Joseph Pincu, M.S. U. of Ph.D. Program Daniel Barash, M.S. Harris Corporation, Washington, D.C. Paul Firehammer, M.S. unknown Nirwan Ansari, M.S. U of M Ph.D. Program David Gal, M.S. R.O.L.M. in California Mark Epstein, M.S. IBM, Boca Raton, Florida Neil Nathason, M.S. IBM, Toledo, Ohio Chi-Chan Tsang, M.S. Computerized Office Systems, Ann Arbor Glen Healy, B.S. Stanford Graduate Program Elesh Shah, M.S. unknown 5.5. Permanent Staff Research Engineer John Caldwell Jerry Turney Systems.Programmer Charles Lake Ron Theriault Technician Rob Giles August 1, 1984-July 31,1984 110 Annual Report

A dministratite Assiatant Jerry L. Jackson Secretaries Frances Bourdas Virginia Folsom Mary Ann Pruder Shirine Repucci Annual Report 111 August 1, 1984-July 31, 1984

August 1, 1984-July 31,1984 112 Annual Report

6. Coupling Activities An important aspect of our program is the development 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. The following sections describe the coupling activities which have taken place during the past year. 6.1. Intra Project Interactions The interactions begun last year within the project have continued and grown. Frequent seminars held with both internal and external speakers provided a means of keeping everyone generally aware of work both within our project and at other institutions around the country. Indeed, at times the frequency of seminars was so high that it was difficult for any one person to attend all of interest. The joint seminar series sponsored by CRIM and the Industrial Technology Institute enabled us to bring truly outstanding speakers from both industry and academia to Michigan. The direct technical interactions anticipated in last year's report have largely developed as expected. While the direct technical interactions among subgroups is far from totally connected, a number of significant connections have taken place, and more are developing for the future. The kinematic and dynamic equations developed by Professor Lee and his students are in regular use both in the real time simulation project and in the graphical robot programming system. The generic robot cell and graphical programming subprojects described in Secs. 3.4 and 3.5 are the results of successful interaction among four subprojects. And the two groups working on user interfaces to manufacturing databases have joined forces to synergistically address different aspects of the problem. In addition, the vision and computer architecture groups have laid plans for beginning the development of a rapid prototyping vision system during the next year. There are regular technical discussion meetings among members of several of the research groups occurring on a weekly basis. Membership in more than one group is common, particularly among the faculty concerned. Also, most of the faculty are members of several doctoral committees on topics outside of their own immediate research activities. This has proven to a useful form of information diffusion. 6.2. University Interactions Interactions with people from other universities have taken place primarily through seminars, both those given at the University of Michigan, and those given by Michigan Annual Report 113 August 1, 1984-July 31, 1984

people at other universities. Outside Seminar Speakers Among those presenting seminars at Michigan are: * Alexander Meystel, Associate Professor of Electrical Engineering, University of Florida "Knowledge Representation and Motion Planning" * Daniel B. DeBra, Professor of Aeronautics and Astronautics, Stanford University "Overcoming Disturbance Limitations in Ultra Precision Machining" * Paul Wright, Associate Professor of Mechanical Engineering and Project Leader, Robotics Institute, Carnegie-Mellon University'The Physics of Assembly in Flexible Manufacturing Cells" * Michael Brady, Senior Research Scientist, Artificial Intelligence Laboratory, Massachusetts Institute of Technology "Artificial Intelligence and Robotics" * Shimon Nof, Purdue University "New Tools for Planning Robotic Assembly Systems" * Sharat Israni, University of Wisconsin "Support Systems and Flame Cutting" K.K. Wang, Cornell University'Computer Aided Injection Molding System" * David Bourne, Carnegie-Mellon University'Computational View of Flexible Manufacturing Systems" * Leon Harmon, Case Western Reserve University'Touch Sensing for Robots" * A.K. Kochhar, University of Bradford/England "Computer Integrated Manufacturing and Its Applications" * John Bolling, University of Wisconsin/Madison "Automated CAD Programming of Commerical Robots" * B.F. Von Turkovich, Professor of Engineering and Material Science, University of Vermont "Process Modeling in Flexible Manufacturing Systems" * S.M. Wu, Research Professor in Manufacturing Engineering, University of Wisconsin, Madison "Precision Engineering without Precise Machinery" * Roger Nagel, Professor Electrical and Computer Engineering and Director of Insitute for Robotics, Leigh University "Robot Software: Current Practices and Future Challenges" * D. Teneketzis, MIT "The Decentralized Quickest Detection Problem" * M. Cutkosky, Carnegie-Mellon "Precision Parts Handling for Flexible Manufacturing" August 1, 1984-July 31,1984 114 Annual Report

* T. Weymouth, University of Massassachusetts "Using Object Descriptions in a Schema Network for Machine Vision:" * Jehuda Tirosh, Technion, Irasel "Upper Bound on the Kinetic and Dynamic Loads Responded by Stationary Tools During High Rate Plastic Forming" * Steven Nahmias, University of Santa Clara "Optimal Policy for a Two-Stage Assembly System Under Random Demand" * Peter Dewhurst, Associate Professor of Mechanical Engineering, University of Massachusetts "Identifying the Correct Assembly System - The First Step in Design for Economic Assembly" 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 * Technion in Haifa, Israel - R.A. Volz "Model Drive Vision and Robot Systems" * Western Michigan University, Kalamazoo, Michigan - C.S.G. Lee "Robot Arm Kinematics" * K.D. Wise presented seminars at Oakland University, Leigh University, and UTC Graduate Study Program. * Wright State University, Dayton, Ohio - C.S.G. Lee "Robot Arm Control" 6.3. Interactions with Industry Interactions with industry have taken place in three forms, seminars presented to industry, seminars presented at Michigan and private technical discussions. 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. Appendix B contains the current membership list in the Affiliates. Major technical briefings were held at the University for the following firms: CALMA Company Ford Motor Company Whirlpool United Technologies Research Center Bell Laboratories Hughes Aircraft Company Hoover/NSK Sperry-Vickers Company Hewlett Packard Company Chrysler Corporation Bechtel Corporation Systems Research Inst. Dow Chemical Corporation Apollo Computer Annual Report 115 August 1, 1984-July 31, 1984

Apple Computer Informatics General Corporation Elbit Rockwell International Gould Lockheed Missiles & Space Co. Eaton Corporation General Electric Matsushita United Technologies SAAB/SCANIA KMS Fusion/NASA * R.A. Volz chaired a two day Management Briefing Seminar on "Robotics and the Factory of the Future" * R. A. Volz presented a seminar on "Model Driven Vision and Robot Systems" at General Electric * K.G. Shin has presented a seminar on "Robot Path Planning by Phase Plane Plot and Dynamic Porgramming Methods" at GM Research Lab * C.S.G. Lee made a presentation at the monthly meeting of the Michigan Robotics Research Circle entitled "Robotics Education at Michigan". * K.D. Wise presented seminars at the following corporations and laboratories: General Motors, Abbott Laboratories, Gould, Westinghouse, SRC and Michigan Technology Council o T.N. Mudge presented a paper entitled, "Intel 432 Based Manufacturing Cell," at the ASEE Annual Conference in Rochester, New York, September 1983. e A.G. Ulsoy presented an invited seminar entitled "Adaptive Control Systems for Machine Tools" at General Motors Research Laboratories. Seminars at Michigan by Industrial People * Gerard LeLan, Institut National De Rechercher en Informatique et en Automatique "Real-Time Local Area Networks" * Richard Kegg, R&D Machine Tools, Cincinnati Milacron "The Batch Manufacturing Factory of the Future" * Jerome A. Smith, President, Industrial Technlogy Institute, "An Overview of the Industrial Technology Institute" ~ John E. Mayer, Jr, Director of Staff Engineering, Kennametal, Inc. "Cutting Tool Automation and Sensing" * Dr. Ernie Kent Leader, Computer Vision, National Bureau of Standards "Robot Vision at the National Bureau of Standards" * Bria.n G. Schunck, General Motors Research Laboratories "Motion Segmentation and Estimation" * Edward Dorrah, Martin-Marietta "Work in Intelligent Task Automation at Martin-Marietta" August 1, 1984-July 31,1984 116 Annual Report

Private technical discussions with industry * D.S. Kochhar meets regularly with Ford Motor Company regarding human-machine (displays) in body and assembly operations. * N.H. McClamroch met with Sperry Vickers, Inc. * Discussions were held with Raycon Corporation; a division of Excello, on interferometric methods applied to robotic vision. This is a continuing relation, involving E. Leith and graduate students D. Angell and S. Leon. * R. Jain meets regularly with GM Research Lab and ERIM. * C.S.G. Lee has met with Ford Scientific Research Lab., Dearborn, Michigan and Aerospace Corporation, El Segundo, California. o R.A. Volz, A. Naylor, A.C. Woo and K.G. Shin discussed scheduled and control of automatic guided vehicles with Volvo of America. * R. Howe and B. Morgowicz developed a dynamic simulation of an automatic guided vehicle for Volvo of America. * R.A. Volz and A. Naylor discussed research direction in robotics with personnel at the General Motors Research Center. 6.4. DoD Interaction The following interactions with DoD have taken place during the past year. * A. Rosenstein from AFOSR visited Michigan for an informal review in October 1983. * A formal review of the project was held in January of 1984. * R.A. Volz, C.S.G. Lee, and N.H. McClamroch visited WPAFB in February of 1984. * C.S.G. Lee presented a seminar at the Air Force Insitute of Technology, Dayton Ohio, March 1984. * D. Atkins and R.A. Volz attended a contactees meeting in May of 1984. * R.A. Volz, T.N. Mudge and R. Jain visited DARPA in May of 1984 to discuss possible interactions. * R. Jain visited ONR in May of 1984 to discuss possible interactions. Annual Report 117 August 1, 1984-July 31, 1984

August 1, 1984-July 31,1984 118 Annual Report

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 TechnolStanford, CA 94305 ogy Cambridge, MA 02139 Professor Robert McGhee Dept. of Electrical Engineering Dr. David Nitzen Ohio State University Director of Robotics Research 2015 Neil Avenue Stanford Research Institute Columbus, OH 43210 333 Ravenswood Avenue Menlo Park, CA 94025 Professor Raj Reddy Computer Science Dept. & Robotics Dr. Robert Bolles Carnegie Mellon University Stanford Research Institute Schenley Park 333 Ravenswood Avenue Pittsburgh, PA 15213 Menlo Park, CA 94025 Professor Michael Brady Dr. William Brown 545 Technology Square Labs ERIM Massachusetts Institute of Technol- P.O. Box 8618 ogy Ann Arbor, MI 48107 Cambridge, MA 02139 Dr. Azriel Rosenfeld Professor Richard Paul Research- Room 4115C Dept. of Computer Information Computer & Space Sciences Bldg. and Sciences University of Maryland University of Pennsylvania College Park, MD 20742 N60 Town Bldg. Philadelphia, PA 19104 Dr. Geoffrey Boothroyd Mechanical Engineering Professor Roger Nagel University of Massachusetts Lehigh University Amhurst, MA 01003 Bethlehem, PA 18015 Dr. Jerome Smith Professor Georges Saridis Industrial Technology Institute ECSE University of Michigan Rensselaer Polytechnical Institute 230 Stearns Troy, NY 12181 Ann Arbor, MI 48109 Professor Delbert Tesar Dept. of Mechanical Engineering University of Florida Gainsville, FL 32611 Annual Report 119 August 1, 1984-July 31, 1984

Government Dr. Vincent Russo Mr. Micky Hitchcock Dr. James Albus Wright Patterson Air Force Base Room A127 Bldg 220 AFWAL/NLBE National Bureau of Standards Wright Patterson, OH 45433 Washington D.C. 20234 Mr. William M. Spurgeon Dr. George Brosseau Program Director Room 1121 Production Research NSF Division of Mechanical Engineering Washington D.C. 20550 & Applied Mechanics NSF Mr. Norman Caplan 1800 Go Street N.W. Deputy Division Director Washington D.C. 20550 Division of Electrical, Computer & Systems Engineering Dr. Nam Suh NSF NSF 1800 G. Street N.W. 1800 G. Street N.W. Washington D.C. 20550 Washington, DC 20550 Mr. Bernie Chern Mr. G. Ronald Green Division of Electrical, Computer & Electronics Division System Engineering U.S. Army Research Office Room 1101 PoO. Box 12211 NSF Research Triangel Park, NC 27709 Washington D.C. 20550 Mr. Theodore J. Brandewie Captain Robert Delyser Project Manager DFEE Computer Integrated U.S. Air Force Academy Manufacturing Branch Colorado 80840 Department of Air Force Air Force Wright Aeronautical Lab Dr. James Gault Wright Patterson Air Force Base, U.S. Army Research Development Ohio 45433 Standardization Group United Kingdom Mr. Daniel Herman P.O. Box 65 NASA Headquarters FPO New York 09510 Code S Washington DC, 20546 Mr. Marvin Denicoff Dept. of Navy Information Sciences Dept. Office of Naval Research 800 N. Quincy Arlington, VA 22217 August 1, 1984-July 31,1984 120 Annual Report

Industry Mr. Donald A. McMillan Helfrecht Machine Company Mr. Bertil Thorvaldsson 414 S. Hamilton Street ASEA Saginaw, MI 48605 Industrial Robot Division 16250 W. Glendale Mr. Pete Matheson New Berlin, WI 53151 Mr. Emil Sarpa Mr. Anthony Anderson Mr. David Kaminski Intel Corporation Dana Corporation 26500 Horthwestern Highway Technical Center Southfield, MI 48075 8000 Yankee Road Ottawa Lake, MI 49267 Mr. J.L. Escover Mr. Robert Casey Mr. R. Gary Diaz Lockheed General Dynamics Missiles and Space Company, Inc. Land Systems Division P.O. Box 1700 P.O. Box 1901 Austin, TX 78760 Warren, MI 48090 Mr. Richard Barron Mr. William Little Northern Telecom Inc. Mr. Robert Roy P.O. Box 1222 General Electric Minneapolis, MN 55440 P.O. Box 17500 Orlando, FL 32860-7500 Mr. Dwight Carlson Perceptron Mr. Victor Stofonovich 23920 Freeway Park Drive General Electric Farmington Hills, MI 48024 P.O. Box 8106 M/S PR-1 Charlottesville, VA 22909 Mr. Clifford T. Anglewicz Volvo of America Corporation Mr. William Gruver Volvo Automated Systems Division General Electric 40712 Brentwood Drive Industrial Automation - Europe Sterling Heights, MI 48078 Praunheimer Landstrasse 50 6000 Frankfort/Main 90 Dr. Gale Cutler West Germany, 0611-76071 Whirlpool Monte Road Dr. Steve Holland Benton Harbor, MI 49022 Dr. Brian Schunck Mr. Frank DiPietro Dr. John Klein Mr. Gerald Elson IBM Mr. Gabe Tiberio 1798 NW 40th Street Mr. Richard Beecher Boca Raton, FL 33432 General Motors General Motors Research Laboratories Warren, MI 48090 Annual Report 121 August 1, 1984-July 31, 1984

UNIVERSITY OF MICHIGAN 3 911111 111 1115 02493 8451 3 9015 02493 8451