Accurate binding affinity prediction (BAP) is crucial to structure-based drug design. We present PATH+, a novel, generalizable machine learning algorithm for BAP that exploits recent advances in computational topology. Compared to current binding affinity prediction algorithms, PATH+ shows similar or better accuracy and is more generalizable across orthogonal datasets. PATH+ is not only one of the most accurate algorithms for BAP, it is also the first algorithm that is inherently interpretable. Interpretability is a key factor of trust for an algorithm and alongside generalizability, which allows PATH+ to be trusted in critical applications, such as inhibitor design. We visualized the features captured by PATH+ for two clinically relevant protein-ligand complexes and find that PATH+ captures binding-relevant structural mutations that are corroborated by biochemical data. Our work also sheds light on the features captured by current computational topology BAP algorithms that contributed to their high performance, which have been poorly understood. PATH+ also offers an improvement of 𝒪 (m + n)3 in computational complexity and is empirically over 10 times faster than the dominant (uninterpretable) computational topology algorithm for BAP. Based on insights from PATH+, we built PATH-, a scoring function for differentiating between binders and non-binders that has outstanding accuracy against 11 current algorithms for BAP. In summary, we report progress in a novel combination of interpretability, speed, and accuracy that should further empower topological screening of large virtual inhibitor libraries to protein targets, and allow binding affinity predictions to be understood and trusted. The source code for PATH+ and PATH- is released open-source as part of the OSPREY protein design software package.

Antimicrobial resistance presents a significant health care crisis. The mutation F98Y in Staphylococcus aureus dihydrofolate reductase (SaDHFR) confers resistance to the clinically important antifolate trimethoprim (TMP). Propargyl-linked antifolates (PLAs), next generation DHFR inhibitors, are much more resilient than TMP against this F98Y variant, yet this F98Y substitution still reduces efficacy of these agents. Surprisingly, differences in the enantiomeric configuration at the stereogenic center of PLAs influence the isomeric state of the NADPH cofactor. To understand the molecular basis of F98Y-mediated resistance and how PLAs' inhibition drives NADPH isomeric states, we used protein design algorithms in the osprey protein design software suite to analyze a comprehensive suite of structural, biophysical, biochemical, and computational data. Here, we present a model showing how F98Y SaDHFR exploits a different anomeric configuration of NADPH to evade certain PLAs' inhibition, while other PLAs remain unaffected by this resistance mechanism.

The K* algorithm provably approximates partition functions for a set of states (e.g., protein, ligand, and protein-ligand complex) to a user-specified accuracy ε. Often, reaching an ε-approximation for a particular set of partition functions takes a prohibitive amount of time and space. To alleviate some of this cost, we introduce two new algorithms into the osprey suite for protein design: fries, a Fast Removal of Inadequately Energied Sequences, and EWAK*, an Energy Window Approximation to K*. fries pre-processes the sequence space to limit a design to only the most stable, energetically favorable sequence possibilities. EWAK* then takes this pruned sequence space as input and, using a user-specified energy window, calculates K* scores using the lowest energy conformations. We expect fries/EWAK* to be most useful in cases where there are many unstable sequences in the design sequence space and when users are satisfied with enumerating the low-energy ensemble of conformations. In combination, these algorithms provably retain calculational accuracy while limiting the input sequence space and the conformations included in each partition function calculation to only the most energetically favorable, effectively reducing runtime while still enriching for desirable sequences. This combined approach led to significant speed-ups compared to the previous state-of-the-art multi-sequence algorithm, BBK*, while maintaining its efficiency and accuracy, which we show across 40 different protein systems and a total of 2,826 protein design problems. Additionally, as a proof of concept, we used these new algorithms to redesign the protein-protein interface (PPI) of the c-Raf-RBD:KRas complex. The Ras-binding domain of the protein kinase c-Raf (c-Raf-RBD) is the tightest known binder of KRas, a protein implicated in difficult-to-treat cancers. fries/EWAK* accurately retrospectively predicted the effect of 41 different sets of mutations in the PPI of the c-Raf-RBD:KRas complex. Notably, these mutations include mutations whose effect had previously been incorrectly predicted using other computational methods. Next, we used fries/EWAK* for prospective design and discovered a novel point mutation that improves binding of c-Raf-RBD to KRas in its active, GTP-bound state (KRasGTP). We combined this new mutation with two previously reported mutations (which were highly-ranked by osprey) to create a new variant of c-Raf-RBD, c-Raf-RBD(RKY). fries/EWAK* in osprey computationally predicted that this new variant binds even more tightly than the previous best-binding variant, c-Raf-RBD(RK). We measured the binding affinity of c-Raf-RBD(RKY) using a bio-layer interferometry (BLI) assay, and found that this new variant exhibits single-digit nanomolar affinity for KRasGTP, confirming the computational predictions made with fries/EWAK*. This new variant binds roughly five times more tightly than the previous best known binder and roughly 36 times more tightly than the design starting point (wild-type c-Raf-RBD). This study steps through the advancement and development of computational protein design by presenting theory, new algorithms, accurate retrospective designs, new prospective designs, and biochemical validation.

Computational protein design is a transformative field with exciting prospects for advancing both basic science and translational medical research. New algorithms blend discrete and continuous geometry to address the challenges of creating designer proteins. I will discuss recent progress in this area and some interesting open problems. I will motivate this talk by discussing how, by using continuous geometric representations within a discrete optimization framework, broadly-neutralizing anti-HIV-1 antibodies were computationally designed that are now being tested in humans - the designed antibodies are currently in eight clinical trials, one of which is Phase 2a (NCT03721510). These continuous representations model the flexibility and dynamics of biological macromolecules, which are an important structural determinant of function. However, reconstruction of biomolecular dynamics from experimental observables requires the determination of a conformational probability distribution. These distributions are not fully constrained by the limited geometric information from experiments, making the problem ill-posed in the sense of Hadamard. The ill-posed nature of the problem comes from the fact that it has no unique solution. Multiple or even an infinite number of solutions may exist. To avoid the ill-posed nature, the problem must be regularized by making (hopefully reasonable) assumptions. I will present new ways to both represent and visualize correlated inter-domain protein motions. We use Bingham distributions, based on a quaternion fit to circular moments of a physics-based quadratic form. To find the optimal solution for the distribution, we designed an efficient, provable branch-and-bound algorithm that exploits the structure of analytical solutions to the trigonometric moment problem. Hence, continuous conformational PDFs can be determined directly from NMR measurements. The representation works especially well for multi-domain systems with broad conformational distributions. For more information please see Y. Qi et al. Jour. Mol. Biol. 2018; 430(18 Pt B):3412-3426. doi: 10.1016/j.jmb.2018.06.022. Ultimately, this method has parallels to other branches of geometric computing that balance discrete and continuous representations, including physical geometric algorithms, robotics, computational geometry, and robust optimization. I will advocate for using continuous distributions for protein modeling, and describe future work and open problems.

