7.5 Folding Problems in Robotics and Biology

A growing number of motion planning applications involve some form of folding. Examples include automated carton folding, computer-aided drug design, protein folding, modular reconfigurable robots, and even robotic origami. These problems are generally modeled as a linkage in which all bodies are connected by revolute joints. In robotics, self-collision between pairs of bodies usually must be avoided. In biological applications, energy functions replace obstacles. Instead of crisp obstacle boundaries, energy functions can be imagined as “soft” obstacles, in which a real value is defined for every q , instead of defining a set obs . For a given threshold value, such energy functions can be converted into an obstacle region by defining obs to be the configurations that have energy above the threshold. However, the energy function contains more information because such thresholds are arbitrary. This section briefly shows some examples of folding problems and techniques from the recent motion planning literature.

C

∈ C C ⊂ C

Carton folding An interesting application of motion planning to the automated folding of boxes is presented in [661]. Figure 7.28 shows a carton in its original flat form and in its folded form. As shown in Figure 7.29, the problem can be modeled as a tree of bodies connected by revolute joints. Once this model has been formulated, many methods from Chapters 5 and 6 can be adapted for this problem. In [661], a planning algorithm optimized particularly for box folding is presented.

Figure 7.27: Planning for the Logabex LX4 robot [187]. This solution was com-

puted in less than a minute by applying active-passive decomposition to an RDT- based planner [244]. In this example, the dimension of C is 97 and the dimension of Cclo is 25.

It is an adaptation of an approximate cell decomposition algorithm developed for kinematic chains in [658]. Its complexity is exponential in the degrees of freedom of the carton, but it gives good performance on practical examples. One such solution that was found by motion planning is shown in Figure 7.30. To use these solutions in a factory, the manipulation problem has to be additionally considered. For example, as demonstrated in [661], a manipulator arm robot can be used in combination with a well-designed set of fixtures. The fixtures help hold the carton in place while the manipulator applies pressure in the right places, which yields the required folds. Since the feasibility with fixtures depends on the particular folding path, the planning algorithm generates all possible distinct paths from the

Figure 7.28: An important packaging problem is to automate the folding of a perforated sheet of cardboard into a carton.

Figure 7.29: The carton can be cleverly modeled as a tree of bodies that are attached by revolute joints.

Figure 7.30: A folding sequence that was computed using the algorithm in [661].

initial configuration (at which the box is completely unfolded).

Simplifying knots A knot is a closed curve that does not intersect itself, is em- bedded in R3, and cannot be untangled to produce a simple loop (such as a circular path). If the knot is allowed to intersect itself, then any knot can be untangled;

therefore, a careful definition of what it means to untangle a knot is needed. For a closed curve, τ : [0, 1] → R3, embedded in R3 (it cannot intersect itself), let the set R3 \ τ ([0, 1]) of points not reached by the curve be called the ambient space

of τ . In knot theory, an ambient isotopy between two closed curves, τ1 and τ2, embedded in R3 is a homeomorphism between their ambient spaces. Intuitively, this means that τ1 can be warped into τ2 without allowing any self-intersections. Therefore, determining whether two loops are equivalent seems closely related to

motion planning. Such equivalence gives rise to groups that characterize the space of knots and are closely related to the fundamental group described in Section

4.1.3. For more information on knot theory, see [8, 451, 511].

A motion planning approach was developed in [571] to determine whether a closed curve is equivalent to the unknot, which is completely untangled. This can be expressed as a curve that maps onto S1, embedded in R3. The algorithm

takes as input a knot expressed as a circular chain of line segments embedded in R3. In this case, the unknot can be expressed as a triangle in R3. One of the most challenging examples solved by the planner is shown in Figure 7.31. The

planner is sampling-based and shares many similarities with the RDT algorithm of Section 5.5 and the Ariadne’s clew and expansive space planners described in Section 5.4.4. Since the task is not to produce a collision-free path, there are several unique aspects in comparison to motion planning. An energy function is defined over the collection of segments to try to guide the search toward simpler configurations. There are two kinds of local operations that are made by the planner: 1) Try to move a vertex toward a selected subgoal in the ambient space. This is obtained by using random sampling to grow a search tree. 2) Try to delete a vertex, and connect the neighboring vertices by a straight line. If no collision occurs along the intermediate configurations, then the knot has been simplified. The algorithm terminates when it is unable to further simplify the knot.

Drug design A sampling-based motion planning approach to pharmaceutical drug design is taken in [601]. The development of a drug is a long, incremental process, typically requiring years of research and experimentation. The goal is to find a relatively small molecule called a ligand, typically comprising a few dozen atoms, that docks with a receptor cavity in a specific protein [615]; Figure 1.14 (Section 1.2) illustrated this. Examples of drug molecules were also given in Figure

1.14. Protein-ligand docking can stimulate or inhibit some biological activity, ultimately leading to the desired pharmacological effect. The problem of finding suitable ligands is complicated due to both energy considerations and the flexibility of the ligand. In addition to satisfying structural considerations, factors such as synthetic accessibility, drug pharmacology and toxicology greatly complicate and

