Algorithmic and Geometric Aspects of Robotics (Routledge Revivals)

Jacob T. Schwartz, Chee-Keng Yap, Jacob T. Schwartz, Chee-Keng Yap

• Publisher: Routledge
• Year: 2016
• ISBN:
  9781315471433
• Edition: 1
• Topic: Informatica
• Subtopic: Programmazione di giochi

First published in 1987, the seven chapters that comprise this book review contemporary work on the geometric side of robotics. The first chapter defines the fundamental goal of robotics in very broad terms and outlines a research agenda each of whose items constitutes a substantial area for further research. The second chapter presents recently developed techniques that have begun to address the geometric side of this research agenda and the third reviews several applied geometric ideas central to contemporary work on the problem of motion planning. The use of Voronoi diagrams, a theme opened in these chapters, is explored further later in the book. The fourth chapter develops a theme in computational geometry having obvious significance for the simplification of practical robotics problems — the approximation or decomposition of complex geometric objects into simple ones. The final chapters treat two examples of a class of geometric 'reconstruction' problem that have immediate application to computer-aided geometric design systems.

1 The Challenge of Robotics for Computer Science

John E. Hopcroft
Dean B. Krafft
Cornell University

Abstract

Computer scientists have the opportunity to make contributions to the field of Robotics in a way that traditional engineering disciplines cannot. This chapter describes some of the opportunities, problems, and challenges that Robotics poses for computer science. Fundamentally, these fall into the area of representing and reasoning about physical objects, tasks, and processes—an area that we call stereo-phenomenology.

1. What is Robotics?

The traditional view is that robotics is the study of designing, controlling, and instrumenting robots. These topics form an essential part of the field of robotics. They have been, and are continuing to be, successfully investigated by researchers in engineering disciplines.

Robots manipulate physical objects in accordance with a set of predefined instructions and, possibly, sensory input from the workspace. General-purpose programmable robots differ from computer-controlled hard automation, which has long been the province of the mechanical, electrical and industrial engineer, in that they are not specialized for a single problem. Instead, they can potentially perform arbitrary physical manipulations.

Robots can be used simply as a replacement for hard automation. They can be programmed, with a teach pendant perhaps, for a specific task. When the task changes, rather than scrapping the production line, the robots need only to be reprogrammed for the new task. However, this is a rather limited use for a very powerful tool.

By making use of off-line programming, a robot system can provide more powerful capabilities and deal with much more complex situations. For example, information from a computer-aided-design database can be used to control machining or assembly. The robot can make use of sensory feedback to guide its actions. If it detects errors, it can take alternative actions to correct the problem and proceed with the task. Finally, off-line programming allows the system to deal with variations in the objects or processes it is handling, without having had all the cases preprogrammed by hand.

However, off-line programming brings with it new requirements. Programmers can no longer make use of the actual robot and physical prototypes to answer all their questions about position, action and movement. Instead, there need to be computer models of the workspace and the objects being manipulated. The robot task can then be described in terms of these models.

The next step in sophistication immediately suggests itself. If the robot system has models of the physical objects with which it is dealing, why not make use of these models to simulate and reason about the objects? This would allow robot programmers to work at a much higher level, saving time and reducing the chance for error. Such reasoning might allow the robot system: to figure out a grip, to plan motion, to determine the stability of an assembly (and thus how to move it from one location to another), to understand the behavior of nonrigid objects (when picking up a pair of pliers, for example), and so forth

This leads to a much broader view of robotics. Areas involving high-level programming, reasoning about objects, and perception are qualitatively different from the issues involved in designing, controlling and instrumenting robots. The problems and goals are much less clear, and the techniques required to elucidate and solve them are very different. It is in dealing with these areas that computer science can make great contributions.

The study of robotics and physical systems is a natural step for computer science. Computer science was mostly begun by numerical analysts, physical scientists and engineers. Moving from scientific applications, the discipline drew into itself to develop a set of fundamental intellectual tools. Having specialized in developing representations and languages and in reasoning about abstractions, computer scientists are now well prepared to attack complex applications in other disciplines. The field is turning outward and applying its tools and knowledge in a broad range of areas, of which robotics is one of the most important.

The process or applying computer science to robotics has already begun. Researchers are studying problems in robot language design, motion planning, fine motion strategies, and many others. The AI community has been studying certain aspects such as vision and navigation for years. However, a much wider application of computer science tools to the problems of robotics is needed.