Nuclear Magnetic Resonance (NMR) experiments provide distances between nearby atoms of a protein molecule. The corresponding structure determination problem is to determine the 3D protein structure by exploiting such distances. We present a new order on the atoms of the protein, based on information from the chemistry of proteins and NMR experiments, which allows us to formulate the problem as a combinatorial search. Additionally, this order tells us what kind of NMR distance information is crucial to understand the cardinality of the solution set of the problem and its computational complexity.

MOTIVATION: When proteins mutate or bind to ligands, their backbones often move significantly, especially in loop regions. Computational protein design algorithms must model these motions in order to accurately optimize protein stability and binding affinity. However, methods for backbone conformational search in design have been much more limited than for sidechain conformational search. This is especially true for combinatorial protein design algorithms, which aim to search a large sequence space efficiently and thus cannot rely on temporal simulation of each candidate sequence. RESULTS: We alleviate this difficulty with a new parameterization of backbone conformational space, which represents all degrees of freedom of a specified segment of protein chain that maintain valid bonding geometry (by maintaining the original bond lengths and angles and ω dihedrals). In order to search this space, we present an efficient algorithm, CATS, for computing atomic coordinates as a function of our new continuous backbone internal coordinates. CATS generalizes the iMinDEE and EPIC protein design algorithms, which model continuous flexibility in sidechain dihedrals, to model continuous, appropriately localized flexibility in the backbone dihedrals ϕ and ψ as well. We show using 81 test cases based on 29 different protein structures that CATS finds sequences and conformations that are significantly lower in energy than methods with less or no backbone flexibility do. In particular, we show that CATS can model the viability of an antibody mutation known experimentally to increase affinity, but that appears sterically infeasible when modeled with less or no backbone flexibility. AVAILABILITY AND IMPLEMENTATION: Our code is available as free software at https://github.com/donaldlab/OSPREY_refactor . CONTACT: [email protected] or [email protected]. SUPPLEMENTARY INFORMATION: Supplementary data are available at Bioinformatics online.

Protein design algorithms enumerate a combinatorial number of candidate structures to compute the Global Minimum Energy Conformation (GMEC). To efficiently find the GMEC, protein design algorithms must methodically reduce the conformational search space. By applying distance and energy cutoffs, the protein system to be designed can thus be represented using a sparse residue interaction graph, where the number of interacting residue pairs is less than all pairs of mutable residues, and the corresponding GMEC is called the sparse GMEC. However, ignoring some pairwise residue interactions can lead to a change in the energy, conformation, or sequence of the sparse GMEC vs. the original or the full GMEC. Despite the widespread use of sparse residue interaction graphs in protein design, the above mentioned effects of their use have not been previously analyzed. To analyze the costs and benefits of designing with sparse residue interaction graphs, we computed the GMECs for 136 different protein design problems both with and without distance and energy cutoffs, and compared their energies, conformations, and sequences. Our analysis shows that the differences between the GMECs depend critically on whether or not the design includes core, boundary, or surface residues. Moreover, neglecting long-range interactions can alter local interactions and introduce large sequence differences, both of which can result in significant structural and functional changes. Designs on proteins with experimentally measured thermostability show it is beneficial to compute both the full and the sparse GMEC accurately and efficiently. To this end, we show that a provable, ensemble-based algorithm can efficiently compute both GMECs by enumerating a small number of conformations, usually fewer than 1000. This provides a novel way to combine sparse residue interaction graphs with provable, ensemble-based algorithms to reap the benefits of sparse residue interaction graphs while avoiding their potential inaccuracies.

MOTIVATION: Structure-based computational protein design (SCPR) is an important topic in protein engineering. Under the assumption of a rigid backbone and a finite set of discrete conformations of side-chains, various methods have been proposed to address this problem. A popular method is to combine the dead-end elimination (DEE) and A* tree search algorithms, which provably finds the global minimum energy conformation (GMEC) solution. RESULTS: In this article, we improve the efficiency of computing A* heuristic functions for protein design and propose a variant of A* algorithm in which the search process can be performed on a single GPU in a massively parallel fashion. In addition, we make some efforts to address the memory exceeding problem in A* search. As a result, our enhancements can achieve a significant speedup of the A*-based protein design algorithm by four orders of magnitude on large-scale test data through pre-computation and parallelization, while still maintaining an acceptable memory overhead. We also show that our parallel A* search algorithm could be successfully combined with iMinDEE, a state-of-the-art DEE criterion, for rotamer pruning to further improve SCPR with the consideration of continuous side-chain flexibility. AVAILABILITY: Our software is available and distributed open-source under the GNU Lesser General License Version 2.1 (GNU, February 1999). The source code can be downloaded from http://www.cs.duke.edu/donaldlab/osprey.php or http://iiis.tsinghua.edu.cn/∼compbio/software.html.

UNLABELLED: Optimizing amino acid conformation and identity is a central problem in computational protein design. Protein design algorithms must allow realistic protein flexibility to occur during this optimization, or they may fail to find the best sequence with the lowest energy. Most design algorithms implement side-chain flexibility by allowing the side chains to move between a small set of discrete, low-energy states, which we call rigid rotamers. In this work we show that allowing continuous side-chain flexibility (which we call continuous rotamers) greatly improves protein flexibility modeling. We present a large-scale study that compares the sequences and best energy conformations in 69 protein-core redesigns using a rigid-rotamer model versus a continuous-rotamer model. We show that in nearly all of our redesigns the sequence found by the continuous-rotamer model is different and has a lower energy than the one found by the rigid-rotamer model. Moreover, the sequences found by the continuous-rotamer model are more similar to the native sequences. We then show that the seemingly easy solution of sampling more rigid rotamers within the continuous region is not a practical alternative to a continuous-rotamer model: at computationally feasible resolutions, using more rigid rotamers was never better than a continuous-rotamer model and almost always resulted in higher energies. Finally, we present a new protein design algorithm based on the dead-end elimination (DEE) algorithm, which we call iMinDEE, that makes the use of continuous rotamers feasible in larger systems. iMinDEE guarantees finding the optimal answer while pruning the search space with close to the same efficiency of DEE. AVAILABILITY: Software is available under the Lesser GNU Public License v3. Contact the authors for source code.

