2002 · 145 citations · 23 references
EngineeringComputer ScienceRobotics EngineeringMotion PlanningRobot KinematicsRoboticsRobot Motion PlanningTrajectory GenerationComplexityConfiguration Space AnalysisMotion Planning For ManipulatorsMotion Planning In Configuration SpacePseudo-triangulationRigidity TheoryRobot Trajectory GenerationTriangulations
We propose a combinatorial approach to plan noncolliding motions for a polygonal bar-and-joint framework. Our approach yields very efficient deterministic algorithms for a category of robot arm motion planning problems with many degrees of freedom, where the known general roadmap techniques would give exponential complexity. It is based on a novel class of one-degree-of-freedom mechanisms induced by pseudo triangulations of planar point sets, for which we provide several equivalent characterization and exhibit rich combinatorial and rigidity theoretic properties. The main application is an efficient algorithm for the Carpenter's rule problem: convexify a simple bar-and-joint planar polygonal linkage using only non self-intersecting planar motions. A step in the convexification motion consists in moving a pseudo-triangulation-based mechanism along its unique trajectory in configuration space until two adjacent edges align. At that point, a local alteration restores the pseudo triangulation. The motion continues for O(n/sup 2/) steps until all the points are in convex position.
23
Handbook of discrete and computational geometry
Choice Reviews Online · 1998 · 1.5K citations · Full text
Problems in low-dimensional topology
Frank Quinn · Institutional Repositories DataBase (IRDB) · 1997 · 437 citations · Full text