Spatial Reasoning and Planning: Geometry, Mechanism, and Motion (Hardcover, 2004)

1 Introduction.- 1.1 Motivation.- 1.2 Issues.- 1.3 Scope of the Book.- 1.4 Organization of the Book.- 2 Overview of Spatial Reasoning and Planning Techniques.- 2.1 Computer-Aided Kinematic Design of Mechanisms.- 2.2 Geometric Path Planning.- 2.2.1 Path Search in Configuration Space.- 2.2.2 Path Finding Based on Direct Free-Space Characterization.- 2.2.3 Local Path Planning.- 2.3 Qualitative Reasoning.- 2.3.1 Qualitative Mechanism Analysis.- 2.3.2 Qualitative Spatial Reasoning.- 2.3.3 Qualitative Robotics.- 2.3.4 Qualitative Physics.- 2.4 Simulated Annealing.- 3 Interesting Problems in Spatial Reasoning and Planning.- 3.1 Terminology and Notation.- 3.2 The Problems.- 3.3 Assumptions.- 4 How to Represent Qualitative Spatial Relationships.- 4.1 Qualitative Distance.- 4.2 Qualitative Angle.- 4.3 Notes on Label-Based Distance and Angle Descriptions.- 4.4 Completeness.- 4.5 Minimum-Spanning Edge (m-Edge) between Two Polygons.- 4.6 Qualitative Location in a Convex Polygonal Environment.- 4.6.1 Qualitative Location.- 4.7 Graphic Representation of the m-Edge Partitioned Free-Space.- 4.8 Notes on Qualitative Location.- 5 Methodology of Spatial Reasoning and Planning.- 5.1 Spatial Inferencing.- 5.1.1 Qualitative Trigonometry (QT ).- 5.1.2 Qualitative Arithmetic (QA) and Propagation.- 5.1.3 Inferencing.- 5.2 Envisionments.- 5.3 Spatial Planning in Q-Space.- 5.3.1 Qualitative Route.- 5.3.2 Clearance Measurements of a Qualitative Route.- 5.4 Quantitative Configuration Generation with Simulated Annealing.- 6 How to Reason about Mechanism Configurations.- 6.1 An Overview of the Method.- 6.2 Qualitative Configuration Analysis.- 6.2.1 Examples.- 6.3 Quantitative Configuration Generation.- 6.3.1 Examples.- 6.4 Discussions.- 6.4.1 Features and Advantages.- 6.4.2 Limitations.- 6.5 Kinematic State Transitions in CSV Mechanisms.- 6.5.1 Vertex-Contact Configurations of CSV Mechanisms.- 6.5.2 Placement of Vertices in VC Configurations.- 6.5.3 Identification of Kinematic State Transitions.- 6.6 Summary.- 7 How to Reason about Velocity Relationships.- 7.1 Instantaneous Rotation Center.- 7.2 Velocity Relationship Analysis.- 7.3 Examples.- 7.4 Notes on the Application of Velocity Analysis.- 7.5 Relative Motion Method of Analyzing Velocities.- 7.5.1 Axioms and Theorems in Revolute or Prismatic-Pairing Body Motion.- 7.5.2 Kinematic Modeling.- 7.6 Qualitative Analysis of Relative Velocities.- 7.6.1 Solving Velocity Constraint Equations.- 7.6.2 An Algorithm for Determining Linear Velocities.- 7.7 An Example.- 7.8 Summary.- 8 How to Plan Robot Motions.- 8.1 An Overview of the Method.- 8.2 Qualitative Route Planning in the m-Edge Partitioned Euclidean Free-Space.- 8.2.1 Eliminating Dead-End Regions.- 8.2.2 Representing Path-Segment Invariants.- 8.2.3 An Algorithm for Finding Qualitative Routes.- 8.3 Constructing Exact Paths from Qualitative Routes.- 8.3.1 The Composition of an Exact Path.- 8.3.2 Randomized Search for Exact Path Segments.- 8.3.3 An Algorithm for Computing Exact Path Segments.- 8.4 Graphical Simulations.- 8.4.1 Examples.- 8.5 Discussions.- 8.5.1 Efficiency.- 8.5.2 Near-Obstacle Paths.- 8.5.3 Comparison with Other Free-Space-Based Approaches.- 8.5.4 Comparison with Other Monte-Carlo Path-Planning Approaches.- 8.5.5 Limitations.- 9 How to Make Spatial Measurements and Maps.- 9.1 Mapping.- 9.2 m-Uncertainty and FS Theory.- 9.3 Incorporating m-Uncertainty.- 9.4 Collective Spatial Map Construction.- 9.4.1 Related Work on Spatial Map Construction.- 9.4.2 The Problem.- 9.5 Self-Organization of a Potential Map.- 9.5.1 Coordinate Systems for an Agent.- 9.5.2 Proximity Measurements.- 9.5.3 Distance Association within a Neighboring Region.- 9.5.4 Incremental Self-Organization of a Potential Map.- 9.6 Experiments.- 9.6.1 Experimental Design.- 9.6.2 Comparison with a Non-Adaptive Mode.- 9.6.3 Experimental Results and Comparisons.- 9.7 Summary.- 10 Concluding Remarks.- 10.1 Key Concepts Revisited.- 10.2 Practical Application.- 10.2.1 Computer-Aided Mechani