Amino acid substitutions in protein structures often require subtle backbone adjustments that are difficult to model in atomic detail. An improved ability to predict realistic backbone changes in response to engineered mutations would be of great utility for the blossoming field of rational protein design. One model that has recently grown in acceptance is the backrub motion, a low-energy dipeptide rotation with single-peptide counter-rotations, that is coupled to dynamic two-state sidechain rotamer jumps, as evidenced by alternate conformations in very high-resolution crystal structures. It has been speculated that backrubs may facilitate sequence changes equally well as rotamer changes. However, backrub-induced shifts and experimental uncertainty are of similar magnitude for backbone atoms in even high-resolution structures, so comparison of wildtype-vs.-mutant crystal structure pairs is not sufficient to directly link backrubs to mutations. In this study, we use two alternative approaches that bypass this limitation. First, we use a quality-filtered structure database to aggregate many examples for precisely defined motifs with single amino acid differences, and find that the effectively amplified backbone differences closely resemble backrubs. Second, we directly apply a provably-accurate, backrub-enabled protein design algorithm to idealized versions of these motifs, and discover that the lowest-energy computed models match the average-coordinate experimental structures. These results support the hypothesis that backrubs participate in natural protein evolution and validate their continued use for design of synthetic proteins.

The cystic fibrosis transmembrane conductance regulator (CFTR) is an epithelial chloride channel mutated in patients with cystic fibrosis (CF). The most prevalent CFTR mutation, ΔF508, blocks folding in the endoplasmic reticulum. Recent work has shown that some ΔF508-CFTR channel activity can be recovered by pharmaceutical modulators ("potentiators" and "correctors"), but ΔF508-CFTR can still be rapidly degraded via a lysosomal pathway involving the CFTR-associated ligand (CAL), which binds CFTR via a PDZ interaction domain. We present a study that goes from theory, to new structure-based computational design algorithms, to computational predictions, to biochemical testing and ultimately to epithelial-cell validation of novel, effective CAL PDZ inhibitors (called "stabilizers") that rescue ΔF508-CFTR activity. To design the "stabilizers", we extended our structural ensemble-based computational protein redesign algorithm K* to encompass protein-protein and protein-peptide interactions. The computational predictions achieved high accuracy: all of the top-predicted peptide inhibitors bound well to CAL. Furthermore, when compared to state-of-the-art CAL inhibitors, our design methodology achieved higher affinity and increased binding efficiency. The designed inhibitor with the highest affinity for CAL (kCAL01) binds six-fold more tightly than the previous best hexamer (iCAL35), and 170-fold more tightly than the CFTR C-terminus. We show that kCAL01 has physiological activity and can rescue chloride efflux in CF patient-derived airway epithelial cells. Since stabilizers address a different cellular CF defect from potentiators and correctors, our inhibitors provide an additional therapeutic pathway that can be used in conjunction with current methods.

Nuclear magnetic resonance (NMR) spectroscopy is an important experimental technique that allows one to study protein structure and dynamics in solution. An important bottleneck in NMR protein structure determination is the assignment of NMR peaks to the corresponding nuclei. Structure-based assignment (SBA) aims to solve this problem with the help of a template protein which is homologous to the target and has applications in the study of structure–activity relationship, protein–protein and protein–ligand interactions. We formulate SBA as a linear assignment problem with additional nuclear overhauser effect constraints, which can be solved within nuclear vector replacement's (NVR) framework (Langmead, C., Yan, A., Lilien, R., Wang, L. and Donald, B. (2003) A Polynomial-Time Nuclear Vector Replacement Algorithm for Automated NMR Resonance Assignments. Proc. the 7th Annual Int. Conf. Research in Computational Molecular Biology (RECOMB), Berlin, Germany, April 10–13, pp. 176–187. ACM Press, New York, NY. J. Comp. Bio., (2004), 11, pp. 277–298; Langmead, C. and Donald, B. (2004) An expectation/maximization nuclear vector replacement algorithm for automated NMR resonance assignments. J. Biomol. NMR, 29, 111–138). Our approach uses NVR's scoring function and data types and also gives the option of using CH and NH residual dipolar coupling (RDCs), instead of NH RDCs which NVR requires. We test our technique on NVR's data set as well as on four new proteins. Our results are comparable to NVR's assignment accuracy on NVR's test set, but higher on novel proteins. Our approach allows partial assignments. It is also complete and can return the optimum as well as near-optimum assignments. Furthermore, it allows us to analyze the information content of each data type and is easily extendable to accept new forms of input data, such as additional RDCs.

MOTIVATION: The Backrub is a small but kinematically efficient side-chain-coupled local backbone motion frequently observed in atomic-resolution crystal structures of proteins. A backrub shifts the C(alpha)-C(beta) orientation of a given side-chain by rigid-body dipeptide rotation plus smaller individual rotations of the two peptides, with virtually no change in the rest of the protein. Backrubs can therefore provide a biophysically realistic model of local backbone flexibility for structure-based protein design. Previously, however, backrub motions were applied via manual interactive model-building, so their incorporation into a protein design algorithm (a simultaneous search over mutation and backbone/side-chain conformation space) was infeasible. RESULTS: We present a combinatorial search algorithm for protein design that incorporates an automated procedure for local backbone flexibility via backrub motions. We further derive a dead-end elimination (DEE)-based criterion for pruning candidate rotamers that, in contrast to previous DEE algorithms, is provably accurate with backrub motions. Our backrub-based algorithm successfully predicts alternate side-chain conformations from < or = 0.9 A resolution structures, confirming the suitability of the automated backrub procedure. Finally, the application of our algorithm to redesign two different proteins is shown to identify a large number of lower-energy conformations and mutation sequences that would have been ignored by a rigid-backbone model. AVAILABILITY: Contact authors for source code.

