A Motion-Planning Approach to Folding: From Paper Craft to Protein Folding

Abstract

In this paper, we present a framework for studying folding problems from a motion-planning perspective. The version of the motion-planning problem we consider is that of determining a sequence of motions to transform some configuration of a foldable object (the start) into another configuration (the goal). Modeling foldable objects as tree-like multilink objects allows us to apply motion-planning techniques for articulated objects with many degrees of freedom (many links) to folding problems. An important feature of this approach is that it not only allows us to study foldability questions, such as, can one object be folded (or unfolded) into another object, but it also provides us with another tool for investigating the dynamic folding process itself. The framework proposed here has application to traditional motion-planning areas such as automation and animation, to paper-folding problems studied in computational geometry, and to computational biology problems such as protein folding. Preliminary experimental results with paper folding and the folding of small proteins (approximately 60 residues) are quite encouraging.