@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}
}