Some of the most challenging and influential opportunities for Physical Geometric Algorithms (PGA) arise in developing and applying information technology to understand the molecular machinery of the cell. Our recent work (and work by others) shows that many PGA techniques may be fruitfully applied to the challenges of computational molecular biology. PGA research may lead to computer systems and algorithms that are useful in structural molecular biology, proteomics, and rational drug design.Concomitantly, a wealth of interesting computational and physical modeling problems arise in proposed methods for discovering new pharmaceuticals. In this talk, I'll discuss some recent results from my lab, including new algorithms for interpreting X-ray crystallography and NMR (nuclear magnetic resonance) data, disease classification using mass spectrometry of human serum, and protein redesign. Our algorithms have recently been used, respectively, to reveal the enzymatic architecture of organisms high on the CDC bioterrorism watch-list, for probabilistic cancer classification from human peripheral blood, and to redesign an antibiotic-producing enzyme to bind a novel substrate. I'll overview these projects, and survey some of the algorithmic, modeling, and computational challenges.

Realization of novel molecular function requires the ability to alter molecular complex formation. Enzymatic function can be altered by changing enzyme-substrate interactions via modification of an enzyme's active site. A redesigned enzyme may either perform a novel reaction on its native substrates or its native reaction on novel substrates. A number of computational approaches have been developed to address the combinatorial nature of the protein redesign problem. These approaches typically search for the global minimum energy conformation among an exponential number of protein conformations. We present a novel algorithm for protein redesign, which combines a statistical mechanics-derived ensemble-based approach to computing the binding constant with the speed and completeness of a branch-and-bound pruning algorithm. In addition, we developed an efficient deterministic approximation algorithm, capable of approximating our scoring function to arbitrary precision. In practice, the approximation algorithm decreases the execution time of the mutation search by a factor of ten. To test our method, we examined the Phe-specific adenylation domain of the non-ribosomal peptide synthetase gramicidin synthetase A (GrsA-PheA). Ensemble scoring, using a rotameric approximation to the partition functions of the bound and unbound states for GrsA-PheA, is first used to predict binding of the wildtype protein and a previously described mutant (selective for leucine), and second, to switch the enzyme specificity toward leucine, using two novel active site sequences computationally predicted by searching through the space of possible active site mutations. The top scoring in silico mutants were created in the wetlab and dissociation / binding constants were determined by fluorescence quenching. These tested mutations exhibit the desired change in specificity from Phe to Leu. Our ensemble-based algorithm which flexibly models both protein and ligand using rotamer-based partition functions, has application in enzyme redesign, the prediction of protein-ligand binding, and computer-aided drug design.

High-throughput NMR structural biology can play an important role in structural genomics. We report an automated procedure for high-throughput NMR resonance assignment for a protein of known structure, or of an homologous structure. These assignments are a prerequisite for probing protein-protein interactions, protein-ligand binding, and dynamics by NMR. Assignments are also the starting point for structure determination and refinement. A new algorithm, called Nuclear Vector Replacement (NVR) is introduced to compute assignments that optimally correlate experimentally-measured NH residual dipolar couplings (RDCs) to a given a priori whole-protein 3D structural model. The algorithm requires only uniform 15N-labelling of the protein, and processes unassigned HN-15N HSQC spectra, HN-15N RDCs, and sparse HN-HN NOE's dNNs), all of which can be acquired in a fraction of the time needed to record the traditional suite of experiments used to perform resonance assignments. NVR runs in minutes and efficiently assigns the (HN,15N) backbone resonances as well as the dNNs of the 3D \nfif-NOESY spectrum, in O(n3) time. The algorithm is demonstrated on NMR data from a 76-residue protein, human ubiquitin, matched to four structures, including one mutant (homolog), determined either by X-ray crystallography or by different NMR experiments (without RDCs). NVR achieves an average assignment accuracy of over 90%. We further demonstrate the feasibility of our algorithm for different and larger proteins, using NMR data for hen lysozyme (129 residues, 98% accuracy) and streptococcal protein G (56 residues, 95% accuracy), matched to a variety of 3D structural models. Finally, we extend NVR to a second application, 3D structural homology detection, and demonstrate that NVR is able to identify structural homologies between proteins with remote amino acid sequences using a database of structural models.

We introduce a model-based analysis technique for extracting and characterizing rhythmic expression profiles from genome-wide DNA microarray hybridization data. These patterns are clues to discovering rhythmic genes implicated in cell-cycle, circadian, and other biological processes. The algorithm, implemented in a program called RAGE (Rhythmic Analysis of Gene Expression), decouples the problems of estimating a pattern's periodicity and phase. Our algorithm is linear-time in frequency and phase resolution, an improvement over previous quadratic-time approaches. Unlike previous approaches, RAGE uses a true distance metric for measuring expression profile similarity, based on the Hausdorff distance. This results in better clustering of expression profiles for rhythmic analysis. The confidence of each frequency estimate is computed using Z-scores. We demonstrate that RAGE is superior to other techniques on synthetic and actual DNA microarray hybridization data. We also show how to replace the discretized phase search in our method with an exact (combinatorially precise) phase search, resulting in a faster algorithm with no complexity dependence on phase resolution.

This paper surveys our recent work in three key areas, using a physical geometric algorithm approach to data interpretation, experiment planning, and drug design: 1) data-directed computational protocols for high-throughput protein structure determination; 2) an experiment planning and data interpretation algorithms for reducing mass degeneracy in mass spectrometry; and 3) computer-aided drug design tools and applying them to the design of an inhibitor for the core-binding factor-/spl beta/ on-coprotein (CBF/spl beta/-MYII11), a fusion protein involved in some forms of acute myclomonocytic leukemia. Our long-range goal is the structural and functional understanding of biopolymer interactions in systems of significant biochemical as well as pharmacological interest. The research overviewed here represents a set of important steps towards that goal.

High-throughput, data-directed computational protocols for Structural Genomics (or Proteomics) are required in order to evaluate the protein products of genes for structure and function at rates comparable to current gene-sequencing technology. To develop such methods, new algorithms are required that can quickly extract significantly more structural information from sparse experimental data. This paper presents a new class of signal processing algorithms for nuclear magnetic resonance (NMR) structural biology, based on time-frequency analysis of chemical shift dynamics.

This paper describes a system in which multiple robots cooperate to move multiple objects such as groups of boxes using a constrained prehensile manipulation mode, by wrapping ropes around them. The system consists of three manipulation skills: tying ropes around objects, effecting rotations using a flossing manipulation gait, and effecting translations using a ratcheting manipulation gait. We present algorithms for these operations, a numerical analysis for the motion of groups of boxes, and experimental results.

