Book contents
- Frontmatter
- Contents
- Preface
- 0 Introduction
- Part I Linkages
- 1 Problem Classification and Examples
- 2 Upper and Lower Bounds
- 3 Planar Linkage Mechanisms
- 4 Rigid Frameworks
- 5 Reconfiguration of Chains
- 6 Locked Chains
- 7 Interlocked Chains
- 8 Joint-Constrained Motion
- 9 Protein Folding
- Part II Paper
- Part III Polyhedra
- Bibliography
- Index
2 - Upper and Lower Bounds
Published online by Cambridge University Press: 07 September 2010
- Frontmatter
- Contents
- Preface
- 0 Introduction
- Part I Linkages
- 1 Problem Classification and Examples
- 2 Upper and Lower Bounds
- 3 Planar Linkage Mechanisms
- 4 Rigid Frameworks
- 5 Reconfiguration of Chains
- 6 Locked Chains
- 7 Interlocked Chains
- 8 Joint-Constrained Motion
- 9 Protein Folding
- Part II Paper
- Part III Polyhedra
- Bibliography
- Index
Summary
GENERAL ALGORITHMS AND UPPER BOUNDS
Configuration Space Approach
One of the earliest achievements in the field is an algorithm by Schwartz and Sharir that can solve any “motion planning” problem, including essentially any linkage problem. The technique is to explicitly construct a representation of the free space for the mechanism and then answer all questions with this representation. For example, a reconfiguration decision question reduces to deciding if the initial configuration A is in the same connected component of the free space as the final configuration B. An example of the configuration space for a 2-link arm in the presence of obstacles is shown in Figure 2.1. Because each configuration is mapped to a point in configuration space, the complex motion of the arm in (a) of the figure is reduced to the path of a point in configuration space (b). In this case the configuration space is a torus representing two angles θ1 and θ2, each with wrap-around ranges [0, 2π] (see p. 61).
Their original algorithm, developed in the justly famous five “piano mover's” papers, resulted in a doubly exponential algorithm. Subsequent research has improved this to singly exponential. Although we will not employ this algorithm subsequently, it is an important milestone and serves as a baseline for all subsequent work, and so it is worth stating the result more precisely.
- Type
- Chapter
- Information
- Geometric Folding AlgorithmsLinkages, Origami, Polyhedra, pp. 17 - 28Publisher: Cambridge University PressPrint publication year: 2007