@article{moll2016structure-guided-selection-of-specificity-determining, abstract = {Background: The human kinome contains many important drug targets. It is well-known that inhibitors of protein kinases bind with very different selectivity profiles. This is also the case for inhibitors of many other protein families. The increased availability of protein 3D structures has provided much information on the structural variation within a given protein family. However, the relationship between structural variations and binding specificity is complex and incompletely understood. We have developed a structural bioinformatics approach which provides an analysis of key determinants of binding selectivity as a tool to enhance the rational design of drugs with a specific selectivity profile. Results: We propose a greedy algorithm that computes a subset of residue positions in a multiple sequence alignment such that structural and chemical variation in those positions helps explain known binding affinities. By providing this information, the main purpose of the algorithm is to provide experimentalists with possible insights into how the selectivity profile of certain inhibitors is achieved, which is useful for lead optimization. In addition, the algorithm can also be used to predict binding affinities for structures whose affinity for a given inhibitor is unknown. The algorithm's performance is demonstrated using an extensive dataset for the human kinome. Conclusion: We show that the binding affinity of 38 different kinase inhibitors can be explained with consistently high precision and accuracy using the variation of at most six residue positions in the kinome binding site. We show for several inhibitors that we are able to identify residues that are known to be functionally important.}, author = {Moll, Mark and Finn, Paul W. and Kavraki, Lydia E.}, doi = {10.1186/s12864-016-2790-3}, note = {PMID: 27556159, PMCID: PMC5001202}, journal = {BMC Genomics}, keywords = {functional annotation}, pages = {431}, volume = {17 (Suppl.\ 4)}, title = {Structure-Guided Selection of Specificity Determining Positions in the Human Kinome}, year = {2016} }
@inproceedings{moll2015structure-guided-selection-of-specificity-determining, abstract = {It is well-known that inhibitors of protein kinases bind with very different selectivity profiles. This is also the case for inhibitors of many other protein families. A better understanding of binding selectivity would enhance the design of drugs that target only a subfamily, thereby minimizing possible side-effects. The increased availability of protein 3D structures has made it possible to study the structural variation within a given protein family. However, not every structural variation is related to binding specificity. We propose a greedy algorithm that computes a subset of residue positions in a multiple sequence alignment such that structural and chemical variation in those positions helps explain known binding affinities. By providing this information, the main purpose of the algorithm is to provide experimentalists with possible insights into how the selectivity profile of certain inhibitors is achieved, which is useful for lead optimization. In addition, the algorithm can also be used to predict binding affinities for structures whose affinity for a given inhibitor is unknown. The algorithm's performance is demonstrated using an extensive dataset for the human kinome, which includes a large and important set of drug targets. We show that the binding affinity of 38 different kinase inhibitors can be explained with consistently high precision and accuracy using the variation of at most six residue positions in the kinome binding site.}, author = {Moll, Mark and Finn, Paul W. and Kavraki, Lydia E.}, booktitle = {Proceedings of the IEEE International Conference on Bioinformatics and Biomedicine (BIBM)}, month = nov, title = {Structure-Guided Selection of Specificity Determining Positions in the Human Kinome}, year = {2015}, pages = {21--28}, keywords = {functional annotation}, doi = {10.1109/BIBM.2015.7359650} }
@article{bryant-moll2013combinatorial-clustering-of, title = {Combinatorial clustering of residue position subsets predicts inhibitor affinity across the human kinome}, journal = {PLoS Computational Biology}, volume = {9}, number = {6}, year = {2013}, pages = {e1003087}, abstract = {The protein kinases are a large family of enzymes that play fundamental roles in propagating signals within the cell. Because of the high degree of binding site similarity shared among protein kinases, designing drug compounds with high specificity among the kinases has proven difficult. However, computational approaches to comparing the 3-dimensional geometry and physicochemical properties of key binding site residue positions have been shown to be informative of inhibitor selectivity. The Combinatorial Clustering Of Residue Position Subsets (ccorps) method, introduced here, provides a semi-supervised learning approach for identifying structural features that are correlated with a given set of annotation labels. Here, ccorps is applied to the problem of identifying structural features of the kinase atp binding site that are informative of inhibitor binding. ccorps is demonstrated to make perfect or near-perfect predictions for the binding affinity profile of 8 of the 38 kinase inhibitors studied. Additionally, ccorps is shown to identify shared structural features across phylogenetically diverse groups of kinases that are correlated with binding affinity for particular inhibitors; such instances of structural similarity among phylogenetically diverse kinases are also shown to not be rare among kinases. Finally, these function-specific structural features may serve as potential starting points for the development of highly specific kinase inhibitors.}, keywords = {functional annotation, proteins and drugs}, doi = {10.1371/journal.pcbi.1003087}, note = {PMCID: PMC3675009, PMID: 23754939}, author = {Bryant, Drew H and Moll, Mark and Finn, Paul W. and Kavraki, Lydia E} }
@inproceedings{chyan-moll2013improving-prediction-of, title = {Improving the Prediction of Kinase Binding Affinity Using Homology Models}, booktitle = {Proceedings of the Computational Structural Bioinformatics Workshop at the ACM Conference on Bioinformatics, Computational Biology and Biomedical Informatics}, year = {2013}, address = {Washington, DC}, abstract = {Kinases are a class of proteins very important to drug design; they play a pivotal role in many of the cell signaling pathways in the human body. Thus, many drug design studies involve finding inhibitors for kinases in the human kinome. However, identifying inhibitors of high selectivity is a difficult task. As a result, computational prediction methods have been developed to aid in this drug design problem. The recently published CCORPS method [3] is a semi-supervised learning method that identifies structural features in protein kinases that correlate with kinase binding affinity to inhibitors. However, CCORPS is dependent on the amount of available structural data. The amount of known structural data for proteins is extremely small compared to the amount of known protein sequences. To paint a clearer picture of how kinase structure relates to binding affinity, we propose extending the CCORPS method by integrating homology models for predicting kinase binding affinity. Our results show that using homology models significantly improves the prediction performance for some drugs while maintaining comparable performance for other drugs.}, keywords = {functional annotation}, doi = {10.1145/2506583.2506704}, author = {Chyan, Jeffrey and Moll, Mark and Kavraki, Lydia E} }
@article{moll-bryant2011labelhash-server-and, title = {The LabelHash Server and Tools for Substructure-Based Functional Annotation}, journal = {Bioinformatics}, volume = {27}, number = {15}, year = {2011}, month = aug, pages = {2161--2162}, abstract = {Summary: The LabelHash server and tools are designed for large- scale substructure comparison. The main use is to predict the function of unknown proteins. Given a set of (putative) functional residues, LabelHash finds all occurrences of matching substructures in the entire Protein Data Bank, along with a statistical significance estimate and known functional annotations for each match. The results can be downloaded for further analysis in any molecular viewer. For Chimera there is a plugin to facilitate this process. Availability: The website is free and open to all users with no login requirements at http://labelhash.kavrakilab.org.}, keywords = {functional annotation}, doi = {10.1093/bioinformatics/btr343}, note = {PMID: 21659320}, author = {Moll, Mark and Bryant, Drew H and Kavraki, Lydia E} }
@article{moll-bryant2010labelhash-algorithm-for, title = {The LabelHash Algorithm for Substructure Matching}, journal = {BMC Bioinformatics}, volume = {11}, year = {2010}, month = dec, pages = {555}, abstract = {Background There is an increasing number of proteins with known structure but unknown function. Determining their function would have a significant impact on understanding diseases and designing new therapeutics. However, experimental protein function determination is expensive and very time-consuming. Computational methods can facilitate function determination by identifying proteins that have high structural and chemical similarity. Results We present LabelHash, a novel algorithm for matching substructural motifs to large collections of protein structures. The algorithm consists of two phases. In the first phase the proteins are preprocessed in a fashion that allows for instant lookup of partial matches to any motif. In the second phase, partial matches for a given motif are expanded to complete matches. The general applicability of the algorithm is demonstrated with three different case studies. First, we show that we can accurately identify members of the enolase superfamily with a single motif. Next, we demonstrate how LabelHash can complement SOIPPA, an algorithm for motif identification and pairwise substructure alignment. Finally, a large collection of Catalytic Site Atlas motifs is used to benchmark the performance of the algorithm. LabelHash runs very efficiently in parallel; matching a motif against all proteins in the 95\% sequence identity filtered non-redundant Protein Data Bank typically takes no more than a few minutes. The LabelHash algorithm is available through a web server and as a suite of standalone programs at http://labelhash.kavrakilab.org. The output of the LabelHash algorithm can be further analyzed with Chimera through a plugin that we developed for this purpose. Conclusions LabelHash is an efficient, versatile algorithm for large-scale substructure matching. When LabelHash is running in parallel, motifs can typically be matched against the entire PDB on the order of minutes. The algorithm is able to identify functional homologs beyond the twilight zone of sequence identity and even beyond fold similarity. The three case studies presented in this paper illustrate the versatility of the algorithm.}, keywords = {functional annotation}, issn = {1471-2105}, doi = {10.1186/1471-2105-11-555}, note = {PMCID: PMC2996407, PMID: 21070651}, author = {Moll, Mark and Bryant, Drew H and Kavraki, Lydia E} }
@article{bryant-moll2010analysis-of-substructural, title = {Analysis of substructural variation in families of enzymatic proteins with applications to protein function prediction}, journal = {BMC Bioinformatics}, volume = {11}, number = {242}, year = {2010}, pages = {242}, abstract = {Background Structural variations caused by a wide range of physicochemical and biological sources directly influence the function of a protein. For enzymatic proteins, the structure and chemistry of the catalytic binding site residues can be loosely defined as a substructure of the protein. Comparative analysis of drug-receptor substructures across and within species has been used for lead evaluation. Substructure-level similarity between the binding sites of functionally similar proteins has also been used to identify instances of convergent evolution among proteins. In functionally homologous protein families, shared chemistry and geometry at catalytic sites provide a common, local point of comparison among proteins that may differ significantly at the sequence, fold, or domain topology levels. Results This paper describes two key results that can be used separately or in combination for protein function analysis. The Family-wise Analysis of SubStructural Templates (FASST) method uses all-against-all substructure comparison to determine Substructural Clusters (SCs). SCs characterize the binding site substructural variation within a protein family. In this paper we focus on examples of automatically determined SCs that can be linked to phylogenetic distance between family members, segregation by conformation, and organization by homology among convergent protein lineages. The Motif Ensemble Statistical Hypothesis (MESH) framework constructs a representative motif for each protein cluster among the SCs determined by FASST to build motif ensembles that are shown through a series of function prediction experiments to improve the function prediction power of existing motifs. Conclusions FASST contributes a critical feedback and assessment step to existing binding site substructure identification methods and can be used for the thorough investigation of structure-function relationships. The application of MESH allows for an automated, statistically rigorous procedure for incorporating structural variation data into protein function prediction pipelines. Our work provides an unbiased, automated assessment of the structural variability of identified binding site substructures among protein structure families and a technique for exploring the relation of substructural variation to protein function. As available proteomic data continues to expand, the techniques proposed will be indispensable for the large-scale analysis and interpretation of structural data.}, keywords = {functional annotation, proteins and drugs}, doi = {10.1186/1471-2105-11-242}, note = {PMCID: PMC2885373, PMID: 20459833}, author = {Bryant, Drew H and Moll, Mark and Chen, B. Y. and Fofanov, Viacheslav Y. and Kavraki, Lydia E} }
@inproceedings{moll-kavraki2008labelhash-flexible-and, title = {LabelHash: A Flexible and Extensible Method for Matching Structural Motifs}, booktitle = {Automated Function Prediction / BioSapiens meeting (AFP-BioSapiens)}, year = {2008}, note = {Available from Nature Precedings.}, keywords = {functional annotation}, doi = {10.1038/npre.2008.2199.1}, author = {Moll, Mark and Kavraki, Lydia E} }
@inproceedings{moll-kavraki2008matching-of-structural, title = {Matching of Structural Motifs Using Hashing on Residue Labels and Geometric Filtering for Protein Function Prediction}, booktitle = {The Seventh Annual International Conference on Computational Systems Bioinformatics (CSB2008)}, year = {2008}, pages = {157-168}, abstract = {There is an increasing number of proteins with known structure but unknown function. Determining their function would have a significant impact on understanding diseases and designing new therapeutics. However, experimental protein function determination is expensive and very time-consuming. Computational methods can facilitate function determination by identifying proteins that have high structural and chemical similarity. Our focus is on methods that determine binding site similarity. Although several such methods exist, it still remains a challenging problem to quickly find all functionally-related matches for structural motifs in large data sets with high specificity. In this context, a structural motif is a set of 3D points annotated with physicochemical information that characterize a molecular function. We propose a new method called LabelHash that creates hash tables of $n$-tuples of residues for a set of targets. Using these hash tables, we can quickly look up partial matches to a motif and expand those matches to complete matches. We show that by applying only very mild geometric constraints we can find statistically significant matches with extremely high specificity in very large data sets and for very general structural motifs. We demonstrate that our method requires a reasonable amount of storage when employing a simple geometric filter and further improves on the specificity of our previous work while maintaining very high sensitivity. Our algorithm is evaluated on 20 homolog classes and a non-redundant version of the Protein Data Bank as our background data set. We use cluster analysis to analyze why certain classes of homologs are more difficult to classify than others. The LabelHash algorithm is implemented on a web server at http://kavrakilab.org/labelhash/.}, keywords = {functional annotation}, doi = {10.1142/9781848162648_0014}, url = {http://csb2008.org/csb2008papers/077Moll.pdf}, author = {Moll, Mark and Kavraki, Lydia E} }
@article{kristensen-ward2008prediction-of-enzyme, title = {Prediction of enzyme function based on {3D} templates of evolutionarily important amino acids}, journal = {BMC Bioinformatics}, volume = {9}, year = {2008}, abstract = {Background: Structural genomics projects such as the Protein Structure Initiative (PSI) yield many new structures, but often these have no known molecular functions. One approach to recover this information is to use 3D templates{\textemdash}structure-function motifs that consist of a few functionally critical amino acids and may suggest functional similarity when geometrically matched to other structures. Since experimentally determined functional sites are not common enough to define 3D templates on a large scale, this work tests a computational strategy to select relevant residues for 3 emplates. Results: Based on evolutionary information and heuristics, an Evolutionary Trace Annotation (ETA) pipeline built templates for 98 enzymes, half taken from the PSI, and sought matches in a non- redundant structure database. On average each template matched 2.7 distinct proteins, of which 2.0 share the first three Enzyme Commission digits as the template{\textquoteright}s enzyme of origin. In many cases (61\%) a single most likely function could be predicted as the annotation with the most matches, and in these cases such a plurality vote identified the correct function with 87\% accuracy. ETA was also found to be complementary to sequence homology-based annotations. When matches are required to both geometrically match the 3D template and to be sequence homologs found by BLAST or PSI-BLAST, the annotation accuracy is greater than either method alone, especially in the region of lower sequence identity where homology-based annotations re east eliable. Conclusions: These data suggest that knowledge of evolutionarily important residues improves functional annotation among distant enzyme homologs. Since, unlike other 3D template approaches, the ETA method bypasses the need for experimental knowledge of the catalytic mechanism, it should prove a useful, large scale, and general adjunct to combine with other methods to decipher rotein unction n he tructural poteome.}, keywords = {functional annotation}, doi = {10.1186/1471-2105-9-17}, note = {PMCID: PMC2219985, PMID: 18190718}, author = {Kristensen, D. M. and Ward, Matthew R. and Lisewski, A. M. and Edrin, S. and Chen, B. Y. and Fofanov, Viacheslav Y. and Kimmel, Marek and Kavraki, Lydia E and Lichtarge, Olivier} }
@inproceedings{fofanov-chen2008statistical-model-to, title = {A Statistical Model to Correct Systematic Bias Introduced by Algorithmic Thresholds in Protein Structural Comparison Algorithms}, booktitle = {IEEE International Conference on Bioinformatics and Biomedicine (BIBM)}, year = {2008}, address = {Philadelphia, PA}, abstract = {The identification of protein function is crucial to understanding cellular processes and selecting novel proteins as drug targets. However, experimental methods for determining protein function can be expensive and time-consuming. Protein partial structure comparison methods seek to guide and accelerate the process of function determination by matching characterized functional site representations, motifs, to substructures within uncharacterized proteins, matches. One common difficulty of all protein structural comparison techniques is the computational cost of obtaining a match. In an effort to maintain practical efficiency, some algorithms employ efficient geometric threshold-based searches to eliminate biologically irrelevant matches. Thresholds refine and accelerate the method by limiting the number of potential matches that need to be considered. However, because statistical models rely on the output of the geometric matching method to accurately measure statistical significance, geometric thresholds can also artificially distort the basis of statistical models, making statistical scores dependant on geometric thresholds and potentially causing significant reductions in accuracy of the functional annotation method. This paper proposes a point-weight based correction approach to quantify and model the dependence of statistical scores to account for the systematic bias introduced by heuristics. Using a benchmark dataset of 20 structural motifs, we show that the point-weight correction procedure accurately models the information lost during the geometric comparison phase, removing systematic bias and greatly reducing misclassification rates of functionally related proteins, while maintaining specificity.}, keywords = {functional annotation}, doi = {10.1109/BIBMW.2008.4686202}, author = {Fofanov, Viacheslav Y. and Chen, B. Y. and Bryant, Drew H and Moll, Mark and Lichtarge, Olivier and Kavraki, Lydia E and Kimmel, Marek} }
@article{chen-bryant2007cavity-scaling-automated, title = {Cavity Scaling: Automated Refinement of Cavity-Aware Motifs in Protein Function Prediction}, journal = {Journal of Bioinformatics and Computational Biology}, volume = {5}, number = {2a}, year = {2007}, pages = {353-382}, abstract = { Algorithms for geometric and chemical comparison of protein substructure can be useful for many applications in protein function prediction. These motif matching algorithms identify matches of geometric and chemical similarity between well-studied functional sites, motifs, and substructures of functionally uncharacterized proteins, targets. For the purpose of function prediction, the accuracy of motif matching algorithms can be evaluated with the number of statistically significant matches to functionally related proteins, true positives (TPs), and the number of statistically insignificant matches to functionally unrelated proteins, false positives (FPs). Our earlier work developed cavity-aware motifs which use motif points to represent functionally significant atoms and C-spheres to represent functionally significant volumes. We observed that cavity-aware motifs match significantly fewer FPs than matches containing only motif points. We also observed that high-impact C-spheres, which significantly contribute to the reduction of FPs, can be isolated automatically with a technique we call Cavity Scaling. This paper extends our earlier work by demonstrating that C-spheres can be used to accelerate point-based geometric and chemical comparison algorithms, maintaining accuracy while reducing runtime. We also demonstrate that the placement of C-spheres can significantly affect the number of TPs and FPs identified by a cavity-aware motif. While the optimal placement of C-spheres remains a diffcult open problem, we compared two logical placement strategies to better understand C-sphere placement.}, keywords = {functional annotation}, doi = {10.1142/S021972000700276X}, note = {PMID: 17589966}, author = {Chen, B. Y. and Bryant, Drew H and Fofanov, Viacheslav Y. and Kristensen, D. M. and Cruess, A. E. and Kimmel, Marek and Lichtarge, Olivier and Kavraki, Lydia E} }
@inproceedings{chen-bryant2007composite-motifs-integrating, title = {Composite Motifs Integrating Multiple Protein Structures Increase Sensitivity for Function Prediction}, booktitle = {Computational Systems Bioinformatics Conference (CSB2007)}, year = {2007}, pages = {343-355}, abstract = {The study of disease often hinges on the biological function of proteins, but determining protein function is a difficult experimental process. To minimize duplicated effort, algorithms for function prediction seek characteristics indicative of possible protein function. One approach is to identify substructural matches of geometric and chemical similarity between motifs representing known active sites and target protein structures with unknown function. In earlier work, statistically significant matches of certain effective motifs have identified functionally related active sites. Effective motifs must be carefully designed to maintain similarity to functionally related sites (sensitivity) and avoid incidental similarities to functionally unrelated protein geometry (specificity). Existing techniques design motifs using the geometry of a single protein structure. Poor selection of this structure can limit motif effectiveness if the selected functional site lacks similarity to functionally related sites. To address this problem, this paper presents composite motifs, which combine structures of functionally related active sites to potentially increase sensitivity. Our experimentation compares the effectiveness of composite motifs with simple motifs designed from single protein structures. On six distinct families of functionally related proteins, leave-one-out testing showed that composite motifs had sensitivity comparable to the most sensitive of all simple motifs and specificity comparable to the average simple motif. On our data set, we observed that composite motifs simultaneously capture variations in active site conformation, diminish the problem of selecting motif structures, and enable the fusion of protein structures from diverse data sources.}, note = {PMID: 17951837}, keywords = {functional annotation}, author = {Chen, B. Y. and Bryant, Drew H and Cruess, A. E. and Bylund, J. H. and Fofanov, Viacheslav Y. and Kimmel, Marek and Lichtarge, Olivier and Kavraki, Lydia E} }
@article{chen-fofanov2007mash-pipeline-for, title = {The {MASH} Pipeline for Protein Function Prediction and an Algorithm for the Geometric Refinement of {3D} Motifs}, journal = {Journal of Computational Biology}, volume = {14}, number = {6}, year = {2007}, pages = {791-816}, abstract = {The development of new and effective drugs is strongly affected by the need to identify drug targets and to reduce side effects. Resolving these issues depends partially on a thorough understanding of the biological function of proteins. Unfortunately, the experimental determination of protein function is expensive and time consuming. To support and accelerate the determination of protein functions, algorithms for function prediction are designed to gather evidence indicating functional similarity with well studied proteins. One such approach is the MASH pipeline, described in the first half of this paper. MASH identifies matches of geometric and chemical similarity between motifs, representing known functional sites, and substructures of functionally uncharacterized proteins (targets). Observations from several research groups concur that statistically significant matches can indicate functionally related active sites. One major subproblem is the design of effective motifs, which have many matches to functionally related targets (sensitive motifs), and few matches to functionally unrelated targets (specific motifs). Current techniques select and combine structural, physical, and evolutionary properties to generate motifs that mirror functional characteristics in active sites. This approach ignores incidental similarities that may occur with functionally unrelated proteins. To address this problem, we have developed Geometric Sieving (GS), a parallel distributed algorithm that efficiently refines motifs, designed by existing methods, into optimized motifs with maximal geometric and chemical dissimilarity from all known protein structures. In exhaustive comparison of all possible motifs based on the active sites of 10 well-studied proteins, we observed that optimized motifs were among the most sensitive and specific.}, keywords = {functional annotation}, doi = {10.1089/cmb.2007.R017}, note = {PMID: 17691895}, author = {Chen, B. Y. and Fofanov, Viacheslav Y. and Bryant, Drew H and Dodson, B. D. and Kristensen, D. M. and Lisewski, A. M. and Kimmel, Marek and Lichtarge, Olivier and Kavraki, Lydia E} }
@inproceedings{chen-bryant2006cavity-aware-motifs-reduce, title = {Cavity-Aware Motifs Reduce False Positives in Protein Function Prediction}, booktitle = {Systems Bioinformatics Conference (CSB)}, volume = {4}, year = {2006}, month = aug, pages = {311-323}, address = {Stanford, CA}, abstract = {Determining the function of proteins is a problem with immense practical impact on the identification of inhibition targets and the causes of side effects. Unfortunately, experimental determination of protein function is expensive and time consuming. For this reason, algorithms for computational function prediction have been developed to focus and accelerate this effort. These algorithms are comparison techniques which identify matches of geometric and chemical similarity between motifs, representing known functional sites, and substructures of functionally uncharacterized proteins (targets). Matches of statistically significant geometric and chemical similarity can identify targets with active sites cognate to the matching motif. Unfortunately statistically significant matches can include false positive matches to functionally unrelated proteins. We target this problem by presenting Cavity Aware Match Augmentation (CAMA), a technique which uses C-spheres to represent active clefts which must remain vacant for ligand binding. CAMA rejects matches to targets without similar binding volumes. On 18 sample motifs, we observed that introducing C-spheres eliminated 80\% of false positive matches and maintained 87\% of true positive matches found with identical motifs lacking C-spheres. Analyzing a range of C-sphere positions and sizes, we observed that some high-impact C-spheres eliminate more false positive matches than others. High-impact C-spheres can be detected with a geometric analysis we call Cavity Scaling, permitting us to refine our initial cavity-aware motifs to contain only high-impact C-spheres. In the absence of expert knowledge, Cavity Scaling can guide the design of cavity-aware motifs to eliminate many false positive matches.}, keywords = {functional annotation, fundamentals of protein modeling}, url = {http://lib.bioinfo.pl/pmid:17369649}, note = {PMID: 17369649}, author = {Chen, B. Y. and Bryant, Drew H and Fofanov, Viacheslav Y. and Kristensen, D. M. and Cruess, A. E. and Kimmel, Marek and Lichtarge, Olivier and Kavraki, Lydia E} }
@inproceedings{chen-fofanov2006geometric-sieving-automated, title = {Geometric Sieving: Automated Distributed Optimization of 3D Motifs for Protein Function Prediction}, booktitle = {Research in Computational Biology: 10th Annual International Conference (RECOMB)}, year = {2006}, note = {Published in Lecture Notes in Computer Science, A. Apostolico, C. Guerra, S. Istrail, P. Pevzner, M. Waterman (Eds), Springer, 3909/2006, 500-515}, month = apr, address = {Venice, Italy}, abstract = {Determining the function of all proteins is a recurring theme in modern biology and medicine, but the sheer number of proteins makes experimental approaches impractical. For this reason, current efforts have considered in silico function prediction in order to guide and accelerate the function determination process. One approach to predicting protein function is to search functionally uncharacterized protein structures (targets), for substructures with geometric and chemical similarity (matches), to known active sites (motifs). Finding a match can imply that the target has an active site similar to the motif, suggesting functional homology. An effective function predictor requires effective motifs - motifs whose geometric and chemical characteristics are detected by comparison algorithms within functionally homologous targets (sensitive motifs), which also are not detected within functionally unrelated targets (specific motifs). Designing effective motifs is a difficult open problem. Current approaches select and combine structural, physical, and evolutionary properties to design motifs that mirror functional characteristics of active sites. We present a new approach, Geometric Sieving (GS), which refines candidate motifs into optimized motifs with maximal geometric and chemical dissimilarity from all known protein structures. The paper discusses both the usefulness and the efficiency of GS. We show that candidate motifs from six well-studied proteins, including alpha-Chymotrypsin, Dihydrofolate Reductase, and Lysozyme, can be optimized with GS to motifs that are among the most sensitive and specific motifs possible for the candidate motifs. For the same proteins, we also report results that relate evolutionarily important motifs with motifs that exhibit maximal geometric and chemical dissimilarity from all known protein structures. Our current observations show that GS is a powerful tool that can complement existing work on motif design and protein function prediction.}, keywords = {functional annotation, fundamentals of protein modeling}, doi = {10.1007/11732990_42}, author = {Chen, B. Y. and Fofanov, Viacheslav Y. and Bryant, Drew H and Dodson, B. D. and Kristensen, D. M. and Lisewski, A. M. and Kimmel, Marek and Lichtarge, Olivier and Kavraki, Lydia E} }
@article{shehu-clementi2006modeling-protein-conformational, title = {Modeling Protein Conformational Ensembles: From Missing Loops to Equilibrium Fluctuations}, journal = {Proteins: Structure, Function and Bioinformatics}, volume = {65}, number = {1}, year = {2006}, pages = {164-179}, abstract = {Characterizing protein flexibility is an important goal for understanding the physical-chemical principles governing biological function. This paper presents a Fragment Ensemble Method to capture the mobility of a protein fragment such as a missing loop and its extension into a Protein Ensemble Method to characterize the mobility of an entire protein at equilibrium. The underlying approach in both methods is to combine a geometric exploration of conformational space with a statistical mechanics formulation to generate an ensemble of physical conformations on which thermodynamic quantities can be measured as ensemble averages. The Fragment Ensemble Method is validated by applying it to characterize loop mobility in both instances of strongly stable and disordered loop fragments. In each instance, fluctuations measured over generated ensembles are consistent with data from experiment and simulation. The Protein Ensemble Method captures the mobility of an entire protein by generating and combining ensembles of conformations for consecutive overlapping fragments defined over the protein sequence. This method is validated by applying it to characterize flexibility in ubiquitin and protein G. Thermodynamic quantities measured over the ensembles generated for both proteins are fully consistent with available experimental data. On these proteins, the method recovers nontrivial data such as order parameters, residual dipolar couplings, and scalar couplings. Results presented in this work suggest that the proposed methods can provide insight into the interplay between protein flexibility and function.}, keywords = {functional annotation}, doi = {10.1002/prot.21060}, note = {PMID: 16917941}, author = {Shehu, A. and Clementi, C. and Kavraki, Lydia E} }
@article{kristensen-chen2006recurrent-use-of, title = {Recurrent Use of Evolutionary Importance for Functional Annotation of Proteins Based on Local Structural Similarity}, journal = {Protein Science}, volume = {15}, number = {6}, year = {2006}, pages = {1530-1536}, keywords = {functional annotation}, doi = {10.1110/ps.062152706}, note = {PMCID: PMC2242527, PMID: 16672239}, author = {Kristensen, D. M. and Chen, B. Y. and Fofanov, Viacheslav Y. and Ward, Matthew R. and Lisewski, A. M. and Kimmel, Marek and Kavraki, Lydia E and Lichtarge, Olivier} }
@inproceedings{chen-fofanov2005algorithms-for-structural, title = {Algorithms for Structural Comparison and Statistical Analysis of 3D Protein Motifs}, booktitle = {Pacific Symposium on Biocomputing}, year = {2005}, publisher = {World Scientific}, address = {Hawaii, USA}, keywords = {functional annotation}, note = {PMID: 15759639}, author = {Chen, B. Y. and Fofanov, Viacheslav Y. and Kristensen, D. M. and Kimmel, Marek and Lichtarge, Olivier and Kavraki, Lydia E} }
@article{zhang-white2005improving-conformational-searches, title = {Improving Conformational Searches by Geometric Screening}, journal = {Bioinformatics}, volume = {21}, number = {5}, year = {2005}, pages = {624-630}, abstract = { Motivation: Conformational searches in molecular docking are a time-consuming process with wide range of applications. Favorable conformations of the ligands that successfully bind with receptors are sought to form stable ligand{\textendash}receptor complexes. Usually a large number of conformations are generated and their binding energies are examined. We propose adding a geometric screening phase before an energy minimization procedure so that only conformations that geometrically fit in the binding site will be prompted for energy calculation. Results: Geometric screening can drastically reduce the number of conformations to be examined from millions (or higher) to thousands (or lower). The method can also handle cases when there are more variables than geometric constraints. An early-stage implementation is able to finish the geometric filtering of conformations for molecules with up to nine variables in 1 min. To the best of our knowledge, this is the first time such results are reported deterministically.}, keywords = {functional annotation}, doi = {10.1093/bioinformatics/bti055}, note = {PMID: 15479715}, author = {Zhang, M. and White, R. A. and Wang, L. and Goldman, R. and Kavraki, Lydia E and Hassett, B.} }
@article{yao-kristensen2003accurate-sensitive-and, title = {An Accurate, Sensitive, and Scalable Method to Identify Functional Sites in Protein Structures}, journal = {Journal of Molecular Biology}, volume = {326}, number = {1}, year = {2003}, pages = {255-261}, abstract = {Functional sites determine the activity and interactions of proteins and as such constitute the targets of most drugs. However, the exponential growth of sequence and structure data far exceeds the ability of experimental techniques to identify their locations and key amino acids. To fill this gap we developed a computational Evolutionary Trace method that ranks the evolutionary importance of amino acids in protein sequences. Studies show that the best-ranked residues form fewer and larger structural clusters than expected by chance and overlap with functional sites, but until now the significance of this overlap has remained qualitative. Here, we use 86 diverse protein structures, including 20 determined by the structural genomics initiative, to show that this overlap is a recurrent and statistically significant feature. An automated ET correctly identifies seven of ten functional sites by the least favorable statistical measure, and nine of ten by the most favorable one. These results quantitatively demonstrate that a large fraction of functional sites in the proteome may be accurately identified from sequence and structure. This should help focus structure{\textendash}function studies, rational drug design, protein engineering, and functional annotation to the relevant regions of a protein.}, keywords = {functional annotation}, doi = {10.1016/S0022-2836(02)01336-0}, note = {PMID: 12547207}, author = {Yao, H. and Kristensen, D. M. and Mihalek, I. and Sowa, M. and Shaw, Ch. and Kimmel, Marek and Kavraki, Lydia E and Lichtarge, Olivier} }
@article{antunes2020-hla-arena, author = {Antunes, Dinler A. and Abella, Jayvee R. and Hall-Swan, Sarah and Devaurs, Didier and Conev, Anja and Moll, Mark and Liz\'{e}e, Gregory and Kavraki, Lydia E.}, title = {{HLA}-{A}rena: a customizable environment for the structural modeling and analysis of peptide-{HLA} complexes for cancer immunotherapy}, abstract = {PURPOSE: HLA protein receptors play a key role in cellular immunity. They bind intracellular peptides and display them for recognition by T-cell lymphocytes. Because T-cell activation is partially driven by structural features of these peptide-HLA complexes, their structural modeling and analysis are becoming central components of cancer immunotherapy projects. Unfortunately, this kind of analysis is limited by the small number of experimentally determined structures of peptide-HLA complexes. Overcoming this limitation requires developing novel computational methods to model and analyze peptide-HLA structures. METHODS: Here we describe a new platform for the structural modeling and analysis of peptide-HLA complexes, called HLA-Arena, which we have implemented using Jupyter Notebook and Docker. It is a customizable environment that facilitates the use of computational tools, such as APE-Gen and DINC, which we have previously applied to peptide-HLA complexes. By integrating other commonly used tools, such as MODELLER and MHCflurry, this environment includes support for diverse tasks in structural modeling, analysis, and visualization. RESULTS: To illustrate the capabilities of HLA-Arena, we describe 3 example workflows applied to peptide-HLA complexes. Leveraging the strengths of our tools, DINC and APE-Gen, the first 2 workflows show how to perform geometry prediction for peptide-HLA complexes and structure-based binding prediction, respectively. The third workflow presents an example of large-scale virtual screening of peptides for multiple HLA alleles. CONCLUSION: These workflows illustrate the potential benefits of HLA-Arena for the structural modeling and analysis of peptide-HLA complexes. Because HLA-Arena can easily be integrated within larger computational pipelines, we expect its potential impact to vastly increase. For instance, it could be used to conduct structural analyses for personalized cancer immunotherapy, neoantigen discovery, or vaccine development.}, journal = {JCO Clinical Cancer Informatics}, year = {2020}, volume = {4}, pages = {623--636}, keywords = {fundamentals of protein modeling, proteins and drugs, other biomedical computing}, doi = {10.1200/CCI.19.00123}, note = {PMID: 32667823, PMCID: 7397777}, month = jul }
@article{abella2020-frontiers-random-forest, author = {Abella, Jayvee R. and Antunes, Dinler A. and Clementi, Cecilia and Kavraki, Lydia E.}, title = {Large-scale structure-based prediction of stable peptide binding to Class I HLAs using random forests}, abstract = {Prediction of stable peptide binding to Class I HLAs is an important component for designing immunotherapies. While the best performing predictors are based on machine learning algorithms trained on peptide-HLA (pHLA) sequences, the use of structure for training predictors deserves further exploration. Given enough pHLA structures, a predictor based on the residue-residue interactions found in these structures has the potential to generalize for alleles with little or no experimental data. We have previously developed APE-Gen, a modeling approach able to produce pHLA structures in a scalable manner. In this work we use APE-Gen to model over 150,000 pHLA structures, the largest dataset of its kind, which were used to train a structure-based pan-allele model. We extract simple, homogenous features based on residue-residue distances between peptide and HLA, and build a random forest model for predicting stable pHLA binding. Our model achieves competitive AUROC values on leave-one-allele-out validation tests using significantly less data when compared to popular sequence-based methods. Additionally, our model offers an interpretation analysis that can reveal how the model composes the features to arrive at any given prediction. This interpretation analysis can be used to check if the model is in line with chemical intuition, and we showcase particular examples. Our work is a significant step towards using structure to achieve generalizable and more interpretable prediction for stable pHLA binding.}, keywords = {fundamentals of protein modeling, proteins and drugs, other biomedical computing}, doi = {10.3389/fimmu.2020.01583}, note = {PMID: 32793224, PMCID: PMC7387700}, journal = {Frontiers in Immunology}, year = {2020}, volume = {11}, number = {1583}, month = jul }
@article{abella2019-apegen, author = {Abella, Jayvee R. and Antunes, Dinler A. and Clementi, Cecilia and Kavraki, Lydia E.}, title = {APE-Gen: A Fast Method for Generating Ensembles of Bound Peptide-MHC Conformations}, journal = {Molecules}, volume = {24}, year = {2019}, number = {5}, article-number = {881}, url = {http://www.mdpi.com/1420-3049/24/5/881}, issn = {1420-3049}, abstract = {The Class I Major Histocompatibility Complex (MHC) is a central protein in immunology as it binds to intracellular peptides and displays them at the cell surface for recognition by T-cells. The structural analysis of bound peptide-MHC complexes (pMHCs) holds the promise of interpretable and general binding prediction (i.e., testing whether a given peptide binds to a given MHC). However, structural analysis is limited in part by the difficulty in modelling pMHCs given the size and flexibility of the peptides that can be presented by MHCs. This article describes APE-Gen (Anchored Peptide-MHC Ensemble Generator), a fast method for generating ensembles of bound pMHC conformations. APE-Gen generates an ensemble of bound conformations by iterated rounds of (i) anchoring the ends of a given peptide near known pockets in the binding site of the MHC, (ii) sampling peptide backbone conformations with loop modelling, and then (iii) performing energy minimization to fix steric clashes, accumulating conformations at each round. APE-Gen takes only minutes on a standard desktop to generate tens of bound conformations, and we show the ability of APE-Gen to sample conformations found in X-ray crystallography even when only sequence information is used as input. APE-Gen has the potential to be useful for its scalability (i.e., modelling thousands of pMHCs or even non-canonical longer peptides) and for its use as a flexible search tool. We demonstrate an example for studying cross-reactivity.}, doi = {10.3390/molecules24050881}, note = {PMID: 30832312, PMCID: PMC6429480}, keywords = {fundamentals of protein modeling} }
@article{hruska2018quantitative-comparison-of-adaptive-sampling, abstract = {Adaptive sampling methods, often used in combination with Markov state models, are becoming increasingly popular for speeding up rare events in simulation such as molecular dynamics (MD) without biasing the system dynamics. Several adaptive sampling strategies have been proposed, but it is not clear which methods perform better for different physical systems. In this work, we present a systematic evaluation of selected adaptive sampling strategies on a wide selection of fast folding proteins. The adaptive sampling strategies were emulated using models constructed on already existing MD trajectories. We provide theoretical limits for the sampling speed-up and compare the performance of different strategies with and without using some a priori knowledge of the system. The results show that for different goals, different adaptive sampling strategies are optimal. In order to sample slow dynamical processes such as protein folding without a priori knowledge of the system, a strategy based on the identification of a set of metastable regions is consistently the most efficient, while a strategy based on the identification of microstates performs better if the goal is to explore newer regions of the conformational space. Interestingly, the maximum speed-up achievable for the adaptive sampling of slow processes increases for proteins with longer folding times, encouraging the application of these methods for the characterization of slower processes, beyond the fast-folding proteins considered here.}, author = {Hruska, Eugen and Abella, Jayvee R. and N{\"u}ske, Feliks and Kavraki, Lydia E. and Clementi, Cecilia}, doi = {10.1063/1.5053582}, note = {PMID: 30599712}, journal = {The Journal of Chemical Physics}, month = dec, number = {24}, pages = {244119}, title = {Quantitative comparison of adaptive sampling methods for protein dynamics}, volume = {149}, year = {2018}, keywords = {fundamentals of protein modeling} }
@article{devaurs2018revealing-unknown-protein0structures, abstract = {Both experimental and computational methods are available to gather information about a protein’s conformational space and interpret changes in protein structure. However, experimentally observing and computationally modeling large proteins remain critical challenges for structural biology. Our work aims at addressing these challenges by combining computational and experimental techniques relying on each other to overcome their respective limitations. Indeed, despite its advantages, an experimental technique such as hydrogen-exchange monitoring cannot produce structural models because of its low resolution. Additionally, the computational methods that can generate such models suffer from the curse of dimensionality when applied to large proteins. Adopting a common solution to this issue, we have recently proposed a framework in which our computational method for protein conformational sampling is biased by experimental hydrogen-exchange data. In this paper, we present our latest application of this computational framework: generating an atomic-resolution structural model for an unknown protein state. For that, starting from an available protein structure, we explore the conformational space of this protein, using hydrogen-exchange data on this unknown state as a guide. We have successfully used our computational framework to generate models for three proteins of increasing size, the biggest one undergoing large-scale conformational changes.}, author = {Devaurs, Didier and Antunes, Dinler A. and Kavraki, Lydia E.}, title = {Revealing Unknown Protein Structures Using Computational Conformational Sampling Guided by Experimental Hydrogen-Exchange Data}, journal = {International Journal of Molecular Sciences}, year = {2018}, volume = {19}, number = {11}, pages = {3406}, doi = {10.3390/ijms19113406}, note = {PMID: 30384411, PMCID: PMC6280153}, keywords = {fundamentals of protein modeling} }
@article{abella2018maintaining-and-enhancing-diversity-of-sampled, abstract = {The ability to efficiently sample structurally diverse protein conformations allows one to gain a high-level view of a protein's energy landscape. Algorithms from robot motion planning have been used for conformational sampling and promote diversity by keeping track of ``coverage'' in conformational space based on the local sampling density. However, large proteins present special challenges. In particular, larger systems require running many concurrent instances of these algorithms, but these algorithms can quickly become memory intensive because they typically keep previously sampled conformations in memory to maintain coverage estimates. Additionally, many of these algorithms depend on defining useful perturbation strategies for exploring the conformational space, which is a very difficult task for large proteins because such systems are typically more constrained and exhibit complex motions. In this paper, we introduce two methodologies for maintaining and enhancing diversity in robotics-inspired conformational sampling. The first method leverages the use of a low-dimensional projection to define a global coverage grid that maintains coverage across concurrent runs of sampling. The second method is an automatic definition of a perturbation strategy through readily available flexibility information derived from B-factors, secondary structure, and rigidity analysis. Our results show a significant increase in the diversity of the conformations sampled for proteins consisting of up to 500 residues. The methodologies presented in this paper may be vital components for the scalability of robotics-inspired approaches.}, author = {Abella, Jayvee R. and Moll, Mark and Kavraki, Lydia E.}, doi = {10.1089/cmb.2017.0164}, journal = {Journal of Computational Biology}, keywords = {fundamentals of protein modeling}, note = {PMID: 29035572, PMCID: PMC5756939}, number = {1}, pages = {3--20}, title = {Maintaining and Enhancing Diversity of Sampled Protein Conformations in Robotics-Inspired Methods}, volume = {25}, year = {2018} }
@article{devaurs_16_icibm, author = {Devaurs, Didier and Papanastasiou, Malvina and Antunes, Dinler A. and Abella, Jayvee R. and Moll, Mark and Ricklin, Daniel and Lambris, John D. and Kavraki, Lydia E.}, title = {Native state of complement protein {C3d} analysed via hydrogen exchange and conformational sampling}, journal = {International Journal of Computational Biology and Drug Design}, keywords = {fundamentals of protein modeling}, volume = {11}, number = {1/2}, pages = {90-113}, doi = {10.1504/IJCBDD.2018.10011903}, note = {PMID: 30700993, PMCID: PMC6349257}, year = {2018}, abstract = {Hydrogen/deuterium exchange detected by mass spectrometry (HDX-MS) provides valuable information on protein structure and dynamics. Although HDX-MS data is often interpreted using crystal structures, it was suggested that conformational ensembles produced by molecular dynamics simulations yield more accurate interpretations. In this paper, we analyse the complement protein C3d through HDX-MS data and evaluate several interpretation methodologies, using an existing prediction model to derive HDX-MS data from protein structure. We perform an HDX-MS experiment on C3d and, then, to interpret and refine the obtained data, we look for a conformation (or conformational ensemble) of C3d that allows computationally replicating this data. First, we confirm that crystal structures are not a good choice. Second, we suggest that conformational ensembles produced by molecular dynamics simulations might not always be satisfactory either. Finally, we show that coarse-grained conformational sampling of C3d produces a conformation from which the HDX-MS data can be replicated and refined.} }
@article{devaurs-17-fmb, abstract = {Monitoring hydrogen/deuterium exchange (HDX) undergone by a protein in solution produces experimental data that translates into valuable information about the protein’s structure. Data produced by HDX experiments is often interpreted using a crystal structure of the protein, when available. However, it has been shown that the correspondence between experimental HDX data and crystal structures is often not satisfactory. This creates difficulties when trying to perform a structural analysis of the HDX data. In this paper, we evaluate several strategies to obtain a conformation providing a good fit to the experimental HDX data, which is a premise of structural analysis. We show that performing molecular dynamics simulations can be inadequate to obtain such conformations, and we propose a novel methodology involving a coarse-grained conformational sampling approach instead. By extensively exploring the intrinsic flexibility of a protein with this approach, we produce a conformational ensemble from which we extract a single conformation providing a good fit to the experimental HDX data. We successfully demonstrate the applicability of our method to four small and medium-sized proteins.}, keywords = {fundamentals of protein modeling}, author = {Devaurs, Didier and Antunes, Dinler A. and Papanastasiou, Malvina and Moll, Mark and Ricklin, Daniel and Lambris, John D. and Kavraki, Lydia E.}, title = {Coarse-grained conformational sampling of protein structure improves the fit to experimental hydrogen-exchange data}, journal = {Frontiers in Molecular Biosciences}, volume = {4}, number = {13}, doi = {10.3389/fmolb.2017.00013}, note = {PMCID: PMC5344923, PMID: 28344973}, year = {2017} }
@article{novinskaya2016_defining_proj, author = {Novinskaya, Anastasia and Devaurs, Didier and Moll, Mark and Kavraki, Lydia E.}, journal = {Journal of Computational Biology}, year = {2017}, volume = {24}, number = {1}, pages = {79--89}, title = {Defining low-dimensional projections to guide protein conformational sampling}, abstract = {Exploring the conformational space of proteins is critical to characterizing their functions. Numerous methods have been proposed to sample a protein's conformational space, including techniques developed in the field of robotics and known as sampling-based motion-planning algorithms (or sampling-based planners). However, these algorithms suffer from the curse of dimensionality when applied to large pro- teins. Many sampling-based planners attempt to mitigate this issue by keeping track of sampling density to guide conformational sampling toward unexplored regions of the conformational space. This is often done using low-dimensional projections as an indirect way to reduce the dimensionality of the exploration problem. However, how to choose an appropriate projection and how much it influences the planner's performance are still poorly understood problems. In this paper, we introduce two methodologies defining low-dimensional projections that can be used by sampling-based planners for protein conformational sampling. The first method leverages information about a protein's flexibility to construct projections that can efficiently guide conformational sampling, when expert knowledge is available. The second method builds similar projections automatically, without expert intervention. We evaluate the projections produced by both methodologies on two conformational-search problems involving three middle-size proteins. Our experiments demonstrate that (i) defining projections based on expert knowledge can benefit conformational sampling, and (ii) automatically constructing such projections is a reasonable alternative.}, keywords = {fundamentals of protein modeling}, doi = {10.1089/cmb.2016.0144}, note = {PMID: 27892695} }
@inproceedings{novinskaya2015_guid_proj, author = {Novinskaya, Anastasia and Devaurs, Didier and Moll, Mark and Kavraki, Lydia E.}, booktitle = {Proceedings of the IEEE International Conference on Bioinformatics and Biomedicine Workshops (BIBMW)}, year = {2015}, month = nov, title = {Improving protein conformational sampling by using guiding projections}, abstract = {Sampling-based motion planning algorithms from the field of robotics have been very successful in exploring the conformational space of proteins. However, studying the flexibility of large proteins with hundreds or thousands of Degrees of Freedom (DoFs) remains a big challenge. Large proteins are also highly-constrained systems, which makes them more challenging for standard robotic approaches. So-called ``expansive'' motion planning algorithms were specifically developed to address highly-dimensional and highly- constrained problems. Many such planners employ a low- dimensional projection to estimate exploration coverage and direct their search based on this information. We believe that such a projection plays an essential role in the success of these planners. This paper shows how the low-dimensional projection used by expansive planners can be tailored with respect to a given molecular system to enhance the process of conformational sampling. We introduce a methodology to generate an expert projection using any available information about a given protein. We evaluate this methodology on several conformational search problems involving proteins with hundreds of DoFs. Our experiments demonstrate that incorporating expert knowledge into the projection can significantly benefit the exploration process.}, pages = {1272-1279}, keywords = {fundamentals of protein modeling}, doi = {10.1109/BIBM.2015.7359863} }
@article{gipson-hsu2012computational-models-of, title = {Computational Models of Proteins Kinematics and Dynamics: Beyond Simulation}, journal = {Annual Reviews of Analytical Chemistry}, volume = {5}, year = {2012}, month = apr, pages = {273-291}, abstract = {Physics-based simulation represents a powerful method for investigating the time-varying behavior of dynamic protein systems at high spatial and temporal resolution. Such simulations, however, can be prohibitively difficult or lengthy for large proteins or when probing the lower-resolution, long-timescale behaviors of proteins generally. Importantly, not all questions about a protein system require full space and time resolution to produce an informative answer. For instance, by avoiding the simulation of uncorrelated, high-frequency atomic movements, a larger, domain-level picture of protein dynamics can be revealed. The purpose of this review is to highlight the growing body of complementary work that goes beyond simulation. In particular, this review focuses on methods that address kinematics and dynamics, as well as those that address larger organizational questions and can quickly yield useful information about the long-timescale behavior of a protein.}, keywords = {fundamentals of protein modeling, kinodynamic systems}, doi = {10.1146/annurev-anchem-062011-143024}, note = {PMCID: PMC4866812, PMID: 22524225}, msid = {NIHMS712423}, author = {Gipson, B and Hsu, David and Kavraki, Lydia E and Latombe, Jean-Claude} }
@article{shehu-kavraki2012modeling-structures-and, title = {Modeling Structures and Motions of Loops in Protein Molecules}, journal = {Entropy}, volume = {14}, year = {2012}, month = feb, pages = {252--290}, abstract = {Unlike the secondary structure elements that connect in protein structures, loop fragments in protein chains are often highly mobile even in generally stable proteins. The structural variability of loops is often at the center of a protein{\textquoteright}s stability, folding, and even biological function. Loops are found to mediate important biological processes, such as signaling, protein-ligand binding, and protein-protein interactions. Modeling conformations of a loop under physiological conditions remains an open problem in computational biology. This article reviews computational research in loop modeling, highlighting progress and challenges. Important insight is obtained on potential directions for future research.}, keywords = {fundamentals of protein modeling}, doi = {10.3390/e14020252}, author = {Shehu, A. and Kavraki, Lydia E} }
@article{haspel-moll2010tracing-conformational-changes, title = {Tracing conformational changes in proteins}, journal = {BMC Structural Biology}, volume = {10}, number = {Suppl. 1}, year = {2010}, pages = {S1}, abstract = {Background: Many proteins undergo extensive conformational changes as part of their functionality. Tracing these changes is important for understanding the way these proteins function. Traditional biophysics-based conformational search methods require a large number of calculations and are hard to apply to large-scale conformational motions. Results: In this work we investigate the application of a robotics-inspired method, using backbone and limited side chain representation and a coarse grained energy function to trace large-scale conformational motions. We tested the algorithm on four well known medium to large proteins and we show that even with relatively little information we are able to trace low-energy conformational pathways efficiently. The conformational pathways produced by our methods can be further filtered and refined to produce more useful information on the way proteins function under physiological conditions. Conclusions: The proposed method effectively captures large-scale conformational changes and produces pathways that are consistent with experimental data and other computational studies. The method represents an important first step towards a larger scale modeling of more complex biological systems.}, keywords = {fundamentals of protein modeling, proteins and drugs}, doi = {10.1186/1472-6807-10-S1-S1}, note = {PMCID: PMC2873824, PMID: 20487508}, author = {Haspel, N. and Moll, Mark and Baker, M. L. and Chiu, W. and Kavraki, Lydia E} }
@article{heath-kavraki2007from-coarse-grain-to, title = {From coarse-grain to all-atom: Toward multiscale analysis of protein landscapes}, journal = {Proteins: Structure, Function and Bioinformatics}, volume = {68}, number = {3}, year = {2007}, month = aug, pages = {646-661}, abstract = {Multiscale methods are becoming increasingly promising as a way to characterize the dynamics of large protein systems on biologically relevant time-scales. The underlying assumption in multiscale simulations is that it is possible to move reliably between different resolutions. We present a method that efficiently generates realistic all-atom protein structures starting from the C(alpha) atom positions, as obtained for instance from extensive coarse-grain simulations. The method, a reconstruction algorithm for coarse-grain structures (RACOGS), is validated by reconstructing ensembles of coarse-grain structures obtained during folding simulations of the proteins src-SH3 and S6. The results show that RACOGS consistently produces low energy, all-atom structures. A comparison of the free energy landscapes calculated using the coarse-grain structures versus the all-atom structures shows good correspondence and little distortion in the protein folding landscape.}, keywords = {fundamentals of protein modeling}, doi = {10.1002/prot.21371}, note = {PMID: 17523187}, author = {Heath, A. P. and Kavraki, Lydia E and Clementi, C.} }
@inproceedings{chen-bryant2006cavity-aware-motifs-reduce, title = {Cavity-Aware Motifs Reduce False Positives in Protein Function Prediction}, booktitle = {Systems Bioinformatics Conference (CSB)}, volume = {4}, year = {2006}, month = aug, pages = {311-323}, address = {Stanford, CA}, abstract = {Determining the function of proteins is a problem with immense practical impact on the identification of inhibition targets and the causes of side effects. Unfortunately, experimental determination of protein function is expensive and time consuming. For this reason, algorithms for computational function prediction have been developed to focus and accelerate this effort. These algorithms are comparison techniques which identify matches of geometric and chemical similarity between motifs, representing known functional sites, and substructures of functionally uncharacterized proteins (targets). Matches of statistically significant geometric and chemical similarity can identify targets with active sites cognate to the matching motif. Unfortunately statistically significant matches can include false positive matches to functionally unrelated proteins. We target this problem by presenting Cavity Aware Match Augmentation (CAMA), a technique which uses C-spheres to represent active clefts which must remain vacant for ligand binding. CAMA rejects matches to targets without similar binding volumes. On 18 sample motifs, we observed that introducing C-spheres eliminated 80\% of false positive matches and maintained 87\% of true positive matches found with identical motifs lacking C-spheres. Analyzing a range of C-sphere positions and sizes, we observed that some high-impact C-spheres eliminate more false positive matches than others. High-impact C-spheres can be detected with a geometric analysis we call Cavity Scaling, permitting us to refine our initial cavity-aware motifs to contain only high-impact C-spheres. In the absence of expert knowledge, Cavity Scaling can guide the design of cavity-aware motifs to eliminate many false positive matches.}, keywords = {functional annotation, fundamentals of protein modeling}, url = {http://lib.bioinfo.pl/pmid:17369649}, note = {PMID: 17369649}, author = {Chen, B. Y. and Bryant, Drew H and Fofanov, Viacheslav Y. and Kristensen, D. M. and Cruess, A. E. and Kimmel, Marek and Lichtarge, Olivier and Kavraki, Lydia E} }
@article{das-moll2006low-dimensional-free-energy-landscapes, title = {Low-dimensional Free-energy Landscapes of Protein-Folding Reactions by Nonlinear Dimensionality Reduction}, journal = {Proceedings of the National Academy of Sciences}, volume = {103}, number = {26}, year = {2006}, month = jun, pages = {9885-9890}, abstract = {The definition of reaction coordinates for the characterization of a protein-folding reaction has long been a controversial issue, even for the {\textquotedblleft}simple{\textquotedblright} case in which one single free-energy barrier separates the folded and unfolded ensemble. We propose a general approach to this problem to obtain a few collective coordinates by using nonlinear dimensionality reduction. We validate the usefulness of this method by characterizing the folding landscape associated with a coarse-grained protein model of src homology 3 as sampled by molecular dynamics simulations. The folding free-energy landscape projected on the few relevant coordinates emerging from the dimensionality reduction can correctly identify the transition-state ensemble of the reaction. The first embedding dimension efficiently captures the evolution of the folding process along the main folding route. These results clearly show that the proposed method can efficiently find a low-dimensional representation of a complex process such as protein folding.}, keywords = {fundamentals of protein modeling, proteins and drugs}, doi = {10.1073/pnas.0603553103}, note = {PMCID: PMC1502548, PMID: 16785435}, author = {Das, P. and Moll, Mark and Stamati, H. and Kavraki, Lydia E and Clementi, C.} }
@inproceedings{chen-fofanov2006geometric-sieving-automated, title = {Geometric Sieving: Automated Distributed Optimization of 3D Motifs for Protein Function Prediction}, booktitle = {Research in Computational Biology: 10th Annual International Conference (RECOMB)}, year = {2006}, note = {Published in Lecture Notes in Computer Science, A. Apostolico, C. Guerra, S. Istrail, P. Pevzner, M. Waterman (Eds), Springer, 3909/2006, 500-515}, month = apr, address = {Venice, Italy}, abstract = {Determining the function of all proteins is a recurring theme in modern biology and medicine, but the sheer number of proteins makes experimental approaches impractical. For this reason, current efforts have considered in silico function prediction in order to guide and accelerate the function determination process. One approach to predicting protein function is to search functionally uncharacterized protein structures (targets), for substructures with geometric and chemical similarity (matches), to known active sites (motifs). Finding a match can imply that the target has an active site similar to the motif, suggesting functional homology. An effective function predictor requires effective motifs - motifs whose geometric and chemical characteristics are detected by comparison algorithms within functionally homologous targets (sensitive motifs), which also are not detected within functionally unrelated targets (specific motifs). Designing effective motifs is a difficult open problem. Current approaches select and combine structural, physical, and evolutionary properties to design motifs that mirror functional characteristics of active sites. We present a new approach, Geometric Sieving (GS), which refines candidate motifs into optimized motifs with maximal geometric and chemical dissimilarity from all known protein structures. The paper discusses both the usefulness and the efficiency of GS. We show that candidate motifs from six well-studied proteins, including alpha-Chymotrypsin, Dihydrofolate Reductase, and Lysozyme, can be optimized with GS to motifs that are among the most sensitive and specific motifs possible for the candidate motifs. For the same proteins, we also report results that relate evolutionarily important motifs with motifs that exhibit maximal geometric and chemical dissimilarity from all known protein structures. Our current observations show that GS is a powerful tool that can complement existing work on motif design and protein function prediction.}, keywords = {functional annotation, fundamentals of protein modeling}, doi = {10.1007/11732990_42}, author = {Chen, B. Y. and Fofanov, Viacheslav Y. and Bryant, Drew H and Dodson, B. D. and Kristensen, D. M. and Lisewski, A. M. and Kimmel, Marek and Lichtarge, Olivier and Kavraki, Lydia E} }
@inproceedings{zhang-kavraki2002approximating-solutions-of, title = {Approximating Solutions of Molecular Inverse Kinematics Problems by Subdivision}, booktitle = {The 24th International Conference of the IEEE Engineering in Medicine and Biology Society (EMBS) and the Annual Meeting of the Biomedical Engineering Society (BMES)}, year = {2002}, month = oct, pages = {2182-2183}, publisher = {IEEE Press}, abstract = {Modeling in biological systems is important at every level from the molecular, to the cellular, to the tissue level. In this paper we discuss the following problem in molecular modeling: given a three-dimensional conformation of a molecule, how do we automatially compute the conformations of the molecule that satisfy certain spatial constraints, that is, certain "feature" atoms of the molecule are in user-specified positions? This task is important in the analysis of receptor-ligand interactions and in other applications such as drug design and protein folding. Using an analogy between robots and molecules, we use the term inverse kinematics to describe the above conformational problems. To solve these problems, we first derive a system of polynomial equations. Then, we adopt a technique based on the Groebner basis from algebraic geometry and develop a novel subdivision algorithm to approximate the real solutions. The approximated solutions can then be used as the starting conformations for existing (heuristic) energy minimization procedures that try to satisfy the target positions of feature atoms and reduce the overall energy of the conformation. To our knowledge, this is the first time that a rigorous algebraic methodology has been used to approximate molecular inverse kinematics solutions.}, keywords = {fundamentals of protein modeling}, doi = {10.1109/IEMBS.2002.1053229}, author = {Zhang, M. and Kavraki, Lydia E} }
@inproceedings{zhang-kavraki2002solving-molecular-inverse, title = {Solving Molecular Inverse Kinematics Problems for Protein Folding and Drug Design}, booktitle = {Currents in Computational Molecular Biology}, year = {2002}, note = {Book includes short papers from The Sixth ACM International Conference on Research in Computational Biology (RECOMB 2002), Washington, DC, 2002}, month = apr, pages = {214-215}, publisher = {ACM Press}, keywords = {fundamentals of protein modeling}, author = {Zhang, M. and Kavraki, Lydia E} }
@article{zhang-kavraki2002new-method-for, title = {A New Method for Fast and Accurate Derivation of Molecular Conformations}, journal = {Journal of Chemical Information and Computer Sciences}, volume = {42}, number = {1}, year = {2002}, pages = {64-70}, abstract = {During molecular simulations, three-dimensional conformations of biomolecules are calculated from the values of their bond angles, bond lengths, and torsional angles. In this paper we study how to efficiently derive three-dimensional molecular conformations from the values of torsional angles. This case is of broad interest as torsional angles greatly affect molecular shape and are always taken into account during simulations. We first review two widely used methods for deriving molecular conformations, the simple rotations scheme and the Denavit-Hartenberg local frames method. We discuss their disadvantages which include extensive bookkeeping, accumulation of numerical errors, and redundancies in the local frames used. Then we introduce a new, fast, and accurate method called the atomgroup local frames method. This new method not only eliminates the disadvantages of earlier approaches but also provides lazy evaluation of atom positions and reduces the computational cost. Our method is especially useful in applications where many conformations are generated or updated such as in energy minimization and conformational search.}, keywords = {fundamentals of protein modeling}, doi = {10.1021/ci010327z}, note = {PMID: 11855967}, author = {Zhang, M. and Kavraki, Lydia E} }
@inproceedings{teodoro-phillips2001molecular-docking-problem, title = {Molecular Docking: A Problem with Thousands of Degrees of Freedom}, booktitle = {Proc. of the 2001 IEEE International Conference on Robotics and Automation (ICRA 2001)}, year = {2001}, month = may, pages = {960-966}, publisher = {IEEE press}, address = {Seoul, Korea}, abstract = {This paper reports on the problem of docking a highly flexible small molecule to the pocket of a highly flexible receptor macromolecule. The prediction of the intermolecular complex is of vital importance for the development of new therapeutics as docking can alter the chemical behavior of the receptor macromolecule. We first present current methods for docking, which have several limitations. Some of these methods consider only the flexibility of the ligand solving a problem with a few tens of degrees of freedom. When the receptor flexibility is taken into account several hundreds or even thousands of degrees of freedom need to be considered. Most methods take into account only a small number of these degrees of freedom by using chemical knowledge specific to the problem. We show how to use a singular value decomposition of molecular dynamics trajectories to automatically obtain information about the global flexibility of the receptor and produce interesting conformations that can be used for docking purposes.}, keywords = {fundamentals of protein modeling}, doi = {10.1109/ROBOT.2001.932674}, author = {Teodoro, Miguel L. and {Phillips Jr.}, George N. and Kavraki, Lydia E} }
@inproceedings{zhang-kavraki2001efficiently-maintaining-molecular, title = {Efficiently Maintaining Molecular Conformations Using Local Frames}, booktitle = {Currents in Computational Molecular Biology}, year = {2001}, note = {Book includes short papers from The Fifth ACM International Conference on Research in Computational Biology (RECOMB), Montreal, Canada, 2001}, pages = {97-98}, publisher = {Les Publications CRM}, address = {Montreal, Canada}, keywords = {fundamentals of protein modeling}, author = {Zhang, M. and Kavraki, Lydia E} }
@inproceedings{teodoro-phillips2000singular-value-decomposition, title = {Singular Value Decomposition of Protein Conformational Motions: Application to {HIV-1} Protease}, booktitle = {Currents in Computational Molecular Biology}, year = {2000}, note = {Book includes short papers from The Forth ACM International Conference on Computational Biology (RECOMB), 2000}, month = apr, pages = {198-199}, publisher = {Universal Academy Press Inc.}, address = {Tokyo, Japan}, keywords = {fundamentals of protein modeling}, author = {Teodoro, Miguel L. and {Phillips Jr.}, George N. and Kavraki, Lydia E} }
@article{chamzas2022-learn-retrieve, abstract = {Recent work has demonstrated that motion planners’ performance can be significantly improved by retrieving past experiences from a database. Typically, the experience database is queried for past similar problems using a similarity function defined over the motion planning problems. However, to date, most works rely on simple hand-crafted similarity functions and fail to generalize outside their corresponding training dataset. To address this limitation, we propose (FIRE), aframework that extracts local representations of planning problems and learns a similarity function over them. To generate the training data we introduce a novel self-supervised method that identifies similar and dissimilar pairs of local primitives from past solution paths. With these pairs, a Siamese network is trained with the contrastive loss and the similarity function is realized in the network’s latent space. We evaluate FIRE on an 8-DOF manipulator in five categories of motion planning problems with sensed environments. Our experiments show that FIRE retrieves relevant experiences which can informatively guide sampling-based planners even in problems outside its training distribution, outperforming other baselines.}, author = {Chamzas, Constantinos and Cullen, Aedan and Shrivastava, Anshumali and E. Kavraki, Lydia}, keywords = {fundamentals of sampling-based motion planning}, booktitle = {2022 International Conference on Robotics and Automation (ICRA)}, month = may, publisher = {IEEE}, title = {Learning to Retrieve Relevant Experiences for Motion Planning}, year = {2022} }
@inproceedings{kingston2021experience-foliations, abstract = {Many robotic manipulation problems are multi-modal—they consist of a discrete set of mode families (e.g., whether an object is grasped or placed) each with a continuum of parameters (e.g., where exactly an object is grasped). Core to these problems is solving single-mode motion plans, i.e., given a mode from a mode family (e.g., a specific grasp), find a feasible motion to transition to the next desired mode. Many planners for such problems have been proposed, but complex manipulation plans may require prohibitively long computation times due to the difficulty of solving these underlying single-mode problems. It has been shown that using experience from similar planning queries can significantly improve the efficiency of motion planning. However, even though modes from the same family are similar, they impose different constraints on the planning problem, and thus experience gained in one mode cannot be directly applied to another. We present a new experience-based framework, ALEF , for such multi-modal planning problems. ALEF learns using paths from single-mode problems from a mode family, and applies this experience to novel modes from the same family. We evaluate ALEF on a variety of challenging problems and show a significant improvement in the efficiency of sampling-based planners both in isolation and within a multi-modal manipulation planner.}, author = {Kingston, Zachary and Chamzas, Constantinos and Kavraki, Lydia E.}, booktitle = {{IEEE/RSJ} International Conference on Intelligent Robots and Systems}, month = sep, title = {Using Experience to Improve Constrained Planning on Foliations for Multi-Modal Problems}, year = {2021}, keywords = {fundamentals of sampling-based motion planning} }
@inproceedings{chamzas2021-learn-sampling, abstract = {Earlier work has shown that reusing experience from prior motion planning problems can improve the efficiency of similar, future motion planning queries. However, for robots with many degrees-of-freedom, these methods exhibit poor generalization across different environments and often require large datasets that are impractical to gather. We present SPARK and FLAME, two experience-based frameworks for sampling-based planning applicable to complex manipulators in 3D environments. Both combine samplers associated with features from a workspace decomposition into a global biased sampling distribution. SPARK decomposes the environment based on exact geometry while FLAME is more general, and uses an octree-based decomposition obtained from sensor data. We demonstrate the effectiveness of SPARK and FLAME on a real and simulated Fetch robot tasked with challenging pick-and-place manipulation problems. Our approaches can be trained incrementally and significantly improve performance with only a handful of examples, generalizing better over diverse tasks and environments as compared to prior approaches.}, author = {Chamzas, Constantinos and Kingston, Zachary and Quintero-Pe{\~n}a, Carlos and Shrivastava, Anshumali and Kavraki, Lydia E.}, booktitle = {Proceedings of the {IEEE} International Conference on Robotics and Automation}, month = jun, title = {{Learning Sampling Distributions Using Local 3D Workspace Decompositions for Motion Planning in High Dimensions}}, year = {2021}, keywords = {fundamentals of sampling-based motion planning}, note = {(Top-4 finalist for best paper in Cognitive Robotics)}, pages = {1283-1289}, url = {https://dx.doi.org/10.1109/ICRA48506.2021.9561104}, doi = {10.1109/ICRA48506.2021.9561104} }
@inproceedings{kingston2020weighting-multi-modal-leads, abstract = {Robotic manipulation problems are inherently continuous, but typically have underlying discrete structure, e.g., whether or not an object is grasped. This means many problems are multi-modal and in particular have a continuous infinity of modes. For example, in a pick-and-place manipulation domain, every grasp and placement of an object is a mode. Usually manipulation problems require the robot to transition into different modes, e.g., going from a mode with an object placed to another mode with the object grasped. To successfully find a manipulation plan, a planner must find a sequence of valid single-mode motions as well as valid transitions between these modes. Many manipulation planners have been proposed to solve tasks with multi-modal structure. However, these methods require mode-specific planners and fail to scale to very cluttered environments or to tasks that require long sequences of transitions. This paper presents a general layered planning approach to multi-modal planning that uses a discrete "lead" to bias search towards useful mode transitions. The difficulty of achieving specific mode transitions is captured online and used to bias search towards more promising sequences of modes. We demonstrate our planner on complex scenes and show that significant performance improvements are tied to both our discrete "lead" and our continuous representation.}, author = {Kingston, Zachary and Wells, Andrew M. and Moll, Mark and Kavraki, Lydia E.}, booktitle = {{IEEE} International Conference on Robotics and Automation}, title = {Informing Multi-Modal Planning with Synergistic Discrete Leads}, year = {2020}, keywords = {fundamentals of sampling-based motion planning}, pages = {3199-3205}, doi = {10.1109/ICRA40945.2020.9197545} }
@inproceedings{chamzas2019using-local-experiences-for-global-motion-planning, abstract = {Sampling-based planners are effective in many real-world applications such as robotics manipulation, navigation, and even protein modeling.However, it is often challenging to generate a collision-free path in environments where key areas are hard to sample. In the absence of any prior information, sampling-based planners are forced to explore uniformly or heuristically, which can lead to degraded performance. One way to improve performance is to use prior knowledge of environments to adapt the sampling strategy to the problem at hand. In this work, we decompose the workspace into local primitives, memorizing local experiences by these primitives in the form of local samplers, and store them in a database. We synthesize an efficient global sampler by retrieving local experiences relevant to the given situation. Our method transfers knowledge effectively between diverse environments that share local primitives and speeds up the performance dramatically. Our results show, in terms of solution time, an improvement of multiple orders of magnitude in two traditionally challenging high-dimensional problems compared to state-of-the-art approaches.}, author = {Chamzas, Constantinos and Shrivastava, Anshumali and Kavraki, Lydia E.}, booktitle = {Proceedings of the {IEEE} International Conference on Robotics and Automation}, month = may, title = {Using Local Experiences for Global Motion Planning}, year = {2019}, keywords = {fundamentals of sampling-based motion planning}, pages = {8606--8612}, doi = {10.1109/ICRA.2019.8794317} }
@article{kingston2019exploring-implicit-spaces-for-constrained, author = {Kingston, Zachary and Moll, Mark and Kavraki, Lydia E.}, journal = {International Journal of Robotics Research}, title = {Exploring Implicit Spaces for Constrained Sampling-Based Planning}, volume = {38}, number = {10-11}, pages = {1151-1178}, year = {2019}, abstract = {We present a review and reformulation of manifold constrained sampling-based motion planning within a unifying framework, IMACS (Implicit MAnifold Configuration Space). IMACS enables a broad class of motion planners to plan in the presence of manifold constraints, decoupling the choice of motion planning algorithm and method for constraint adherence into orthogonal choices. We show that implicit configuration spaces defined by constraints can be presented to sampling-based planners by addressing two key fundamental primitives: sampling and local planning, and that IMACS preserves theoretical properties of probabilistic completeness and asymptotic optimality through these primitives. Within IMACS, we implement projection- and continutation-based methods for constraint adherence, and demonstrate the framework on a range of planners with both methods in simulated and realistic scenarios. Our results show that the choice of method for constraint adherence depends on many factors and that novel combinations of planners and methods of constraint adherence can be more effective than previous approaches. Our implementation of IMACS is open source within the Open Motion Planning Library and is easily extended for novel planners and constraint spaces.}, keywords = {fundamentals of sampling-based motion planning}, doi = {10.1177/0278364919868530} }
@article{kingston2018sampling-based-methods-for-motion-planning, abstract = {Robots with many degrees of freedom (e.g., humanoid robots and mobile manipulators) have increasingly been employed to accomplish realistic tasks in domains such as disaster relief, spacecraft logistics, and home caretaking. Finding feasible motions for these robots autonomously is essential for their operation. Sampling-based motion planning algorithms have been shown to be effective for these high-dimensional systems. However, incorporating task constraints (e.g., keeping a cup level, writing on a board) into the planning process introduces significant challenges. is survey describes the families of methods for sampling-based planning with constraints and places them on a spectrum delineated by their complexity. Constrained sampling-based methods are based upon two core primitive operations: (1) sampling constraint-satisfying configurations and (2) generating constraint-satisfying continuous motion. Although the basics of sampling-based planning are presented for contextual background, the survey focuses on the representation of constraints and sampling- based planners that incorporate constraints.}, author = {Kingston, Zachary K. and Moll, Mark and Kavraki, Lydia E.}, journal = {Annual Review of Control, Robotics, and Autonomous Systems}, title = {Sampling-Based Methods for Motion Planning with Constraints}, year = {2018}, month = may, volume = {1}, pages = {159--185}, keywords = {fundamentals of sampling-based motion planning}, doi = {10.1146/annurev-control-060117-105226} }
@inproceedings{kingston2017decoupling-constraints, abstract = {We present a general unifying framework for sampling-based motion planning under kinematic task constraints which enables a broad class of planners to compute plans that satisfy a given constraint function that encodes, e.g., loop closure, balance, and end-effector constraints. The framework decouples a planner’s method for exploration from constraint satisfaction by representing the implicit configuration space defined by a constraint function. We emulate three constraint satisfaction methodologies from the literature, and demonstrate the framework with a range of planners utilizing these constraint methodologies. Our results show that the appropriate choice of constrained satisfaction methodology depends on many factors, e.g., the dimension of the configuration space and implicit constraint manifold, and number of obstacles. Furthermore, we show that novel combinations of planners and constraint satisfaction methodologies can be more effective than previous approaches. The framework is also easily extended for novel planners and constraint spaces.}, address = {Puerto Varas, Chile}, author = {Kingston, Zachary and Moll, Mark and Kavraki, Lydia E.}, keywords = {fundamentals of sampling-based motion planning}, booktitle = {Proceedings of the International Symposium of Robotics Research}, title = {Decoupling Constraints from Sampling-Based Planners}, year = {2017} }
@incollection{halperin2016robotics, title = {Robotics}, booktitle = {Handbook of Discrete and Computational Geometry}, year = {2017}, publisher = {CRC Press}, address = {Boca Raton, NY}, keywords = {fundamentals of sampling-based motion planning}, url = {http://www.csun.edu/%7Ectoth/Handbook/HDCG3.html}, author = {Halperin, D. and Kavraki, Lydia E and Solovey, Kiril}, editor = {Goodman, Jacob E. and O'Rourke, Joseph and T\'oth, Csaba D.} }
@inproceedings{pokorny2016warrt, author = {Pokorny, Florian T. and Kragic, Danica and Kavraki, Lydia E. and Goldberg, Ken}, title = {High-Dimensional Winding-Augmented Motion Planning with 2D Topological Task Projections and Persistent Homology}, year = {2016}, pages = {24--31}, booktitle = {Proceedings of the IEEE International Conference on Robotics and Automation}, doi = {10.1109/ICRA.2016.7487113}, abstract = {Recent progress in motion planning has made it possible to determine homotopy inequivalent trajectories between an initial and terminal configuration in a robot configuration space. Current approaches have however either assumed the knowledge of differential one-forms related to a skeletonization of the collision space, or have relied on a simplicial representation of the free space. Both of these approaches are currently however not yet practical for higher dimensional configuration spaces. We propose 2D topological task projections (TTPs): mappings from the configuration space to 2-dimensional spaces where simplicial complex filtrations and persistent homology can identify topological properties of the high-dimensional free configuration space. Our approach only requires the availability of collision free samples to identify winding centers that can be used to determine homotopy inequivalent trajectories. We propose the Winding Augmented RRT and RRT* (WA-RRT/RRT*) algorithms using which homotopy inequivalent trajectories can be found. We evaluate our approach in experiments with configuration spaces of planar linkages with 2-10 degrees of freedom. Results indicate that our approach can reliably identify suitable topological task projections and our proposed WA-RRT and WA-RRT* algorithms were able to identify a collection of homotopy inequivalent trajectories in each considered configuration space dimension.}, keywords = {fundamentals of sampling-based motion planning} }
@incollection{kavraki-lavalle2016motion-planning, title = {Motion Planning}, booktitle = {Handbook of Robotics, 2nd Edition}, year = {2016}, publisher = {Springer}, keywords = {fundamentals of sampling-based motion planning}, doi = {10.1007/978-3-319-32552-1_7}, author = {Kavraki, Lydia E and LaValle, Steven M.}, abstract = {This chapter first provides a formulation of the geometric path planning problem in Sect. 7.2 and then introduces sampling-based planning in Sect. 7.3. Sampling-based planners are general techniques applicable to a wide set of problems and have been successful in dealing with hard planning instances. For specific, often simpler, planning instances, alternative approaches exist and are presented in Sect. 7.4. These approaches provide theoretical guarantees and for simple planning instances they outperform samplingbased planners. Section 7.5 considers problems that involve differential constraints, while Sect. 7.6 overviews several other extensions of the basic problem formulation and proposed solutions. Finally, Sect. 7.8 addresses some important andmore advanced topics related to motion planning.}, note = {(\url{http://www.bookmetrix.com/detail_full/book/bf39ef83-36b6-4bac-b546-a86864c58e19#downloads})} }
@article{moll-sucan2015benchmarking-motion-planning, title = {Benchmarking Motion Planning Algorithms: An Extensible Infrastructure for Analysis and Visualization}, journal = {IEEE Robotics \& Automation Magazine (Special Issue on Replicable and Measurable Robotics Research)}, volume = {22}, number = {3}, year = {2015}, pages = {96--102}, abstract = {Sampling-based planning algorithms are widely used on many robot platforms. Within this class of algorithms, many variants have been proposed over the last 20 years, yet there is still no characterization of which algorithms are well-suited for which classes of problems. This has motivated us to develop a benchmarking infrastructure for motion planning algorithms. It consists of three main components. First, we have created an extensive benchmarking software framework that is included with the Open Motion Planning Library (OMPL), a C++ library that contains implementations of many sampling-based algorithms. Second, we have defined extensible formats for storing benchmark results. The formats are fairly straightforward so that other planning libraries could easily produce compatible output. Finally, we have created an interactive, versatile visualization tool for compact presentation of collected benchmark data. The tool and underlying database facilitate the analysis of performance across benchmark problems and planners.}, keywords = {fundamentals of sampling-based motion planning}, doi = {10.1109/MRA.2015.2448276}, author = {Moll, Mark and {\c S}ucan, Ioan A. and Kavraki, Lydia E} }
@inproceedings{luna-sucan2013anytime-solution-optimization, title = {Anytime Solution Optimization for Sampling-Based Motion Planning}, booktitle = {Proceedings of the IEEE International Conference on Robotics and Automation}, year = {2013}, month = may, pages = {5053-5059}, address = {Karlsruhe, Germany}, abstract = {Recent work in sampling-based motion planning has yielded several different approaches for computing good quality paths in high degree of freedom systems: path shortcutting methods that attempt to shorten a single solution path by connecting non-consecutive configurations, a path hybridization technique that combines portions of two or more solutions to form a shorter path, and asymptotically optimal algorithms that converge to the shortest path over time. This paper presents an extensible meta-algorithm that incorporates a traditional sampling-based planning algorithm with offline path shorten- ing techniques to form an anytime algorithm which exhibits competitive solution lengths to the best known methods and optimizers. A series of experiments involving rigid motion and complex manipulation are performed as well as a comparison with asymptotically optimal methods which show the efficacy of the proposed scheme, particularly in high-dimensional spaces.}, keywords = {fundamentals of sampling-based motion planning}, doi = {10.1109/ICRA.2013.6631301}, author = {Luna, Ryan and {\c S}ucan, Ioan A. and Moll, Mark and Kavraki, Lydia E} }
@inproceedings{gipson-moll2013resolution-independent-density, title = {Resolution Independent Density Estimation for Motion Planning in High-Dimensional Spaces}, booktitle = {IEEE International Conference on Robotics and Automation}, year = {2013}, pages = {2429--2435}, abstract = {This paper presents a new motion planner, Search Tree with Resolution Independent Density Estimation (STRIDE), designed for rapid exploration and path planning in high-dimensional systems (greater than 10). A Geometric Near- neighbor Access Tree (GNAT) is maintained to estimate the sampling density of the configuration space, allowing an implicit, resolution-independent, Voronoi partitioning to provide sampling density estimates, naturally guiding the planner towards unexplored regions of the configuration space. This planner is capable of rapid exploration in the full dimension of the configuration space and, given that a GNAT requires only a valid distance metric, STRIDE is largely parameter-free. Extensive experimental results demonstrate significant dimension- dependent performance improvements over alternative state-of-the-art planners. In particular, high-dimensional systems where the free space is mostly defined by narrow passages were found to yield the greatest performance improvements. Experimental results are shown for both a classical 6-dimensional problem and those for which the dimension incrementally varies from 3 to 27.}, keywords = {fundamentals of sampling-based motion planning}, doi = {10.1109/ICRA.2013.6630908}, author = {Gipson, B and Moll, Mark and Kavraki, Lydia E} }
@article{sucan-moll2012open-motion-planning, title = {The Open Motion Planning Library}, journal = {IEEE Robotics \& Automation Magazine}, volume = {19}, year = {2012}, note = {http://ompl.kavrakilab.org}, month = dec, pages = {72-82}, abstract = {We describe the Open Motion Planning Library (OMPL), a new library for sampling-based motion planning, which contains implementations of many state-of-the-art planning algorithms. The library is designed in a way that allows the user to easily solve a variety of complex motion planning problems with minimal input. OMPL facilitates the addition of new motion planning algorithms and it can be conveniently interfaced with other software components. A simple graphical user interface (GUI) built on top of the library, a number of tutorials, demos and programming assignments have been designed to teach students about sampling-based motion planning. Finally, the library is also available for use through the Robot Operating System (ROS).}, keywords = {fundamentals of sampling-based motion planning, other robotics}, doi = {10.1109/MRA.2012.2205651}, author = {{\c S}ucan, Ioan A. and Moll, Mark and Kavraki, Lydia E} }
@article{sucan-kavraki2012sampling-based-tree-planner, title = {A Sampling-Based Tree Planner for Systems With Complex Dynamics}, journal = {IEEE Transactions on Robotics}, volume = {28}, number = {1}, year = {2012}, pages = {116-131}, abstract = {This paper presents a kinodynamic motion planner, Kinodynamic Motion Planning by Interior-Exterior Cell Exploration (KPIECE), specifically designed for systems with complex dynamics, where integration backward in time is not possible and speed of computation is important. A grid-based discretization is used to estimate the coverage of the state space. The coverage estimates help the planner detect the less explored areas of the state space. An important characteristic of this discretization is that it keeps track of the boundary of the explored region of the state space and focuses exploration on the less covered parts of this boundary. Extensive experiments show that KPIECE provides significant computational gain over existing state-of-the-art methods and allows solving some harder, previously unsolvable problems. For some problems KPIECE is shown to be up to two orders of magnitude faster than existing methods and use up to forty times less memory. A shared memory parallel implementation is presented as well. This implementation provides better speedup than an embarrassingly parallel implementation by taking advantage of the evolving multi-core technology.}, keywords = {fundamentals of sampling-based motion planning}, issn = {1552-3098}, doi = {10.1109/TRO.2011.2160466}, author = {Sucan, Ioan Alexandru and Kavraki, Lydia E} }
@inproceedings{sucan-kavraki2010on-implementation-of, title = {On the Implementation of Single-Query Sampling-Based Motion Planners}, booktitle = {IEEE International Conference on Robotics and Automation}, year = {2010}, pages = {2005-2011}, address = {Anchorage, Alaska}, keywords = {fundamentals of sampling-based motion planning}, doi = {10.1109/ROBOT.2010.5509172}, author = {Sucan, Ioan Alexandru and Kavraki, Lydia E} }
@inproceedings{sucan-kavraki2009on-performance-of, title = {On the Performance of Random Linear Projections for Sampling-Based Motion Planning}, booktitle = {IEEE/RSJ International Conference on Intelligent Robots and Systems}, year = {2009}, month = oct, pages = {2434-2439}, address = {St. Louis}, keywords = {fundamentals of sampling-based motion planning}, doi = {10.1109/IROS.2009.5354403}, author = {Sucan, Ioan Alexandru and Kavraki, Lydia E} }
@incollection{tsianos-halperin2008robot-algorithms, title = {Robot Algorithms}, booktitle = {Algorithms and Theory of Computation Handbook}, volume = {2}, year = {2008}, publisher = {CRC Press}, edition = {Second}, chapter = {4}, address = {Boca Raton, FL}, keywords = {fundamentals of sampling-based motion planning, other robotics}, author = {Tsianos, Konstantinos I. and Halperin, D. and Kavraki, Lydia E and Latombe, Jean-Claude} }
@article{tsianos-sucan2007sampling-based-robot-motion, title = {Sampling-based robot motion planning: Towards realistic applications}, journal = {Computer Science Review}, volume = {1}, year = {2007}, month = aug, pages = {2--11}, abstract = {This paper presents some of the recent improvements in sampling-based robot motion planning. Emphasis is placed on work that brings motion-planning algorithms closer to applicability in real environments. Methods that approach increasingly difficult motion planning problems including kinodynamic motion planning and dynamic environments are discussed. The ultimate goal for such methods is to generate plans that can be executed with few modifications in a real robotics mobile platform.}, keywords = {fundamentals of sampling-based motion planning}, doi = {10.1016/j.cosrev.2007.08.002}, author = {Tsianos, Konstantinos I. and Sucan, Ioan Alexandru and Kavraki, Lydia E} }
@inproceedings{plaku-kavraki2007nonlinear-dimensionality-reduction, title = {Nonlinear Dimensionality Reduction Using Approximate Nearest Neighbors}, booktitle = {SIAM International Conference on Data Mining (SDM)}, year = {2007}, pages = {3711-3716}, address = {Minneapolis, Minnesota}, abstract = {Nonlinear dimensionality reduction methods often rely on the nearest-neighbors graph to extract low-dimensional embeddings that reliably capture the underlying structure of high-dimensional data. Research however has shown that computing nearest neighbors of a point from a high-dimensional data set generally requires time proportional to the size of the data set itself, rendering the computation of the nearest-neighbors graph prohibitively expensive. This work significantly reduces the major computational bottleneck of many nonlinear dimensionality reduction methods by efficiently and accurately approximating the nearest-neighbors graph. The approximation relies on a distance-based projection of high-dimensional data onto low-dimensional Euclidean spaces. As indicated by experimental results, the advantage of the proposed approximation is that while it reliably maintains the accuracy of nonlinear dimensionality reduction methods, it significantly reduces the computational time.}, keywords = {fundamentals of sampling-based motion planning}, url = {http://www.siam.org/proceedings/datamining/2007/dm07_preface.php}, author = {Plaku, E. and Kavraki, Lydia E} }
@article{moll-kavraki2006path-planning-for, title = {Path Planning for Deformable Linear Objects}, journal = {IEEE Transactions on Robotics}, volume = {22}, number = {4}, year = {2006}, month = aug, pages = {625-636}, abstract = {We present a new approach to path planning for deformable linear (one-dimensional) objects such as flexible wires. We introduce a method for efficiently computing stable configurations of a wire subject to manipulation constraints. These configurations correspond to minimal-energy curves. By restricting the planner to minimal-energy curves, the execution of a path becomes easier. Our curve representation is adaptive in the sense that the number of parameters automatically varies with the complexity of the underlying curve. We introduce a planner that computes paths from one minimal-energy curve to another such that all intermediate curves are also minimal-energy curves. This planner can be used as a powerful local planner in a sampling-based roadmap method. This makes it possible to compute a roadmap of the entire {\textquotedblleft}shape space,{\textquotedblright} which is not possible with previous approaches. Using a simplified model for obstacles, we can find minimal-energy curves of fixed length that pass through specified tangents at given control points. Our work has applications in cable routing, and motion planning for surgical suturing and snake-like robots.}, keywords = {fundamentals of sampling-based motion planning, other robotics}, doi = {10.1109/TRO.2006.878933}, author = {Moll, Mark and Kavraki, Lydia E} }
@incollection{bekris-argyros2006exploiting-panoramic-vision, title = {Exploiting Panoramic Vision for Angle-Based Robot Navigation}, booktitle = {Lecture Notes in Computer Science, Vol. 33}, year = {2006}, pages = {229-251}, publisher = {Springer}, abstract = {Omni-directional vision allows for the development of techniques for mobile robot navigation that have minimum perceptual requirements. In this work, we focus on robot navigation algorithms that do not require range information or metric maps of the environment. More specifically, we present a homing strategy that enables a robot to return to its home position after executing a long path. The proposed strategy relies on measuring the angle between pairs of features extracted from panoramic images, which can be achieved accurately and robustly. In the heart of the proposed homing strategy lies a novel, local control law that enables a robot to reach any position on the plane by exploiting the bearings of at least three landmarks of unknown position, without making assumptions regarding the robot{\textquoteright}s orientation and without making use of a compass. This control law is the result of the unification of two other local control laws which guide the robot by monitoring the bearing of landmarks and which are able to reach complementary sets of goal positions on the plane. Long-range homing is then realized through the systematic application of the unified control law between automatically extracted milestone positions connecting the robot{\textquoteright}s current position to the home position. Experimental results, conducted both in a simulated environment and on a robotic platform equipped with a panoramic camera validate the employed local control laws as well as the overall homing strategy. Moreover, they show that panoramic vision can assist in simplifying the perceptual processes required to support robust and accurate homing behaviors.}, keywords = {fundamentals of sampling-based motion planning, other robotics}, author = {Bekris, Kostas E. and Argyros, A. A. and Kavraki, Lydia E} }
@inproceedings{plaku-kavraki2006quantitative-analysis-of, title = {Quantitative Analysis of Nearest Neighbors Search in High-Dimensional Sampling-based Motion Planning}, booktitle = {Workshop on Algorithmic Foundations of Robotics (WAFR)}, year = {2006}, address = {New York, NY}, abstract = {We quantitatively analyze the performance of exact and approximate nearest-neighbors algorithms on increasingly high-dimensional problems in the context of sampling-based motion planning. We study the impact of the dimension, number of samples, distance metrics, and sampling schemes on the efficiency and accuracy of nearest-neighbors algorithms. Efficiency measures computation time and accuracy indicates similarity between exact and approximate nearest neighbors. Our analysis indicates that after a critical dimension, which varies between 15 and 30, exact nearest-neighbors algorithms examine almost all the samples. As a result, exact nearest-neighbors algorithms become impractical for sampling-based motion planners when a considerably large number of samples needs to be generated. The impracticality of exact nearest-neighbors algorithms motivates the use of approximate algorithms, which trade off accuracy for efficiency. We propose a simple algorithm, termed Distance-based Projection onto Euclidean Space (DPES), which computes approximate nearest neighbors by using a distance-based projection of high-dimensional metric spaces onto low-dimensional Euclidean spaces. Our results indicate DPES achieves high efficiency and only a negligible loss in accuracy.}, keywords = {fundamentals of sampling-based motion planning}, author = {Plaku, E. and Kavraki, Lydia E} }
@book{choset-burgard2005principles-of-robot, title = {Principles of Robot Motion: Theory, Algorithms, and Implementation}, year = {2005}, month = jun, publisher = {MIT Press}, abstract = {Robot motion planning has become a major focus of robotics. Research findings can be applied not only to robotics but to planning routes on circuit boards, directing digital actors in computer graphics, robot-assisted surgery and medicine, and in novel areas such as drug design and protein folding. This text reflects the great advances that have taken place in the last ten years, including sensor-based planning, probabalistic planning, localization and mapping, and motion planning for dynamic and nonholonomic systems. Its presentation makes the mathematical underpinnings of robot motion accessible to students of computer science and engineering, rleating low-level implementation details to high-level algorithmic concepts.}, keywords = {fundamentals of sampling-based motion planning}, author = {Choset, H. and Burgard, W. and Hutchinson, S. and Kantor, G. and Kavraki, Lydia E and Lynch, K. and Thrun, S.}, isbn = {978-0262033275} }
@inproceedings{plaku-kavraki2005distributed-sampling-based-roadmap, title = {Distributed Sampling-Based Roadmap of Trees for Large-Scale Motion Planning}, booktitle = {IEEE International Conference on Robotics and Automation}, year = {2005}, month = apr, pages = {3879-3884}, address = {Barcelona, Spain}, abstract = {High-dimensional problems arising from complex robotic systems test the limits of current motion planners and require the development of efficient distributed motion planners that take full advantage of all the available resources. This paper shows how to effectively distribute the computation of the Sampling-based Roadmap of Trees (SRT) algorithm using a decentralized master-client scheme. The distributed SRT algorithm allows us to solve very high-dimensional problems that cannot be efficiently addressed with existing planners. Our experiments show nearly linear speedups with eighty processors and indicate that similar speedups can be obtained with several hundred processors.}, keywords = {fundamentals of sampling-based motion planning}, doi = {10.1109/ROBOT.2005.1570711}, author = {Plaku, E. and Kavraki, Lydia E} }
@incollection{ladd-kavraki2005fast-tree-based-exploration, title = {Fast Tree-Based Exploration of State Space for Robots with Dynamics}, booktitle = {Algorithmic Foundations of Robotics VI}, year = {2005}, pages = {297-312}, publisher = {Springer, STAR 17}, abstract = {This paper presents a new motion planning algorithm which we call the Path-Directed Subdivision Tree exploration Planner PDST-EXPLORE. It is a sampling-based method which builds a tree and takes a substantially different approach from other exploration planners such as RRT [18] and EST [12]. PDST-EXPLORE is a general purpose planner but is designed to overcome difficulties inherent in planning for robots with non-trivial dynamics. Specifically, our planner represents samples as path segments rather than individual states and uses non-uniform subdivisions of the state space to estimate coverage. This change avoids many of the problems that previous sampling-based planners have had with milestone placement, metrics and coverage estimation. We use a deterministic update schedule together with randomized path generation to adaptively strike a balance between greedy exploration and methodical search. We have obtained a proof of probabilistic completeness for the planner which assumes very little about the specific robot system that the planner operates on. Finally, we have implemented the planner for planar kinodynamic point robots, differential drive robots and blimp-like robots. The experimental results demonstrate the efficiency of the planner{\textquoteright}s implementation as well as its robustness in covering the entire reachable free space.}, keywords = {fundamentals of sampling-based motion planning, kinodynamic systems}, doi = {10.1007/10991541_21}, author = {Ladd, A. M. and Kavraki, Lydia E} }
@incollection{akinc-bekris2005probabilistic-roadmaps-of, title = {Probabilistic Roadmaps of Trees for Parallel Computation of Multiple Query Roadmaps}, booktitle = {Robotic Research: The Eleventh International Symposium}, year = {2005}, pages = {80-89}, publisher = {Springer, STAR 15}, abstract = { We propose the combination of techniques that solve multiple queries for motion planning problems with single query planners in a motion planning framework that can be efficiently parallelized. In multiple query motion planning, a data structure is built during a preprocessing phase in order to quickly respond to on-line queries. Alternatively, in single query planning, there is no preprocessing phase and all computations occur during query resolution. This paper shows how to effectively combine a powerful sample-based method primarily designed for multiple query planning (the Probabilistic Roadmap Method - PRM) with sample-based tree methods that were primarily designed for single query planning (such as Expansive Space Trees, Rapidly Exploring Random Trees, and others). Our planner, which we call the Probabilistic Roadmap of Trees (PRT), uses a tree algorithm as a subroutine for PRM. The nodes of the PRM roadmap are now trees. We take advantage of the very powerful sampling schemes of recent tree planners to populate our roadmaps. The combined sampling scheme is in the spirit of the non-uniform sampling and refinement techniques employed in earlier work on PRM. PRT not only achieves a smooth spectrum between multiple query and single query planning but it combines advantages of both. We present experiments which show that PRT is capable of solving problems that cannot be addressed efficiently with PRM or single-query planners. A key advantage of PRT is that it is significantly more decoupled than PRM and sample-based tree planners. Using this property, we designed and implemented a parallel version of PRT. Our experiments show that PRT distributes well and can easily solve high dimensional problems that exhaust resources available to single machines.}, keywords = {fundamentals of sampling-based motion planning}, doi = {10.1007/11008941_9}, author = {Akinc, M. and Bekris, Kostas E. and Chen, B. Y. and Ladd, A. M. and Plaku, E. and Kavraki, Lydia E} }
@article{plaku-bekris2005sampling-based-roadmap-of, title = {Sampling-Based Roadmap of Trees for Parallel Motion Planning}, journal = {IEEE Transactions on Robotics}, volume = {21}, number = {4}, year = {2005}, pages = {597-608}, abstract = {This paper shows how to effectively combine a sampling-based method primarily designed for multiple-query motion planning [probabilistic roadmap method (PRM)] with sampling-based tree methods primarily designed for single-query motion planning (expansive space trees, rapidly exploring random trees, and others) in a novel planning framework that can be efficiently parallelized. Our planner not only achieves a smooth spectrum between multiple-query and single-query planning, but it combines advantages of both. We present experiments which show that our planner is capable of solving problems that cannot be addressed efficiently with PRM or single-query planners. A key advantage of our planner is that it is significantly more decoupled than PRM and sampling-based tree planners. Exploiting this property, we designed and implemented a parallel version of our planner. Our experiments show that our planner distributes well and can easily solve high-dimensional problems that exhaust resources available to single machines and cannot be addressed with existing planners.}, keywords = {fundamentals of sampling-based motion planning}, doi = {10.1109/TRO.2005.847599}, author = {Plaku, E. and Bekris, Kostas E. and Chen, B. Y. and Ladd, A. M. and Kavraki, Lydia E} }
@article{ladd-kavraki2004measure-theoretic-analysis, title = {Measure Theoretic Analysis of Probabilistic Path Planning}, journal = {IEEE Transactions on Robotics and Automation}, volume = {20}, number = {2}, year = {2004}, month = apr, pages = {229-242}, abstract = {This paper presents a novel analysis of the probabilistic roadmap method (PRM) for path planning. We formulate the problem in terms of computing the transitive closure of a relation over a probability space, and give a bound on the expected number iterations of PRM required to find a path, in terms of the number of intermediate points and the probability of choosing a point from a certain set. Explicit geometric assumptions are not necessary to complete this analysis. As a result, the analysis provides some unification of previous work. We provide an upper bound which could be refined using details specific to a given problem. This bound is of the same form as that proved in previous analyses, but has simpler prerequisites and is proved on a more general class of problems. Using our framework, we analyze some new path-planning problems, 2k-degree-of-freedom kinodynamic point robots, polygonal robots with contact, and deformable robots with force field control. These examples make explicit use of generality in our approach that did not exist in previous frameworks.}, keywords = {fundamentals of sampling-based motion planning}, doi = {10.1109/TRA.2004.824649}, author = {Ladd, A. M. and Kavraki, Lydia E} }
@incollection{halperin-kavraki2004robotics, title = {Robotics}, booktitle = {Handbook of Discrete and Computational Geometry}, year = {2004}, pages = {1065-1094}, publisher = {CRC Press}, address = {Boca Raton, NY}, keywords = {fundamentals of sampling-based motion planning}, author = {Halperin, D. and Kavraki, Lydia E and Latombe, Jean-Claude} }
@inproceedings{bekris-chen2003multiple-query-probabilistic, title = {Multiple Query Probabilistic Roadmap Planning Using Single Query Planning Primitives}, booktitle = {2003 IEEE/RJS International Conference on Intelligent Robots and Systems (IROS)}, year = {2003}, month = oct, pages = {656-661}, address = {Las Vegas, NV}, abstract = {We propose the combination of techniques that solve multiple queries for motion planning problems with single query planners. Our implementation uses a probabilistic roadmap method PRM with bidirectional rapidly exploring random trees BIRRT as the local planner. With small modifications to the standard algorithms, we obtain a multiple query planner which is significantly faster and more reliable than its component parts. Our method provides a smooth spectrum between the PRM and BIRRT techniques and obtains the advantages of both. We observed that the performance differences are most notable in planning instances with several rigid non-convex robots in a scene with narrow passages. This planner is in the spirit of non-uniform sampling and refinement techniques used in earlier work on PRM.}, keywords = {fundamentals of sampling-based motion planning}, doi = {10.1109/IROS.2003.1250704}, author = {Bekris, Kostas E. and Chen, B. Y. and Ladd, A. M. and Plaku, E. and Kavraki, Lydia E} }
@inproceedings{ladd-kavraki2002generalizing-analysis-of, title = {Generalizing the Analysis of {PRM}}, booktitle = {Proceedings of the 2002 IEEE International Conference on Robotics and Automation (ICRA 2002)}, year = {2002}, month = may, pages = {2120-2125}, publisher = {IEEE Press}, address = {Washington, DC}, abstract = {This paper presents it novel analysis of the probabilistic roadmap method (PRM) for path planning. We formulate the problem in terms of computing the transitive closure of a relation over a probability space and give a bound in terms of the number of intermediate points for some path and the probability of choosing a point from a certain set. Explicit geometric assumptions are not necessary to complete this analysis and consequently it provides some unification of the previous work as well as generalizing new path planning problems, two of which, 2k-DOF kinodynamic point robots and deformable robots with force field control, are presented in this paper.}, keywords = {fundamentals of sampling-based motion planning}, doi = {10.1109/ROBOT.2002.1014853}, author = {Ladd, A. M. and Kavraki, Lydia E} }
@article{agrawal-guibas2002algorithmic-issues-in, title = {Algorithmic Issues in Modeling Motion}, journal = {ACM Computing Surveys}, volume = {34}, number = {4}, year = {2002}, pages = {550-572}, abstract = {This article is a survey of research areas in which motion plays a pivotal role. The aim of the article is to review current approaches to modeling motion together with related data structures and algorithms, and to summarize the challenges that lie ahead in producing a more unified theory of motion representation that would be useful across several disciplines.}, keywords = {fundamentals of sampling-based motion planning}, doi = {10.1145/592642.592647}, author = {Agrawal, P. K. and Guibas, L. J. and Edelsbrunner, H. and Erickson, J. and Isard, M. and Har-Peled, S. and Hershberger, J. and Jensen, Ch. and Kavraki, Lydia E and Koehl, P. and Lin, M. and Manocha, D. and Metaxas, D. and Mirtich, B. and Mount, D. and Muthukrishnan, S.} }
@inproceedings{brock-kavraki2001decomposition-based-motion-planning, title = {Decomposition-Based Motion Planning: A Framework for Real-Time Motion Planning in High-Dimensional Configuration Places}, booktitle = {Proceedings of The 2001 IEEE International Conference on Robotics and Automation (ICRA)}, year = {2001}, month = may, pages = {1469-1475}, publisher = {IEEE Press}, keywords = {fundamentals of sampling-based motion planning}, doi = {10.1109/ROBOT.2001.932817}, author = {Brock, Oliver and Kavraki, Lydia E} }
@incollection{bohlin-kavraki2001randomized-algorithm-for, title = {A Randomized Algorithm for Robot Path Planning Based on Lazy Evaluation}, booktitle = {Handbook on Randomized Computing}, year = {2001}, pages = {221-249}, publisher = {Kluwer Academic Publishers}, keywords = {fundamentals of sampling-based motion planning}, author = {Bohlin, R. and Kavraki, Lydia E} }
@article{yakey-lavalle2001randomized-path-planning, title = {Randomized Path Planning for Linkages with Closed Kinematics Chains}, journal = {IEEE Transactions on Robotics and Automation}, volume = {17}, number = {6}, year = {2001}, pages = {951-959}, abstract = {We extend randomized path planning algorithms to the case of articulated robots that have closed kinematic chains. This is an important class of problems, which includes applications such as manipulation planning using multiple open-chain manipulators that cooperatively grasp an object and planning for reconfigurable robots in which links might be arranged in a loop to ease manipulation or locomotion. Applications also exist in areas beyond robotics, including computer graphics, computational chemistry, and virtual prototyping. Such applications typically involve high degrees of freedom and a parameterization of the configurations that satisfy closure constraints is usually not available. We show how to implement key primitive operations of randomized path planners for general closed kinematics chains. These primitives include the generation of random free configurations and the generation of local paths. To demonstrate the feasibility of our primitives for general chains, we show their application to recently developed randomized planners and present computed results for high-dimensional problems.}, keywords = {fundamentals of sampling-based motion planning}, doi = {10.1109/70.976030}, author = {Yakey, J. and LaValle, Steven M. and Kavraki, Lydia E} }
@inproceedings{nielsen-kavraki2000two-level-fuzzy-prm, title = {A Two-Level Fuzzy {PRM} for Manipulation Planning}, booktitle = {Proceedings of The IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS)}, volume = {3}, year = {2000}, month = nov, pages = {1716-1722}, publisher = {IEEE Press}, abstract = {This paper presents an algorithm which extends the probabilistic roadmap (PRM) framework to handle manipulation planning. This is done by using a two level approach, a PRM of PRMs. The first level builds a manipulation graph, whose nodes represent stable placements of the manipulated objects while the edges represent transfer and transit actions. The actual motion planning for the transfer and transit paths is done by PRM planners at the second level. The approach is made possible by the introduction of a new kind of roadmap, called the fuzzy roadmap. The fuzzy roadmap contains edges which are not verified by a local planner during construction. Instead, each edge is assigned a number which represents the probability that it is feasible. Later, if the edge is part of a solution path, the edge is checked for collisions. The overall effect is that our roadmaps evolve iteratively until they contain a solution. The use of fuzzy roadmaps in both levels of our manipulation planner offers many advantages. At the first level, a fuzzy roadmap represents the manipulation graph and addresses the problem of having probabilistically complete planners at the second level. At the second level, fuzzy roadmaps drastically reduce the number of collision checks. The paper contains experimental results demonstrating the feasibility and efficiency of our scheme.}, keywords = {fundamentals of sampling-based motion planning}, doi = {10.1109/IROS.2000.895219}, author = {Nielsen, C. and Kavraki, Lydia E} }
@inproceedings{bohlin-kavraki2000path-planning-using, title = {Path Planning Using Lazy {PRM}}, booktitle = {Proceedings of the IEEE International Conference on Robotics and Automation}, volume = {1}, year = {2000}, month = apr, pages = {521-528}, publisher = {IEEE Press}, address = {San Fransisco, CA}, abstract = {Describes an approach to probabilistic roadmap planners (PRMs). The overall theme of the algorithm, called Lazy PRM, is to minimize the number of collision checks performed during planning and hence minimize the running time of the planner. Our algorithm builds a roadmap in the configuration space, whose nodes are the user-defined initial and goal configurations and a number of randomly generated nodes. Neighboring nodes are connected by edges representing paths between the nodes. In contrast with PRMs, our planner initially assumes that all nodes and edges in the roadmap are collision-free, and searches the roadmap at hand for a shortest path between the initial and the goal node. The nodes and edges along the path are then checked for collision. If a collision with the obstacles occurs, the corresponding nodes and edges are removed from the roadmap. Our planner either finds a new shortest path, or first updates the roadmap with new nodes and edges, and then searches for a shortest path. The above process is repeated until a collision-free path is returned. Lazy PRM is tailored to efficiently answer single planning queries, but can also be used for multiple queries. Experimental results presented in the paper show that our lazy method is very efficient in practice.}, keywords = {fundamentals of sampling-based motion planning}, doi = {10.1109/ROBOT.2000.844107}, author = {Bohlin, R. and Kavraki, Lydia E} }
@inproceedings{danner-kavraki2000randomized-planning-for, title = {Randomized Planning for Short Inspection Paths}, booktitle = {Proceedings of The IEEE International Conference on Robotics and Automation (ICRA)}, volume = {2}, year = {2000}, month = apr, pages = {971-976}, publisher = {IEEE Press}, address = {San Fransisco, CA}, abstract = {Addresses the following inspection problem: given a known workspace and a robot with vision capabilities compute a short path path for the robot such that each point on boundary of the workspace is visible from some point on the path. Autonomous inspection, such as by a flying camera, or a virtual reality architectural walkthrough, could be guided by a solution to the above inspection problem. Visibility constraints on both maximum viewing distance and maximum angle of incidence are considered to better model real sensors. An algorithm is presented for planar workspaces which operates in two steps: selecting art gallery-style guards and connecting them to form an inspection path. Experimental results for this algorithm are discussed. Next, the algorithm is extended to three dimensions and inspection paths are shown.}, keywords = {fundamentals of sampling-based motion planning}, doi = {10.1109/ROBOT.2000.844726}, author = {Danner, T. and Kavraki, Lydia E} }
@inproceedings{holleman-kavraki2000framework-for-using, title = {A Framework for Using the Workspace Medial Axis in {PRM} Planners}, booktitle = {Proc.\ of the International Conference on Robotics and Automation (ICRA)}, volume = {2}, year = {2000}, pages = {1408-1413}, publisher = {IEEE Press}, address = {San Fransisco, CA}, abstract = {Probabilistic roadmap (PRM) planners have been very successful in path planning for a wide variety of problems, especially applications involving robots with many degrees of freedom. These planners randomly sample the configuration space, building up a roadmap that connects the samples. A major problem is finding valid configurations in tight areas, and many methods have been proposed to more effectively sample these regions. By constructing a skeleton-like subset of the free regions of the workspace, these heuristics can be strengthened. The skeleton provides a concise description of the workspace topology and an efficient means of finding points with maximal clearance from the obstacles. We examine the medial axis as a skeleton, including a method to compute an approximation to it. The medial axis is a two-equidistant surface in the workspace. We form a heuristic for finding difficult configurations using the medial axis, and demonstrate its effectiveness in a planner for rigid objects in a 3D workspace.}, keywords = {fundamentals of sampling-based motion planning}, doi = {10.1109/ROBOT.2000.844795}, author = {Holleman, C. and Kavraki, Lydia E} }
@inproceedings{lavalle-yakey1999probabilistic-roadmap-approach, title = {A Probabilistic Roadmap Approach for Systems with Closed Kinematic Chains}, booktitle = {Proceedings of The IEEE International Conference on Robotics and Automation (ICRA)}, volume = {3}, year = {1999}, month = may, pages = {1671-1677}, publisher = {IEEE Press}, address = {Detroit, MI}, abstract = {We present a randomized approach to path planning for articulated robots that have closed kinematic chains. The approach extends the probabilistic roadmap technique which has previously been applied to rigid and elastic objects, and articulated robots without closed chains. It provides a framework for path planning problems that must satisfy closure constraints in addition to standard collision constraints. This expands the power of the probabilistic roadmap technique to include a variety of problems such as manipulation planning using two open-chain manipulators that cooperatively grasp an object, forming a system with a closed chain, and planning for reconfigurable robots where the robot links may be rearranged in a loop to ease manipulation or locomotion. We generate the vertices and edges in our probabilistic roadmap. We focus on the problem of planning the motions for a collection of attached links in a 2D environment with obstacles. The approach has been implemented and successfully demonstrated on several examples.}, keywords = {fundamentals of sampling-based motion planning}, doi = {10.1109/ROBOT.1999.770349}, author = {LaValle, Steven M. and Yakey, J. and Kavraki, Lydia E} }
@incollection{kavraki1999algorithms-in-robotics, title = {Algorithms in Robotics: The Motion Planning Perspective}, booktitle = {Frontiers of Engineering Publication}, year = {1999}, pages = {90-93}, publisher = {National Academy of Engineering}, keywords = {fundamentals of sampling-based motion planning}, author = {Kavraki, Lydia E} }
@incollection{hsu-kavraki1999capturing-connectivity-of, title = {Capturing the Connectivity of High-Dimensional Geometric Spaces by Parallelizable Random Sampling Techniques}, booktitle = {Parallel and Distributed Processing}, volume = {5}, year = {1999}, pages = {159-182}, publisher = {Springer, Boston, MA.}, keywords = {fundamentals of sampling-based motion planning}, doi = {10.1007/978-1-4613-3282-4_8}, isbn = {978-1-4613-3284-8}, author = {Hsu, David and Latombe, Jean-Claude and Motwani, R. and Kavraki, Lydia E}, editor = {Pardalos, P.M. and Rajasekaran, S.} }
@inproceedings{guibas-holleman1999probabilistic-roadmap-planner, title = {A Probabilistic Roadmap Planner for Flexible Objects with a Workspace Medial-Axis Based Sampling Approach}, booktitle = {Proceedings of the IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS)}, volume = {1}, year = {1999}, pages = {254-260}, publisher = {IEEE Press}, address = {Kyongju, Korea}, abstract = {Probabilistic roadmap planners have been used with success to plan paths for flexible objects such as metallic plates or plastic flexible pipes. This paper improves the performance of these planners by using the medial axis of the workspace to guide the random sampling. At a preprocessing stage, the medial axis of the workspace is computed using a recent efficient algorithm. Then the flexible object is fitted at random points along the medial axis. The energy of all generated configurations is minimized and the planner proceeds to connect them with low-energy quasi-static paths in a roadmap that captures the connectivity of the free space. Given an initial and a final configuration, the planner connects these to the roadmap and searches the roadmap for a path. Our experimental results show that the new sampling scheme is successful in identifying critical deformations of the object along solution paths which results in a significant reduction of the computation time. Our work on planning for flexible objects has applications in industrial settings, virtual reality environments, and medicine.}, keywords = {fundamentals of sampling-based motion planning}, doi = {10.1109/IROS.1999.813013}, author = {Guibas, L. J. and Holleman, C. and Kavraki, Lydia E} }
@incollection{halperin-kavraki1999robot-algorithms, title = {Robot Algorithms}, booktitle = {Algorithms and Theory of Computation Handbook}, year = {1999}, publisher = {CRC Press}, chapter = {21}, address = {Boca Raton, NY}, keywords = {fundamentals of sampling-based motion planning}, author = {Halperin, D. and Kavraki, Lydia E and Latombe, Jean-Claude and Attalah, M.} }
@article{kavraki-latombe1998randomized-query-processing, title = {Randomized Query Processing in Robot Path Planning}, journal = {Journal of Computer and System Sciences}, volume = {57}, number = {1}, year = {1998}, month = aug, pages = {50-60}, abstract = {The subject of this paper is the analysis of a randomized preprocessing scheme that has been used for query processing in robot path planning. The attractiveness of the scheme stems from its general applicability to virtually any path-planning problem, and its empirically observed success. In this paper we initiate a theoretical basis for explaining this empirical success. Under a simple assumption about the configuration space, we show that it is possible to perform preprocessing following which queries can be answered quickly. En route, we consider related problems on graph connectivity in the evasiveness model and art-gallery theorems.}, keywords = {fundamentals of sampling-based motion planning}, doi = {10.1006/jcss.1998.1578}, author = {Kavraki, Lydia E and Latombe, Jean-Claude and Motwani, R. and Raghavan, P.} }
@article{kavraki-kolountzakis1998analysis-of-probabilistic, title = {Analysis of Probabilistic Roadmaps for Path Planning}, journal = {IEEE Transactions on Robotics and Automation}, volume = {14}, number = {1}, year = {1998}, pages = {166-171}, abstract = {We provide an analysis of a path planning method which uses probabilistic roadmaps. This method has proven very successful in practice, but the theoretical understanding of its performance is still limited. Assuming that a path γ exists between two configurations a and b of the robot, we study the dependence of the failure probability to connect a and b, on: 1) the length of γ; 2) the distance function of γ from the obstacles; 3) the number of nodes N of the probabilistic roadmap constructed. Importantly, our results do not depend strongly on local irregularities of the configuration space, as was the case with previous analysis. These results are illustrated with a simple but illuminating example. In this example, we provide estimates for N, the principal parameter of the method, in order to achieve failure probability within prescribed bounds. We also compare, through this example, the different approaches to the analysis of the planning method.}, keywords = {fundamentals of sampling-based motion planning}, doi = {10.1109/70.660866}, author = {Kavraki, Lydia E and Kolountzakis, M. N. and Latombe, Jean-Claude} }
@incollection{hsu-kavraki1998on-finding-narrow, title = {On Finding Narrow Passages with Probabilistic Roadmap Planners}, booktitle = {Robotics: The algorithmic perspective}, year = {1998}, pages = {141-153}, publisher = {A.K. Peters}, address = {Natick, MA}, keywords = {fundamentals of sampling-based motion planning}, url = {http://portal.acm.org/citation.cfm?id=298960.299001}, author = {Hsu, David and Kavraki, Lydia E and Latombe, Jean-Claude and Motwani, R. and Sorkin, S.} }
@incollection{kavraki-latombe1998probabilistic-roadmaps-for, title = {Probabilistic Roadmaps for Robot Path Planning}, booktitle = {Practical Motion Planning in Robotics: Current Approaches and Future Directions}, year = {1998}, pages = {33-53}, publisher = {John Wiley}, keywords = {fundamentals of sampling-based motion planning}, author = {Kavraki, Lydia E and Latombe, Jean-Claude} }
@book{agrawal-kavraki1998robotics-algorithmic-perspective, title = {Robotics: The Algorithmic Perspective}, year = {1998}, publisher = {AK Peters}, address = {Natick MA}, abstract = {Robotic technology is becoming ubiquitous as sensors, motors, and computers become smaller and cheaper. However, robotic technology depends not only on the physical hardware, but also on the software to perceive, plan, and control. Progress on the algorithmic foundations of robotics is critical. The papers in this volume give a solid overview of the state of the art in robot algorithms. They cover core problems in robotics, such as motion planning, sensor-based planning, manipulation, and assembly planning, and also examine the application of robotics algorithms in other domains, like molecular modeling, geometric modeling, and computer-assisted surgery. The volume includes papers presented at the Third International Workshop on the Algorithmic Foundations of Robotics, held at Rice University in 1998.}, keywords = {fundamentals of sampling-based motion planning}, author = {Agrawal, P. K. and Kavraki, Lydia E and Mason, M.}, isbn = {978-1568810812} }
@article{barraquand-kavraki1997random-sampling-scheme, title = {A Random Sampling Scheme for Robot Path Planning}, journal = {International Journal of Robotics Research}, volume = {16}, number = {6}, year = {1997}, pages = {759-774}, keywords = {fundamentals of sampling-based motion planning}, doi = {10.1177/027836499701600604}, author = {Barraquand, B. and Kavraki, Lydia E and Latombe, Jean-Claude and Li, T.-Y. and Motwani, R. and Raghavan, P.} }
@inproceedings{kavraki-kolountzakis1996analysis-of-probabilistic, title = {Analysis of Probabilistic Roadmaps for Path Planning}, booktitle = {Proceeedings of The 1996 International Conference on Robotics and Automation (ICRA 1996)}, year = {1996}, pages = {3020-3026}, address = {Minneapolis, MN}, keywords = {fundamentals of sampling-based motion planning}, doi = {10.1109/ROBOT.1996.509171}, author = {Kavraki, Lydia E and Kolountzakis, M. N. and Latombe, Jean-Claude} }
@article{kavraki-svestka1996probabilistic-roadmaps-for, title = {Probabilistic Roadmaps for Path Planning in High Dimensional Configuration Spaces}, journal = {IEEE Transactions on Robotics and Automation}, volume = {12}, number = {4}, year = {1996}, pages = {566-580}, abstract = {A new motion planning method for robots in static workspaces is presented. This method proceeds in two phases: a learning phase and a query phase. In the learning phase, a probabilistic roadmap is constructed and stored as a graph whose nodes correspond to collision-free configurations and whose edges correspond to feasible paths between these configurations. These paths are computed using a simple and fast local planner. In the query phase, any given start and goal configurations of the robot are connected to two nodes of the roadmap; the roadmap is then searched for a path joining these two nodes. The method is general and easy to implement. It can be applied to virtually any type of holonomic robot. It requires selecting certain parameters (e.g., the duration of the learning phase) whose values depend on the scene, that is the robot and its workspace. But these values turn out to be relatively easy to choose, Increased efficiency can also be achieved by tailoring some components of the method (e.g., the local planner) to the considered robots. In this paper the method is applied to planar articulated robots with many degrees of freedom. Experimental results show that path planning can be done in a fraction of a second on a contemporary workstation (\≈150 MIPS), after learning for relatively short periods of time (a few dozen seconds)}, keywords = {fundamentals of sampling-based motion planning}, doi = {10.1109/70.508439}, author = {Kavraki, Lydia E and {\v{S}}vestka, P. and Latombe, Jean-Claude and Overmars, M.} }
@inproceedings{barraquand-kavraki1996random-sampling-scheme, title = {A Random Sampling Scheme for Robot Path Planning}, booktitle = {Robotics Research}, year = {1996}, note = {Book contains selected papers form the 7th International Conference on Robotics Research (ISRR), 1996}, pages = {249-264}, publisher = {Springer}, address = {North Holland}, keywords = {fundamentals of sampling-based motion planning}, doi = {10.1007/978-1-4471-0765-1_28}, author = {Barraquand, B. and Kavraki, Lydia E and Latombe, Jean-Claude and Li, T.-Y. and Motwani, R. and Raghavan, P.} }
@inproceedings{kavraki-latombe1995randomized-query-processing, title = {Randomized Query Processing in Robot Path Planning}, booktitle = {Proceedings of the 27th Annual ACM Symposium on Theory of Computing (STOC)}, year = {1995}, month = may, pages = {353-362}, publisher = {ACM Press}, address = {Las Vegas, NV}, keywords = {fundamentals of sampling-based motion planning}, doi = {10.1145/225058.225159}, author = {Kavraki, Lydia E and Latombe, Jean-Claude and Motwani, R. and Raghavan, P.} }
@inproceedings{kavraki-latombe1994randomized-preprocessing-of, title = {Randomized Preprocessing of Configuration Space for Fast Path Planning}, booktitle = {Proceedings of the International Conference on Robotics and Automation (ICRA)}, year = {1994}, pages = {2138-2139}, publisher = {IEEE Press}, address = {San Diego, CA}, keywords = {fundamentals of sampling-based motion planning}, doi = {10.1109/ROBOT.1994.350966}, author = {Kavraki, Lydia E and Latombe, Jean-Claude} }
@inproceedings{kavraki-latombe1994randomized-preprocessing-of_2, title = {Randomized Preprocessing of Configuration Space for Path Planning: Articulated Robots}, booktitle = {Proceedings of the IEEE/RSJ/GI International Conference on Intelligent Robots and Systems (IROS)}, year = {1994}, pages = {1764-1771}, publisher = {IEEE Press}, address = {Munchen, Germany}, abstract = {This paper describes the application of a recent approach to path planning for robots with many degrees of freedom (DOF) to articulated robots moving in two or three dimensional static environments. The planning approach, which itself is not restricted to articulated robots, consists of a preprocessing and a planning stage. The preprocessing is done only once for a given environment and generates a connected network of randomly, but properly selected, collision-free configurations (nodes). The planning then connects any given initial and final configurations of the robot to two nodes of the network and computes a path through the network between these two nodes. We show that after paying the preprocessing cost, planning is extremely fast for many difficult examples involving 7-DOF and 12-DOF robots. The approach is particularly attractive for many-DOF robots which have to perform many successive point-to-point motions in the same environment.}, keywords = {fundamentals of sampling-based motion planning}, doi = {10.1109/IROS.1994.407619}, author = {Kavraki, Lydia E and Latombe, Jean-Claude} }
@inproceedings{vidal2019online-multilayered-motion-planning, abstract = {Underwater robots are subject to complex hydrodynamic forces. These forces define how the vehicle moves, so it is important to consider them when planning trajectories. However, performing motion planning considering the dynamics on the robot's onboard computer is challenging due to the limited computational resources available. In this paper an efficient motion planning framework for AUV is presented. By introducing a loosely coupled multilayered planning design, our framework is able to generate dynamically feasible trajectories while keeping the planning time low enough for online planning. First, a fast path planner operating in a lower-dimensional projected space computes a lead path from the start to the goal configuration. Then, the lead path is used to bias the sampling of a second motion planner, which takes into account all the dynamic constraints. Furthermore, we propose a strategy for online planning that saves computational resources by generating the final trajectory only up to a finite horizon. By using the finite horizon strategy together with the multilayered approach, the sampling of the second planner focuses on regions where good quality solutions are more likely to be found, significantly reducing the planning time. To provide strong safety guarantees our framework also incorporates the conservative approximations of ICS. Finally, we present simulations and experiments using a real underwater robot to demonstrate the capabilities of our framework.}, author = {Vidal Garcia, Eduard and Moll, Mark and Palomeras, Narcis and Hern{\'a}ndez, Juan David and Carreras, Marc and Kavraki, Lydia E.}, booktitle = {{IEEE} International Conference on Robotics and Automation}, month = may, title = {Online Multilayered Motion Planning with Dynamic Constraints for Autonomous Underwater Vehicles}, year = {2019}, pages = {8936--8942}, note = {(Top-3 finalist for best student paper award)}, keywords = {planning from high-level specifications, kinodynamic systems}, doi = {10.1109/ICRA.2019.8794009} }
@article{muhayyuddin2018randomized-physics-based-motion-planning, abstract = {Planning motions to grasp an object in cluttered and uncertain environments is a challenging task, particularly when a collision-free trajectory does not exist and objects obstructing the way are required to be carefully grasped and moved out. This paper takes a different approach and proposes to address this problem by using a randomized physics-based motion planner that permits robot-object and object-object interactions. The main idea is to avoid an explicit high-level reasoning of the task by providing the motion planner with a physics engine to evaluate possible complex multi-body dynamical interactions. The approach is able to solve the problem in complex scenarios, also considering uncertainty in the objects' pose and in the contact dynamics. The work enhances the state validity checker, the control sampler and the tree exploration strategy of a kinody- namic motion planner called KPIECE. The enhanced algorithm, called p-KPIECE, has been validated in simulation and with real experiments. The results have been compared with an ontological physics-based motion planner and with task and motion planning approaches, resulting in a significant improvement in terms of planning time, success rate and quality of the solution path.}, author = {Muhayyuddin and Moll, Mark and Kavraki, Lydia E. and Rosell, Jan}, journal = {IEEE Robotics and Automation Letters}, keywords = {kinodynamic systems}, title = {Randomized Physics-based Motion Planning for Grasping in Cluttered and Uncertain Environments}, year = {2018}, volume = {3}, number = {2}, pages = {712--719}, month = apr, doi = {10.1109/LRA.2017.2783445} }
@inproceedings{butler2016a-general-algorithm-for-time-optimal-trajectory, abstract = {This paper presents a new algorithm which generates time-optimal trajectories given a path as input. The algorithm improves on previous approaches by generically handling a broader class of constraints on the dynamics. It eliminates the need for heuristics to select trajectory segments that are part of the optimal trajectory through an exhaustive, but efficient search. We also present an algorithm for computing all achievable velocities at the end of a path given an initial range of velocities. This algorithm effectively computes bundles of feasible trajectories for a given path and is a first step toward a new generation of more efficient kinodynamic motion planning algorithms. We present results for both algorithms using a simulated WAM arm with a Barrett hand subject to dynamics constraints on joint torque, joint velocity, momentum, and end effector velocity. The new algorithms are compared with a state-of-the-art alternative approach.}, author = {Butler, Stephen and Moll, Mark and Kavraki, Lydia E.}, booktitle = {Proceedings of the Workshop on the Algorithmic Foundations of Robotics}, month = dec, title = {A General Algorithm for Time-Optimal Trajectory Generation Subject to Minimum and Maximum Constraints}, year = {2016}, keywords = {kinodynamic systems} }
@article{gipson-hsu2012computational-models-of, title = {Computational Models of Proteins Kinematics and Dynamics: Beyond Simulation}, journal = {Annual Reviews of Analytical Chemistry}, volume = {5}, year = {2012}, month = apr, pages = {273-291}, abstract = {Physics-based simulation represents a powerful method for investigating the time-varying behavior of dynamic protein systems at high spatial and temporal resolution. Such simulations, however, can be prohibitively difficult or lengthy for large proteins or when probing the lower-resolution, long-timescale behaviors of proteins generally. Importantly, not all questions about a protein system require full space and time resolution to produce an informative answer. For instance, by avoiding the simulation of uncorrelated, high-frequency atomic movements, a larger, domain-level picture of protein dynamics can be revealed. The purpose of this review is to highlight the growing body of complementary work that goes beyond simulation. In particular, this review focuses on methods that address kinematics and dynamics, as well as those that address larger organizational questions and can quickly yield useful information about the long-timescale behavior of a protein.}, keywords = {fundamentals of protein modeling, kinodynamic systems}, doi = {10.1146/annurev-anchem-062011-143024}, note = {PMCID: PMC4866812, PMID: 22524225}, msid = {NIHMS712423}, author = {Gipson, B and Hsu, David and Kavraki, Lydia E and Latombe, Jean-Claude} }
@article{bekris-grady2012safe-distributed-motion, title = {Safe Distributed Motion Coordination for Second-Order Systems With Different Planning Cycles}, journal = {International Journal of Robotics Research}, volume = {31}, number = {2}, year = {2012}, month = feb, pages = {129-150}, chapter = {129}, abstract = {When multiple robots operate in the same environment, it is desirable for scalability purposes to coordinate their motion in a distributed fashion while providing guarantees about their safety. If the robots have to respect second-order dynamics, this becomes a challenging problem, even for static environments. This work presents a replanning framework where each robot computes partial plans during each cycle, while executing a previously computed trajectory. Each robot communicates with its neighbors to select a trajectory that is safe over an infinite time horizon. The proposed approach does not require synchronization and allows the robots to dynamically change their cycles over time. This paper proves that the proposed motion coordination algorithm guarantees safety under this general setting. This framework is not specific to the underlying robot dynamics, as it can be used with a variety of dynamical systems, nor to the planning or control algorithm used to generate the robot trajectories. The performance of the approach is evaluated using a distributed multi-robot simulator on a computing cluster, where the simulated robots are forced to communicate by exchanging messages. The simulation results confirm the safety of the algorithm in various environments with up to 32 robots governed by second-order dynamics.}, keywords = {kinodynamic systems}, doi = {10.1177/0278364911430420}, author = {Bekris, Kostas E. and Grady, Devin K and Moll, Mark and Kavraki, Lydia E} }
@incollection{grady-bekris2011asynchronous-distributed-motion, title = {Asynchronous Distributed Motion Planning with Safety Guarantees under Second-Order Dynamics}, booktitle = {Algorithmic Foundations of Robotics IX}, series = {Springer Tracts in Advanced Robotics}, volume = {68}, year = {2011}, pages = {53-70}, publisher = {Springer Berlin / Heidelberg}, address = {Singapore, Singapore}, abstract = {As robots become more versatile, they are increasingly found to operate together in the same environment where they must coordinate their motion in a distributed manner. Such operation does not present problems if the motion is quasi-static and collisions can be easily avoided. However, when the robots follow second-order dynamics, the problem becomes challenging even for a known environment. The setup in this work considers that each robot replans its own trajectory for the next replanning cycle. The planning process must guarantee the robot{\textquoteright}s safety by ensuring collision-free paths for the considered period and by not bringing the robot to states where collisions cannot be avoided in the future. This problem can be addressed through communication among the robots, but it becomes complicated when the replanning cycles of the different robots are not synchronized and the robots make planning decisions at different time instants. This paper shows how to guarantee the safe operation of multiple communicating second-order vehicles, whose replanning cycles do not coincide, through an asynchronous, distributed motion planning framework. The method is evaluated through simulations, where each robot is simulated on a different processor and communicates with its neighbors through message passing. The simulations confirm that the approach provides safety in scenarios with up to 48 robots with second-order dynamics in environments with obstacles, where collisions occur often without a safety framework.}, keywords = {kinodynamic systems}, doi = {10.1007/978-3-642-17452-0_4}, author = {Grady, Devin K and Bekris, Kostas E. and Kavraki, Lydia E} }
@article{plaku-kavraki2010motion-planning-with, title = {Motion Planning with Dynamics by a Synergistic Combination of Layers of Planning}, journal = {IEEE Transactions on Robotics}, volume = {26}, number = {3}, year = {2010}, month = jun, pages = {469--482}, chapter = {469}, abstract = {To efficiently solve challenges related to motion-planning problems with dynamics, this paper proposes treating motion planning not just as a search problem in a continuous space but as a search problem in a hybrid space consisting of discrete and continuous components. A multilayered framework is presented which combines discrete search and sampling-based motion planning. This framework is called synergistic combination of layers of planning ( SyCLoP) hereafter. Discrete search uses a workspace decomposition to compute leads, i.e., sequences of regions in the neighborhood that guide sampling-based motion planning during the state-space exploration. In return, information gathered by motion planning, such as progress made, is fed back to the discrete search. This combination allows SyCLoP to identify new directions to lead the exploration toward the goal, making it possible to efficiently find solutions, even when other planners get stuck. Simulation experiments with dynamical models of ground and flying vehicles demonstrate that the combination of discrete search and motion planning in SyCLoP offers significant advantages. In fact, speedups of up to two orders of magnitude were obtained for all the sampling-based motion planners used as the continuous layer of SyCLoP.}, keywords = {kinodynamic systems, planning from high-level specifications}, doi = {10.1109/TRO.2010.2047820}, author = {Plaku, E. and Kavraki, Lydia E and Vardi, Moshe Y.} }
@inproceedings{sucan-kavraki2009kinodynamic-motion-planning, title = {Kinodynamic Motion Planning by Interior-Exterior Cell Exploration}, booktitle = {Algorithmic Foundation of Robotics VIII (Proceedings of Workshop on the Algorithmic Foundations of Robotics)}, volume = {57}, year = {2009}, pages = {449-464}, publisher = {STAR}, address = {Guanajuato, Mexico}, abstract = { This paper presents a kinodynamic motion planner, Kinodynamic Motion Planning by Interior-Exterior Cell Exploration (KPIECE), specifically designed for systems with complex dynamics, where physics-based simulation is necessary. A multiple-level grid-based discretization is used to estimate the coverage of the state space. The coverage estimates help the planner detect the less explored areas of the state space. The planner also keeps track of the boundary of the explored region of the state space and focuses exploration on the less covered parts of this boundary. Extensive experiments show KPIECE provides computational gain over state-of-the-art methods and allows solving some harder, previously unsolvable problems. A shared memory parallel implementation is presented as well. This implementation provides better speedup than an embarrassingly parallel implementation by taking advantage of the evolving multi-core technology.}, keywords = {kinodynamic systems}, doi = {10.1007/978-3-642-00312-7_28}, author = {Sucan, Ioan Alexandru and Kavraki, Lydia E} }
@article{bekris-tsianos2009safe-and-distributed, title = {Safe and Distributed Kinodynamic Replanning for Vehicular networks}, journal = {ACM/Springer Mobile Networks and Applications (MONET)}, volume = {14}, number = {3}, year = {2009}, pages = {292{\textendash}308}, abstract = {This work deals with the problem of planning collision-free motions for multiple communicating vehicles that operate in the same, partially-observable environment in real-time. A challenging aspect of this problem is how to utilize communication so that vehicles do not reach states from which collisions cannot be avoided due to second-order motion constraints. This paper initially shows how it is possible to provide theoretical safety guarantees with a priority-based coordination scheme. Safety means avoiding collisions with obstacles and between vehicles. This notion is also extended to include the retainment of a communication network when the vehicles operate as a networked team. The paper then progresses to extend this safety framework into a fully distributed communication protocol for real-time planning. The proposed algorithm integrates sampling-based motion planners with message-passing protocols for distributed constraint optimization. Each vehicle uses the motion planner to generate candidate feasible trajectories and the message-passing protocol for selecting a safe and compatible trajectory. The existence of such trajectories is guaranteed by the overall approach. The theoretical results have also been experimentally confirmed with a distributed simulator built on a cluster of processors and using applications such as coordinated exploration. Furthermore, experiments show that the distributed protocol has better scalability properties when compared against the priority-based scheme.}, keywords = {kinodynamic systems}, doi = {10.1007/s11036-009-0152-y}, author = {Bekris, Kostas E. and Tsianos, Konstantinos I. and Kavraki, Lydia E} }
@inproceedings{tsianos-kavraki2008replanning-powerful-planning, title = {Replanning: A powerful planning strategy for hard kinodynamic problems}, booktitle = {IEEE/RSJ International Conference on Intelligent Robots and Systems}, year = {2008}, month = sep, pages = {1667-1672}, address = {Nice, France}, abstract = { A series of kinodynamic sampling-based planners have appeared over the last decade to deal with high dimen- sional problems for robots with realistic motion constraints. Yet, offline sampling-based planners only work in static and known environments, suffer from unbounded memory requirements and the produced paths tend to contain a lot of unnecessary maneuvers. This paper describes an online replanning algo- rithm which is flexible and extensible. Our results show that using a sampling-based planner in a loop, we can guide the robot to its goal using a low dimensional navigation function. We obtain higher success rates and shorter solution paths in a series of problems using only bounded memory.}, keywords = {kinodynamic systems}, isbn = {978-1-4244-2058-2}, doi = {10.1109/IROS.2008.4650965}, author = {Tsianos, Konstantinos I. and Kavraki, Lydia E} }
@inproceedings{plaku-kavraki2008discrete-search-leading, title = {Discrete Search Leading Continuous Exploration for Kinodynamic Motion Planning}, booktitle = {Robotics: Science and Systems}, year = {2008}, month = jun, pages = {326-333}, publisher = {MIT Press}, address = {Atlanta, Georgia}, abstract = {This paper presents the Discrete Search Leading continuous eXploration (DSLX) planner, a multi-resolution approach to motion planning that is suitable for challenging problems involving robots with kinodynamic constraints. Initially the method decomposes the workspace to build a graph that encodes the physical adjacency of the decomposed regions. This graph is searched to obtain leads, that is, sequences of regions that can be explored with sampling-based tree methods to generate solution trajectories. Instead of treating the discrete search of the adjacency graph and the exploration of the continuous state space as separate components, DSLX passes information from one to the other in innovative ways. Each lead suggests what regions to explore and the exploration feeds back information to the discrete search to improve the quality of future leads. Information is encoded in edge weights, which indicate the importance of including the regions associated with an edge in the next exploration step. Computation of weights, leads, and the actual exploration make the core loop of the algorithm. Extensive experimentation shows that DSLX is very versatile. The discrete search can drastically change the lead to reflect new information allowing DSLX to find solutions even when sampling-based tree planners get stuck. Experimental results on a variety of challenging kinodynamic motion planning problems show computational speedups of two orders of magnitude over other widely used motion planning methods.}, keywords = {kinodynamic systems}, url = {http://www.roboticsproceedings.org/rss03/p40.html}, author = {Plaku, E. and Kavraki, Lydia E and Vardi, Moshe Y.} }
@inproceedings{sucan-kruse2008kinodynamic-motion-planning, title = {Kinodynamic Motion Planning with Hardware Demonstrations}, booktitle = {IEEE/RSJ International Conference on Intelligent Robots and Systems}, year = {2008}, pages = {1661--1666}, address = {Nice, France}, abstract = {This paper provides proof-of-concept that state-of-the-art sampling-based motion planners that are tightly integrated with a physics-based simulator can compute paths that can be executed by a physical robotic system. Such a goal has been the subject of intensive research during the last few years and reflects the desire of the motion planning community to produce paths that are directly relevant to realistic mechanical systems and do not need a huge post-processing step in order to be executed on a robotic platform. To evaluate this approach, a recently developed motion planner is used to compute paths for a modular robot constructed from seven modules. These paths are then executed on hardware and compared with the paths predicted by the planner. For the system considered, the planner prediction and the paths achieved by the physical robot match, up to small errors. This work reveals the potential of modern motion planning research and its implications in the design and operation of complex robotic platforms.}, keywords = {kinodynamic systems}, doi = {10.1109/IROS.2008.4650914}, author = {Sucan, Ioan Alexandru and Kruse, Jonathan F. and Yim, Mark and Kavraki, Lydia E} }
@inproceedings{sucan-kruse2008reconfiguration-for-modular, title = {Reconfiguration for modular robots using kinodynamic motion planning}, booktitle = {ASME -- Dynamic Systems and Control}, year = {2008}, address = {Ann Arbor, Michigan, USA}, keywords = {kinodynamic systems}, doi = {10.1115/DSCC2008-2296}, author = {Sucan, Ioan Alexandru and Kruse, Jonathan F. and Yim, Mark and Kavraki, Lydia E} }
@inproceedings{bekris-tsianos2007decentralized-planner-that, title = {A Decentralized Planner that Guarantees the Safety of Communicating Vehicles with Complex Dynamics that Replan Online}, booktitle = {IEEE/RSJ International Conference on Intelligent Robots and Systems}, year = {2007}, month = oct, address = {San Diego, CA}, abstract = {This paper considers the problem of coordinating multiple vehicles with kinodynamic constraints that operate in the same partially-known environment. The vehicles are able to communicate within limited range. Their objective is to avoid collisions between them and with the obstacles, while the vehicles move towards their goals. An important issue of real-time planning for systems with bounded acceleration is that inevitable collision states must also be avoided. The focus of this paper is to guarantee safety despite the dynamic constraints with a decentralized motion planning technique that employs only local information. We propose a coordination framework that allows vehicles to generate and select compatible sets of valid trajectories and prove that this scheme guarantees collision-avoidance in the specified setup. The theoretical results have been also experimentally confirmed with a distributed simulator where each vehicle replans online with a sampling-based, kinodynamic motion planner and uses message-passing to communicate with neighboring agents.}, keywords = {kinodynamic systems}, doi = {10.1109/IROS.2007.4399520}, author = {Bekris, Kostas E. and Tsianos, Konstantinos I. and Kavraki, Lydia E} }
@inproceedings{bekris-tsianos2007distributed-protocol-for, title = {A Distributed Protocol for Safe Real-Time Planning of Communicating Vehicles with Second-Order Dynamics}, booktitle = {First International Conference on Robot Communication and Coordination (ROBOCOMM 07)}, year = {2007}, month = oct, address = {Athens, Greece}, abstract = {This work deals with the problem of planning in real-time, collision-free motions for multiple communicating vehicles that operate in the same, partially-observable environment. A challenging aspect of this problem is how to utilize communication so that vehicles do not reach states from which collisions cannot be avoided due to second-order motion constraints. This paper provides a distributed communication protocol for real-time planning that guarantees collision avoidance with obstacles and between vehicles. It can also allow the retainment of a communication network when the vehicles operate as a networked team. The algorithm is a novel integration of sampling-based motion planners with message-passing protocols for distributed constraint optimization. Each vehicle uses the motion planner to generate candidate feasible trajectories and the message-passing protocol for selecting a safe and compatible trajectory. The existence of such trajectories is guaranteed by the overall approach. Experiments on a distributed simulator built on a cluster of processors confirm the safety properties of the approach in applications such as coordinated exploration. Furthermore, the distributed protocol has better scalability properties when compared against typical priority-based schemes.}, keywords = {kinodynamic systems}, author = {Bekris, Kostas E. and Tsianos, Konstantinos I. and Kavraki, Lydia E} }
@inproceedings{bekris-kavraki2007greedy-but-safe, title = {Greedy but Safe Replanning under Kinodynamic Constraints}, booktitle = {International Conference on Robotics and Automation}, year = {2007}, month = apr, pages = {704-710}, publisher = {IEEE press}, address = {Rome, Italy}, abstract = {We consider motion planning problems for a vehicle with kinodynamic constraints, where there is partial knowledge about the environment and replanning is required. We present a new tree-based planner that explicitly deals with kinodynamic constraints and addresses the safety issues when planning under finite computation times, meaning that the vehicle avoids collisions in its evolving configuration space. In order to achieve good performance we incrementally update a tree data-structure by retaining information from previous steps and we bias the search of the planner with a greedy, yet probabilistically complete state space exploration strategy. Moreover, the number of collision checks required to guarantee safety is kept to a minimum. We compare our technique with alternative approaches as a standalone planner and show that it achieves favorable performance when planning with dynamics. We have applied the planner to solve a challenging replanning problem involving the mapping of an unknown workspace with a non-holonomic platform.}, keywords = {kinodynamic systems}, doi = {10.1109/ROBOT.2007.363069}, author = {Bekris, Kostas E. and Kavraki, Lydia E} }
@inproceedings{plaku-kavraki2007motion-planner-for, title = {A Motion Planner for a Hybrid Robotic System with Kinodynamic Constraints}, booktitle = {IEEE International Conference on Robotics and Automation (ICRA)}, year = {2007}, pages = {692--697}, address = {Rome, Italy}, abstract = {The rapidly increasing complexity of tasks robotic systems are expected to carry out underscores the need for the development of motion planners that can take into account discrete changes in the continuous motions of the system. Completion of tasks such as exploration of unknown or hazardous environments often requires discrete changes in the controls and motions of the robot in order to adapt to different terrains or maintain operability during partial failures or other mishaps. The contribution of this work toward this objective is the development of an efficient motion planner for a hybrid robotic system. The controls and motion equations of the robot could change discretely in order to enable the robot to operate in different terrains. The framework in this paper blends discrete searching with sampling-based motion planning for continuous state spaces and is well-suited for robotic systems modeled as hybrid systems with numerous discrete modes and transitions. This multi-layered approach offers considerable improvements over existing methods addressing similar problems, as indicated by the experimental results.}, keywords = {kinodynamic systems}, doi = {10.1109/ROBOT.2007.363067}, author = {Plaku, E. and Kavraki, Lydia E and Vardi, Moshe Y.} }
@inproceedings{ladd-kavraki2005motion-planning-in, title = {Motion Planning in the Presence of Drift, Underactuation and Discrete System Changes}, booktitle = {Robotics: Science and Systems I}, year = {2005}, month = jun, pages = {233-241}, publisher = {MIT Press}, address = {Boston, MA}, abstract = {Motion planning research has been successful in developing planning algorithms which are effective for solving problems with complicated geometric and kinematic constraints. Various applications in robotics and in other fields demand additional physical realism. Some progress has been made for non-holonomic systems. However systems with significant drift, underactuation and discrete system changes remain challenging for existing planning techniques particularly as the dimensionality of the state space increases. In this paper, we demonstrate a motion planning technique for the solution of problems with these challenging characteristics. Our approach uses sampling-based motion planning and subdivision methods. The problem that we solve is a game that was chosen to exemplify characteristics of dynamical systems that are difficult for planning. To our knowledge, this is first application of algorithmic motion planning to a problem of this type and complexity.}, keywords = {kinodynamic systems}, url = {http://www.roboticsproceedings.org/rss01/p31.html}, author = {Ladd, A. M. and Kavraki, Lydia E} }
@incollection{ladd-kavraki2005fast-tree-based-exploration, title = {Fast Tree-Based Exploration of State Space for Robots with Dynamics}, booktitle = {Algorithmic Foundations of Robotics VI}, year = {2005}, pages = {297-312}, publisher = {Springer, STAR 17}, abstract = {This paper presents a new motion planning algorithm which we call the Path-Directed Subdivision Tree exploration Planner PDST-EXPLORE. It is a sampling-based method which builds a tree and takes a substantially different approach from other exploration planners such as RRT [18] and EST [12]. PDST-EXPLORE is a general purpose planner but is designed to overcome difficulties inherent in planning for robots with non-trivial dynamics. Specifically, our planner represents samples as path segments rather than individual states and uses non-uniform subdivisions of the state space to estimate coverage. This change avoids many of the problems that previous sampling-based planners have had with milestone placement, metrics and coverage estimation. We use a deterministic update schedule together with randomized path generation to adaptively strike a balance between greedy exploration and methodical search. We have obtained a proof of probabilistic completeness for the planner which assumes very little about the specific robot system that the planner operates on. Finally, we have implemented the planner for planar kinodynamic point robots, differential drive robots and blimp-like robots. The experimental results demonstrate the efficiency of the planner{\textquoteright}s implementation as well as its robustness in covering the entire reachable free space.}, keywords = {fundamentals of sampling-based motion planning, kinodynamic systems}, doi = {10.1007/10991541_21}, author = {Ladd, A. M. and Kavraki, Lydia E} }
@inproceedings{phillips-bedrosian2004guided-expansive-spaces, title = {Guided Expansive Spaces Trees: A Search Strategy for Motion- and Cost-Constrained State Spaces}, booktitle = {Proceedings of The IEEE International Conference on Robotics and Automation (ICRA)}, year = {2004}, month = apr, pages = {3968-3973}, publisher = {IEEE Press}, address = {New Orleans, LA}, abstract = {Motion planning for systems with constraints on controls or the need for relatively straight paths for real-time actions presents challenges for modern planners. This paper presents an approach which addresses these types of systems by building on existing motion planning approaches. Guided Expansive Spaces Trees are introduced to search for a low cost and relatively straight path in a space with motion constraints. Path Gradient Descent, which builds on the idea of Elastic Strips, finds the locally optimal path for an existing path. These techniques are tested on simulations of rendezvous and docking of the space shuttle to the International Space Station and of a 4-foot fan-controlled blimp in a factory setting.}, keywords = {kinodynamic systems}, doi = {10.1109/ROBOT.2004.1308890}, author = {Phillips, Jeff M. and Bedrosian, N. and Kavraki, Lydia E} }
@inproceedings{phillips-kavraki2003spacecraft-rendezvous-and, title = {Spacecraft Rendezvous and Docking With Real-Time Randomized Optimization}, booktitle = {AIAA (American Institute of Aeronautics and Astronautics) Guidance, Navigation and Control Conference}, year = {2003}, month = aug, address = {Austin, TX}, keywords = {kinodynamic systems}, author = {Phillips, Jeff M. and Kavraki, Lydia E and Bedrosian, N.} }
@inproceedings{phillips-kavraki2003probabilistic-optimization-applied, title = {Probabilistic Optimization Applied to Spacecraft Rendezvous and Docking}, booktitle = {13th American Astronomical Society/AIAA - Space Flight Mechanics Meeting}, year = {2003}, month = feb, address = {Puerto Rico}, keywords = {kinodynamic systems}, author = {Phillips, Jeff M. and Kavraki, Lydia E and Bedrosian, N.} }
@inproceedings{bekris-glick2006evaluation-of-algorithms, title = {Evaluation of Algorithms for Bearing-Only {SLAM}}, booktitle = {Proceedings of The IEEE International Conference on Robotics and Automation (ICRA)}, year = {2006}, month = may, pages = {1937-1944}, publisher = {IEEE Press}, address = {Orlando, FL}, abstract = {An important milestone for building affordable robots that can become widely popular is to address robustly the Simultaneous Localization and Mapping (SLAM) problem with inexpensive, off-the-shelf sensors, such as monocular cameras. These sensors, however, impose significant challenges on SLAM procedures because they provide only bearing data related to environmental landmarks. This paper starts by providing an extensive comparison of different techniques for bearing-only SLAM in terms of robustness under different noise models, landmark densities and robot paths. We have experimented in a simulated environment with a variety of existing online algorithms including Rao-Blackwellized Particle Filters (RB-PFs). Our experiments suggest that RB-PFs are more robust compared to other existing methods and run considerably faster. Nevertheless, their performance suffers in the presence of outliers. In order to overcome this limitation we proceed to propose an augmentation of RB-PFs with: (a) Gaussian Sum Filters for landmark initialization and (b) an online, unsupervised outlier rejection policy. This framework exhibits impressive robustness and efficiency even in the presence of outliers.}, keywords = {localization}, doi = {10.1109/ROBOT.2006.1641989}, author = {Bekris, Kostas E. and Glick, M. and Kavraki, Lydia E} }
@article{ladd-bekris2005robotics-based-location-sensing, title = {Robotics-Based Location Sensing using Wireless Ethernet (Invited)}, journal = {Wireless Networks (The Journal of Mobile Communication, Computation and Information)}, volume = {11}, number = {1-2}, year = {2005}, month = jan, pages = {189-204}, abstract = {A key subproblem in the construction of location-aware systems is the determination of the position of a mobile device. This article describes the design, implementation and analysis of a system for determining position inside a building from measured RF signal strengths of packets on an IEEE 802.11b wireless Ethernet network. Previous approaches to location-awareness with RF signals have been severely hampered by non-Gaussian signals, noise, and complex correlations due to multi-path effects, interference and absorption. The design of our system begins with the observation that determining position from complex, noisy and non-Gaussian signals is a wellstudied problem in the field of robotics. Using only off-the-shelf hardware, we achieve robust position estimation to within a meter in our experimental context and after adequate training of our system. We can also coarsely determine our orientation and can track our position as we move. Our results show that we can localize a stationary device to within 1.5 meters over 80\% of the time and track a moving device to within 1 meter over 50\% of the time. Both localization and tracking run in real-time. By applying recent advances in probabilistic inference of position and sensor fusion from noisy signals, we show that the RF emissions from base stations as measured by off-the-shelf wireless Ethernet cards are sufficiently rich in information to permit a mobile device to reliably track its location.}, keywords = {localization}, doi = {10.1007/s11276-004-4755-8}, author = {Ladd, A. M. and Bekris, Kostas E. and Rudys, A. and Marceau, G. and Kavraki, Lydia E and Wallach, D. S.} }
@inproceedings{haeberlen-flannery2004practical-robust-localization, title = {Practical Robust Localization over Large-Scale 802.11 Wireless Networks}, booktitle = {Proceedings of the Tenth ACM International Conference on Mobile Computing and Networking (MOBICOM 2004)}, year = {2004}, month = sep, pages = {70-84}, address = {Philadelphia, PA}, abstract = {We demonstrate a system built using probabilistic techniques that allows for remarkably accurate localization across our entire office building using nothing more than the built-in signal intensity meter supplied by standard 802.11 cards. While prior systems have required significant investments of human labor to build a detailed signal map, we can train our system by spending less than one minute per office or region, walking around with a laptop and recording the observed signal intensities of our building{\textquoteright}s unmodified base stations. We actually collected over two minutes of data per office or region, about 28 man-hours of effort. Using less than half of this data to train the localizer, we can localize a user to the precise, correct location in over 95\% of our attempts, across the entire building. Even in the most pathological cases, we almost never localize a user any more distant than to the neighboring office. A user can obtain this level of accuracy with only two or three signal intensity measurements, allowing for a high frame rate of localization results. Furthermore, with a brief calibration period, our system can be adapted to work with previously unknown user hardware. We present results demonstrating the robustness of our system against a variety of untrained time-varying phenomena, including the presence or absence of people in the building across the day. Our system is sufficiently robust to enable a variety of location-aware applications without requiring special-purpose hardware or complicated training and calibration procedures.}, keywords = {localization}, doi = {10.1145/1023720.1023728}, author = {Haeberlen, A. and Flannery, E. and Ladd, A. M. and Rudys, A. and Wallach, D. S. and Kavraki, Lydia E} }
@article{ladd-bekris2004on-feasibility-of, title = {On the Feasibility of Using Wireless Ethernet for Indoor Localization}, journal = {IEEE Transactions on Robotics and Automation}, volume = {20}, number = {3}, year = {2004}, month = jun, pages = {555-559}, abstract = {IEEE 802.11b wireless Ethernet is becoming the standard for indoor wireless communication. This paper proposes the use of measured signal strength of Ethernet packets as a sensor for a localization system. We demonstrate that off-the-shelf hardware can accurately be used for location sensing and real-time tracking by applying a Bayesian localization framework.}, keywords = {localization}, doi = {10.1109/TRA.2004.824948}, author = {Ladd, A. M. and Bekris, Kostas E. and Rudys, A. and Kavraki, Lydia E and Wallach, D. S.} }
@inproceedings{ladd-bekris2002robotics-based-location-sensing, title = {Robotics-Based Location Sensing using Wireless Ethernet}, booktitle = {Proceedings of the Eight ACM International Conference on Mobile Computing and Networking (MOBICOM 2002)}, year = {2002}, month = sep, pages = {227-238}, publisher = {ACM Press}, address = {Atlanta, GE}, abstract = {A key subproblem in the construction of location-aware systems is the determination of the position of a mobile device. This paper describes the design, implementation and analysis of a system for determining position inside a building from measured RF signal strengths of packets on an IEEE 802.11b wireless Ethernet network. Previous approaches to location-awareness with RF signals have been severely hampered by non-linearity, noise and complex correlations due to multi-path effects, interference and absorption. The design of our system begins with the observation that determining position from complex, noisy and non-linear signals is a well-studied problem in the field of robotics. Using only off-the-shelf hardware, we achieve robust position estimation to within a meter in our experimental context and after adequate training of our system. We can also coarsely determine our orientation and can track our position as we move. By applying recent advances in probabilistic inference of position and sensor fusion from noisy signals, we show that the RF emissions from base stations as measured by off-the-shelf wireless Ethernet cards are sufficiently rich in information to permit a mobile device to reliably track its location.}, keywords = {localization}, doi = {10.1145/570645.570674}, author = {Ladd, A. M. and Bekris, Kostas E. and Rudys, A. and Marceau, G. and Kavraki, Lydia E and Wallach, D. S.} }
@inproceedings{ladd-bekris2002using-wireless-ethernet, title = {Using Wireless Ethernet for Localization}, booktitle = {Proceedings of the 2002 IEEE/RJS International Conference on Intelligent Robots and Systems (IROS 2002)}, volume = {1}, year = {2002}, month = sep, pages = {402-408}, publisher = {IEEE Press}, address = {Lausanne, Switzerland}, abstract = {IEEE 802.11b wireless Ethernet is rapidly becoming the standard for in-building and short-range wireless communication. Many mobile devices such as mobile robots, laptops and PDAs already use this protocol for wireless communication. Many wireless Ethernet cards measure the signal strength of incoming packets. This paper investigates the feasibility of implementing a localization system using this sensor. Using a Bayesian localization framework, we show experiments demonstrating that off-the-shelf wireless hardware can accurately be used for location sensing and tracking with about one meter precision in a wireless-enabled office building.}, keywords = {localization}, doi = {10.1109/IRDS.2002.1041423}, author = {Ladd, A. M. and Bekris, Kostas E. and Marceau, G. and Rudys, A. and Kavraki, Lydia E and Wallach, D. S.} }
@article{litsa2019atom-mapping, abstract = {Atom mapping of a chemical reaction is a mapping between the atoms in the reactant molecules and the atoms in the product molecules. It encodes the underlying reaction mechanism and, as such, constitutes essential information in computational studies in metabolic engineering. Various techniques have been investigated for the automatic computation of the atom mapping of a chemical reaction, approaching the problem as a graph matching problem. The graph abstraction of the chemical problem, though, eliminates crucial chemical information. There have been efforts for enhancing the graph representation by introducing the bond stabilities as edge weights, as they are estimated based on experimental evidence. Here, we present a fully automated optimization-based approach, named AMLGAM, (Automated Machine Learning Guided Atom Mapping), that uses machine learning techniques for the estimation of the bond stabilities based on the chemical environment of each bond. The optimization method finds the reaction mechanism which favors the breakage/formation of the less stable bonds. We evaluated our method on a manually curated data set of 382 chemical reactions and ran our method on a much larger and diverse data set of 7400 chemical reactions. We show that the proposed method improves the accuracy over existing techniques based on results published by earlier studies on a common data set and is capable of handling unbalanced reactions.}, author = {Litsa, Eleni E. and Pena, Matthew I. and Moll, Mark and Giannakopoulos, George and Bennett, George N. and Kavraki, Lydia E.}, title = {Machine Learning Guided Atom Mapping of Metabolic Reactions}, journal = {Journal of Chemical Information and Modeling}, year = {2019}, doi = {10.1021/acs.jcim.8b00434}, note = {PMID: 30500191}, keywords = {metabolic networks}, volume = {59}, number = {3}, pages = {1121--1135} }
@article{kim2017_pathfinding_review, abstract = {Recent developments in metabolic engineering have led to the successful biosynthesis of valuable products, such as the precursor of the antimalarial compound, artemisinin, and opioid precursor, thebaine. Synthesizing these traditionally plant-derived compounds in genetically modified yeast cells introduces the possibility of significantly reducing the total time and resources required for their production, and in turn, allows these valuable compounds to become cheaper and more readily available. Most biosynthesis pathways used in metabolic engineering applications have been discovered manually, requiring a tedious search of existing literature and metabolic databases. However, the recent rapid development of available metabolic information has enabled the development of automated approaches for identifying novel pathways. Computer-assisted pathfinding has the potential to save biochemists time in the initial discovery steps of metabolic engineering. In this paper, we review the parameters and heuristics used to guide the search in recent pathfinding algorithms. These parameters and heuristics capture information on the metabolic network structure, compound structures, reaction features, and organism-specificity of pathways. No one metabolic pathfinding algorithm or search parameter stands out as the best to use broadly for solving the pathfinding problem, as each method and parameter has its own strengths and shortcomings. As assisted pathfinding approaches continue to become more sophisticated, the development of better methods for visualizing pathway results and integrating these results into existing metabolic engineering practices is also important for encouraging wider use of these pathfinding methods.}, keywords = {metabolic networks}, author = {Kim, Sarah M. and Pe\~{n}a, Matthew I. and Moll, Mark and Bennett, George N. and Kavraki, Lydia E.}, title = {A Review of Parameters and Heuristics for Guiding Metabolic Pathfinding}, journal = {Journal of Cheminformatics}, year = {2017}, volume = {9}, number = {1}, pages = {51}, month = sep, doi = {10.1186/s13321-017-0239-6}, note = {PMCID: PMC5602787, PMID: 29086092} }
@inproceedings{kim-pena2016an-evaluation-of-different-clustering-methods, abstract = {Large-scale annotated metabolic databases, such as KEGG and MetaCyc, provide a wealth of information to researchers designing novel biosynthetic pathways. However, many metabolic pathfinding tools that assist in identifying possible solution pathways fail to facilitate the grouping and interpretation of these pathway results. Clustering possible solution pathways can help users of pathfinding tools quickly identify major patterns and unique pathways without having to sift through individual results one by one. In this paper, we assess the ability of three separate clustering methods (hierarchical, k -means, and k -medoids) along with three pair-wise distance measures (Levenshtein, Jaccard, and n -gram) to expertly group lysine, isoleucine, and 3-hydroxypropanoic acid (3-HP) biosynthesis pathways. The quality of the resulting clusters were quantitatively evaluated against expected pathway groupings taken from the literature. Hierarchical clustering and Levenshtein distance seemed to best match external pathway labels across the three biosynthesis pathways. The lysine biosynthesis pathways, which had the most distinct separation of pathways, had better quality clusters than isoleucine and 3-HP, suggesting that grouping pathways with more complex underlying topologies may require more tailored clustering methods.}, author = {Kim, Sarah M. and Pe{\~n}a, Matthew I. and Moll, Mark and Giannakopoulos, George and Bennett, George N. and Kavraki, Lydia E.}, booktitle = {2016 International Conference on Bioinformatics and Computational Biology. ISCA}, keywords = {metabolic networks}, title = {An Evaluation of Different Clustering Methods and Distance Measures Used for Grouping Metabolic Pathways}, year = {2016}, pages = {115-122} }
@article{heath-bennett2011algorithm-for-efficient, title = {An Algorithm for Efficient Identification of Branched Metabolic Pathways}, journal = {Journal of Computational Biology}, volume = {18}, number = {11}, year = {2011}, month = nov, pages = {1575-1597}, abstract = {This article presents a new graph-based algorithm for identifying branched metabolic pathways in multi-genome scale metabolic data. The term branched is used to refer to metabolic pathways between compounds that consist of multiple pathways that interact biochemically. A branched pathway may produce a target compound through a combination of linear pathways that split compounds into smaller ones, work in parallel with many compounds, and join compounds into larger ones. While branched metabolic pathways predominate in metabolic networks, most previous work has focused on identifying linear metabolic pathways. The ability to automatically identify branched pathways is important in applications that require a deeper understanding of metabolism, such as metabolic engineering and drug target identification. The algorithm presented in this article utilizes explicit atom tracking to identify linear metabolic pathways and then merges them together into branched metabolic pathways. We provide results on several well-characterized metabolic pathways that demonstrate that the new merging approach can efficiently find biologically relevant branched metabolic pathways.}, keywords = {metabolic networks}, doi = {10.1089/cmb.2011.0165}, note = {PMID: 21999288}, author = {Heath, A. P. and Bennett, G. N. and Kavraki, Lydia E} }
@article{heath-bennett2011identifying-branched-metabolic, title = {Identifying Branched Metabolic Pathways by Merging Linear Metabolic Pathways}, journal = {15th Annual International Conference on Research in Computational Molecular Biology (RECOMB)}, volume = {6577/2011}, year = {2011}, pages = {70-84}, abstract = {This paper presents a graph-based algorithm for identifying complex metabolic pathways in multi-genome scale metabolic data. These complex pathways are called branched pathways because they can arrive at a target compound through combinations of pathways that split compounds into smaller ones, work in parallel with many compounds, and join compounds into larger ones. While most previous work has focused on identifying linear metabolic pathways, branched metabolic pathways predominate in metabolic networks. Automatic identification of branched pathways has a number of important applications in areas that require deeper understanding of metabolism, such as metabolic engineering and drug target identification. Our algorithm utilizes explicit atom tracking to identify linear metabolic pathways and then merges them together into branched metabolic pathways. We provide results on two well-characterized metabolic pathways that demonstrate that this new merging approach can efficiently find biologically relevant branched metabolic pathways with complex structures.}, keywords = {metabolic networks}, doi = {10.1007/978-3-642-20036-6_9}, author = {Heath, A. P. and Bennett, G. N. and Kavraki, Lydia E} }
@article{heath-bennett2010finding-metabolic-pathways, title = {Finding Metabolic Pathways Using Atom Tracking}, journal = {Bioinformatics}, volume = {26}, number = {12}, year = {2010}, pages = {1548-1555}, abstract = {Motivation: Finding novel or non-standard metabolic pathways, possibly spanning multiple species, has important applications in fields such as metabolic engineering, metabolic network analysis, and metabolic network reconstruction. Traditionally, this has been a manual process, but the large volume of metabolic data now available has created a need for computational tools to automatically identify biologically relevant pathways. Results: We present new algorithms for finding metabolic pathways, given a desired start and target compound, that conserve a given number of atoms by tracking the movement of atoms through metabolic networks containing thousands of compounds and reactions. First, we describe an algorithm that identifies linear pathways. We then present a new algorithm for finding branched metabolic pathways. Comparisons to known metabolic pathways demonstrate that atom tracking enables our algorithms to avoid many unrealistic connections, often found in previous approaches, and return biologically meaningful pathways. Our results also demonstrate the potential of the algorithms to find novel or non-standard pathways that may span multiple organisms. Availability: The software is freely available for academic use at: http://www.kavrakilab.org/atommetanet}, keywords = {metabolic networks}, doi = {10.1093/bioinformatics/btq223}, note = {PMID: 20421197, PMCID: PMC2881407}, author = {Heath, A. P. and Bennett, G. N. and Kavraki, Lydia E} }
@article{antunes2020-hla-arena, author = {Antunes, Dinler A. and Abella, Jayvee R. and Hall-Swan, Sarah and Devaurs, Didier and Conev, Anja and Moll, Mark and Liz\'{e}e, Gregory and Kavraki, Lydia E.}, title = {{HLA}-{A}rena: a customizable environment for the structural modeling and analysis of peptide-{HLA} complexes for cancer immunotherapy}, abstract = {PURPOSE: HLA protein receptors play a key role in cellular immunity. They bind intracellular peptides and display them for recognition by T-cell lymphocytes. Because T-cell activation is partially driven by structural features of these peptide-HLA complexes, their structural modeling and analysis are becoming central components of cancer immunotherapy projects. Unfortunately, this kind of analysis is limited by the small number of experimentally determined structures of peptide-HLA complexes. Overcoming this limitation requires developing novel computational methods to model and analyze peptide-HLA structures. METHODS: Here we describe a new platform for the structural modeling and analysis of peptide-HLA complexes, called HLA-Arena, which we have implemented using Jupyter Notebook and Docker. It is a customizable environment that facilitates the use of computational tools, such as APE-Gen and DINC, which we have previously applied to peptide-HLA complexes. By integrating other commonly used tools, such as MODELLER and MHCflurry, this environment includes support for diverse tasks in structural modeling, analysis, and visualization. RESULTS: To illustrate the capabilities of HLA-Arena, we describe 3 example workflows applied to peptide-HLA complexes. Leveraging the strengths of our tools, DINC and APE-Gen, the first 2 workflows show how to perform geometry prediction for peptide-HLA complexes and structure-based binding prediction, respectively. The third workflow presents an example of large-scale virtual screening of peptides for multiple HLA alleles. CONCLUSION: These workflows illustrate the potential benefits of HLA-Arena for the structural modeling and analysis of peptide-HLA complexes. Because HLA-Arena can easily be integrated within larger computational pipelines, we expect its potential impact to vastly increase. For instance, it could be used to conduct structural analyses for personalized cancer immunotherapy, neoantigen discovery, or vaccine development.}, journal = {JCO Clinical Cancer Informatics}, year = {2020}, volume = {4}, pages = {623--636}, keywords = {fundamentals of protein modeling, proteins and drugs, other biomedical computing}, doi = {10.1200/CCI.19.00123}, note = {PMID: 32667823, PMCID: 7397777}, month = jul }
@article{abella2020-frontiers-random-forest, author = {Abella, Jayvee R. and Antunes, Dinler A. and Clementi, Cecilia and Kavraki, Lydia E.}, title = {Large-scale structure-based prediction of stable peptide binding to Class I HLAs using random forests}, abstract = {Prediction of stable peptide binding to Class I HLAs is an important component for designing immunotherapies. While the best performing predictors are based on machine learning algorithms trained on peptide-HLA (pHLA) sequences, the use of structure for training predictors deserves further exploration. Given enough pHLA structures, a predictor based on the residue-residue interactions found in these structures has the potential to generalize for alleles with little or no experimental data. We have previously developed APE-Gen, a modeling approach able to produce pHLA structures in a scalable manner. In this work we use APE-Gen to model over 150,000 pHLA structures, the largest dataset of its kind, which were used to train a structure-based pan-allele model. We extract simple, homogenous features based on residue-residue distances between peptide and HLA, and build a random forest model for predicting stable pHLA binding. Our model achieves competitive AUROC values on leave-one-allele-out validation tests using significantly less data when compared to popular sequence-based methods. Additionally, our model offers an interpretation analysis that can reveal how the model composes the features to arrive at any given prediction. This interpretation analysis can be used to check if the model is in line with chemical intuition, and we showcase particular examples. Our work is a significant step towards using structure to achieve generalizable and more interpretable prediction for stable pHLA binding.}, keywords = {fundamentals of protein modeling, proteins and drugs, other biomedical computing}, doi = {10.3389/fimmu.2020.01583}, note = {PMID: 32793224, PMCID: PMC7387700}, journal = {Frontiers in Immunology}, year = {2020}, volume = {11}, number = {1583}, month = jul }
@article{antunes2017_dinc2, abstract = {Molecular docking is a standard computational approach to predict binding modes of protein-ligand complexes, by exploring alternative orientations and conformations of the ligand (i.e., by exploring ligand flexibility). Docking tools are largely used for virtual screening of small drug-like molecules, but their accuracy and efficiency greatly decays for ligands with more than 10 flexible bonds. This prevents a broader use of these tools to dock larger ligands such as peptides, which are molecules of growing interest in cancer research. To overcome this limitation, our group has previously proposed a meta-docking strategy, called DINC, to predict binding modes of large ligands. By incrementally docking overlapping fragments of a ligand, DINC allowed predicting binding modes of peptide-based inhibitors of transcription factors involved in cancer. Here we describe DINC 2.0, a revamped version of the DINC webserver with enhanced capabilities and a more user-friendly interface. DINC 2.0 allows docking ligands that were previously too challenging for DINC, such as peptides with more than 25 flexible bonds. The webserver is freely accessible at \url{http://dinc.kavrakilab.org}, together with additional documentation and video tutorials. Our team will provide continuous support for this tool and is working on extending its applicability to other challenging fields, such as personalized immunotherapy against cancer.}, keywords = {proteins and drugs, other biomedical computing}, author = {Antunes, Dinler A and Moll, Mark and Devaurs, Didier and Jackson, KR and Liz\'{e}e, Gregory and Kavraki, Lydia E}, title = {{DINC} 2.0: a new protein-peptide docking webserver using an incremental approach}, journal = {Cancer Research}, volume = {77}, number = {21}, pages = {e55-57}, year = {2017}, doi = {10.1158/0008-5472.CAN-17-0511}, note = {PMCID: PMC5679007, PMID: 29092940}, month = nov }
@article{heath-kavraki2009computational-challenges-in, title = {Computational Challenges in Systems Biology}, journal = {Computer Science Review}, volume = {3}, number = {1}, year = {2009}, pages = {1-17}, abstract = {Systems biology is a broad field that incorporates both computational and experimental approaches to provide a system level understanding of biological function. Initial forays into computational systems biology have focused on a variety of biological networks such as protein{\textendash}protein interaction, signaling, transcription and metabolic networks. In this review we will provide an overview of available data relevant to systems biology, properties of biological networks, algorithms to compare and align networks and simulation and modeling techniques. Looking towards the future, we will discuss work on integrating additional functional information with biological networks, such as three dimensional structures and the complex environment of the cell. Combining and understanding this information requires development of novel algorithms and data integration techniques and solving these difficult computational problems will advance both computational and biological research.}, keywords = {other biomedical computing}, doi = {10.1016/j.cosrev.2009.01.002}, author = {Heath, A. P. and Kavraki, Lydia E} }
@article{heath-balazsi2008bipolarity-of-saccharomyces, title = {Bipolarity of the saccharomyces cerevisiae genome}, journal = {International Conference on Bioinformatics and Biomedical Engineering (iCBBE)}, year = {2008}, pages = {330{\textendash}333}, abstract = {Accumulating evidence indicates that eukaryotic genes tend to belong in two distinct categories that we will call class I and class II. Class I genes do not contain a TATA box in their promoter, and have low expression variability both at the single cell level (in constant environment) and at the population level (in changing environmental conditions). In contrast, class II genes contain a TATA box in their promoter, and tend to have pronounced expression variability both at the single cell level (in constant environment) and at the population level (in changing environmental conditions). Here we show that the positioning and regulation of class I and class II genes is strikingly different in the large-scale transcriptional regulatory (TR) network of S. cerevisiae. We also show that class I and class II genes differ dramatically in several properties, including gene expression variability at diverse time scales and population sizes, mutational variance, gene essentiality and subcellular localization. This dichotomy might indicate that evolution placed different genes in different locations within the cell and within the TR network, according to some fundamental principles that govern cellular information processing and survival in a changing environment.}, keywords = {other biomedical computing}, doi = {10.1109/ICBBE.2008.84}, author = {Heath, A. P. and Bal{\'a}zsi, G. and Kavraki, Lydia E} }
@incollection{teodoro-kavraki2002pharmacology, title = {Pharmacology}, booktitle = {Handbook of Data Mining and Knowledge Discovery}, year = {2002}, month = jul, pages = {808-816}, publisher = {Oxford University Press}, keywords = {other biomedical computing}, author = {Teodoro, Miguel L. and Kavraki, Lydia E}, editor = {Kl\"osgen, W. and \.Zytkow, J.} }
@inproceedings{schweikard-tombropoulos1994treatment-planning-for, title = {Treatment Planning for a Radiosurgical System with General Kinematics}, booktitle = {Proceedings of the IEEE/RJS International Conference on Robotics and Automation (ICRA)}, year = {1994}, pages = {1764-1771}, publisher = {IEEE Press}, address = {San Diego, CA}, abstract = {In radiosurgery a beam of radiation is used as an ablative surgical instrument to destroy brain tumors. Treatment planning consists of computing a sequence of beam configurations for delivering a necrotic dose to the tumor, without damaging healthy tissue or particularly critical structures. In current systems, kinematic limitations severely constrain beam motion. This often results in inappropriate dose distributions. A new radiosurgical system has been implemented to overcome this disadvantage. In this system, a compact radiation source of high energy is moved by a 6-dof robotic arm. We describe algorithms for computing a motion with specified characteristics for this new system. Treatment plans used at test sites with earlier systems are compared to plans computed with the described algorithms. The experience reported shows that full kinematic flexibility combined with treatment planning algorithms allows for better protection of healthy tissue and higher dosage in tumors.}, keywords = {other biomedical computing, other robotics}, doi = {10.1109/ROBOT.1994.351344}, author = {Schweikard, A. and Tombropoulos, R. and Kavraki, Lydia E and Adler, J. and Latombe, Jean-Claude} }
@inproceedings{chamzas2020rep-learning, abstract = {Representation learning allows planning actions directly from raw observations. Variational Autoencoders (VAEs) and their modifications are often used to learn latent state representations from high-dimensional observations such as images of the scene. This approach uses the similarity between observations in the space of images as a proxy for estimating similarity between the underlying states of the system. We argue that, despite some successful implementations, this approach is not applicable in the general case where observations contain task-irrelevant factors of variation. We compare different methods to learn latent representations for a box stacking task and show that models with weak supervision such as Siamese networks with a simple contrastive loss produce more useful representations than traditionally used autoencoders for the final downstream manipulation task.}, author = {Chamzas, Constantinos and Lippi, Martina and Welle, Michael C. and Varava, Anastasiia and Marino, Alessandro and Kavraki, Lydia E. and Kragic, Danica}, booktitle = {NeurIPS, 3rd Robot Learning Workshop: Grounding Machine Learning Development in the Real World}, title = {State Representations in Robotics: Identifying Relevant Factors of Variation using Weak Supervision}, year = {2020}, month = dec, url = {http://www.robot-learning.ml/2020/}, keywords = {other robotics} }
@article{hernandez2019online-motion-planning-auvs, abstract = {We present an approach to endow an autonomous underwater vehicle (AUV) with the capabilities to move through unexplored environments. To do so, we propose a computational framework for planning feasible and safe paths. The framework allows the vehicle to incrementally build a map of the surroundings, while simultaneously (re)planning a feasible path to a specified goal. To accomplish this, the framework considers motion constraints to plan feasible 3D paths, i.e., those that meet the vehicle’s motion capabilities. It also incorporates a risk function to avoid navigating close to nearby obstacles. Furthermore, the framework makes use of two strategies to ensure meeting online computation limitations. The first one is to reuse the last best known solution to eliminate time-consuming pruning routines. The second one is to opportunistically check the states’ risk of collision. To evaluate the proposed approach, we use the Sparus II performing autonomous missions in different real-world scenarios. These experiments consist of simulated and in-water trials for different tasks. The conducted tasks include the exploration of challenging scenarios such as artificial marine structures, natural marine structures, and confined natural environments. All these applications allow us to extensively prove the efficacy of the presented approach, not only for constant-depth missions (2D), but, more importantly, for situations in which the vehicle must vary its depth (3D).}, author = {Hern{\'a}ndez, Juan David and Vidal, Eduard and Moll, Mark and Palomeras, Narc{\'i}s and Carreras, Marc and Kavraki, Lydia E.}, journal = {Journal of Field Robotics}, title = {Online Motion Planning for Unexplored Underwater Environments using Autonomous Underwater Vehicles}, year = {2019}, volume = {36}, issue = {2}, pages = {370--396}, doi = {10.1002/rob.21827}, keywords = {other robotics} }
@article{bohg2016big-data-on-robotics, author = {Bohg, Jeannette and Ciocarlie, Matei and Civera, Javier and Kavraki, Lydia E.}, title = {Big Data in Robotics}, journal = {Big Data}, month = dec, year = {2016}, volume = {4}, number = {4}, pages = {195-196}, doi = {10.1089/big.2016.29013.rob}, note = {PMID: 27992266}, keywords = {other robotics} }
@article{dantam2016unix, author = {Dantam, Neil T. and B{\o}ndergaard, Kim and Johansson, Mattias A. and Furuholm, Tobias and Kavraki, Lydia E.}, title = {Unix Philosophy and the Real World: Control Software for Humanoid Robots}, journal = {Frontiers in Robotics and Artificial Intelligence}, keywords = {other robotics}, month = mar, year = {2016}, volume = {3}, doi = {10.3389/frobt.2016.00006}, abstract = {Robot software combines the challenges of general purpose and real-time software, requiring complex logic and bounded resource use. Physical safety, particularly for dynamic systems such as humanoid robots, depends on correct software. General purpose computation has converged on unix-like operating systems -- standardized as POSIX, the Portable Operating System Interface -- for devices from cellular phones to supercomputers. The modular, multi-process design typical of POSIX applications is effective for building complex and reliable software. Absent from POSIX, however, is an interproccess communication mechanism that prioritizes newer data as typically desired for control of physical systems. We address this need in the Ach communication library which provides suitable semantics and performance for real-time robot control. Although initially designed for humanoid robots, Ach has broader applicability to complex mechatronic devices -- humanoid and otherwise -- that require real-time coupling of sensors, control, planning, and actuation. The initial user space implementation of Ach was limited in the ability to receive data from multiple sources. We remove this limitation by implementing Ach as a Linux kernel module, enabling Ach's high-performance and latest-message-favored semantics within conventional POSIX communication pipelines. We discuss how these POSIX interfaces and design principles apply to robot software, and we present a case study using the Ach kernel module for communication on the Baxter robot.} }
@inproceedings{hernandez2016planning-feasible-and-safe-paths, abstract = {We present a framework for planning collision-free and safe paths online for autonomous underwater vehicles (AUVs) in unknown environments. We build up on our previous work and propose an improved approach. While preserving its main modules (mapping, planning and mission handler), the framework now considers motion constraints to plan feasible paths, i.e., those that meet vehicle's motion capabilities. The new framework also incorporates a risk function to avoid navigating close to nearby obstacles, and reuses the last best known solution to eliminate time-consuming pruning routines. To evaluate this approach, we use the Sparus II AUV, a torpedo-shaped vehicle performing autonomous missions in a 2-dimensional workspace. We validate the framework's new features by solving tasks in both simulation and real-world in water trials and comparing results with our previous approach.}, author = {Hern{\'a}ndez, Juan David and Moll, Mark and Vidal Garcia, Eduard and Carreras, Marc and Kavraki, Lydia E.}, booktitle = {Proceedings of the {IEEE/RSJ} International Conference on Intelligent Robots and Systems}, title = {Planning Feasible and Safe Paths Online for Autonomous Underwater Vehicles in Unknown Environments}, year = {2016}, pages = {1313-1320}, keywords = {other robotics}, doi = {10.1109/IROS.2016.7759217} }
@article{kavraki-moll2016rss2014, author = {Kavraki, Lydia E. and Moll, Mark}, doi = {10.1177/0278364915608299}, journal = {International Journal of Robotics Research}, number = {1--3}, volume = {3--4}, title = {Editorial: Special Issue on the 2014 ``{R}obotics: {S}cience \& {S}ystems'' Conference}, year = {2016}, keywords = {other robotics} }
@proceedings{rss2015, title = {Robotics Science and Systems XI}, editor = {Kavraki, L. E. and Hsu, D. and Buchli, J.}, year = {2015}, isbn = {978-0-9923747-1-6}, keywords = {other robotics}, url = {http://www.roboticsproceedings.org/rss11/index.html} }
@inproceedings{kingston2015lc3, author = {Kingston, Zachary and Dantam, Neil and Kavraki, Lydia E.}, booktitle = {Proceedings of the IEEE-RAS 15th International Conference on Humanoid Robots (Humanoids)}, title = {Kinematically constrained workspace control via linear optimization}, year = {2015}, pages = {758--764}, abstract = {We present a method for Cartesian workspace control of a robot manipulator that enforces joint-level acceleration, velocity, and position constraints using linear optimization. This method is robust to kinematic singularities. On redundant manipulators, we avoid poor configurations near joint limits by including a maximum permissible velocity term to center each joint within its limits. Compared to the baseline Jacobian damped least-squares method of workspace control, this new approach honors kinematic limits, ensuring physically realizable control inputs and providing smoother motion of the robot. We demonstrate our method on simulated redundant and non-redundant manipulators and implement it on the physical 7-degree-of-freedom Baxter manipulator. We provide our control software under a permissive license.}, doi = {10.1109/HUMANOIDS.2015.7363455}, keywords = {other robotics} }
@article{kavraki-likhachev2015rss2014, author = {Kavraki, Lydia E. and Likhachev, Maxim}, doi = {10.1007/s10514-015-9482-8}, journal = {Autonomous Robots}, number = {3}, volume = {39}, title = {Editorial: Special Issue on the 2014 ``{R}obotics: {S}cience \& {S}ystems'' Conference}, year = {2015}, keywords = {other robotics} }
@inproceedings{voss-moll2015heuristic-approach-to, title = {A Heuristic Approach to Finding Diverse Short Paths}, booktitle = {IEEE International Conference on Robotics and Automation}, year = {2015}, pages = {4173--4179}, address = {Seattle, WA}, abstract = {We present an algorithm that seeks to find a set of diverse, short paths through a roadmap graph. The usefulness of a such a set is illustrated in robotic motion planning and routing applications wherein a precomputed roadmap of the environment is partially invalidated by some change, for example, relocation of obstacles or modification of the robot. Our algorithm employs the heuristic that configurations near each other are likely to be invalidated by the same change in the environment. To find short, diverse paths, the algorithm finds a detour that is the shortest path avoiding a selection of balls in the configuration space. Different collections of these balls, or simulated obstacles, yield different and diverse short paths. Paths may then be checked for validity as a cheap alternative to checking or reconstructing the entire roadmap. We describe a formal definition of path set diversity and several measures on which to evaluate our algorithm. We compare the speed and quality of our heuristic algorithm{\textquoteright}s results against an exact algorithm that computes the optimally shortest set of paths on the roadmap having a minimum diversity. We will show that, with a tolerable loss in path shortness, our algorithm produces equally diverse path sets orders of magnitude faster.}, keywords = {other robotics}, doi = {10.1109/ICRA.2015.7139774}, author = {Voss, Caleb and Moll, Mark and Kavraki, Lydia E} }
@proceedings{rss2014, title = {Robotics Science and Systems X}, editor = {Fox, D. and Kavraki, L. E. and Kurniawati, H.}, year = {2014}, isbn = {978-0-9923747-0-9}, keywords = {other robotics}, url = {http://www.roboticsproceedings.org/rss10/index.html} }
@article{moll-bordeaux2013software-for-project-based, title = {Software for Project-Based Learning of Robot Motion Planning}, journal = {Computer Science Education, Special Issue on Robotics in CS Education}, volume = {23}, number = {4}, year = {2013}, pages = {332{\textendash}348}, abstract = {Motion planning is a core problem in robotics concerned with finding feasible paths for a given robot. Motion planning algorithms perform a search in the high-dimensional continuous space of robot configurations and exemplify many of the core algorithmic concepts of search algorithms and associated data structures. Motion planning algorithms can be explained in a simplified two-dimensional setting, but this masks many of the subtleties and complexities of the underlying problem. We have developed software for Project-Based Learning of motion planning that enables deep learning. The projects that we have developed allow advanced undergraduate students and graduate students to reflect on the performance of existing textbook algorithms and their own variations on such algorithms. Formative assessment has been conducted at three institutions. The core of the software used for this teaching module is also used within the Robot Operating System (ROS), a widely adopted platform by the robotics research community. This allows for transfer of knowledge and skills to robotics research projects involving a large variety robot hardware platforms.}, keywords = {other robotics}, doi = {10.1080/08993408.2013.847167}, author = {Moll, Mark and Bordeaux, Janice and Kavraki, Lydia E} }
@article{sucan-moll2012open-motion-planning, title = {The Open Motion Planning Library}, journal = {IEEE Robotics \& Automation Magazine}, volume = {19}, year = {2012}, note = {http://ompl.kavrakilab.org}, month = dec, pages = {72-82}, abstract = {We describe the Open Motion Planning Library (OMPL), a new library for sampling-based motion planning, which contains implementations of many state-of-the-art planning algorithms. The library is designed in a way that allows the user to easily solve a variety of complex motion planning problems with minimal input. OMPL facilitates the addition of new motion planning algorithms and it can be conveniently interfaced with other software components. A simple graphical user interface (GUI) built on top of the library, a number of tutorials, demos and programming assignments have been designed to teach students about sampling-based motion planning. Finally, the library is also available for use through the Robot Operating System (ROS).}, keywords = {fundamentals of sampling-based motion planning, other robotics}, doi = {10.1109/MRA.2012.2205651}, author = {{\c S}ucan, Ioan A. and Moll, Mark and Kavraki, Lydia E} }
@inproceedings{grady-moll2011look-before-you, title = {Look Before You Leap: Predictive Sensing and Opportunistic Navigation}, booktitle = {Workshop on Progress and Open Problems in Motion Planning at the IEEE/RSJ International Conference on Intelligent Robots and Systems}, year = {2011}, month = sep, address = {San Francisco}, abstract = {This paper describes a novel method for identifying multiple targets with multiple robots in a partially known environment. Two main issues are addressed. The first relates to the use of motion planning algorithms to determine whether robots can reach {\textquoteleft}{\textquoteleft}good{\textquoteright}{\textquoteright} positions that offer the most informative measurements. The second concerns the use of predictive sensing to decide where sensor measurements should be taken. The problem is formulated similar to a next-best-view problem with differential constraints on the robots{\textquoteright} motion, with additional layers of complexity due to visual occlusions as well as navigational obstacles. We propose a new distributed sensing strategy that exploits the structure of image manifolds to predict the utility of the measurements at a given position. This information is encoded in a cost map that guides a motion planning algorithm. Coordination among robots is achieved by incorporating additional information in each robot{\textquoteright}s cost map. A range of simulations indicates that our approach outperforms current approaches and demonstrates the advantages of predictive sensing and accounting for reachability constraints.}, keywords = {other robotics}, author = {Grady, Devin K and Moll, Mark and Hegde, Chinmay and Sankaranarayanan, Aswin C. and Baraniuk, Richard G. and Kavraki, Lydia E} }
@inproceedings{moll-sucan2011teaching-motion-planning, title = {Teaching Motion Planning Concepts to Undergraduate Students}, booktitle = {IEEE Workshop on Advanced Robotics and its Social Impacts}, year = {2011}, abstract = {Motion planning is a central problem in robotics. Although it is an engaging topic for undergraduate students, it is difficult to teach, and as a result, the material is often only covered at an abstract level. Deep learning could be achieved by having students implement and test different algorithms. However, there is usually no time within a single class to have students completely implement several motion planning algorithms as they require the development of many lower-level data structures. We present an ongoing project to develop a teaching module for robotic motion planning centered around an integrated software environment. The module can be taught early in the undergraduate curriculum, after students have taken an introductory programming class.}, keywords = {other robotics}, doi = {10.1109/ARSO.2011.6301976}, author = {Moll, Mark and Sucan, Ioan Alexandru and Bordeaux, Janice and Kavraki, Lydia E} }
@article{moll-bordeaux2010teaching-robot-motion, title = {Teaching Robot Motion Planning}, journal = {Computers in Education (Special Issue on Novel Approaches to Robotics Education)}, volume = {20}, number = {3}, year = {2010}, pages = {50{\textendash}59}, abstract = {Robot motion planning is a fairly intuitive and engaging topic, yet it is difficult to teach. The material is taught in undergraduate and graduate robotics classes in computer science, electrical engineering, mechanical engineering and aeronautical engineering, but at an abstract level. Deep learning could be achieved by having students implement and test different motion planning strategies. However, it is practically impossible in the context of a single class to have undergraduates implement motion planning algorithms that are powerful and fun to use, even when the students have proficient programming skills. Due to lack of supporting educational material, students are often asked to implement simple (and uninteresting) motion planning algorithms from scratch, or access thousands of lines of code and just figure out how things work. We present an ongoing project to develop microworld software and a modeling curriculum that supports undergraduate acquisition of motion planning knowledge and tool use by computer science and engineering students. The goal is to open the field of motion planning and robotics to young and enthusiastic talent.}, keywords = {other robotics}, author = {Moll, Mark and Bordeaux, Janice and Kavraki, Lydia E}, url = {https://www.asee.org/papers-and-publications/publications/division-publications/computers-in-education-journal/volume-xx} }
@inproceedings{rusu-sucan2009real-time-perception-guided-motion, title = {Real-Time Perception-Guided Motion Planning for a Personal Robot}, booktitle = {IEEE/RSJ International Conference on Intelligent Robots and Systems}, year = {2009}, month = oct, pages = {4245-4252}, address = {St. Louis}, keywords = {other robotics}, doi = {10.1109/IROS.2009.5354396}, author = {Rusu, Radu Bogdan and Sucan, Ioan Alexandru and Gerkey, Brian P and Chitta, Sachin and Beetz, Michael and Kavraki, Lydia E} }
@incollection{tsianos-halperin2008robot-algorithms, title = {Robot Algorithms}, booktitle = {Algorithms and Theory of Computation Handbook}, volume = {2}, year = {2008}, publisher = {CRC Press}, edition = {Second}, chapter = {4}, address = {Boca Raton, FL}, keywords = {fundamentals of sampling-based motion planning, other robotics}, author = {Tsianos, Konstantinos I. and Halperin, D. and Kavraki, Lydia E and Latombe, Jean-Claude} }
@article{plaku-kavraki2007distributed-computation-of, title = {Distributed Computation of the KNN Graph for Large High-Dimensional Point Sets}, journal = {Journal of Parallel and Distributed Computing}, volume = {67}, number = {3}, year = {2007}, pages = {346--359}, abstract = {High-dimensional problems arising from robot motion planning, biology, data mining, and geographic information systems often require the computation of k nearest neighbor (knn) graphs. The knn graph of a data set is obtained by connecting each point to its k closest points. As the research in the above-mentioned fields progressively addresses problems of unprecedented complexity, the demand for computing knn graphs based on arbitrary distance metrics and large high-dimensional data sets increases, exceeding resources available to a single machine. In this work we efficiently distribute the computation of knn graphs for clusters of processors with message passing. Extensions to our distributed framework include the computation of graphs based on other proximity queries, such as approximate knn or range queries. Our experiments show nearly linear speedup with over one hundred processors and indicate that similar speedup can be obtained with several hundred processors.}, keywords = {other robotics}, doi = {10.1016/j.jpdc.2006.10.004}, note = {PMCID: PMC2764297, PMID: 19847318}, msid = {NIHMS18161}, author = {Plaku, E. and Kavraki, Lydia E} }
@inproceedings{plaku-bekris2007oops-for-motion, title = {{OOPS} for Motion Planning: An Online Open-source Programming System}, booktitle = {IEEE International Conference on Robotics and Automation (ICRA)}, year = {2007}, pages = {3711-3716}, address = {Rome, Italy}, abstract = {The success of sampling-based motion planners has resulted in a plethora of methods for improving planning components, such as sampling and connection strategies, local planners and collision checking primitives. Although this rapid progress indicates the importance of the motion planning problem and the maturity of the field, it also makes the evaluation of new methods time consuming. We propose that a systems approach is needed for the development and the experimental validation of new motion planners and/or components in existing motion planners. In this paper, we present the Online, Open-source, Programming System for Motion Planning (OOPSMP), a programming infrastructure with an open interface. OOPSMP provides implementations of various existing algorithms in a modular, object-oriented fashion that is easily extendable. The system is open-source, since a community-based effort better facilitates the development of a common infrastructure and is less prone to errors. We hope that researchers will contribute their optimized implementations of their methods and thus improve the quality of the code available for use. A dynamic web interface and a dynamic linking architecture at the programming level allows users to easily add new planning components, algorithms, benchmarks, and experiment with different parameters. The system allows the direct comparison of new contributions with existing approaches on the same hardware and programming infrastructure.}, keywords = {other robotics}, doi = {10.1109/ROBOT.2007.364047}, author = {Plaku, E. and Bekris, Kostas E. and Kavraki, Lydia E} }
@article{moll-kavraki2006path-planning-for, title = {Path Planning for Deformable Linear Objects}, journal = {IEEE Transactions on Robotics}, volume = {22}, number = {4}, year = {2006}, month = aug, pages = {625-636}, abstract = {We present a new approach to path planning for deformable linear (one-dimensional) objects such as flexible wires. We introduce a method for efficiently computing stable configurations of a wire subject to manipulation constraints. These configurations correspond to minimal-energy curves. By restricting the planner to minimal-energy curves, the execution of a path becomes easier. Our curve representation is adaptive in the sense that the number of parameters automatically varies with the complexity of the underlying curve. We introduce a planner that computes paths from one minimal-energy curve to another such that all intermediate curves are also minimal-energy curves. This planner can be used as a powerful local planner in a sampling-based roadmap method. This makes it possible to compute a roadmap of the entire {\textquotedblleft}shape space,{\textquotedblright} which is not possible with previous approaches. Using a simplified model for obstacles, we can find minimal-energy curves of fixed length that pass through specified tangents at given control points. Our work has applications in cable routing, and motion planning for surgical suturing and snake-like robots.}, keywords = {fundamentals of sampling-based motion planning, other robotics}, doi = {10.1109/TRO.2006.878933}, author = {Moll, Mark and Kavraki, Lydia E} }
@incollection{bekris-argyros2006exploiting-panoramic-vision, title = {Exploiting Panoramic Vision for Angle-Based Robot Navigation}, booktitle = {Lecture Notes in Computer Science, Vol. 33}, year = {2006}, pages = {229-251}, publisher = {Springer}, abstract = {Omni-directional vision allows for the development of techniques for mobile robot navigation that have minimum perceptual requirements. In this work, we focus on robot navigation algorithms that do not require range information or metric maps of the environment. More specifically, we present a homing strategy that enables a robot to return to its home position after executing a long path. The proposed strategy relies on measuring the angle between pairs of features extracted from panoramic images, which can be achieved accurately and robustly. In the heart of the proposed homing strategy lies a novel, local control law that enables a robot to reach any position on the plane by exploiting the bearings of at least three landmarks of unknown position, without making assumptions regarding the robot{\textquoteright}s orientation and without making use of a compass. This control law is the result of the unification of two other local control laws which guide the robot by monitoring the bearing of landmarks and which are able to reach complementary sets of goal positions on the plane. Long-range homing is then realized through the systematic application of the unified control law between automatically extracted milestone positions connecting the robot{\textquoteright}s current position to the home position. Experimental results, conducted both in a simulated environment and on a robotic platform equipped with a panoramic camera validate the employed local control laws as well as the overall homing strategy. Moreover, they show that panoramic vision can assist in simplifying the perceptual processes required to support robust and accurate homing behaviors.}, keywords = {fundamentals of sampling-based motion planning, other robotics}, author = {Bekris, Kostas E. and Argyros, A. A. and Kavraki, Lydia E} }
@inproceedings{moll-kavraki2005path-planning-for, title = {Path Planning for Variable Resolution Minimal-Energy Curves of Constant Length}, booktitle = {International Conference on Robotics and Automation}, year = {2005}, month = apr, pages = {2143-2147}, publisher = {IEEE Press}, address = {Barcelona, Spain}, abstract = {We present a new approach to path planning for flexible wires. We introduce a method for computing stable configurations of a wire subject to manipulation constraints. These configurations correspond to minimal-energy curves. The representation is adaptive in the sense that the number of parameters automatically varies with the complexity of the underlying curve. We introduce a planner that computes paths from one minimal-energy curve to another such that all intermediate curves are also minimal-energy curves. Using a simplified model for obstacles, we can find minimal-energy curves of fixed length that pass through specified tangents at given control points. Our work has applications in motion planning for surgical suturing and snake-like robots.}, keywords = {other robotics}, doi = {10.1109/ROBOT.2005.1570428}, author = {Moll, Mark and Kavraki, Lydia E} }
@article{argyros-bekris2005robot-homing-by, title = {Robot Homing by Exploiting Panoramic Vision}, journal = {Autonomous Robots}, volume = {19}, number = {1}, year = {2005}, pages = {7-25}, abstract = {We propose a novel, vision-based method for robot homing, the problem of computing a route so that a robot can return to its initial home position after the execution of an arbitrary prior path. The method assumes that the robot tracks visual features in panoramic views of the environment that it acquires as it moves. By exploiting only angular information regarding the tracked features, a local control strategy moves the robot between two positions, provided that there are at least three features that can be matched in the panoramas acquired at these positions. The strategy is successful when certain geometric constraints on the configuration of the two positions relative to the features are fulfilled. In order to achieve long-range homing, the features}, keywords = {other robotics}, doi = {10.1007/s10514-005-0603-7}, author = {Argyros, A. A. and Bekris, Kostas E. and Orphanoudakis, S. C. and Kavraki, Lydia E} }
@inproceedings{bekris-argyros2004angle-based-methods-for, title = {Angle-Based Methods for Mobile Robot Navigation: Reaching the Entire Plane}, booktitle = {Proceedings of The IEEE International Conference on Robotics and Automation (ICRA)}, year = {2004}, month = apr, pages = {2373--2378}, publisher = {IEEE Press}, address = {New Orleans, LA}, abstract = {Popular approaches for mobile robot navigation involve range information and metric maps of the workspace. For many sensors, however, such as cameras and wireless hardware, the angle between two extracted features or beacons is easier to measure. With these sensors{\textquoteright} features in mind, this paper initially presents a control law, which allows a robot equipped with an omni-directional sensor to reach a subset of the plane by monitoring the angles of only three landmarks. By analyzing the properties of this law, a second law has been developed that reaches the complementary set of points. The two methods are then combined in a path planning framework that reaches any possible goal configuration in a planar obstacle-free workspace with three landmarks. The proposed framework could be combined with other techniques, such as obstacle avoidance and topological maps, to improve the efficiency of autonomous navigation. Experiments have been conducted on a robotic platform equipped with a panoramic camera that exhibits the effectiveness and accuracy of the proposed techniques. This work provides evidence that navigational tasks can be performed using only a small number of primitive sensor cues and without the explicit computation of range information.}, keywords = {other robotics}, doi = {10.1109/ROBOT.2004.1307416}, author = {Bekris, Kostas E. and Argyros, A. A. and Kavraki, Lydia E} }
@inproceedings{moll-kavraki2004path-planning-for, title = {Path Planning for Minimal Energy Curves of Constant Length}, booktitle = {Proceedings of The IEEE International Conference on}, year = {2004}, month = apr, pages = {2826-2831}, publisher = {IEEE Press}, address = {New Orleans, LA}, abstract = {In this paper we present a new path planning technique for a flexible wire. We first introduce a new parametrization designed to represent low-energy configurations. Based on this parametrization we can find curves that satisfy endpoint constraints. Next, we present three different techniques for minimizing energy within the self-motion manifold of the curve. We introduce a local planner to find smooth minimal energy deformations for these curves that can be used by a general path planning algorithm. Using a simplified model for obstacles, we can find minimal energy curves of fixed length that pass through specified tangents at given control points. Finally, we show that the parametrization introduced in this paper is a good approximation of true minimal energy curves. Our work has applications in surgical suturing and snake-like robots.}, keywords = {other robotics}, doi = {10.1109/ROBOT.2004.1307489}, author = {Moll, Mark and Kavraki, Lydia E} }
@incollection{ladd-kavraki2004motion-planning-for, title = {Motion Planning for Knot Untangling}, booktitle = {Algorithmic Foundations of Robotics V}, year = {2004}, pages = {7-23}, publisher = {Springer Tracks in Advanced Robotics, Springer Verlag, STAR 7}, abstract = {This paper investigates the application of motion planning techniques to the untangling of mathematical knots. Knot untangling can be viewed as a high-dimensional planning problem in reparameterizable configuration spaces. In the past, simulated annealing and other energy minimization methods have been used to find knot untangling paths. We develop a probabilistic planner that is capable of untangling knots described by over four hundred variables and known difficult benchmarks in this area more quickly than has been achieved with minimization in the literature. The use of motion planning techniques was critical for the untangling. Our planner defines local goals and makes combined use of energy minimization and randomized tree-based planning. We also show how to produce candidates with minimal number of segments for a given knot. Finally, we discuss some possible applications of our untangling planner in computational topology, in the study of DNA rings and protein folding and for planning with flexible robots.}, keywords = {other robotics}, doi = {10.1007/b80173}, author = {Ladd, A. M. and Kavraki, Lydia E} }
@article{ladd-kavraki2004using-motion-planning, title = {Using Motion Planning for Knot Untangling}, journal = {International Journal of Robotics Research}, volume = {23}, number = {7-8}, year = {2004}, pages = {797-808}, abstract = {In this paper we investigate the application of motion planning techniques to the untangling of mathematical knots. Knot untangling can be viewed as a high-dimensional planning problem in reparametrizable configuration spaces. In the past, simulated annealing and other energy minimization methods have been used to find knot untangling paths. We have developed a probabilistic planner that is capable of untangling knots described by over 400 variables. We have tested on known difficult benchmarks in this area and untangled them more quickly than has been achieved with minimization in the literature. In this work, the use of motion planning techniques is critical for the untangling. Our planner defines local goals and makes combined use of energy minimization and randomized tree-based planning. We also show how to produce candidates with a minimal number of segments for a given knot. The planner developed in this work is novel in that it is used to study issues arising in practical motion planning for high-dimensional and reparametrizable geometry. The use of energy methods, local goals and tree-based expansion is also novel and may suggest solutions in other planning applications. Finally, we discuss some possible applications of our untangling planner in computational topology, in the study of DNA rings and protein folding and for planning with flexible robots.}, keywords = {other robotics}, doi = {10.1177/0278364904045469}, author = {Ladd, A. M. and Kavraki, Lydia E} }
@inproceedings{phillips-ladd2002simulated-knot-tying, title = {Simulated Knot Tying}, booktitle = {Proceedings of The 2002 IEEE International Conference on Robotics and Automation (ICRA 2002)}, year = {2002}, month = may, pages = {841-846}, publisher = {IEEE Press}, address = {Washington, DC}, abstract = {Applications such as suturing in medical simulations require the modeling of knot tying in physically realistic rope. The paper describes the design and implementation of such a system. Our model uses a spline of linear springs, adaptive subdivision and a dynamics simulation. Collisions are discrete event simulated and follow the impulse model. Although some care must be taken to maintain stable knots, we demonstrate our simple model is sufficient for this task. In particular, we do not use friction or explicit constraints to maintain the knot. As examples, we tie an overhand knot and a reef knot.}, keywords = {other robotics}, doi = {10.1109/ROBOT.2002.1013462}, author = {Phillips, Jeff M. and Ladd, A. M. and Kavraki, Lydia E} }
@inproceedings{sudsang-kavraki2001part-orientation-with, title = {Part Orientation with a Force Field: Orienting Multiple Shapes using a Single Field}, booktitle = {Proceedings of The 2001 IEEE/RJS International Conference on Intelligent Robots and Systems (IROS 2001)}, volume = {1}, year = {2001}, month = nov, pages = {208-213}, publisher = {IEEE Press}, abstract = {In automated assembly, before parts can be put together, they often have to be appropriately oriented and positioned. The device performing this task is generally referred to as a part feeder. A new class of devices for non-prehensible distributed manipulation, such as MEMS actuator arrays, vibrating plates, etc., provides an alternative to traditional mechanical platforms for part feeding. These devices can be abstracted as programmable vector fields. Manipulation plans for these devices can therefore be considered as strategies for applying a sequence of fields to bring parts to some desired configurations. Typically, to uniquely orient and position a part, several fields have to be sequentially employed. In previous work (2001), we have shown that this objective can be accomplished using a single field. The work characterizes such a field for a given part. In this paper, we discover another interesting property of the field. In particular, we show that for a finite set of parts (with different shapes), we can specify a single field that can uniquely orient and position every part in the set. A force field device implementing this field therefore may be used as a part feeder for every part in the set without any reconfiguration.}, keywords = {other robotics}, doi = {10.1109/IROS.2001.973360}, author = {Sudsang, A. and Kavraki, Lydia E} }
@inproceedings{sudsang-kavraki2001geometric-approach-to, title = {A Geometric Approach to Designing a Programmable Force Field with a Unique Stable Equilibrium for Parts in the Plane}, booktitle = {Proceedings of The 2001 IEEE International Conference on Robotics and Automation (ICRA 2001)}, volume = {2}, year = {2001}, note = {This paper was a finalist for best conference paper award}, month = may, pages = {1079-1085}, publisher = {IEEE Press}, address = {Seoul, Korea}, abstract = {In automated assembly, before parts can be put together, they often have to be appropriately oriented and positioned. The device performing this task is generally referred to as a part feeder. A new class of devices for non-prehensile distributed manipulation, such as MEMS actuator arrays, vibrating plates, etc., provide an alternative to traditional mechanical platforms for part feeding. These devices can be abstracted as programmable vector fields. Manipulation plans for these devices can therefore be considered as strategies for applying a sequence of fields to bring parts to some desired configurations. Typically, to uniquely orient and position a part, several fields have to be sequentially employed. Previously, it has been proven that there exists a combination of the unit radial field and a constant field that induces a unique stable equilibrium for almost any part. However, that work focuses mainly on an existential proof and fails to address how to compute the field for a given part. We propose a radically different field with a proof confirming that the field induces a unique stable equilibrium for almost any part. This proof leads us to a method for computing a single field for orienting a given part, together with the corresponding stable equilibrium configuration of the part.}, keywords = {other robotics}, doi = {10.1109/ROBOT.2001.932737}, author = {Sudsang, A. and Kavraki, Lydia E} }
@article{lamiraux-kavraki2001planning-paths-for, title = {Planning Paths for Elastic Objects under Manipulation Constraints}, journal = {International Journal of Robotics Research}, volume = {20}, number = {3}, year = {2001}, pages = {188-208}, keywords = {other robotics}, doi = {10.1177/02783640122067354}, author = {Lamiraux, F. and Kavraki, Lydia E} }
@article{lamiraux-kavraki2001positioning-of-symmetric, title = {Positioning of Symmetric and Non-Symmetric Parts Using Radial and Constant Fields: Computation of All Equilibrium Configurations}, journal = {International Journal of Robotics Research}, volume = {20}, number = {8}, year = {2001}, pages = {635-659}, abstract = {Programmable force fields have been used as an abstraction to represent a whole new class of devices that have been proposed for part manipulation. The general idea behind these devices is that a force field is implemented in a plane upon which the part is placed. The forces and torques exerted on the contact surface of the part translate and rotate the part. Manipulation plans for these devices can therefore be considered as strategies for applying a sequence of force fields to bring parts to some desired configuration. Instances of these novel devices are currently implemented using microelectromechanical systems technology, small airjets, vibration, and small motors. Manipulation in this case is sensorless and nonprehensile and promises to address the handling of very small or very fragile parts, such as electronics components, that cannot be handled with conventional pick-and-place robotics techniques. In this paper, the authors consider the problem of bringing a part to a stable equilibrium configuration using force fields. The authors study the combination of a unit radial field with a small constant field. A part placed on the radial field moves toward the origin of the radial field but cannot be oriented due to symmetry. Perturbing the radial field with a constant force field breaks the symmetry and gives rise to a finite number of equilibria. Under certain conditions, there is a unique stable equilibrium configuration. For the case in which these conditions are not fulfilled, the authors provide a comprehensive and unified analysis of the problem that leads to an algorithm to compute all stable equilibrium configurations. The paper contains a detailed discussion on how to implement the algorithm for any part. In the analysis, the authors make extensive use of potential fields. Using the theory of potential fields, the stable equilibrium configurations of a part are equivalent to the local minima of a scalar function. The work presented in this paper leads to the design of a new generation of efficient, open-loop part feeders that can bring a part to a desired orientation from any initial orientation without the need of sensing or a clock.}, keywords = {other robotics}, doi = {10.1177/02783640122067589}, author = {Lamiraux, F. and Kavraki, Lydia E} }
@inproceedings{lamiraux-kavraki2001positioning-symmetric-and, title = {Positioning Symmetric and Non-Symmetric Parts using Radial and Constant Force Fields}, booktitle = {Robotics: New Directions}, year = {2001}, note = {Book contains the proceedings of the International Workshop on the Algorithmic Foundations of Robotics (WAFR), Dartmouth, March 2000}, pages = {37-50}, publisher = {A K Peters}, address = {Natick, MA}, keywords = {other robotics}, author = {Lamiraux, F. and Kavraki, Lydia E} }
@inproceedings{luo-kavraki2000part-assembly-using, title = {Part Assembly Using Static and Dynamic Force Fields}, booktitle = {Proceedings of The IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS)}, volume = {2}, year = {2000}, month = nov, pages = {1468-1474}, publisher = {IEEE Press}, abstract = {Part assembly is an important goal of part manipulation. Among other techniques, programmable force fields have been introduced for part manipulation. For part assembly, more than one part needs to be manipulated. This can create problems since there can be interactions between the parts such as impact and friction. Modern technology is beginning to provide the means to control the magnitude and frequency of each actuator of the implemented force field. Thus dynamic and localized force fields can be used for part manipulation. This paper presents a novel strategy to assemble two parts with a sequence of static and dynamic programmable force fields. The strategy involves some initial sensing. Uncertainties occurring in the motion of the parts are taken into account to make the proposed strategy more robust.}, keywords = {other robotics}, doi = {10.1109/IROS.2000.893227}, author = {Luo, J. and Kavraki, Lydia E} }
@inproceedings{brock-kavraki2000towards-real-time-motion, title = {Towards Real-Time Motion Planning in High Dimensional Spaces}, booktitle = {Proceedings of The International Symposium on Robotics and Automation (ISRA)}, year = {2000}, month = nov, address = {Monterey, Mexico}, keywords = {other robotics}, author = {Brock, Oliver and Kavraki, Lydia E} }
@inproceedings{anshelevich-owens2000deformable-volumes-in, title = {Deformable Volumes in Path Planning Applications}, booktitle = {Proceedings of The IEEE International Conference on Robotics and Automation (ICRA)}, volume = {3}, year = {2000}, month = apr, pages = {2290-2295}, publisher = {IEEE Press}, address = {San Fransisco, CA}, abstract = {This paper addresses the problem of path planning for a class of deformable volumes under fairly general manipulation constraints. The underlying geometric model for the volume is provided by a mass-spring representation. It is augmented by a realistic mechanical model. The latter permits the computation of the shape of the considered object with respect to the grasping constraints by minimizing the energy function of the deformation of the object. Previous research in planning for deformable objects considered the case of elastic plates and proposed a randomized framework for planning paths for plates under manipulation constraints. The present paper modifies and extends the previously proposed framework to handle simple volumes. Our planner builds a roadmap in the configuration space. The nodes of the roadmap are equilibrium configurations of the considered volume under the manipulation constraints, while its edges correspond to quasi-static equilibrium paths. Paths are found by searching the roadmap. We present experimental results that illustrate our approach}, keywords = {other robotics}, doi = {10.1109/ROBOT.2000.846368}, author = {Anshelevich, E. and Owens, S. and Lamiraux, F. and Kavraki, Lydia E} }
@inproceedings{lamiraux-kavraki2000positioning-and-orienting, title = {Positioning and Orienting a Class of Symmetric Parts Using a Combination of a Unit-Radial and a Constant Force Fields}, booktitle = {Proceedings of The 2000 IEEE International Conference on Robotics and Automation (ICRA 2000)}, volume = {1}, year = {2000}, month = apr, pages = {178--183}, publisher = {IEEE press}, address = {San Fransisco, CA}, abstract = {Part positioning and orientation is a key issue in manufacturing. Extensive recent work has investigated a series of force fields for part positioning and orientation. Typically, a strategy that brings a part to a unique equilibrium consists of several force fields that are employed in sequence. Bohringer and Donald conjectured a few years ago that the combination of a unit radial field with a constant field would give rise to a unique equilibrium. Such a field is extremely interesting as it positions and orients parts without the need of sensing or a clock. We (2000) have proved this conjecture for nonsymmetric parts. In this paper, we focus our attention on symmetric parts and show that some of them can be uniquely positioned and oriented using the same field. Our work further explores the capabilities and limits of force fields and provides additional evidence that force fields are a powerful tool for parts manipulation.}, keywords = {other robotics}, doi = {10.1109/ROBOT.2000.844056}, author = {Lamiraux, F. and Kavraki, Lydia E} }
@incollection{bohringer-donald2000distributed-universal-device, title = {A Distributed, Universal Device for Planar Parts Feeding: Unique Part Orientation in Programmable Vector Fields}, booktitle = {Distributed Manipulation}, year = {2000}, pages = {1-29}, publisher = {Kluwer Academic Publishers}, keywords = {other robotics}, author = {Bohringer, K.-F. and Donald, B. R. and Kavraki, Lydia E and Lamiraux, F.} }
@article{bohringer-donald2000part-orientation-with, title = {Part Orientation with One or Two Stable Equilibria Using Programmable Vector Fields}, journal = {IEEE Transactions on Robotics and Automation}, volume = {16}, number = {2}, year = {2000}, pages = {157-170}, keywords = {other robotics}, doi = {10.1109/70.843172}, author = {Bohringer, K.-F. and Donald, B. R. and Kavraki, Lydia E and Lamiraux, F.} }
@inproceedings{lamiraux-kavraki1999path-planning-for, title = {Path Planning for Elastic Plates Under Manipulation}, booktitle = {Proceedings of The IEEE International Conference on Robotics and Automation (ICRA)}, volume = {1}, year = {1999}, month = may, pages = {151-156}, publisher = {IEEE Press}, address = {Detroit, MI}, keywords = {other robotics}, doi = {10.1109/ROBOT.1999.769951}, author = {Lamiraux, F. and Kavraki, Lydia E} }
@incollection{bohringer-donald1999single-universal-force, title = {A Single Universal Force Field can Uniquely Orient Non-Symmetric Parts}, booktitle = {Robotics Research: The 9th International Symposium}, year = {1999}, pages = {395-402}, publisher = {Springer}, keywords = {other robotics}, author = {Bohringer, K.-F. and Donald, B. R. and Kavraki, Lydia E and Lamiraux, F.} }
@inproceedings{holleman-kavraki1998planning-paths-for, title = {Planning Paths for a Flexible Surface Patch}, booktitle = {Proceedings of The IEEE International Conference on Robotics and Automation (ICRA)}, volume = {1}, year = {1998}, pages = {21-26}, publisher = {IEEE Press}, address = {Leuven, Belgium}, abstract = {This paper presents a probabilistic planner capable of finding paths for a flexible surface patch. The planner is based on the probabilistic roadmap approach to path planning while the surface patch is modeled as a low degree Bezier surface. We assume that we are dealing with an elastic part and define an approximate energy model for the part. The energy function penalizes excessive shear and bending of the part and we assume that low-energy configurations correspond to reversible elastic deformations of the part. The planner captures the connectivity of a space by building a roadmap, a network of simple paths connecting configurations selected in the space using randomized techniques. We report on the implementation of our planner and show experimental results with examples where the surface patch is required to move through a small hole in its workspace. Our work is a first step towards considering the physical properties of parts when planning paths.}, keywords = {other robotics}, doi = {10.1109/ROBOT.1998.676243}, author = {Holleman, C. and Kavraki, Lydia E and Warren, J.} }
@inproceedings{kavraki-lamiraux1998towards-planning-for, title = {Towards Planning for Elastic Objects}, booktitle = {Robotics: The Algorithmic Perspective}, year = {1998}, note = {Proceedings of the Third Workshop on the Algorithmic Foundations of Robotics (WAFR), Houston, TX, 1998}, pages = {313-325}, publisher = {A.K. Peters}, address = {Natick, MA}, keywords = {other robotics}, author = {Kavraki, Lydia E and Lamiraux, F. and Holleman, C.} }
@inproceedings{kavraki1997part-orientation-with, title = {Part Orientation with Programmable Vector Fields: Two Stable Equilibria for Most Parts}, booktitle = {Proceedings of The International Conference on Robotics and Automation (ICRA)}, volume = {3}, year = {1997}, month = apr, pages = {2446-2452}, publisher = {IEEE Press}, address = {Albuquerque, NM}, abstract = {Part manipulation is an important but also time-consuming operation in industrial automation. Recent work explores alternative solutions to the mechanical parts feeders which have been traditionally used to sort and orient parts for assembly. One of the proposed alternatives is the use of programmable vector fields. The fields are realized on a plane on which the part is placed. The forces exerted on the part{\textquoteright}s contact surface translate and rotate the part to an equilibrium orientation. Certain vector fields can be implemented in the microscale with actuator arrays and in the macroscale with transversely vibrating plates. Although current technology is still limited, the dexterity that programmable vector fields offer has prompted researchers to further explore their capabilities. This paper presents a vector field that can simultaneously orient and pose most parts into two stable equilibrium configurations. The equilibrium configurations are easily computed a priori given the part to be oriented. Our analysis makes no assumptions about the shape of the part or its connectivity except that it moves as a rigid body. The proposed vector field offers the great advantage of stability of the equilibrium configurations under small perturbations of the part which is key for the orientation of toleranced parts.}, keywords = {other robotics}, doi = {10.1109/ROBOT.1997.619328}, author = {Kavraki, Lydia E} }
@incollection{halperin-kavraki1997robotics, title = {Robotics}, booktitle = {Handbook of Discrete and Computational Geometry}, year = {1997}, pages = {755-779}, publisher = {CRC Press}, address = {Boca Raton, NY}, keywords = {other robotics}, author = {Halperin, D. and Kavraki, Lydia E and Latombe, Jean-Claude} }
@article{kavraki1995computation-of-configuration, title = {Computation of Configuration Space Obstacles Using the Fast {F}ourier Transform}, journal = {IEEE Transactions on Robotics and Automation}, volume = {11}, number = {3}, year = {1995}, pages = {408-413}, abstract = {This paper presents a new method for computing the configuration-space map of obstacles that is used in motion-planning algorithms. The method derives from the observation that, when the robot is a rigid object that can only translate, the configuration space is a convolution of the workspace and the robot. This convolution is computed with the use of the fast Fourier transform (FFT) algorithm. The method is particularly promising for workspaces with many and/or complicated obstacles, or when the shape of the robot is not simple. It is an inherently parallel method that can significantly benefit from existing experience and hardware on the FFT.}, keywords = {other robotics}, doi = {10.1109/70.388783}, author = {Kavraki, Lydia E} }
@techreport{kavraki1995on-number-of, title = {On the Number of Equilibrium Placements of Mass Distributions in Elliptic Potential Fields}, number = {1559}, year = {1995}, institution = {Computer Science Department, Stanford University}, keywords = {other robotics}, author = {Kavraki, Lydia E} }
@article{kavraki-kolountzakis1995partitioning-assembly-into, title = {Partitioning an Assembly into Connected Parts is NP-hard}, journal = {Information Processing Letters}, volume = {55}, year = {1995}, pages = {159-165}, keywords = {other robotics}, doi = {10.1016/0020-0190(95)00083-O}, author = {Kavraki, Lydia E and Kolountzakis, M. N.} }
@article{wilson-kavraki1995two-handed-assembly-sequencing, title = {Two-Handed Assembly Sequencing}, journal = {International Journal of Robotics Research}, volume = {14}, number = {4}, year = {1995}, pages = {335-350}, abstract = {This article considers the computational complexity of automat ically determining assembly sequences for mechanical products. Specifically, we address the partitioning problem: given an assembly of rigid parts, identify a proper subassembly that can be removed as a rigid object without disturbing the rest of the assembly. We examine the complexity of the partition ing problem under various types of relative motions allowed for the subassemblies. We show that when arbitrary motions are allowed to separate the two subassemblies, partitioning is NP-complete. We then describe a general framework for reasoning about assembly motions called the interference diagram. In its most general form the interference diagram yields an exponential- time algorithm to partition an assembly. However, two special cases of the interference diagram studied in this article yield polynomial-time sequencing algorithms. The first case occurs when assembly motions are restricted to single translations. The second case considers infinitesimal rigid motions in translation and rotation and yields a superset of all feasible partitionings. These two algorithms have important practical applications in assembly planning.}, doi = {10.1177/027836499501400403}, author = {Wilson, R. H. and Kavraki, Lydia E and Latombe, Jean-Claude and Lozano-Perez, Tomas}, keywords = {other robotics} }
@inproceedings{schweikard-tombropoulos1994treatment-planning-for, title = {Treatment Planning for a Radiosurgical System with General Kinematics}, booktitle = {Proceedings of the IEEE/RJS International Conference on Robotics and Automation (ICRA)}, year = {1994}, pages = {1764-1771}, publisher = {IEEE Press}, address = {San Diego, CA}, abstract = {In radiosurgery a beam of radiation is used as an ablative surgical instrument to destroy brain tumors. Treatment planning consists of computing a sequence of beam configurations for delivering a necrotic dose to the tumor, without damaging healthy tissue or particularly critical structures. In current systems, kinematic limitations severely constrain beam motion. This often results in inappropriate dose distributions. A new radiosurgical system has been implemented to overcome this disadvantage. In this system, a compact radiation source of high energy is moved by a 6-dof robotic arm. We describe algorithms for computing a motion with specified characteristics for this new system. Treatment plans used at test sites with earlier systems are compared to plans computed with the described algorithms. The experience reported shows that full kinematic flexibility combined with treatment planning algorithms allows for better protection of healthy tissue and higher dosage in tumors.}, keywords = {other biomedical computing, other robotics}, doi = {10.1109/ROBOT.1994.351344}, author = {Schweikard, A. and Tombropoulos, R. and Kavraki, Lydia E and Adler, J. and Latombe, Jean-Claude} }
@inproceedings{kavraki1993computation-of-configuration-space, title = {Computation of configuration-space obstacles using the fast {F}ourier transform}, booktitle = {IEEE International Conference on Robotics and Automation}, volume = {3}, year = {1993}, month = may, pages = {255--261}, abstract = {A method is proposed for computing the configuration-space map of obstacles. The map is used in motion-planning algorithms. The method derives from the observation that, when the robot is a rigid object that can only translate, the configuration space is a convolution of the workspace and the robot. It makes use of the fast Fourier transform (FFT) algorithm to compute this convolution. The method is particularly promising for workspaces with many and/or complicated obstacles, or when the shape of the robot is not simple. It is an inherently parallel method, and it can significantly benefit from existing experience and hardware on the FFT.}, keywords = {other robotics}, doi = {10.1109/ROBOT.1993.292185}, author = {Kavraki, Lydia E} }
@article{kavraki-latombe1993on-complexity-of, title = {On the Complexity of Assembly Partitioning}, journal = {Information Processing Letters}, volume = {48}, number = {5}, year = {1993}, pages = {229-235}, abstract = {This paper studies the complexity of the assembly partitioning problem in the plane: given a collection of non-overlapping polygons, decide if there is a proper subcollection of them that can be removed as a rigid body without colliding with or disturbing the other parts of the assembly. It is shown that assembly partitioning is NP-complete. The result extends to several interesting variants of the problem.}, keywords = {other robotics}, doi = {10.1016/0020-0190(93)90085-N}, author = {Kavraki, Lydia E and Latombe, Jean-Claude and Wilson, R. H.} }
@inproceedings{bansal2022-synthesis, author = {Bansal, Suguman and Kavraki, Lydia E. and Vardi, Moshe V. and Wells, Andrew}, title = {Synthesis from Satisficing and Temporal Goals}, booktitle = {Proceedings of the AAAI Conference on Artifical Intelligence}, publisher = {AAAI}, year = {2022}, abstract = {Reactive synthesis from high-level specifications that combine hard constraints expressed in Linear Temporal Logic (LTL) with soft constraints expressed by discounted-sum (DS) rewards has applications in planning and reinforcement learning. An existing approach combines techniques from LTL synthesis with optimization for the DS rewards but has failed to yield a sound algorithm. An alternative approach combining LTL synthesis with satisficing DS rewards (rewards that achieve a threshold) is sound and complete for integer discount factors, but, in practice, a fractional discount factor is desired. This work extends the existing satisficing approach, presenting the first sound algorithm for synthesis from LTL and DS rewards with fractional discount factors. The utility of our algorithm is demonstrated on robotic planning domains.}, keywords = {planning from high-level specifications} }
@article{wells2020-ltlf, title = {LTLf Synthesis on Probabilistic Systems}, volume = {326}, issn = {2075-2180}, url = {http://dx.doi.org/10.4204/EPTCS.326.11}, doi = {10.4204/eptcs.326.11}, journal = {Electronic Proceedings in Theoretical Computer Science}, publisher = {Open Publishing Association}, author = {Wells, Andrew M. and Lahijanian, Morteza and Kavraki, Lydia E. and Vardi, Moshe Y.}, year = {2020}, month = sep, pages = {166–181}, keywords = {planning from high-level specifications, uncertainty}, abstract = {Many systems are naturally modeled as Markov Decision Processes (MDPs), combining probabilities and strategic actions. Given a model of a system as an MDP and some logical specification of system behavior, the goal of synthesis is to find a policy that maximizes the probability of achieving this behavior. A popular choice for defining behaviors is Linear Temporal Logic (LTL). Policy synthesis on MDPs for properties specified in LTL has been well studied. LTL, however, is defined over infinite traces, while many properties of interest are inherently finite. Linear Temporal Logic over finite traces (LTLf) has been used to express such properties, but no tools exist to solve policy synthesis for MDP behaviors given finite-trace properties. We present two algorithms for solving this synthesis problem: the first via reduction of LTLf to LTL and the second using native tools for LTLf. We compare the scalability of these two approaches for synthesis and show that the native approach offers better scalability compared to existing automaton generation tools for LTL.} }
@inproceedings{he2019efficient-symbolic-reactive-synthesis-for-finite-horizon-tasks, abstract = {When humans and robots perform complex tasks together, the robot must have a strategy to choose its actions based on observed human behavior. One well-studied approach for finding such strategies is reactive synthesis. Existing ap- proaches for finite-horizon tasks have used an explicit state approach, which incurs high runtime. In this work, we present a compositional approach to perform synthesis for finite- horizon tasks based on binary decision diagrams. We show that for pick-and-place tasks, the compositional approach achieves exponential speed-ups compared to previous approaches. We demonstrate the synthesized strategy on a UR5 robot.}, author = {He, Keliang and Wells, Andrew M. and Kavraki, Lydia E. and Vardi, Moshe Y.}, booktitle = {Proceedings of the {IEEE} International Conference on Robotics and Automation}, month = may, title = {Efficient Symbolic Reactive Synthesis for Finite-Horizon Tasks}, year = {2019}, pages = {8993--8999}, note = {(Best paper award in Cognitive Robotics)}, keywords = {planning from high-level specifications}, doi = {10.1109/ICRA.2019.8794170} }
@inproceedings{hernandez2019lazy-evaluation-of-goal-specifications, abstract = {Nowadays robotic systems are expected to share workspaces and collaborate with humans. In such collaborative environments, an important challenge is to ground or establish the correct semantic interpretation of a human request. Once such an interpretation is available, the request must be translated into robot motion commands in order to complete the desired task. Nonetheless, there are some cases in which a human request cannot be grounded to a unique interpretation, thus leading to an ambiguous request. A simple example could be to ask a robot to ``put a cup on the table,'' where multiple cups are available. In order to deal with this kind of ambiguous request, and therefore, to make the human-robot interaction easy and as seamless as possible, we propose a delayed or lazy variable grounding. Our approach uses a motion planner, which considers and determines the feasibility of the different valid groundings by representing them with goal regions. This new approach also includes a reward-penalty strategy, which attempts to prioritize those goal regions that are more promising to provide a final solution. We validate our approach by solving requests with multiple valid alternatives in both simulation and real-world experiments.}, author = {Hern{\'a}ndez, Juan David and Moll, Mark and Kavraki, Lydia E.}, booktitle = {Proceedings of the {IEEE} International Conference on Robotics and Automation}, month = may, title = {Lazy Evaluation of Goal Specifications Guided by Motion Planning}, year = {2019}, pages = {944--950}, keywords = {planning from high-level specifications, fundamentals of sampling-based motion planning}, doi = {10.1109/ICRA.2019.8793570} }
@inproceedings{vidal2019online-multilayered-motion-planning, abstract = {Underwater robots are subject to complex hydrodynamic forces. These forces define how the vehicle moves, so it is important to consider them when planning trajectories. However, performing motion planning considering the dynamics on the robot's onboard computer is challenging due to the limited computational resources available. In this paper an efficient motion planning framework for AUV is presented. By introducing a loosely coupled multilayered planning design, our framework is able to generate dynamically feasible trajectories while keeping the planning time low enough for online planning. First, a fast path planner operating in a lower-dimensional projected space computes a lead path from the start to the goal configuration. Then, the lead path is used to bias the sampling of a second motion planner, which takes into account all the dynamic constraints. Furthermore, we propose a strategy for online planning that saves computational resources by generating the final trajectory only up to a finite horizon. By using the finite horizon strategy together with the multilayered approach, the sampling of the second planner focuses on regions where good quality solutions are more likely to be found, significantly reducing the planning time. To provide strong safety guarantees our framework also incorporates the conservative approximations of ICS. Finally, we present simulations and experiments using a real underwater robot to demonstrate the capabilities of our framework.}, author = {Vidal Garcia, Eduard and Moll, Mark and Palomeras, Narcis and Hern{\'a}ndez, Juan David and Carreras, Marc and Kavraki, Lydia E.}, booktitle = {{IEEE} International Conference on Robotics and Automation}, month = may, title = {Online Multilayered Motion Planning with Dynamic Constraints for Autonomous Underwater Vehicles}, year = {2019}, pages = {8936--8942}, note = {(Top-3 finalist for best student paper award)}, keywords = {planning from high-level specifications, kinodynamic systems}, doi = {10.1109/ICRA.2019.8794009} }
@article{wang2019point-based-policy, abstract = {Effectively planning robust executions under uncertainty is critical for building autonomous robots. Partially Observable Markov Decision Processes (POMDPs) provide a standard framework for modeling many robot applications under uncertainty. We study POMDPs with two kinds of objectives: (1) boolean objectives for a correctness guarantee of accomplishing tasks and (2) quantitative objectives for optimal behaviors. For robotic domains that require both correctness and optimality, POMDPs with boolean and quantitative objectives are natural formulations. We present a practical policy synthesis approach for POMDPs with boolean and quantitative objectives by combining policy iteration and policy synthesis for POMDPs with only boolean objectives. To improve efficiency, our approach produces approximate policies by performing the point-based backup on a small set of representative beliefs. Despite being approximate, our approach maintains validity (satisfying boolean objectives) and guarantees improved policies at each iteration before termination. Moreover, the error due to approximation is bounded. We evaluate our approach in several robotic domains. The results show that our approach produces good approximate policies that guarantee task completion.}, author = {Wang, Yue and Chaudhuri, Swarat and Kavraki, Lydia E.}, title = {Point-Based Policy Synthesis for {POMDP}s with Boolean and Quantitative Objectives}, journal = {IEEE Robotics and Automation Letters}, year = {2019}, volume = {4}, number = {2}, pages = {1860--1867}, month = apr, keywords = {planning from high-level specifications}, doi = {10.1109/LRA.2019.2898045} }
@article{he2019automated-abstraction-of-manipulation, author = {He, K. and Lahijanian, M. and Kavraki, L. E. and Vardi, Moshe Y.}, journal = {IEEE Robotics and Automation Letters}, title = {Automated Abstraction of Manipulation Domains for Cost-Based Reactive Synthesis}, year = {2019}, volume = {4}, number = {2}, pages = {285--292}, month = apr, abstract = {When robotic manipulators perform high-level tasks in the presence of another agent, e.g., a human, they must have a strategy that considers possible interferences in order to guarantee task completion and efficient resource usage. One approach to generate such strategies is called reactive synthesis. Reactive synthesis requires an abstraction, which is a discrete structure that captures the domain in which the robot and other agents operate. Existing works discuss the construction of abstractions for mobile robots through space decomposition; however, they cannot be applied to manipulation domains due to the curse of dimensionality caused by the manipulator and the objects. In this work, we present the first algorithm for automatic abstraction construction for reactive synthesis of manipulation tasks. We focus on tasks that involve picking and placing objects with possible extensions to other types of actions. The abstraction also provides an upper bound on path-based costs for robot actions. We combine this abstraction algorithm with our reactive synthesis planner to construct correct-by-construction plans. We demonstrate the power of the framework on examples of a UR5 robot completing complex tasks in face of interferences by a human.}, keywords = {planning from high-level specifications}, doi = {10.1109/LRA.2018.2889191} }
@article{wells2019learning-feasibility-for-tmp, abstract = {Task and motion planning (TMP) combines discrete search and continuous motion planning. Earlier work has shown that to efficiently find a task-motion plan, the discrete search can leverage information about the continuous geometry. However, incorporating continuous elements into discrete planners presents challenges. We improve the scalability of TMP algorithms in tabletop scenarios with a fixed robot by introducing geometric knowledge into a constraint-based task planner in a robust way. The key idea is to learn a classifier for feasible motions and to use this classifier as a heuristic to order the search for a task-motion plan. The learned heuristic guides the search towards feasible motions and thus reduces the total number of motion planning attempts. A critical property of our approach is allowing robust planning in diverse scenes. We train the classifier on minimal exemplar scenes and then use principled approximations to apply the classifier to complex scenarios in a way that minimizes the effect of errors. By combining learning with planning, our heuristic yields order-of-magnitude run time improvements in diverse tabletop scenarios. Even when classification errors are present, properly biasing our heuristic ensures we will have little computational penalty}, author = {Wells, Andrew M. and Dantam, Neil T. and Shrivastava, Anshumali and Kavraki, Lydia E.}, title = {Learning Feasibility for Task and Motion Planning in Tabletop Environments}, journal = {IEEE Robotics and Automation Letters}, year = {2019}, keywords = {planning from high-level specifications}, volume = {4}, number = {2}, month = apr, pages = {1255--1262}, doi = {10.1109/LRA.2019.2894861}, note = {PMID: 31058229, PMCID: PMC6491048} }
@article{lagriffoul2018tmp-benchmarks, abstract = {We present the first platform-independent evaluation method for task and motion planning (TAMP). Previously point, various problems have been used to test individual planners for specific aspects of TAMP. However, no common set of metrics, formats, and problems have been accepted by the community. We propose a set of benchmark problems covering the challenging aspects of TAMP and a planner-independent specification format for these problems. Our objective is to better evaluate and compare TAMP planners, foster communication, and progress within the field, and lay a foundation to better understand this class of planning problems.}, author = {Lagriffoul, Fabien and Dantam, Neil and Garrett, Caelan and Akbari, Aliakbar and Srivastava, Siddharth and Kavraki, Lydia E.}, title = {Platform-Independent Benchmarks for Task and Motion Planning}, journal = {IEEE Robotics and Automation Letters}, year = {2018}, month = oct, volume = {3}, issue = {4}, pages = {3765--3772}, doi = {10.1109/LRA.2018.2856701}, keywords = {planning from high-level specifications; uncertainty} }
@article{dantam2018task-motion-kit, abstract = {Robots require novel reasoning systems to achieve complex objectives in new environments. Daily activities in the physical world combine two types of reasoning: discrete and continuous. For example, to set the table, the robot must make discrete decisions about which and in what order to pick objects, and it must execute these decisions by computing continuous motions to reach objects or desired locations. Robotics has traditionally treated these issues in isolation. Reasoning about discrete events is referred to as task planning, while reasoning about and computing continuous motions is in the realm of motion planning. However, several recent works have shown that separating task planning from motion planning is problematic. This article provides an introduction to task-motion planning (TMP), this concept tightly couples task planning and motion planning, producing a sequence of steps that can actually be executed by a real robot. The implementation and use of an open-source TMP framework tht is adaptable to new robots is also discussed.}, author = {Dantam, Neil T. and Chaudhuri, Swarat and Kavraki, Lydia E.}, title = {The Task Motion Kit}, journal = {Robotics and Automation Magazine}, publisher = {IEEE}, year = {2018}, volume = {25}, number = {3}, month = sep, pages = {61--70}, doi = {10.1109/MRA.2018.2815081}, keywords = {planning from high-level specifications} }
@inproceedings{wang2018partial, title = {Online Partial Conditional Plan Synthesis for POMDPs with Safe-Reachability Objectives}, booktitle = {Workshop on the Algorithmic Foundations of Robotics}, year = {2018}, keywords = {planning from high-level specifications; uncertainty}, author = {Wang, Yue and Chaudhuri, Swarat and Kavraki, Lydia E.}, abstract = {The framework of Partially Observable Markov Decision Processes (POMDPs) offers a standard approach to model uncertainty in many robot tasks. Traditionally, POMDPs are formulated with optimality objectives. However, for robotic domains that require a correctness guarantee of accomplishing tasks, boolean objectives are natural formulations. We study POMDPs with a common boolean objective: safe-reachability, which requires that, with a probability above a threshold, the robot eventually reaches a goal state while keeping the probability of visiting unsafe states below a different threshold. The solutions to POMDPs are policies or conditional plans that specify the action to take contingent on every possible event. A full policy or conditional plan that covers all possible events is generally expensive to compute. To improve efficiency, we introduce the notion of partial conditional plans that only cover a sampled subset of all possible events. Our approach constructs a partial conditional plan parameterized by a replanning probability. We prove that the probability of the constructed partial conditional plan failing is bounded by the replanning probability. Our approach allows users to specify an appropriate bound on the replanning probability to balance efficiency and correctness. We validate our approach in several robotic domains. The results show that our approach outperforms a previous approach for POMDPs with safe-reachability objectives in these domains.} }
@inproceedings{wang2018bounded-policy-synthesis, abstract = {Planning robust executions under uncertainty is a fundamental challenge for building autonomous robots. Partially Observable Markov Decision Processes (POMDPs) provide a standard framework for modeling uncertainty in many applications. In this work, we study POMDPs with safe-reachability objectives, which require that with a probability above some threshold, a goal state is eventually reached while keeping the probability of visiting unsafe states below some threshold. This POMDP formulation is different from the traditional POMDP models with optimality objectives and we show that in some cases, POMDPs with safe-reachability objectives can provide a better guarantee of both safety and reachability than the existing POMDP models through an example. A key algorithmic problem for POMDPs is policy synthesis, which requires reasoning over a vast space of beliefs (probability distributions). To address this challenge, we introduce the notion of a goal-constrained belief space, which only contains beliefs reachable from the initial belief under desired executions that can achieve the given safe-reachability objective. Our method compactly represents this space over a bounded horizon using symbolic constraints, and employs an incremental Satisfiability Modulo Theories (SMT) solver to efficiently search for a valid policy over it. We evaluate our method using a case study involving a partially observable robotic domain with uncertain obstacles. The results show that our method can synthesize policies over large belief spaces with a small number of SMT solver calls by focusing on the goal-constrained belief space.}, address = {Stockholm, Sweden}, author = {Wang, Yue and Chaudhuri, Swarat and Kavraki, Lydia E.}, keywords = {planning from high-level specifications; uncertainty}, booktitle = {Proceedings of the 17th International Conference on Autonomous Agents and Multiagent Systems}, series = {AAMAS 2018}, title = {Bounded Policy Synthesis for {POMDP}s with Safe-Reachability Objectives}, year = {2018}, url = {http://dl.acm.org/citation.cfm?id=3237383.3237424}, acmid = {3237424}, pages = {238--246} }
@article{dantam2018incremental-tmp, abstract = {We present a new constraint-based framework for task and motion planning (TMP). Our approach is extensible, probabilistically-complete, and offers improved performance and generality compared to a similar, state-of-the-art planner. The key idea is to leverage incremental constraint solving to efficiently incorporate geometric information at the task level. Using motion feasibility information to guide task planning improves scalability of the overall planner. Our key abstractions address the requirements of manipulation and object rearrangement. We validate our approach on a physical manipulator and evaluate scalability on scenarios with many objects and long plans, showing order-of-magnitude gains compared to the benchmark planner and improved scalability from additional geometric guidance. Finally, in addition to describing a new method for TMP and its implementation on a physical robot, we also put forward requirements and abstractions for the development of similar planners in the future.}, title = {An Incremental Constraint-Based Framework for Task and Motion Planning}, journal = {International Journal of Robotics Research, vol. 37, no. 10, pp. 1134-1151. (Invited Article)}, year = {2018}, author = {Dantam, Neil T. and Kingston, Zachary K. and Chaudhuri, Swarat and Kavraki, Lydia E.}, doi = {10.1177/0278364918761570}, keywords = {planning from high-level specifications} }
@inproceedings{he-lahijanian2017reactive-manipulation, title = {Reactive Synthesis For Finite Tasks Under Resource Constraints}, booktitle = {2017 IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS)}, year = {2017}, month = sep, pages = {5326-5332}, publisher = {IEEE}, address = {Vancouver, BC}, abstract = {There are many applications where robots have to operate in environments that other agents can change. In such cases, it is desirable for the robot to achieve a given high- level task despite interference. Ideally, the robot must decide its next action as it observes the changes in the world, i.e. act reactively. In this paper, we consider a reactive planning problem for finite robotic tasks with resource constraints. The task is represented using a temporal logic for finite behaviors and the robot must achieve the task using limited resources under all possible finite sequences of moves of other agents. We present a formulation for this problem and an approach based on quantitative games. The efficacy of the approach is demonstrated through a manipulation case study.}, keywords = {planning from high-level specifications}, doi = {10.1109/IROS.2017.8206426}, author = {He, Keliang and Lahijanian, Morteza and Kavraki, Lydia E. and Vardi, Moshe Y.} }
@inproceedings{baker2017robonaut-2-and-you, abstract = {Crew time is a precious resource due to the expense of trained human operators in space. Efficient caretaker robots could lessen the manual labor load required by frequent vehicular and life support maintenance tasks, freeing astronaut time for scientific mission objectives. Humanoid robots can fluidly exist alongside human counterparts due to their form, but they are complex and high-dimensional platforms. This paper describes a system that human operators can use to maneuver Robonaut 2 (R2), a dexterous humanoid robot developed by NASA to research co-robotic applications. The system includes a specification of constraints used to describe operations, and the supporting planning framework that solves constrained problems on R2 at interactive speeds. The paper is developed in reference to an illustrative, typical example of an operation R2 performs to highlight the challenges inherent to the problems R2 must face. Finally, the interface and planner is validated through a case-study using the guiding example on the physical robot in a simulated microgravity environment. This work reveals the complexity of employing humanoid caretaker robots and suggest solutions that are broadly applicable.}, address = {Austin, TX}, author = {Baker, William and Kingston, Zachary and Moll, Mark and Badger, Julia and Kavraki, Lydia E.}, booktitle = {Proceedings of the IEEE Workshop on Advanced Robotics and its Social Impacts (ARSO)}, keywords = {planning from high-level specifications}, title = {Robonaut 2 and You: Specifying and Executing Complex Operations}, doi = {10.1109/ARSO.2017.8025204}, year = {2017} }
@inproceedings{dantam2016tmp, author = {Dantam, Neil T. and Kingston, Zachary K. and Chaudhuri, Swarat and Kavraki, Lydia E.}, title = {Incremental Task and Motion Planning: A Constraint-Based Approach}, booktitle = {Robotics: Science and Systems}, year = {2016}, abstract = {We present a new algorithm for task and motion planning (TMP) and discuss the requirements and abstractions necessary to obtain robust solutions for TMP in general. Our Iteratively Deepened Task and Motion Planning (IDTMP) method is probabilistically-complete and offers improved performance and generality compared to a similar, state-of-the-art, probabilistically-complete planner. The key idea of IDTMP is to leverage incremental constraint solving to efficiently add and remove constraints on motion feasibility at the task level. We validate IDTMP on a physical manipulator and evaluate scalability on scenarios with many objects and long plans, showing order-of-magnitude gains compared to the benchmark planner and a four-times self-comparison speedup from our extensions. Finally, in addition to describing a new method for TMP and its implementation on a physical robot, we also put forward requirements and abstractions for the development of similar planners in the future.}, keywords = {planning from high-level specifications}, doi = {10.15607/RSS.2016.XII.002} }
@article{lahijanian2016iterative, author = {Lahijanian, Morteza and Maly, Matthew R. and Fried, Dror and Kavraki, Lydia E. and Kress-Gazit, Hadas and Vardi, Moshe Y.}, title = {Iterative Temporal Planning in Uncertain Environments with Partial Satisfaction Guarantees}, year = {2016}, journal = {IEEE Transactions on Robotics}, volume = {32}, number = {3}, pages = {583-599}, doi = {10.1109/TRO.2016.2544339}, abstract = {This work introduces a motion-planning framework for a hybrid system with general continuous dynamics to satisfy a temporal logic specification consisting of co-safety and safety components in a partially unknown environment. The framework employs a multi-layered synergistic planner to generate trajectories that satisfy the specification and adopts an iterative replanning strategy to deal with unknown obstacles. When the discovery of an obstacle renders the specification unsatisfiable, a division between the constraints in the specification is considered. The co-safety component of the specification is treated as a soft constraint, whose partial satisfaction is allowed, while the safety component is viewed as a hard constraint, whose violation is forbidden. To partially satisfy the co-safety component, inspirations are taken from indoor-robotic scenarios, and three types of (unexpressed) restrictions on the ordering of sub-tasks in the specification are considered. For each type, a partial satisfaction method is introduced, which guarantees the generation of trajectories that do not violate the safety constraints while attending to partially satisfying the co-safety requirements with respect to the chosen restriction type. The efficacy of the framework is illustrated through case studies on a hybrid car-like robot in an office environment.}, keywords = {planning from high-level specifications} }
@inproceedings{wang2016task, author = {Wang, Yue and Dantam, Neil T. and Chaudhuri, Swarat and Kavraki, Lydia E.}, title = {Task and Motion Policy Synthesis as Liveness Games}, booktitle = {Proceedings of the International Conference on Automated Planning and Scheduling}, publisher = {AAAI}, year = {2016}, abstract = {We present a novel and scalable policy synthesis approach for robots. Rather than producing single-path plans for a static environment, we consider changing environments with uncontrollable agents, where the robot needs a policy to respond correctly over the infinite-horizon interaction with the environment. Our approach operates on task and motion domains, and combines actions over discrete states with continuous, collision-free paths. We synthesize a task and motion policy by iteratively generating a candidate policy and verifying its correctness. For efficient policy generation, we use grammars for potential policies to limit the search space and apply domain-specific heuristics to generalize verification failures, providing stricter constraints on policy candidates. For efficient policy verification, we construct compact, symbolic constraints for valid policies and employ a Satisfiability Modulo Theories (SMT) solver to check the validity of these constraints. Furthermore, the SMT solver enables quantitative specifications such as energy limits. The results show that our approach offers better scalability compared to a state-of-the-art policy synthesis tool in the tested benchmarks and demonstrate an order-of-magnitude speedup from our heuristics for the tested mobile manipulation domain.}, keywords = {planning from high-level specifications}, url = {http://www.aaai.org/ocs/index.php/ICAPS/ICAPS16/paper/view/13146}, pages = {536-540} }
@inproceedings{he-lahijanian2015towards-manipulation-planning, title = {Towards Manipulation Planning with Temporal Logic Specifications}, booktitle = {Proceedings of the 2015 IEEE International Conference on Robotics and Automation (ICRA)}, year = {2015}, month = may, pages = {346--352}, publisher = {IEEE}, address = {Seattle, WA}, abstract = {Manipulation planning from high-level task specifications, even though highly desirable, is a challenging problem. The large dimensionality of manipulators and complexity of task specifications make the problem computationally intractable. This work introduces a manipulation planning framework with linear temporal logic (LTL) specifications. The use of LTL as the specification language allows the expression of rich and complex manipulation tasks. The framework deals with the state-explosion problem through a novel abstraction technique. Given a robotic system, a workspace consisting of obstacles, manipulable objects, and locations of interest, and a co-safe LTL specification over the objects and locations, the framework computes a motion plan to achieve the task through a synergistic multi-layered planning architecture. The power of the framework is demonstrated through case studies, in which the planner efficiently computes plans for complex tasks. The case studies also illustrate the ability of the framework in intelligently moving away objects that block desired executions without requiring backtracking.}, keywords = {planning from high-level specifications}, doi = {10.1109/ICRA.2015.7139022}, author = {He, Keliang and Lahijanian, Morteza and Kavraki, Lydia E. and Vardi, Moshe Y.} }
@inproceedings{nedunuri-prabhu2014smt-based-synthesis-of, title = {{SMT}-Based Synthesis of Integrated Task and Motion Plans for Mobile Manipulation}, booktitle = {Proceedings of the IEEE International Conference on Robotics and Automation}, year = {2014}, pages = {655-662}, abstract = {Satisfiability Modulo Theories (SMT) solvers have recently emerged as a core technology in automated reasoning about systems. In this paper, we demonstrate the utility of these solvers in integrated task and motion planning (ITMP) for robots performing mobile manipulation. Specifically, we present a system{\textendash}-called ROBOSYNTH{\textendash}-for integrated task and motion planning that uses discrete search based on SMT-solvers as a complement to motion planning algorithms. As far as we know, this is the first application of SMT-solving in ITMP. The inputs to our version of ITMP are: (1) a scene description that specifies the physical space that the robot manipulates; (2) a plan outline that syntactically defines a space of plausible integrated plans; and (3) a set of logical requirements that we want the generated plan to satisfy. Given these inputs, our method uses a motion planning algorithm to construct a discrete placement graph whose paths represent feasible, low-level motion plans. An SMT-solver is now used to symbolically explore the space of all integrated plans that correspond to paths in the placement graph, and also satisfy the constraints demanded by the plan outline and the requirements. We have evaluated our approach on a generalization of an ITMP problem investigated in prior work. The experiments demonstrate that our method is capable of generating inte- grated plans that are interesting in a qualitative sense. We also find the method to scale well with an increase in the number of objects and locations manipulated, as well as the size of the space of plausible integrated plans.}, keywords = {planning from high-level specifications}, doi = {10.1109/ICRA.2014.6906924}, author = {Nedunuri, Srinivas and Prabhu, Sailesh and Moll, Mark and Chaudhuri, Swarat and Kavraki, Lydia E} }
@inproceedings{maly-lahijanian2013iterative-temporal-motion, title = {Iterative Temporal Motion Planning for Hybrid Systems in Partially Unknown Environments}, booktitle = {ACM International Conference on Hybrid Systems: Computation and Control (HSCC)}, year = {2013}, month = apr, pages = {353-362}, publisher = {ACM}, address = {Philadelphia, PA, USA}, abstract = {This paper considers the problem of motion planning for a hybrid robotic system with complex and nonlinear dynamics in a partially unknown environment given a temporal logic specification. We employ a multi-layered synergistic framework that can deal with general robot dynamics and combine it with an iterative planning strategy. Our work allows us to deal with the unknown environmental restrictions only when they are discovered and without the need to repeat the computation that is related to the temporal logic specification. In addition, we define a metric for satisfaction of a specification. We use this metric to plan a trajectory that satisfies the specification as closely as possible in cases in which the discovered constraint in the environment renders the specification unsatisfiable. We demonstrate the efficacy of our framework on a simulation of a hybrid second-order car-like robot moving in an office environment with unknown obstacles. The results show that our framework is successful in generating a trajectory whose satisfaction measure of the specification is optimal. They also show that, when new obstacles are discovered, the reinitialization of our framework is computationally inexpensive.}, keywords = {planning from high-level specifications}, doi = {10.1145/2461328.2461380}, author = {Maly, MR and Lahijanian, M and Kavraki, Lydia E and Kress-Gazit, H. and Vardi, Moshe Y.} }
@article{plaku-kavraki2013falsification-of-ltl, title = {Falsification of {LTL} safety properties in hybrid systems}, journal = {International Journal on Software Tools for Technology Transfer (STTT)}, volume = {15}, number = {4}, year = {2013}, pages = {305-320}, publisher = {Springer Berlin / Heidelberg}, keywords = {planning from high-level specifications}, issn = {1433-2779}, doi = {10.1007/s10009-012-0233-2}, author = {Plaku, E. and Kavraki, Lydia E and Vardi, Moshe Y.} }
@inproceedings{grady-moll2012multi-objective-sensor-based-replanning, title = {Multi-Objective Sensor-Based Replanning for a Car-Like Robot}, booktitle = {IEEE International Symposium on Safety, Security, and Rescue Robotics}, year = {2012}, month = nov, pages = {1--6}, publisher = {IEEE}, address = {College Station, TX}, abstract = {In search and rescue applications it is important that mobile ground robots can verify whether a potential target/victim is indeed a target of interest. This paper describes a novel approach to multi-robot target verification of multiple static objects. Suppose a team of multiple mobile ground robots are operating in a partially known environment with knowledge of possible target locations and obstacles. The ground robots{\textquoteright} goal is to (a) collectively classify the targets (or build models of them) by identifying good viewpoints to sense the targets, while (b) coordinating their actions to execute the mission and always be safe by avoiding obstacles and each other. As opposed to a traditional next-best-view (NBV) algorithm that generates a single good view, we characterize the informativeness of all potential views. We propose a measure for the informativeness of a view that exploits the geometric structure of the pose manifold. This information is encoded in a cost map that guides a multi-robot motion planning algorithm towards views that are both reachable and informative. Finally, we account for differential constraints in the robots{\textquoteright} motion that prevent unrealistic scenarios such as the robots stopping or turning instantaneously. A range of simulations indicates that our approach outperforms current approaches and demonstrates the advantages of predictive sensing and accounting for reachability constraints.}, keywords = {planning from high-level specifications, uncertainty}, isbn = {978-1-4799-0164-7}, doi = {10.1109/SSRR.2012.6523898}, author = {Grady, Devin K and Moll, Mark and Hegde, Chinmay and Sankaranarayanan, Aswin C. and Baraniuk, Richard G. and Kavraki, Lydia E} }
@inproceedings{grady-moll2012multi-robot-target-verification, title = {Multi-Robot Target Verification with Reachability Constraints}, booktitle = {IEEE International Symposium on Safety, Security, and Rescue Robotics}, year = {2012}, month = nov, pages = {1--6}, publisher = {IEEE}, address = {College Station, TX}, abstract = {This paper studies a core problem in multi-objective mission planning for robots governed by differential constraints. The problem considered is the following. A car-like robot computes a plan to move from a start configuration to a goal region. The robot is equipped with a sensor that can alert it if an anomaly appears within some range while the robot is moving. In that case, the robot tries to deviate from its computed path and gather more information about the target without incurring considerable delays in fulfilling its primary mission, which is to move to its final destination. This problem is important in, e.g., surveillance, where inspection of possible threats needs to be balanced with completing a nominal route. The paper presents a simple and intuitive framework to study the trade-offs present in the above problem. Our work utilizes a state-of-the-art sampling-based planner, which employs both a high-level discrete guide and low-level planning. We show that modifications to the distance function used by the planner and to the weights that the planner employs to compute the high-level guide can help the robot react online to new secondary objectives that were unknown at the outset of the mission. The modifications are computed using information obtained from a conventional camera model. We find that for small percentage increases in path length, the robot can achieve significant gains in information about an unexpected target.}, keywords = {planning from high-level specifications, uncertainty}, isbn = {978-1-4799-0164-7}, doi = {10.1109/SSRR.2012.6523873}, author = {Grady, Devin K and Moll, Mark and Hegde, Chinmay and Sankaranarayanan, Aswin C. and Baraniuk, Richard G. and Kavraki, Lydia E} }
@inproceedings{maly-kavraki2012low-dimensional-projections-for, title = {Low-Dimensional Projections for SyCLoP}, booktitle = {IEEE/RSJ International Conference on Intelligent Robots and Systems}, year = {2012}, month = oct, pages = {420-425}, address = {Vilamoura, Algarve, Portugal}, abstract = {This paper presents an extension to SyCLoP, a multilayered motion planning framework that has been shown to successfully solve high-dimensional problems with differen- tial constraints. SyCLoP combines traditional sampling-based planning with a high-level decomposition of the workspace through which it attempts to guide a low-level tree of motions. We investigate a generalization of SyCLoP in which the high- level decomposition is defined over a given low-dimensional projected subspace of the state space. We begin with a manually-chosen projection to demonstrate that projections other than the workspace can potentially work well. We then evaluate SyCLoP{\textquoteright}s performance with random projections and projections determined from linear dimensionality reduction over elements of the state space, for which the results are mixed. As we will see, finding a useful projection is a difficult problem, and we conclude this paper by discussing the merits and drawbacks of various types of projections.}, keywords = {planning from high-level specifications}, doi = {10.1109/IROS.2012.6386202}, author = {Maly, MR and Kavraki, Lydia E} }
@inproceedings{sucan-kavraki2012accounting-for-uncertainty, title = {Accounting for Uncertainty in Simultaneous Task and Motion Planning Using Task Motion Multigraphs}, booktitle = {IEEE International Conference on Robotics and Automation}, year = {2012}, month = may, pages = {4822-4828}, address = {St. Paul}, abstract = {This paper describes an algorithm that considers uncertainty while solving the simultaneous task and motion planning (STAMP) problem. Information about uncertainty is transferred to the task planning level from the motion planning level using the concept of a task motion multigraph (TMM). TMMs were introduced in previous work to improve the efficiency of solving the STAMP problem for mobile manipulators. In this work, Markov Decision Processes are used in conjunction with TMMs to select sequences of actions that solve the STAMP problem such that the resulting solutions have higher probability of feasibility. Experimental evaluation indicates significantly improved probability of feasibility for solutions to the STAMP problem, compared to algorithms that ignore uncertainty information when selecting possible sequences of actions. At the same time, the efficiency due to TMMs is largely maintained.}, keywords = {planning from high-level specifications, uncertainty}, doi = {10.1109/ICRA.2012.6224885}, author = {Sucan, Ioan Alexandru and Kavraki, Lydia E} }
@article{bhatia-maly2011motion-planning-with, title = {Motion Planning with Complex Goals}, journal = {Robotics Automation Magazine, IEEE}, volume = {18}, number = {3}, year = {2011}, month = sep, pages = {55--64}, abstract = {This article describes approach for solving motion planning problems for mobile robots involving temporal goals. Traditional motion planning for mobile robotic systems involves the construction of a motion plan that takes the system from an initial state to a set of goal states while avoiding collisions with obstacles at all times. The motion plan is also required to respect the dynamics of the system that are typically described by a set of differential equations. A wide variety of techniques have been pro posed over the last two decades to solve such problems [1], [2].}, keywords = {planning from high-level specifications}, issn = {1070-9932}, doi = {10.1109/MRA.2011.942115}, author = {Bhatia, Amit and Maly, MR and Kavraki, Lydia E and Vardi, Moshe Y.} }
@inproceedings{sucan-kavraki2011on-advantages-of, title = {On the Advantages of Using Task Motion Multigraphs for Efficient Mobile Manipulation}, booktitle = {IEEE/RSJ International Conference on Intelligent Robots and Systems}, year = {2011}, pages = {4621-4626}, address = {San Francisco, CA}, keywords = {planning from high-level specifications}, doi = {10.1109/IROS.2011.6048260}, author = {Sucan, Ioan Alexandru and Kavraki, Lydia E} }
@inproceedings{sucan-kavraki2011mobile-manipulation-encoding, title = {Mobile Manipulation: Encoding Motion Planning Options Using Task Motion Multigraphs}, booktitle = {IEEE International Conference on Robotics and Automation}, year = {2011}, pages = {5492--5498}, address = {Shanghai, China}, keywords = {planning from high-level specifications}, doi = {10.1109/ICRA.2011.5980212}, author = {Sucan, Ioan Alexandru and Kavraki, Lydia E} }
@article{plaku-kavraki2010motion-planning-with, title = {Motion Planning with Dynamics by a Synergistic Combination of Layers of Planning}, journal = {IEEE Transactions on Robotics}, volume = {26}, number = {3}, year = {2010}, month = jun, pages = {469--482}, chapter = {469}, abstract = {To efficiently solve challenges related to motion-planning problems with dynamics, this paper proposes treating motion planning not just as a search problem in a continuous space but as a search problem in a hybrid space consisting of discrete and continuous components. A multilayered framework is presented which combines discrete search and sampling-based motion planning. This framework is called synergistic combination of layers of planning ( SyCLoP) hereafter. Discrete search uses a workspace decomposition to compute leads, i.e., sequences of regions in the neighborhood that guide sampling-based motion planning during the state-space exploration. In return, information gathered by motion planning, such as progress made, is fed back to the discrete search. This combination allows SyCLoP to identify new directions to lead the exploration toward the goal, making it possible to efficiently find solutions, even when other planners get stuck. Simulation experiments with dynamical models of ground and flying vehicles demonstrate that the combination of discrete search and motion planning in SyCLoP offers significant advantages. In fact, speedups of up to two orders of magnitude were obtained for all the sampling-based motion planners used as the continuous layer of SyCLoP.}, keywords = {kinodynamic systems, planning from high-level specifications}, doi = {10.1109/TRO.2010.2047820}, author = {Plaku, E. and Kavraki, Lydia E and Vardi, Moshe Y.} }
@inproceedings{bhatia-kavraki2010sampling-based-motion-planning, title = {Sampling-Based Motion Planning with Temporal Goals}, booktitle = {IEEE International Conference on Robotics and Automation}, year = {2010}, month = may, pages = { 2689-2696}, publisher = {IEEE}, address = {Anchorage, Alaska}, abstract = {This paper presents a geometry-based, multi-layered synergistic approach to solve motion planning problems for mobile robots involving temporal goals. The temporal goals are described over subsets of the workspace (called propositions) using temporal logic. A multi-layered synergistic framework has been proposed recently for solving planning problems involving significant discrete structure. In this framework, a high-level planner uses a discrete abstraction of the system and the exploration information to suggest feasible high-level plans. A low-level sampling-based planner uses the physical model of the system, and the suggested high-level plans, to explore the state-space for feasible solutions. In this paper, we advocate the use of geometry within the above framework to solve motion planning problems involving temporal goals. We present a technique to construct the discrete abstraction using the geometry of the obstacles and the propositions defined over the workspace. Furthermore, we show through experiments that the use of geometry results in significant computational speedups compared to previous work. Traces corresponding to trajectories of the system are defined employing the sampling interval used by the low-level algorithm. The applicability of the approach is shown for second-order nonlinear robot models in challenging workspace environments with obstacles, and for a variety of temporal logic specifications.}, keywords = {planning from high-level specifications}, isbn = {978-1-4244-5040-4}, doi = {10.1109/ROBOT.2010.5509503}, author = {Bhatia, Amit and Kavraki, Lydia E and Vardi, Moshe Y.} }
@inproceedings{bhatia-kavraki2010motion-planning-with, title = {Motion Planning with Hybrid Dynamics and Temporal Goals}, booktitle = {IEEE Conference on Decision and Control}, year = {2010}, pages = {1108-1115}, publisher = {IEEE}, address = {Atlanta, GA}, abstract = {In this paper, we consider the problem of motion planning for mobile robots involving discrete constraints on dynamics, and high-level temporal goals. The robot is modeled as a nonlinear hybrid system with the discrete transitions modeling the discrete constraints. We use a multi-layered synergistic framework that has been proposed recently for solving planning problems involving hybrid systems and high-level temporal goals. A high-level planner uses a user-defined discrete abstraction of the hybrid system as well as exploration information to suggest high-level plans. A low-level sampling-based planner uses the dynamics of the hybrid system and the suggested high-level plans to explore the state-space for feasible solutions. In our previous work, we have proposed a geometry-based approach for the construction of the discrete abstraction for the case when the robot is modeled as a continuous system. Here, we extend the approach for the construction of the discrete abstraction to the case when the robot is modeled as nonlinear hybrid system. To use the resulting abstraction more efficiently, we also propose a lazy-search approach for high-level planning that reduces the size of the search space by reusing previously constructed high-level plans for initializing the search. The new techniques are tested experimentally for second-order nonlinear hybrid robot models in challenging workspace environments with obstacles and for a variety of temporal logic specifications.}, keywords = {planning from high-level specifications}, doi = {10.1109/CDC.2010.5717440}, author = {Bhatia, Amit and Kavraki, Lydia E and Vardi, Moshe Y.} }
@inproceedings{plaku-kavraki2009falsification-of-ltl, title = {Falsification of {LTL} Safety Properties in Hybrid Systems}, booktitle = {Proceedings of the Conference on Tools and Algorithms for the Construction and Analysis of Systems (TACAS 2009)}, year = {2009}, address = {York, UK}, abstract = {This paper develops a novel computational method for the falsification of safety properties specified by syntactically safe linear temporal logic (LTL) formulas φ for hybrid systems with general nonlinear dynamics and input controls. The method is based on an effective combination of robot motion planning and model checking. Experiments on a hybrid robotic system benchmark with nonlinear dynamics show significant speedup over related work. The experiments also indicate significant speedup when using minimized DFA instead of non-minimized NFA, as obtained by standard tools, for representing the violating prefixes of φ.}, keywords = {planning from high-level specifications}, doi = {10.1007/s10009-012-0233-2}, author = {Plaku, E. and Kavraki, Lydia E and Vardi, Moshe Y.} }
@article{plaku-kavraki2009hybrid-systems-from, title = {Hybrid systems: from verification to falsification by combining motion planning and discrete search}, journal = {Formal Methods in System Design}, volume = {34}, year = {2009}, pages = {157-182}, abstract = {We propose HyDICE, Hybrid DIscrete Continuous Exploration, a multi-layered approach for hybrid-system falsification that combines motion planning with discrete search and discovers safety violations by computing witness tra jectories to unsafe states. The discrete search uses discrete transitions and a state-space decomposition to guide the motion planner during the search for witness tra jectories. Experiments on a nonlinear hybrid robotic system with over one million modes and experiments with an aircraft conflict-resolution protocol with high-dimensional continuous state spaces demonstrate the effectiveness of HyDICE. Comparisons to related work show computational speedups of up to two orders of magnitude.}, keywords = {planning from high-level specifications}, doi = {10.1007/s10703-008-0058-5}, author = {Plaku, E. and Kavraki, Lydia E and Vardi, Moshe Y.} }
@inproceedings{plaku-kavraki2008impact-of-workspace, title = {Impact of Workspace Decompositions on Discrete Search Leading Continuous Exploration (DSLX) Motion Planning}, booktitle = {IEEE International Conference on Robotics and Automation}, year = {2008}, month = may, pages = {3751-3756}, address = {Pasadena, CA}, abstract = {We have recently proposed DSLX, a motion planner that significantly reduces the computational time for solving challenging kinodynamic problems by interleaving continuous state-space exploration with discrete search on a workspace decomposition. An important but inadequately understood aspect of DSLX is the role of the workspace decomposition on the computational efficiency of the planner. Understanding this role is important for successful applications of DSLX to increasingly complex robotic systems. This work shows that the granularity of the workspace decomposition directly impacts computational efficiency: DSLX is faster when the decomposition is neither too fine- nor too coarse-grained. Finding the right level of granularity can require extensive fine-tuning. This work demonstrates that significant computational efficiency can instead be obtained with no fine-tuning by using conforming Delaunay triangulations, which in the context of DSLX provide a natural workspace decomposition that allows an efficient interplay between continuous state-space exploration and discrete search. The results of this work are based on extensive experiments on DSLX using grid, trapezoidal, and triangular decompositions of various granularities to solve challenging first and second-order kinodynamic motion-planning problems.}, keywords = {planning from high-level specifications}, doi = {10.1109/ROBOT.2008.4543786}, author = {Plaku, E. and Kavraki, Lydia E and Vardi, Moshe Y.} }
@incollection{plaku-kavraki2007hybrid-systems-from, title = {Hybrid Systems: From Verification to Falsification}, booktitle = {International Conference on Computer Aided Verification (CAV)}, volume = {4590}, year = {2007}, pages = {468--481}, publisher = {Lecture Notes in Computer Science, Springer-Verlag Heidelberg}, address = {Berlin, Germany}, abstract = {We propose HyDICE, Hybrid DIscrete Continuous Exploration, a multi-layered approach for hybrid-system testing that integrates continuous sampling-based robot motion planning with discrete searching. The discrete search uses the discrete transitions of the hybrid system and coarse-grained decompositions of the continuous state spaces or related projections to guide the motion planner during the search for witness trajectories. Experiments presented in this paper, using a hybrid system inspired by robot motion planning and with nonlinear dynamics associated with each of several thousand modes, provide an initial validation of HyDICE and demonstrate its promise as a hybrid-system testing method. Comparisons to related work show computational speedups of up to two orders of magnitude.}, keywords = {planning from high-level specifications}, doi = {10.1007/978-3-540-73368-3_48}, author = {Plaku, E. and Kavraki, Lydia E and Vardi, Moshe Y.} }
@article{conev2022-3phla-score, author = {Conev, Anja and Devaurs, Didier and Rigo, Mauricio M. and Antunes, Dinler A. and Kavraki, Lydia E.}, title = {3pHLA-score improves structure-based peptide-{HLA} binding affinity prediction}, journal = {Scientific Reports}, year = {2022}, month = jun, publisher = {Springer Science and Business Media {LLC}}, volume = {12}, number = {1}, doi = {10.1038/s41598-022-14526-x}, url = {https://doi.org/10.1038/s41598-022-14526-x}, keywords = {proteins and drugs}, abstract = {Binding of peptides to Human Leukocyte Antigen (HLA) receptors is a prerequisite for triggering immune response. Estimating peptide-HLA (pHLA) binding is crucial for peptide vaccine target identification and epitope discovery pipelines. Computational methods for binding affinity prediction can accelerate these pipelines. Currently, most of those computational methods rely exclusively on sequence-based data, which leads to inherent limitations. Recent studies have shown that structure-based data can address some of these limitations. In this work we propose a novel machine learning (ML) structure-based protocol to predict binding affinity of peptides to HLA receptors. For that, we engineer the input features for ML models by decoupling energy contributions at different residue positions in peptides, which leads to our novel per-peptide-position protocol. Using Rosetta’s ref2015 scoring function as a baseline we use this protocol to develop 3pHLA-score. Our per-peptide-position protocol outperforms the standard training protocol and leads to an increase from 0.82 to 0.99 of the area under the precision-recall curve. 3pHLA-score outperforms widely used scoring functions (AutoDock4, Vina, Dope, Vinardo, FoldX, GradDock) in a structural virtual screening task. Overall, this work brings structure-based methods one step closer to epitope discovery pipelines and could help advance the development of cancer and viral vaccines.} }
@article{antunes2020-hla-arena, author = {Antunes, Dinler A. and Abella, Jayvee R. and Hall-Swan, Sarah and Devaurs, Didier and Conev, Anja and Moll, Mark and Liz\'{e}e, Gregory and Kavraki, Lydia E.}, title = {{HLA}-{A}rena: a customizable environment for the structural modeling and analysis of peptide-{HLA} complexes for cancer immunotherapy}, abstract = {PURPOSE: HLA protein receptors play a key role in cellular immunity. They bind intracellular peptides and display them for recognition by T-cell lymphocytes. Because T-cell activation is partially driven by structural features of these peptide-HLA complexes, their structural modeling and analysis are becoming central components of cancer immunotherapy projects. Unfortunately, this kind of analysis is limited by the small number of experimentally determined structures of peptide-HLA complexes. Overcoming this limitation requires developing novel computational methods to model and analyze peptide-HLA structures. METHODS: Here we describe a new platform for the structural modeling and analysis of peptide-HLA complexes, called HLA-Arena, which we have implemented using Jupyter Notebook and Docker. It is a customizable environment that facilitates the use of computational tools, such as APE-Gen and DINC, which we have previously applied to peptide-HLA complexes. By integrating other commonly used tools, such as MODELLER and MHCflurry, this environment includes support for diverse tasks in structural modeling, analysis, and visualization. RESULTS: To illustrate the capabilities of HLA-Arena, we describe 3 example workflows applied to peptide-HLA complexes. Leveraging the strengths of our tools, DINC and APE-Gen, the first 2 workflows show how to perform geometry prediction for peptide-HLA complexes and structure-based binding prediction, respectively. The third workflow presents an example of large-scale virtual screening of peptides for multiple HLA alleles. CONCLUSION: These workflows illustrate the potential benefits of HLA-Arena for the structural modeling and analysis of peptide-HLA complexes. Because HLA-Arena can easily be integrated within larger computational pipelines, we expect its potential impact to vastly increase. For instance, it could be used to conduct structural analyses for personalized cancer immunotherapy, neoantigen discovery, or vaccine development.}, journal = {JCO Clinical Cancer Informatics}, year = {2020}, volume = {4}, pages = {623--636}, keywords = {fundamentals of protein modeling, proteins and drugs, other biomedical computing}, doi = {10.1200/CCI.19.00123}, note = {PMID: 32667823, PMCID: 7397777}, month = jul }
@article{abella2020-frontiers-random-forest, author = {Abella, Jayvee R. and Antunes, Dinler A. and Clementi, Cecilia and Kavraki, Lydia E.}, title = {Large-scale structure-based prediction of stable peptide binding to Class I HLAs using random forests}, abstract = {Prediction of stable peptide binding to Class I HLAs is an important component for designing immunotherapies. While the best performing predictors are based on machine learning algorithms trained on peptide-HLA (pHLA) sequences, the use of structure for training predictors deserves further exploration. Given enough pHLA structures, a predictor based on the residue-residue interactions found in these structures has the potential to generalize for alleles with little or no experimental data. We have previously developed APE-Gen, a modeling approach able to produce pHLA structures in a scalable manner. In this work we use APE-Gen to model over 150,000 pHLA structures, the largest dataset of its kind, which were used to train a structure-based pan-allele model. We extract simple, homogenous features based on residue-residue distances between peptide and HLA, and build a random forest model for predicting stable pHLA binding. Our model achieves competitive AUROC values on leave-one-allele-out validation tests using significantly less data when compared to popular sequence-based methods. Additionally, our model offers an interpretation analysis that can reveal how the model composes the features to arrive at any given prediction. This interpretation analysis can be used to check if the model is in line with chemical intuition, and we showcase particular examples. Our work is a significant step towards using structure to achieve generalizable and more interpretable prediction for stable pHLA binding.}, keywords = {fundamentals of protein modeling, proteins and drugs, other biomedical computing}, doi = {10.3389/fimmu.2020.01583}, note = {PMID: 32793224, PMCID: PMC7387700}, journal = {Frontiers in Immunology}, year = {2020}, volume = {11}, number = {1583}, month = jul }
@article{devaurs2019using-parallelized-incremental-meta-docking, author = {Devaurs, Didier and Antunes, Dinler A and Hall-Swan, Sarah and Mitchell, Nicole and Moll, Mark and Liz{\'e}e, Gregory and Kavraki, Lydia E}, journal = {BMC Molecular and Cell Biology}, title = {Using parallelized incremental meta-docking can solve the conformational sampling issue when docking large ligands to proteins}, volume = {20}, number = {1}, pages = {42}, month = sep, year = {2019}, keywords = {proteins and drugs}, doi = {10.1186/s12860-019-0218-z}, note = {PMID: 31488048, PMCID: PMC6729087}, abstract = {Background: Docking large ligands, and especially peptides, to protein receptors is still considered a challenge in computational structural biology. Besides the issue of accurately scoring the binding modes of a protein-ligand complex produced by a molecular docking tool, the conformational sampling of a large ligand is also often considered a challenge because of its underlying combinatorial complexity. In this study, we evaluate the impact of using parallelized and incremental paradigms on the accuracy and performance of conformational sampling when docking large ligands. We use five datasets of protein-ligand complexes involving ligands that could not be accurately docked by classical protein-ligand docking tools in previous similar studies. Results: Our computational evaluation shows that simply increasing the amount of conformational sampling performed by a protein-ligand docking tool, such as Vina, by running it for longer is rarely beneficial. Instead, it is more efficient and advantageous to run several short instances of this docking tool in parallel and group their results together, in a straightforward parallelized docking protocol. Even greater accuracy and efficiency are achieved by our parallelized incremental meta-docking tool, DINC, showing the additional benefits of its incremental paradigm. Using DINC, we could accurately reproduce the vast majority of the protein-ligand complexes we considered. Conclusions: Our study suggests that, even when trying to dock large ligands to proteins, the conformational sampling of the ligand should no longer be considered an issue, as simple docking protocols using existing tools can solve it. Therefore, scoring should currently be regarded as the biggest unmet challenge in molecular docking. Keywords: molecular docking; protein-ligand docking; protein-peptide docking; conformational sampling; scoring; parallelism; incremental protocol} }