We are developing paradigms and algorithms for browsing and editing families of animation using a haptic force-feedback device called a Phantom. These techniques may be generalized to navigation of any high degree-of-freedom system from a lower degree-of-freedom control space, with applications to telerobotics and simulation of virtual humans. We believe that modeling the animation configuration space coupled with the highly interactive nature of the haptic device provides one with useful and intuitive means of control. We have implemented our ideas in a system for the manipulation of animation motion capture data; in particular, anthropomorphic figures with 57 degrees of freedom are controlled by the user in real time. We treat trajectories, which encode animation, as first-class objects; haptic manipulation of these trajectories results in change to the animation. We have several haptic editing modes in which these trajectories are either haptically deformed or performed by the user with expressive control subject to dynamic haptic constraints.

A map-making robot integrates accumulated sensor data into a data structure that can be used for future localization or planning operations. Localization is the process of determining the robot's location within its environment. This paper describes experiments in which a robot simultaneously makes a map and localizes to that map. The map is a collection of tangent vectors constructed from stored sonar readings localized to a series of estimated poses. The vectors retain sensed surface normal information to improve accuracy. The localization scheme is a Hough transform into a space described by the robot's current sonar scan. The Hough transform finds a best fit in the presence of both sporadic sensor noise and discretization error.

The first micromachined bimorph organic ciliary array with on-chip CMOS circuitry is presented. This device is composed of an 8/spl times/8 array of cells each having four orthogonally oriented actuators in on overall die-size of 9.4 mm/spl times/9.4 mm. The polyimide based actuators were fabricated directly above the selection and drive circuitry. Selection and activation of actuators in this array shows that integration was successful. The integration of CMOS electronics and MEMS micromechanisms allows the implementation of new task-level micromanipulation strategies. New low-level control algorithms (actuator gaits) were also demonstrated. The array was programmed to perform several kinds of manipulation tasks, including linear translation, diagonal motion, as well as vector field operations such as squeeze field and radial field orienting and centering. Preliminary experiments were also performed using thin silicon dice of about 3 mm/spl times/3 mm/spl times/0.5 mm size as the object being moved.

High-throughput, data-directed computational protocols for Structural Genomics (or Proteomics) are required in order to evaluate the protein products of genes for structure and function at rates comparable to current gene-sequencing technology. This paper presents the JIGSAW algorithm, a novel high-throughput, automated approach to protein structure characterization with nuclear magnetic resonance (NMR). JIGSAW applies graph algorithms and probabilistic reasoning techniques, enforcing first-principles consistency rules in order to overcome a 5-10% signal-to-noise ratio. It consists of two main components: (1) graph-based secondary structure pattern identification in unassigned heteronuclear NMR data, and (2) assignment of spectral peaks by probabilistic alignment of identified secondary structure elements against the primary sequence. JIGSAW's deferment of assignment until after secondary structure identification differs greatly from traditional approaches, which begin by correlating peaks among dozens of experiments. By deferring assignment, JIGSAW not only eliminates this bottleneck, it also allows the number of experiments to be reduced from dozens to four, none of which requires 13 C-labeled protein. This in turn dramatically reduces the amount and expense of wet lab molecular biology for protein expression and purification, as well as the total spectrometer time to collect data.Our results for three test proteins demonstrate that we are able to identify and align approximately 80 percent of a-helical and 60 percent of b-sheet structure. JIGSAW is very fast, running in minutes on a Pentium-class Linux workstation. This approach yields quick and reasonably accurate (as opposed to the traditional slow and extremely accurate) structure calculations, utilizing a suite of graph analysis algorithms to compensate for the data sparseness. JIGSAW could be used for quick structural assays to speed data to the biologist early in the process of investigation, and could in principle be applied in an automation-like fashion to a large fraction of the proteome.

O ur goal is to em bed free-form constraints into a graphical m odel. W ith such constraints a graphic can m aintain its visual integrity— and break rules tastefully— while being m anipulated by a casualuser. A typicalparam eterized graphic does notm eet these needs because its configuration space contains nonsense im ages in m uch higher proportion than desirable im ages, and the casual user is apt to ruin the graphic on any attem pt to m odify oranim ate it.

Programmable force fields are a representation of a class of devices for distributed, nonprehensile manipulation for applications in parts feeding, sorting, positioning, and assembly. They generate force vector fields in which the parts move until they reach a stable equilibrium pose. Research has yielded open-loop strategies to uniquely position, orient, and sort parts. These strategies typically consist of several fields employed in sequence to achieve a desired final pose. The length of the sequence depends on the complexity of the part. We show that unique part poses can be achieved with just one field. First, we exhibit a single field that positions and orients any part (except certain symmetric parts) into two stable equilibrium poses. Then, we show that for any part there exists a field in which the part reaches a unique stable equilibrium pose (again, except for symmetric parts). Besides giving an optimal upper bound for unique parts positioning and orientation, our work gives further evidence that programmable force fields are a powerful tool for parts manipulation. Our second result also leads to the design of "universal parts feeders", proving an earlier conjecture about their existence. We argue that universal parts feeders are relatively easy to build, and we report on extensive simulation results which indicate that these devices may work very well in practice. We believe that the results in this paper could be the basis for a new generation of efficient, open-loop, parallel parts feeders.

We consider the family of area bisectors of a polygon (possibly with holes) in the plane, We say that two bisectors of a polygon P are combinatorially distinct if they induce different partitionings of the vertices of P. We show that there are simple polygons with n vertices that have fl(nz ) combinatorially distinct area bisectors (matching the obvious upper bound), and we present an output-sensitive algorithm for computing an explicit representation of all the bisectors of a given polygon.Our study is motivated by the development of novel, flexible feeding devices for parts positioning and orienting.The question of determining all the bisectors of polygonal parts arises in connection with the development of efficient part positioning strategies when using these devices.

