CCF- Algorithmic Foundations: Motion Planning for Geometrically Constrained Structures

Smith College, Northampton MA

Investigators

Abstract

Linkage reconfiguration problems underlie modern mathematical investigations in robotics, mechanical design, structural engineering, and bio-geometry, and have the potential of impacting computational biology, especially the problems emerging from modeling protein folding or, more generally, protein flexibility and motion. This proposal focuses on the foundations of motion planning approaches to geometrically constrained structures. The selected problems are part of a long-term program for understanding the combinatorial, rigidity-theoretic, algebraic and algorithmic aspects of a variety of motion planning approaches to geometric reconfiguration questions. It builds upon the PIs' previous work on: (a) applying concepts from Rigidity Theory to 2-dimensional (2D) linkage reconfiguration problems (such as the Carpenter's Rule problem using pointed pseudo-triangulation), (b) Combinatorial Rigidity (generalizations of Pebble Game algorithms for 2D-rigidity to other classes of matroidal sparse graphs, computation of rigid and stressed clusters), (c) motion generation (for pseudo-triangulations in 2D and for complex structures with many loops in 3D), and (d) recent results on finding extremal configurations of revolute jointed robotic manipulators. The proposal aims at developing systematic motion planning approaches, using mathematically proven techniques and exploiting discrete underlying structures of the geometrically constrained systems under investigation. Examples include expansive motions and pseudo-triangulations, motion and reconfiguration for 3D-structures (linkages, panel-and-hinge and polyhedral structures) and reconfigurations of robot arms towards extremal configurations (minima and maxima), together with a theoretical investigation of their 3D workspace.