Figure 7.31: The planner in [571] untangles the famous Ochiai unknot benchmark in a few minutes on a standard PC.

lengthen the search for the most effective drug molecules.

One popular model used by chemists in the context of drug design is a pharma- cophore, which serves as a template for the desired ligand [229, 339, 383, 860]. The pharmacophore is expressed as a set of features that an effective ligand should pos- sess and a set of spatial constraints among the features. Examples of features are specific atoms, centers of benzene rings, positive or negative charges, hydrophobic or hydrophilic centers, and hydrogen bond donors or acceptors. Features gener-

ally require that parts of the molecule must remain fixed in R3, which induces kinematic closure constraints. These features are developed by chemists to en-

capsulate the assumption that ligand binding is due primarily to the interaction of some features of the ligand to “complementary” features of the receptor. The interacting features are included in the pharmacophore, which is a template for screening candidate drugs, and the rest of the ligand atoms merely provide a scaf- fold for holding the pharmacophore features in their spatial positions. Figure 7.32 illustrates the pharmacophore concept.

Candidate drug molecules (ligands), such as the ones shown in Figure 1.14, can be modeled as a tree of bodies as shown in Figure 7.33. Some bonds can rotate, yielding revolute joints in the model; other bonds must remain fixed. The drug design problem amounts to searching the space of configurations (called confor- mations) to try to find a low-energy configuration that also places certain atoms

(x_2, y2, z_2)

(x_3, y3, z_3)

(x_1, y1, z_1)

(0, 0, 0)

Figure 7.32: A pharmacophore is a model used by chemists to simplify the inter- action process between a ligand (candidate drug molecule) and a protein. It often amounts to holding certain features of the molecule fixed in R3. In this example,

the positions of three atoms must be fixed relative to the body frame of an arbi-

trarily designated root atom. It is assumed that these features interact with some complementary features in the cavity of the protein.

in specified locations in R3. This additional constraint arises from the pharma- cophore and causes the planning to occur on clo from Section 7.4 because the pharmacophores can be expressed as closure constraints.

C

An energy function serves a purpose similar to that of a collision detector. The evaluation of a ligand for drug design requires determining whether it can achieve low-energy conformations that satisfy the pharmacophore constraints. Thus, the task is different from standard motion planning in that there is no predetermined goal configuration. One of the greatest difficulties is that the energy functions are extremely complicated, nonlinear, and empirical. Here is typical example (used in [601]):

e(q)= 寸 1 Kb(R − R′)2 + 寸 1 Ka(α − α′)2+

bonds 2

ang 2

寸torsions Kd[1 + cos(pθ − θ′)] +

(7.25)

寸 （4ǫ

i,j

(σij \12 − (σij \6『 + _cicj 1 .

The energy accounts for torsion-angle deformations, van der Waals potential, and Coulomb potentials. In (7.25), the first sum is taken over all bonds, the second over all bond angles, the third over all rotatable bonds, and the last is taken over all pairs of atoms. The variables are the force constants, Kb, Ka, and Kd; the dielectric constant, ǫ; a periodicity constant, p; the Lennard-Jones radii, σij ; well depth, ǫij ; partial charge, ci; measured bond length, R; equilibrium bond length,

ij

rij

rij

ǫrij

Root Atom

Figure 7.33: The modeling of a flexible molecule is similar to that of a robot. One atom is designated as the root, and the remaining bodies are arranged in a tree. If there are cyclic chains in the molecules, then constraints as described in Section

4.4 must be enforced. Typically, only some bonds are capable of rotation, whereas others must remain rigid.

R′; measured bond angle, α; equilibrium bond angle, α′; measured torsional angle, θ; equilibrium torsional angle, θ′; and distance between atom centers, rij . Although the energy expression is very complicated, it only depends on the configuration variables; all others are constants that are estimated in advance.

Protein folding In computational biology, the problem of protein folding shares many similarities with drug design in that the molecules have rotatable bonds and energy functions are used to express good configurations. The problems are much more complicated, however, because the protein molecules are generally much larger than drug molecules. Instead of a dozen degrees of freedom, which is typical for a drug molecule, proteins have hundreds or thousands of degrees of freedom. When proteins appear in nature, they are usually in a folded, low- energy configuration. The structure problem involves determining precisely how the protein is folded so that its biological activity can be completely understood. In some studies, biologists are even interested in the pathway that a protein takes to arrive in its folded state [24, 25]. This leads directly to an extension of motion planning that involves arriving at a goal state in which the molecule is folded. In [24, 25], sampling-based planning algorithms were applied to compute folding pathways for proteins. The protein starts in an unfolded configuration and must arrive in a specified folded configuration without violating energy constraints along the way. Figure 7.34 shows an example from [25]. That work also draws interesting

connections between protein folding and box folding, which was covered previously.

Figure 7.34: Protein folding for a polypeptide, computed by a sampling-based roadmap planning algorithm [24]