Distributed manipulation experiments were performed using a massively-parallel, microfabricated actuator array. An organic ciliary array of thin-film polyimide bimorph microactuators exploiting combined thermal and electrostatic control was employed to implement task-level, sensorless manipulation strategies for macroscopic objects. The tasks of parts-translation, -rotation, -orientation, and -centering were demonstrated using small integrated circuit (IC) dice. Strategies were programmed in a fine-grained SIMD (single instruction, multiple data) fashion by specifying planar force vector fields. When a part is placed on the array, the programmed vector field induces a force and moment upon it. The part's equilibrium states may be predicted and cascaded (using a sequence of fields) to bring the part to a desired final state. Vector fields with and without potential were tested in experiments, and the behavior of parts in the fields was compared with the theory of programmable vector fields. These fields were implemented by actuating the organic cilia in a cyclic, gait-like fashion. Motion in non-principal (e.g. diagonal) directions was effected by a pairwise coupling of the cilia to implement virtual cilia. These experiments suggest that MEMS actuator arrays are useful for parts-orientation, -posing, -transfer, -singulation, and -sorting.

We have designed and implemented multi-agent strategies for manipulation tasks by distributing mechanically-based sequential algorithms across several autonomous spatially-separated agents, such as mobile robots. Our experience using mobile robots for the manipulation of large objects (couches, boxes, file cabinets, etc.) leads us to recommend a minimalist architecture for multi-agent programming. In particular, our methodology has led us to derive asynchronous distributed strategies that require no direct communication between agents, and very sparse geometric and dynamic models of the objects our robots manipulate. We argue for a design principle called supermodularity, which is orthogonal both to the notion of modularity in cognitive AI and also to horizontal decomposition (the non-modularity advocated in the subsumption/connectionist literature.) Finally, we discuss a simple mobotscheme infrastructure to implement supermodular architectures. In the past few years we have programmed many supermodular manipulation protocols and tested them extensively on our team of mobile robots. We describe why we think the supermodular infrastructure results in robust, simple, readable, manipulation strategies that can be recycled and reused.

Programmable vector fields can be used to control a variety of flexible planar parts feeders. When a part is placed on our devices, the programmed vector field induces a force and moment upon it. Over time, the part may come to rest in a dynamic equilibrium state. We demonstrate lower bounds on what the devices cannot do, and results on a classification of control strategies. We suggest sufficient conditions for programmable fields to induce well-behaved equilibria on every part placed on our devices. We define composition operators to build complex strategies from simple ones, and show the resulting fields are also well-behaved. We discuss whether fields outside this class can be useful and free of pathology. Using these tools, we describe new manipulation algorithms, and improve existing planning algorithms by a quadratic factor, and the plan-length by a linear factor. We relax earlier dynamic and mechanical assumptions to obtain more robust and flexible strategies. Finally, we consider parts feeders that can only implement a very limited "vocabulary" of vector fields. We discuss the trade-off between mechanical complexity and planning complexity.

The authors wish to organize furniture in a room with a team of robots that can push objects. The authors show how coordinated pushing by robots can change the pose (position and orientation) of objects and then they ask whether planning, global control, and explicit communication are necessary for cooperatively changing the pose of objects. The authors answer in the negative and present, as witnesses, four cooperative manipulation protocols that use different amounts of state, sensing, and communication. The authors analyze these protocols in the information invariant framework. The authors formalize the notion of resource tradeoffs for robot protocols and give the tradeoffs for the specific protocols discussed here.

We consider the problem of determining the information requirements to perform robot tasks, using the concept of information invariants. This paper represents our attempt to characterize a family of complicated and subtle issues concerned with measuring robot task complexity. We also provide a first approximation to a purely operational theory that addresses a narrow but interesting special case. We discuss several measures for the information complexity of a task: (a) How much internal state should the robot retain? (b) How many cooperating agents are required, and how much communication between them is necessary? (c) How can the robot change (side-effect) the environment in order to record state or sensory information to perform a task? (d) How much information is provided by sensors? and (e) How much computation is required by the robot? We consider how one might develop a kind of “calculus” on (a)–(e) in order to compare the power of sensor systems analytically. To this end, we attempt to develop a notion of information invariants. We develop a theory whereby one sensor can be “reduced” to another (much in the spirit of computation-theoretic reductions), by adding, deleting, and reallocating (a)–(e) among collaborating autonomous agents.

This paper investigates manipulation tasks with arrays of microelectromechanical structures (MEMS). We develop a geometric model for the mechanics of microactuators and a theory of sensorless, parallel manipulation, and we describe efficient algorithms for their evaluation. The theory of limit surfaces offers a purely geometric characterization of microscale contacts between actuator and moving object, which can be used to efficiently predict the motion of the object on an actuator array. It is shown how simple actuator control strategies can be used to uniquely align a part up to symmetry without sensor feedback. This theory is applicable to a wide range of microactuator arrays. Our actuators are oscillating structures of single-crystal silicon fabricated in a IC-compatible process. Calculations show that these actuators are strong enough to levitate and move, for example, a piece of paper.>

We consider the problem of planning the configuration of a sensor within the context of a robotic task. In this paper, we focus on geometrically specified tasks in the plane, and give algorithms for computing the regions from which an idealized point-and-shoot sensor can detect a polygonal robot. Our main algorithm allows sensor configurations from which the robot may be partially obstructed, and computes the regions from which the robot can be detected as it translates through the goal at a known orientation. This algorithm runs in time O(kmn/sup 3/(n+m)) for an environment of complexity n, a robot of complexity m, and a goal of complexity k. The regions constructed can be used by an active sensing system to configure sensors that are guaranteed to observe the robot as it enters the goal.>

Donald (1993) described a manipulation task for cooperating mobile robots that can push large, heavy objects. There, the author asked whether explicit local and global communication between the agents can be removed from a family of pushing protocols. In this paper, the authors answer in the affirmative. They do so by using the general methods of Donald for analyzing information invariants. The authors discuss several measures for the information complexity of the task of pushing with cooperating mobile robots, and they present a methodology for creating new manipulation strategies out of existing ones. The authors develop and analyze synchronous and asynchronous manipulation protocols for a small team of cooperating mobile robots than can push large boxes. The protocols described have been implemented in several forms on the Cornell mobile robots in the authors' laboratory.>

Kinodynamicplanmng attempts to solve a robot motion problem subject to simultaneous kinematic and dynamics constraints.In the general problem, ggven a robot system, we must find a minimal-time trajectory that goes from a start position and veloclty to a goal position and velocity while avoiding obstacles by a safety margur and respecting constraints cm velocity and acceleration.We consider the simplified case of a point mass under Newtoman mechanics.together with velocity and acceleration bounds.The point must be flown from a start to a goal, amidst polyhedral obstacles in 2D or 3D.Although exact sohztions to this problem are not known, we provide the first provably good approximation algorlthm, and show that it runs in polynomial time.