In this paper we sketch out some ideas, suggestions and challenges for the field of computer science. Although these were inspired by the problems of robotics, as we shall see in the next section, they are applicable to a much wider range of problems and disciplines. This paper is intended to provoke thought and discussion, not to provide answers. If the paper gets existing robotics researchers thinking in new ways and new researchers interested in the problems of robotics, then the authors will have achieved their goal. We are convinced that, whatever the effect of this paper, the area of research we are outlining is difficult, exciting, and critically important. Over the next decade, it will become a vital area of computer science research.

2. A New Science

The problems and potential benefits of representing and reasoning about physical objects and processes extend far beyond the realm of robot arms. At the simplest level, representation techniques clearly extend to controlling and reasoning about other automated production equipment. Thus, numerically controlled milling machines, lathes, and drill presses, automated parts handling systems, and even typical hard automation machinery could all be described and reasoned about in a general system of physical object representations.

Consider a computer-integrated manufacturing system. Such a system could involve graphics-based computer-aided design for specifying individual parts and simple assemblies, an off-line programming/simulation system for controlling individual workcells, and finally, a production control system to manage parts flow throughout the factory. Currently, integrated systems of this type are constructed on an ad hoc basis for a single factory application (when they are possible at all). The existence of general systems that could represent physical objects and processes and use that information to control production machinery would greatly simplify the design and implementation of truly integrated manufacturing facilities.

Moving on to engineering analysis, consider the problem of prototyping. Currently, verifying the behavior of a mechanical assembly almost always requires building a physical prototype. Not only is this a time-consuming and expensive process, but later design changes frequently require scrapping the prototype and starting again. Worse yet, there are situations where a physical prototype cannot answer necessary questions about the design. It is easy to imagine a satellite having an antenna system that, when fully deployed, cannot support its own weight under normal gravity. It seems extremely difficult to verify the correctness of the deployment process for such an antenna without using computer-based object representation and simulation techniques. Accurate electronic prototyping to determine correct operation, stability, behavior under mechanical and other loads, and so forth would be quicker, less expensive, more flexible, and potentially more informative than current physical prototyping techniques. What is needed is the scientific knowledge about representing physical objects that guarantees that the electronic prototype is as accurate as the physical one.

More sophisticated and dramatic examples are easy to come by. The design and construction of medical implants provides an entire class of them. Currently, an artificial knee joint is designed by a surgeon for each individual patient using a set of ad hoc rules. A sufficiently powerful object representation system could take into account the physical characteristics of a given patient and model the forces acting on the joint, the shape of the joint surfaces, and all the other important factors. The action of and stresses on the joint under such activities as sitting down or walking upstairs could be simulated. Thus, the system would allow verifying the specific design for an individual patient before the operation to install the knee is performed.

It is easy to imagine still more complex and speculative examples in such areas as modeling plastic flow in molds, realistically animating objects from a representation database, and many others. Some of these may be beyond the capability of a general object representation and reasoning system, but some will not. Until the field has been developed, this cannot be determined.

A new science of representing physical objects and of manipulating and reasoning about those representations is needed. This new science draws on material from a host of existing fields, including computer science, physics, and many branches of engineering. It is a science because researchers will be establishing and systematizing the facts, methods and principles underlying the representation of physical objects. Drawing on the Greek, we take the word for "solid," stereo, and combine it with the word for "the study of representations," phenomenology, to christen this new science—stereophenomenology.

The importance of this new discipline is not, of course, in its name. It is instead in the concept that there is a collected set of principles, tools, and methodologies, forming the science of stereophenomenology, that can be applied to a broad range of important problems. We believe this to be true, but only time, and the collected efforts of many researchers, will provide the final answer.

3. Representations for Physical Objects and Processes

If we are going to reason about physical objects and simulate physical processes with computer systems, then the systems must have representations for the objects and the physical processes that modify and manipulate them. This section examines both the kinds of information that must be represented and techniques for doing so. As the individual sections make clear, on at least some aspects of representation much excellent research has already been done. However, there are large areas that are almost untouched, and no work has been done that truly ties together all the various aspects of physical object representation.

The real challenge seems to be develop...

Table of contents

• Cover
• Title
• Copyright
• Original Title
• Original Copyright
• Contents
• Preface
• Introduction
• 1. The Challenge of Robotics for Computer Science
• 2. Computational Geometry—A User's Guide
• 3. Algorithmic Motion Planning
• 4. Approximation and Decomposition of Shapes
• 5. Intersection and Proximity Problems and Voronoi Diagrams
• 6. Fleshing Out Wire Frames: Reconstruction of Objects, Part I
• 7. Fleshing Out Projections: Reconstruction of Objects, Part II
• AUTHOR INDEX
• SUBJECT INDEX