Algorithmic and Geometric Aspects of Robotics (Routledge Revivals)

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.

Preface; Introduction Chee-Keng Yap; 1. Why Robotics? 2. An Overview of the Contents of the Volume 3. Brief Review of Standard Terminology; 1. The Challenge of Robotics for computer Science John E. Hopcroft and Dean B. Krafft; 1. What is Robotics? 2. A New Science 3. Representations for Physical Objects and processes 4. Manipulating Object Representations 5. Reasoning 6. Conclusions References; 2. Computational Geometry — A User’s Guide David P. Dobkin and Diane L. Souvaine; 1. Introduction 2. Hierarchical Search 3. Hierarchical Computation 4. Geometric Transformations 5. Conclusion References; 3. Algorithmic Motion Planning Chee-Keng Yap; 1. History 2. Basic Concepts 3. A Taxonomy of Motion Planning Problems 4. Issues related to Algorithmic Motion Planning 5. Moving a Disc 6. Moving a Ladder 7. Two Approaches to Motion Planning 8. Solution to the General Motion Planning Problem 9. Retraction Via Cell Complexes 10. Lower Bounds 11. Summary: New Directions and Open Problems 12. Conclusion References; 4. Approximation and Decomposition of Shapes Bernard Chazelle; 1. Introduction 2. Approximation of Shapes 3. Decomposition of Shapes 4. Epilogue References; 5. Intersection and Proximity Problems and Voronoi Diagrams Daniel Leven and Micha Sharir; 1. Introduction 2. A Simple Intersection Detection Algorithm in Two-Dimensional Space 3. Generalized Planar Voronoi Diagrams 4. Applications of Voronoi Diagrams 5. Efficient Construction of Voronoi Diagrams 6. Dynamic Intersection and Proximity Problems 7. The Three-Dimensional Case References; 6. Fleshing Out Wire Frames: Reconstruction of Objects, Part I George Markowsky and Michael A. Wesley; 1. Introduction 2. Basic concepts 3. The Wire Frame Algorithm 4. Examples Appendix A: Topological Concepts References; 7. Fleshing Out Projections: Reconstruction of Objects, Part II Michael A. Wesley and George Markowsky; 1. Introduction 2. Basic Concepts and Results 3. Fleshing Out Unlabled Projections 4. Additional Information from Drawing Conventions 5. Examples 6. Summary References; Author Index; Subject Index