Algorithms in computational geometry often use the real-RAM model of computation. This model as-sumes that exact real numbers can be stored in mem-

A principled theory of sensing and action is crucial in developing task-level programming for autonomous mobile robots. A framework for such a theory is proposed, providing both a precise vocabulary and also appropriate computational machinery for working with issues of information flow in and through a robot system equipped with various types of sensors and operating in a dynamic unstructured environment. The authors focus on the problem of constructing virtual sensors out of concrete sensors. Virtual sensors may be defined in terms of existing concrete sensors. A method of task-directed construction of such virtual sensors is described. Virtual sensors are queried in robot programs much as their concrete counterparts are. In allowing the task to direct the composition of virtual sensors, robot programs which are organized in such a way as to guide the robot toward acquiring the information it needs to accomplish the task can be derived. Many information-acquisition and representational issues are made explicit.>

The authors have implemented a software environment that permits a small mobile robot to be programmed using the Scheme programming language. The environment supports incremental modifications to running programs and interactive debugging using a distributed read-evaluate-print loop. The programming environment separates the essential onboard run-time system from the development environment, which runs on a separate workstation. The development environment takes advantage of the workstation's large address space and user environment. It is fully detachable, so that the robot can operate autonomously if desired, and can be reattached for retrospective analysis of the robots behavior. To make concurrent applications easier to write, the run-time library provides multitasking and synchronization primitives. Tasks are lightweight, and all tasks run in the same address space.>

An algorithm for computing the homology type of a triangulation is analyzed. By triangulation is meant a finite simplicial complex; its homology type is given by its homology groups (with integer coefficients). The algorithm could be used in computer-aided design to tell whether two finite-element meshes or Bezier-spline surfaces are of the same topological type, and whether they can be embedded in R/sup 3/. Homology computation is a pure combinatorial problem of considerable intrinsic interest. While the worst-case bounds obtained for this algorithm are poor, it is argued that many triangulations (in general) and virtually all triangulations in design are very sparse in a particular sense. This sparseness measure is formalized, and a probabilistic analysis of the sparse case is performed to show that the expected running time, of the algorithm is roughly quadratic in the geometric complexity (number of simplices) and linear in the dimension.>

Consideration is given to how a robot may interpret its sensors and direct its actions so as to gain more information about the world, and to accomplish manipulation tasks. The focus is on general techniques for coping with uncertainty, specifically, to sense the state of the task, adapt to changes, and reason to select actions to gain information and achieve the goal. When the environment is integrated through sensors, one in effect views a projection of the world onto the space of possible sensor values. The structure of this sensor space and its relationship to the world is investigated. It is observed that sensors partition the world into perceptual equivalence classes that can serve as natural landmarks. By analyzing the properties of these equivalence classes a lattice and a bundle structure for the information available to the robot through sensing and action are developed. This yields a framework in which algorithms for sensor-based planning and reasoning are developed and characterized.>

The kinodynamic planning problem is, given a robot system, to find a trajectory from a start state to a goal state, while avoiding obstacles by a safety margin delta (v) and respecting dynamics bounds. Provably good polynomial-time approximation algorithms for optimal kinodynamic planning find trajectories within in of optimal and have a time complexity polynomial in 1/ in and in the geometric complexity of the robot world. The authors obtain such algorithms to find near-optimal trajectories obeying piecewise constant extremal controls and bang-bang control. Previous provably good kinodynamic planning algorithms for robot arms produce nonextremal, and hence locally nonoptimal trajectories. Using parameters in /sub T/ and in /sub S/ and describe closeness to optimality in execution time and observance of the safety margin, the authors derive equicomplexity curves to show how their algorithms permit to tradeoffs between time and safety.>

Considers a theory of planning, sensing and action in which the fundamental building blocks are, in effect, the 'recognizable sets'-that is, the places in the world that the robot can recognize and distinguish between. To this end the authors observe that viewing the world through sensors, partitions the world into 'perceptual equivalence classes.' The more information the sensors provide, the 'finer' this partition is. Various possible partitions of the world fit into a lattice structure. This lattice structure captures the information or knowledge state about the world. Using this theory the authors develop notions of task-directed planning and show how history can be used to direct actions and gain information. The authors investigate the structure of the recognizability lattice and its relationship to the world. The authors consider how to compute perceptual equivalence classes both from a model, and incrementally, from the world. Finally, the authors investigate mathematical properties that can help the robot generate disambiguating strategies to gain information about the world to accomplish a task.>

We consider the following problem: given a robot system, find a minimal-time trajectory from a start state to a goal state, while avoiding obstacles by a speed-dependent safety margin and respecting dynamics bounds. In [CDRX] we developed a provably good approximation algorithm for the minimum-time trajectory problem for a robot system with decoupled dynamics bounds. This algorithm differed from previous work in three ways: it is possible (1) to bound the goodness of the approximation by an error term ε (2) to polynomially bound the running time (complexity) of our algorithm; and (3) to express the complexity as a polynomial function of the error term.

For pt.I see Cornell Computer Science Tech. Report (1989). A fully algorithmic, combinatorially precise approach to designing devices so that they are easy to assemble and (optional) hard to disassemble is presented. The analysis can be used to validate good designs and can be iterated to generate improved designs. The approach is based on an algorithm for predicting the motion of flexible objects in contact. Such objects are intended to model snap-fastener-type devices, which are very useful in assembly design. The authors describe the algorithm, its implementation in a system for predicting and analyzing the motion of snap-fastener-type devices, and experiments run using the system to analyze and design particular devices. The issues discussed include: the relevance of the approach to engineering, the computational methods employed, the algebraic techniques for predicting motions in contact with rotational compliance, and issues of robustness and stability of the geometric and algebraic algorithms. Subtle mechanical difficulties arise in predicting motions under rotational compliance. The authors discuss these problems and their solutions.>

We present a real-time robot motion planner that is fast and complete to a resolution. The technique is guaranteed to find a path if one exists at the resolution, and all paths returned are safe. The planner can handle any polyhedral geometry of robot and obstacles, including disjoint and highly concave unions of polyhedra.The planner uses standard graphics hardware to rasterize configuration space obstacles into a series of bitmap slices, and then uses dynamic programming to create a navigation function (a discrete vector-valued function) and to calculate paths in this rasterized space. The motion paths which the planner produces are minimal with respect to an L1 (Manhattan) distance metric that includes rotation as well as translation.Several examples are shown illustrating the competence of the planner at generating planar rotational and translational plans for complex two and three dimensional robots. Dynamic motion sequences, including complicated and non-obvious backtracking solutions, can be executed in real time.

The authors describe the first implementation of a good polynomial-time approximation algorithm for kinodynamic planning. Attention is given to the following problem: given a robot system, find a minimal-time trajectory from a start position and velocity to a goal position and velocity, while avoiding obstacles and respecting dynamic constraints on velocity and acceleration. From the class of approximate minimal-time trajectories for a given problem instance that the theoretical algorithm would find, the proposed implementation will find a trajectory with minimal useless chattering. In addition, the authors present an improved analysis of the accuracy of the approximation strength of this approach. This analysis reveals that the algorithm produces approximations good to a small additive error in state space and exact in time while only sacrificing the epsilon -approximation factor in safety, where epsilon is an error term. In addition, the analysis halves the polynomial complexity of the algorithm in (1/ epsilon ), and it provides a simple characterization of when the algorithm will find a trajectory that is exact at the start and goal.>

In earlier work, B.R. Donald (1988, 1989) implemented an automated compliant motion planner based on a geometric theory of error detection and recovery (EDR). In the present work, an attempt is made to validate the theory, in part, by executing the plans it has generated on a physical force-controlled robot. The planner, LIMITED, accepts as input geometric descriptions of the environment and bounds on sensing and control uncertainties, and synthesizes motion sequences that, when executed, recognizably achieve the goal when possible and signal failure otherwise. The motions are compliant; that is, surfaces can be used to guide motions toward a goal. Experimental results attained in executing two plans earlier generated by LIMITED are presented. The first plan is for the task of inserting a planar peg into a planar hole, with geometric model uncertainty. This plan was found to be quite robust. The second plan meshes two gears in the plane. This plan proved less robust than the peg insertion plan, and the authors examine why this is so.>

We consider the computational complexity of planning compliant motions in the plane, given geometric bounds on the uncertainty in sensing and control. We can give efficient algorithms for generating and verifying compliant motion strategies that are guaranteed to succeed as long as the sensing and control uncertainties lie within the specified bounds. We also consider the case where a compliant motion plan is required to succeed over some parametric family of geometries. While these problems are known to be intractable in 3D, we identify tractable subclasses in the plane.

The following problem, is considered: given a robot system find a minimal-time trajectory from a start position and velocity to a goal position and velocity, while avoiding obstacles and respecting dynamic constraints on velocity and acceleration. The simplified case of a point mass under Newtonian mechanics together with velocity and acceleration bounds is considered. The point must be flown from a start to a goal, amid 2-D or 3-D polyhedral obstacles. While exact solutions to this problem are not known, the first provably good approximation algorithm is given and shown to run in polynomial time.

The author describes techniques for planning multistep error detection and recovery strategies for robots operating in the presence of uncertainty. He introduces two approaches for their synthesis: the push-forward algorithm and failure mode analysis. He has implemented the theory in the form of a planner, called LIMITED, in the domain of planar assemblies.>

Robots must plan and execute tasks in the presence of uncertainty. Uncertainty arises from sensing errors, control errors, and uncertainty in the geometric models of the environment and of the robot. The last, which we will call model uncertainty, has received little previous attention. In this paper we present a formal framework for computing motion strategies which are guaranteed to succeed in the presence of all three kinds of uncertainty. We show that it is effectively computable for some simple cases. The motion strategies we consider include sensor-based gross motions, compliant motions, and simple pushing motions. We show that model uncertainty can be represented by position uncertainty in a generalized configuration space. We describe the structure of this space, and how motion strategies may be planned in it. It is not always possible to find plans that are guaranteed to succeed. In the presence of model error, such plans may not even exist. For this reason we investigate error detection and recovery (EDR) strategies. We characterize what such strategies are, and propose a formal framework for constructing them. Our theory represents what is perhaps the first systematic attack on the problem of error detection and recovery based on geometric and physical reasoning.

We are interested in Voronoi diagrams as a tool in robot path planning, where the search for a path in an τ dimensional space may be simplified to a search on an τ - 1 dimensional Voronoi diagram. We define a Voronoi diagram V based on a measure of distance which is not a true metric. This formulation has lower algebraic complexity than the usual definition, which is a considerable advantage in motion planning problems with many degrees of freedom. In its simplest form, the measure of distance between a point and a polytope is the maximum of the distances of the point from the half-spaces which pass through faces of the polytope. More generally, the measure is defined in configuration spaces which represent rotation. The Voronoi diagram defined using this distance measure is no longer a strong deformation retract of free space, but it has the following useful property: any path through free space which starts and ends on the diagram can be continuously deformed so that it lies entirely on the diagram. Thus it is still complete for motion planning, but it has lower algebraic complexity than a diagram based on the Euclidean metric.

This paper addresses robot motion planning with uncertainty in sensing, control, and the geometric models of the robot and environment. To this end, a formal framework for error detection and recovery is proposed.

The Movers' problem is to find a continuous, collision-free path for a moving object through an environment containing obstacles. The classical formulation of the three-dimensional Movers' problem is as fellows: given an arbitrary rigid polyhedral moving object P with three translational and three rotational degrees of freedom, find a contineous, collision-free path taking P from some initial configuration to a desired goal configuration. The six degree or freedom Movers' problem may be transformed into a point, navigation problem in a six-dimensional configuration space (called C-Space). The C-Space obstacles, which characterize the physically unachievable configurations, are directly represented by six-dimensional manifolds whose boundaries are five dimensional C-surfaces. By characterizing these surfaces and their intersections, collision-free paths may be found by the closure of three operators which (i) slide along 5-dimensional level C-surfaces parallel to C-Space obstacles; (ii) slide along 1- to 4-dimensional intersections of level C-surfaces; and (iii) jump between 6-dimensional obstacles. We show how to construct and represent C-surfaces and their intersection manifolds. We also demonstrate how to intersect trajectories with the boundaries of C</-Space obstacles. The theory and representations we develop extend to Cartesian manipulators with six degrees of freedom.